单向链表.doc

数据结构实验报 告 实验目的： 1掌握单向链表的存储特点及其实现。 2掌握单向链表的插入、删除算法及其应用算法的程序实现。实验内容 1随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。 2遍历单向链表。 3把单向链表中元素逆置（不允许申请新的结点空间）。 4在单向链表中删除所有的偶数元素结点。 5编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。 6利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。 7利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。代码如下：/02.h#include #include#define LENGTH 10typedef int ElemType;typedef struct LNode ElemType data;struct LNode *next; LNode; void CreateList(LNode *L)int i;LNode *p;printf(头插法建立链表n);L-next=NULL;for(i=0;idata=rand();p-next=L-next;L-next=p;void SortInsert(ElemType e,LNode *L)LNode a,*p,*q;p=L-next ;q=L;a.data =e;a.next =NULL;while(p!=NULL)if(p-data=e)a.next =q-next ;q-next =&a;return;q=p;p=p-next;void Traveller(LNode *L)LNode *p;p=L-next;printf(链表为:n);if(p=NULL)printf(空！n);return;while(p!=NULL)printf(%d,p-data);p=p-next;void Sort(LNode *L)LNode *p,*q,*r;int temp;p=L-next;while (p!=NULL)q=p;r=p-next;while (r)if(q-datar-data)q=r;r=r-next;if(p!=q)temp=p-data;p-data=q-data;q-data=temp;p=p-next;printf(排序后的链表为:n);Traveller(L);void daozhi(LNode *L)LNode *p,*q;p=L-next-next;if(p!=NULL)q=L-next-next;p=p-next;L-next-next-next =L-next;L-next-next=NULL;L-next =q;while(p!=NULL)L-next =p;p=p-next;L-next -next =q;q=L-next ;printf(倒置后的线性链表为:n);Traveller(L);void FenJie(LNode *l1)LNode s1,s2,*s,*p;s1.next=NULL;s2.next=NULL;p=l1-next;if(p!=NULL)s=p-next;while (s!=NULL)if (p-data%2!=0)p-next=s1.next;s1.next=p;else p-next=s2.next; s2.next=p;p=s;s=s-next;printf(分解后的奇数链表为:n);Traveller(&s1);printf(分解后的偶数链表为:n);Traveller(&s2);void DelNode(ElemType e,LNode *l)LNode *p,*q;p=l-next ;q=l;while (p-next!=NULL)if (p-data =e)q-next =p-next ;free(p);printf(已经删除%d!n,e);return;q-next =p;p-next =p-next -next ;printf(%d不存在！,e);void Deletd_Os(LNode *l1)LNode *p,*q,*s;p=l1;q=l1-next;while (q)if (q-data%2=0)p-next=q-next;s=q;q=q-next;free(s);elsep=p-next;q=q-next;printf(删除偶数节点的线性链表为:n);Traveller(l1); /02.cpp #include #include#include02.h#define LENGTH 10void main()LNode l,*l1;int i,j;l.next =NULL;l1=&l;doprintf(n *); printf(n * 0 生成链表1 遍历输出 2 倒置 3 排序 4 奇偶分解*);printf(n * 5 有序插入6 输入建链 7 删除 8 删除偶数 *);printf(n *n);scanf(%d,&i);switch(i)case 0:CreateList(l1);Traveller(l1);break;case 1:Traveller(l1);break;case 2:daozhi(l1);break;case 3:Sort(l1);break;case 4:FenJie(l1);break;case 5:printf(请输入要插入的数：n);scanf(%d,&j);SortInsert(j,l1);Traveller(l1);break;case 6:for(i=0;i5;i+)scanf(%d,&j);SortInsert(j,l1);break;case 7:pr