[报告]数据结构实验报告

1、 数据结构 课程实验项目目录学生姓名： 学号： 序号实验项目编号实验项目名称*实验项目类型成绩指导教师1 三元组抽象数据类型的表示与实现综合性2 复数四则运算设计性3 顺序表的操作综合性4 学生课程理系统设计性5 栈及队列的操作综合性6 停车场管理设计性7 二叉树的建立与操作综合性8 哈夫曼码编码器设计性9 求最短路径综合性10 0校园导游咨询设计性11 1顺序、折半查找综合性12 2电话号码的查询设计性13 3统计成绩综合性14151617*实验项目类型：演示性、验证性、综合性、设计性实验。*此表由学生按顺序填写。 本科实验报告专用纸课程名称 数据结构 成绩评定 实验项目名称 三元组抽象数据

2、类型的表示与实现 指导教师 实验项目编号 & 实验项目类型 综合性 学生姓名 学号 实验地点 南海楼 学院 系 专业 实验时间 2009 年 09月16日 上午09月16日上午 温度 湿度 （一） 实验目的和要求1. 熟悉抽象数据类型和实现方式；2. 熟悉抽象数据类型的表示和实现方法，利用高级程序语言中已存在的数据类型说明新的结构；（二） 实验主要内容实验内容：1 定义三元组抽象数据类型Triplet，说明三元组存储结构以及基本操作原型；实现对三元组的构造、读取、求最大、最小值等基本操作。2 定义复数抽象数据类型Complex，说明其基本操作原型；实现下类基本运算：由输入的实部和虚部生成一个复

3、数；两个复数求和；两个复数求差；两个复数求积。运算结果以相应的复数或实数的表示形式显示。（三） 主要仪器设备仪器：计算机实验环境：Windows 7 Open Watcom C/C+（四） 实验原理1）.首先引入抽象三元组抽象数据类型定义ADT Triplet 数据对象：e1,e2,e3,|e1,e2,e3ElemSet(定义了关系运算的某个集合)数据关系：R1=,基本操作：InitTriplet(&T,v1,v2,v3) 操作结果：构造了三元组T，元素e1,e2和e3分别被赋以参数v1,v2和v3的值。DestroyTriplet (&T) 操作结果：三元组T被销毁。Get(t,I,) 初始

4、条件：三元组T已存在，1=i=3.操作结果：返回的第i元的值e。Put(&T,i,e) 初始条件：三元组已存在，1=i=3.操作结果：改变的第i元的值为e。Max(T) 初始条件：三元组已存在。操作结果：返回的元素中的最大值。Min(T) 初始条件：三元组已存在。操作结果：返回的元素中的最小值。ADT Triplet2.存储类型：typedef float *triplet;3.主函数与其他函数的调用关系：参数是通过地址传递进行的。函数的伪代码：int Initriplet(triplet &t,float v1,float v2,float v3) 分配3个元素的存储空间 分配失败返回err

5、or 对各元素赋值 int Get(triplet t,int i,float *e) /1=i=3,用e返回第i个元素值 判断i的值是否异常 是则返回error 将第i个元素值赋给eint Max(triplet t,float *e) 对三个元素进行两两比较找出最大值int Min(triplet t,float *e) 对三个元素进行两两比较找出最少值2）下面引入复数抽象数据类型定义以及操作。typedef structElemType real;ElemType imaginary;Complex;/定义复数数据类型void CreatComplex(Complex &c,ElemTy

6、pe a,ElemType b)c.real=a;c.imaginary=b;/CreatComplex/构造复数void AddComplex(Complex &sum,Complex c1,Complex c2)sum.real=c1.real+c2.real;sum.imaginary=c1.imaginary+c2.imaginary;/AddComplex/复数加法void SubtractComplex(Complex &sub,Complex c1,Complex c2)sub.real=c1.real-c2.real;sub.imaginary=c1.imaginary-c2.

