数据结构 实验报告完整版

1、四川师范大学计算机学院 实 验 报 告 册 院系名称： 计算机科学学院 课程名称： 数据结构 实验学期 2010 年至 2011 年 第 一 学期 专业班级： 2010级教育技术学 姓名： 学号： 指导教师： 实验最终成绩： 实验报告须知 1学生填写实验报告应按规范填写，填写格式见由任课老师给出的实验报告样本； 2学生应填写的内容包括：封面相关栏目、第一页中本学期（年）开设实验课程情况一览表中的实验名称、学时数；每次报告中的实验性质、同组人姓名、实验日期、以及实验报告中的一至五项； 3教师填写内容为：实验评价、每次报告成绩、第一页中本学期（年）开设实验课程情况一览表中成绩、及封面的实验最终成绩

2、； 4学生实验结束后，教师应对学生实验结果进行核实，学生方可离开实验室。 5、实验成绩等级分为（90100分）优，（8089分）良，(70-79分)中，（6069分）及格，（59分）不及格。 6本实验册应妥善保管，本课程实验结束后应交回实验室。本学期（年）开设实验课程情况一览表 实验名成学时（分数或等级（学生实验后填写学1抽象数据类型的表示与实学2线性表实3学栈和队列实学4稀疏矩阵实5学树和二叉树实6学图及其应用实学7查找和排序实89101112131415161718 19 20 实验报告（1） 实验名称抽象数据类型的表示与实现 基本操作 验证性 同组人姓名实验性质 综合性 设计性 实验日期

3、2011年9月 实验成绩 30日 教师评价： 实验预习 实验操作 实验结果 实验报告 其它 教师签名： 一、实验目的及要求 1) 熟悉类C语言的描述方法，学会将类C语言描述的算法转换为实现； C源程序2) 理解抽象数据类型的定义，编写完整的程序实现一个抽象数据类型（如三元组）。 3) 认真阅读和掌握本实验的参考程序，上机运行程序，保存和打印出程序的运行结果，并结合程序进行分析。二、 实验内容 1）编程实现抽象数据类型三元组的定义、存储、基本操作（最大值、最小值、，并设计一个主菜单完成各个功能的调用。平均值等的求解） 三、主要设备及软件 1) 机PC2) Turbo C 2.0 Visual C

4、+或 四、实验流程、操作步骤或核心代码、算法片段 （一）头文件（H1.h） #ifndef H1_H #define H1_H #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef int ElemType; typedef ElemType *Triplet; 函数声明/InitTriplet (Triplet &T,ElemType v1,ElemType v2,ElemType v3); extern Status DestroyTriplet (Triplet &T); extern S

5、tatus Get(Triplet T,int i,ElemType &e); extern Status Put(Triplet &T, int i, ElemType e); extern Status Max(Triplet T,ElemType &e); extern Status Min(Triplet T,ElemType &e); extern Status Average(Triplet T,ElemType &e); extern Status #endif ）function.cpp)(二功能函数（#include #include h1.h Status InitTrip

6、let(Triplet &T, ElemType v1, ElemType v2, ElemType v3) T=(ElemType *)malloc(3*sizeof(ElemType); if(!T) return OVERFLOW; T0=v1;T1=v2;T2=v3; return OK; DestroyTriplet(Triplet &T) Status T=NULL; free(T); return OK; Get(Triplet T,int i,ElemType &e) Status if(i3) return ERROR; e=Ti-1; return OK; Put(Trip

7、let &T, int i, ElemType e) Status if(i3) return ERROR; Ti-1=e; return OK; Status Max(Triplet T,ElemType &e) e=(T0=T1)?(T0=T2) ? T0:T2):(T1=T2)?T1:T2); return OK; Min(Triplet T,ElemType &e) Status e=(T0= T1)?(T0=T2) ? T0:T2):(T1=T2)?T1:T2); return OK; Status Average(Triplet T,ElemType &e) e=(T0+T1+T2

8、)/3; return OK; (triplet.cpp) （三）主函数#include #include h1.h void main() p; Triplet ElemType e,v1,v2,v3; int i; int select; n); 输入三个数，建立一个三元组 牰湩晴尨scanf(%d%d%d,&v1,&v2,&v3); if (InitTriplet(p,v1,v2,v3)=OVERFLOW) ); 分配失败，退出程序！ 牰湩晴尨 else do printf(: 取三元组的最大值 n); printf(: 取三元组的最小值 n); printf(: 求三元组的平均值n);

