川师 数学院 数据结构试验报告.docx

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

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

3、过此步；2.录入程序代码并进行调试和算法分析；对实验内容(1)的操作步骤：1) 用类C语言描述算法过程；2) 用C语言环境实现该算法。对实验内容(2)的操作步骤：1) 完成算法的C实现；2) 分析其时间复杂度和空间复杂度。3.编写实验报告。实验结果：/ 动态分配数组空间#include stdio.h#include malloc.hint size,i;int *pArray;int *p;void malloc_size() pArray=(int *)malloc(size*(sizeof(int);int input_size() printf(please input the siz

4、e:n); printf(size= ); scanf(%d,&size); return 0;int input_data() printf(please input the value:n); for(i=0;isize;i+) printf(pArray%d= ,i); scanf(%d,&pArrayi); return *pArray;int Compare() int x,y,i; x=y=p0; for(i=0;i=pi) x=pi; if(y=pi) y=pi; printf(min= %dt max=%dn,x,y); return 0;int Output_data() p

5、=pArray; printf(before ofpaixu :n); for(i=0;isize;i+) printf(%dt,*pArray); pArray+; printf(n); return *pArray;void paixu() int x=0; int i,j; printf(later of paixu:n); for(i=0;isize;i+) for(j=i+1;j=pj) x=pi;pi=pj;pj=x; printf(%dt,pi); printf(n);void main() clrscr(); input_size(); malloc_size(); input

6、_data(); Output_data(); Compare(); paixu();实验结果：实验二 线性表及其基本操作实验(2学时)实验目的：(1) 熟练掌握线性表ADT和相关算法描述、基本程序实现结构；(2) 以线性表的基本操作为基础实现相应的程序；(3) 掌握线性表的顺序存储结构和动态存储结构之区分。实验内容：(类C算法的程序实现，任选其一。具体要求参见教学实验大纲)(1) 一元多项式运算的C语言程序实现(加法必做，其它选做)；(2) 有序表的合并；(3) 集合的并、交、补运算；实验准备：1) 计算机设备；2) 程序调试环境的准备，如TC环境；3) 实验内容的算法分析与代码设计与分析准

7、备。实验步骤：1.录入程序代码并进行调试和算法分析；2.编写实验报告。实验结果：/线性链表#include malloc.h#include stdio.h#define M 6typedef struct node int data; struct node *next;*Sqlist;void Initlialize(Sqlist &L) L=(Sqlist)malloc(sizeof(Sqlist); L-next =NULL;int Getlength(Sqlist L) int i=0; Sqlist p=L-next ; while(p!=NULL) i+; p=p-next; r

8、eturn i;int Getelem(Sqlist L,int i) int j=1,e; Sqlist p=L-next; while(jnext ; j+; e=p-data ; printf(第 %d 个元素是：%dn,i,e); return 1;int Locatelem(Sqlist L,int x) int i=0; Sqlist p=L-next ; while(p!=NULL&p-data !=x) p=p-next ; i+; if(p=NULL) return 0; else printf(%d 是第 %d 个元素n,x,i); return i; void Creat

9、listF(Sqlist &L,int a,int n)/头插法/从一个空表开始，读取字符数组a中字符生成新结点，将读取数据存放到新结点数据域，/再将新结点插入当前链表表头、直至结束 Sqlist s; int i; L=(Sqlist)malloc(sizeof(Sqlist); L-next =NULL; for(i=0;idata =ai; s-next =L-next ; L-next =s; void CreatlistR(Sqlist &L,int a,int n)/尾插法/将新结点插到当前链表表尾，为此必须新增一个尾指针r,使其始终指向当前链表的尾结点 Sqlist s,r; i

10、nt i; L=(Sqlist)malloc(sizeof(Sqlist); L-next =NULL; r=L; for(i=0;idata =ai; s-next=NULL; r-next =s ; r =s; int Inselem(Sqlist &L,int i,int x)/1、将所建新结点s的next域指向p的下一结点：s-next=p-next/2、将结点p的next域指向新结点s：p-next=s int j=1; Sqlist s,p=L-next ; s=(Sqlist)malloc(sizeof(Sqlist); s-data =x;s-next =NULL; if(iG

11、etlength(L) return 0; while(jnext ; j+; printf(在第 %d 个位置插入数据：%dn,i,x); s-next =p-next ; p-next =s; return 1;int Delelem(Sqlist &L,int i) int j=1; Sqlist p,q; p=L; if(iGetlength(L) return 0; while(jnext ; j+; q=p-next ; p-next =q-next ; free(q); return 1;void Displist(Sqlist L) Sqlist p=L-next ; whil

12、e(p!=NULL) printf(%dt,p-data); p=p-next ; printf(“n”);void input(int *pArray,int n) printf(请输入数组数据(共含 %d 个元):n,n); for(int i=0;i= S.stacksize) /* 栈满，追加存储空间*/ S.base = (ElemType *) realloc ( S.base,(S.stacksize + STACKINCREMENT) * sizeof(ElemType); if(!S.base) exit (OVERFLOW); /*存储空间失败*/ S.top = S.ba

13、se + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK; /*Push*/Status Pop (SqStack &S,ElemType &e) /*取栈顶元素，用e返回*/ /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if(S.top = S.base) return ERROR; e = * -S.top; return OK; /*Pop*/char In(char c,char OP) /*判断字符c是否属于运算符*/ if(c=35 & c；2表示 ; e

14、lse if(mab=2) return 47) a=atoi(&a); /*将字符数转化为整型数*/ if(b47) b=atoi(&b); switch(theta) case +: return a+b; break; case -: return a-b; break; case *: return a*b; break; case /: return a/b; break; return 1;OperandType EvaluateExpression() /*算术表达式求值的算符优先算法*/ SqStack OPTR,OPND; /* 设OPTR、OPND分别运算符栈和运算数栈*/

15、 OperandType a,b,c; OperatorType theta; InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c=getchar(); while (c!=# | GetTop(OPTR)!=#) if (!In(c,OP)Push(OPND,c);c=getchar(); else switch(Precede(GetTop(OPTR),c) case : Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; return GetTop(OPND);int main( ) printf(请输入运算表达式：以#为结束符)n); int a; a=(int)EvaluateExpression();/*执行函数EvaluateExpression()，将表达式的最终值强制转换为整型，并用a返回*/ printf(%d,a); getchar(); return 0; 测试结果为：表达式中包含+、-、*的情况；表达式中包含（）、+、-、*的情况；表达式中包含（）、+、-、*、/的情况；表达式中出现负数的情况；实验四 字符串实验(2学时)实验