《数据结构》课程实验指导书

1、数学与计算机学院数据结构课程实验指导书适用专业: 计算机科学与技术目 录第二部分 实验指导3实验一 线性表的插入和删除3实验二 线性结构（二）栈和队列13实验三 查找算法18实验四 排序算法25实验五 二叉树的操作27实验六 图的操作31第一部分 绪论本指导书是根据数据结构课程实验教学大纲编写的，适用于计算机科学与技术专业。一、 本课程实验的作用与任务（楷体小三号）该课程实验的作用与任务是让同学们掌握计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法。数据结构的学习不但需要有扎实的理论学习过程，合理和有效的实验也是必不可少的。通过数据结构实验课程的教学和

2、实际操作，需要学生总体上把握以下三个方面：其一就是让学生学会分析研究计算机加工的数据对象的特性，以便为数据选择适当的物理结构和逻辑结构；其二，根据结构，选择适当的算法，并初步掌握算法的时间分析和空间分析；其三，学习复杂的程序设计。二、 本课程实验的基础知识依据理论课的讲授情况，本书的实验安排以表（包括有序表、链表等），树，图三个主要的数据结构为重点。 本书的第一个实验是表的实验，有序表、链表为重中之重，必须掌握。第五个实验为树的实验，树也是数据结构课中的一个重点，要认真掌握。应当以二叉树的建立和遍历为重点。图论是近年来兴起的新兴学科，第六个实验为图的实验：邻接表的建立与图的遍历。建立邻接表，应

3、当与链表的实验相比较，并且应当站在数据结构的角度来考虑两个实验的区别、联系。图的遍历，可以和二叉树的遍历相比较。第三个和第四个的实验是查找和排序的实验。就算法而言，排序就是使关键字有序；就数据结构而论，排序还应关注数据的逻辑结构和物理结构，即排序的对象是记录，只有这样理解，才能真正的理解数据结构这门课。三、本课程实验教学项目及其教学要求序号实验项目名称学时教学目标、要求1线性结构（线性表的插入和删除4掌握用Turbo C上机调试线性表的基本方法；掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。掌握握单链表的基本操作：插入、删除、查找等运算*2线

4、性结构（二）4掌握栈的基础知识、结构特点及应用；掌握队列的结构特点和基本操作3查找算法3掌握查找表的定义和存贮；掌握查找常用方法及过程；实现顺序查找、二分查找、二叉排序树查找等算法。4排序算法3掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。5二叉树的操作4进一步掌握指针变量、动态变量的含义；掌握二叉树的结构特征，以及各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算。6图的操作4掌握图的基本存储方法；掌握有关图的操作算法并用高

5、级语言实现；熟练掌握图的两种搜索路径的遍历方法。合计18注：有*号的表示是选开的实验，学生自由上机完成。第二部分 实验指导实验一 线性表的插入和删除一、 实验目的1. 掌握用Turbo C上机调试线性表的基本方法；2. 掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。3. 掌握握单链表的基本操作：插入、删除、查找等运算二、 实验要求1、顺序表要用函数creatlist()随机生成,用三个函数完成顺序表的插入，删除和按值查找。2、用四个函数实现单链表的建立、插入、删除和查找。3、保存和打印出程序的运行结果，并结合程序进行分析。4、打印出文件清单。

6、三、 实验原理线性表是最常用的而且也是最简单的一种数据结构，线性表是N个数据元素的有限序列。例如26个英文元素的字母表：（A，B，C，D，）。其数据结构的描述为：Linear_list=(D,R)其中：D=ai|ai属于D0,i=1,2,3,R=N,N=|i=2,3,4,。本实验是以数组的形式把有序表存放在计算机内存的一个连续的区域内，这样便有：LOC(ai+1)=LOC(ai)+m。其中m是存放每个元素所占的内存字数。LOC(ai)=LO+m(i-1)。其中LO是ai的地址，即首地址。四、 主要仪器及耗材计算机，Turbo C 2.0 软件。五、 实验内容与步骤程序1：线性表基本操作的实现这

