川师数学院数据结构试验报告资料

1、四川师范大学数学与软件科学学院实验报告课程名称：数据结构（_C语言版）_指导老师：冯山实验项目实验名称学时成绩实验一ADT勺类C描述向C程序的转换实验2学时实验二线性表及其基本操作实验2学时实验三栈和队列实验6学时实验四字符串实验2学时实验五稀疏矩阵的三元组实现实验4学时实验六二叉树的基本算法实验4学时实验七Huffman树与Huffman树编码算法实验4学时实验八图的建立与遍历算法实验4学时实验九内部排序算法实验4学时实验十查找实验2学时班 级：2009级6班学 号：30姓 名：总成绩：_实验一：ADT的类C描述向C程序的转换实验(2学时)实验目的：(1)复习C语言的基本用法；(2)学会用类

2、C的语言对算法进行描述的方法，将类C算法转换成0源程序的方法和过程;(3)抽象数据类型的定义和表示、实现；(4)加深对数据的逻辑结构和物理结构之间关系的理解；(5)初步建立起时间复杂度和空间复杂度的概念。实验内容：(类C算法的程序实现)(1)输入一组数据存入数组中，并将数据元素的个数动态地由输入函数完成。求输入数据的最大值、最小值，并通过函数参数返回所求结果；实验准备：1)计算机设备；2)程序调试环境的准备， 如TC环境；3)实验内容的算法分析与代码 设计与分析准备。实验步骤：1.安装TC并设置好环境，如果已安装好，可以跳过此步；2.录入程序代码并进行调试和算法分析;对实验内容（1）的操作步骤

3、：1）用类C语言描述算法过程；2）用C语言环境实现该算法。对实验内容（2）的操作步骤：1）完成算法的C实现；2）分析其时间复杂度和空间复杂 度。3.编写实验报告。实验结果：入程序代码并进行调试和算法分析；2.编写实验报告。实验结果：入程序代码并进行调试和算法分析；2.编写实验报告。实验结果：（1）/*队列存储*/#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);实验结果：(2)/*用栈实现对表达式的求值运算*/#i nclude #i nclude #include /*数据类型转换库函数*/#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 /*存储空间的分配增量*/ typedef int Status;typedef char ElemType;typedef ElemType Opera ndType; /*操作数*/typedef char OperatorType;typedef structElemType *base;ElemType *top;int stacksize;SqStack;Status InitStack(SqStack &S)/*构造一个空栈S */=(ElemT

