單鏈表的基本操作

《單鏈表的基本操作》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、實(shí)驗(yàn)二：?jiǎn)捂湵淼幕静僮骶帉懸粋€(gè)完整的程序，實(shí)現(xiàn)單鏈表的建立、插入、刪除、輸出等基本操作。（1）建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表。（2）計(jì)算單鏈表的長(zhǎng)度，然后輸出單鏈表。（3）查找值為x的直接前驅(qū)結(jié)點(diǎn)q。（4）刪除值為x的結(jié)點(diǎn)。（5）把單向鏈表中元素逆置（不允許申請(qǐng)新的結(jié)點(diǎn)空間）。（6）已知單鏈表中元素遞增有序，請(qǐng)寫出一個(gè)高效的算法，刪除表中所有值大于mink且小于maxk的元素（若表中存在這樣的元素），同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度（注意：mink和maxk是給定的兩個(gè)參變量，他們的值可以和表中的元素相同，也可以不同）。（7）同（6）的條件，試寫

2、一高效的算法，刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同），同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法時(shí)間復(fù)雜度。（8）利用（1）建立的鏈表，實(shí)現(xiàn)將其分解成兩個(gè)鏈表，其中一個(gè)全部為奇數(shù)，另一個(gè)全部為偶數(shù)（盡量利用已知的存儲(chǔ)空間）。（9）在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別測(cè)試上述算法。#include#includetypedefstructnode{intdata;structnode*next;}Lnode,*LinkList;intm=sizeof(Lnode);//建立新的鏈表voidBuli

3、d_List(LinkListroot){intnum;LinkLists,p;s=root->next;intn;printf("請(qǐng)輸入新建鏈表的長(zhǎng)度n數(shù)據(jù):");scanf("%d",&n);printf("請(qǐng)依次建立鏈表：");for(inti=0;idata=num;p=(LinkList)malloc(m);s->next=p;s=p;s->next=NULL;}printf("鏈表已建立！");}//對(duì)鏈表的輸出，包括長(zhǎng)度和元素voidOutPut_list(LinkListroot

4、){intlen=0;LinkLists;s=root->next;if(s->next==NULL)printf("單鏈表無(wú)數(shù)據(jù)，請(qǐng)先新建單鏈表。");else{while(s->next!=NULL){s=s->next;len++;}printf("單鏈表的長(zhǎng)度為：%d",len);printf("單鏈表的數(shù)據(jù)如下:");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("單鏈表無(wú)數(shù)據(jù)，請(qǐng)先新建單鏈表。");else{s=root->next;p=root->next->next;if(s->data==x)printf("此X值無(wú)前驅(qū)結(jié)點(diǎn)。");else{while(p->next!=NULL){if(p->data==x){printf("此X值的前驅(qū)結(jié)點(diǎn)的值為：%d",s->data);return;}else{s=p;p=p->next;}}printf("此鏈表不存在值為X的結(jié)點(diǎn)。");}}return;

6、}voidDelete_list(LinkListroot,intx){LinkLists;intflag;if(root->next->next==NULL)printf("單鏈表無(wú)數(shù)據(jù)，請(qǐng)先新建單鏈表。");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("待刪除的數(shù)據(jù)不存在。");}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