川師數(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告資料

1、四川師范大學(xué)數(shù)學(xué)與軟件科學(xué)學(xué)院實(shí)驗(yàn)報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu)（_C語(yǔ)言版）_指導(dǎo)老師：馮山實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)名稱學(xué)時(shí)成績(jī)實(shí)驗(yàn)一ADT勺類C描述向C程序的轉(zhuǎn)換實(shí)驗(yàn)2學(xué)時(shí)實(shí)驗(yàn)二線性表及其基本操作實(shí)驗(yàn)2學(xué)時(shí)實(shí)驗(yàn)三棧和隊(duì)列實(shí)驗(yàn)6學(xué)時(shí)實(shí)驗(yàn)四字符串實(shí)驗(yàn)2學(xué)時(shí)實(shí)驗(yàn)五稀疏矩陣的三元組實(shí)現(xiàn)實(shí)驗(yàn)4學(xué)時(shí)實(shí)驗(yàn)六二叉樹(shù)的基本算法實(shí)驗(yàn)4學(xué)時(shí)實(shí)驗(yàn)七Huffman樹(shù)與Huffman樹(shù)編碼算法實(shí)驗(yàn)4學(xué)時(shí)實(shí)驗(yàn)八圖的建立與遍歷算法實(shí)驗(yàn)4學(xué)時(shí)實(shí)驗(yàn)九內(nèi)部排序算法實(shí)驗(yàn)4學(xué)時(shí)實(shí)驗(yàn)十查找實(shí)驗(yàn)2學(xué)時(shí)班 級(jí)：2009級(jí)6班學(xué) 號(hào)：30姓 名：總成績(jī)：_實(shí)驗(yàn)一：ADT的類C描述向C程序的轉(zhuǎn)換實(shí)驗(yàn)(2學(xué)時(shí))實(shí)驗(yàn)?zāi)康模?1)復(fù)習(xí)C語(yǔ)言的基本用法；(2)學(xué)會(huì)用類

2、C的語(yǔ)言對(duì)算法進(jìn)行描述的方法，將類C算法轉(zhuǎn)換成0源程序的方法和過(guò)程;(3)抽象數(shù)據(jù)類型的定義和表示、實(shí)現(xiàn)；(4)加深對(duì)數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之間關(guān)系的理解；(5)初步建立起時(shí)間復(fù)雜度和空間復(fù)雜度的概念。實(shí)驗(yàn)內(nèi)容：(類C算法的程序?qū)崿F(xiàn))(1)輸入一組數(shù)據(jù)存入數(shù)組中，并將數(shù)據(jù)元素的個(gè)數(shù)動(dòng)態(tài)地由輸入函數(shù)完成。求輸入數(shù)據(jù)的最大值、最小值，并通過(guò)函數(shù)參數(shù)返回所求結(jié)果；實(shí)驗(yàn)準(zhǔn)備：1)計(jì)算機(jī)設(shè)備；2)程序調(diào)試環(huán)境的準(zhǔn)備， 如TC環(huán)境；3)實(shí)驗(yàn)內(nèi)容的算法分析與代碼 設(shè)計(jì)與分析準(zhǔn)備。實(shí)驗(yàn)步驟：1.安裝TC并設(shè)置好環(huán)境，如果已安裝好，可以跳過(guò)此步；2.錄入程序代碼并進(jìn)行調(diào)試和算法分析;對(duì)實(shí)驗(yàn)內(nèi)容（1）的操作步驟

3、：1）用類C語(yǔ)言描述算法過(guò)程；2）用C語(yǔ)言環(huán)境實(shí)現(xiàn)該算法。對(duì)實(shí)驗(yàn)內(nèi)容（2）的操作步驟：1）完成算法的C實(shí)現(xiàn)；2）分析其時(shí)間復(fù)雜度和空間復(fù)雜 度。3.編寫實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)結(jié)果：入程序代碼并進(jìn)行調(diào)試和算法分析；2.編寫實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)結(jié)果：入程序代碼并進(jìn)行調(diào)試和算法分析；2.編寫實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)結(jié)果：（1）/*隊(duì)列存儲(chǔ)*/#i nclude typedef int status;#defi ne QueueSize 10typedef struct sqqueuechar dataQueueSize;int fron t,rear;SqQueue;void In itQueue(SqQueue &

4、;qu)=0;status En Queue(SqQueue &qu,char x)if( +1)%QueueSize=return 0;=+1)%QueueSize;=x；return 1;status DeQueue(SqQueue &qu,char &x)if=)return 0;=+1)%QueueSize;x=；return 1;status GetHead(SqQueue qu,char &x)if =return 0;x=+1)%QueueSize;return 1;status QueueEmpty(SqQueue qu)if=return 1;

