1/1實(shí)驗(yàn)一線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)驗(yàn)?zāi)康模?．掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2．熟練地利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的基本操作。3．能熟練地掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中算法的實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容：1．用頭插法或尾插法建立帶頭結(jié)點(diǎn)的單鏈表。2．實(shí)現(xiàn)單鏈表上的插入、刪除、查找、修改、計(jì)數(shù)、輸出等基本操作。三、實(shí)驗(yàn)要求：1.根據(jù)實(shí)驗(yàn)內(nèi)容編寫程序，上機(jī)調(diào)試、得出正確的運(yùn)行程序。2.寫出實(shí)驗(yàn)報(bào)告（包括源程序和運(yùn)行結(jié)果）。四、實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí)五、實(shí)驗(yàn)步驟：1．進(jìn)入編程環(huán)境，建立一新文件；2.參考以下相關(guān)內(nèi)容，編寫程序，觀察并分析輸出結(jié)果。①定義單鏈表的數(shù)據(jù)類型，然后將頭插法和尾插法、插入、刪除、查找、修改、計(jì)數(shù)、輸出等基本操作都定義成子函數(shù)的形式，最后在主函數(shù)中調(diào)用它，并將每一種操作前后的結(jié)果輸出，以查看每一種操作的效果。②部分參考程序//單鏈表的建立(頭插法)，插入，刪除，查找、修改、計(jì)數(shù)、輸出#include<iostream.h>#defineelemtypeintstructlink{elemtypedata；//元素類型link*next；//指針類型，存放下一個(gè)元素地址};//頭插法建立帶頭結(jié)點(diǎn)的單鏈表link*hcreat(){links,p;elemtypei;cout<<”輸入多個(gè)結(jié)點(diǎn)數(shù)值(用空格分隔)，為0時(shí)算法結(jié)束”；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()；//頭插法建立鏈表print(p)；//輸出剛建立的單鏈表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：}//單鏈表的建立(尾插法)、插入、刪除、查找、修改、計(jì)數(shù)、輸出#include<iostream.h>#defineelemtypeintstructlink{elemtypedata；//元素類型link*next；//指針類型，存放下-個(gè)元素地址}；//尾插法建立帶頭結(jié)點(diǎn)的單鏈表link*rcreat(){link*s，*p，*r；elemtypei；cout<<”輸入多個(gè)結(jié)點(diǎn)數(shù)值(用空格分隔)，為0時(shí)算法結(jié)束”；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()；//尾插法建立鏈表print(p)；//輸出剛建立的單鏈表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．建立一元多項(xiàng)式；2．輸出相應(yīng)的一元多項(xiàng)式；3．相加操作的實(shí)現(xiàn)。實(shí)驗(yàn)二循環(huán)鏈表的操作實(shí)驗(yàn)?zāi)康模和ㄟ^本實(shí)驗(yàn)中循環(huán)鏈表和雙向鏈表的使用，使學(xué)生進(jìn)一步熟練掌握鏈表的操作方式。二、實(shí)驗(yàn)內(nèi)容：本次實(shí)驗(yàn)可以從以下兩個(gè)實(shí)驗(yàn)中任選一個(gè)：1．建立一個(gè)單循環(huán)鏈表并實(shí)現(xiàn)單循環(huán)鏈表上的逆置。所謂鏈表的逆置運(yùn)算(或稱為逆轉(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)容編寫程序，上機(jī)調(diào)試、得出正確的運(yùn)行程序。2.寫出實(shí)驗(yàn)報(bào)告（包括源程序和運(yùn)行結(jié)果）。四、實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí)五、實(shí)驗(yàn)步驟：1．進(jìn)入編程環(huán)境，建立一新文件；2.參考以下相關(guān)內(nèi)容，編寫程序，觀察并分析輸出結(jié)果。①建立一個(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步操作，注意語句的次序，不要任意交換位置，以免不能正確插入或刪除結(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”)；}//建立單循環(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(“輸入所建立的循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù)：\n”)；scanf(“%d”，＆n)；head=creat(n)；printf(”輸出建立的單循環(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ù)用來構(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ù)用來實(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(”沒找到該結(jié)點(diǎn)!\n”)；}//insdulist函數(shù)用來實(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ù)用來輸出整個(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．建立雙向鏈表\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)結(jié)束}此程序不論是插入、查找還是刪除運(yùn)算均是按序號(hào)的方式來處理，當(dāng)然也可改為按結(jié)點(diǎn)的值來作相應(yīng)的處理，試修改以上程序?qū)崿F(xiàn)按值操作的功能。六、選作實(shí)驗(yàn)利用單循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)，解決約瑟夫（Josephus）環(huán)問題。即：將編號(hào)是1,2,…,n(n>0)的n個(gè)人按照順時(shí)針方向圍坐一圈，每人持有一個(gè)正整數(shù)密碼。開始時(shí)任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從某個(gè)人開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有的人全部出列為止。令n最大值取30。設(shè)計(jì)一個(gè)程序，求出出列順序，并輸出結(jié)果。實(shí)驗(yàn)三樹形結(jié)構(gòu)實(shí)驗(yàn)?zāi)康模?．掌握二叉樹的數(shù)據(jù)類型描述及二叉樹的特性。2．掌握二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(二叉鏈表)的建立算法。3．掌握二叉鏈表上二叉樹的基本運(yùn)算的實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容：從以下1、2和3、4中各選擇一項(xiàng)內(nèi)容1.用遞歸實(shí)現(xiàn)二叉樹的先序、中序、后序3種遍歷。2.用非遞歸實(shí)現(xiàn)二叉樹的先序、中序、后序3種遍歷。3.實(shí)現(xiàn)二叉樹的層次遍歷。4.將一棵二叉樹的所有左右子樹進(jìn)行交換。實(shí)驗(yàn)要求：1.根據(jù)實(shí)驗(yàn)內(nèi)容編程，上機(jī)調(diào)試、得出正確的運(yùn)行程序。2.寫出實(shí)驗(yàn)報(bào)告（包括源程序和運(yùn)行結(jié)果）。四、實(shí)驗(yàn)學(xué)時(shí)：4學(xué)時(shí)五、實(shí)驗(yàn)步驟：1．進(jìn)入編程環(huán)境，建立一新文件；2.參考以下相關(guān)內(nèi)容，編寫程序，觀察并分析輸出結(jié)果。將建立二叉樹及先序、中序、后序3種遍歷算法都寫成子函數(shù)，然后分別在主函數(shù)中調(diào)用它，但在建立二又樹中，必須把二叉樹看成完全二叉樹的形式。若不是完全二叉樹，則在輸入數(shù)據(jù)時(shí)，用虛結(jié)點(diǎn)(不存在)表示(本算法中，用“，”號(hào)代替)。用非遞歸法實(shí)現(xiàn)二叉樹的遍歷非遞歸算法中，必須設(shè)置堆棧，可以直接用一維數(shù)組來代替棧，但必須另外設(shè)置棧頂指針。③實(shí)現(xiàn)二叉樹的層次遍歷用一個(gè)一維數(shù)組代替隊(duì)列，實(shí)現(xiàn)二叉樹的層次遍歷。④將一棵二叉樹的所有左右子樹進(jìn)行交換。本算法只要增加一個(gè)實(shí)現(xiàn)二叉樹左右子樹交換的子函數(shù)即可。為了便于查看，在主函數(shù)將交換前后的三種遍歷效果，分別輸出。以下為部分參考程序：//遞歸實(shí)現(xiàn)二叉樹的3種遍歷#include<iostream.h>typedefcharelemtype；structbitree{定義二叉樹數(shù)據(jù)類型elemtypedata；//結(jié)點(diǎn)信息bitree*lchild，*rchild；//左右孩子};bitree*create()//建立二叉鏈表{bitree*root,*s，*q[100]；//q為隊(duì)列，最大空間為100intfront=l，rear=0；//隊(duì)列頭、尾指針charch；root=NULL；cout<<”請(qǐng)輸入結(jié)點(diǎn)值(‘，’為虛結(jié)點(diǎn)，‘#’結(jié)束)：”<<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()；//建立二叉鏈表cout<<”先序遍歷的結(jié)果”<<endl；preorder(root)；cout<<endl；cout<<”中序遍歷的結(jié)果”<<endl；inorder(root)；cout<<endl：cout<<”后序遍歷的結(jié)果”<<endl；postorder(root)；cout<<endl；}//用非遞歸實(shí)現(xiàn)二叉樹的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)；}//建立二叉鏈表參考前述程序//按照層次遍歷二叉鏈表#include<iostream.h>typedefcharelemtype；structbitree{elemtypedata；//結(jié)點(diǎn)信息bitree*lchild，*rchild；//左右孩子};//按層次遍歷二叉樹(建立二叉鏈表同前)voidlorder(bitree*t){bitreeq[100]，*p；//q代表隊(duì)列intf,r;//f，r類似于隊(duì)列頭、尾指針q[1]=t；f=r=l；cout<<”按層次遍歷二叉樹的結(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；//建立二叉鏈表lorder(t)；//：按層次遍歷二叉樹}//將二叉樹的左右子樹進(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()；//建立二叉鏈表cout<<endl<<endl<<”左右子樹交換前的遍歷結(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<<”左右子樹交換后的遍歷結(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，建立哈夫曼樹，輸出哈夫曼編碼。2.對(duì)上述給定的哈夫曼樹及得到的哈夫曼編碼，試輸入一串二進(jìn)制編碼，輸出它的哈夫曼譯碼。算法提示：將建立哈夫曼樹、實(shí)現(xiàn)哈夫曼編、哈夫曼譯碼都定義成子函數(shù)的形式，然后在主函數(shù)調(diào)用它們。建立哈夫曼樹時(shí)，將哈夫曼樹的結(jié)構(gòu)定義為一個(gè)結(jié)構(gòu)型的一維數(shù)組，每個(gè)元素含有四項(xiàng)：雙親、左孩子、右孩子。給定的權(quán)值可以從鍵盤輸入，要輸出所建立的哈夫曼樹，只要輸出哈夫曼樹的一維數(shù)組中全部元素即可。要實(shí)現(xiàn)哈夫曼編碼，只要在所建立的哈夫曼樹上進(jìn)行二進(jìn)制編碼：往左走，編碼為0，往右走，編碼為1，然后將從根結(jié)點(diǎn)到樹葉中所有0、l排列起來，則得到該樹葉的哈夫曼編碼。哈夫曼編碼可以用一個(gè)結(jié)構(gòu)型的一維數(shù)組保存，每個(gè)元素包含：編碼、編碼的開始位置、編碼所對(duì)應(yīng)的字符等3項(xiàng)。哈夫曼譯碼，就是將輸入的編碼還原成對(duì)應(yīng)的字符。實(shí)驗(yàn)四圖的遍歷操作實(shí)驗(yàn)?zāi)康模?.掌握?qǐng)D的含義。2.掌握用鄰接矩陣和鄰接表的方法描述圖的存儲(chǔ)結(jié)構(gòu)。3.理解并掌握深度優(yōu)先遍歷和廣度優(yōu)先遍歷的存儲(chǔ)結(jié)構(gòu)。二、實(shí)驗(yàn)內(nèi)容：從以下1、2和3、4中各選擇一項(xiàng)內(nèi)容1.建立無向圖的鄰接矩陣，并實(shí)現(xiàn)插入、刪除邊的功能。2.建立有向圖的鄰接表，并實(shí)現(xiàn)插入、刪除邊的功能。3.建立一個(gè)包含6個(gè)結(jié)點(diǎn)的圖，并實(shí)現(xiàn)該圖的深度優(yōu)先搜索遍歷。4.建立一個(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.寫出實(shí)驗(yàn)報(bào)告（包括源程序和運(yùn)行結(jié)果）。四、實(shí)驗(yàn)學(xué)時(shí)：4學(xué)時(shí)五、實(shí)驗(yàn)步驟：1.進(jìn)入編程環(huán)境，建立一新文件；2.參考以下相關(guān)內(nèi)容，編寫程序，觀察并分析輸出結(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ù)結(jié)構(gòu)。對(duì)于實(shí)際問題，需要根據(jù)具體圖的結(jié)構(gòu)特點(diǎn)以及所要實(shí)施的操作，選擇建立合適的存儲(chǔ)結(jié)構(gòu)。圖的存儲(chǔ)結(jié)構(gòu)包括鄰接矩陣和鄰接表。鄰接矩陣：用一維數(shù)據(jù)組存儲(chǔ)圖中頂點(diǎn)的信息，用矩陣表示圖中各頂點(diǎn)之間的相鄰關(guān)系。它屬于靜態(tài)存儲(chǔ)方法。鄰接表：鄰接表存儲(chǔ)方法是一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法。順序存儲(chǔ)部分用來保存圖中頂點(diǎn)的信息，鏈?zhǔn)酱鎯?chǔ)部分用來保存圖中邊的信息。//鄰接矩陣的存儲(chǔ)結(jié)構(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)的結(jié)構(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)造有向圖鏈接表與無向圖鏈接表的算法區(qū)別是：無向圖兩結(jié)點(diǎn)無向?qū)ε迹蚨徑颖碛幸欢ǖ膶?duì)偶性；有向圖兩結(jié)點(diǎn)間有向無對(duì)偶關(guān)系，因而建立鄰接表時(shí)應(yīng)根據(jù)輸入的頂點(diǎn)及邊的有向關(guān)系建立(當(dāng)箭頭方向離開結(jié)點(diǎn)為有關(guān)，當(dāng)箭頭方向指向結(jié)點(diǎn)為無關(guān))。//內(nèi)容2的參考程序//有向圖鏈表的存儲(chǔ)結(jié)構(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]；//參考程序見內(nèi)容1內(nèi)容3的知識(shí)要點(diǎn)：深度優(yōu)先搜索遍歷圖的算法：首先訪問指定的起始頂點(diǎn)v0，從vo出發(fā)，訪問vo的一個(gè)未被訪問過的鄰接頂點(diǎn)w1，再從w1出發(fā)，訪問w1的一個(gè)未被訪問的頂點(diǎn)w2，然后從w2出發(fā)，訪問w2的一個(gè)未被訪問的鄰接頂點(diǎn)w3，依此類推，直到一個(gè)所有鄰接點(diǎn)都被訪問過為止。圖采用鄰接表作存儲(chǔ)結(jié)構(gòu)，圖的深度優(yōu)先遍歷次序?yàn)棰佟凇堋荨蕖蹍⒖汲绦蜻\(yùn)行過程中，深度優(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//定義結(jié)構(gòu)體{intadivex；intweigh；structst_arc*nextarc；}arcnode；typedefstruct{intvertex；structst_arc*firstarc；}vernode；typedefvernodeadjlist[maxnode]；voidtrave(adjlistg，intn)//采用鄰接表作存儲(chǔ)結(jié)構(gòu)的/深度優(yōu)先遍歷{inti，visited[maxnode]；//數(shù)組visited標(biāo)志圖中的定點(diǎ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)先遍歷圖的算法：首先訪問指定的起始頂點(diǎn)v0,從v0出發(fā)，訪問v0的所有未被訪問的鄰接頂點(diǎn)w1，w2，…，wk，然后再依次從w1，w2，…，wk出發(fā)，訪問所有未被訪問過的鄰接頂點(diǎn)，依此類推，直到圖中所有未被訪問過的鄰接頂點(diǎn)都被訪問過為止。根據(jù)廣度優(yōu)點(diǎn)遍歷的規(guī)則，在其算法實(shí)現(xiàn)中，借助一個(gè)隊(duì)列g(shù)－queue來存放已被訪問過的頂點(diǎn)。從指定頂點(diǎn)開始，每訪問一個(gè)頂點(diǎn)，就將它入隊(duì)并排在隊(duì)尾，然后從隊(duì)頭取出一個(gè)頂點(diǎn)，訪問該頂點(diǎn)的所有未被訪問的鄰接點(diǎn)，依此類推，直至隊(duì)列為空且圖中結(jié)點(diǎn)均被訪問過為止。圖的廣度優(yōu)先遍歷次序?yàn)椋孩佟凇邸堋荨迏⒖汲绦蜻\(yùn)行過程中，廣度優(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//定義結(jié)構(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;//訪問點(diǎn)從k開始，并把它入隊(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)是否已被訪問。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í)現(xiàn)。4.掌握Hash表查找的算法與實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容：從以下1、2和3、4中各選擇一項(xiàng)內(nèi)容1.建立一個(gè)線性表，對(duì)表中數(shù)據(jù)元素存放的先后次序沒有任何要求。輸入待查數(shù)據(jù)元素的關(guān)鍵字進(jìn)行查找。（為了簡化算法，數(shù)據(jù)元素只含一個(gè)整型量關(guān)鍵字字段，數(shù)據(jù)元素的其余數(shù)據(jù)部分忽略不考慮。）2.查找表的存儲(chǔ)結(jié)構(gòu)為有序表，即表中記錄按關(guān)鍵字大小排序存放。輸入待查數(shù)據(jù)元素的關(guān)鍵字進(jìn)行查找。（為了簡化算法，記錄只含一個(gè)整型量關(guān)鍵字字段，記錄的其余數(shù)據(jù)部分略不考慮。程序要求對(duì)整型量關(guān)鍵字?jǐn)?shù)據(jù)的輸入按從小到大排序輸入。）3.編程實(shí)現(xiàn)二叉排序樹的創(chuàng)建、查找、插入、輸出等算法。4.設(shè)哈希表長為20，用除留余數(shù)法構(gòu)造一個(gè)哈希函數(shù)，以開放定址法中的線性探測再散列法作為解決沖突的方法，編程實(shí)現(xiàn)哈希表查找、插入和建立算法。三、實(shí)驗(yàn)要求：1.根據(jù)實(shí)驗(yàn)內(nèi)容編程，上機(jī)調(diào)試、得出正確的運(yùn)行程序。2.寫出實(shí)驗(yàn)報(bào)告（包括源程序和運(yùn)行結(jié)果）。四、實(shí)驗(yàn)學(xué)時(shí)：6學(xué)時(shí)五、實(shí)驗(yàn)步驟：1．進(jìn)入編程環(huán)境，建立一新文件；2.參考以下相關(guān)內(nèi)容，編寫程序，觀察并分析輸出結(jié)果。順序查找的基本思想及程序?qū)崿F(xiàn)對(duì)于給定的關(guān)鍵字k，從表的一端開始，逐個(gè)進(jìn)行數(shù)據(jù)元素的關(guān)鍵字和給定值的比較，若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與k相等則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于k的節(jié)點(diǎn)，則查找失敗。建立一個(gè)順序表，數(shù)據(jù)元素從下標(biāo)為1的單元開始放入，下標(biāo)為0的單元起監(jiān)視哨作用，將待查的關(guān)鍵字存入下標(biāo)為0的單元，順序表從后向前查找，若直到下標(biāo)為0時(shí)才找到關(guān)鍵字則說明查找失敗；若不到下標(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)輸入順序表元素，元素為整型量，用空格分開，-99為結(jié)束標(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)鍵字比較：若key=r[mid].key，查找成功，下標(biāo)為m的記錄即為所求，返回mid。若key<r[mid].key，所要找的記錄只能在左半部分記錄中，再對(duì)左半部分使用折半查找法繼續(xù)進(jìn)行查找，搜索區(qū)間縮小了一半。若key>r[mid].key，所要找的記錄只能在右半部分記錄中，再對(duì)右半部分使用折半查找法繼續(xù)進(jìn)行查找，搜索區(qū)間縮小了一半。重復(fù)上述過程，直到找到查找表中某一個(gè)數(shù)據(jù)元素的關(guān)鍵字的值等于給定的值key說明查找成功；或者出現(xiàn)low的值大于high的情況，說明查找不成功。建立一個(gè)有序表，數(shù)據(jù)元素從下標(biāo)為1的單元開始放入。實(shí)現(xiàn)查找算法時(shí)，首先將low賦值為l，high等于最后一個(gè)數(shù)據(jù)元素的下標(biāo)，然后將給定的關(guān)鍵字的值與查找區(qū)間[low，high]中間的數(shù)據(jù)元素的關(guān)鍵字比較，實(shí)現(xiàn)查找過程。//參考程序#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)輸入有序表元素，元素為整型量(從小到大輸入)，用空格分開，-99為結(jié)束標(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")；}二叉排序樹基本思想及程序?qū)崿F(xiàn)二叉排序樹就是指將原來已有的數(shù)據(jù)根據(jù)大小構(gòu)成一棵二叉樹，二叉樹中的所有結(jié)點(diǎn)數(shù)據(jù)滿足一定的大小關(guān)系，所有的左子樹中的結(jié)點(diǎn)均比根結(jié)點(diǎn)小，所有的右子樹的結(jié)點(diǎn)均比根結(jié)點(diǎn)大。二叉排序樹查找是指按照二叉排序樹中結(jié)點(diǎn)的關(guān)系進(jìn)行查找，查找關(guān)鍵字首先同根結(jié)點(diǎn)進(jìn)行比較，如果相等則查找成功；如果比根結(jié)點(diǎn)小，則在左子樹中查找；如果比根結(jié)點(diǎn)大，則在右子樹中進(jìn)行查找。這種查找方法可以快速縮小查找范圍，大大減少查找關(guān)鍵字的比較次數(shù)，從而提高查找效率。算法的關(guān)鍵過程實(shí)際上就是二叉排序樹的創(chuàng)建和查找兩個(gè)步驟。首先分析二叉排序樹的創(chuàng)建運(yùn)算，由于二叉排序樹中的所有結(jié)點(diǎn)都有一個(gè)大小關(guān)系，因此，每個(gè)結(jié)點(diǎn)必須在二叉排序樹中尋找其合適的位置。創(chuàng)建二叉排序樹的第一步就是創(chuàng)建一個(gè)根結(jié)點(diǎn)，第二步就是將其他結(jié)點(diǎn)不斷插入到二叉排序樹中的合適位置。二叉排序樹進(jìn)行結(jié)點(diǎn)插入時(shí)，首先要為被插入結(jié)點(diǎn)尋找合適的插入位置。這個(gè)過程實(shí)際上就是一個(gè)關(guān)鍵值不斷的比較的過程。第一次比較是與二叉排序樹的根結(jié)點(diǎn)比較，如果比根結(jié)點(diǎn)的關(guān)鍵值小，則插入到他的左子樹中；如果比根結(jié)點(diǎn)的關(guān)鍵值大，則插入到它的右子樹中。在子樹中重復(fù)這樣過程，直到找到合適的位置為止。二叉排序樹的查找運(yùn)算實(shí)際上同二叉排序樹的創(chuàng)建運(yùn)算是一致的。區(qū)別在于，創(chuàng)建過程中要為二叉排序樹中沒有位置的關(guān)鍵字建立結(jié)點(diǎn)，而查找過程中，只是在二叉排序樹中查找是否等于查找關(guān)鍵字值的結(jié)點(diǎn)存在，不管有還是沒有，它都不會(huì)創(chuàng)建一個(gè)新的結(jié)點(diǎn)。//參考程序#include<stdio.h>#include<malloc.h>#definenull0typedefintkeytype；//查找關(guān)鍵字為整型數(shù)據(jù)sturcBsnode//二叉排序樹結(jié)點(diǎn)類型{keytypedata；//數(shù)據(jù)域structBsnode*Lchild,*Rchild；//左右指針};typedefstructBsnodeBST；typedefstructBsnode*BSP；//BSP為二叉排序樹結(jié)點(diǎn)類型指針BSPcreateBst(keytypekey)//為關(guān)鍵字key創(chuàng)建一個(gè)二叉排序樹結(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指向的二叉排序樹中{BSPq,p;if(T==null)return(S);else{p=T;q=null;while(p)//在二叉排序樹中為s結(jié)點(diǎn)尋找插入位置{q=p；if(s->data==p->data)//如果S結(jié)點(diǎn)與二叉排序樹中根結(jié)點(diǎn)的值相等，則不插入{printf(“Theinputkey(%d)ishavein!”，s->data)；return(t)；}if(s->data<p->date)//如果比根結(jié)點(diǎn)值小，則在左子樹中尋找插入位置p=p->Lchild；else//否則在右子樹中尋找插入位置p=p->Rchild；}if(s->data<q->data)q->Lchild=s；//作為左孩子插入elseq->Rchild=s；//作為右孩子插入return(t)；}}voidsearch(BSPT，keytypex)//在二叉排序樹T中查找是否存在關(guān)鍵宇{BSPp；if(T==null){printf(“error\n”);return;}else{p=Twhile(p){if(p->data==x)//如果根結(jié)點(diǎn)是查找的關(guān)鍵字，查找結(jié)束{printf(“searchsuccess!\n”)；return；}elseif(x<p->-data)//如果小于根結(jié)點(diǎn)，則在左于樹中查找p=p->Lchild；elsep=p->Rchild；//否則，在右子樹中查找}if(!p)printf(”%dnotexist!\n”，x)；}}voidBSTPrint(BSPT)//輸出二叉排序樹{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)建二叉排序樹{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：//在二叉排序樹中插入關(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：//在二叉排序樹中查找關(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)哈希表查找是一種基于盡可能不通過比較操作而直接得到記錄的存儲(chǔ)位置的想法而提出的一種特殊查找技術(shù)。它的基本思想是通過記錄中的關(guān)鍵字的值key為自變量，通過某一種確定的函數(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ì)數(shù)。用開放定址法解決沖突，形成下一個(gè)地址的形式是Hi=(h(key)+di)%Mi=l，2，…，k(k≤m-1)式中，h(key)為哈希函數(shù)；M為某個(gè)正整數(shù)；di為增量序列。線性探測再散列是將開放定址法中的增量序列di設(shè)定為-系列從1開始一直到表長減l的整數(shù)序列：l，2，3，…,m－1（m為表長)。算法的關(guān)鍵過程實(shí)際上就是Hash表的創(chuàng)建和查找兩個(gè)步驟。首先分析Hash表的創(chuàng)建運(yùn)算：將由鍵盤輸入的關(guān)鍵字key作為自變量，通過除留余數(shù)法構(gòu)造哈希函數(shù)h，計(jì)算出函數(shù)值h(key)作為存儲(chǔ)地址，將該關(guān)鍵字存儲(chǔ)到對(duì)應(yīng)的位置上。如果產(chǎn)生沖突，則采用線性探查法，從關(guān)鍵字的哈希地址開始向后掃描，直到找到空位置，將該關(guān)鍵字存儲(chǔ)在這個(gè)位置，插入成功；若掃描到哈希表的最后仍沒有找到空位置，則插入失敗。查找時(shí)仍利用除留余數(shù)法構(gòu)造哈希函數(shù)h，計(jì)算出函數(shù)值h(key)獲得所要查找的關(guān)鍵字所在記錄的存儲(chǔ)位置。若存儲(chǔ)位置對(duì)應(yīng)的數(shù)據(jù)元素的值與查找關(guān)鍵字相等，則查找成功，否則，采用線性探查法，從關(guān)鍵字的哈希地址開始向后掃描，直到找到與關(guān)鍵字相等的數(shù)據(jù)元素，查找成功；若掃描到哈希表的最后仍沒有找到與關(guān)鍵字相等的數(shù)據(jù)元素，則查找失敗，不存在與關(guān)鍵字相等的數(shù)據(jù)元素。//參考程序#include<stdio.h>//哈希表長最大值#defineHM20#defineM19#defineFREE0//空閑標(biāo)記#defineSUCESS1//成功#defineUNSUCESS0//不成功typedefintkeytype；//keytype為整型typedefstruct//keytype型關(guān)鍵字key{keytypekey；intcn;//查找次數(shù)}hashtable；//哈希表類型inth(keytypekey)//哈希函數(shù){return(key%M)；}intHashSearch(hashtableht[],keytyoekey)//哈希表查找函數(shù)｛intd，i;i=0;d=h(key)；//求哈希地址ht[d].cn=0；while((ht[d].key!=key)&&(ht[d].key!=FREE)&&(i<HM)){i++;//求下一個(gè)地址ht[d].cn++;//查找次數(shù)加1d=(d+i)%M;//線性探查記錄的插入位置}if(i>=HM){printf(”Thehashtableisfull!\n)；return(UNSUCESS)；}return(d);//若h[d]的關(guān)鍵字等于key說明查找成功}intHashInsert(hashtableht[]，keytypekey){//產(chǎn)哈希表插入函數(shù)，查找不成功的時(shí)候，將給定關(guān)鍵字key插入哈希表中intd;d=HashSearch(ht，key)；if(ht[d].key==FREE){ht[d].key=key；printf(“Insertsucess!\n”);return(SUCESS)；//插入成功}else{printf(”Uncessful!\n”)；return(UNSUCESS)；//插入不成功}}voidHashCreat(hashtableht[])//建立哈希表的函數(shù){inti，n;keytypekey1；printf(”請(qǐng)輸入元素個(gè)數(shù)(要小于表長%d)：\n”，HM)；scanf(”%d”，&n)；for(i=0；i<n；i++){printf(”請(qǐng)輸入元素關(guān)鍵字：\n”)；scanf(”%d”，&keyl)；HashInsert(ht，keyl)；//調(diào)用哈希表插入算法}}Voidmain(){hashtableht[HM]；//哈希表空間keytypekey=0；inti；for(i=0；i<HM；i++){ht[i].key=0；}printf(”建立哈希表\n”)；HashCreat(ht)；printf(“請(qǐng)輸入要查找元素關(guān)鍵字的值：\n”)；scanf(“%d”，＆key)；i=HashSearch(ht，key)；if(ht[i].key==key){printf(“表中存在關(guān)鍵字為%d的元素：\n”,key);printf(“該元素的位置為%d\n”，i);}elseprintf(“沒有查找到\n”)；}六、選作實(shí)驗(yàn)編程實(shí)現(xiàn)一個(gè)開放式的高校本科招生最低錄取分?jǐn)?shù)線的查詢系統(tǒng)，供師生和家長查詢。高校自愿放入該校的信息，可能隨時(shí)有高校加入。要求實(shí)現(xiàn)的查詢功能有：①查詢等于用戶給定分?jǐn)?shù)的高校；②查詢大于(或小于)用戶給定分?jǐn)?shù)的高校；③查詢最低錄取分?jǐn)?shù)線在用戶給定的分?jǐn)?shù)段中的高校。該實(shí)驗(yàn)主要的功能是查找，查找表為高校最低錄取分?jǐn)?shù)信息的集合。根據(jù)題意可知，該查找表中的元素個(gè)數(shù)可能隨時(shí)增減，所以它是一個(gè)動(dòng)態(tài)查找表，可采用樹狀結(jié)構(gòu)保存。為了提高查詢速度，可建立二叉排序樹并在二叉排序樹中實(shí)現(xiàn)查找。第一個(gè)要求可以直接利用一般的二叉排序樹的查找算法實(shí)現(xiàn)。第二個(gè)要求可以利用比較二叉排序樹根結(jié)點(diǎn)的關(guān)鍵字值和給定的分?jǐn)?shù)實(shí)現(xiàn)，若前者大于或等于后者，根結(jié)點(diǎn)及其右子樹中的結(jié)點(diǎn)全部滿足要求，再在根結(jié)點(diǎn)的左子樹中查找；否則只在根結(jié)點(diǎn)的右子樹中查找即可。第三個(gè)要求可以利用比較二叉排序樹根結(jié)點(diǎn)的關(guān)鍵字值和給定的分?jǐn)?shù)段實(shí)現(xiàn)，若前者在給定的分?jǐn)?shù)段中，根結(jié)點(diǎn)就滿足要求，則在根結(jié)點(diǎn)的左、右子樹中繼續(xù)查找即可：若前者給定的分?jǐn)?shù)段的左側(cè)，只在根結(jié)點(diǎn)的右子樹中查找即可；若前者在給定的分?jǐn)?shù)段的右側(cè)，只根節(jié)點(diǎn)的左子樹中查找即可。實(shí)驗(yàn)六排序?qū)嶒?yàn)?zāi)康模?．掌握各種排序的基本思想。．2．掌握各種排序方法的算法實(shí)現(xiàn)。3．掌握各種排序方法的優(yōu)劣及花費(fèi)時(shí)間的計(jì)算。4．掌握各種排序方法所適應(yīng)的不同場合。二、實(shí)驗(yàn)內(nèi)容：從以下1、2中各選擇一項(xiàng)內(nèi)容1．隨機(jī)函數(shù)產(chǎn)生10000個(gè)隨機(jī)數(shù)，用直接