【數(shù)據(jù)結(jié)構(gòu)】實(shí)驗(yàn)指導(dǎo)書(shū)（源代碼）

...wd......wd......wd...實(shí)驗(yàn)一線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造實(shí)驗(yàn)?zāi)康模?．掌握線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造。2．熟練地利用鏈?zhǔn)酱鎯?chǔ)構(gòu)造實(shí)現(xiàn)線性表的基本操作。3．能熟練地掌握鏈?zhǔn)酱鎯?chǔ)構(gòu)造中算法的實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容：1．用頭插法或尾插法建設(shè)帶頭結(jié)點(diǎn)的單鏈表。2．實(shí)現(xiàn)單鏈表上的插入、刪除、查找、修改、計(jì)數(shù)、輸出等基本操作。三、實(shí)驗(yàn)要求：1.根據(jù)實(shí)驗(yàn)內(nèi)容編寫(xiě)程序，上機(jī)調(diào)試、得出正確的運(yùn)行程序。2.寫(xiě)出實(shí)驗(yàn)報(bào)告〔包括源程序和運(yùn)行結(jié)果〕。四、實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí)五、實(shí)驗(yàn)步驟：1．進(jìn)入編程環(huán)境，建設(shè)一新文件；2.參考以下相關(guān)內(nèi)容，編寫(xiě)程序，觀察并分析輸出結(jié)果。①定義單鏈表的數(shù)據(jù)類(lèi)型，然后將頭插法和尾插法、插入、刪除、查找、修改、計(jì)數(shù)、輸出等基本操作都定義成子函數(shù)的形式，最后在主函數(shù)中調(diào)用它，并將每一種操作前后的結(jié)果輸出，以查看每一種操作的效果。②局部參考程序//單鏈表的建設(shè)(頭插法)，插入，刪除，查找、修改、計(jì)數(shù)、輸出#include<iostream.h>#defineelemtypeintstructlink{elemtypedata；//元素類(lèi)型link*next；//指針類(lèi)型，存放下一個(gè)元素地址};//頭插法建設(shè)帶頭結(jié)點(diǎn)的單鏈表link*hcreat(){links,p;elemtypei;cout<<〞輸入多個(gè)結(jié)點(diǎn)數(shù)值(用空格分隔)，為0時(shí)算法完畢〞；cin>>i；p=newlink；p->next=NULL；while(i)//當(dāng)輸入的數(shù)據(jù)不為0時(shí)，循環(huán)建單鏈表{s=newlink；s->data=i；s->next=p->next；p->next=s；cin>>i；}returnp；}//輸出單鏈表voidprint(1ink*head){1ink*p；p=head->next；while(p->next!=NULL){cout<<p->data<<〞->〞；//輸出表中非最后一個(gè)元素p=p->next；}cout<<p->data；//輸出表中最后一個(gè)元素cout<<endl；}∥在單鏈表head中查找值為x的結(jié)點(diǎn)Link*Locate(1ink*head，elemtypex){Link*p；p=head->next；while((p!=NULL)&&(p->data!=x))p=p->next；returnp；}//在head為頭指針的單鏈表中，刪除值為x的結(jié)點(diǎn)voiddeletel(1ink*head，elemtypex){1ink*p，*q；q=head；p=head->next；while((p!=NULL)&&(p->data!=x)){q=p；p=p->next；}If(p==NULL)cout<<“要?jiǎng)h除的結(jié)點(diǎn)不存在〞；elseq->next=p->next；delete(p)；}}//在頭指針head所指的單鏈表中，在值為x的結(jié)點(diǎn)之后插入值為y的結(jié)點(diǎn)voidinsert(1ink*head，elemtypex，elemtypey)｛link*p，*s；s=newlink；s->data=y；if(head->next==NULL)//鏈表為空{(diào)head->next=s；s->next=NULL：}p=Locate(head，x)；//調(diào)用查找算法‘if(p==NULL)cout<<〞插入位置非法〞：else(s->next=p->next；p->next=s；}}//將單鏈表p中所有值為x的元素修改成yvoidchange(1ink*p,elemtypex,elemtypey){link*q；q=p->next；while(q!=NULL){if(q->data==x)q->data=y；q=q->next；}}voidcount(1ink*h)//統(tǒng)計(jì)單鏈表中結(jié)點(diǎn)個(gè)數(shù){1ink*p；intn=0；p=h->next；while(p!=NULL){n++；p=p->next；}returnn;}voidmain(){intn；elemtypex，y；link*p，*q；p=hcreat()；//頭插法建設(shè)鏈表print(p)；//輸出剛建設(shè)的單鏈表cout<<〞請(qǐng)輸入要?jiǎng)h除的元素〞；cin>>y；deletel(p，y)；print(p)；//輸出刪除后的結(jié)果cout<<〞請(qǐng)輸入插入位置的元素值(將待插元素插入到它的后面)〞;cin>>x；cout<<〞請(qǐng)輸入待插元素值〞；cin>>y；insert(p，x，y)；print(p)；//輸出插入后的結(jié)果cout<<〞請(qǐng)輸入要修改前、后的元素值〞;cin>>x>>y；change(p，x，y)；print(p)；cout<<〞請(qǐng)輸入要查找的元素值〞；cin>>x；q=Locate(p，x)；if(q==NULL)cout<<x<<〞不在表中，找不到!〞<<endl；elsecout<<x<<〞在表中，已找到!〞<<endl；n=count(p)；cout<<〞鏈表中結(jié)點(diǎn)個(gè)數(shù)為：〞<<n<<endl：}//單鏈表的建設(shè)(尾插法)、插入、刪除、查找、修改、計(jì)數(shù)、輸出#include<iostream.h>#defineelemtypeintstructlink{elemtypedata；//元素類(lèi)型link*next；//指針類(lèi)型，存放下-個(gè)元素地址}；//尾插法建設(shè)帶頭結(jié)點(diǎn)的單鏈表link*rcreat(){link*s，*p，*r；elemtypei；cout<<〞輸入多個(gè)結(jié)點(diǎn)數(shù)值(用空格分隔)，為0時(shí)算法完畢〞；cin>>i;p=r=newlink；p->next=NULL；while(i){s=newlink；s->data=i；r->next=s；r=s；cin>>i；}r->next=NULL；returnp；}//輸出單鏈表voidprint(1ink*head){link*p；p=head->next；while(p->next!=NULL){cout<<p->data<<"->〞;//輸出表中非最后一個(gè)元素p=p->next；)cout<<p->data；//輸出表中最后一個(gè)元素cout<<endl；}link*Locate(1ink*head，intx)∥在單鏈表中查找第x個(gè)結(jié)點(diǎn){link*p；p=head；intj=0；while((p!=NULL)&&(j<x)){p=p->next;j++；}returnp；}voiddeleteI(1ink*head，elemtypex)//在head為頭指針的單鏈表中，刪除值為x的結(jié)點(diǎn){link*p,*q；q=head；p=head->next；while((p!=NULL)&&(p->data!=x)){q=p；p=p->next；)if(p==NULL)cout<<〞要?jiǎng)h除的結(jié)點(diǎn)不存在“;else{q->next=p->next；delete(p)；}}voidinsert(1ink*head，intx,elemtypey)//在頭指針head所指單鏈表中，在第x個(gè)結(jié)點(diǎn)之后插入值為y的結(jié)點(diǎn){link*p，*s；s=newlink；s->data=y；if(head->next==NULL)//鏈表為空{(diào)head->next=s；s->next=NULL：}p=Locate(head，x)；//調(diào)用查找算法if(p==NULL)cout<<〞插入位置非法〞;else{s->next=p->next；p->next=s；}}voidchange(1ink*p,elemtypex，elemtypey){∥將單鏈表P中所有值為x的元素改成值為ylink*q；q=p->next；while(q!=NULL){if(q->data==x)q->data=y；q=q->next；}}voidcount(1ink*h)//統(tǒng)計(jì)單鏈表中結(jié)點(diǎn)個(gè)數(shù)(1ink*p；intn=0；p=h->next；while(p!=NULL){n++；p=p->next；}retumn;}voidmain(){intn;linkp,q;p=rcreat()；//尾插法建設(shè)鏈表print(p)；//輸出剛建設(shè)的單鏈表cout<<〞請(qǐng)輸入要?jiǎng)h除的元素〞；cin>>y；deletel(p，y)；print(p)；//輸出刪除后的結(jié)果cout<<〞請(qǐng)輸入插入位置〞;cin>>x；cout<<〞請(qǐng)輸入待插元素值〞；cin>>y；insert(p，x，y)；print(p)；//輸出插入后的結(jié)果cout<<〞請(qǐng)輸入修改前、后的元素值〞;cin>>x>>y；change(p，x，y)；print(p)；cout<<“請(qǐng)輸入要查找的元素值〞;cin>>x；q=Locate(p,x)；if(q==NULL)cout<<x<<〞不在表中,找不到!〞<<endl；elsecout<<x<<〞在表中，已找到!〞<<endl；n=count(p)；cout<<〞鏈表中結(jié)點(diǎn)個(gè)數(shù)為：〞<<n<endl;}六、選作實(shí)驗(yàn)試設(shè)計(jì)一元多項(xiàng)式相加〔鏈?zhǔn)酱鎯?chǔ)〕的加法運(yùn)算。A〔X〕=7+3X+9X8+5X9B〔X〕=8X+22X7-9X81．建設(shè)一元多項(xiàng)式；2．輸出相應(yīng)的一元多項(xiàng)式；3．相加操作的實(shí)現(xiàn)。實(shí)驗(yàn)二循環(huán)鏈表的操作實(shí)驗(yàn)?zāi)康模和ㄟ^(guò)本實(shí)驗(yàn)中循環(huán)鏈表和雙向鏈表的使用，使學(xué)生進(jìn)一步熟練掌握鏈表的操作方式。二、實(shí)驗(yàn)內(nèi)容：本次實(shí)驗(yàn)可以從以下兩個(gè)實(shí)驗(yàn)中任選一個(gè)：1．建設(shè)一個(gè)單循環(huán)鏈表并實(shí)現(xiàn)單循環(huán)鏈表上的逆置。所謂鏈表的逆置運(yùn)算(或稱(chēng)為逆轉(zhuǎn)運(yùn)算)是指在不增加新結(jié)點(diǎn)的前提下，依次改變數(shù)據(jù)元素的邏輯關(guān)系，使得線性表(al，a2，a3，…，an)成為(an，…，a3，a2，a1)。2.構(gòu)建一個(gè)雙向鏈表，實(shí)現(xiàn)插入、查找和刪除操作。三、實(shí)驗(yàn)要求：1.根據(jù)實(shí)驗(yàn)內(nèi)容編寫(xiě)程序，上機(jī)調(diào)試、得出正確的運(yùn)行程序。2.寫(xiě)出實(shí)驗(yàn)報(bào)告〔包括源程序和運(yùn)行結(jié)果〕。四、實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí)五、實(shí)驗(yàn)步驟：1．進(jìn)入編程環(huán)境，建設(shè)一新文件；2.參考以下相關(guān)內(nèi)容，編寫(xiě)程序，觀察并分析輸出結(jié)果。①建設(shè)一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表，從頭到尾掃描單鏈表L，把p作為活動(dòng)指針，沿著鏈表向前移動(dòng)，q作為p前趨結(jié)點(diǎn)，r作為q的前趨結(jié)點(diǎn)。其中，q的next值為r；r的初值置為head。②雙向鏈表的構(gòu)造與單鏈表一樣，至于它的插入與刪除運(yùn)算比單鏈表復(fù)雜，插入運(yùn)算需要4步操作，刪除運(yùn)算需要2步操作，注意語(yǔ)句的次序，不要任意交換位置，以免不能正確插入或刪除結(jié)點(diǎn)。③局部參考程序//循環(huán)鏈表∥頭文件h1．h的內(nèi)容#defineNULL0#include<stdio．h>#include<malloc．h>typedefstructnode{intnum；structnode*next；}linklist；∥以下是主程序#include〞h1．h〞∥輸出循環(huán)鏈表的信息voidoutput(linklist*head){linklist*p；p=head->next；while(p!=head){printf(〞％d〞，p->num)；p=p->next；}printf(〞\n〞)；}//建設(shè)單循環(huán)鏈表Linklist*creat(intn){intk;linklist*head,*r,*p；p=(linklist*)malloc(sizeof(linklist))；head=p；r=p；p->next=p；for(k=1；k<=n；k++){p=(linklist*)malloc(sizeof(linklist))；p->num=k；r->next=p；r=p；}p->next=head；return(head)；}∥逆置函數(shù)linklist*invert(linklist*head){Linklist*p，*q，*r；p=head->next；q=head；while(p!=head){r=q；q=p；p=p->next；q->next=r；}head->next=q；return(head)；}voidmain(){intn；Linklist*head；printf(“輸入所建設(shè)的循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù)：\n〞)；scanf(“%d〞，＆n)；head=creat(n)；printf(〞輸出建設(shè)的單循環(huán)鏈表：\n〞)；output(head)；printf(〞現(xiàn)在進(jìn)展逆置!\n〞)；head=invert(head)；printf(〞輸出進(jìn)展逆置運(yùn)算后的單循環(huán)鏈表的結(jié)點(diǎn)信息!\n〞)；output(head)；}//雙向鏈表參考程序//以下是頭文件hh．h的內(nèi)容#include<stdio.h>#include<malloc.h>typedefstructdupnode{intdata；structdupnode*next,*prior；}dulinklist；//以下是主程序的內(nèi)容#include〞hh．h〞//create函數(shù)用來(lái)構(gòu)建雙向鏈表dulinklist*create(){dulinklist*head,*p，*r;inti，n；head=(dulinklist*)malloc(sizeof(dulinklist))；head->next=NULL；head->prior=NULL；r=head；printf(“請(qǐng)輸入所建雙向鏈表中結(jié)點(diǎn)的個(gè)數(shù)：\n〞)；scanf(“％d〞,＆n)；for(i=l；i<=n；i++){p=(dulinklist*)malloc(sizeof(dulinklist))；printf(〞輸入結(jié)點(diǎn)的值：\n〞)；scanf(〞%d’，&p->data)；p->next=NULL；r->next=p；p->prior=r；r=r->next；}return(head)；}//find函數(shù)用來(lái)實(shí)現(xiàn)在雙向鏈表中按序號(hào)查找某個(gè)結(jié)點(diǎn)的功能。voidfind(dulinklist*h){intk,i；dulinklist*p；p=h；i=0：printf(〞輸入要查找結(jié)點(diǎn)的序號(hào)：\n〞)；scanf(〞%d〞,&k)；while((p!=NULL)&&(i<k)){p=p->next；i++：}if(p){printf(〞所查到的結(jié)點(diǎn)的值為：\n〞)；printf(〞%d\n〞,p->data)；}elseprintf(〞沒(méi)找到該結(jié)點(diǎn)!\n〞)；}//insdulist函數(shù)用來(lái)實(shí)現(xiàn)在雙向鏈表中按序號(hào)插入結(jié)點(diǎn)的功能dulinklist*insdulist(dulinklist*head，inti，intx){dulinklist*p，*s；intj；p=head；j=0；whi1e((p->next!=head)&&(j<i-1))//找到第i-1個(gè)結(jié)點(diǎn){p=p->next；j++；}If(j==i-1){s＝(dulinklist*)malloc(sizeof(dulinklist))；s->data=x；s->prior=p；s->next=p->next；p->next->prior=s；p->next=s；}elseprintf(〞error\n〞)；returnhead；}//deledulist函數(shù)實(shí)現(xiàn)在雙向鏈表中按序號(hào)刪除某個(gè)結(jié)點(diǎn)的功能dulinklist*deledulist(dulinklist*head，inti){dulinklist*p；intj；p=head；j=0while((p->next!=head)&&(j<i)){p=p->next；j++；}If(j==i){p->prior->next=p->next；p->next->prior=p->prior；free(p)；}elseprintf(〞error\n〞)；returnhead；}//output函數(shù)用來(lái)輸出整個(gè)雙向鏈表的結(jié)點(diǎn)值voidoutput(dulinklist*h){dulinklist*p；p=h->next；while(p!=NULL){printf(〞輸出該雙向鏈表的結(jié)點(diǎn)，分別為：\n〞)；printf(〞%d\n〞,p->data)；p=p->next；}}voidmain(){dulinklist*head；intflag=l，i，k，x；while(flag)//flag作為判斷循環(huán)的標(biāo)志位{printf(〞1．建設(shè)雙向鏈表\n〞)；printf(〞2．查找某個(gè)結(jié)點(diǎn)\n〞)；printf(〞3．插入一個(gè)結(jié)點(diǎn)\n〞)；prtntf(〞4．刪除一個(gè)結(jié)點(diǎn)\n〞)；printf(〞5．退出\n〞)；printf(〞請(qǐng)輸入選擇：\n“)；scanf(〞%d〞，&i)；switch(i){case1：head=create0；break；case2：find(head)；break；case3：printf(〞輸入待插的結(jié)點(diǎn)的序號(hào)及新插入結(jié)點(diǎn)的data值.\n〞);scanf(〞%d%d〞，＆k，＆x)；head=insdulist(head，k，x)；output(head)；break；case4：printf(〞輸入要?jiǎng)h除的結(jié)點(diǎn)的序號(hào).\n〞)；scanf(〞%d，＆k)；head=deledulist(head，k)；output(head)；break；case5:flag=0；}}//while循環(huán)完畢}此程序不管是插入、查找還是刪除運(yùn)算均是按序號(hào)的方式來(lái)處理，當(dāng)然也可改為按結(jié)點(diǎn)的值來(lái)作相應(yīng)的處理，試修改以上程序?qū)崿F(xiàn)按值操作的功能。六、選作實(shí)驗(yàn)利用單循環(huán)鏈表存儲(chǔ)構(gòu)造，解決約瑟夫〔Josephus〕環(huán)問(wèn)題。即：將編號(hào)是1,2,…,n(n>0)的n個(gè)人按照順時(shí)針?lè)较驀蝗Γ咳顺钟幸粋€(gè)正整數(shù)密碼。開(kāi)場(chǎng)時(shí)任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從某個(gè)人開(kāi)場(chǎng)順時(shí)針?lè)较蜃?開(kāi)場(chǎng)順序報(bào)數(shù)，報(bào)到m時(shí)停頓報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)場(chǎng)重新從1報(bào)數(shù)，如此下去，直到所有的人全部出列為止。令n最大值取30。設(shè)計(jì)一個(gè)程序，求出出列順序，并輸出結(jié)果。實(shí)驗(yàn)三樹(shù)形構(gòu)造實(shí)驗(yàn)?zāi)康模?．掌握二叉樹(shù)的數(shù)據(jù)類(lèi)型描述及二叉樹(shù)的特性。2．掌握二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)構(gòu)造(二叉鏈表)的建設(shè)算法。3．掌握二叉鏈表上二叉樹(shù)的基本運(yùn)算的實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容：從以下1、2和3、4中各選擇一項(xiàng)內(nèi)容1.用遞歸實(shí)現(xiàn)二叉樹(shù)的先序、中序、后序3種遍歷。2.用非遞歸實(shí)現(xiàn)二叉樹(shù)的先序、中序、后序3種遍歷。3.實(shí)現(xiàn)二叉樹(shù)的層次遍歷。4.將一棵二叉樹(shù)的所有左右子樹(shù)進(jìn)展交換。實(shí)驗(yàn)要求：1.根據(jù)實(shí)驗(yàn)內(nèi)容編程，上機(jī)調(diào)試、得出正確的運(yùn)行程序。2.寫(xiě)出實(shí)驗(yàn)報(bào)告〔包括源程序和運(yùn)行結(jié)果〕。四、實(shí)驗(yàn)學(xué)時(shí)：4學(xué)時(shí)五、實(shí)驗(yàn)步驟：1．進(jìn)入編程環(huán)境，建設(shè)一新文件；2.參考以下相關(guān)內(nèi)容，編寫(xiě)程序，觀察并分析輸出結(jié)果。將建設(shè)二叉樹(shù)及先序、中序、后序3種遍歷算法都寫(xiě)成子函數(shù)，然后分別在主函數(shù)中調(diào)用它，但在建設(shè)二又樹(shù)中，必須把二叉樹(shù)看成完全二叉樹(shù)的形式。假設(shè)不是完全二叉樹(shù)，那么在輸入數(shù)據(jù)時(shí)，用虛結(jié)點(diǎn)(不存在)表示(本算法中，用“，〞號(hào)代替)。用非遞歸法實(shí)現(xiàn)二叉樹(shù)的遍歷非遞歸算法中，必須設(shè)置堆棧，可以直接用一維數(shù)組來(lái)代替棧，但必須另外設(shè)置棧頂指針。③實(shí)現(xiàn)二叉樹(shù)的層次遍歷用一個(gè)一維數(shù)組代替隊(duì)列，實(shí)現(xiàn)二叉樹(shù)的層次遍歷。④將一棵二叉樹(shù)的所有左右子樹(shù)進(jìn)展交換。本算法只要增加一個(gè)實(shí)現(xiàn)二叉樹(shù)左右子樹(shù)交換的子函數(shù)即可。為了便于查看，在主函數(shù)將交換前后的三種遍歷效果，分別輸出。以下為局部參考程序：//遞歸實(shí)現(xiàn)二叉樹(shù)的3種遍歷#include<iostream.h>typedefcharelemtype；structbitree{定義二叉樹(shù)數(shù)據(jù)類(lèi)型elemtypedata；//結(jié)點(diǎn)信息bitree*lchild，*rchild；//左右孩子};bitree*create()//建設(shè)二叉鏈表{bitree*root,*s，*q[100]；//q為隊(duì)列，最大空間為100intfront=l，rear=0；//隊(duì)列頭、尾指針charch；root=NULL；cout<<〞請(qǐng)輸入結(jié)點(diǎn)值(‘，’為虛結(jié)點(diǎn)，‘#’完畢)：〞<<endl；cin>>ch；while(ch!=’#’){s==NULL；if(ch!=’,’){s=newbitree；s->data=ch；s->lchild=NULL；s->rchild=NULL；}rear++；q[rear]=s；//進(jìn)隊(duì)if(rear==1)root=s；else{if((s!=NULL)&&(q[front]!=NULL)){if(rear%2==0)q[front]->lchild=s；elseq[front]->rchid=s；}if(rear％2==1)front++；//出隊(duì)}cin>>ch；｝returnroot：}voidpreorder(bitree*root)//先序遍歷{bitree*p；p=root；if(p!=NULL){cout<<p->data<<〞〞；preorder(p->lchild)；preorder(p->rchild)；}}voidinorderl(bitree*root)//中序遍歷{bitree*p；p=root；if(p!=NULL){inorder(p->lchild)；cout<<p->data<<“〞;inorder(p->rchild)；}}voidpostorder(bitree*root)//后序遍歷{bitree*p；p=root；if(p!=NULL){postorder(p->lchild)；postorder(p->rchild)；cout<<p->data<<“〞；}}voidmain(){bitree*root；root=create()；//建設(shè)二叉鏈表cout<<〞先序遍歷的結(jié)果〞<<endl；preorder(root)；cout<<endl；cout<<〞中序遍歷的結(jié)果〞<<endl；inorder(root)；cout<<endl：cout<<〞后序遍歷的結(jié)果〞<<endl；postorder(root)；cout<<endl；}//用非遞歸實(shí)現(xiàn)二叉樹(shù)的3種遍歷，局部遍歷程序如下：voidpreorderl(bitree*root)//先序遍歷{bitree*p，*s[100]；//s為堆棧inttop=0；//top為棧頂指針p=root；while((p!=NULL)||(top>0)){while(p!=NULL){cout<<p->data<<〞〞；s[++top]=p；//進(jìn)棧p=p->lchild；}p=s[top--]；//退棧p=p->rchild；}}voidinorderl(bitree*root)//中序遍歷{bitree*p，*s[100]；inttop=0；p=root；while((p!=NULL)Il(top>O)){while(p!=NULL){s[++top]=p；p=p->lchild；}{p=s[top--]；cout<<p->data<<“〞；p=p－>rchild；｝｝｝voidpostorderl(bitree*root)//后序遍歷(bitree*p*sl[100]；ints2[100]，top=0，b；p=root；do{while(p!=NULL){s1[top]=p；s2[top++]=0；p=p->lchild；)if(top>0)(b=s2[--top]；p=s1[top]；if(b==0){sl[top]=p；s2[top++]=l；p=p->rchild；}else{cout<<p->data<<〞〞;p=NULL；}}}while(top>0)；}//建設(shè)二叉鏈表參考前述程序//按照層次遍歷二叉鏈表#include<iostream.h>typedefcharelemtype；structbitree{elemtypedata；//結(jié)點(diǎn)信息bitree*lchild，*rchild；//左右孩子};//按層次遍歷二叉樹(shù)(建設(shè)二叉鏈表同前)voidlorder(bitree*t){bitreeq[100]，*p；//q代表隊(duì)列intf,r;//f，r類(lèi)似于隊(duì)列頭、尾指針q[1]=t；f=r=l；cout<<〞按層次遍歷二叉樹(shù)的結(jié)果為：〞;whileif<==r){p=q[f]；f++；//出隊(duì)cout<<p->data<<〞〞;if(P->lchild!=NULL){r++；q[r]=p->lchild；}//入隊(duì)ifp->rchild!=NULLl．{r++；q[r]=p->rchild;}//入隊(duì)}cout<<endl；}voidmain(){bitree*t；t=create0；//建設(shè)二叉鏈表lorder(t)；//：按層次遍歷二叉樹(shù)}//將二叉樹(shù)的左右子樹(shù)進(jìn)展交換voidleftOright(bitree*r){bitree*root=r;if(root!=NULL){leftOright(root->lchild);leftOright(root->rchild);bitree*t=root->lchild;root->lchild=root->rchild;root->rchild=t;}}//主函數(shù)voidmain(){bitree*root；root=create()；//建設(shè)二叉鏈表cout<<endl<<endl<<〞左右子樹(shù)交換前的遍歷結(jié)果〞<<endl；cout<<〞先序遍歷的結(jié)果〞<<endl；preorder(root)；cout<<endl；cout<<〞中序遍歷的結(jié)果〞<<endl；inorder(root)；cout<<endl：cout<<〞后序遍歷的結(jié)果〞<<endl；postorder(root)；cout<<endl；}leftTOright(root)；cout<<endl<<endl<<〞左右子樹(shù)交換后的遍歷結(jié)果〞<<endl；cout<<〞先序遍歷的結(jié)果〞<<endl；preorder(root)；cout<<endl；cout<<〞中序遍歷的結(jié)果〞<<endl；inorder(root)；cout<<endl；cout<<〞后序遍歷的結(jié)果〞<<endl；postorder(root)；cout<<endl；}六、選作實(shí)驗(yàn)1.給定權(quán)值5,29,7,8,14,23,3,11，建設(shè)哈夫曼樹(shù)，輸出哈夫曼編碼。2.對(duì)上述給定的哈夫曼樹(shù)及得到的哈夫曼編碼，試輸入一串二進(jìn)制編碼，輸出它的哈夫曼譯碼。算法提示：將建設(shè)哈夫曼樹(shù)、實(shí)現(xiàn)哈夫曼編、哈夫曼譯碼都定義成子函數(shù)的形式，然后在主函數(shù)調(diào)用它們。建設(shè)哈夫曼樹(shù)時(shí)，將哈夫曼樹(shù)的構(gòu)造定義為一個(gè)構(gòu)造型的一維數(shù)組，每個(gè)元素含有四項(xiàng)：雙親、左孩子、右孩子。給定的權(quán)值可以從鍵盤(pán)輸入，要輸出所建設(shè)的哈夫曼樹(shù)，只要輸出哈夫曼樹(shù)的一維數(shù)組中全部元素即可。要實(shí)現(xiàn)哈夫曼編碼，只要在所建設(shè)的哈夫曼樹(shù)上進(jìn)展二進(jìn)制編碼：往左走，編碼為0，往右走，編碼為1，然后將從根結(jié)點(diǎn)到樹(shù)葉中所有0、l排列起來(lái)，那么得到該樹(shù)葉的哈夫曼編碼。哈夫曼編碼可以用一個(gè)構(gòu)造型的一維數(shù)組保存，每個(gè)元素包含：編碼、編碼的開(kāi)場(chǎng)位置、編碼所對(duì)應(yīng)的字符等3項(xiàng)。哈夫曼譯碼，就是將輸入的編碼復(fù)原成對(duì)應(yīng)的字符。實(shí)驗(yàn)四圖的遍歷操作實(shí)驗(yàn)?zāi)康模?.掌握?qǐng)D的含義。2.掌握用鄰接矩陣和鄰接表的方法描述圖的存儲(chǔ)構(gòu)造。3.理解并掌握深度優(yōu)先遍歷和廣度優(yōu)先遍歷的存儲(chǔ)構(gòu)造。二、實(shí)驗(yàn)內(nèi)容：從以下1、2和3、4中各選擇一項(xiàng)內(nèi)容1.建設(shè)無(wú)向圖的鄰接矩陣，并實(shí)現(xiàn)插入、刪除邊的功能。2.建設(shè)有向圖的鄰接表，并實(shí)現(xiàn)插入、刪除邊的功能。3.建設(shè)一個(gè)包含6個(gè)結(jié)點(diǎn)的圖，并實(shí)現(xiàn)該圖的深度優(yōu)先搜索遍歷。4.建設(shè)一個(gè)包含6個(gè)結(jié)點(diǎn)的圖，并實(shí)現(xiàn)該圖的廣度優(yōu)先搜索遍歷。三、實(shí)驗(yàn)要求：1.根據(jù)實(shí)驗(yàn)內(nèi)容編程，上機(jī)調(diào)試、得出正確的運(yùn)行程序。2.寫(xiě)出實(shí)驗(yàn)報(bào)告〔包括源程序和運(yùn)行結(jié)果〕。四、實(shí)驗(yàn)學(xué)時(shí)：4學(xué)時(shí)五、實(shí)驗(yàn)步驟：1.進(jìn)入編程環(huán)境，建設(shè)一新文件；2.參考以下相關(guān)內(nèi)容，編寫(xiě)程序，觀察并分析輸出結(jié)果。內(nèi)容1的知識(shí)要點(diǎn)：圖由一個(gè)非空的頂點(diǎn)的集合和一個(gè)描述頂點(diǎn)之間關(guān)系(邊)的集合組成。它可以定義為G=(V，E)。其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合。圖是一種復(fù)雜的數(shù)據(jù)構(gòu)造。對(duì)于實(shí)際問(wèn)題，需要根據(jù)具體圖的構(gòu)造特點(diǎn)以及所要實(shí)施的操作，選擇建設(shè)適宜的存儲(chǔ)構(gòu)造。圖的存儲(chǔ)構(gòu)造包括鄰接矩陣和鄰接表。鄰接矩陣：用一維數(shù)據(jù)組存儲(chǔ)圖中頂點(diǎn)的信息，用矩陣表示圖中各頂點(diǎn)之間的相鄰關(guān)系。它屬于靜態(tài)存儲(chǔ)方法。鄰接表：鄰接表存儲(chǔ)方法是一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法。順序存儲(chǔ)局部用來(lái)保存圖中頂點(diǎn)的信息，鏈?zhǔn)酱鎯?chǔ)局部用來(lái)保存圖中邊的信息。//鄰接矩陣的存儲(chǔ)構(gòu)造typedefstruct{intvertex；}node；typedefstruct{intadj；}arc；typedefstruct{nodenode[maxnode]；arcarcs[maxnode][maxnode]；}graph；//實(shí)現(xiàn)插入、刪除邊的操作voidins_arc(graph*g，intv，intw){g->arcs[v][w].adj=l；return；}voiddel_arc(graph*g，intv，intw){g->arc[v][w].adj=0；retum;}//內(nèi)容1參考程序#definemaxnode40#definenull0#include<stdio．h>typedefstructst_arc{intadjvex；intweight；structst_arc*nextrac；}arcnode；typedefstruct{intvertex；structst_arc*firstarc；}vernode；typedefvernodeadjlist[maxnode]；voiddel_arc(vernodeg[]，intv，intw)//刪除從頂點(diǎn)v到頂點(diǎn)w的邊{arcnode*rl,*r2；rl=g[v]．frrstarc；r2=rl；while(r1!=null&&r1->adjvex!=w){r2=rl;rl=rl->nextarc；}if(rl==null){printf(〞noedgev-w．〞)；return；}elseif(r1==r2)//當(dāng)只有一個(gè)邊結(jié)點(diǎn)時(shí)g[v].firstarc=r1->nextarc；elser2->nextarc=r1->nextarc；//有多個(gè)邊結(jié)點(diǎn)時(shí)rl=g[w].firstarc；r2=rl；while(r1!=null&&r1->adjvex!=v)//在以v為頭結(jié)點(diǎn)的鏈表中，刪除相應(yīng)的//邊結(jié)點(diǎn){r2=rl；rl＝rl->nextarc；｝if(rl=＝null){printf(〞noedgev-w.〞)；return；}elseif(r1==r2)g[w].firstarc=rl->nextarc；elser2->nextarc=r1->nextarc；}voidprint(vernodeg[]，intn)//打印圖中各結(jié)點(diǎn)的構(gòu)造{arcnode*q；inti；printf(〞adjacencylistofthegraph：\n〞)；for(i=0；i<n；i++){printf(〞\t%d\t〞，i)；printf(〞%d\t〞，g[i].vertex)；q=g[i].firstarc；while(q!=null){printf(〞%d\t〞，q->adjvex)；printf(〞%d\t〞，q->weight)；q=q->nextarc；}printf(〞\n〞)；}}main(){inti，j，n，k，w，v；arcnode*p，*q；adjlistg；printf(〞Inputnode：〞)；//輸入圖中頂點(diǎn)個(gè)數(shù)scanf(〞%d〞，&n)；for(k=0；k<n；k++)//輸入邊值和權(quán)值{printf(〞node%d=〞，k)；scanf(“%d〞，＆g[k].vertex)；g[k].firstarc=null；//對(duì)順序存儲(chǔ)局部初始化}for(；；)//輸入各邊，并將對(duì)應(yīng)的邊結(jié)點(diǎn)插入到鏈表中{printf(〞Insertedgei-j，w：〞)scanf(〞%d〞，＆i)；scanf(〞%d〞，＆j)；scanf(〞%d〞，＆w)；if〔i==-1&＆j=＝-1&&w=-1)break；q=(arcnode*)malloc(sizeof(arcnode))；q->adjvex=j；q->weight=w；q->nextarc=g[i].firstarc；//頭指針指向新的邊結(jié)點(diǎn)g[i].firstarc=q；p=(arcnode*)malloc(sizeof(arcnode))；p->nextarc=g[i].firstarc；g[i].firstarc=q；p=(arcnode*)malloc(sizeof(arcnode))；p->adjvex=i；p->weight=w；p->nextarc=g[j].firstarc；g[j].firstarc=p；}print(g，n)；printf(〞DeleteedgeV-w：〞)；scanf(〞%d%d〞，＆v，&w)；del_arc(g，v，w)；print(g，n)；}內(nèi)容2的知識(shí)要點(diǎn)：構(gòu)造有向圖鏈接表與無(wú)向圖鏈接表的算法區(qū)別是：無(wú)向圖兩結(jié)點(diǎn)無(wú)向?qū)ε?，因而鄰接表有一定的?duì)偶性；有向圖兩結(jié)點(diǎn)間有向無(wú)對(duì)偶關(guān)系，因而建設(shè)鄰接表時(shí)應(yīng)根據(jù)輸入的頂點(diǎn)及邊的有向關(guān)系建設(shè)(當(dāng)箭頭方向離開(kāi)結(jié)點(diǎn)為有關(guān)，當(dāng)箭頭方向指向結(jié)點(diǎn)為無(wú)關(guān))。//內(nèi)容2的參考程序//有向圖鏈表的存儲(chǔ)構(gòu)造為：typedefstructst_arc{intaajvex；//存放依附于該邊的另一頂點(diǎn)在一維數(shù)組中的序號(hào)intweight；//存放和該邊有關(guān)的信息，如權(quán)值等structst_arc*nextarc；//依附于該頂點(diǎn)的下一個(gè)邊結(jié)點(diǎn)的指針}arcnode；typedefstruct{intvertex；//存放與頂點(diǎn)有關(guān)的信息structst_arc*firstarc；}vernode；//存儲(chǔ)頂點(diǎn)信息typedefvernodeadjlist[maxnode]；//參考程序見(jiàn)內(nèi)容1內(nèi)容3的知識(shí)要點(diǎn)：深度優(yōu)先搜索遍歷圖的算法：首先訪問(wèn)指定的起始頂點(diǎn)v0，從vo出發(fā)，訪問(wèn)vo的一個(gè)未被訪問(wèn)過(guò)的鄰接頂點(diǎn)w1，再?gòu)膚1出發(fā)，訪問(wèn)w1的一個(gè)未被訪問(wèn)的頂點(diǎn)w2，然后從w2出發(fā)，訪問(wèn)w2的一個(gè)未被訪問(wèn)的鄰接頂點(diǎn)w3，依此類(lèi)推，直到一個(gè)所有鄰接點(diǎn)都被訪問(wèn)過(guò)為止。圖采用鄰接表作存儲(chǔ)構(gòu)造，圖的深度優(yōu)先遍歷次序?yàn)棰佟凇堋荨蕖蹍⒖汲绦蜻\(yùn)行過(guò)程中，深度優(yōu)先遍歷時(shí)指針p的移動(dòng)方向示意如圖下所示，圖中p1、p2、p3、p4、p5和p6為深度優(yōu)先遍歷圖的各結(jié)點(diǎn)時(shí)，指針p的移動(dòng)次序。//內(nèi)容3的參考程序#definemaxnode40#definenull0#include<sddio．h>typedefstructst_arc//定義構(gòu)造體{intadivex；intweigh；structst_arc*nextarc；}arcnode；typedefstruct{intvertex；structst_arc*firstarc；}vernode；typedefvernodeadjlist[maxnode]；voidtrave(adjlistg，intn)//采用鄰接表作存儲(chǔ)構(gòu)造的/深度優(yōu)先遍歷{inti，visited[maxnode]；//數(shù)組visited標(biāo)志圖中的定點(diǎn)是否已被訪問(wèn)voiddfs()；for(i=0；i<n；i++)visited[i]=0;//數(shù)組初始化for(i=0；i<n；i++)if(visited[i]==0)dfs(g，i，visted)；}voiddfs(adjlistg，intk，intvisited[])//從頂點(diǎn)k出發(fā)，深度優(yōu)先遍歷圖g。{arcnode*p；intw；visited[k]=1；printf(%d，g[k]，vertex)；p=g[k]，firstarc；while(p!=null){w=p->adjvex；if(visited[w]==0)dfs(g，w，visited)；p=p->nextarc；}}main(){inti，j，n，k，v；arcnode*p,*q;adjlistg；printf(“Inputnode：〞)；scanf(“%d〞，＆n)；for(k=0；k<n；k++)//構(gòu)造圖{printf(“node%d=〞，k)；g[k].firstarc=null；}for(；；){printf(“Insertedgei-j:〞)；scanf(“%d〞，＆i)；scanfi(“%d〞，＆j)；if(i==-1&&j==-1)break；q=(arcnode*)malloc(sizeof(arcnode))；q->adjvex=j；q->nextarc=g[i].firstarc；g[i]firstarc=q；p=(arcnode*)malloc(sizeof(arcnode))；p->adjvex=i；p->nextarc=g[i].firstarc;g[i]_firstarc=p；}printf(“dfs：〞)；trave(g，n)；//深度優(yōu)先遍歷圖。printf(“\n〞);}內(nèi)容4的知識(shí)要點(diǎn)：廣度優(yōu)先遍歷圖的算法：首先訪問(wèn)指定的起始頂點(diǎn)v0,從v0出發(fā)，訪問(wèn)v0的所有未被訪問(wèn)的鄰接頂點(diǎn)w1，w2，…，wk，然后再依次從w1，w2，…，wk出發(fā)，訪問(wèn)所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)，依此類(lèi)推，直到圖中所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)都被訪問(wèn)過(guò)為止。根據(jù)廣度優(yōu)點(diǎn)遍歷的規(guī)那么，在其算法實(shí)現(xiàn)中，借助一個(gè)隊(duì)列g(shù)－queue來(lái)存放已被訪問(wèn)過(guò)的頂點(diǎn)。從指定頂點(diǎn)開(kāi)場(chǎng)，每訪問(wèn)一個(gè)頂點(diǎn)，就將它入隊(duì)并排在隊(duì)尾，然后從隊(duì)頭取出一個(gè)頂點(diǎn)，訪問(wèn)該頂點(diǎn)的所有未被訪問(wèn)的鄰接點(diǎn)，依此類(lèi)推，直至隊(duì)列為空且圖中結(jié)點(diǎn)均被訪問(wèn)過(guò)為止。圖的廣度優(yōu)先遍歷次序?yàn)椋孩佟凇邸堋荨迏⒖汲绦蜻\(yùn)行過(guò)程中，廣度優(yōu)先搜索時(shí)指針p的移動(dòng)示意如以以下圖所示，圖中片p1、p2、p3、p4、p5和p6為廣度優(yōu)先遍歷圖的各結(jié)點(diǎn)指針p的移動(dòng)次序。//內(nèi)容4的參考程序#definemaxnode40#definenull0#include<sddio．h>typedefstructst_arc//定義構(gòu)造體{intadivex；intweigh；structst_arc*nextarc；}arcnode；typedefstruct{intvertex；structst_arc*firstarc；}vernode；typedefvernodeadjlist[maxnode]；typedefstruct{intqueue[maxnode];intfront;intrear;}qqtype;voidintiate(qqtype*q)//初始化隊(duì)列｛q->front=-1;q->rear=-1;}intenter(qqtype*q,intx)//將X入隊(duì){if(q->rear==maxnode-1)return(-1);else{q->rear++;q->queue[q->rear]=x;return(0);}}intdelete(qqtype*q)//出隊(duì){if(q->front==q->rear)return(null);else{q->front++;return(q->queue[q->front]);}}intemtype(qqtype*q){if(q->front==q->rear)return(-1);return(0);}voidbfs(adjlistg，intk，intvisited[])//從頂點(diǎn)k出發(fā)進(jìn)展廣度優(yōu)先遍歷{arcnode*p；intw；intiate(g);visited[k]=1;//訪問(wèn)點(diǎn)從k開(kāi)場(chǎng)，并把它入隊(duì)。printf(“%d〞,g[p->adjvex].vertex);enter(g,k);while(emptye(g)==0){w=delete(g);p=g[w].firstarc;while(p!=null){if(visited[p->adjves]==0){printf(“%d〞,g[p->adjvex].verte);visited[p->adjvex]=1;enter(g.p->adjvex);}p=p->nextarc;}}}voidtrave(adjlistg，intn)//圖采用鄰接表存儲(chǔ)的廣度優(yōu)先遍歷{inti，visited[maxnode]；//數(shù)組visited標(biāo)志圖中的定點(diǎn)是否已被訪問(wèn)。for(i=0；i<n；i++)visited[i]=0;//數(shù)組初始化for(i=0；i<n；i++)if(visited[i]==0)bfs(g，i，visted)；}main(){inti，j，n，k，v；arcnode*p,*q;adjlistg；printf(“Inputnode：〞)；scanf(“%d〞，＆n)；for(k=0；k<n；k++)//構(gòu)造圖{printf(“node%d=〞，k)；scanf(“%d〞,&g[k].vertex);g[k].firstarc=null；}for(；；){printf(“Insertedgei-j:〞)；scanf(“%d〞，＆i)；scanfi(“%d〞，＆j)；if(i==-1&&j==-1)break；q=(arcnode*)malloc(sizeof(arcnode))；q->adjvex=j；q->nextarc=g[i].firstarc；g[i]firstarc=q；p=(arcnode*)malloc(sizeof(arcnode))；p->adjvex=i；p->nextarc=g[i].firstarc;g[i]_firstarc=p；}printf(“bfs：〞)；trave(g，n)；//廣度優(yōu)先遍歷圖。printf(“\n〞);}六、選作實(shí)驗(yàn)假設(shè)有n個(gè)城市，要實(shí)現(xiàn)n個(gè)城市之間都能互相通信和構(gòu)造n個(gè)城市之間的通信網(wǎng)，使工程總造價(jià)最低。設(shè)計(jì)一個(gè)能滿足要求的最低造價(jià)方案。實(shí)驗(yàn)五查找實(shí)驗(yàn)?zāi)康模?.掌握查找的含義。2.掌握基本查找操作的算法與實(shí)現(xiàn)。3.掌握二叉排序樹(shù)查找的算法與實(shí)現(xiàn)。4.掌握Hash表查找的算法與實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容：從以下1、2和3、4中各選擇一項(xiàng)內(nèi)容1.建設(shè)一個(gè)線性表，對(duì)表中數(shù)據(jù)元素存放的先后次序沒(méi)有任何要求。輸入待查數(shù)據(jù)元素的關(guān)鍵字進(jìn)展查找。〔為了簡(jiǎn)化算法，數(shù)據(jù)元素只含一個(gè)整型量關(guān)鍵字字段，數(shù)據(jù)元素的其余數(shù)據(jù)局部忽略不考慮?！?.查找表的存儲(chǔ)構(gòu)造為有序表，即表中記錄按關(guān)鍵字大小排序存放。輸入待查數(shù)據(jù)元素的關(guān)鍵字進(jìn)展查找?！矠榱撕?jiǎn)化算法，記錄只含一個(gè)整型量關(guān)鍵字字段，記錄的其余數(shù)據(jù)局部略不考慮。程序要求對(duì)整型量關(guān)鍵字?jǐn)?shù)據(jù)的輸入按從小到大排序輸入?！?.編程實(shí)現(xiàn)二叉排序樹(shù)的創(chuàng)立、查找、插入、輸出等算法。4.設(shè)哈希表長(zhǎng)為20，用除留余數(shù)法構(gòu)造一個(gè)哈希函數(shù)，以開(kāi)放定址法中的線性探測(cè)再散列法作為解決沖突的方法，編程實(shí)現(xiàn)哈希表查找、插入和建設(shè)算法。三、實(shí)驗(yàn)要求：1.根據(jù)實(shí)驗(yàn)內(nèi)容編程，上機(jī)調(diào)試、得出正確的運(yùn)行程序。2.寫(xiě)出實(shí)驗(yàn)報(bào)告〔包括源程序和運(yùn)行結(jié)果〕。四、實(shí)驗(yàn)學(xué)時(shí)：6學(xué)時(shí)五、實(shí)驗(yàn)步驟：1．進(jìn)入編程環(huán)境，建設(shè)一新文件；2.參考以下相關(guān)內(nèi)容，編寫(xiě)程序，觀察并分析輸出結(jié)果。順序查找的基本思想及程序?qū)崿F(xiàn)對(duì)于給定的關(guān)鍵字k，從表的一端開(kāi)場(chǎng)，逐個(gè)進(jìn)展數(shù)據(jù)元素的關(guān)鍵字和給定值的比較，假設(shè)當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與k相等那么查找成功；假設(shè)掃描完畢后，仍未找到關(guān)鍵字等于k的節(jié)點(diǎn)，那么查找失敗。建設(shè)一個(gè)順序表，數(shù)據(jù)元素從下標(biāo)為1的單元開(kāi)場(chǎng)放入，下標(biāo)為0的單元起監(jiān)視哨作用，將待查的關(guān)鍵字存入下標(biāo)為0的單元，順序表從后向前查找，假設(shè)直到下標(biāo)為0時(shí)才找到關(guān)鍵字那么說(shuō)明查找失?。患僭O(shè)不到下標(biāo)為0時(shí)就找到關(guān)鍵字，那么查找成功。//參考程序#include<stdio.h>#defineKEYTYPEint#defineMAXSIZE100typedefstruct{KEYTYPEkey；}SSELEMENT；typedefstruct{SSELEMENTr[MAXSIZE]；intlen；}SSTABLE；intseq_search(KEYTYPEk，SSTABLE*st)//順序表查找元素{intj；j=st->len；//順序表元素個(gè)數(shù)st->r[0].key=k；//st->r[0]單元作為監(jiān)視哨while(st->r[j].key!=k)//順序表從后向前查找j--;returnj；//j=0，找不到，j≠0找到}main(){SSTABLEa;inti，j，k；printf(〞請(qǐng)輸入順序表元素，元素為整型量，用空格分開(kāi)，-99為完畢標(biāo)志：〞)；j=0；k=1;i=0;scanf(〞%d〞，＆i)；while(i!=-99){j++；a.r[k].key=i；k++;scanf(〞%d〞，＆i)；}a.1en=j;printf(〞\n順序表元素列表顯示：〞)；for(i=1；i<=a.1en;i++)printf(〞%d〞，a.r[i].key)；printf(“\n〞);printf(〞\n輸入待查元素關(guān)鍵字：〞)；scanf(“%d〞，&i)；k=seq_search(i，&a)；if(k==0)printf(“表中待查元素不存在\n\n〞)；elseprintf(“表中待查元素存在\n\n〞)；}折半查找的基本思想及程序?qū)崿F(xiàn)：設(shè)查找表中的元素存放在數(shù)組r中，數(shù)據(jù)元素的下標(biāo)范圍為[low,high]，要查找的關(guān)鍵字值為key，中間元素的下標(biāo)為mid=(low+high)／2(向下取整)，令key與r[mid]的關(guān)鍵字比較：假設(shè)key=r[mid].key，查找成功，下標(biāo)為m的記錄即為所求，返回mid。假設(shè)key<r[mid].key，所要找的記錄只能在左半局部記錄中，再對(duì)左半局部使用折半查找法繼續(xù)進(jìn)展查找，搜索區(qū)間縮小了一半。假設(shè)key>r[mid].key，所要找的記錄只能在右半局部記錄中，再對(duì)右半局部使用折半查找法繼續(xù)進(jìn)展查找，搜索區(qū)間縮小了一半。重復(fù)上述過(guò)程，直到找到查找表中某一個(gè)數(shù)據(jù)元素的關(guān)鍵字的值等于給定的值key說(shuō)明查找成功；或者出現(xiàn)low的值大于high的情況，說(shuō)明查找不成功。建設(shè)一個(gè)有序表，數(shù)據(jù)元素從下標(biāo)為1的單元開(kāi)場(chǎng)放入。實(shí)現(xiàn)查找算法時(shí)，首先將low賦值為l，high等于最后一個(gè)數(shù)據(jù)元素的下標(biāo)，然后將給定的關(guān)鍵字的值與查找區(qū)間[low，high]中間的數(shù)據(jù)元素的關(guān)鍵字比較，實(shí)現(xiàn)查找過(guò)程。//參考程序#include<stdio.h>#defineKEYTYPEjnt#defineMAXSIZE100typedefstruct{KEYTYPEkey；}SEELEMENT；typedefstruct{SSELEMENTr[MAXSIZE]；intlen；}SSTABLE；intsearch_bin(KEYTYPEk，SSTABLE*st)，//有序表上折半查找{intlow，high，mid；low=1；//low=l表示元素從下標(biāo)為1的單元放起high=st->len；//high=st->len表示最后一個(gè)元素的下標(biāo)while(1ow<=high)//low<=high為繼續(xù)查找的條件{mid=(1ow+high)／2；if(k==st->r[mid].key)//k==st->r[mid].key表示查找成功retummid；elseif(k<st->r[mid].key)//否那么繼續(xù)二分查找high=mid－l；elselow=mid+l；｝return0;//查找不成功，返回0}main(){{SSTABLEa;inti，j，k;printf(“請(qǐng)輸入有序表元素，元素為整型量(從小到大輸入)，用空格分開(kāi)，-99為完畢標(biāo)志：〞)；j=0；k=1;I=0;scanf(“%d〞，&i)；while(i!=-99){j++；a.r[k].key=i；k++;scanf(“%d〞,＆i)；//輸入有序表元素}a.1en=j；printf(“\n有序表元素列表顯示：〞)；for(i=l；i<=a.1en；i++)printf(“%d〞，a.r[i])；printf(“\n〞)；pfintf(〞\n輸入待查元素關(guān)鍵字：〞)；scanf[“%d〞，＆i]；k=search_bin(i，&a)；if(k==0)printf("表中待查元素不存在\n\n")；elseprintf(〞表中待查元素存在\n\n")；}二叉排序樹(shù)基本思想及程序?qū)崿F(xiàn)二叉排序樹(shù)就是指將原來(lái)已有的數(shù)據(jù)根據(jù)大小構(gòu)成一棵二叉樹(shù)，二叉樹(shù)中的所有結(jié)點(diǎn)數(shù)據(jù)滿足一定的大小關(guān)系，所有的左子樹(shù)中的結(jié)點(diǎn)均比根結(jié)點(diǎn)小，所有的右子樹(shù)的結(jié)點(diǎn)均比根結(jié)點(diǎn)大。二叉排序樹(shù)查找是指按照二叉排序樹(shù)中結(jié)點(diǎn)的關(guān)系進(jìn)展查找，查找關(guān)鍵字首先同根結(jié)點(diǎn)進(jìn)展比較，如果相等那么查找成功；如果比根結(jié)點(diǎn)小，那么在左子樹(shù)中查找；如果比根結(jié)點(diǎn)大，那么在右子樹(shù)中進(jìn)展查找。這種查找方法可以快速縮小查找范圍，大大減少查找關(guān)鍵字的比較次數(shù)，從而提高查找效率。算法的關(guān)鍵過(guò)程實(shí)際上就是二叉排序樹(shù)的創(chuàng)立和查找兩個(gè)步驟。首先分析二叉排序樹(shù)的創(chuàng)立運(yùn)算，由于二叉排序樹(shù)中的所有結(jié)點(diǎn)都有一個(gè)大小關(guān)系，因此，每個(gè)結(jié)點(diǎn)必須在二叉排序樹(shù)中尋找其適宜的位置。創(chuàng)立二叉排序樹(shù)的第一步就是創(chuàng)立一個(gè)根結(jié)點(diǎn)，第二步就是將其他結(jié)點(diǎn)不斷插入到二叉排序樹(shù)中的適宜位置。二叉排序樹(shù)進(jìn)展結(jié)點(diǎn)插入時(shí)，首先要為被插入結(jié)點(diǎn)尋找適宜的插入位置。這個(gè)過(guò)程實(shí)際上就是一個(gè)關(guān)鍵值不斷的比較的過(guò)程。第一次比較是與二叉排序樹(shù)的根結(jié)點(diǎn)比較，如果比根結(jié)點(diǎn)的關(guān)鍵值小，那么插入到他的左子樹(shù)中；如果比根結(jié)點(diǎn)的關(guān)鍵值大，那么插入到它的右子樹(shù)中。在子樹(shù)中重復(fù)這樣過(guò)程，直到找到適宜的位置為止。二叉排序樹(shù)的查找運(yùn)算實(shí)際上同二叉排序樹(shù)的創(chuàng)立運(yùn)算是一致的。區(qū)別在于，創(chuàng)立過(guò)程中要為二叉排序樹(shù)中沒(méi)有位置的關(guān)鍵字建設(shè)結(jié)點(diǎn)，而查找過(guò)程中，只是在二叉排序樹(shù)中查找是否等于查找關(guān)鍵字值的結(jié)點(diǎn)存在，不管有還是沒(méi)有，它都不會(huì)創(chuàng)立一個(gè)新的結(jié)點(diǎn)。//參考程序#include<stdio.h>#include<malloc.h>#definenull0typedefintkeytype；//查找關(guān)鍵字為整型數(shù)據(jù)sturcBsnode//二叉排序樹(shù)結(jié)點(diǎn)類(lèi)型{keytypedata；//數(shù)據(jù)域structBsnode*Lchild,*Rchild；//左右指針};typedefstructBsnodeBST；typedefstructBsnode*BSP；//BSP為二叉排序樹(shù)結(jié)點(diǎn)類(lèi)型指針BSPcreateBst(keytypekey)//為關(guān)鍵字key創(chuàng)立一個(gè)二叉排序樹(shù)結(jié)點(diǎn){BSPs;s=(BSP)malloc(sizeof(BST))；s->data=key；s->Lchild=s->Rchild=null；return(s)；}BSPBSTinsert(BSPT，BSPS)//將S指向的結(jié)點(diǎn)插入到T指向的二叉排序樹(shù)中{BSPq,p;if(T==null)return(S);else{p=T;q=null;while(p)//在二叉排序樹(shù)中為s結(jié)點(diǎn)尋找插入位置{q=p；if(s->data==p->data)//如果S結(jié)點(diǎn)與二叉排序樹(shù)中根結(jié)點(diǎn)的值相等，那么不插入{printf(“Theinputkey(%d)ishavein!〞，s->data)；return(t)；}if(s->data<p->date)//如果比根結(jié)點(diǎn)值小，那么在左子樹(shù)中尋找插入位置p=p->Lchild；else//否那么在右子樹(shù)中尋找插入位置p=p->Rchild；}if(s->data<q->data)q->Lchild=s；//作為左孩子插入elseq->Rchild=s；//作為右孩子插入return(t)；}}voidsearch(BSPT，keytypex)//在二叉排序樹(shù)T中查找是否存在關(guān)鍵宇{BSPp；if(T==null){printf(“error\n〞);return;}else{p=Twhile(p){if(p->data==x)//如果根結(jié)點(diǎn)是查找的關(guān)鍵字，查找完畢{printf(“searchsuccess!\n〞)；return；}elseif(x<p->-data)//如果小于根結(jié)點(diǎn)，那么在左于樹(shù)中查找p=p->Lchild；elsep=p->Rchild；//否那么，在右子樹(shù)中查找}if(!p)printf(〞%dnotexist!\n〞，x)；}}voidBSTPrint(BSPT)//輸出二叉排序樹(shù){if(T){BSTPrint(T->Lchild)；printf(〞%d->〞，T->data)；BSTPrint(T->Rchild)；}}main(){BSPT，S；keytypekey；intselect=0，flag=l；T=null；while(flag)//主菜單{printf(〞1…CreateBsort_tree\n〞)；printf(〞2…Insertkey\n〞)；printf(〞3…Searchkey\n〞)；printf(〞4…Quit\n〞)；printf(〞Pleaseselect：\n〞)；scanf(〞%d〞，＆select)；switch(select){casel：//創(chuàng)立二叉排序樹(shù){printf(〞PleaseinputkeytocreateBsort_Tree：\n〞)；scanf(〞%d〞，＆key)；while(key!==0){S=createBst(key)；T=BSTinsert(T，S)；printf(〞continueinput!\n〞)；scanf(“%d〞,＆key)；}printf(〞Bsort_Treeis：\n〞)；BSTPrint(T)；Printf(“\n\n〞)；break；}case2：//在二叉排序樹(shù)中插入關(guān)鍵字{printf(〞Pleaseinputkeywhichinserted：\n〞)；scanf(“%d〞，&key)；S=createBst(key)；T=BSTinsert(T，S)；printf(〞Bsort_Treeis：\n〞)；BSTPrint(T)；printf(〞\n\n〞)；break；}case3：//在二叉排序樹(shù)中查找關(guān)鍵字{printf(〞Pleaseinputkeywhichsearched：\n〞)；scanf(“%d〞，＆key)；search(T，key)；printf(〞\n\n);break；}case4：//產(chǎn)退出{flag=0；break；}}}}哈希表查找基本思想及程序?qū)崿F(xiàn)哈希表查找是一種基于盡可能不通過(guò)比較操作而直接得到記錄的存儲(chǔ)位置的想法而提出的一種特殊查找技術(shù)。它的基本思想是通過(guò)記錄中的關(guān)鍵字的值key為自變量，通過(guò)某一種確定的函數(shù)h，計(jì)算出函數(shù)值h(key)作為存儲(chǔ)地址，將相應(yīng)關(guān)鍵字的記錄存儲(chǔ)到對(duì)應(yīng)的位置上。而在查找時(shí)仍需要用這個(gè)確定的函數(shù)h進(jìn)展計(jì)算，獲得所要查找的關(guān)鍵字所在記錄的存儲(chǔ)位置。除留余數(shù)法(DivisionMethod)是用關(guān)鍵字key除以某個(gè)正整數(shù)M，所得余數(shù)作為哈希地址的方法。對(duì)應(yīng)的哈希函數(shù)h(key)為h(key)=key%M，一般情況下M的取值為不大于表長(zhǎng)的質(zhì)數(shù)。用開(kāi)放定址法解決沖突，形成下一個(gè)地址的形式是Hi=(h(key)+di)%Mi=l，2，…，k(k≤m-1)式中，h(key)為哈希函數(shù)；M為某個(gè)正整數(shù)；di為增量序列。線性探測(cè)再散列是將開(kāi)放定址法中的增量序列di設(shè)定為-系列從1開(kāi)場(chǎng)一直到表長(zhǎng)減l的整數(shù)序列：l，2，3，…,m－1〔m為表長(zhǎng))。算法的關(guān)鍵過(guò)程實(shí)際上就是Hash表的創(chuàng)立和查找兩個(gè)步驟。首先分析Hash表的創(chuàng)立運(yùn)算：將由鍵盤(pán)輸入的關(guān)鍵字key作為自變量，通過(guò)除留余數(shù)法構(gòu)造哈希函數(shù)h，計(jì)算出函數(shù)值h(key)作為存儲(chǔ)地址，將該關(guān)鍵字存儲(chǔ)到對(duì)應(yīng)的位置上。如果產(chǎn)生沖突，那么采用線性探查法，從關(guān)鍵字的哈希地址開(kāi)場(chǎng)向后掃描，直到找到空位置，將該關(guān)鍵字存儲(chǔ)在這個(gè)位置，插入成功；假設(shè)掃描到哈希表的最后仍沒(méi)有找到空位置，那么插入失敗。查找時(shí)仍利用除留余數(shù)法構(gòu)造哈希函數(shù)h，計(jì)算出函數(shù)值h(key)獲得所要查找的關(guān)鍵字所在記錄的存儲(chǔ)位置。假設(shè)存儲(chǔ)位置對(duì)應(yīng)的數(shù)據(jù)元素的值與查找關(guān)鍵字相等，那么查找成功，否那么，采用線性探查法，從關(guān)鍵字的哈希地址開(kāi)場(chǎng)向后掃描，直到找到與關(guān)鍵字相等的數(shù)據(jù)元素，查找成功；假設(shè)掃描到哈希表的最后仍沒(méi)有找到與關(guān)鍵字相等的數(shù)據(jù)元素，那么查找失敗，不存在與關(guān)鍵字相等的數(shù)據(jù)元素。//參考程序#include<stdio.h>//哈希表長(zhǎng)最大值#defineHM20#defineM19#defineFREE0//空閑標(biāo)記#defineSUCESS1//成功#defineUNSUCESS0//不成功typedefintkeytype；//keytype為整型typedefstruct//keytype型關(guān)鍵字key{keytypekey；intcn;