9、 printf(结束！n); 牰湩晴尨 请输入选择！n); scanf(%d,&select); switch (select) case 1: Max(p,e); 牰湩晴尨最大值是：%dn,e);break; case 2: Min(p,e); 牰湩晴最小值是%dn,e);break;case 3:Average(p,e);牰湩晴平均值是%dn,e);break;case 0:牰湩晴操作结束); break;敤慦汵?瀠楲瑮输入选择出错n);/ end of switchwhile(select!=0); /end of whileDestroyTriplet(p);/ end of main

10、五实验结果的分析与评实验结果： 分析： （1） 类C语言面对对象，而C语言面对过程； （2） 核心算法就相当于C语言的程序； （3） 初步了解三元组的建立等知识； （4） 初步了解利用C+编程的步骤及编程的组成部分； （5） 初次接触还是对很多地方倍感疑惑，需要多多操作理解； 实验报告（2） 线性表实验：顺序存储、链式存储 实验名称 基本操作 验证性 实验性质同组人姓名 综合性 设计性 10年2010实验成绩实验日期 日9月 教师评价： 其它 实验报告 实验结果 实验操作 实验预习 一、1现； 23指针类型、链表的使用）认真阅读和掌握本实验的参考程序，运行结果，并结合程序进行分析。按照你对线性

11、表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果二、教师签名： 实验目的及要求 ） 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实）以线性表的各种操作（建立、插入、删除等）的实现为重点；）通过本次实习帮助学生加深对高级语言 C语言的使用（特别是函数参数、。 上机运行本程序， 保存和打印出程序的实验内容 1） 编程实现线性表两种存储结构中的基本操作的实现（线性表的创建、插入、删除和查找），并设计一个主菜单完成各个功能的调用。 三、主要设备及软件 1） 机PC2） 或Turbo C 2.0 Visual C+ 四、实验流程、操作步骤或核心代码、算法片段 1.顺序存储的程

12、序： Status InitList_Sq(SqList &L,int n) int i; L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); (一)头文件(H1.h) #ifndef H1_H #define H1_H #define LIST_INIT_SIZE 100 /线形表存储空间的初始分配量 #define LISTINCREMENT 10 /线形表存储空间的分配增量 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int ElemType; type

13、def int Status; typedef struct ElemType *elem; /存储空间基址 int length; /当前长度 int listsize; /当前分配的存储容量 SqList;/函数声明 extern Status InitList_Sq(SqList &L,int n); extern Status ListInsert_Sq(SqList &L,int i,ElemType e); extern Status ListDelete_Sq(SqList &L,int i,ElemType &e); extern Status LocateElem_Sq(Sq

14、List L,ElemType e); extern Status Destrory_Sq(SqList &L); #endif (二)功能函数（function.cpp） #include stdlib.h #include h1.h #include stdio.h if(!L.elem)return OVERFLOW;/存储分配失L.length=0;/空表长度0for(i=0;in;i+)scanf(%d,&(L.elemi);+L.length;L.listsize=LIST_INIT_SIZE;/初始存储容return OK;/Initlist_sqStatusListInsert

15、_Sq(SqList &L,int i,ElemType e)ElemType *newbase;ElemType *p;ElemType *q;if(iL.length+1)return ERROR;/值不合if(L.length=L.listsize)/当前存储空间已满，增加分newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)return OVERFLOW;/存储分配失L.elem=newbase;/新基L.listsize+=LISTINCREMENT;/增

