《数据结构》实验指导

1、数据 结 构 实 验指 导 数 据 结 构实验指导南昌大学计算机系2011年3月前 言数据结构是计算机程序设计的重要理论技术基础，不仅是计算机学科的核心课程，而且己成为其它理工专业的热门选修课程。数据结构课程主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现，其教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，但由于这门课程相对抽象且内容复杂，因此，在数据结构的整个教学过程中，辅助课堂教学的实验非常有助于帮助学生学好这门课程，培养学生独立思考和解决问题的能力，锻炼学生的动手能力，希望能对我校的数据结构教学工作有所帮助。目 录实验1：C+ 语言基础练习2实验2：线性表及

2、其应用2实验3：栈和队列2实验4：串及其应用2实验5：数组2实验6：二叉树及其应用2实验7：图的应用2实验8：查找、排序2附录：实验报告格式2数据结构实验指导书实验1：C+ 语言基础练习一、实验目的对C+语言的复习，增强学生对结构体数组和指针的学习，尤以结构体的应用和指针的操作, 还有C+中类作为重点。二、问题描述1、 构造一个学生结构体数组，成员包括学号，姓名，四门成绩，以及平均成绩；2、 从键盘上输入学生的学号，姓名和四门成绩；3、 找出学生中考试没有通过的学生姓名并输出；找出考试在90分以上的学生并输出。三、实验要求1、 要求用链表存储学生的记录，并设计出输入和查找的基本操作算法。2、

3、在实验过程中，分析算法的时间复杂度和空间复杂度进行分析。 四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境 五、实验步骤1、用所选择的语言实现算法;3、 测试程序,并对算法进行时间和空间复杂度分析。六、实验报告要求实验报告应包括以下几个部分：1、 问题描述；2、 测试结果的分析与讨论，在测试过程中遇到的主要问题及采取的解决措施。3、 设计与实现过程中的体会，进一步的改进设想。4、 实现算法的程序清单，应有足够的注释。【算法实现】#define m 4 /*每个学生所学习课程数*/#define N

4、ULL 0typedef struct stnode int id; /*学号*/ char name16; /*姓名*/ int class4; /*所有课程成绩分别存储在class0,class1,class2,中*/ float ave; /*学生个人所有课程的平均成绩*/ struct stnode *next; /*指针域*/ students; students *head; /*head 为指向学生单链表的头指针，且为全局变量*/ int n; /*参加成绩管理的班上的学生个数*/ average() /*求每门课程的平均成绩的函数*/ int i,j; /*i为课程数，j为学生

5、数*/ float sum,aver; students *p; printf("Class Average resultn"); printf("*Class*Class Average*n"); for(i=0;i<m;i+) /*分别求出所有课程的平均分，循环次数为所有课程的数目*/ j=0; sum=0; p=head; while(p->next) /*求某一门课程的所有学生的得分总和*/ sum=sum+p->classi; p=p->next; j+; aver=sum/j; /*求某一门课程的平均分*/ print

6、f(" Class%d %16.2fn",i+1,aver); printf("*nn"); nopass() /*找含有课程不及格的学生，如有则输出它的学号、姓名、所有课程成绩、它的所有课程的平均分*/ int i,j; students *p; p=head; /*从第1个结点开始查找*/ printf("NO Pass resultn"); /*输入不格的结果*/ printf("*ID*Name*Class*Average*n"); while(p->next) /*最后一个结点无数据，不用输出*/

7、i=0; while(i<m) if(p->classi<60) printf("%8d%10s",p->id,p->name); /*输出不及格学生的学号、姓名*/ for(i=0;i<m;i+) /*输出不及格学生的所有课程成绩*/ printf("%6d",p->classi); printf("%8.2fn",p->ave); break; else i+; /*查找该同学的下一门课程*/ p=p->next; /*查找下一个同学*/ printf("*nn&qu

8、ot;); over90( ) /*查找所有课程个人平均分在90分以上（包含90分）的学生，如有则输出该学生的学号*/ students *p; p=head; /*从表头开始查找*/ while(p->next) /*直到倒数第二个结点为止 ，倒数第一个结点数据*/ if(p->ave>=90.0) /*找到则输出该学生的学号*/ printf("n"); printf("average over 90 its id is %dn",p->id); p=p->next; else /*否则查找下一个结点*/ p=p->

