单链表的基本操作.doc

实验二：单链表的基本操作编写一个完整的程序，实现单链表的建立、插入、删除、输出等基本操作。（1）建立一个带头结点的单链表。（2）计算单链表的长度，然后输出单链表。（3）查找值为x的直接前驱结点q。（4）删除值为x的结点。（5）把单向链表中元素逆置（不允许申请新的结点空间）。（6）已知单链表中元素递增有序，请写出一个高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，他们的值可以和表中的元素相同，也可以不同）。（7）同（6）的条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法时间复杂度。（8）利用（1）建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。（9）在主函数中设计一个简单的菜单，分别测试上述算法。# include # include typedef struct nodeint data;struct node * next;Lnode, * LinkList;int m=sizeof(Lnode); /建立新的链表void Bulid_List(LinkList root) int num;LinkList s,p;s=root-next;int n;printf(请输入新建链表的长度n数据:n);scanf(%d,&n);printf(请依次建立链表：);for(int i=0;idata=num;p=(LinkList)malloc(m);s-next=p;s=p;s-next=NULL;printf(链表已建立！n);/对链表的输出，包括长度和元素void OutPut_list(LinkList root) int len=0;LinkList s;s=root-next;if(s-next=NULL) printf(单链表无数据，请先新建单链表。n);elsewhile(s-next!=NULL) s=s-next;len+;printf(单链表的长度为：%dn,len);printf(单链表的数据如下:n);s=root-next;while(s-next!=NULL) printf(%d ,s-data);s=s-next;printf(n);void Find_list(LinkList root,int x) LinkList s,p;if(root-next-next=NULL) printf(单链表无数据，请先新建单链表。n);elses=root-next;p=root-next-next;if(s-data=x) printf(此X值无前驱结点。n);elsewhile(p-next!=NULL)if(p-data=x) printf(此X值的前驱结点的值为：%dn,s-data);return; elses=p;p=p-next;printf(此链表不存在值为X的结点。n);return;void Delete_list(LinkList root,int x) LinkList s;int flag; if(root-next-next=NULL) printf(单链表无数据，请先新建单链表。n);else flag=0;while(root-next!=NULL)if(root-next-data=x) if(root-next-next!=NULL)s=root-next;root-next=root-next-next;free(s);flag=1;return;elseroot=root-next;if(flag=0)printf(待删除的数据不存在。n);return;LinkList NEW()LinkList new_node;new_node=(LinkList)malloc(m);new_node-next=NULL;new_node-data=0;return new_node;/分解链表void Divid(LinkList head)LinkList head_odd,head_even,p_odd,p_even,p,s;head_odd=NEW();head_even=NEW();p=head-next;p_odd=head_odd;p_even=head_even;while(p!=NULL)s=p;p=p-next;if(s-data%2=0)p_odd-next=s;p_odd=p_odd-next;p_odd-next=NULL;elsep_even-next=s;p_even=p_even-next;p_even-next=NULL;printf(构建成功！n);printf(奇数链表为：);p=head_even-next;while(p-next!=NULL)printf(%d ,p-data);p=p-next;printf(n偶数链表为：);p=head_odd;while(p-next!=NULL)printf(%d ,p-next-data);p=p-next;printf(n);/6void DelteAndFree_list(LinkList root) LinkList s,p,t,k;int min,max;if(root=NULL) printf(单链表无数据，请先新建单链表。n);elseprintf(请输入所要min的值，max的值(min next;p=root;while(s-datanext;p=p-next;t=p;while(s-datanext;t=t-next;s=p-next; p-next=t-next-next;t-next=NULL;while(s-next!=NULL) k=s;s=s-next;free(k);free(s);return;void DeleteCommon_list(LinkList root) LinkList s,p,t;if(root-next-next=NULL) printf(单链表无数据，请先新建单链表。n);elses=root-next;p=root-next-next;while(p-next!=NULL)if(s-data=p-data) t=p;p=p-next;s-next=p;free(t);elses=s-next;p=p-next;return;void Reserve_list(LinkList root) /链表的逆置LinkList s,p,t;s=root-next;root-next=NULL;while(s-next!=NULL)p=s-next;s-next=root-next;root-next=s;s=p;LinkList head; head=(LinkList)malloc(m);head-next=NULL;t=root;while(t-next!=NULL)t=t-next;t-next=head;return;/打印菜单void print()printf(n菜单如下：n);printf(1.建立单链表n);printf(2.计算单链表的长度并输出n);printf(3.查找值为x的直接前驱结点qn);printf(4.删除值为x的节点n);printf(5.逆置单链表n);printf(6.将单链表递增排序后删除表中所有值大于mink且小于maxk的元素n);printf(7.将单链表递增排序后删除表中所有值相同的多余元素n);printf(8.分解单链表，一个为奇数，另一个为偶数n);printf(0.EXITnn);printf(请输入你选菜单的数字：n);/循环菜单int main(void)LinkList root;int x;root = (LinkList)malloc(m);root-next = NULL;root-next = (LinkList)malloc(m);root-next-next = NULL;bool flag;int op;print();/show_arr(&arr);while(scanf(%d,&op)!=EOF)flag=true;switch(op)case 0:flag=false;break;case 1:Bulid_List(root);break;case 2:OutPut_list(root);break;case 3:printf(请输入所要查找的x:n); scanf(%d,&x);Find_list(root,x);break;case 4:printf(请输入所要删除值x:n);scanf(%d,&x);Delete_list(root,x);break;case 5:Reserve_list(root);break;c