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

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=<e1,e2>,<e2,e3>基本操作：InitTriplet(&T,v1,v2,v3) 操作结果：构造了三元组T，元素e1,e2和e3分别被赋以参数v1,v2和v3的值。DestroyTrip

4、let (&T) 操作结果：三元组T被销毁。Get(t,I,) 初始条件：三元组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(tr

5、iplet &t,float v1,float v2,float v3) 分配3个元素的存储空间 分配失败返回error 对各元素赋值 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;E

6、lemType imaginary;Complex;/定义复数数据类型void CreatComplex(Complex &c,ElemType 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 &

7、;sub,Complex c1,Complex c2)sub.real=c1.real-c2.real;sub.imaginary=c1.imaginary-c2.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/复

8、数乘法void 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("The real part is %dn",c1.

9、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);/ApartReal复数实部分部分别显示void PrintComplex(Complex &c) if(c.real && c.imaginary) if(c.imaginary<0) printf(&

10、quot;%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/输出（五） 实验步骤及调试分析；

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

12、实部和虚部。 （六）实验结果及分析；如上。（七）附录：源程序题目一：#include <stdio.h>#include <stdlib.h> 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)

13、 return OVERFLOW; 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 (i<1 | i>3) return ERROR; *e=Ti-1; return OK;/GetStatus Max(Triplet T,ElemType

14、*e) *e=(T0>=T1) ? (T0>=T2) ? T0:T2) : (T1>=T2) ? T1:T2); 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)=OVER

15、FLOW) printf("错误,退出!"); else do printf("n请输入数字选择功能:n"); printf("1:取得第n个数字n"); printf("2:取得最大数字n"); printf("3:取得最小数字n"); printf("0:结束n"); scanf("%d",&select); switch (select) case 1:printf("ni=");scanf("%d",

16、&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; default:printf("输入

17、错误！n"); /*switch*/ while (select!=0);/*main*/题目二：#include <stdio.h>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,Com

18、plex c1,Complex c2)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

19、.real=c1.real*c2.real-c1.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 imagin

20、ary 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)

21、;/ApartRealvoid PrintComplex(Complex &c) if(c.real && c.imaginary) if(c.imaginary<0) 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 &

