1、數據結構課程設計任務書學期：11-12-2班級：網絡10一、設計目的數據結構是一門實踐性較強的專業基礎課程，為了學好這門課程，必須在掌握理論 知識的同時，加強上機實踐。本課程設計的目的就是要達到理論與實際應用相結合，使同學 們能夠根據數據對象的特性，學會數據組織的方法，能把現實世界中的實際問題在計算機內 部表示出來，并培養基本的、良好的程序設計技能。二、設計要求1、通過這次設計，要求在數據結構的邏輯特性和物理表示、數據結構的選擇應用、算 法的設計及其實現等方面加深對課程基本內容的理解。同時，在程序設計方法以及上機操作 等基本技能和科學作風方面受到比較系統和嚴格的訓練。2、學生必須仔細研讀數據結

2、構課程設計（實習）要求，以學生自學為主、指導教師 指導為輔，認真、獨立地完成課程設計的任務，有問題及時主動與指導教師溝通。3、本次課程設計按照教學要求需要在一周半時間內獨立完成，學生要發揮自主學習的 能力，充分利用時間，安排好課設的時間計劃，并在課設過程中不斷檢測自己的計劃完成情 況，及時地向指導教師匯報。4、編程語言任選。三、設計選題題一：線索二叉樹（*）任務：建立中序線索二叉樹，并且中序遍歷；求中序線索二叉樹上已知結點中序的前驅和后繼；需求分析和概要設計：建立中序線索二叉樹，并且中序遍歷。首先就是要建立樹，再將樹中序線索化。求中序線索 二叉樹上已知結點中序的前驅和后繼時，即是將樹在遍歷一遍

3、。也可以在遍歷的過程中，將 樹的結點放在數組中，當然必須講述先遍歷一遍，這是用空間來換時間。詳細設計：樹的結構體的聲明：typedef char TElemtype;typedef enum PointerTagLink,Thread;/設置標志：Link 為指針，Thread 為線索typedef struct BiThrNode/樹結點結構體TElemtype data;struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;相關函數的聲明：voidInitBiTree(BiThrTree &T)

4、;/初始化樹voidCreatBiTree(BiThrTree &T);/建立二叉樹voidInOrderThreading(BiThrTree&Thrt,BiThrTree &T);/中序線索二叉樹/線索化/中序遍歷求已知結點中序的前驅和后繼void InThreading(BiThrTree p);int InOrderTraverse_Thr(BiThrTree T);void InOrderThread_BeAf();初始化樹：void InitBiTree(BiThrTree &T)T = new BiThrNode;if(!T) exit(1);T = NULL;建立二叉樹：voi

5、d CreatBiTree(BiThrTree &T)char ch;cinch;if(ch =智)T = NULL;elseT = new BiThrNode;if(!T) exit(1);T-data = ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild);中序線索二叉樹：void InOrderThreading(BiThrTree &Thrt,BiThrTree &T) Thrt = new BiThrNode;/設置頭結點if(!Thrt) exit(1); Thrt-LTag = Link;/頭結點左邊標志為指針Thrt-RTag =Thr

6、ead;/右邊的為線索Thrt-rchild = Thrt;/有孩子指向頭結點本身if(!T) Thrt-lchild = Thrt; /若樹根結點為空，則頭結點左孩子指向頭結點else/若根結點不為空Thrt-lchild = T;/頭結點左孩子指向根結點pre = Thrt;/設置指針pre指向頭結點InThreading(T);/線索化樹 Tpre-rchild = Thrt; pre-RTag = Thread; Thrt-rchild = pre;線索化樹：void InThreading(BiThrTree p)if(p)InThreading(p-lchild);/線索化左子樹i

7、f(!p-lchild) p-LTag = Thread; p-lchild = pre;if(!pre-rchild)pre-RTag = Thread; pre-rchild = p;pre = p;InThreading(p-rchild);中序遍歷：int InOrderTraverse_Thr(BiThrTree T)BiThrTree p;int i=1;p = T-lchild;while(p!=T)while(p-LTag!=Thread)p = p-lchild;coutdatadata;i+；length+;while(p-RTag=Thread&p-rchild!=T)p