16、加存储容q=&(L.elemi-1);for(p=&(L.elemL.length-1); p=q;-p)插入位置及之后的元素右/*(p+1)=*p;e*q=e;插/1+L.length;表长/return OK;/ListInsert_sqStatusListDelete_Sq(SqList &L,int i,ElemType &e)ElemType *p;ElemType *q; if(iL.length) return ERROR; /i 值不合法 p=&(L.elemi-1); /p为被删除元素的位置 e=*p; /被删除元素的值赋给e q=L.elem+L.length-1; / 表

17、尾元素的位置 for(+p;p=q;+p) *(p-1)=*p; /被删除元素之后的元素左移 -L.length; /表长减1 return OK; /ListDelete_sq Status LocateElem_Sq(SqList L, ElemType e) / 在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回 0 int i = 1; / i 的初值为第 1 元素的位序 ElemType *p=L.elem; / p 的初值为第 1 元素的存储位置 while(i=L.length)&(*p+!=e) +i; if (i=L.length) retur

18、n i; else return 0; / LocateElem_Sq Status Destrory_Sq(SqList &L) return OK; main.cpp）三 ()主函数（#include #include h1.h void main() SqList p; int i,e,n; int select; 牰湩晴尨请输入你将要建立的链表的大小n：); scanf(%d,&n); printf(请输入%d个数值并用空格符分隔:n,n); InitList_Sq(p,n); printf(你建立的链表为： n); for(i=0;in;i+) printf(=,p.elemi);

19、/*if(InitList_Sq(p,n)=OVERFLOW) 牰湩晴尨分配失败，退出程序!); else */ do printf(1:在链表原来的基础上插入一个值n); printf(: 删除链表中的一个值 n); printf(: 查找链表中的某一个值 n); printf(结束！ n); 牰湩晴尨 请输入选择！n); scanf(%d,&select); switch (select) case 1: 牰湩晴尨从键盘输入你插入的元素的位置 i和插入元素的值e:n); scanf(%d%d,&i,&e); ListInsert_Sq (p,i,e); 牰湩晴尨 插入后所有的值是： n);

20、 for(i=0;ip.length;i+) printf(=,p.elemi); break; case 2: 牰湩晴尨输入你删除的元素的位置 i ：n); scanf(%d,&i); ListDelete_Sq(p,i,e); 瀠楲瑮? 删除后所有的值是：n); for(i=0;inext=NULL; /先建一个带头结点的单链表 for(i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode); / 生成结点 scanf(%d,&p-data); /输入元素 p-next=L-next; L-next=p; /插入到表头 return OK; /CreateL

21、ist_L Status GetElem_L(LinkList L,int i,ElemType &e) /L为带结点的单链表的头指针 /当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR LinkList p; p=L-next; int j=1; / 初始化，p 指向第一个结点，j为计数器 while(p&jnext; +j; if(!p|ji) i个元素不存在第 return ERROR; / e=p-data; return OK; /GetElem_L Status ListInsert_L(LinkList &L,int i,ElemType e) e 个位置之前插入元素

22、i中第L在带结点的单链线性表/ struct LNode *s; struct LNode *p; p=L; int j=0; while(p&jnext;+j; /寻找第 i-1个结点 if(!p|ji-1) return ERROR; /i 小于1或者大于表长加1 s=(LinkList)malloc (sizeof(LNode); / 生成新结点 s-data=e;s-next=p-next; /插入L中 p-next=s; return OK; /ListInsert_L Status ListDelete_L(LinkList &L,int i,ElemType &e) /在带头结点

23、的单链线性表L中，删除第i个元素，并由e返回其值 struct LNode *p; p=L; struct LNode *q; int j=0; while(p-next&jnext;+j; if(!(p-next)|j(i-1) 删除位置不合理 /return ERROR; 删除并释放结点 / q=p-next;p-next=q-next; e=q-data;free(q); return OK; /ListDelete_L Destroy_L(LinkList &L) return OK; ）main.cpp（三）主函数（#include #include h1.h void main()

24、 LinkList p,L,s; ElemType data; int i,n,e; int select; 牰湩晴尨 从键盘输入你建立的链表的数值个数n：); scanf(%d,&n); printf(请输入%d个链表的值，并用空格符分隔：n,n); CreateList_L(L,n); p=L; printf(建立的单链线性表L 为:n); while(p-next) p=p-next; printf(=,p-data); /*if(CreateList_L(p,n)=OVERFLOW) ); 牰湩晴尨分配失败，退出程序！ else */ do printf(1:取出建立的链表中的某一个值

25、 n); printf(: 在链表中插入某一个新值 n); printf(: 删除链表中的某一个值 n); printf(结束！ n); 牰湩晴尨 请输入选择！ n); scanf(%d,&select); switch (select) case 1: 牰湩晴尨 从键盘输入取出的元素的位置 i ：n); scanf(%d,&i); GetElem_L(L,i,e); :%dn,e); 取出的元素是牰湩晴尨 break;case 2:牰湩晴从键盘输入插入元素的位和插入元素的e并空格分隔n);scanf(%d%d,&i,&e);ListInsert_L(L,i,e);牰湩晴插入后的所有元素是n)

