實驗一 線性表的鏈式存儲結構一、 實驗目的： 1掌握線性表的鏈式存儲結構。2熟練地利用鏈式存儲結構實現線性表的基本操作。 3能熟練地掌握鏈式存儲結構中算法的實現。二、實驗內容： 1用頭插法或尾插法建立帶頭結點的單鏈表。 2實現單鏈表上的插入、刪除、查找、修改、計數、輸出等基本操作 。三、實驗要求：1. 根據實驗內容編寫程序，上機調試、得出正確的運行程序。2. 寫出實驗報告（包括源程序和運行結果）。四、實驗學時：2學時五、實驗步驟：1進入編程環境，建立一新文件；2. 參考以下相關內容，編寫程序，觀察并分析輸出結果。 定義單鏈表的數據類型，然后將頭插法和尾插法、插入、刪除、查找、修改、計數、輸出等基本操作都定義成子函數的形式，最后在主函數中調用它，并將每一種操作前后的結果輸出，以查看每一種操作的效果。 部分參考程序/單鏈表的建立(頭插法)，插入，刪除，查找、修改、計數、輸出 #include #define elemtype intstruct link elemtype data；/元素類型 link *next； /指針類型，存放下一個元素地址; /頭插法建立帶頭結點的單鏈表 link *hcreat() link s,p; elemtype i; couti； p=new link； p-next=NULL； while(i) /當輸入的數據不為0時，循環建單鏈表 s=new link； s-data=i； s-next=p-next； p-next=s； cini； return p；/輸出單鏈表void print(1ink *head) 1ink *p； p=head-next； while(p-next!=NULL) coutdata”； /輸出表中非最后一個元素p=p-next； coutdata； /輸出表中最后一個元素 coutnext； while(p!=NULL)&(p-data!=x) p=p-next； return p； /在head為頭指針的單鏈表中，刪除值為x的結點 void deletel(1ink *head，elemtype x) 1ink *p， *q； q=head； p=head-next； while(p!=NULL)&(p-data!=x) q=p；p=p-next；If(p=NULL) coutnext=p -next；delete(p)；/在頭指針head所指的單鏈表中，在值為x的結點之后插入值為y的結點void insert(1ink *head，elemtype x，elemtype y) link *p， *s； s=new link； s-data=y； if(head-next=NULL) /鏈表為空head-next=s；s-next=NULL： p=Locate(head，x)；/調用查找算法 if(p=NULL)coutnext=p-next；p-next=s；/將單鏈表p中所有值為x的元素修改成yvoid change(1ink *p,elemtype x,elemtype y)link *q；q=p-next；while(q!=NULL) if(q-data=x) q-data=y； q=q-next； void count(1ink *h) /統計單鏈表中結點個數1ink *p；int n=0；p=h-next；while(p!=NULL)n+；p=p-next；return n;void main() int n； elemtype x，y； link *p， *q； p=hcreat()； /頭插法建立鏈表 print(p)； /輸出剛建立的單鏈表 couty； deletel(p，y)； print(p)； /輸出刪除后的結果 coutx； couty； insert(p，x，y)； print(p)； /輸出插入后的結果 coutxy； change(p，x，y)； print(p)； coutx； q=Locate(p，x)； if(q=NULL)coutx”不在表中，找不到!”endl； else coutx”在表中，已找到!”endl； n=count(p)； cout”鏈表中結點個數為：”nendl： /單鏈表的建立(尾插法)、插入、刪除、查找、修改、計數、輸出#include#define elemtype intstruct link elemtype data；/元素類型 link *next；/指針類型，存放下-個元素地址；/尾插法建立帶頭結點的單鏈表link *rcreat() link *s， *p， *r； elemtype i；couti; p=r=new link； p-next=NULL； while(i) s=new link； s-data=i； r-next=s； r=s； cini； r-next=NULL；return p；/輸出單鏈表void print(1ink *head)link *p； p=head-next； while(p-next!=NULL) coutdata”; /輸出表中非最后一個元素 p=p-next； ) coutdata； /輸出表中最后一個元素 coutendl； link *Locate(1ink *head，int x) 在單鏈表中查找第x個結點 link *p； p=head； int j=0； while(p!=NULL)&(jnext; j+； return p； void delete I(1ink *head，elemtype x)/在head為頭指針的單鏈表中，刪除值為x的結點 link *p, *q； q=head； p=head-next； while(p!=NULL)&(p-data!=x) q=p； p=p-next；) if(p=NULL)coutnext=p-next；delete(p)； void insert(1ink *head，int x,elemtype y)/在頭指針head所指單鏈表中，在第x個結點之后插入值為y的結點link *p， *s； s=new link； s-data=y； if(head-next=NULL)/鏈表為空 head-next=s； s-next=NULL： p=Locate(head，x)； /調用查找算法 if(p=NULL) coutnext=p-next；p-next=s；void change(1ink *p,elemtype x，elemtype y)將單鏈表P中所有值為x的元素改成值為ylink *q； q=p-next； while(q!=NULL) if(q-data=x)q-data=y； q=q-next； void count(1ink *h) /統計單鏈表中結點個數(1ink *p；int n=0；p=h-next；while(p!=NULL)n+；p=p-next； retum n;void main() int n; link p,q;p=rcreat()；/尾插法建立鏈表print(p)； /輸出剛建立的單鏈表couty；deletel(p，y)；print(p)； /輸出刪除后的結果coutx；couty；insert(p，x，y)；print(p)； /輸出插入后的結果coutxy；change(p，x，y)；print(p)；coutx；q=Locate(p ,x)；if(q=NULL)coutx”不在表中,找不到!”endl；else coutx”在表中，已找到!”endl；n=count(p)；cout”鏈表中結點個數為：”nendl;六、選作實驗試設計一元多項式相加（鏈式存儲）的加法運算。 A（X）=7+3X+9X8+5X9 B（X）=8X+22X7-9X8 1建立一元多項式； 2輸出相應的一元多項式； 3相加操作的實現。實驗二 循環鏈表的操作一、 實驗目的： 通過本實驗中循環鏈表和雙向鏈表的使用，使學生進一步熟練掌握鏈表的操作方式。二、實驗內容： 本次實驗可以從以下兩個實驗中任選一個： 1建立一個單循環鏈表并實現單循環鏈表上的逆置。 所謂鏈表的逆置運算(或稱為逆轉運算)是指在不增加新結點的前提下，依次改變數據元素的邏輯關系，使得線性表(al，a2，a3，an)成為(an，a3，a2，a1)。2. 構建一個雙向鏈表，實現插入、查找和刪除操作。三、實驗要求：1. 根據實驗內容編寫程序，上機調試、得出正確的運行程序。2. 寫出實驗報告（包括源程序和運行結果）。四、實驗學時：2學時五、實驗步驟：1進入編程環境，建立一新文件；2. 參考以下相關內容，編寫程序，觀察并分析輸出結果。 建立一個帶頭結點的單循環鏈表，從頭到尾掃描單鏈表L，把p作為活動指針，沿著鏈表向前移動，q作為p前趨結點，r作為q的前趨結點。其中，q的next值為r；r的初值置為head。 雙向鏈表的構造與單鏈表相同，至于它的插入與刪除運算比單鏈表復雜，插入運算需要4步操作，刪除運算需要2步操作，注意語句的次序，不要任意交換位置，以免不能正確插入或刪除結點。 部分參考程序/循環鏈表 頭文件h1h的內容 #define NULL 0 #include #include typedef struct node int num； struct node *next；linklist；以下是主程序#include”h1h”輸出循環鏈表的信息void output(linklist *head)linklist *p；p=head-next；while(p!=head)printf(”d”，p-num)；p=p-next；printf(”n”)；/建立單循環鏈表Linklist *creat(int n) int k; linklist *head,*r,*p； p=(linklist*)malloc(sizeof(linklist)； head=p； r=p； p-next=p；for(k=1；knum=k； r-next=p； r=p； p-next=head；return(head)；逆置函數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)； void main() int n； Linklist *head； printf(“輸入所建立的循環鏈表的結點個數：n”)； scanf(“%d”，n)； head=creat(n)； printf(”輸出建立的單循環鏈表：n”)； output(head)； printf(”現在進行逆置! n”)； head=invert(head)； printf(”輸出進行逆置運算后的單循環鏈表的結點信息! n”)； output(head)； /雙向鏈表參考程序 /以下是頭文件hhh的內容 #include #include typedef struct dupnode int data； struct dupnode *next,*prior；dulinklist；/以下是主程序的內容#include”hhh”/create函數用來構建雙向鏈表dulinklist *create()dulinklist *head,*p，*r; int i，n；head=(dulinklist*)malloc(sizeof(dulinklist )；head-next=NULL；head-prior=NULL；r=head；printf(“請輸入所建雙向鏈表中結點的個數：n”)；scanf(“d”,n)；for(i=l；idata)； p-next=NULL； r-next=p； p-prior=r； r=r-next； return(head)；/find函數用來實現在雙向鏈表中按序號查找某個結點的功能。void find(dulinklist *h)int k,i；dulinklist *p；p=h；i=0：printf(”輸入要查找結點的序號：n”)； scanf(”%d”,&k)； while(p!=NULL)&(inext； i+： if(p)printf(”所查到的結點的值為：n”)； printf(”%dn”,p-data)； elseprintf(”沒找到該結點! n”)；/insdulist函數用來實現在雙向鏈表中按序號插入結點的功能dulinklist *insdulist(dulinklist *head，int i，int x)dulinklist *p，*s；int j；p=head；j=0；whi1e(p-next!=head)&(jnext；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(”errorn”)；return head；/deledulist函數實現在雙向鏈表中按序號刪除某個結點的功能dulinklist *deledulist(dulinklist *head，int i)dulinklist *p；int j；p=head； j=0while(p-next!=head)&(jnext； j+； If(j=i)p-prior-next=p-next；p-next-prior=p-prior；free(p)；else printf(”error n”)；return head； /output函數用來輸出整個雙向鏈表的結點值void output(dulinklist *h) dulinklist *p；p=h-next；while(p!=NULL)printf(”輸出該雙向鏈表的結點，分別為： n”)；printf(”%dn”,p-data)；p=p-next； void main()dulinklist *head；int flag=l，i，k，x；while(flag) /flag作為判斷循環的標志位 printf(”1建立雙向鏈表 n”)； printf(”2查找某個結點 n”)； printf(”3插入一個結點 n”)； prtntf(”4刪除一個結點 n”)； printf(”5退出 n”)；printf(”請輸入選擇：n“)；scanf(”%d”，&i)；switch(i) case 1：head=create0；break； case 2：find(head)；break； case 3：printf(”輸入待插的結點的序號及新插入結點的data值. n”); scanf(”%d%d”，k，x)； head=insdulist(head，k，x)； output(head)； break； case 4：printf(”輸入要刪除的結點的序號. n”)；scanf(”%d，k)；head=deledulist(head，k)；output(head)；break；case 5: flag=0；/while循環結束此程序不論是插入、查找還是刪除運算均是按序號的方式來處理，當然也可改為按結點的值來作相應的處理，試修改以上程序實現按值操作的功能。 六、選作實驗 利用單循環鏈表存儲結構，解決約瑟夫（Josephus）環問題。即：將編號是1,2,n(n0)的n個人按照順時針方向圍坐一圈，每人持有一個正整數密碼。開始時任選一個正整數作為報數上限值m,從某個人開始順時針方向自1開始順序報數，報到m時停止報數，報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數，如此下去，直到所有的人全部出列為止。令n最大值取30。設計一個程序，求出出列順序，并輸出結果。實驗三 樹形結構一、 實驗目的： 1掌握二叉樹的數據類型描述及二叉樹的特性。2掌握二叉樹的鏈式存儲結構(二叉鏈表)的建立算法。3掌握二叉鏈表上二叉樹的基本運算的實現。二、實驗內容： 從以下1、2和3、4中各選擇一項內容1. 用遞歸實現二叉樹的先序、中序、后序3種遍歷。2. 用非遞歸實現二叉樹的先序、中序、后序3種遍歷。3. 實現二叉樹的層次遍歷。4.將一棵二叉樹的所有左右子樹進行交換。 三、 實驗要求： 1. 根據實驗內容編程，上機調試、得出正確的運行程序。2. 寫出實驗報告（包括源程序和運行結果）。四、實驗學時：4學時五、實驗步驟： 1進入編程環境，建立一新文件；2. 參考以下相關內容，編寫程序，觀察并分析輸出結果。 將建立二叉樹及先序、中序、后序3種遍歷算法都寫成子函數，然后分別在主函數中調用它，但在建立二又樹中，必須把二叉樹看成完全二叉樹的形式。若不是完全二叉樹，則在輸入數據時，用虛結點(不存在)表示(本算法中，用“，”號代替)。 用非遞歸法實現二叉樹的遍歷非遞歸算法中，必須設置堆棧，可以直接用一維數組來代替棧，但必須另外設置棧頂指針。 實現二叉樹的層次遍歷 用一個一維數組代替隊列，實現二叉樹的層次遍歷。將一棵二叉樹的所有左右子樹進行交換。 本算法只要增加一個實現二叉樹左右子樹交換的子函數即可。為了便于查看，在主函數將交換前后的三種遍歷效果，分別輸出。以下為部分參考程序：/遞歸實現二叉樹的3種遍歷#includetypedef char elemtype；struct bitree定義二叉樹數據類型elemtype data； /結點信息bitree *lchild，*rchild； /左右孩子;bitree *create() /建立二叉鏈表 bitree *root, *s，*q100； /q為隊列，最大空間為100int front=l，rear=0； /隊列頭、尾指針char ch；root=NULL；cout”請輸入結點值(，為虛結點，#結束)：”ch；while(ch!=#)s=NULL；if(ch!=,) s=new bitree； s-data=ch； s-lchild=NULL； s-rchild=NULL； rear+； qrear=s； /進隊 if(rear=1) root=s；elseif(s!=NULL)&(qfront!=NULL) if(rear%2=0) qfront-lchild=s； else qfront-rchid=s；if(rear2=1)front+； /出隊cinch；return root：void preorder(bitree *root) /先序遍歷bitree *p；p=root；if(p!=NULL)coutdatalchild)； preorder(p-rchild)；void inorderl(bitree *root) /中序遍歷bitree*p；p=root；if(p!=NULL) inorder(p-lchild)； coutdatarchild)；void postorder( bitree *root) /后序遍歷 bitree *p；p=root；if(p!=NULL) postorder(p-lchild)； postorder(p-rchild)；coutdata“”； void main()bitree *root；root=create()； /建立二叉鏈表cout”先序遍歷的結果”endl； preorder(root)；coutendl； cout”中序遍歷的結果”endl；inorder(root)；coutendl：cout”后序遍歷的結果”endl；postorder(root)；cout0) while(p!=NULL) coutdatalchild； p=stop-； /退棧p=p-rchild； void inorderl(bitree*root) /中序遍歷bitree*p，*s100； int top=0； p=root； while(p!=NULL)Il(topO) while(p!=NULL) s+top=p；p=p-lchild； p=stop-； coutdatarchild； void postorderl( bitree *root) /后序遍歷(bitree *p *sl100； int s2100，top=0，b； p=root； do while(p!=NULL) s1top=p；s2top+=0； p=p-lchild；) if(top0) (b=s2-top； p=s1top； if(b=0) sltop=p；s2top+=l； p=p-rchild； elsecoutdata0)；/ /建立二叉鏈表參考前述程序/按照層次遍歷二叉鏈表#includetypedef char elemtype；struct bitree elemtype data； /結點信息bitree *lchild，*rchild； /左右孩子;/按層次遍歷二叉樹(建立二叉鏈表同前)void lorder(bitree *t) bitree q100，*p； /q代表隊列int f,r; /f，r類似于隊列頭、尾指針q1=t； f=r=l；cout”按層次遍歷二叉樹的結果為：”;while if=r) p=qf； f+； /出隊 coutdatalchild!=NULL) r+；qr=p-lchild； /入隊 if p-rchild!=NULLl r+； qr=p-rchild; /入隊 coutlchild); leftOright(root-rchild); bitree *t=root-lchild; root-lchild=root-rchild; root-rchild=t;/主函數 void main()bitree *root；root=create()； /建立二叉鏈表coutendlendl”左右子樹交換前的遍歷結果”endl；cout”先序遍歷的結果”endl； preorder(root)；coutendl； cout”中序遍歷的結果”endl；inorder(root)；coutendl：cout”后序遍歷的結果”endl；postorder(root)；coutendl；leftTOright(root)；coutendlendl”左右子樹交換后的遍歷結果”endl；cout”先序遍歷的結果”endl；preorder(root)；coutendl；cout”中序遍歷的結果”endl；inorder(root)；coutendl；cout”后序遍歷的結果”endl；postorder(root)；coutarcsvw.adj=l； return； void del_arc(graph *g，int v，int w) g-arcvw.adj=0； retum; /內容1參考程序 #define maxnode 40 #define null 0 #include typedef struct st_arc int adjvex； int weight； struct st_arc *nextrac；arcnode； typedef struct int vertex； struct st_arc *firstarc；vernode； typedef vernode adjlistmaxnode； void del_arc(vernode g，int v，int w) /刪除從頂點v到頂點w的邊 arcnode *rl,*r2； rl=gvfrrstarc；r2=rl；while(r1!=null&r1-adjvex!=w)r2=rl;rl=rl-nextarc；if (rl=null)printf(”no edge v-w”)；return；elseif(r1=r2) /當只有一個邊結點時gv.firstarc=r1-nextarc；else r2-nextarc=r1-nextarc； /有多個邊結點時rl=gw.firstarc；r2=rl；while(r1!=null&r1-adjvex!=v) /在以v為頭結點的鏈表中，刪除相應的 /邊結點r2=rl；rlrl-nextarc；if (rl=null)printf(”no edge v-w.”)；return；elseif(r1=r2)gw.firstarc=rl-nextarc；elser2-nextarc=r1-nextarc；void print(vernode g，int n) /打印圖中各結點的結構arcnode *q；int i；printf(”adjacency list of the graph：n”)；for(i=0；iadjvex)；printf(”%dt”，q-weight)；q=q-nextarc； printf(”n”)； main() int i，j，n，k，w，v； arcnode *p，*q； adjlist g； printf(”Input node： ”)； /輸入圖中頂點個數 scanf(”%d”，&n)； for(k=0；kadjvex=j； q-weight=w； q-nextarc=gi.firstarc； /頭指針指向新的邊結點 gi.firstarc=q； p=(arcnode*)malloc(sizeof(arcnode)； p-nextarc=gi.firstarc； gi.firstarc=q； p=(arcnode*)malloc(sizeof(arcnode)； p-adjvex=i； p-weight=w； p-nextarc=gj.firstarc； gj.firstarc=p； print(g，n)； printf(”Delete edge V-w：”)；scanf(”%d%d”，v，&w)；del_arc(g，v，w)；print(g，n)； 內容2的知識要點：構造有向圖鏈接表與無向圖鏈接表的算法區別是：無向圖兩結點無向對偶，因而鄰接表有一定的對偶性；有向圖兩結點間有向無對偶關系，因而建立鄰接表時應根據輸入的頂點及邊的有向關系建立(當箭頭方向離開結點為有關，當箭頭方向指向結點為無關)。/內容2的參考程序/有向圖鏈表的存儲結構為：typedef struct st_arc int aajvex； /存放依附于該邊的另一頂點在一維數組中的序號int weight； /存放和該邊有關的信息，如權值等struct st_arc *nextarc； /依附于該頂點的下一個邊結點的指針arcnode；typedef structint vertex； /存放與頂點有關的信息struct st_arc*firstarc；vernode； /存儲頂點信息typedef vernode adjlistmaxnode；/參考程序見內容1 內容3的知識要點：深度優先搜索遍歷圖的算法：首先訪問指定的起始頂點v0，從vo出發，訪問vo的一個未被訪問過的鄰接頂點w1，再