8、 = p-rchild;coutdatadata;/將結點存于數組中i+;length+;p = p-rchild;return OK;測試結果和設計心得體會：建立二叉闋二叉樹律斯艮為當輸入時表不結點為空:中序遍歷為：425163?植輸入結點的信息言的甚驅為4Z的啟繼為S是否繼續查找Jress key to continue通過對樹的中序線索化使我更加清楚樹的有關操作算法,題二：最小生成樹問題（*）【問題描述】若要在n個城市之間建設通信網絡，只需要假設n-1條線路即可。如何以最低的經濟代價建 設這個通信網，是一個網的最小生成樹問題。【系統要求】利用克魯斯卡爾算法求網的最小生成樹。利用普里姆算法

9、求網的最小生成樹。要求輸出各條邊及它們的權值。【測試數據】由學生任意指定，但報告上要求寫出多批數據測試結果。【實現提示】通信線路一旦建成，必然是雙向的。因此，構造最小生成樹的網一定是無向網。設圖的頂點 數不超過30個，并為簡單起見，網中邊的權值設成小于100的整數，可利用C語言提供的 隨機函數產生。圖的存儲結構的選取應和所作操作相適應。為了便于選擇權值最小的邊，此題的存儲結構既 不選用鄰接矩陣的數組表示法，也不選用鄰接表，而是以存儲邊（帶權）的數組表示圖。【選作內容】利用堆排序實現選擇權值最小的邊。需求分析和概要設計：用克魯斯卡爾和普里姆算法生成圖的最小生成樹。首先要構造出圖，然后將圖生成樹，