8、ype *)malloc(STACK_INIT_SIZE * sizeof(ElemType);if(! exit (OVERFLOW); /*存储空间失败*/一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 - =/*栈满，追加存储空间*/=

9、(ElemType *) realloc ( , + STACKINCREMENT) * sizeof(ElemType);if(! exit (OVERFLOW); /*存储空间失败*/=+ ;+= 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是否属于运算符*/if(c=35 & c2表示;else if(mab=2) return 47) a=atoi(&a); /*将字符数转化为整型数*/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() /*算术表达式求值的算符优先算法*/

11、SqStack OPTR,OPND; /*设OPTR OPN分别运算符栈和运算数栈*/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(请输入运算表达式：以#为结束符)n);int a;a=(i nt)EvaluateExpressio n();/*执行函数EvaluateExpression()，将表达式的最终值强制转换为整型，并用回*/prin tf(%d,a);getchar();return 0;测试结果为：1表达式中包含+、-、*的情况；2表达式中包含（）、+、-、*的情况；3表达式中包含（）、+、-、*、/的情况；4表达式中出现负数的情况；实验四字符串实验（2学时）实验目的：掌握

13、有关字符串的基本操作和存储结构，并编写相应的基本操作算法实验内容：（类C算法的程序实现，任选其二）（1）求字符串的长度算法（必做）；（2）求字符串的子串算法（选做）；（3）字符串的合并算法（选做）；（4）字符串的置换算法（选做）；（5）字符串的插入算法（选做）。实验准备:1）计算机设备；2）程序调试环境的准备，如TC环境；3）实验内容的算法分析与代码 设计与分析准备。实验步骤：1.录入程序代码并进行调试和算法分析；2.编写实验报告。实验结果：#i nclude #i nclude typedef int Status;typedef struct nodechar ch 5;入程序代码并进行调

14、试和算法分析；2.编写实验报告。实验结果：#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;入程序代码并进行调试和算法分析;2.编写实验报告。实验结果：n,；for(i=0;i;i+) n,;for(i=0;ivexs0;pgraph-arcs00 = 1;/*表示顶点v0在集合U中*/for(i = 1;

18、 i n; i+)/*初始化集合V-U中顶点的距离值*/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); /*初始化，此时集合U中只有顶点vO*/for(i = 1; i ; i+)min=MAX; minv ex=0;for

19、 (j = 1; j ; j+) /*在V-U中选出距离值最小顶点*/if( jj = 0 & distj.le ngth min )mi n=distj.le ngth; min vex=j;/*从v0没有路径可以通往集合V-U中的顶点*/if(minvex = 0) break;minvexminvex = 1;/*集合V-U中路径最小的顶点为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;实验结果：实验九内部排序算法实验(4学时)实验目的：(1)熟练掌握各种排序的算法思想和方法；(2)掌握快速排序、堆排序、归并排序等的实现方法;(3)对已知数据和排序方法要求可给出其排序过程;（4）熟悉各种排序算法的复杂度分析。实验内容：（类C算法的程序实现，任选其二）（1）选择排序（简单选择排序、堆排序）（必做）；（2）归并排序（选做）。实验准备：1）计算机设备；2）程序调试环境的准备，如TC环境；3）实验内容的算法分析与代码 设计与分析准备。实验步骤：1.录入程序代码并进行调试和算

22、法分析（应强调排序算法的时间复杂度和空间复杂度 分析）；2.编写实验报告。实验结果：/*直接选择排序算法*/#defi ne MAXITEM 100typedef int KeyType;typedef char ElemType5;typedef struct recKeyType key; /*关键字域*/ElemType data; /*数据域*/ 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指出每趟在无序区段的最小元素*/r0=ri; /*将rk与ri交换*/ri=rk;rk=r0;printf（成绩从低到高排列如下: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(按直接排序结果为：n);elemnode s=0, ,75,王华,87,李英,68,张萍,92,陈涛,88,刘丽,61,章强,77,孙军,96,朱斌,80,许伟,72,曾亚;/*s0元素不计入元素个数*/int

24、n=10;selectsort(s, n);实验结果:/*二路归并排序算法的源程序*/#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为文件中的记录个数，nM AXNUM */RecordNode recordMAXNUM; SortObject;void m

25、erge(RecordNode r, RecordNode r1, int low, int m, int high)/* rlow到rm和rm+1到rright是两个有序段*/int i = low, j = m + 1, k = low;while ( i = m & j = high ) /*反复复制两个段的第一个记录中较小的*/if (ri.key = rj.key)r1k+ = ri+;else r1k+ = rj+;while (i = m) r1k+ = ri+; /*复制第一个段的剩余记录*/while (j = high) r1k+ = rj+;/*复制第二个段的剩余

26、记录*/*对r做一趟归并，结果放到r1中*/void mergePass(RecordNode r, RecordNode r1, int n, int len gth)int i = 0, j;/* len gth为本趟归并的有序子段的长度*/while(i + 2*le ngth - 1 n) merge(r, r1, i, i+length-1, i + 2*length - 1);/*归并长length的两个子段*/i += 2*le ngth;if(i + len gth - 1 n - 1)/*剩下两段，后一段长度小于len gth */merge(r, r1, i, i+le n

27、gth-1, n-1);else/*将剩下的一段复制到数组r1 */for(j = i; j n; j+) r1j = rj;void MergeSort(SortObject * pvector)RecordNode recordMAXNUM;int len gth = 1;while (le ngth n)/*一趟归并，结果存放在数组record中*/mergePass(pvector-record, record, pvector- n, len gth);len gth *= 2;/*一趟归并，结果存回*/mergePass(record, pvector-record, pvector- n, len gth);len gth *= 2;SortObject vector = 8, 49,38,65,97,76,13,27,49;输入你想要查找的数据：);scan f(%d,&data);for(int i=0;iLength;i+)if(fpi=data)prin tf(数据%d是第%d个数据n,data,i+1);return ;printf(”未能查找到数据%d