7、个程序中演示了顺序表的创建、插入、删除和查找，请修改并完成。 程序如下：#include #include /*顺序表的定义：*/#define ListSize 100typedef structint dataListSize;/*向量data用于存放表结点*/int length;/*当前的表长度*/SeqList;void main()void CreateList(SeqList *L,int n);void PrintList(SeqList *L,int n);int LocateList(SeqList *L,int x);void InsertList(SeqList *L,

8、int x,int i);void DeleteList(SeqList *L,int i); SeqList L;int i,x;int n=10;/*THE LENGTH OF LIST*/L.length=0;clrscr();CreateList(&L,n);/*CREAT THE LIST*/PrintList(&L,n);/*PRINT THE LIST*/printf(INPUT THE RESEARCH ELEMENT);scanf(%d,&x);i=LocateList(&L,x);printf(the research position is %dn,i);/*顺序表查找*

9、/printf(input the position of insert:n);scanf(%d,&i);printf(input the value of insertn);scanf(%d,&x);InsertList(&L,x,i);/*顺序表插入*/PrintList(&L,n);/*打印顺序表*/printf(input the position of deleten);scanf(%d,&i);DeleteList(&L,i);/*顺序表删除*/PrintList(&L,n);getch();/*打印顺序表*/*顺序表的建立：*/void CreateList(SeqList *L

10、,int n)int i;printf(please input n numbersn);for(i=1;idatai);L-length=n;/*顺序表的打印：*/void PrintList(SeqList *L,int n)int i;printf(the sqlist isn);for(i=1;idatai);/*顺序表的查找：*/int LocateList(SeqList *L,int x)int i;for(i=1;idatai)=x) return(i); else return(0);/*顺序表的插入：*/void InsertList(SeqList *L,int x,in

11、t i)int j;for(j=L-length;j=i;j-)L-dataj+1=L-dataj;L-datai=x;L-length+;/*顺序表的删除：*/void DeleteList(SeqList *L,int i) int j;for(j=i;jlength)-1;j+)L-dataj=L-dataj+1;程序2：单链表基本操作的实现这个程序中演示了单链表的创建、插入、删除和查找。程序如下： #includetypedef struct node int data; struct node *next; NODE;/*/NODE *Create()NODE *p,*head;in

