《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)三報(bào)告13網(wǎng)二吳睿

江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告專(zhuān)業(yè)_網(wǎng)絡(luò)工程2班姓名_吳睿_學(xué)號(hào)1308093095日期__2014.10.30課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)室名稱(chēng)X4313c實(shí)驗(yàn)名稱(chēng)帶頭結(jié)點(diǎn)的單鏈表指導(dǎo)教師左正康成績(jī)實(shí)驗(yàn)?zāi)康睦斫鈳ь^結(jié)點(diǎn)的單鏈表的特點(diǎn)，掌握采用這種數(shù)據(jù)結(jié)構(gòu)的算法設(shè)計(jì)熟練掌握運(yùn)用帶頭結(jié)點(diǎn)鏈表表示特定形式的數(shù)據(jù)的方法，并設(shè)計(jì)出有關(guān)算法實(shí)驗(yàn)原理和內(nèi)容基于slnklist.h文件中定義的單鏈表表，完成實(shí)驗(yàn)1~9。實(shí)驗(yàn)：編寫(xiě)函數(shù)voiddelx(linklisthead,datatypex)，刪除帶頭結(jié)點(diǎn)單鏈表head中第一個(gè)值為x的結(jié)點(diǎn)。假設(shè)線(xiàn)性表（a1,a2,a3,…an）采用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)，請(qǐng)?jiān)O(shè)計(jì)算法函數(shù)linklistreverse(linklisthead)，將帶頭結(jié)點(diǎn)的單鏈表head就地倒置，使表變成（an,an-1,…a3.a2,a1）。假設(shè)帶頭結(jié)點(diǎn)的單鏈表head是升序排列的，設(shè)計(jì)算法函數(shù)linklistinsert(linklisthead,datatypex)，將值為x的結(jié)點(diǎn)插入到鏈表head中，并保持鏈表有序性。編寫(xiě)算法函數(shù)linklistdelallx(linklisthead,intx)，刪除帶頭結(jié)點(diǎn)單鏈表head中所有值為x的結(jié)點(diǎn)。已知線(xiàn)性表存儲(chǔ)在帶頭結(jié)點(diǎn)的單鏈表head中，請(qǐng)?jiān)O(shè)計(jì)算法函數(shù)voidsort(linklisthead)，將已知兩個(gè)帶頭結(jié)點(diǎn)的單鏈表L1和L2中的結(jié)點(diǎn)值均已按升序排序，設(shè)計(jì)算法函數(shù)linklistmergeAscend(linklistL1,linklistL2)將L1和L2合并成一個(gè)升序的帶頭結(jié)單鏈表作為函數(shù)的返回結(jié)果；設(shè)計(jì)算法函數(shù)linklistmergeDescend(linklistL1,linklistL2)將L1和L2合并成一個(gè)降序的帶頭結(jié)單鏈表作為函數(shù)的返回結(jié)果head中的結(jié)點(diǎn)按結(jié)點(diǎn)值升序排列。設(shè)計(jì)一個(gè)算法linklistinterSection(linklistL1,linklistL2)，求兩個(gè)單鏈表表示的集合L1和L2的交集，并將結(jié)果用一個(gè)新的帶頭結(jié)點(diǎn)的單鏈表保存并返回表頭地址。請(qǐng)編寫(xiě)一個(gè)算法函數(shù)voidpartion(linklisthead)，將帶頭結(jié)點(diǎn)的單鏈表head中的所有值為奇數(shù)的結(jié)點(diǎn)調(diào)整到鏈表的前面，所有值為偶數(shù)的結(jié)點(diǎn)調(diào)整到鏈表的后面。編寫(xiě)一個(gè)程序，用盡可能快的方法返回帶頭結(jié)點(diǎn)單鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)的地址，如果不存在，則返回NULL。實(shí)驗(yàn)步驟在visualC++6.0中進(jìn)行編程，調(diào)試，完成實(shí)驗(yàn)。程序及運(yùn)行結(jié)果（或?qū)嶒?yàn)數(shù)據(jù)記錄及分析）實(shí)驗(yàn)1：linklistdelx(linklisthead,datatypex){ linklistp=head->next,pre=head,q; inti=0; while(p!=NULL&&i==0){ if(p->info==x){ q=p; p=p->next; pre->next=p; free(q); i=1; }else{ pre=p; p=p->next; i=0; } }returnhead;}實(shí)驗(yàn)2linklistreverse(linklisthead){ linklistp,q; p=head->next; head->next=NULL; while(p!=NULL){ q=p->next; p->next=head->next; head->next=p; p=q; } returnhead;}實(shí)驗(yàn)3linklistinsert(linklisthead,datatypex){ linklistp,q; q=head; p=(linklist)malloc(sizeof(node)); p->info=x; while(q->next->info<x&&q->next!=NULL){ q=q->next; } p->next=q->next; q->next=p; returnhead;}：實(shí)驗(yàn)4linklistdelallx(linklisthead,intx){linklistp=head->next,pre=head,q; while(p!=NULL){ if(p->info==x){ q=p; p=p->next; pre->next=p; free(q); }else{ pre=p; p=p->next; } }returnhead;}實(shí)驗(yàn)5voidsort(linklisthead)//插入法排序{ linklistp,q,qpre,pnext; p=head->next; head->next=NULL; while(p!=NULL){ qpre=head; q=head->next; while(q!=NULL&&q->info<=p->info){ qpre=q; q=q->next; } pnext=p->next; p->next=qpre->next; qpre->next=p; p=pnext; }}實(shí)驗(yàn)6linklistmergeAscend(linklistL1,linklistL2){linklisthead,tmp=NULL;linklisthead1=L1,head2=L2;head=(linklist)malloc(sizeof(node)); head->next=NULL;if(L1->next->info>L2->next->info)//哪個(gè)鏈表第一個(gè)節(jié)點(diǎn)值小，則把它的頭指針作為合并后的頭指針{head1=L2;head2=L1;}head->next=head1->next;while(head2!=NULL){while((head1->next->info<head2->info)&&head1->next!=NULL){head1=head1->next;}tmp=head2;head2=head2->next;tmp->next=head1->next;head1->next=tmp;}returnhead;}實(shí)驗(yàn)7linklistinterSection(linklistL1,linklistL2){linklistp1,p2,p3,L3,r;L3=r=(linklist)malloc(sizeof(node));L3->next=NULL;p1=L1->next;while(p1!=NULL){p2=L2->next;while((p2!=NULL)&&(p2->info!=p1->info))p2=p2->next;if((p2!=NULL)&&(p2->info==p1->info)){p3=(linklist)malloc(sizeof(node)); //L3=L3->next;p3->info=p1->info;r->next=p3;r=p3; }p1=p1->next;}//print(L3); r->next=NULL; returnL3;}實(shí)驗(yàn)8voidpartion(linklisthead){ linklistp,s,pre; pre=head; p=head->next; while(p) { if(p->info%2==0) { pre=p; p=p->next; } else { s=p; pre->next=p->next; p=pre->next; s->next=NULL; s->next=head->next; head->next=s; } }}實(shí)驗(yàn)9linklistsearch(linklisthead,intk