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

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