数据结构 实验报告完整版.doc

四川师范大学计算机学院实 验 报 告 册院系名称： 计算机科学学院 课程名称： 数据结构 实验学期 2010 年至 2011 年 第 一 学期专业班级： 2010级教育技术学 姓名： 学号： 指导教师： 实验最终成绩： 实验报告须知1学生填写实验报告应按规范填写，填写格式见由任课老师给出的实验报告样本；2学生应填写的内容包括：封面相关栏目、第一页中本学期（年）开设实验课程情况一览表中的实验名称、学时数；每次报告中的实验性质、同组人姓名、实验日期、以及实验报告中的一至五项；3教师填写内容为：实验评价、每次报告成绩、第一页中本学期（年）开设实验课程情况一览表中成绩、及封面的实验最终成绩；4学生实验结束后，教师应对学生实验结果进行核实，学生方可离开实验室。5、实验成绩等级分为（90100分）优，（8089分）良，(70-79分)中，（6069分）及格，（59分）不及格。6本实验册应妥善保管，本课程实验结束后应交回实验室。 本学期（年）开设实验课程情况一览表序号实验名称（学生实验后填写）学时数成绩（分数或等级）1抽象数据类型的表示与实现2学时2线性表实验4学时3栈和队列实验6学时4稀疏矩阵实验4学时5树和二叉树实验6学时6图及其应用实验6学时7查找和排序实验4学时891011121314151617181920实验报告（1）实验名称抽象数据类型的表示与实现同组人姓名实验性质 基本操作 验证性 综合性 设计性实验日期2011年9月30日实验成绩教师评价：实验预习 实验操作 实验结果 实验报告 其它 教师签名：一、实验目的及要求1) 熟悉类C语言的描述方法，学会将类C语言描述的算法转换为C源程序实现；2) 理解抽象数据类型的定义，编写完整的程序实现一个抽象数据类型（如三元组）。3) 认真阅读和掌握本实验的参考程序，上机运行程序，保存和打印出程序的运行结果，并结合程序进行分析。二、实验内容1）编程实现抽象数据类型三元组的定义、存储、基本操作（最大值、最小值、平均值等的求解），并设计一个主菜单完成各个功能的调用。三、主要设备及软件1) PC机2) Turbo C 2.0 或Visual C+四、实验流程、操作步骤或核心代码、算法片段（一）头文件（H1.h）#ifndef H1_H#define H1_H#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef ElemType *Triplet;/函数声明extern Status InitTriplet (Triplet &T,ElemType v1,ElemType v2,ElemType v3);extern Status DestroyTriplet (Triplet &T);extern Status 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);#endif(二)功能函数（function.cpp）#include #include h1.hStatus InitTriplet(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;Status DestroyTriplet(Triplet &T)free(T); T=NULL;return OK;Status Get(Triplet T,int i,ElemType &e)if(i3) return ERROR; e=Ti-1;return OK;Status Put(Triplet &T, int i, ElemType e)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;Status Min(Triplet T,ElemType &e)e=(T0= T1)?(T0=T2) ? T0:T2):(T1=T2)?T1:T2);return OK;Status Average(Triplet T,ElemType &e)e=(T0+T1+T2)/3; return OK;（三）主函数(triplet.cpp)#include #include h1.hvoid main()Triplet p;ElemType e,v1,v2,v3;int i;int select;printf(输入三个数，建立一个三元组n);scanf(%d%d%d,&v1,&v2,&v3);if (InitTriplet(p,v1,v2,v3)=OVERFLOW) printf(分配失败，退出程序！);else do printf(1: 取三元组的最大值n);printf(2: 取三元组的最小值n); printf(3: 求三元组的平均值n);printf(0:结束！n);printf(请输入选择！n);scanf(%d,&select);switch (select)case 1: Max(p,e); printf(最大值是：%dn,e);break;case 2:Min(p,e); printf(最小值是：%dn,e);break;case 3:Average(p,e); printf(平均值是：%dn,e);break;case 0:printf(操作结束！); break;default: printf(输入选择出错！n);/ end of switchwhile(select!=0); /end of whileDestroyTriplet(p);/ end of main五、实验结果的分析与评价实验结果：分析：（1） 类C语言面对对象，而C语言面对过程；（2） 核心算法就相当于C语言的程序；（3） 初步了解三元组的建立等知识；（4） 初步了解利用C+编程的步骤及编程的组成部分；（5） 初次接触还是对很多地方倍感疑惑，需要多多操作理解；实验报告（2）实验名称线性表实验：顺序存储、链式存储同组人姓名实验性质 基本操作 验证性 综合性 设计性实验日期2010年10月9日实验成绩教师评价：实验预习 实验操作 实验结果 实验报告 其它 教师签名：一、实验目的及要求1） 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现；2）以线性表的各种操作（建立、插入、删除等）的实现为重点；3）通过本次实习帮助学生加深对高级语言C语言的使用（特别是函数参数、指针类型、链表的使用）。认真阅读和掌握本实验的参考程序，上机运行本程序， 保存和打印出程序的运行结果，并结合程序进行分析。按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果二、实验内容1） 编程实现线性表两种存储结构中的基本操作的实现（线性表的创建、插入、删除和查找），并设计一个主菜单完成各个功能的调用。三、主要设备及软件1） PC机2） Turbo C 2.0 或Visual C+四、实验流程、操作步骤或核心代码、算法片段1.顺序存储的程序：(一)头文件(H1.h)#ifndef H1_H#define H1_H#define LIST_INIT_SIZE 100 /线形表存储空间的初始分配量#define LISTINCREMENT 10 /线形表存储空间的分配增量#define OVERFLOW -2#define OK 1#define ERROR 0typedef int ElemType;typedef 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(SqList L,ElemType e);extern Status Destrory_Sq(SqList &L);#endif(二)功能函数（function.cpp）#include stdlib.h#include h1.h#include stdio.hStatus InitList_Sq(SqList &L,int n) int i;L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);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_sqStatus ListInsert_Sq(SqList &L,int i,ElemType e)ElemType *newbase;ElemType *p;ElemType *q;if(iL.length+1)return ERROR; /i值不合法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; /增加存储容量q=&(L.elemi-1);for(p=&(L.elemL.length-1); p=q;-p) *(p+1)=*p; /插入位置及之后的元素右移*q=e; /插入e+L.length; /表长增1return OK;/ListInsert_sqStatus ListDelete_Sq(SqList &L,int i,ElemType &e)ElemType *p;ElemType *q;if(iL.length) return ERROR; /i值不合法p=&(L.elemi-1); /p为被删除元素的位置e=*p; /被删除元素的值赋给eq=L.elem+L.length-1; /表尾元素的位置for(+p;p=q;+p)*(p-1)=*p; /被删除元素之后的元素左移-L.length; /表长减1return OK;/ListDelete_sqStatus 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)return i;elsereturn 0; / LocateElem_SqStatus Destrory_Sq(SqList &L)return OK; (三)主函数（main.cpp）#include #include h1.hvoid main()SqList p;int i,e,n;int select;printf(请输入你将要建立的链表的大小n：);scanf(%d,&n);printf(n请输入%d个数值并用空格符分隔:n,n);InitList_Sq(p,n);printf(n你建立的链表为：n);for(i=0;in;i+) printf(%3d,p.elemi);/*if(InitList_Sq(p,n)=OVERFLOW) printf(分配失败，退出程序!);else */ do printf(n1:在链表原来的基础上插入一个值n);printf(2: 删除链表中的一个值n);printf(3: 查找链表中的某一个值n);printf(0:结束！n);printf(请输入选择！n);scanf(%d,&select);switch (select)case 1:printf(从键盘输入你插入的元素的位置i和插入元素的值e:n);scanf(%d%d,&i,&e);ListInsert_Sq (p,i,e);printf(插入后所有的值是：n);for(i=0;ip.length;i+)printf(%3d,p.elemi);break;case 2:printf(输入你删除的元素的位置i：n);scanf(%d,&i);ListDelete_Sq(p,i,e); printf(删除后所有的值是：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;/CreateList_LStatus GetElem_L(LinkList L,int i,ElemType &e)/L为带结点的单链表的头指针/当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORLinkList p;p=L-next;int j=1; /初始化，p指向第一个结点，j为计数器while(p&jnext;+j;if(!p|ji) return ERROR; /第i个元素不存在e=p-data;return OK;/GetElem_LStatus ListInsert_L(LinkList &L,int i,ElemType e)/在带结点的单链线性表L中第i个位置之前插入元素estruct LNode *s;struct LNode *p;p=L;int j=0;while(p&jnext;+j; /寻找第i-1个结点if(!p|ji-1)return ERROR; /i小于1或者大于表长加1s=(LinkList)malloc (sizeof(LNode); /生成新结点s-data=e;s-next=p-next; /插入L中p-next=s;return OK;/ListInsert_LStatus ListDelete_L(LinkList &L,int i,ElemType &e)/在带头结点的单链线性表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_LDestroy_L(LinkList &L)return OK;（三）主函数（main.cpp）#include #include h1.hvoid main()LinkList p,L,s;ElemType data;int i,n,e;int select;printf(从键盘输入你建立的链表的数值个数n：);scanf(%d,&n);printf(n请输入%d个链表的值，并用空格符分隔：n,n); CreateList_L(L,n);p=L;printf(n建立的单链线性表L为:n);while(p-next)p=p-next;printf(%3d,p-data);/*if(CreateList_L(p,n)=OVERFLOW) printf(分配失败，退出程序！);else */ do printf(n1:取出建立的链表中的某一个值n);printf(2: 在链表中插入某一个新值n);printf(3: 删除链表中的某一个值n);printf(0:结束！n);printf(请输入选择！n);scanf(%d,&select);switch (select)case 1:printf(从键盘输入取出的元素的位置i：n);scanf(%d,&i);GetElem_L(L,i,e);printf(取出的元素是:%dn,e);break;case 2:printf(从键盘输入插入元素的位置i和插入元素的值e,并用空格符分隔：n);scanf(%d%d,&i,&e);ListInsert_L(L,i,e);printf(插入后的所有元素是：n);s=L;while(s-next)s=s-next;printf(%3d,s-data);break;case 3:printf(从键盘输入删除的元素位序i：n);scanf(%d,&i);ListDelete_L(L,i,e);printf(删除后的所有元素是：n);s=L;while(s-next)s=s-next;printf(%3d,s-data);break;case 0:printf(操作结束！);break;default: printf(输入选择出错！n);/ end of switchwhile(select!=0); /end of while Destroy_L(p);/ end of main五、实验结果的分析与评价结果：1）顺序存储2）链式存储分析：（1）对实验的整体结果比较清楚，但具体细节或者说每一个关键的操作步骤还是不懂；（2）试着尝试抛弃书上的编程过程，建立属于自己的编程风格，了解必要编程知识；实验报告（3）实验名称栈和队列实验同组人姓名实验性质 基本操作 验证性 综合性 设计性实验日期2011年10月28日实验成绩教师评价：实验预习 实验操作 实验结果 实验报告 其它教师签名：一、 实验目的及要求1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。2）本实验训练的要点是“栈”和“队列”的观点；二、实验内容1) 利用栈，实现任一个表达式中的语法检查（如括号的匹配）。2） 编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）；三、主要设备及软件1) PC机2) Turbo C 2.0 或Visual C+四、实验流程、操作步骤或核心代码、算法片段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 0typedef 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,SElemType &e);#endif(二)功能函数（function.cpp）#include #include h1.h#include stdio.hStatus 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.base); 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) return 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.hmain() SqStack S; SElemType elem; char e,a20; int i=0; int flag=1; if( InitStack(S) printf(空间已经准备好!n); else printf(空间不足!n); printf(n请输入括号 (=20个)并且以 # 结束:n); do scanf(%c,&e); ai=e; i+; while(e!=#); i=0;e=ai; while(e!=#&flag) switch(e)case (: Push(S,e); break;case : Push(S,e);break;case : Push(S,e);break; case ):if(!StackEmpty(S)Pop(S,e); if(e!=()flag=0;else flag=0;break;case : if(!StackEmpty(S)Pop(S,e);if(e!=) flag=0;else flag=0;break;case :if(!StackEmpty(S) Pop(S,e);if(e!=) flag=0;else flag=0;break;i+;e=ai; if(!StackEmpty(S) flag=0; if(flag) printf(括号匹配!n); else printf(括号不匹配!n); /*if(DestroyStack(S) printf(这个栈已经摧毁!n); else printf(摧毁失败!n);*/ printf(n按任何键继续!n); 2)队列存储1.链式存储队列（一）H1.h(头文件)#include#include#include#define OK 1#define ERROR 0#define OVERFLOW 0typedef struct QNodeint data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;extern int InitQueue(LinkQueue &Q);extern void QueueEmpty(LinkQueue Q);extern void EnQueue(LinkQueue &Q,int e);extern int EnnQueue(LinkQueue &Q,int e);extern void DeQueue(LinkQueue &Q);extern void GetHead(LinkQueue &Q);extern void OutQueue(LinkQueue &Q);extern void LengthQueue(LinkQueue &Q);(二)功能函数（function.cpp）#include #include h1.h#include stdio.hint InitQueue(LinkQueue &Q)Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode);if(!Q.rear)exit(OVERFLOW);Q.front-next=NULL;return OK;void QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)printf(该链队为空:);elseprintf(该链队不为空:);void EnQueue(LinkQueue &Q,int e)QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)printf(error);p-data=e;Q.rear-next=p;Q.rear=p;printf(元素%d入队成功,e);int EnnQueue(LinkQueue &Q,int e)QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)return ERROR;p-data=e;Q.rear-next=p;Q.rear=p; return OK;void DeQueue(LinkQueue &Q)QueuePtr p;if(Q.front=Q.rear)printf(该链队为空);p=Q.front-next;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);printf(队首元素删除成功);void GetHead(LinkQueue &Q)QueuePtr p;if(Q.front=Q.rear)printf(该链队为空);p=Q.front-next;printf(队首元素为:%d,p-data);void OutQueue(LinkQueue &Q)QueuePtr p;if(Q.front=Q.rear)printf(该链队为空);p=Q.front-next;while(p!=Q.rear-next)printf(%d,p-data);p=p-next;void LengthQueue(LinkQueue &Q)int f=0;QueuePtr p;if(Q.front=Q.rear)printf(该队列的长度是:%d,f);elsep=Q.front-next;while(p!=Q.rear-next)p=p-next;f+; printf(该队列的长度是:%d,f); （三）主函数（main.cpp）#include #include h1.h#include stdio.hvoid main()system(cls);int flag=1,i;LinkQueue Q;InitQueue(Q);printf(*链队列功能菜单*n);printf(1:初始化链队列, 2:判断链队列是否为空, 3:进入队列, 4:取出队首元素n);printf(5:输出该队列的所有元素,6:输出该队列的长度, 7:结束程序, 8:清屏n);while(flag)printf(n请输入操作符:);scanf(%d,&i);switch(i)case 1:int e,n,k;printf(请输入队列的长度:);scanf(%d,&n);printf(请输入队列的元素:);for(e=1;e=n;e+)scanf(%d,&k);EnnQueue(Q,k);printf(初始化链队成功.n);break;case 2: QueueEmpty(Q); printf(n);break;case 3:int j;printf(请输入要进入队列的元素:);scanf(%d,&j);EnQ