5、elsereturn 0;void mai n()SqQueue qu;char e;In itQueue(qu);printf(Queue %sn,(QueueEmpty(qu)=1Empty:Not Empty);prin tf(i nser an); En Queue(qu,a);printf(inser bn); EnQueue(qu,b);prin tf(i nser cn); En Queue(qu,c);prin tf(i nser dn); En Queue(qu,d);printf(Queue %sn,(QueueEmpty(qu)=1Empty:Not Empty);Get

6、Head(qu,e);prin tf(Queue of top elem is: %cn,e);prin tf(show of Queue: n);while(!QueueEmpty(qu)DeQueue(qu,e);prin tf(%ct,e);prin tf(n);實(shí)驗(yàn)結(jié)果：(2)/*用棧實(shí)現(xiàn)對(duì)表達(dá)式的求值運(yùn)算*/#i nclude #i nclude #include /*數(shù)據(jù)類型轉(zhuǎn)換庫(kù)函數(shù)*/#defi ne TRUE 1#defi ne FALSE 0#defi ne OK 1#define ERROR 0#define INFEASIBLE -1#defi ne OVERFLOW

7、-2#define STACK_INIT_SIZE 100 /*初始分配量*/#define STACKINCREMENT 10 /*存儲(chǔ)空間的分配增量*/ typedef int Status;typedef char ElemType;typedef ElemType Opera ndType; /*操作數(shù)*/typedef char OperatorType;typedef structElemType *base;ElemType *top;int stacksize;SqStack;Status InitStack(SqStack &S)/*構(gòu)造一個(gè)空棧S */=(ElemT

8、ype *)malloc(STACK_INIT_SIZE * sizeof(ElemType);if(! exit (OVERFLOW); /*存儲(chǔ)空間失敗*/一J=STACK_INIT_SIZE;return OK; /* Ini tStack*/Status GetTop(SqStack S)/*若棧不空，則用e返回S的棧頂元素*/ElemType e;if = return ERROR;e = *;return e; /*GetTop*/Status Push (SqStack &S,ElemType e) /*插入元素e為新的棧頂元素*/if - =/*棧滿，追加存儲(chǔ)空間*/=

9、(ElemType *) realloc ( , + STACKINCREMENT) * sizeof(ElemType);if(! exit (OVERFLOW); /*存儲(chǔ)空間失敗*/=+ ;+= STACKINCREMENT;*+ = e;return OK; /*Push*/Status Pop (SqStack &S,ElemType &e) /*取棧頂元素，用e返回*/*若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK否則返回ERROR */if = return ERROR;e = * ;return OK; /*Pop*/char ln(char c,ch

10、ar OP) /*判斷字符c是否屬于運(yùn)算符*/if(c=35 & c2表示;else if(mab=2) return 47) a=atoi(&a); /*將字符數(shù)轉(zhuǎn)化為整型數(shù)*/if(b47) b=atoi(&b);switch(theta)case +: retur n a+b;break;case -: retur n a-b;break;case *: retur n a*b;break;case /: retur n a/b;break;return 1;Opera ndType EvaluateExpressio n() /*算術(shù)表達(dá)式求值的算符優(yōu)先算法*/

11、SqStack OPTR,OPND; /*設(shè)OPTR OPN分別運(yùn)算符棧和運(yùn)算數(shù)棧*/Opera ndType a,b,c; OperatorType theta;In itStack(OPTR); Push(OPTR,#);In itStack(OPND); c=getchar();while (c!=# | GetTop(OPTR)!=#)if (!I n( c,OP)Push(OPND,c);c=getchar();elseswitch(Precede(GetTop(OPTR),c)case : Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a);Push

12、(OPND,Operate(a,theta,b);break;return GetTop(OPND);int mai n()printf(請(qǐng)輸入運(yùn)算表達(dá)式：以#為結(jié)束符)n);int a;a=(i nt)EvaluateExpressio n();/*執(zhí)行函數(shù)EvaluateExpression()，將表達(dá)式的最終值強(qiáng)制轉(zhuǎn)換為整型，并用回*/prin tf(%d,a);getchar();return 0;測(cè)試結(jié)果為：1表達(dá)式中包含+、-、*的情況；2表達(dá)式中包含（）、+、-、*的情況；3表達(dá)式中包含（）、+、-、*、/的情況；4表達(dá)式中出現(xiàn)負(fù)數(shù)的情況；實(shí)驗(yàn)四字符串實(shí)驗(yàn)（2學(xué)時(shí)）實(shí)驗(yàn)?zāi)康模赫莆?/p>

13、有關(guān)字符串的基本操作和存儲(chǔ)結(jié)構(gòu)，并編寫相應(yīng)的基本操作算法實(shí)驗(yàn)內(nèi)容：（類C算法的程序?qū)崿F(xiàn)，任選其二）（1）求字符串的長(zhǎng)度算法（必做）；（2）求字符串的子串算法（選做）；（3）字符串的合并算法（選做）；（4）字符串的置換算法（選做）；（5）字符串的插入算法（選做）。實(shí)驗(yàn)準(zhǔn)備:1）計(jì)算機(jī)設(shè)備；2）程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3）實(shí)驗(yàn)內(nèi)容的算法分析與代碼 設(shè)計(jì)與分析準(zhǔn)備。實(shí)驗(yàn)步驟：1.錄入程序代碼并進(jìn)行調(diào)試和算法分析；2.編寫實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)結(jié)果：#i nclude #i nclude typedef int Status;typedef struct nodechar ch 5;入程序代碼并進(jìn)行調(diào)

14、試和算法分析；2.編寫實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)結(jié)果：#i nclude #defi ne Maxsize 100#defi ne M 6#defi ne N 6typedef structint r; =i;.c=j；.d=Aij;+；k+; k+;ifk.r=rs & k.c=cs)k.d=x; =i.r;i+1.c=i.c;i+1.d=i.d;k.r=rs;k.c=cs;k.d=x;+；return 1;k+;while(kk.c) k+;ifk.r=rs& k.c=cs)x=k.d;prin tf(第%d行第%d列的元素為：x=%dn,rs,cs,x);return x;else

15、return 0;,i.c,i.d);return 1;=v)q.r=p.c;q.c=p.r;q.d=p.d;q+；=j.r)ifi.c j.c)k.r=j.r;k.c=j.c;k.d=j.d;k+;j+;elsee=i.d+j.d; if(e!=O)k.r=i.r;k.c=i.c;k.d=e; k+;i+;j+;else ifk.r Ts2.weight)j=s1;s仁s2;s2=j;void Huffma nCodi ng(Huffma nTree & HT,Huffma nCode & HC,i nt *w,i nt n)aren t=(*p ).l child=(*p)