9、;next; main() students *p,*q; int i,j; float sum; clrscr(); printf("please student num!n"); scanf("%d",&n); /*n为学生个数*/ head=(students *)malloc(sizeof(students); q=head; for(i=0;i<n;i+) /*创建单链表*/ printf("input student%d its ID,namen",i+1); p=q; scanf("%dn&quo

10、t;,&p->id); /*输入学生的学号*/ scanf("%s",&p->name); /*输入学生姓名*/ printf("n"); printf("input student%i its scoren",i+1); for(j=0;j<m;j+) /*输入每个学生的所课程的成绩*/ scanf("%d",&p->classj); q=(students *)malloc(sizeof(students); q->next=NULL; p->next

11、=q; p=head; while(p->next) /*求每个学生个人所有课程的平均成绩*/ sum=0; for(j=0;j<m;j+) sum=sum+p->classj; p->ave=sum/m; p=p->next; average(); nopass(); over90();实验2：线性表及其应用一、实验目的帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。二、问题描述1、 构造一个空的线性表L。2、 在线性表L的第i个元素之前插入新的元素e；3、 在线性表L中删除第i个元素，并用e返回其值。三、实验要求1

12、、 分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。2、 在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。 四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境 五、实验步骤 1、用学生选择的语言，设计出线性表的顺序和链表存储结构; 2、设计出这两种存储结构下的线性表的插入、删除算法;4、 用所选择的语言实现算法;5、 测试程序,并对不同存储结构下的算法分析。六、实验报告要求实验报告应包括以下几个部分：1、 问题描述；2、 设计

13、两种存储结构与核心算法描述；3、 测试结果的分析与讨论，在测试过程中遇到的主要问题及采取的解决措施。4、 设计与实现过程中的体会，进一步的改进设想。5、 实现算法的程序清单，应有足够的注释。七、思考题1、 如何设计和实现基本线性表在两种存储结构下就地逆置算法？2.1 实现基本线性表的运算【算法实现】#define null 0typedef int ElemType;typedef struct node ElemType data; /*数据域*/ struct node *next; /*指针域*/Lnode; /*定义基本线性表的结点类型*/Lnode *head; /*定义指向基本线性

14、表的表头指针为全局变量*/ int length (Lnode *p) /*求指针p指向的基本线性表的长度*/ int n=0; /*结点位置计数器*/ Lnode *q=p; /*临时指针q*/ while (q!=null) /*当基本线性表不空时，统计基本线性表中的结点数*/ n+; q=q->next; return(n); /*返回统计的结点数*/ElemType get(Lnode *p,int i) /*求指针p指向的基本线性表中的第i个结点的值*/ int j=1; /*查找结点位置的计数器*/ Lnode *q=p; /*定义临时指针 q*/ while (j<i

15、&&q!=null) /*查找结点i是否存在*/ q=q->next; j+; if(q!=null) /*如果存在，则返回其数据域的值*/ return(q->data); else /*否则，输出“位置参数不正确”*/ printf("位置参数不正确!n");int locate(Lnode *p,ElemType x) /*求指针p指向的基本线性表中的数据元素x的位置序号*/ int n=0; /*结点位置计数器*/ Lnode *q=p; /*定义临时指针 q*/ while (q!=null&&q->data!=x

16、) /*在基本线性表中查找数据元素x的位置*/ q=q->next; n+; if(q=null) /*如果不存在，则返回-1*/ return(-1); else /*否则返回结点的位置序号*/ return(n+1);void insert(ElemType x,int i) /*在基本线性表的位置i,插入数据元素x*/ int j=1; /*结点位置计数器*/ Lnode *s,*q; /*定义临时指针变量p, q*/ s=(Lnode *)malloc(sizeof(Lnode); /*生成新结点*/ s->data=x; /*并将新结点的数据域置为x*/ q=head;

17、if(i=1) /*如果插入位置是1，则将新结点插入到表头*/ s->next=q; head=s; else /*否则，查找插入位置*/ while(j<i-1)&&(q->next!=null) q=q->next; j+; if(j=i-1) /*将新结点插入到位置i*/ s->next=q->next; q->next=s; else /*插入位置不存在*/ printf("位置参数不正确!n"); void delete(Lnode *p,int i) /*将指针p指向的基本线性表中的位置i的数据元素删除*

18、/ int j=1; /*结点位置计数器*/ Lnode *q=p,*t; if(i=1) /*如果位置序号为1，则将基本线性表的第1个数据元素结点删除*/ t=q; p=q->next; else /*否则从表头查找相应的位置序号i*/ while(j<i-1&&q->next!=null) q=q->next; j+; if(q->next!=null&&j=i-1) /*如果找到位置i，则将该位置的结点删除*/ t=q->next; q->next=t->next; else /*否则位置i不存在*/ pri

19、ntf("位置参数不正确!n"); if(t!=null) free(t);void display(Lnode *p) /*将指针p指向的基本线性表输出*/ Lnode *q; q=p; printf("单链表显示: "); if(q=null) printf("链表为空!"); else if (q->next=null) /*如果基本线性表只有单个结点，则将其数据域输出*/ printf("%dn",q->data); else /*否则，逐个输出所有结点的数据域*/ while(q->ne

20、xt!=null) printf("%d->",q->data); q=q->next; printf("%d",q->data); printf("n");main() Lnode *q; int d,i,n,select,k,flag=1; clrscr(); head=null; printf("请输入数据长度: "); scanf("%d",&n); for(i=1;i<=n;i+) printf("将数据插入到单链表中: ");

21、 scanf("%d",&d); insert(d,i); display(head); printf("n"); while(flag) printf("1- 求长度 n"); printf("2- 取结点 n"); printf("3- 求值查找 n"); printf("4- 增加结点 n"); printf("5- 删除结点 n"); printf("6- 退出 n"); printf("input your

22、select: "); scanf("%d",&select); switch(select) case 1: d=length(head); printf("n单链表的长度为：%d ",d); printf("n"); display(head); printf("n"); break; case 2: printf("n请输入取得结点的位置: "); scanf("%d",&d); k=get(head,d); printf("%dn&

23、quot;,k); display(head); printf("n"); break; case 3: printf("n请输入要查找的数据: "); scanf("%d",&d); k=locate(head,d); printf("%dn",k); display(head); printf("n"); break; case 4: printf("n请输入增加结点的位置："); scanf("%d",&k); printf(&quo

24、t;n请输入增加结点的数据："); scanf("%d",&d); insert(d,k); display(head); printf("n"); break; case 5: printf("n请输入删除结点的位置: "); scanf("%d",&d); delete(head,d); printf("n"); display(head); printf("n"); break; case 6: flag=0; break; 2.2 基本线性表

25、的就地逆置【算法实现】（1）顺序结构基本线性表的就地逆置算法实现。#define max 20 /*基本线性表中的最多元素个数为20*/typedef int datatype;typedef struct node datatype datamax; int length;sqlist; /*将基本线性表类型定义为sqlist 类型*/ sqlist p1; /*定义p1为基本线性表类型*/void reverlist() /*将顺序存储结构的基本线性表就地逆置*/ int i; for(i=0;i<p1.length/2;i+) /*数据元素交换的次数为p1.length/2*/ p

26、1.datap1.length+1=p1.datai; /*将第length+1个存储单元作为中间存储单元*/ p1.datai=p1.datap1.length-1-i; /*将相应位置的元素前后交换*/ p1.datap1.length-1-i=p1.datap1.length+1; main() int j; clrscr(); p1.length=0; printf("please input 10 datan"); for(j=0;j<10;j+) /*创建初始基本线性表*/ scanf("%d",&p1.dataj); p1.l

27、ength+; printf("the sqlist is:n"); for(j=0;j<10;j+) /*将创建成功的基本线性表输出*/ printf("%4d",p1.dataj); printf("nn"); reverlist( ); /*将基本线性表逆置*/ printf("the result is:nn"); for(j=0;j<10;j+) /*将逆置后的基本线性表输出*/ printf("%4d",p1.dataj);（2）链式存储结构基本线性表的就地逆置算法实现。

28、#include <stdio.h>#define null 0#define LEN sizeof(struct stu)#define elemtype int typedef struct stu /*定义结点结构体类型*/ elemtype data; /*数据域*/ struct stu *next; /*指针域*/Llist;Llist *creatlist(int n) /*创建一个含 n 个结点的链表*/ Llist *head=NULL, *p; int i; for(i=0;i<n;i+) /*创建有n个结点的链式基本线性表*/ p=(Llist *)ma

29、lloc(LEN); /*生成新结点*/ printf("record %dn",i+1); printf("input data:"); scanf("%d",&p->data); /*对新结点的数据域赋值*/ if(i=0) /*创建链式基本线性表的头结点*/ head=p; head->next=null; else /*创建链式基本线性表中的其他结点*/ p->next=head; head=p; return(head);void printlist ( Llist *head) /*输出链表中各结

30、点信息*/ Llist *p; p=head; printf("基本线性表为： n"); while(p!=NULL) printf("%d->",p->data); p=p->next; Llist *reverlist(Llist *head) /*逆置链式基本线性表*/ Llist *p,*q; if(head&&head->next) /*当链式基本线性表中有两个以上的结点时，进行逆置*/ p=head; /*指针p指向指针head所指向的链式基本线性表*/ q=p->next; /*指针q指向链式基

31、本线性表的第2个结点*/ p->next=null; /*在第1个结点与第2个结点间断开，原来的链式基本线性表变成两个链式基本线性表，分别由指针head和指针q指向*/ while(q) /*每次将指针q指向链表的第1个结点，插入到指针head指向链式基本线性表的最前面*/ p=q; q=q->next; p->next=head; head=p; return(head);main() Llist *head=NULL,*p; int n,num; clrscr(); printf("input number of node:"); /*输入链式基本线性

32、表的结点数*/ scanf("%d",&n); head=creatlist(n); /*创建链式基本线性表*/ printf("nn逆置前"); printlist(head); /*输出创建成功的链式基本线性表*/ printf("n"); p=reverlist(head); /*将链式基本线性表逆置*/ printf("nn逆置后"); printlist(p); /*输出逆置后的线性表*/实验3：栈和队列一、实验目的深入了解栈和队列的特性，学会在实际问题下灵活运用它们。二、问题描述表达式求值运算是

33、实现程序设计语言的基本问题之一，也是栈应用的一个典型例子。设计并演示用算符优先级对算术表达式的求解过程。三、实验要求1、算法优先级别如下：'+', '-', '*', '/', '(', ')', '#''+' '>', '>', '<', '<', '<', '>', '>','-' '&g

34、t;', '>', '<', '<', '<', '>', '>','*' '>', '>', '>', '>', '<', '>', '>','/' '>', '>', '>', '>'

35、;, '<', '>', '>','(' '<', '<', '<', '<', '<', '=', ' ',')' '>', '>', '>', '>', ' ', '>', '>','#' &

36、#39;<', '<', '<', '<', '<', ' ', '='2、以字符序列的形式从终端输入语法正确、不含变量的算术表达式，利用给出的算符优先级关系，实现对算术四则混合运算的求解过程。 四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境 五、实验步骤1、 根据给出的算符优先级，设置运算符栈和运算数栈；2、 在读入表达式的同时，完成运算符和运算数的识别处理，并

37、将运算数的字符序列形式转换成整数形式，并进行相应的运算；3、 调试程序，检查输出结果；4、 实验小结。 六、测试数据1. 输入数据：1+（20+4）/（4-1） 正确结果：92. 输入数据：2*9-6-（20+4）/（4-1） 正确结果：4七、实验报告要求实验报告应包括以下几个部分：1、问题描述；2、算法的设计描述；3、测试结果的分析与讨论。4、设计与实现过程中的体会，进一步的改进设想。实现算法的程序清单，应有足够的注释。#include<iostream>#include<stdio.h>#include<stdlib.h>#include<

38、;malloc.h>#define STACK_INT_SIZE 100#define STACKINCREMENT 10using namespace std;char a7='+','-','*','/','(',')','#'char b77='>','>','<','<','<','>','>','>&#

39、39;,'>','<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>&#

40、39;,'<','<','<','<','<','=',' ','>','>','>','>',' ','>','>','<','<','<','<','<',' ','=&#

41、39;typedef structchar *base;char *top;int stacksize;SqStack;int InitStack(SqStack &S)S.base=(char *)malloc(STACK_INT_SIZE*sizeof(char);if(!S.base)return 0;S.top=S.base;S.stacksize=STACK_INT_SIZE;return 1;char GetTop(SqStack S)char e;if(S.top=S.base)return 0; e= *(S.top-1);return e;int Push(SqSta

42、ck &S,char e)if(S.top-S.base>=S.stacksize)S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base)return 0;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+ =e;return 1;char Pop(SqStack &S)char e;if(S.top=S.base)return 0;e= * -S.top;return e;int In(ch

43、ar c)int i;for(i=0;i<=6;i+)if(ai=c)return 1;return 0;char Precede(char c1,char c2)int i=0;int j=0;while(ai!=c1)i+;while(aj!=c2)j+;return bij;char Operate(char x,char c,char y)int i=0;int m,n;char d;m=x-'0'n=y-'0'while(c!=ai)i+;switch(ai)case'+':d=(m+n)+'0'break;cas

44、e'-':d=(m-n)+'0'break;case'*':d=m*n+'0'break;case'/':d=m/n+'0'break;return d;int main()SqStack OPTR,OPND;char c;char theta;char x1,x2;InitStack(OPTR);Push(OPTR,'#');InitStack(OPND);c=cin.get();while(c!='#'|GetTop(OPTR)!='#')if(!

45、In(c)Push(OPND,c);c=cin.get();elseswitch(Precede(GetTop(OPTR),c)case'<':Push(OPTR,c);c=cin.get();break;case'=':Pop(OPTR);c=cin.get();break;case'>':theta=Pop(OPTR);x2=Pop(OPND);x1=Pop(OPND);Push(OPND,Operate(x1,theta,x2);break;cout<<(int(GetTop(OPND)-'0')&l

46、t;<endl;return 0;八、思考题1、 试着扩充运算符集，如增加乘方、单目加等。2、 如何增强计数器的功能和仿真界面。3、 如何实现前缀算术表达式、后缀表达式的求解？实验4：串及其应用一、实验目的掌握串类型的实现方法和文本模式匹配方法，熟悉一般文字处理软件的设计方法。二、问题描述全屏幕文本编辑器通过终端对文本文件进行创建、插入、删除、修改、存储等操作。用户可完成对文本的插入、删除、修改等功能。三、实验要求1、 对光标实现如下操作：上、下、左、右移动一个字符位置；向前、后翻页；光标移至文件首、尾；光标移至本行首、尾。2、 实现基本编辑命令：I-在当前光标前插入内容，按ESC结束F

47、-在当前光标后插入内容，按ESC结束D-删除光标所在行ND-删除光标位置开始的n行N-删除光标上的字符W-将修改后的文本保存下来Q-退出编辑状态。 四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境 五、实验步骤1、 在内存开辟可容纳80行大小的编辑工作区和buffer 的修改缓冲区。2、 要求用户输入编辑文件名，对读入的文件建立相应的页表和行表，在文本编辑程序中设立页指针、行指针、字符指针，分别指示当前操作的页、行、字符。 3、执行插入、删除、修改操作时，将本次操作内容放到缓冲区；4、操作确定后，

48、将修改后的文本存到文件中。 六、测试数据 自行设定。七、实验报告要求实验报告应包括以下几个部分：1、问题描述；2、算法的设计描述；3、测试结果的分析与讨论。4、设计与实现过程中的体会，进一步的改进设想。5、实验总结。八、思考题1、 对命令格式非法等错误做严格检查和适当处理。2、 扩充编辑操作，如对某行进行串替换？实验5：数组一、实验目的深入研究数组的存储表示和实现技术，着重掌握对稀疏矩阵的表示方法及其运算的实现。二、问题描述稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行存储和计算可以大大节省存储空间，提高效率。通过对稀疏矩阵的存储表示，实现矩阵的基本操作。三、实验要求1、 要求

49、矩阵的输入形式采用三元组表示，以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵。2、 设计矩阵的逆置算法，实现矩阵的逆置。3、 实现两个稀疏矩阵的相加、相减和相乘等运算。4、 要求运算结果的矩阵则以通常的阵列形式出现。 四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境 五、实验步骤1、 首先应输入矩阵的行数和列数、并判别给出的两个矩阵的行、列数对于所要求的运算是否相匹配；2、 以三元组的形式输入矩阵；3、 #include<stdio.h>4、 typedef struct5、 6、

50、int i,j;7、 int elem;8、 triple;9、10、 typedef struct 11、 12、 triple data10;13、 int mu,nu,tu;14、 tsm;15、 void main()16、 17、 int c,i=1;18、 triple a1;19、 tsm b1;20、 21、 printf("i j vn");22、 for(int a=1;a<b1.mu;a+)23、 for(int b=1;b<b1.nu;b+)24、 for(c=1;c<=b1.tu;c+)25、 26、 if(b1.datac.i=

51、a&&b1.datac.j=b)27、 printf("%6d %6d %6d n",a+1,b+1,b1.datac.elem);28、 29、 getchar();30、 31、 void input(triple &a1,tsm &b1)32、 33、34、 printf("请?输º?º?入¨?¨¡ì?系¦Ì¦Ì§?数ºyºy矩?阵¨®¨¡ì

52、4;行DD数ºyºy：êoê§oon");35、 scanf("%d",&b1.mu);36、 printf("请?输º?º?入¨?¨¡ì?系¦Ì¦Ì§?数ºyºy矩?阵¨®¨¡ì®列¢D¢¨¦D数ºyºy：êoê§oon

53、");37、 scanf("%d",&b1.nu);38、 printf("请?输º?º?入¨?¨¡ì?系¦Ì¦Ì§?数ºyºy矩?阵¨®¨¡ì®不?为aa零¢?¢¨¦?元aa个?数ºyºy（ꡧê§o¡§¨¬不?大䨮䨡ì®于®¨²®¨¡ì²10）ê?ê§o?：êoê§oon");39、 scanf("%d",&b1.tu);40、 c=b1.tu;41、 while(c-)4