《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書(shū)2011.doc

數(shù) 據(jù) 結(jié) 構(gòu) 實(shí) 驗(yàn) 指 導(dǎo) 書(shū)南京工程學(xué)院信息管理與信息系統(tǒng)教研室2011年3月實(shí)驗(yàn)一 線性表操作一、實(shí)驗(yàn)?zāi)康?.熟悉C語(yǔ)言的上機(jī)環(huán)境，進(jìn)一步掌握C語(yǔ)言的結(jié)構(gòu)特點(diǎn)。2.掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的定義及C語(yǔ)言實(shí)現(xiàn)。3.掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表的定義及C語(yǔ)言實(shí)現(xiàn)。4.掌握線性表在順序存儲(chǔ)結(jié)構(gòu)即順序表中的各種基本操作。5.掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表中的各種基本操作。二、實(shí)驗(yàn)內(nèi)容 1.順序線性表的建立、插入及刪除。 2.鏈?zhǔn)骄€性表的建立、插入及刪除。三、實(shí)驗(yàn)步驟1.建立含n個(gè)數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長(zhǎng)度。2.利用前面的實(shí)驗(yàn)先建立一個(gè)順序表L=21，23，14，5，56，17，31，然后在第i個(gè)位置插入元素68。3.建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的值域?yàn)檎蛿?shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來(lái)建立相應(yīng)單鏈表。四、實(shí)現(xiàn)提示1.由于C語(yǔ)言的數(shù)組類(lèi)型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。在此，我們利用C語(yǔ)言的結(jié)構(gòu)體類(lèi)型定義順序表：#define MAXSIZE 1024typedef int elemtype; /* 線性表中存放整型元素 */typedef struct elemtype vecMAXSIZE; int len; /* 順序表的長(zhǎng)度 */sequenlist;將此結(jié)構(gòu)定義放在一個(gè)頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書(shū)寫(xiě)，另外在該頭文件里給出順序表的建立及常量的定義。2. 注意如何取到第i個(gè)元素，在插入過(guò)程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。3.單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個(gè)指針域。用C語(yǔ)言描述結(jié)點(diǎn)結(jié)構(gòu)如下： typedef int elemtype;typedef struct node elemtype data; /數(shù)據(jù)域 struct node *next; /指針域 linklist; 注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個(gè)結(jié)點(diǎn)的地址：p=(linklist *)malloc(sizeof(linklist);該語(yǔ)句的功能是申請(qǐng)分配一個(gè)類(lèi)型為linklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p為空值（NULL）。五、思考與提高1. 如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2. 在main函數(shù)里如果去掉L=&a語(yǔ)句，會(huì)出現(xiàn)什么結(jié)果？實(shí)驗(yàn)二 棧和隊(duì)列的應(yīng)用一、實(shí)驗(yàn)?zāi)康?. 掌握棧的順序表示和實(shí)現(xiàn)2. 掌握隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容1. 編寫(xiě)一個(gè)程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算。2. 實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。三、實(shí)驗(yàn)步驟1. 初始化順序棧2. 插入元素3. 刪除棧頂元素4. 取棧頂元素5. 遍歷順序棧6. 置空順序棧7. 初始化并建立鏈隊(duì)列8. 入鏈隊(duì)列9. 出鏈隊(duì)列10. 遍歷鏈隊(duì)列四、實(shí)現(xiàn)提示1. /*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/typedef struct ElemType stackMAXNUM; int top;SqStack; /*初始化順序棧函數(shù)*/void InitStack(SqStack *p) q=(SqStack*)malloc(sizeof(SqStack) /*申請(qǐng)空間*/)/*入棧函數(shù)*/void Push(SqStack *p,ElemType x) if(p-toptop=p-top+1; /*棧頂+1*/ p-stackp-top=x; /*數(shù)據(jù)入棧*/*出棧函數(shù)*/ElemType Pop(SqStack *p)x=p-stackp-top; /*將棧頂元素賦給x*/p-top=p-top-1; /*棧頂-1*/*獲取棧頂元素函數(shù)*/ElemType GetTop(SqStack *p) x=p-stackp-top;/*遍歷順序棧函數(shù)*/void OutStack(SqStack *p) for(i=p-top;i=0;i-)printf(第%d個(gè)數(shù)據(jù)元素是：%6dn,i,p-stacki);/*置空順序棧函數(shù)*/void setEmpty(SqStack *p) p-top= -1;2. /*定義鏈隊(duì)列*/typedef struct Qnode ElemType data; struct Qnode *next;Qnodetype;typedef struct Qnodetype *front; Qnodetype *rear;Lqueue; /*初始化并建立鏈隊(duì)列函數(shù)*/void creat(Lqueue *q) h=(Qnodetype*)malloc(sizeof(Qnodetype); /*初始化申請(qǐng)空間*/ h-next=NULL; q-front=h; q-rear=h;for(i=1;idata=x; s-next=NULL; q-rear-next=s; q-rear=s;/*出鏈隊(duì)列函數(shù)*/ElemType Ldelete(Lqueue *q) p=q-front-next; q-front-next=p-next; if(p-next=NULL) q-rear=q-front; x=p-data; free(p); /*釋放空間*/*遍歷鏈隊(duì)列函數(shù)*/void display(Lqueue *q) while(p!=NULL) /*利用條件判斷是否到隊(duì)尾*/ printf(%d-,p-data); p=p-next; 五、思考與提高1. 讀棧頂元素的算法與退棧頂元素的算法有何區(qū)別？2. 如果一個(gè)程序中要用到兩個(gè)棧，為了不發(fā)生上溢錯(cuò)誤，就必須給每個(gè)棧預(yù)先分配一個(gè)足夠大的存儲(chǔ)空間。若每個(gè)棧都預(yù)分配過(guò)大的存儲(chǔ)空間，勢(shì)必會(huì)造成系統(tǒng)空間緊張。如何解決這個(gè)問(wèn)題？（1）鏈棧只有一個(gè)top指針，對(duì)于鏈隊(duì)列，為什么要設(shè)計(jì)一個(gè)頭指針和一個(gè)尾指針？（2）一個(gè)程序中如果要用到兩個(gè)棧時(shí)，可通過(guò)兩個(gè)棧共享一維數(shù)組來(lái)實(shí)現(xiàn)。即雙向棧共享鄰接空間。如果一個(gè)程序中要用到兩個(gè)隊(duì)列，能否實(shí)現(xiàn)？如何實(shí)現(xiàn)？實(shí)驗(yàn)三 樹(shù)操作一、實(shí)驗(yàn)?zāi)康?. 通過(guò)實(shí)驗(yàn)，掌握二叉樹(shù)的建立與存儲(chǔ)2. 通過(guò)實(shí)驗(yàn)，掌握二叉樹(shù)的遍歷方法二、實(shí)驗(yàn)內(nèi)容1. 練習(xí)二叉樹(shù)的建立與存儲(chǔ)2. 練習(xí)二叉樹(shù)的遍歷三、實(shí)驗(yàn)步驟1. 建立自己的頭文件BT.H，內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹(shù)的建立、二叉樹(shù)的先序、中序與后序遍歷算法。2. 建立二叉樹(shù),并通過(guò)調(diào)用函數(shù), 輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。四、實(shí)現(xiàn)提示建立二叉樹(shù)的代碼如下：BTCHINALR * createbt( ) BTCHINALR *q; struct node1 *s30; int j,i,x; printf(建立二叉樹(shù)，輸入結(jié)點(diǎn)對(duì)應(yīng)的編號(hào)和值,編號(hào)和值之間用逗號(hào)隔開(kāi)nn); printf(i,x = ); scanf(%d,%c,&i,&x); while(i != 0 & x != $) q = (BTCHINALR*)malloc(sizeof(BTCHINALR); /*建立一個(gè)新結(jié)點(diǎn)q*/ q-data = x; q-lchild = NULL; q-rchild = NULL; si = q;/*q新結(jié)點(diǎn)地址存入s指針數(shù)組中*/ if(i != 1)/*i = 1，對(duì)應(yīng)的結(jié)點(diǎn)是根結(jié)點(diǎn)*/ j = i / 2; /*求雙親結(jié)點(diǎn)的編號(hào)j*/ if(i % 2 = 0) sj-lchild = q; /*q結(jié)點(diǎn)編號(hào)為偶數(shù)則掛在雙親結(jié)點(diǎn)j的左邊*/ else sj-rchild = q; /*q結(jié)點(diǎn)編號(hào)為奇數(shù)則掛在雙親結(jié)點(diǎn)j的右邊*/ printf(i,x = ); scanf(%d,%c,&i,&x); return s1; /*返回根結(jié)點(diǎn)地址*/五、思考與提高1. 如何用孩子兄弟表示法存儲(chǔ)樹(shù)？2. 熟悉并掌握赫夫曼樹(shù)。實(shí)驗(yàn)四 查找和排序操作（1）一、實(shí)驗(yàn)?zāi)康?. 掌握查找的不同方法，并能用高級(jí)語(yǔ)言實(shí)現(xiàn)查找算法； 2. 熟練掌握二叉排序樹(shù)的構(gòu)造和查找方法。3. 了解靜態(tài)查找表及哈希表查找方法。二、實(shí)驗(yàn)內(nèi)容設(shè)計(jì)一個(gè)算法讀入一串整數(shù)，然后構(gòu)造二叉排序樹(shù)，進(jìn)行查找。三、實(shí)驗(yàn)步驟1. 從空的二叉樹(shù)開(kāi)始，每輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù)，就建立一個(gè)新結(jié)點(diǎn)插入到當(dāng)前已生成的二叉排序樹(shù)中。2. 在二叉排序樹(shù)中查找某一結(jié)點(diǎn)。3.用其它查找算法進(jìn)行排序（課后自己做）。四、實(shí)現(xiàn)提示1. 定義結(jié)構(gòu)typedef struct node int key; int other; struct node *lchild, *rchild; bstnode; void inorder ( 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 (skeypkey) p=plchild; else p=prchild; if(t= =Null) return s; if (skeyfkey) flchild=s; else frchild=s; return t; bstnode *creatord( ) bstnode *t, * s; int key; t=Null; scanf(“%d”,&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; 五、思考與提高1. 用其它的查找方法完成該算法。2. 比較各種算法的時(shí)間及空間復(fù)雜度。實(shí)驗(yàn)四 查找和排序操作（2）一、實(shí)驗(yàn)?zāi)康?. 掌握常用的排序方法，并掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法的方法； 2. 深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用；3. 了解各種方法的排序過(guò)程及其時(shí)間復(fù)雜度的分析方法。二、實(shí)驗(yàn)內(nèi)容統(tǒng)計(jì)成績(jī) 給出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ù)。三、實(shí)驗(yàn)步驟1. 定義結(jié)構(gòu)體。2. 定義結(jié)構(gòu)體數(shù)組。3. 定出主程序，對(duì)數(shù)據(jù)進(jìn)行排序。四、實(shí)現(xiàn)提示#define n 30 typedef 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; in; i+) printf (“姓名:”); scanf (“%s”, &); scanf (“%4d”, &stui.score); num=1; for (i=0; in; i+)