《數(shù)據(jù)結(jié)構(gòu)》期中作業(yè)

1、北京郵電大學(xué)遠(yuǎn)程教育計算機科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書實驗一 線性表的插入和刪除一、 實驗?zāi)康?、 掌握用Turbo C上機調(diào)試線性表的基本方法；2、 掌握線性表的基本操作，插入、刪除、查找，以及線性表合并等運算在順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)上的運算。二、 實驗內(nèi)容線性表基本操作的實現(xiàn)當(dāng)我們要在線性表的順序存儲結(jié)構(gòu)上的第i個位置上插入一個元素時，必須先將線性表的第i個元素之后的所有元素依次后移一個位置，以便騰空一個位置，再把新元素插入到該位置。若要刪除第i個元素時，也必須把第i個元素之后的所有元素前移一個位置。程序?qū)崿F(xiàn)： typedef Null 0; typedef int datatyp

2、e; #define maxsize 1024; typedef struct datatype datamaxsize; int last; sequenlist; int insert(L, x, i) sequenlist *L; int i; int 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).d

3、ataj+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>(*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,

4、 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-1; printf(“n”); printout (L) sequenlist *L; int i; for(i=0; i<(*L).last; i+) printf(“data%d=”, i); printf(“%d”, (*L).datai); main( ) sequenlist *L; char cmd; int i, t; c

5、lscr( ); printf(“i, I.插入n”); printf(“d,D.刪除n”); printf(“q,Q退出n”); do do cmd =getchar( ); while(cmd!=d)(cmd!=D) (cmd!=q) (cmd!=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; whi

6、le (cmd!=q)&&( cmd!=Q); 實驗二 二叉樹的操作一、 實驗?zāi)康?、 進(jìn)一步掌握指針變量、動態(tài)變量的含義；2、 掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點及適用范圍；3、 掌握用指針類型描述、訪問和處理二叉樹的運算。二、 實驗內(nèi)容已知以二叉鏈表作存儲結(jié)構(gòu)，試編寫按層次順序遍歷二叉樹的算法。算法思想：本算法要采用一個隊列q，先將二叉樹根結(jié)點入隊列，然后退隊列，輸出該結(jié)點；若它有左子樹，便將左子樹根結(jié)點入隊列；若它有右子樹，便將右子樹根結(jié)點入隊列，直到隊列空為止。因為隊列的特點是先進(jìn)先出，從而達(dá)到按層次順序遍歷二叉樹的目的。程序?qū)崿F(xiàn)： #define M 100

7、 #define Null 0 typedef struct node int data; stuuct node *lchild, *rchild; bitree; bitree *queM; int 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

8、; if (t!=Null) inorder (tlchild); printf(“%4d”, tdata); inorder (trchild); void enqueue(t)bitree *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)

9、enqueue( t );while(front!=rear) p=delqueue( ); printf(“%4d”, pdata); if(plchild!=Null) enqueue(plchild); if(prchild!=Null) enqueue(prchild); main ( ) bitree *root; printf(“n”); root=creat ( ); inorder(root); printf(“n”); levorder(root);實驗三 圖的操作一、 實驗?zāi)康?、 掌握圖的基本存儲方法；2、 掌握有關(guān)圖的操作算法并用高級語言實現(xiàn)；3、 熟練掌握圖的兩種搜索

10、路徑的遍歷方法。二、 實驗內(nèi)容假設(shè)以一個帶權(quán)有向圖表示某一區(qū)域的公交線路網(wǎng)，圖中頂點代表一些區(qū)域中的重要場所，弧代表已有的公交線路，弧上的權(quán)表示該線路上的票價（或搭乘所需時間），試設(shè)計一個交通指南系統(tǒng)，指導(dǎo)前來咨詢者以最低的票價或最少的時間從區(qū)域中的某一場所到達(dá)另一場所。算法思想：下面是R、W、Floyd求每對頂點之間最短路徑算法的C語言程序，程序中矩陣A用來進(jìn)行n次迭代，矩陣P用來記錄路徑，Pij為迭代過程中當(dāng)前已經(jīng)求得的從頂點i到頂點j的最短路徑上最后被插入的那個頂點。算法實現(xiàn)：typedef struct node int no; float wgt; struct node *next

11、;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; j<n; j+) if(Aik +Akj<Aij) Pij=k; Aij=Aik+Akj;

12、實驗四 排序一、 實驗?zāi)康?、 掌握常用的排序方法，并掌握用高級語言實現(xiàn)排序算法的方法；2、 深刻理解排序的定義和各種排序方法的特點，并能加以靈活應(yīng)用；3、 了解各種方法的排序過程及其依據(jù)的原則，并掌握各種排序方法的時間復(fù)雜度的分析方法。二、 實驗內(nèi)容統(tǒng)計成績問題描述給出n個學(xué)生的考試成績表，每條信息由姓名和分?jǐn)?shù)組成，試設(shè)計一個算法：（1） 按分?jǐn)?shù)高低次序，打印出每個學(xué)生在考試中獲得的名次，分?jǐn)?shù)相同的為同一名次；（2） 按名次列出每個學(xué)生的姓名與分?jǐn)?shù)?；疽髮W(xué)生的考試成績表必須通過鍵盤輸入數(shù)據(jù)而建立，同時要對輸出進(jìn)行格式控制。算法實現(xiàn)下面給出的是用直接選擇排序算法實現(xiàn)的C語言程序。#defi

13、ne n 30typedef struct student char name8; int score; student Rn;main ( ) int num, i, j, max, temp; printf(“n請輸入學(xué)生成績: n”); for (i=0; i<n; i+) printf (“姓名:”);scanf (“%s”, &);scanf (“%4d”, &stui.score); num=1; for (i=0; i<n; i+) max=i; for (j=i+1; j<n; j+) if (Rj.score>Rmax

14、.score) max=j; if (max!=i) temp = Rmax; Rmax=Ri; Ri= temp; if (i>0)&&(Ri.score<Ri-1.score) num=num+1; printf(“%4d%s%4d”, num, R, Ri.score); 實驗五 查找一、實驗?zāi)康?、掌握查找的不同方法，并能用高級語言實現(xiàn)查找算法；2、熟練掌握二叉樹的構(gòu)造和查找方法。二、實驗內(nèi)容設(shè)計一個讀入一串整數(shù)構(gòu)成一棵二叉排序樹的算法。實現(xiàn)提示二叉排序樹的構(gòu)成，可從空的二叉樹開始，每輸入一個結(jié)點數(shù)據(jù)，就建立一個新結(jié)點插入到當(dāng)前已生成的二叉排序樹

15、中，所以它的主要操作是二叉排序樹插入運算。在二叉排序樹中插入新結(jié)點，只要保證插入后仍符合二叉排序樹的定義即可。算法實現(xiàn)typedef struct node int key; int other; struct node *lchild, *rchild; bstnode; void inorder ( t ) bstnode *t; if (t!=Null) inorder(tlchild); printf(“%4d”, tkey); inorder(trchild); bstnode *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;elsep=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”,&k