26、;s=L;while(s-next)s=s-next;printf(=,s-data);break;case 3:牰湩晴从键盘输入删除的元素位n);scanf(%d,&i);ListDelete_L(L,i,e);牰湩晴删除后的所有元素是n);s=L;while(s-next)s=s-next;printf(=,s-data);break;case 0:牰湩晴操作结束);break;敤慦汵?瀠楲瑮输入选择出错n);/ end of switchwhile(select!=0); /end of whileDestroy_L(p);/ end of mai五实验结果的分析与评结果）顺序存 2）链

27、式存储 分析：（1）对实验的整体结果比较清楚，但具体细节或者说每一个关键的操作步骤还是不懂； （2）试着尝试抛弃书上的编程过程，建立属于自己的编程风格，了解必要编程知识； 实验报告（3） 实验名称栈和队列实验 基本操作 验证性 同组人姓名 实验性质 10 综合性 设计性 2011年实验日期 月实验成绩 28日 教师评价： 实验预习 实验操作 实验结果 实验报告 其它 教师签名： 一、 实验目的及要求 1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。2）本实验训练的要点是“栈”和“队列”的观点； 二、实验内容 1) 利用栈，实现任一个表达式中的语法检查（如括号的

28、匹配）。 2） 编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； 三、主要设备及软件 1) 机PC2) Visual C+或Turbo C 2.0 四、实验流程、操作步骤或核心代码、算法片段 1）括号匹配： （一）H1.h(头文件) #ifndef H1_H #define H1_H #include #include #define OVERFLOW -1 #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define NULL 0 type

29、def char SElemType; typedef int Status; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; extern Status InitStack(SqStack &S); extern Status DestroyStack(SqStack &S); extern Status StackEmpty(SqStack &S); extern Status Push(SqStack &S,SElemType e); extern Status Pop(SqStack &S,

30、SElemType &e); #endif (二)功能函数（function.cpp） #include #include h1.h #include stdio.h Status InitStack(SqStack &S) S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType); if(!S.base) return OVERFLOW; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; Status DestroyStack(SqStack &S) free(S.b

31、ase); S.base=NULL; S.top=NULL; S.stacksize=0; return OK; Status StackEmpty(SqStack &S) if(S.top=S.base) return OK; else return ERROR; Status Push(SqStack &S,SElemType e) if(S.top-S.base=S.stacksize) S.base=(SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) retur

32、n OVERFLOW; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; Status Pop(SqStack &S,SElemType &e) if(S.top=S.base) return ERROR; e=*-S.top; return OK; （三）主函数（main.cpp） #include #include h1.h #include stdio.h main() SqStack S; SElemType elem; char e,a20; int i=0; int flag=1; if( InitStack(S) 牰湩晴尨空间已经准备好!n); else 牰湩晴尨空间不足!n); printf(请输入括号