链式存储结构(一)——单向链表的有关操作.doc

链式存储结构(一)单向链表的有关操作实验目的：1、 掌握单向链表的存储特点及其实现。2、 掌握单向链表的插入、删除算法及其应用算法的程序实现。实验内容：1、 随机产生或键盘输入一组元素，建立一个带头结点的单向链表(无序)。2、 遍历单向链表。3、 把单向链表中元素逆置(不允许申请新的结点空间)。4、 在单向链表中删除所有的偶数元素结点。5、 编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。6、 利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。7、 利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。8、 利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，令一个全部为偶数(尽量利用已知的存储空间).9、 利用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。10、 在主函数中设计一个简单的菜单，分别调试上述算法。实现源代码：5#includestdio.h#includestdlib.htypedef int ElemType;/元素实际类型typedef struct LNodeElemtype data;struct LNode *next;LNode,*LinkList;/定义结点、指针类型名头插法建立无序链表void CreateList(LinkList &L)LinkList p;ElemType e;L=(LinkList)malloc(sizeof(LNode);L-next =NULL;printf(头插法建立链表，以0结束n);scanf(%d,&e);while(e)p=(LinkList)malloc(sizeof(LNode);p-data=e;p-next=L-next;L-next=p;scanf(%d,&e);/非递减有序单向链表L插入元素e序列仍有序void insert_Sort(LinkList &L,ElemType e)LinkList p,s;s=(LinkList)malloc(sizeof(LNode);s-data=e;p=L;while(P-next&p-next-datanext;/查找插入位置s-next=p-next;/插入语句*p结点插入*s结点p-next=s;/*建立递增有序单向链表*/void Create_Sort(LinkList &L)ElemType e;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;printf(建立有序表，输入任意个整型数据以0结束n);scanf(%d,&e);while(e)Insert_Sort(L,e);scanf(%d,&e);/*单向链表的遍历*/void Traverse(LinkList L)LinkList p;printf(遍历链表);for(p=L-next;p;p=p-next)printf(%5d,p-data);printf(n);/*在单向链表中删除元素e*/void Delete(LinkList &L,ElemType e)LinkList p,q;p=L;q=L-next;while(q&q-data!=e)p=q;q=q-next;if(!q)printf(nnot deleted);/*未找到元素e*/elsep-next=q-next;/找到删除free(q);/*单向链表的逆置*/void exch(LinkList &L)LinkList p,s;p=L-next;L-next=NULL;while(p)s=p;p=p-next;s-next =L-next;L-next=s;/*两个非递减有序单向链表合并后仍为非递减序列*/void MergeIncrease(LinkList La,LinkList Lb,LinkList &Lc)LinkList p,q,s,rear;p=La-next;q=Lb-next;Lc=rear=La;free(Lb);while(p&q)if(p-datanext)s=p;p=p-next;else s=q;q=q-next;rear-next=s;/*较小元素插入表尾*/rear=rear-next;if(p)rear-next=p;elserear-next=q;主函数：#includeLinkList.hvoid main()LinkList La,Lb,Lc;ElemType e;int select;doprintf( 1 建立无序表，再删除指定元素n);printf( 2 建立递增有序表，再逆置n);printf( 3 建立两个递增有序表，将它们合并为一个仍递增表n);printf( 0 退出，请输入选项（0-3）n);scanf(%d,&select);switch(select)case 0:break;case 1:CreateList(La);Traverse(La);printf(请输入需删除的元素n);scanf(%d,&e);Delete(La,e);Traverse(La);break;case 2:Create_Sort(La);Traverse(La);exch(La); printf(The list that is exchagedn);Traverse(La);break;case 3:Create_Sort(La);Traverse(La);Cr