10、故要 使用鄰接矩陣儲存圖。詳細設計：有關結構體的聲明：char VertexType;int VRType;char InfoType;struct ArcCell(typedeftypedeftypedeftypedefVRType adj;/VRType是頂點的關系類型。無權圖用1或0表示相連否。對帶權圖，則為權值類型。InfoType *info;/表示相關信息的指針ArcCell,AdjMatrixMAX_VEXTEX_NUMMAX_VEXTEX_NUM;typedef struct（/頂點向量/鄰接矩陣圖的當前頂點數和弧度數VertexType vexsMAX_VEXTEX_NUM;

11、AdjMatrix arcs;vexnum,arcnum;int MGraph;typedef struct(VertexType adjvex;VRType lowcost;closedge;typedef struct(VertexType begin;VertexType end;VRType weight;EdgeType;相關函數的聲明：int CreateGraph(MGraph &G);/創造圖后要返回其值int LocateVex(MGraph G,VertexType u);/求點 u 在圖中的位置int minmum( closedge closedgeMAX_VEXTEX

12、_NUM);/求最小值函數void MinSpanTree_PRIM(MGraph G,VertexType u); /PRIM 最小生成樹void MinSpanTree_KRUSKAL(MGraph G);創造圖：int CreateGraph(MGraph &G)int i,j,k,w;VertexType v1,v2;cout請輸入頂點數和邊數G.vexnumG.arcnum;high=G.arcnum;cout請輸入頂點信息endl;for(i=0;iG.vexsi;for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)G.arcsij.adj =INF

13、INITY;G.=NULL;/ KRUSKAL最小生成樹初始化鄰接矩陣/最大值8cout請輸入每條邊對應的兩個頂點(v1,v2)及其權值(w)endl;for(k=0;kv1v2w;i=LocateVex(G,v1);j=LocateVex(G,v2);edgesk+1.begin=v1;edgesk+1.end=v2;G.arcsij.adj=w;G.arcsji.adj=w;edgesk+1.weight=w;return OK;PRIM最小生成樹：void MinSpanTree_PRIM(MGraph G,VertexType u)int k,j,i;closed

14、ge closedgeMAX_VEXTEX_NUM;cinu;k=LocateVex(G,u);for(j=0;jG.vexnum;+j)closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0;for(i=1;iG.vexnum;+i)k=minmum(closedge);cout 邊 ： (closedgek.adjvex,G.vexsk) 權 值 closedgek.lowcostendl;closedgek.lowcost=0;for(j=1;jG.vexnum;+j)if(G.arcskj.adjclo

15、sedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj;KRUSKAL最小生成樹：void MinSpanTree_KRUSKAL(MGraph G)HeapSort();for(int k=1;k=G.arcnum;k+)coutedgesk.weight ;coutendl;int fatherMAX_VEXTEX_NUM;int i,j,vf1,vf2;for(i=0;iG.vexnum;i+)fatheri=-1;i=0;j=0;while(iG.arcnum&jG.vexnum-1)vf1=Find

16、(father,edgesi+1.begin);vf2=Find(father,edgesi+1.end);if(vf1!=vf2)fathervf2=vf1;j+;cout邊：(edgesi+1.begin,edgesi+1.end)權值:edgesi+1.weight ) ) XI c F D B c F E F r lc,f,c,b,a2LD,B,c,ls s.h _l.:h _l.:h _l.:h _l.:h -I.1271 * 工* 通過對圖的操作更加明白圖與樹之間的關系。從而更加熟練的操作圖與樹。附錄：1.線索二叉樹代碼：#include iostreamusing namespa

17、ce std;3.#define OK 1#define ERROR 06.typedef char TElemtype;typedef enum PointerTagLink,Thread;typedef struct BiThrNodeTElemtype data;struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;14.15.TElemtype e;BiThrTree pre,Thrt;char a100;int length=0;20./初始化樹/建立二叉樹/建立中序線索二叉/線索化/中序

18、遍歷/求已知結點中序的void InitBiTree(BiThrTree &T);void CreatBiTree(BiThrTree &T);void InOrderThreading(BiThrTree &Thrt,BiThrTree &T); 樹void InThreading(BiThrTree p);int InOrderTraverse_Thr(BiThrTree T);void InOrderThread_BeAf();前驅和后繼27.void InitBiTree(BiThrTree &T) TOC o 1-5 h z T = new BiThrNode;if(!T) exit

19、(1);T = NULL;void CreatBiTree(BiThrTree &T)char ch;cinch;if(ch = ) T = NULL;elseT = new BiThrNode;if(!T) exit(1);T-data = ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild); TOC o 1-5 h z void InOrderThreading(BiThrTree &Thrt,BiThrTree &T)Thrt = new BiThrNode;if(!Thrt) exit(1);Thrt-LTag = Link;Thrt-RTag

20、 =Thread;Thrt-rchild = Thrt;if(!T) Thrt-lchild = Thrt;elseThrt-lchild = T;pre = Thrt;InThreading(T);pre-rchild = Thrt;pre-RTag = Thread;Thrt-rchild = pre; TOC o 1-5 h z void InThreading(BiThrTree p)68.if(p)InThreading(p-lchild);if(!p-lchild)p-LTag = Thread;p-lchild = pre;if(!pre-rchild)pre-RTag = Th

21、read;pre-rchild = p;81.82.83.pre = p;InThreading(p-rchild); TOC o 1-5 h z int InOrderTraverse_Thr(BiThrTree T)BiThrTree p;int i=1;p = T-lchild;while(p!=T)while(p-LTag!=Thread)p = p-lchild;coutdatadata; TOC o 1-5 h z i+;length+;while(p-RTag=Thread&p-rchild!=T)p = p-rchild;coutdatadata;i+;length+;108.

22、109.return OK;void InOrderThread_BeAf()22.123.124.char YES;TElemtype data;bool flag=false;cout請輸入結點的信息data;for(int i=1;i=length;i+)if(data=ai)flag = true; if(i=1)coutdata的前驅為NILrchild;else125.coutdata的前驅為ai-1endl;if(i=length)coutdata的后繼為NILendl;elsecoutdata的后繼為ai

23、+1endl;if(!flag)cout沒有該節點endl;cout是否繼續查找(Y/N)YES;if(YES=Y|YES=y)InOrderThread_BeAf();void main()BiThrTree T;InitBiTree(T);cout建立二叉樹endl;cout二叉樹的根為(當輸入時表示結點為空)：endl;CreatBiTree(T);InOrderThreading(Thrt,T);cout中序遍歷為：endl;InOrderTraverse_Thr(Thrt);coutendl;InOrderThread_BeAf();3.最小生成樹代碼：#include iostre

24、amusing namespace std;#define OK 1#define ERROR 0#define MAX_VEXTEX_NUM 30/最多結點數#defineMAX_ARC_NUM 1000#defineINFINITY INT_MAX/最大值8typedefchar VertexType;typedefint VRType;typedefchar InfoType;typedefstruct ArcCell(VRType adj;/VRType是頂點的關系類型。無權圖用1或0表示相連否。對帶權圖，則為權值類型。InfoType *info;/表示相關信息的指針14.15.16

25、.5.36.37.ArcCell,AdjMatrixMAX_VEXTEX_NUMMAX_VEXTEX_NUM; typedef struct( VertexType vexsMAX_VEXTEX_NUM; AdjMatrix arcs;intvexnum,arcnum;MGraph;typedef struct( VertexType adjvex; VRType lowcost; closedge;typedef struct( VertexType begin; VertexTyp

26、e end; VRType weight; EdgeType; MGraph G;/頂點向量/鄰接矩陣圖的當前頂點數和弧度數high;CreateGraph(MGraph &G);LocateVex(MGraph G,VertexType u);minmum( closedge closedgeMAX_VEXTEX_NUM);/創造圖后要返回其值EdgeType edgesMAX_ARC_NUM; int int int int void MinSpanTree_PRIM(MGraph G,VertexType u); void MinSpanTree_KRUSKAL(MGraph G);in

27、t CreateGraph(MGraph &G)int i,j,k,w;VertexType v1,v2;cout請輸入頂點數和邊數G.vexnumG.arcnum;high=G.arcnum;cout請輸入頂點信息endl;for(i=0;iG.vexsi;for(i=0;iG.vexnum;+i)/初始化鄰接矩陣 TOC o 1-5 h z for(j=0;jG.vexnum;+j)G.arcsij.adj =INFINITY;G.=NULL;cout請輸入每條邊對應的兩個頂點(v1,v2)及其權值(w)endl;for(k=0;kv1v2w;i=LocateVex(

28、G,v1);j=LocateVex(G,v2);edgesk+1.begin=v1;edgesk+1.end=v2;G.arcsij.adj=w;G.arcsji.adj=w;edgesk+1.weight=w; TOC o 1-5 h z return OK;int LocateVex(MGraph G,VertexType u)int i;for(i=0;iG.vexnum;i+)if(u=G.vexsi)return i;return OK;int minmum(closedge closedgeMAX_VEXTEX_NUM)int j,k;int mincost;mincost=INF

29、INITY;for(j=0;jG.vexnum;+j) TOC o 1-5 h z if(closedgej.lowcost!=0&closedgej.lowcostu;k=LocateVex(G,u);for(j=0;jG.vexnum;+j)008.109.110.closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0;for(i=1;iG.vexnum;+i)k=minmum(closedge);cout邊：(closedgek.adjvex,G.vexsk

30、)權 值: closedgek.lowcostendl;closedgek.lowcost=0;for(j=1;jG.vexnum;+j)if(G.arcskj.adjclosedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj;44./權值堆排序

31、void HeapAdjust(int s,int high) edges0.weight=edgess.weight;edges0.begin=edgess.begin;edges0.end=edgess.end;for(int j=2*s;j=high;j*=2)if(jhigh&edgesj.weight=edgesj.weight) break;edgess.weight=edgesj.weight;edgess.begin=edgesj.begin;edgess.end=edgesj.end;s=j;edgess.weight=edges0.weight;edgess.begin=edges0.begin;edgess.end=edges0.end;void HeapSort() for(int i=high/2;i0;-i) Heap