16、.rchild=O;for(;i=m;i+,p+)(*p).pare nt=0;for(i=n+1;i=m;i+)Select(HT,i-1,s1,s2);are nt=HTs2.pare nt=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(Huffma nCode)malloc( n+1)*sizeof(char*); cd=(char*)malloc( n*sizeof(char);cdn-1=0;for(i=1;i=n ;i+)start=n-1;for(c=i,f=HTi.pare nt;f!=

17、0;c=f,f=HTf.pare nt)if(HTf.lchild=c)cd-start=O;elsecd-start=1;HCi=(char*)malloc( n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int mai n()Huffma nTree HT;Huffma nCode HC;int n = 0,i;入程序代碼并進(jìn)行調(diào)試和算法分析;2.編寫實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)結(jié)果：n,；for(i=0;i;i+) n,;for(i=0;ivexs0;pgraph-arcs00 = 1;/*表示頂點(diǎn)v0在集合U中*/for(i = 1;

18、 i n; i+)/*初始化集合V-U中頂點(diǎn)的距離值*/disti .len gth=pgraph-arcs0i;disti.vertex=pgraph-vexsi;if (disti.length != MAX)disti.prevex=O;else disti.prevex= -1;void dijkstra(GraphMatrix graph, Path dist)int i,j,m inv ex;AdjType mi n;init(&graph,dist); /*初始化，此時(shí)集合U中只有頂點(diǎn)vO*/for(i = 1; i ; i+)min=MAX; minv ex=0;for

19、 (j = 1; j ; j+) /*在V-U中選出距離值最小頂點(diǎn)*/if( jj = 0 & distj.le ngth min )mi n=distj.le ngth; min vex=j;/*從v0沒(méi)有路徑可以通往集合V-U中的頂點(diǎn)*/if(minvex = 0) break;minvexminvex = 1;/*集合V-U中路徑最小的頂點(diǎn)為for (j = 1; j distmi nvex.le ngth + mi nv exj)distj.le ngth = distmi nv ex.le ngth + mi nv exj;distj.prevex = min vex;Gra

20、phMatrix graph;void in itgraph()int i,j;min vex */=6；for (i = 0; i ; i+)for (j = 0; j ; j+)ij = (i = j 0 : MAX);01 = 50;02 = 10;12 = 15;1 4 = 5;2 0 = 20;2 3 = 15;3 1 = 20;3 4 = 35;4 3 = 30;3 = 3;04 = 45;int mai n()int i;in itgraph();dijkstra(graph, dist);prin tf(最短路徑為：n);for (i = 0; i ; i+)printf(%.

21、Of %d)t, disti.length,disti.prevex);prin tf(n);return 0;實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)九內(nèi)部排序算法實(shí)驗(yàn)(4學(xué)時(shí))實(shí)驗(yàn)?zāi)康模?1)熟練掌握各種排序的算法思想和方法；(2)掌握快速排序、堆排序、歸并排序等的實(shí)現(xiàn)方法;(3)對(duì)已知數(shù)據(jù)和排序方法要求可給出其排序過(guò)程;（4）熟悉各種排序算法的復(fù)雜度分析。實(shí)驗(yàn)內(nèi)容：（類C算法的程序?qū)崿F(xiàn)，任選其二）（1）選擇排序（簡(jiǎn)單選擇排序、堆排序）（必做）；（2）歸并排序（選做）。實(shí)驗(yàn)準(zhǔn)備：1）計(jì)算機(jī)設(shè)備；2）程序調(diào)試環(huán)境的準(zhǔn)備，如TC環(huán)境；3）實(shí)驗(yàn)內(nèi)容的算法分析與代碼 設(shè)計(jì)與分析準(zhǔn)備。實(shí)驗(yàn)步驟：1.錄入程序代碼并進(jìn)行調(diào)試和算