12、t x;head=(NODE *)malloc(sizeof(NODE);head-next=NULL;printf(Input data,-1 to End!n);scanf(%d,&x);while(x!=-1) p=(NODE *)malloc(sizeof(NODE); p-data=x; p-next=head-next; head-next=p; scanf(%d,&x);return(head);/*/void Output(NODE *head) NODE *p; p=head; printf(Begin to dump the LinkList.n); while(p-nex

13、t!=NULL) printf(-%d,p-next-data); p=p-next; printf(nThe LinkList ended!n);/*/int Listlen(NODE *head) int i=0; NODE *p=head; while(p-next!=NULL) i+; p=p-next; return(i);/*/int Get(NODE *head,int i)int j=0;NODE *p=head;while(p-next&jnext;if(!p-next|ji) return(0);else return(p-data);/*/void Del(NODE *h

14、ead,int i)NODE *p=head;int j=0;while(p-next&jnext;if(!p-next|ji-1) printf(the position is wrongn);elsep-next=p-next-next;/*/void Ins(NODE *head,int i,int e)NODE *p=head,*q;int j=0;while(p-next&jnext;if(!p-next&ji-1) printf(Wrong positionn );else q=(NODE *)malloc(sizeof(NODE); q-data=e; q-next=p-next

15、; p-next=q;/*/main() NODE *head; int length; int i,element; clrscr(); head=Create(); Output(head); length=Listlen(head); printf(the length of the link is %dn,length); printf(input the order :n); scanf(%d,&i); element=Get(head,i); printf(the element of the order is %dn,element); printf(input the del

16、position n); scanf(%d,&i); Del(head,i); Output(head); printf(Input the insert posion and element:n); scanf(%d%d,&i,&element); Ins(head,i,element); Output(head); getch();六、 实验注意事项1 在编程的时候，要注意指针的使用。七、 思考题1 有序表，有哪些显著的特点和优点？2 分析实验指导书上的程序，以数据结构上的对有序表的类型定义来改写程序。实验二 线性结构（二）栈和队列一、 实验目的1、理解栈的基本概念和特点；2、理解顺序栈和

17、链栈存储结构的特点；3、掌握顺序栈存储结构的构造、取栈顶元素、入栈和出栈的基本操作算法；4、理解队列的基本概念和特点；5、掌握顺序队列和链队列存储结构的各自特点；6、掌握顺序队列存储结构的构造、取队头元素、入队和出队基本操作算法。二、 实验要求1、 要求掌握本实验的各个算法和程序。2、 要求独立完成并上机运行本程序。三、 实验原理从数据结构角度看，栈和队列是两种特殊的线性表。它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，即栈和队列是操作受限制的线性表，也可以将它们称为限定性的线性表结构。四、 主要仪器及耗材计算机，Turbo C 2.0 软件。五、实验内容与步骤 实验21 顺

18、序栈的建立，入栈和出栈#define n 5#include int Stackn+1;int top=-1;int pop(void);void push(int ch);void main(void)int i;int An=1,3,5,7,9;printf(Data before inversing:);for(i=0;in;i+)printf(%d ,Ai);printf(n);for(i=0;in;i+)push(Ai);for(i=0;in;i+)Ai=pop();printf(Data after inversinging:);for(i=0;in;i+)printf(%d ,A

19、i);printf(n);int pop(void)return Stacktop-;void push(int ch)Stack+top=ch;实验22 顺序队列的建立，入队和出队#define n 5#includeint cQueuen;int cfront=-1;int crear=-1;void addcq(int data);int delcq(void);int iscEmpty(void);int iscFull(void);void main(void)int i;int An=1,3,5,7,9;printf(Data input:);for(i=0;in;i+)print

20、f(%d ,Ai);addcq(Ai);addcq(11);printf(n);printf(Data output:);for(i=0;in;i+)printf(%d ,delcq();printf(n);void addcq(int data)if(iscFull()printf(cQueue is Full!n);elsecQueue+crear%n=data;int delcq(void)if(iscEmpty()printf(cQueue is Empty!n);return 0;elsereturn cQueue+cfront%n;int iscFull(void)if(cfron

21、t=(crear+1)%n)return 1;elsereturn 0;int iscEmpty(void)if(cfront=crear)return 1;elsereturn 0;六、 实验注意事项实验过程中注意队列中判断队满的条件。七、 思考题1. 如何建立一个循环队列，如何实现循环队列的基本的操作？实验三 查找算法一、 实验目的2. 理解查找表的概念；3. 理解关键字的概念；4. 熟练掌握顺序查找算法；5. 熟练掌握折半查找算法。二、 实验要求1、定义学生信息查找表记录结构；2、学生信息查找程序的主控程序设计；3、学生信息查找的功能函数设计；3、保存和打印出程序的运行结果，并结合程序进

22、行分析。4、打印出文件清单。三、 实验原理查找和排序是数据处理中使用频率极高的重要运算，几乎在任何一个计算机系统软件和应用软件中都会涉及到。我们把同一数据类型的数据元素构成的集合称为查找表，把查找表中某个可以标识一个数据元素的数据项的值称为关键字。当问题涉及的数据量大的时候，常常要求使用效率较高的查找方法，如折半查找法，这往往要求先对查找表中的记录进行排序。四、 主要仪器及耗材计算机，Turbo C 2.0 软件。五、实验内容与步骤 实验21 已知学生的信息数据项包括：学号、姓名、性别和年龄。定义学生信息查找表的记录结构。在学生信息查找表中实现对关键字学号进行顺序查找和折半查找。#includ

23、e#include#includetypedef struct student int num; char name20; char sex; int age; StuNODE; /*定义学生记录的结构StuNODE stu5=10101,Li Ling,M,18,10102,Zhang Fun,M,19,10103,Wang Min,F,20,10107,Li Mei,F,19,10105,Zhao Yun,M,20;/*顺序查找算法的定义*/ int seqSearch(StuNODE stu,int n,int key)int i=0;while(i=n)return -1;else r

24、eturn i;/*冒泡排序*/void BubbleSort(StuNODE stu,int n)int i,j;StuNODE temp;for(i=0;ii;j-) if(stuj.num stuj-1.num)temp.num =stuj.num;strcpy(,);temp.sex=stuj.sex;temp.age=stuj.age;stuj.num =stuj-1.num; strcpy(,);stuj.sex=stuj-1.sex;stuj.age=stuj.age; stuj-1.num =temp.

25、num; strcpy(,);stuj-1.sex=temp.sex;stuj-1.age=temp.age;/*折半查找*/int BinSearch(StuNODE stu,int n,int key)int low=0,high=n-1,mid,count=0;while(low key)high=mid-1;elselow=mid+1;return -1;/*主控函数*/void main()StuNODE *p;int n=5;int key,sResult;printf(NO. Name Sex agen);for(p=stu;pnum,p-

26、name,p-sex,p-age);printf(1、顺序查找：n);printf(请输入要查询的学生学号：n);scanf(%d,&key); sResult=seqSearch(stu,n,key); if(sResult0)printf(没有学号为%d的学生n,key);elseprintf(n学号为%d的学生为：n,key); printf(%-8d%-18s%4c%4dn,stusResult.num,stusR,stusResult.sex,stusResult.age);printf(2、按任意健，开始冒泡排序：n);printf(n初始序列：n); prin

27、tf(NO. Name Sex agen);for(p=stu;pnum,p-name,p-sex,p-age);BubbleSort(stu,n); printf(n冒泡排序后的结果序列为：n); printf(NO. Name Sex agen);for(p=stu;pnum,p-name,p-sex,p-age);printf(3、二分查找：n);printf(请输入要查询的学生的学号：n);scanf(%d,&key);sResult=BinSearch(stu,n,key);if(sResultdata); preorder(bt-lchild); preorder(bt-rchil

28、d); else if(g=2) printf(空树n); bitreptr *crt_bt() /*建立二叉树*/ bitreptr *bt; char ch; if(f=1) printf(输入根结点，#表示结束n); else printf(输入结点，#表示结束n); scanf(n%c,&ch); f=f+1; if(ch=#) bt=null; else bt=(bitreptr *)malloc(len); bt-data=ch; printf(%c 左孩子,bt-data); bt-lchild=crt_bt(); printf(%c 右孩子,bt-data); bt-rchil

29、d=crt_bt(); return(bt); main() f=1; g=1; bt=crt_bt(); preorder(bt); 六、 实验注意事项实验过程中注意递归的使用。七、 思考题1. 画出给出的各类型的数据示意图，理解为不同目的而建立的不同数据结构意义。2. 改写程序完成中、后序遍历。3. 考虑用非递归算法完成二叉树遍历。4完成其他的函数所定义的功能。实验六 图的操作一、 实验目的1掌握图的基本存储方法；2掌握有关图的操作算法并用高级语言实现；3熟练掌握图的两种搜索路径的遍历方法。二、 实验要求1 认真阅读和掌握本实验的算法 。2 上机将本算法实现。3 保存和打印出程序的运行结果

30、，并结合程序进行分析。4 按照你对图的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、 实验原理图，是一种比树和表要复杂得多的数据结构。在线性表中，数据元素之间只有线性关系，每一个数据元素只有一个直接前驱和直接后继；在树形结构之中，数据元素之间有着明显的层次关系，并且每上一层的数据元素可能和下一层的多个数据元素相关，但只能和上一层的一个数据元素相关；而在图形结构中，结点之间的关系可以是任意的。图中的任意结点之间的两个数据元素都可以相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学以及数学的其它分支里。图有多种存储方式

31、，邻接表是一链式存储结构。在邻接表中，对图中的每一个结点都建立一个单链表，第一个单链表表示依附于顶点VI的边。每一个结点有三个域组成，其邻接点域指示与顶点VI邻接的点图中的位置，链域指示下一条边或弧的结点，数据域存储和边或弧的相关信息，如权值等。每个链表附设一表头结点。如下图所示：邻接点域链域数据域数据域链域 表结点 头结点四、 主要仪器及耗材计算机，Turbo C 2.0软件。五、 实验内容与步骤以邻接矩阵和邻接表的方式存储连通图。然后分别用深度优先算法遍历邻接矩阵方式存储的图和邻接表方式存储的图。算法 如下：深度优先遍历的递归算法 （1）深度优先遍历算法 int visitedMaxVer

32、texNum； /访问标志向量是全局量void DFSTraverse(ALGraph *G) /深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同int i；for(i=0;in;i+)visitedi=FALSE； /标志向量初始化for(i=0;in；i+)if(!visitedi) /vi未访问过DFS(G，i)； /以vi为源点开始DFS搜索/DFSTraverse（2）邻接表表示的深度优先搜索算法void DFS(ALGraph *G，int i) /以vi为出发点对邻接表表示的图G进行深度优先搜索EdgeNode *p；printf(visit vertex：

33、c，G-adjlisti.vertex)；/访问顶点vivisitedi=TRUE； /标记vi已访问p=G-adjlisti.firstedge； /取vi边表的头指针while(p)/依次搜索vi的邻接点vj，这里j=p-adjvexif (!visitedp-adjvex)/若vi尚未被访问DFS(G，p-adjvex);/则以Vj为出发点向纵深搜索p=p-next； /找vi的下一邻接点/DFS#define MaxVertexNum 5#define m 5#define NULL 0typedef struct node int adjvex;struct node *next;J

34、D;typedef struct tnode int vexdata; JD *firstarc;TD;typedef structTD agm;int n;ALGRAPH;void DFS(ALGRAPH *G,int i);void creat(ALGRAPH *G)int i,m1,j;JD *p,*p1;printf(please input the number of graphn);scanf(%d,&G-n);for(i=0;in;i+)printf(please input the info of node %d,i);scanf(%d,&G-agi.vexdata);prin

35、tf(please input the number of arcs which adj to %d,i);scanf(%d,&m1);printf(please input the adjvex position of the first arcn);p=(JD *)malloc(sizeof(JD);scanf(%d,&p-adjvex);p-next=NULL;G-agi.firstarc=p;p1=p;for(j=2 ;jadjvex);p-next=NULL;p1-next=p;p1=p;int visitedMaxVertexNum;void DFSTraverse(ALGRAPH

36、 *G)int i;for(i=0;in;i+)visitedi=0;for(i=0;in;i+)if(!visitedi)DFS(G,i);/*DFSTraverse */void DFS(ALGRAPH *G,int i)JD *p;printf(visit vertex:%d-,G-agi.vexdata);visitedi=1; /*标记vi已访问 */p=G-agi.firstarc; /*取vi边表的头指针*/while(p)/*依次搜索vi的邻接点vj，这里j=p-adjvex*/if (!visitedp-adjvex)/*若vi尚未被访问 */DFS(G,p-adjvex);

37、/*则以Vj为出发点向纵深搜索 */p=p-next;/*DFS */main() ALGRAPH *G;printf(下面以临接表存储一个图；n); creat(G);printf(下面以深度优先遍历该图 n);DFSTraverse(G);getch();六、 实验注意事项在实验的过程中要注意以邻接矩阵和邻接表的方式存储连通图的过程。七、 思考题在本例程序邻接表这种数据结构上，添加关于结点及弧的有关信息，将本例程序完善成有实际应用价值的邻接表建立程序。第三部分 实验参考书目及网站一、实验教学参考书目：数据结构实验与实训教程清华大学出版社 出版；宁正元、王秀丽 编著；第一版Dr3uhd3uhd3u断喉弩好多年课代表卡不