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

1、北京郵電大學(xué)遠(yuǎn)程教育計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)一 線性表的插入和刪除一、 實(shí)驗(yàn)?zāi)康?、 掌握用Turbo C上機(jī)調(diào)試線性表的基本方法；2、 掌握線性表的基本操作，插入、刪除、查找，以及線性表合并等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)上的運(yùn)算。二、 實(shí)驗(yàn)內(nèi)容線性表基本操作的實(shí)現(xiàn)當(dāng)我們要在線性表的順序存儲(chǔ)結(jié)構(gòu)上的第i個(gè)位置上插入一個(gè)元素時(shí)，必須先將線性表的第i個(gè)元素之后的所有元素依次后移一個(gè)位置，以便騰空一個(gè)位置，再把新元素插入到該位置。若要?jiǎng)h除第i個(gè)元素時(shí)，也必須把第i個(gè)元素之后的所有元素前移一個(gè)位置。程序?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(“請(qǐng)輸入n個(gè)數(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); 實(shí)驗(yàn)二 二叉樹的操作一、 實(shí)驗(yàn)?zāi)康?、 進(jìn)一步掌握指針變量、動(dòng)態(tài)變量的含義；2、 掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍；3、 掌握用指針類型描述、訪問(wèn)和處理二叉樹的運(yùn)算。二、 實(shí)驗(yàn)內(nèi)容已知以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，試編寫按層次順序遍歷二叉樹的算法。算法思想：本算法要采用一個(gè)隊(duì)列q，先將二叉樹根結(jié)點(diǎn)入隊(duì)列，然后退隊(duì)列，輸出該結(jié)點(diǎn)；若它有左子樹，便將左子樹根結(jié)點(diǎn)入隊(duì)列；若它有右子樹，便將右子樹根結(jié)點(diǎn)入隊(duì)列，直到隊(duì)列空為止。因?yàn)殛?duì)列的特點(diǎn)是先進(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);實(shí)驗(yàn)三 圖的操作一、 實(shí)驗(yàn)?zāi)康?、 掌握?qǐng)D的基本存儲(chǔ)方法；2、 掌握有關(guān)圖的操作算法并用高級(jí)語(yǔ)言實(shí)現(xiàn)；3、 熟練掌握?qǐng)D的兩種搜索

10、路徑的遍歷方法。二、 實(shí)驗(yàn)內(nèi)容假設(shè)以一個(gè)帶權(quán)有向圖表示某一區(qū)域的公交線路網(wǎng)，圖中頂點(diǎn)代表一些區(qū)域中的重要場(chǎng)所，弧代表已有的公交線路，弧上的權(quán)表示該線路上的票價(jià)（或搭乘所需時(shí)間），試設(shè)計(jì)一個(gè)交通指南系統(tǒng)，指導(dǎo)前來(lái)咨詢者以最低的票價(jià)或最少的時(shí)間從區(qū)域中的某一場(chǎng)所到達(dá)另一場(chǎng)所。算法思想：下面是R、W、Floyd求每對(duì)頂點(diǎn)之間最短路徑算法的C語(yǔ)言程序，程序中矩陣A用來(lái)進(jìn)行n次迭代，矩陣P用來(lái)記錄路徑，Pij為迭代過(guò)程中當(dāng)前已經(jīng)求得的從頂點(diǎn)i到頂點(diǎn)j的最短路徑上最后被插入的那個(gè)頂點(diǎn)。算法實(shí)現(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、實(shí)驗(yàn)四 排序一、 實(shí)驗(yàn)?zāi)康?、 掌握常用的排序方法，并掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法的方法；2、 深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用；3、 了解各種方法的排序過(guò)程及其依據(jù)的原則，并掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。二、 實(shí)驗(yàn)內(nèi)容統(tǒng)計(jì)成績(jī)問(wèn)題描述給出n個(gè)學(xué)生的考試成績(jī)表，每條信息由姓名和分?jǐn)?shù)組成，試設(shè)計(jì)一個(gè)算法：（1） 按分?jǐn)?shù)高低次序，打印出每個(gè)學(xué)生在考試中獲得的名次，分?jǐn)?shù)相同的為同一名次；（2） 按名次列出每個(gè)學(xué)生的姓名與分?jǐn)?shù)?；疽髮W(xué)生的考試成績(jī)表必須通過(guò)鍵盤輸入數(shù)據(jù)而建立，同時(shí)要對(duì)輸出進(jìn)行格式控制。算法實(shí)現(xiàn)下面給出的是用直接選擇排序算法實(shí)現(xiàn)的C語(yǔ)言程序。#defi

13、ne n 30typedef struct student char name8; int score; student Rn;main ( ) int num, i, j, max, temp; printf(“n請(qǐng)輸入學(xué)生成績(jī): 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); 實(shí)驗(yàn)五 查找一、實(shí)驗(yàn)?zāi)康?、掌握查找的不同方法，并能用高級(jí)語(yǔ)言實(shí)現(xiàn)查找算法；2、熟練掌握二叉樹的構(gòu)造和查找方法。二、實(shí)驗(yàn)內(nèi)容設(shè)計(jì)一個(gè)讀入一串整數(shù)構(gòu)成一棵二叉排序樹的算法。實(shí)現(xiàn)提示二叉排序樹的構(gòu)成，可從空的二叉樹開(kāi)始，每輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù)，就建立一個(gè)新結(jié)點(diǎn)插入到當(dāng)前已生成的二叉排序樹

15、中，所以它的主要操作是二叉排序樹插入運(yùn)算。在二叉排序樹中插入新結(jié)點(diǎn)，只要保證插入后仍符合二叉排序樹的定義即可。算法實(shí)現(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