22、法分析（應(yīng)強(qiáng)調(diào)排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度 分析）；2.編寫實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)結(jié)果：/*直接選擇排序算法*/#defi ne MAXITEM 100typedef int KeyType;typedef char ElemType5;typedef struct recKeyType key; /*關(guān)鍵字域*/ElemType data; /*數(shù)據(jù)域*/ ele mn odeMAXITEM;void selectsort(ele mnode r,i nt n)int i,j,k;for (i=1;i=n-1;i+)k=i;for (j=i+1;j=n ;j+)if (rj.keyrk.key)

23、 k=j; /*用k指出每趟在無(wú)序區(qū)段的最小元素*/r0=ri; /*將rk與ri交換*/ri=rk;rk=r0;printf（成績(jī)從低到高排列如下:n）;for (i=1;i=n ;i+)prin tf(%6d,ri.key);prin tf(n);for (i=1;i=n ;i+)prin tf(%6s,ri.data);prin tf(n);void mai n()printf(按直接排序結(jié)果為：n);elemnode s=0, ,75,王華,87,李英,68,張萍,92,陳濤,88,劉麗,61,章強(qiáng),77,孫軍,96,朱斌,80,許偉,72,曾亞;/*s0元素不計(jì)入元素個(gè)數(shù)*/int

24、n=10;selectsort(s, n);實(shí)驗(yàn)結(jié)果:/*二路歸并排序算法的源程序*/#in clude#defi ne MAXNUM 50#defi ne TRUE 1#defi ne FALSE 0typedef int KeyType;typedef int DataType;typedef structKeyType key;/*排序碼字段*/*DataType info;記錄的其它字段*/ RecordNode;typedef structint n;/* n為文件中的記錄個(gè)數(shù)，nM AXNUM */RecordNode recordMAXNUM; SortObject;void m

25、erge(RecordNode r, RecordNode r1, int low, int m, int high)/* rlow到rm和rm+1到rright是兩個(gè)有序段*/int i = low, j = m + 1, k = low;while ( i = m & j = high ) /*反復(fù)復(fù)制兩個(gè)段的第一個(gè)記錄中較小的*/if (ri.key = rj.key)r1k+ = ri+;else r1k+ = rj+;while (i = m) r1k+ = ri+; /*復(fù)制第一個(gè)段的剩余記錄*/while (j = high) r1k+ = rj+;/*復(fù)制第二個(gè)段的剩余

26、記錄*/*對(duì)r做一趟歸并，結(jié)果放到r1中*/void mergePass(RecordNode r, RecordNode r1, int n, int len gth)int i = 0, j;/* len gth為本趟歸并的有序子段的長(zhǎng)度*/while(i + 2*le ngth - 1 n) merge(r, r1, i, i+length-1, i + 2*length - 1);/*歸并長(zhǎng)length的兩個(gè)子段*/i += 2*le ngth;if(i + len gth - 1 n - 1)/*剩下兩段，后一段長(zhǎng)度小于len gth */merge(r, r1, i, i+le n

27、gth-1, n-1);else/*將剩下的一段復(fù)制到數(shù)組r1 */for(j = i; j n; j+) r1j = rj;void MergeSort(SortObject * pvector)RecordNode recordMAXNUM;int len gth = 1;while (le ngth n)/*一趟歸并，結(jié)果存放在數(shù)組record中*/mergePass(pvector-record, record, pvector- n, len gth);len gth *= 2;/*一趟歸并，結(jié)果存回*/mergePass(record, pvector-record, pvector- n, len gth);len gth *= 2;SortObject vector = 8, 49,38,65,97,76,13,27,49;輸入你想要查找的數(shù)據(jù)：);scan f(%d,&data);for(int i=0;iLength;i+)if(fpi=data)prin tf(數(shù)據(jù)%d是第%d個(gè)數(shù)據(jù)n,data,i+1);return ;printf(”未能查找到數(shù)據(jù)%d