7、imaginary;/SubtractComplex/复数减法void MultiplyComplex(Complex &mul,Complex c1,Complex c2) mul.real=c1.real*c2.real-c1.imaginary*c2.imaginary; mul.imaginary=c1.imaginary*c2.real+c1.real*c2.imaginary;/MultiplyComplex/复数乘法void ApartReal(Complex &apa,Complex c1)int select;printf(Please choose the operatio

8、n.n);printf(1.Print the real part.n);printf(2.Print the imaginary part.n);doscanf(%d,&select);switch(select)case 1:printf(The real part is %dn,c1.real);break;case 2:printf(The imaginary part is %dn,c1.imaginary);break; case 0: printf(endn);break;default:printf(Input error!n);while(select!=0);/ApartR

9、eal复数实部分部分别显示void PrintComplex(Complex &c) if(c.real & c.imaginary) if(c.imaginary0) printf(%d+(%d!),c.real,c.imaginary); else printf(%d+%d!,c.real,c.imaginary); else if (!c.real & c.imaginary) printf(%d!,c.imaginary); else if (c.real & !c.imaginary) printf(%d,c.real); else printf(0);/PrintComplex/输

10、出（五） 实验步骤及调试分析；首先是三元组抽象数据类型试验的结果。在调试过程中，意外发现编译器支持中文。为了表达得更加直观故用中文来进行描述（虽然中文不利于学习英文的正规表达）。同时，为了更好的习惯英文的正规表达，第二题复数采用了全英文界面。本次试验中因为涉及的函数较多，而且正规的函数命名还是很有讲究的。在学习过程中经常会遇到大小写的问题=_=|.但是解决这些问题之后得到的经验确是相当可贵的。可以说一万个错误，让我学会了一万种调试方法。基本上第一次试验的成功就意味着我学会了50%左右的错误调试方法。1.第一题的结果输出页面：2.第二题输出结果页面因为之前做了数据结构后面的习题所以本实验增强了功

11、能，即多一个分别显示一个复数的实部和虚部。 （六）实验结果及分析；如上。（七）附录：源程序题目一：#include #include typedef int ElemType; typedef int Status;typedef ElemType *Triplet;#define OK 1#define ERROR 0#define OVERFLOW -2Status InitTriplet (Triplet *T) ElemType v1, v2, v3; *T=(ElemType*)malloc(3*sizeof(ElemType); if (*T=0) return OVERFLOW;

12、 scanf(%d%d%d,&v1,&v2,&v3); (*T)0=v1;(*T)1=v2;(*T)2=v3; return OK;/InitTriplet /构造了三元组T,元素e1,e2,e3分别被赋予参数v1,v2,v3的值 Status Get (Triplet T,int i, ElemType *e) /用e返回T的第I个值。 if (i3) return ERROR; *e=Ti-1; return OK;/GetStatus Max(Triplet T,ElemType *e) *e=(T0=T1) ? (T0=T2) ? T0:T2) : (T1=T2) ? T1:T2);

13、return OK;/MaxStatus Min(Triplet T, ElemType *e) *e=(T0=T1) ? (T0=T2) ? T0:T2) : (T1=T2) ? T1:T2); return OK;/Minvoid main() Triplet T; ElemType e; int select, i; printf(请输入三个数字:n); if (InitTriplet(&T)=OVERFLOW) printf(错误,退出!); else do printf(n请输入数字选择功能:n); printf(1:取得第n个数字n); printf(2:取得最大数字n); pri

14、ntf(3:取得最小数字n); printf(0:结束n); scanf(%d,&select); switch (select) case 1:printf(ni=);scanf(%d,&i); if (Get(T,i,&e)=ERROR) printf(i输入错误！(1-3)n); else printf(第i个数字是 %dn,e);break; case 2:Max(T,&e); printf(最大的数字是 %dn,e);break; case 3:Min(T,&e); printf(最小的数字是 %dn,e);break; case 0:printf(完成n);break; defau

15、lt:printf(输入错误！n); /*switch*/ while (select!=0);/*main*/题目二：#include typedef int ElemType;typedef int Status;typedef structElemType real;ElemType imaginary;Complex;void CreatComplex(Complex &c,ElemType a,ElemType b)c.real=a;c.imaginary=b;/CreatComplexvoid AddComplex(Complex &sum,Complex c1,Complex c

