单链表的基本操作

《单链表的基本操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验二：单链表的基本操作编写一个完整的程序，实现单链表的建立、插入、删除、输出等基本操作。（1）建立一个带头结点的单链表。（2）计算单链表的长度，然后输出单链表。（3）查找值为x的直接前驱结点q。（4）删除值为x的结点。（5）把单向链表中元素逆置（不允许申请新的结点空间）。（6）已知单链表中元素递增有序，请写出一个高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，他们的值可以和表中的元素相同，也可以不同）。（7）同（6）的条件，试写

2、一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法时间复杂度。（8）利用（1）建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。（9）在主函数中设计一个简单的菜单，分别测试上述算法。#include#includetypedefstructnode{intdata;structnode*next;}Lnode,*LinkList;intm=sizeof(Lnode);//建立新的链表voidBuli

3、d_List(LinkListroot){intnum;LinkLists,p;s=root->next;intn;printf("请输入新建链表的长度n数据:");scanf("%d",&n);printf("请依次建立链表：");for(inti=0;idata=num;p=(LinkList)malloc(m);s->next=p;s=p;s->next=NULL;}printf("链表已建立！");}//对链表的输出，包括长度和元素voidOutPut_list(LinkListroot

4、){intlen=0;LinkLists;s=root->next;if(s->next==NULL)printf("单链表无数据，请先新建单链表。");else{while(s->next!=NULL){s=s->next;len++;}printf("单链表的长度为：%d",len);printf("单链表的数据如下:");s=root->next;while(s->next!=NULL){printf("%d",s->data);s=s->next;}printf("");}}voidFind_list(LinkListroot,int

5、x){LinkLists,p;if(root->next->next==NULL)printf("单链表无数据，请先新建单链表。");else{s=root->next;p=root->next->next;if(s->data==x)printf("此X值无前驱结点。");else{while(p->next!=NULL){if(p->data==x){printf("此X值的前驱结点的值为：%d",s->data);return;}else{s=p;p=p->next;}}printf("此链表不存在值为X的结点。");}}return;

6、}voidDelete_list(LinkListroot,intx){LinkLists;intflag;if(root->next->next==NULL)printf("单链表无数据，请先新建单链表。");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;}i

7、f(flag==0)printf("待删除的数据不存在。");}return;}LinkListNEW(){LinkListnew_node;new_node=(LinkList)malloc(m);new_node->next=NULL;new_node->data=0;returnnew_node;}//分解链表voidDivid(LinkListhead){LinkListhead_odd,head_even,p_odd,p_even,p,s;head_odd=NEW();head_even=NEW();p=head->next;p_odd=hea

8、d_odd;p_even=head_even;whi