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

数学与计算机学院数据结构课程实验指导书适用专业: 计算机科学与技术目 录第二部分 实验指导3实验一 线性表的插入和删除3实验二 线性结构（二）栈和队列13实验三 查找算法18实验四 排序算法25实验五 二叉树的操作27实验六 图的操作31第一部分 绪论本指导书是根据数据结构课程实验教学大纲编写的，适用于计算机科学与技术专业。一、 本课程实验的作用与任务（楷体小三号）该课程实验的作用与任务是让同学们掌握计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法。数据结构的学习不但需要有扎实的理论学习过程，合理和有效的实验也是必不可少的。通过数据结构实验课程的教学和实际操作，需要学生总体上把握以下三个方面：其一就是让学生学会分析研究计算机加工的数据对象的特性，以便为数据选择适当的物理结构和逻辑结构；其二，根据结构，选择适当的算法，并初步掌握算法的时间分析和空间分析；其三，学习复杂的程序设计。二、 本课程实验的基础知识依据理论课的讲授情况，本书的实验安排以表（包括有序表、链表等），树，图三个主要的数据结构为重点。 本书的第一个实验是表的实验，有序表、链表为重中之重，必须掌握。第五个实验为树的实验，树也是数据结构课中的一个重点，要认真掌握。应当以二叉树的建立和遍历为重点。图论是近年来兴起的新兴学科，第六个实验为图的实验：邻接表的建立与图的遍历。建立邻接表，应当与链表的实验相比较，并且应当站在数据结构的角度来考虑两个实验的区别、联系。图的遍历，可以和二叉树的遍历相比较。第三个和第四个的实验是查找和排序的实验。就算法而言，排序就是使关键字有序；就数据结构而论，排序还应关注数据的逻辑结构和物理结构，即排序的对象是记录，只有这样理解，才能真正的理解数据结构这门课。三、本课程实验教学项目及其教学要求序号实验项目名称学时教学目标、要求1线性结构（线性表的插入和删除4掌握用Turbo C上机调试线性表的基本方法；掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。掌握握单链表的基本操作：插入、删除、查找等运算*2线性结构（二）4掌握栈的基础知识、结构特点及应用；掌握队列的结构特点和基本操作3查找算法3掌握查找表的定义和存贮；掌握查找常用方法及过程；实现顺序查找、二分查找、二叉排序树查找等算法。4排序算法3掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。5二叉树的操作4进一步掌握指针变量、动态变量的含义；掌握二叉树的结构特征，以及各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算。6图的操作4掌握图的基本存储方法；掌握有关图的操作算法并用高级语言实现；熟练掌握图的两种搜索路径的遍历方法。合计18注：有*号的表示是选开的实验，学生自由上机完成。第 38 页第二部分 实验指导实验一 线性表的插入和删除一、 实验目的1. 掌握用Turbo C上机调试线性表的基本方法；2. 掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。3. 掌握握单链表的基本操作：插入、删除、查找等运算二、 实验要求1、顺序表要用函数creatlist()随机生成,用三个函数完成顺序表的插入，删除和按值查找。2、用四个函数实现单链表的建立、插入、删除和查找。3、保存和打印出程序的运行结果，并结合程序进行分析。4、打印出文件清单。三、 实验原理线性表是最常用的而且也是最简单的一种数据结构，线性表是N个数据元素的有限序列。例如26个英文元素的字母表：（A，B，C，D，···）。其数据结构的描述为：Linear_list=(D,R)其中：D=ai|ai属于D0,i=1,2,3,···R=N,N=<ai-1,ai>|i=2,3,4,···。本实验是以数组的形式把有序表存放在计算机内存的一个连续的区域内，这样便有：LOC(ai+1)=LOC(ai)+m。其中m是存放每个元素所占的内存字数。LOC(ai)=LO+m·(i-1)。其中LO是ai的地址，即首地址。四、 主要仪器及耗材计算机，Turbo C 2.0 软件。五、 实验内容与步骤程序1：线性表基本操作的实现这个程序中演示了顺序表的创建、插入、删除和查找，请修改并完成。 程序如下：#include <stdio.h>#include <stdlib.h>/*顺序表的定义：*/#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,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);/*顺序表查找*/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,int n)int i;printf("please input n numbersn");for(i=1;i<=n;i+)scanf("%d",&L->datai);L->length=n;/*顺序表的打印：*/void PrintList(SeqList *L,int n)int i;printf("the sqlist isn");for(i=1;i<=n;i+)printf("%d ",L->datai);/*顺序表的查找：*/int LocateList(SeqList *L,int x)int i;for(i=1;i<=10;i+) if(L->datai)=x) return(i); else return(0);/*顺序表的插入：*/void InsertList(SeqList *L,int x,int 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;j<=(L->length)-1;j+)L->dataj=L->dataj+1;程序2：单链表基本操作的实现这个程序中演示了单链表的创建、插入、删除和查找。程序如下： #include<malloc.h>typedef struct node int data; struct node *next; NODE;/*/NODE *Create()NODE *p,*head;int 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->next!=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&&j<i)j+;p=p->next;if(!p->next|j>i) return(0);else return(p->data);/*/void Del(NODE *head,int i)NODE *p=head;int j=0;while(p->next&&j<i-1)j+;p=p->next;if(!p->next|j>i-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&&j<i-1)j+;p=p->next;if(!p->next&&j>i-1) printf("Wrong positionn" );else q=(NODE *)malloc(sizeof(NODE); q->data=e; q->next=p->next; 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 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、理解顺序栈和链栈存储结构的特点；3、掌握顺序栈存储结构的构造、取栈顶元素、入栈和出栈的基本操作算法；4、理解队列的基本概念和特点；5、掌握顺序队列和链队列存储结构的各自特点；6、掌握顺序队列存储结构的构造、取队头元素、入队和出队基本操作算法。二、 实验要求1、 要求掌握本实验的各个算法和程序。2、 要求独立完成并上机运行本程序。三、 实验原理从数据结构角度看，栈和队列是两种特殊的线性表。它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，即栈和队列是操作受限制的线性表，也可以将它们称为限定性的线性表结构。四、 主要仪器及耗材计算机，Turbo C 2.0 软件。五、实验内容与步骤 实验21 顺序栈的建立，入栈和出栈#define n 5#include <stdio.h>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;i<n;i+)printf("%d ",Ai);printf("n");for(i=0;i<n;i+)push(Ai);for(i=0;i<n;i+)Ai=pop();printf("Data after inversinging:");for(i=0;i<n;i+)printf("%d ",Ai);printf("n");int pop(void)return Stacktop-;void push(int ch)Stack+top=ch;实验22 顺序队列的建立，入队和出队#define n 5#include<stdio.h>int 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;i<n;i+)printf("%d ",Ai);addcq(Ai);addcq(11);printf("n");printf("Data output:");for(i=0;i<n;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(cfront=(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、保存和打印出程序的运行结果，并结合程序进行分析。4、打印出文件清单。三、 实验原理查找和排序是数据处理中使用频率极高的重要运算，几乎在任何一个计算机系统软件和应用软件中都会涉及到。我们把同一数据类型的数据元素构成的集合称为查找表，把查找表中某个可以标识一个数据元素的数据项的值称为关键字。当问题涉及的数据量大的时候，常常要求使用效率较高的查找方法，如折半查找法，这往往要求先对查找表中的记录进行排序。四、 主要仪器及耗材计算机，Turbo C 2.0 软件。五、实验内容与步骤 实验21 已知学生的信息数据项包括：学号、姓名、性别和年龄。定义学生信息查找表的记录结构。在学生信息查找表中实现对关键字学号进行顺序查找和折半查找。#include<stdio.h>#include<stdlib.h>#include<string.h>typedef 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 && stui.num !=key)i+;if(i>=n)return -1;else return i;/*冒泡排序*/void BubbleSort(StuNODE stu,int n)int i,j;StuNODE temp;for(i=0;i<n-1;i+)for(j=n-1;j>i;j-) if(stuj.num <stuj-1.num)temp.num =stuj.num;strcpy(temp.name,stuj.name);temp.sex=stuj.sex;temp.age=stuj.age;stuj.num =stuj-1.num; strcpy(stuj.name,stuj-1.name);stuj.sex=stuj-1.sex;stuj.age=stuj.age; stuj-1.num =temp.num; strcpy(stuj-1.name,temp.name);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<=high)mid=(low+high)/2;printf("第%d次查找：在%d,%d中找到元素stu%d:%dn",+count,low,high,mid,stumid.num);if(stumid.num =key)return mid;if(stumid.num > 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;p<stu+n;p+) printf("%-8d%-18s%4c%4dn",p->num,p->name,p->sex,p->age);printf("1、顺序查找：n");printf("请输入要查询的学生学号：n");scanf("%d",&key); sResult=seqSearch(stu,n,key); if(sResult<0)printf("没有学号为%d的学生n",key);elseprintf("n学号为%d的学生为：n",key); printf("%-8d%-18s%4c%4dn",stusResult.num,stusResult.name,stusResult.sex,stusResult.age);printf("2、按任意健，开始冒泡排序：n");printf("n初始序列：n"); printf("NO. Name Sex agen");for(p=stu;p<stu+n;p+) printf("%-8d%-18s%4c%4dn",p->num,p->name,p->sex,p->age);BubbleSort(stu,n); printf("n冒泡排序后的结果序列为：n"); printf("NO. Name Sex agen");for(p=stu;p<stu+n;p+) printf("%-8d%-18s%4c%-4dn",p->num,p->name,p->sex,p->age);printf("3、二分查找：n");printf("请输入要查询的学生的学号：n");scanf("%d",&key);sResult=BinSearch(stu,n,key);if(sResult<0)printf("没有学号为%d的学生n",key);elseprintf("n学号为%d的学生为：n",key); printf("%-8d%-18s%4c%4dn",stusResult.num,stusResult.name,stusResult.sex,stusResult.age);六、 实验注意事项实验过程中注意结构体中各个数据域的使用，注意字符数组的比较和复制。七、 思考题1. 如何修改冒泡排序的函数BubbleSort(),使冒泡排序的平均趟数减少？实验四 排序算法一、 实验目的1.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；2.深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；3.了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。二、 实验要求1认真阅读和掌握本实验的算法。2上机将本算法实现。3保存和打印出程序的运行结果，并结合程序进行分析。三、 实验原理排序是计算机领域的一项重要技术，是程序设计中的一种重要运算。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。学习和研究各种排序方法，是计算机工作者的一项重要工作课题。冒泡排序想来大家都很熟悉，它是一种想法很自然的排序方法。快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两个部分。其中，一部分记录的关键字均比另一部分小，则可分别对两个部分的记录进行排序，以达到整个序列的有序。假设待排的序列为RS, RS+1, RS+2,， RT,首先任意选取一个记录，RS作为枢轴，然后重新排列其它记录。将所有关键字比它小的记录都放在它的前面，其它所有关键字比它大的记录放在它的后面。由此可以将记录以“枢轴”为界，将记录分为两个子序列，这个过程称为一趟快速排序。以后再分别对两个子序列进行快速排序，重复进行这个过程，直到整个序列全部有序为止。快速排序的平均时间为 Tavg(n)=kn ln n，其中n为待排记录的个数。K为某个常数，经验证明在所有的同数量级的先进排序方法之中，快排的k最小。因此，就平均时间而言，快排是被认为最好的内部排序方法。四、 主要仪器及耗材计算机，Turbo C 2.0软件。五、 实验内容与步骤统计成绩1.问题描述 给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：（1） 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；（2） 按名次列出每个学生的姓名与分数。2.基本要求学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。3.算法实现下面给出的是学生的类型定义：typedef struct student char name8; int score; ；分别用直接插入排序、直接选择排序、快速排序和归并排序实现上述算法。六、 实验注意事项在实验过程中，要注意复杂程序的设计过程。七、 思考题1结合实验，理解针对不同待排元素的特点而选择不同排序方法的必要性。实验五 二叉树的操作一、 实验目的1.进一步掌握指针变量、动态变量的含义；2.掌握二叉树的结构特征，以及各种存储结构的特点及适用范围；3.掌握用指针类型描述、访问和处理二叉树的运算。二、 实验要求1.根据以上函数的定义及功能完成函数的函数体；2.在主函数中调用这些函数，完成整个程序。以学会在二叉树的二叉链表这种存储结构上的一些基本操作。3.保存和打印出程序的运行结果，并结合程序进行分析三、 实验原理1树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的，在计算机领域里也得到了广泛的应用。在编译程序里，也可用树来表示源程序的语法结构，在数据库系统中，数形结构也是信息的重要组织形式。2节点的有限集合（N大于等于0）。在一棵非空数里：（1）、有且仅有一个特定的根节点；（2）、当N大于1时，其余结点可分为M（M大于0）个互不相交的子集，其中每一个集合又是一棵树，并且称为根的子树。树的定义是以递归形式给出的。3二叉树是另一种树形结构。它的特点是每个结点最多有两棵子树，并且，二叉树的子树有左右之分，其次序不能颠倒。4二叉树的结点存储结果示意图如下：左指针域数据域右指针域 二叉树的存储（以五个结点为例）：A BNILCNIL NILDNILNILENIL四、 主要仪器及耗材计算机，Turbo C 2.0软件。五、 实验内容与步骤GFECDBA1、 如下二叉树：广义表表示为：A（B（D（，G），C（E，F） 二叉树a已知以下二叉树的存储结构类型， typedef struct node int data; stuuct node *lchild, *rchild; bitree; InitiatTree() root=NULL;/初始建立二叉树为空 void CreateBTree(char* a); /根据存于字符数组a的二叉树广义表建立对应的二叉树存储结构 void TraverseBTree(bitree *root); /按任一种遍历（分别用递归和非递归）次序输出二叉树中的所有结点 int BTreeDepth(bitree *root);/求二叉树的深度 int BTreeCount(bitree *root);/求二叉树中所有结点数 int BTreeLeafCount(bitree *root);/求二叉树中所有叶子结点数void PrintBTree(bitree *root);/按照二叉树的一种表示方法（广义表）输出整个二叉树 main() bitree *root; /定义二叉树 int n,leaf;/定义二叉树的所有节点数和叶子节点数int h;/定义二叉树的深度 2、 参考程序如下： # define bitreptr struct type1 /*二叉树及其先序遍历*/# define null 0# define len sizeof(bitreptr)bitreptr *bt;int f,g;bitreptr /*二叉树结点类型说明*/ char data; bitreptr *lchild,*rchild; ;preorder(bitreptr *bt) /*先序遍历二叉树*/ if(g=1) printf("先序遍历序列为：n"); g=g+1; if(bt) printf("%6c",bt->data); preorder(bt->lchild); preorder(bt->rchild); 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->rchild=crt_bt(); return(bt); main() f=1; g=1; bt=crt_bt(); preorder(bt); 六、 实验注意事项实验过程中注意递归的使用。七、 思考题1. 画出给出的各类型的数据示意图，理解为不同目的而建立的不同数据结构意义。2. 改写程序完成中、后序遍历。3. 考虑用非递归算法完成二叉树遍历。4完成其他的函数所定义的功能。实验六 图的操作一、 实