22、& !c.imaginary) printf("%d",c.real); else printf("0");/PrintComplexvoid main() ElemType a,b,c,d; Complex c1,c2,sum,sub,mul,apa;/ int i,j; int select,choice; printf("please input the 1st Complex number's real part:"); scanf("%d",&a); printf("pl

23、ease input the 1st Complex number's imaginary part:"); scanf("%d",&b); printf("please input the 2nd Complex number's real part:"); scanf("%d",&c); printf("please input the 2nd Complex number's imaginary part:"); scanf("%d",&a

24、mp;d); CreatComplex(c1,a,b); CreatComplex(c2,c,d); printf("nplase choose the following operation with its number:n"); printf("1-addition 2-subtract 3-multiply 4-apart the real or imaginary 0-endn"); do scanf("%d",&select); switch(select) case 1: AddComplex(sum,c1,c2

25、); printf("("); PrintComplex(c1); printf(")+("); PrintComplex(c2); printf(")="); PrintComplex(sum); printf("n"); break; case 2: SubtractComplex(sub,c1,c2); printf("("); PrintComplex(c1); printf(")-("); PrintComplex(c2); printf(")="

26、;); PrintComplex(sub); printf("n"); break; case 3: MultiplyComplex(mul,c1,c2); printf("("); PrintComplex(c1); printf(")*("); PrintComplex(c2); printf(")="); PrintComplex(mul); printf("n"); break; case 4: printf("Please choose the Complex you nee

27、d to apart:n"); printf("1-The first complex 2-The second complexn"); scanf("%d",&choice); if(choice=1) ApartReal(apa,c1); else if(choice=2) ApartReal(apa,c2); else printf("Input error!n"); break; case 0: printf("endn"); break; default: printf("in

28、put errorn"); /switch while(select!=0);/main 本科实验报告专用纸课程名称 数据结构 成绩评定 实验项目名称 线性表及其应用 指导教师 实验项目编号 &806154904 实验项目类型 综合性 学生姓名 学号 实验地点 南海楼 学院 系 专业 实验时间 2009 年 09月16日 上午09月16日上午 温度 湿度 （六） 实验目的和要求1. 熟练掌握线性表的基本操作在顺序存储结构上的实现。2. 熟熟练掌握线性表基本操作的实现及应用.(选一种高级程序语言编写源程序，并调试通过，测试正确。)（七） 实验主要内容实验一内容：1) 建立n个元

29、素的顺序表SqList，实现顺序表的基本操作；2) 在SqList的元素i之后插入一个元素，实现顺序表插入的基本操作；3) 在SqList中删除指定位置i上的元素，实现顺序表删除的操作。实验二内容：1) 利用顺序表完成一个班级的一个学期的课程的管理：能够增加、删除、修改学生的成绩记录。（八） 主要仪器设备仪器：计算机实验环境：Windows 7 Open Watcom C/C+（九） 实验原理1) 抽象数据类型：typedef struct ElemType *elem; int length; int listsize;SqList;基本操作：实验一：Status InitList_Sq(S

30、qList &L,int elem_number) if (elem_number> LIST_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_Sq /创建线性表Status ListInsert_Sq(SqList &L,int i,ElemType e) ElemType *p,*q,*

31、newbase; if (i<1 | i>L.length+1) return ERROR; if (L.length>=L.listsize) newbase=(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

32、;-p) *(p+1)=*p; *q=e; +L.length;return OK;/ ListInsert_Sq/插入线性表元素Status ListDelete_Sq(SqList &L,int i,ElemType &e) ElemType *p,*q; if (i<1 | i>L.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/删除线性

33、表元素void Display_Sq(SqList L) int i; printf("The SqList:"); if (L.length=0) printf("none"); else for (i=0; i<L.length; i+) printf("%d ",L.elemi); printf("n");/Display_SqT/输出线性表元素实验二：Status Input_stu(Stu &e) int i; scanf("%d%s",&e.stu_num,e.

34、stu_name); for (i=0; i<M; i+) scanf ("%f",&e.scorei); return OK;/输入学生信息Status InitList_Sq(SqStu &L,int elem_number) if (elem_number> 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_n

35、umber; return OK;/创建学生信息表Status ListInsert_Sq(SqStu &L,int i,Stu e) Stu *p,*q,*newbase; if (i<1 | i>L.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

36、.listsize+LISTINCREMENT; q=&(L.elemi-1); for(p=&(L.elemL.length-1);p>=q;-p) *(p+1)=*p; *q=e; +L.length; return OK;/ 插入学生信息Status ListDelete_Sq(SqStu &L,int i,Stu &e) Stu *p,*q; if (i<1 | i>L.length) return ERROR; p=&(L.elemi-1); e=*p; q=L.elem+L.length-1; for(+p; p<=q

37、; +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; i<L.length; i+) printf("stu.%d %-7d %-8s ",i+1,L.elemi.stu_num,L.elemi.stu_name); for (j=0; j<M; j+) printf("%.2f ",L.elemi.scorej); prin

38、tf("n"); /输出学生信息（十） 实验步骤及调试分析；在第一个试验中，从实际出发的角度来看，线性表的插入删除功能意味着如果使用顺序表的话在处理上将会消耗大量的时间。所以从实际应用的角度，我选择了链表进行相关操作。在原有第一个试验的基础上进行一些改进便有了第二个试验程序。1.第一题的结果输出页面：2.第二题输出结果页面做了个中文界面。 （六）实验结果及分析；如上。（七）附录：源程序题目一：#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define OVE

39、RFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT   10typedef int ElemType;typedef int Status;typedef struct     ElemType *elem;    int length;    int listsize;SqList;Status InitList_Sq(SqList &L,int elem_numbe

40、r)    if (elem_number> LIST_INIT_SIZE) return ERROR;    L.elem=(ElemType *) malloc(elem_number*sizeof(ElemType);    if (!L.elem) exit(OVERFLOW);    L.length=0;    L.listsize=elem_number;  

41、;  return OK;/InitList_SqStatus ListInsert_Sq(SqList &L,int i,ElemType e)    ElemType *p,*q,*newbase;    if (i<1 | i>L.length+1) return ERROR;    if (L.length>=L.listsize)        

42、60;newbase=(ElemType *) realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType);        if (!newbase) exit(OVERFLOW);        L.elem=newbase;        L.listsize+=L.listsize+LISTI

43、NCREMENT;        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) 

44、;   ElemType *p,*q;    if (i<1 | i>L.length) return ERROR;    p=&(L.elemi-1);    e=*p;    q=L.elem+L.length-1;    for(+p; p<=q; +p) *(p-1)=*p;    -L.len

45、gth;    return OK;/ListDelete_Sqvoid Display_Sq(SqList L)    int i;    printf("The SqList:");    if (L.length=0)        printf("none");    e

46、lse        for (i=0; i<L.length; i+)            printf("%d ",L.elemi);        printf("n");/Display_Sqvoid main()   &#

47、160;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)     &

48、#160;  printf("Fail,exit!");    else            printf("Input the members of the SqList:");        for (i=0; i<n; i+)     

49、       scanf("%d",&L.elemi);        L.length=n;        Display_Sq(L);               printf("

50、;Choose the operation by number:n");        printf("1-insert 2-delete 0-endingn");        do                 &

51、#160;  scanf("%d",&select);            switch (select)            case 1:              

52、;  printf("Input the location to insert:");                scanf("%d",&s);                printf("Inp

53、ut the member to insert:");                scanf("%d",&e);                ListInsert_Sq(L,s,e);    &#

54、160;           Display_Sq(L);                printf("n");                br

55、eak;            case 2:                printf("Input the location to delete:");            

56、;    scanf("%d",&t);                ListDelete_Sq(L,t,e);                Display_Sq(L);   &

57、#160;            printf("n");                break;            case 0:   &#

58、160;            printf("Program Ending!n");                break;            default: 

59、;               printf("input errorn");            /switch        while(select);    Statu InitL

60、ist_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 <stdio.h>

61、#include <stdlib.h>#define OK 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 In

62、put_stu(Stu &e) int i; scanf("%d%s",&e.stu_num,e.stu_name); for (i=0; i<M; i+) scanf ("%f",&e.scorei); return OK;/Input_stuStatus InitList_Sq(SqStu &L,int elem_number) if (elem_number> LIST_INIT_SIZE) return ERROR; L.elem=(Stu *) malloc (LIST_INIT_SIZE * sizeof (Stu); if