數(shù)據(jù)結構實驗指導書(共16頁)

1、精選優(yōu)質文檔-傾情為你奉上數(shù)據(jù)結構與算法課程簡介：本課程總學時需要64學時,其中實驗課10學時,共有5個實驗,每個實驗為2學時,從其中的7個實驗選其中的5個。本課程的先行課為C+程序設計實驗一 線性表及其應用一、實驗目的 1、掌握用上機調試線性表的基本方法； 2、掌握線性表的基本操作，插入、刪除、查找，以及線性表合并等運算在順序存儲結構和鏈接存儲結構上的運算。 二、實驗環(huán)境 硬件：PC 微型計算機、256M以上內存，40G以上硬盤。 軟件：Windows XP，VC或VS.Net三、實驗內容 線性表基本操作的實現(xiàn) 當我們要在線性表的順序存儲結構上的第i個位置上插入一個元素時，必須先將線性表的第

2、i個元素之后的所有元素依次后移一個位置，以便騰空一個位置，再把新元素插入到該位置。若要刪除第i個元素時，也必須把第i個元素之后的所有元素前移一個位置。 四、實驗步驟 1、 本實驗的程序清單如下。 下面只是根據(jù)實驗指導書上的程序，各位同學要按照實際上機調試后的結果程序附上： typedef Null 0; typedef int datatype; #define maxsize 1024; typedef struct datatype datamaxsize; int last; sequenlist; int insert(L, x, i) sequenlist *L; int i; in

3、t j; if (*L).last= =maxsize-1) printf(“overflow”); return Null; else if (i<1)(i>(*L).last+1) printf(“error”); return Null; else for(j=(*L).last; j>=i-1; j-) (*L).dataj+1=(*L).dataj; (*L).datai-1=x; (*L).last=(*L).last+1; return(1); int delete(L,i) sequenlist *L; int i; int j; if (i<1)(i&

4、gt;(*L).last+1) printf (“error”); return Null; else for(j=i, j<=(*L).last; j+) (*L).dataj-1=(*L).dataj; (*L).data - -; return(1); void creatlist( ) sequenlist *L; int n, i, j; printf(“請輸入n個數(shù)據(jù)n”); scanf(“%d”,&n); for(i=0; i<n; i+) printf(“data%d=”, i); scanf (“%d”, (*L).datai); (*L).last=n-

5、1; printf(“n”); printout (L) sequenlist *L; int i; for(i=0; i<(*L).last; i+) printf(“data%d=”, i); printf(“%d”, (*L).datai); void main( ) sequenlist *L; char cmd; int i, t; clscr( ); printf(“i, I.插入n”); printf(“d,D.刪除n”); printf(“q,Q退出n”); do do cmd =getchar( ); while(cmd!=d)(cmd!=D) (cmd!=q) (cm

6、d!=Q) (cmd!=i) (cmd!=I); switch (cmd) case i,I; scanf(&x); scanf(&i); insert(L, x, i); printout(L); break; case d,D; scanf(&i); delete(L, i); printout(L); break; while (cmd!=q)&&( cmd!=Q); 2、 本程序運行的結果如下： 根據(jù)各位同學的實際調試數(shù)據(jù)編寫。 3、 結合以上程序如何進行分析和改進。并把分析和改進的內容附上。 五、實驗小結 實驗過程中的體會和收獲。 六、實驗思考

7、題與練習 線性表的非順序存儲結構如何實現(xiàn)？鏈表是如何操作的？模仿線性表的順序存儲結構的實驗編寫線性表的非順序存儲結構的實驗報告并進行相應的實驗。 實驗二 棧的基本操作 一、 實驗目的 1掌握棧的基本操作：2初始化棧、判棧為空、出棧、入棧等運算。 二、實驗要求 1 認真閱讀和掌握本實驗的算法。 2 上機將本算法實現(xiàn)。 3 保存和打印出程序的運行結果，并結合程序進行分析。 三、實驗內容 利用棧的基本操作實現(xiàn)將任意一個十進制整數(shù)轉化為R進制整數(shù)算法為： 1、定義棧的順序存取結構 2、分別定義棧的基本操作（初始化棧、判棧為空、出棧、入棧等） 3、定義一個函數(shù)用來實現(xiàn)上面問題： 十進制整數(shù)X和R作為形參