16、2)sum.real=c1.real+c2.real;sum.imaginary=c1.imaginary+c2.imaginary;/AddComplexvoid SubtractComplex(Complex &sub,Complex c1,Complex c2)sub.real=c1.real-c2.real;sub.imaginary=c1.imaginary-c2.imaginary;/SubtractComplexvoid MultiplyComplex(Complex &mul,Complex c1,Complex c2) mul.real=c1.real*c2.real-c1.

17、imaginary*c2.imaginary; mul.imaginary=c1.imaginary*c2.real+c1.real*c2.imaginary;/MultiplyComplexvoid ApartReal(Complex &apa,Complex c1)int select;printf(Please choose the operation.n);printf(1.Print the real part.n);printf(2.Print the imaginary part.n);doscanf(%d,&select);switch(select)case 1:printf

18、(The real part is %dn,c1.real);break;case 2:printf(The imaginary part is %dn,c1.imaginary);break; case 0: printf(endn);break;default:printf(Input error!n);while(select!=0);/ApartRealvoid PrintComplex(Complex &c) if(c.real & c.imaginary) if(c.imaginary LIST_INIT_SIZE) return ERROR; L.elem=(ElemType *

19、) malloc(elem_number*sizeof(ElemType); if (!L.elem) exit(OVERFLOW); L.length=0; L.listsize=elem_number; return OK;/InitList_Sq /创建线性表Status ListInsert_Sq(SqList &L,int i,ElemType e) ElemType *p,*q,*newbase; if (iL.length+1) return ERROR; if (L.length=L.listsize) newbase=(ElemType*)realloc(L.elem,(L.

20、listsize+LISTINCREMENT)*sizeof(ElemType); if (!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=L.listsize+LISTINCREMENT; q=&(L.elemi); for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; *q=e; +L.length;return OK;/ ListInsert_Sq/插入线性表元素Status ListDelete_Sq(SqList &L,int i,ElemType &e) ElemType *p,*q;

21、if (iL.length) return ERROR; p=&(L.elemi-1); e=*p; q=L.elem+L.length-1; for(+p; p=q; +p) *(p-1)=*p; -L.length; return OK;/ListDelete_Sq/删除线性表元素void Display_Sq(SqList L) int i; printf(The SqList:); if (L.length=0) printf(none); else for (i=0; iL.length; i+) printf(%d ,L.elemi); printf(n);/Display_SqT

22、/输出线性表元素实验二：Status Input_stu(Stu &e) int i; scanf(%d%s,&e.stu_num,e.stu_name); for (i=0; i LIST_INIT_SIZE) return ERROR; L.elem=(Stu *) malloc (LIST_INIT_SIZE * sizeof (Stu); if (!L.elem) exit (OVERFLOW); L.length=0; L.listsize=elem_number; return OK;/创建学生信息表Status ListInsert_Sq(SqStu &L,int i,Stu e

23、) Stu *p,*q,*newbase; if (iL.length+1) return ERROR; if (L.length=L.listsize) newbase=(Stu *) realloc (L.elem, (L.listsize+LISTINCREMENT)* sizeof (Stu); if (!newbase) exit (OVERFLOW); L.elem=newbase; L.listsize+=L.listsize+LISTINCREMENT; q=&(L.elemi-1); for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; *

24、q=e; +L.length; return OK;/ 插入学生信息Status ListDelete_Sq(SqStu &L,int i,Stu &e) Stu *p,*q; if (iL.length) return ERROR; p=&(L.elemi-1); e=*p; q=L.elem+L.length-1; for(+p; p=q; +p) *(p-1)=*p; -L.length; return OK;/删除学生信息void Display_Sq(SqStu L) int i,j; if (L.length=0) printf(Nonen); else for (i=0; iL.

25、length; i+) printf(stu.%d %-7d %-8s ,i+1,L.elemi.stu_num,L.elemi.stu_name); for (j=0; jM; j+) printf(%.2f ,L.elemi.scorej); printf(n); /输出学生信息（十） 实验步骤及调试分析；在第一个试验中，从实际出发的角度来看，线性表的插入删除功能意味着如果使用顺序表的话在处理上将会消耗大量的时间。所以从实际应用的角度，我选择了链表进行相关操作。在原有第一个试验的基础上进行一些改进便有了第二个试验程序。1.第一题的结果输出页面：2.第二题输出结果页面做了个中文界面。 （六）

26、实验结果及分析；如上。（七）附录：源程序题目一：#include #include #define OK1#define ERROR 0#define OVERFLOW -2#define LIST_INIT_SIZE100#define LISTINCREMENT10typedef int ElemType;typedef int Status;typedef struct ElemType *elem;int length;int listsize;SqList;Status InitList_Sq(SqList &L,int elem_number)if (elem_number LIS

27、T_INIT_SIZE) return ERROR;L.elem=(ElemType *) malloc(elem_number*sizeof(ElemType);if (!L.elem) exit(OVERFLOW);L.length=0;L.listsize=elem_number;return OK;/InitList_SqStatus ListInsert_Sq(SqList &L,int i,ElemType e)ElemType *p,*q,*newbase;if (iL.length+1) return ERROR;if (L.length=L.listsize) newbase

28、=(ElemType *) realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType);if (!newbase) exit(OVERFLOW);L.elem=newbase;L.listsize+=L.listsize+LISTINCREMENT;q=&(L.elemi);for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p;*q=e;+L.length;return OK;/ ListInsert_SqStatus ListDelete_Sq(SqList &L,int i,ElemType &e

29、)ElemType *p,*q;if (iL.length) return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p; p=q; +p) *(p-1)=*p;-L.length;return OK;/ListDelete_Sqvoid Display_Sq(SqList L)int i;printf(The SqList:);if (L.length=0)printf(none);elsefor (i=0; iL.length; i+)printf(%d,L.elemi);printf(n);/Display_Sqvoid mai

30、n()SqList L;int n,e,s,t;int i,select;printf(Input the number of the SqList:);scanf(%d,&n);if (InitList_Sq(L,n)=OVERFLOW)printf(Fail,exit!);elseprintf(Input the members of the SqList:);for (i=0; in; i+)scanf(%d,&L.elemi);L.length=n;Display_Sq(L);printf(Choose the operation by number:n);printf(1-inser

31、t2-delete0-endingn);doscanf(%d,&select);switch (select)case 1:printf(Input the location to insert:);scanf(%d,&s);printf(Input the member to insert:);scanf(%d,&e);ListInsert_Sq(L,s,e);Display_Sq(L);printf(n);break;case 2:printf(Input the location to delete:);scanf(%d,&t);ListDelete_Sq(L,t,e);Display_

32、Sq(L);printf(n);break;case 0:printf(Program Ending!n);break;default:printf(input errorn);/switchwhile(select);Statu InitList_Sq(SqList &L)L.elem=(ElemType *) malloc(elem_number*sizeof(ElemType);if (!L.elem) exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;题目二：#include #include #define O

33、K 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 30#define M 3typedef int Status;typedef struct int stu_num; char stu_name10; float scoreM;Stu;typedef struct Stu *elem; int length; int listsize;SqStu;Status Input_stu(Stu &e) int i; scanf(%d%s,

34、&e.stu_num,e.stu_name); for (i=0; i LIST_INIT_SIZE) return ERROR; L.elem=(Stu *) malloc (LIST_INIT_SIZE * sizeof (Stu); if (!L.elem) exit (OVERFLOW); L.length=0; L.listsize=elem_number; return OK;/InitList_SqStatus ListInsert_Sq(SqStu &L,int i,Stu e) Stu *p,*q,*newbase; if (iL.length+1) return ERROR

35、; if (L.length=L.listsize) newbase=(Stu *) realloc (L.elem, (L.listsize+LISTINCREMENT)* sizeof (Stu); if (!newbase) exit (OVERFLOW); L.elem=newbase; L.listsize+=L.listsize+LISTINCREMENT; q=&(L.elemi-1); for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; *q=e; +L.length; return OK;/ ListInsert_SqStatus ListDelete_Sq(SqStu &L,