8、 初始化棧 只要不為重復做下列動作 將入棧 X=X/R 只要棧不為空重復做下列動作 棧頂出棧 輸出棧頂元素 四、實驗思考題與練習 1、如何實現(xiàn)隊列的操作 2、利用棧實現(xiàn)數(shù)學表達式的轉換 3、迷宮問題 選擇一個以上題目進行實驗，并編寫實驗報告 實驗三、隊列應用迷宮問題 一、 實驗內容 n*m迷宮是一個矩形區(qū)域，（1，1）為入口（n，m）為出口，0表示該方格可通過，1表示該方格有阻礙不能通過，每次只能從一個無障礙方格向其周圍8各方向的鄰接任一無障礙方格移動一步，問，當迷宮有解時如何尋找一條由入口到出口的路徑并返回這個序列，或者不能連通時給出無解標志。迷宮如下表所示。 一個帶邊界哨的10×

9、15迷宮 1 1 1 1 1 1 1 11111111 1 1 1 0 0 0 1 0 0 01000100 1 1 1 0 1 0 0 0 1 01000111 1 1 1 0 1 1 1 1 1 01101110 1 1 1 1 1 0 0 0 1 10111010 1 1 1 1 0 0 1 0 1 11101010 1 1 1 1 0 1 0 0 1 01010101 0 1 1 1 0 1 1 1 1 10011111 0 1 1 1 1 1 0 1 1 11010101 0 1 1 1 0 1 0 1 0 11101000 1 1 1 0 1 0 1 0 1 00011001 0

10、1 1 1 1 1 1 1 1 11111111 1 1 二、 實驗要求 提出思想 給出算法 程序設計 給定一個迷宮表，列出運行結果 三、 實驗目的 通過實驗，同學掌握隊列數(shù)據(jù)結構在算法中的深入應用方法，這是寬度優(yōu)先的搜索過程中使用隊列結構的典型應用 實驗四 二叉樹的操作 一、實驗目的 1、進一步掌握指針變量、動態(tài)變量的含義； 2、掌握二叉樹的結構特征，以及各種存儲結構的特點及適用范圍； 3、掌握用指針類型描述、訪問和處理二叉樹的運算。 二、 實驗要求 1 認真閱讀和掌握本實驗的程序。 2 上機運行本程序。 3 保存和打印出程序的運行結果，并結合程序進行分析。 4 按照你二叉樹的操作需要，重新

11、改寫主程序并運行，打印出文件清單和運行結果 三、實驗內容 已知以二叉鏈表作存儲結構，試編寫按層次順序遍歷二叉樹的算法。 算法思想：本算法要采用一個隊列q，先將二叉樹根結點入隊列，然后退隊列，輸出該結點；若它有左子樹，便將左子樹根結點入隊列；若它有右子樹，便將右子樹根結點入隊列，直到隊列空為止。因為隊列的特點是先進先出，從而達到按層次順序遍歷二叉樹的目的。 程序實現(xiàn)： #define M 100 #define Null 0 typedef struct node int data; stuuct node *lchild, *rchild; bitree; bitree *queM; int

12、front=0, rear=0; bitree *creat( ) bitree *t; int x; scanf (“%d”, &x); if (x= =0) t=Null; else t=malloc(sizeof(bitree); tdata=x; tlchild=creat( ); trchild=creat( ); return t; void inorder( t ) bitree *t; if (t!=Null) inorder (tlchild); printf(“%4d”, tdata); inorder (trchild); void enqueue(t) bitr

13、ee *t; if(front!=(rear+1) % M) rear = (rear+1) % M; querear=t; bitree *delqueue( ) if (front= =rear) return Null; front=(front+1) % M; return (quefront); void levorder ( t ) bitree *t; bitree *p; if(t!=Null) enqueue( t ); while(front!=rear) p=delqueue( ); printf(“%4d”, pdata); if(plchild!=Null) enqu

14、eue(plchild); if(prchild!=Null) enqueue(prchild); main ( ) bitree *root; printf(“n”); root=creat ( ); inorder(root); printf(“n”); levorder(root); 四、實驗思考題與練習 1、二叉樹順序表示和相應的操作？ 2、二叉樹的遞歸算法？ 3、二叉樹的應用舉例？ 選擇一個以上題目進行實驗，并編寫實驗報告 實驗五 圖的及其應用 一、實驗目的 1、掌握圖的基本存儲方法； 2、掌握有關圖的操作算法并用高級語言實現(xiàn)； 3、熟練掌握圖的兩種搜索路徑的遍歷方法。 二、實驗要求

15、 1認真閱讀和掌握本實驗的算法。 2上機將本算法實現(xiàn)。 3保存和打印出程序的運行結果，并結合程序進行分析。 三、實驗內容 假設以一個帶權有向圖表示某一區(qū)域的公交線路網(wǎng)，圖中頂點代表一些區(qū)域中的重要場所，弧代表已有的公交線路，弧上的權表示該線路上的票價（或搭乘所需時間），試設計一個交通指南系統(tǒng)，指導前來咨詢者以最低的票價或最少的時間從區(qū)域中的某一場所到達另一場所。 算法思想：下面是R、W、Floyd求每對頂點之間最短路徑算法的C語言程序，程序中矩陣A用來進行n次迭代，矩陣P用來記錄路徑，Pij為迭代過程中當前已經(jīng)求得的從頂點i到頂點j的最短路徑上最后被插入的那個頂點。 算法實現(xiàn)： typedef

16、 struct node int no; float wgt; struct node *next; edgenode; typedef struct char vtx; edgenode *link; vexnode; typedef vexnode Graphn; void Floyd(Graph G, float Ann, int pnn) int i, j, k; for (i=0; i<n; i+) for(j=0;j<n;j+) Aij=Gij; Pij=-1; for (k=0; k<n; k+) for (i=0; i<n; i+) for (j=0;

17、j<n; j+) if(Aik +Akj<Aij) Pij=k; Aij=Aik+Akj; 四、實驗思考題與練習 1、用矩陣表示圖的方法及其相應的操作？ 2、用鏈接表表示圖的方法及其相應的操作？ 3、圖的應用舉例？ 選擇一個以上題目結合具體的應用實際進行實驗，并編寫實驗報告 實驗六 查找一、實驗目的 1、掌握查找的不同方法，并能用高級語言實現(xiàn)查找算法； 2、熟練掌握二叉樹的構造和查找方法。 二、實驗要求 1認真閱讀和掌握本實驗的算法。 2上機將本算法實現(xiàn)。 3保存和打印出程序的運行結果，并結合程序進行分析。 三、實驗內容 設計一個讀入一串整數(shù)構成一棵二叉排序樹的算法。 實現(xiàn)提示二叉

18、排序樹的構成，可從空的二叉樹開始，每輸入一個結點數(shù)據(jù)，就建立一個新結點插入到當前已生成的二叉排序樹中，所以它的主要操作是二叉排序樹插入運算。在二叉排序樹中插入新結點，只要保證插入后仍符合二叉排序樹的定義即可。 算法實現(xiàn) typedef struct node int key; int other; struct node *lchild, *rchild; bstnode; void inorder ( t ) bstnode *t; if (t!=Null) inorder(tlchild); 專心-專注-專業(yè)printf(“%4d”, tkey); inorder(trchild); bs

19、tnode *insertbst(t, s) bstnode *s, *t; bstnode *f, *p; p=t; while(p!=Null) f=p; if (skey= =pkey) return t; if (skey<pkey) p=plchild; else p=prchild; if(t= =Null) return s; if (skey<fkey) flchild=s; else frchild=s; return t; bstnode *creatord( ) bstnode *t, * s; int key; t=Null; scanf(“%d”,&

20、;key); while (key!=0) s=malloc(sizeof (bitree); skey=key; slchild=Null; srchild=Null; scanf(“%d”, &data); sother=data; t=insertbst(t, s); scanf(“%d”,&key); return t; main ( ) bstnode *root ; root= creatord( ); inorder (root); 五、實驗思考題1、順序查找方法的上機驗證？ 2、二分查找法的上機驗證？ 3、索引結構和散列結構的查找方法？ 選擇一個以上題目結合具體的應用實際進行實驗，并編寫實驗報告實驗七 排序一、實驗目的 1、掌握常用的排序方法，并掌握用高級語言實現(xiàn)排序算法的方法； 2、深刻理解排序的定義和各種排序方法的特點，并能加以靈活應用； 3、了解各種方法的排序過程及其依據(jù)的原則，并掌握各種排序方法的時間復雜性和穩(wěn)定性的分析方法。 二、實驗要求 1認真閱讀和掌握本實驗的算法。 2上機將本算法實現(xiàn)。 3保存和打印出程序的運行結果，并結合程序進行分析。 三、實驗內容 統(tǒng)計成績 問題描述給出n個學生的考試成績表，每條信息由