数据结构实验指导书
数据结构实验指导书
内容简介《数据结构实验教程》为了使学生能够尽快地掌握数据结构中的各种算法而编写的。本教材所写算法结构清晰、可读性强、易于调试、符合软件工程的规范要求等特点。所有实验项目都给出了完整的C语言程序，对关键的算法及语句都给出了详细的注释。所有程序都在VisualC++环境下调试运行通过。对于数据结构的每个知识点给出了多个实验项目，分为验证实验和设计实验，在最后一章给出了综合实验。全书共分9部分。主要内容包括线性表、栈和队列、数组、串、树和二叉树、图、查找、内部排序和文件
内容简介 《数据结构实验教程》为了使学生能够尽快地掌握数据结构中的各种算法而编写 的。本教材所写算法结构清晰、可读性强、易于调试、符合软件工程的规范要求等特点。 所有实验项目都给出了完整的 C 语言程序，对关键的算法及语句都给出了详细的注释。 所有程序都在 Visual C++环境下调试运行通过。 对于数据结构的每个知识点给出了多个实验项目，分为验证实验和设计实验，在最 后一章给出了综合实验。 全书共分 9 部分。主要内容包括线性表、栈和队列、数组、串、树和二叉树、图、 查找、内部排序和文件
目髪录第 1 章 线性表1.1知识点概述1.2线性表的顺序存储结构1.3线性表的链式存储结构101.4小结.16第2 章栈与队列，.17知识点概述2.1172.2栈及其应用.182.3 .27队列及其应用小结2.440第3章数组413.1知识点概述41数组的基本操作3.2 .413.3矩阵的压缩存储.443.4小结.47串第4章.48知识点概述.484.14.2 字符串的基本操作484.3 小结..53第 5章树和二叉树..54知识点概述.545.15.2二叉树的基本操作及应用..575.3小结.66第6章日图.676.1知识点概述.67
目 录 第 1 章 线性表.1 1.1 知识点概述. 1 1.2 线性表的顺序存储结构. 1 1.3 线性表的链式存储结构. 10 1.4 小结. 16 第 2 章 栈与队列.17 2.1 知识点概述. 17 2.2 栈及其应用. 18 2.3 队列及其应用. 27 2.4 小结. 40 第 3 章 数组.41 3.1 知识点概述. 41 3.2 数组的基本操作. 41 3.3 矩阵的压缩存储. 44 3.4 小结. 47 第 4 章 串.48 4.1 知识点概述. 48 4.2 字符串的基本操作. 48 4.3 小结. 53 第 5 章 树和二叉树.54 5.1 知识点概述. 54 5.2 二叉树的基本操作及应用. 57 5.3 小结. 66 第 6 章 图.67 6.1 知识点概述. 67
6.2图的基本操作及应用.69小结6.3.79第 7 章查找...807.1知识点概述.807.2查找实验，..827.3小结.87第 8 章 排序..88知识点概述.888.1排序实验8.2.908.3小结.104第9 章文件....1059.1知识点概述1059.2综合实验..1059.3小结117
6.2 图的基本操作及应用. 69 6.3 小结. 79 第 7 章 查找.80 7.1 知识点概述. 80 7.2 查找实验. 82 7.3 小结. 87 第 8 章 排序.88 8.1 知识点概述. 88 8.2 排序实验. 90 8.3 小结. 104 第 9 章 文件.105 9.1 知识点概述. 105 9.2 综合实验. 105 9.3 小结. 117
第1章?线性表1.1知识点概述线性表是最基本最常用的一种线性结构。其特点是除了第一个元素和最后一个元素以外，其他数据元素都只有一个前驱和一个后继。一个线性表中的数据元素应具有相同的描述性质，即属于同一个数据对象。在实际应用中，必须将线性表中的数据存放在计算机中。常用的存储方式有两种：顺序存储和链式存储，线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各个元素，使得数据元素逻辑上的相邻关系与物理上的相邻关系一致。链式存储是指用一组任意的存储单元来存储线性表中的数据元素，这一组存储单元可以是连续的，也可以是不连续的。因而必须在存储每个元素的同时，也要存储元素之间的逻辑关系。顺序存储的线性表又称顺序表，可以随机地存取表中的任意一个元素；也无需为表示结点之间的逻辑关系而额外增加存储空间。但是，顺序表在进行插入和删除操作时需要移动大量的元素，影响运行的效率；同时表的最大容量事先无法估计，如果对表长估计的过长，可能会浪费空间，相反则可能会发生溢出的现象。链式存储的线性表又称链表，查找表中任一元素时需要从头结点的指针域开始逐步向后（前）查找：每个结点需要增加指针域；动态分配存储空间，存储空间得到了充分利用；易于插入和删除元素。线性表的主要基本操作有初始化、判断表空、求表长、插入、删除和查找等。1.2线性表的顺序存储结构一、实验目的1、熟悉C语言的上机环境，进一步掌握C语言的结构特点。2、掌握线性表的顺序存储结构的定义及C语言实现。3、掌握线性表在顺序存储结构即顺序表中的各种基本操作。1
1 第 1 章 线性表 1.1 知识点概述 线性表是最基本最常用的一种线性结构。其特点是除了第一个元素和最后一个元素 以外，其他数据元素都只有一个前驱和一个后继。一个线性表中的数据元素应具有相同 的描述性质，即属于同一个数据对象。 在实际应用中，必须将线性表中的数据存放在计算机中。常用的存储方式有两种： 顺序存储和链式存储，线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序 存放线性表的各个元素，使得数据元素逻辑上的相邻关系与物理上的相邻关系一致。链 式存储是指用一组任意的存储单元来存储线性表中的数据元素，这一组存储单元可以是 连续的，也可以是不连续的。因而必须在存储每个元素的同时，也要存储元素之间的逻 辑关系。 顺序存储的线性表又称顺序表，可以随机地存取表中的任意一个元素；也无需为表 示结点之间的逻辑关系而额外增加存储空间。但是，顺序表在进行插入和删除操作时需 要移动大量的元素，影响运行的效率；同时表的最大容量事先无法估计，如果对表长估 计的过长，可能会浪费空间，相反则可能会发生溢出的现象。 链式存储的线性表又称链表，查找表中任一元素时需要从头结点的指针域开始逐步 向后（前）查找；每个结点需要增加指针域；动态分配存储空间，存储空间得到了充分 利用；易于插入和删除元素。 线性表的主要基本操作有初始化、判断表空、求表长、插入、删除和查找等。 1.2 线性表的顺序存储结构 一、实验目的 1、熟悉 C 语言的上机环境，进一步掌握 C 语言的结构特点。 2、掌握线性表的顺序存储结构的定义及 C 语言实现。 3、掌握线性表在顺序存储结构即顺序表中的各种基本操作
4、利用线性表的顺序存储结构解决实际问题二、实验内容（一）验证实验1、定义顺序表类型typedef int datatype;typedef structdatatype elem[MAX];int Last,List,*SeqList,2、完成顺序表中的基本操作的实现初始化、插入、删除、求表长、按值查找、按位置查找。实验程序：#include#include#define MAX 100typedef int datatype,typedef structdatatype elem[MAX];int Last,//定义顺序表类型List,*SeqList,1初始化顺序表SeqList InitList()SeqList L;L=(SeqList)malloc(sizeof(List));L->Last=-1;return L,2
2 4、利用线性表的顺序存储结构解决实际问题。 二、实验内容 （一）验证实验 1、定义顺序表类型 typedef int datatype; typedef struct { datatype elem[MAX]; int Last; }List,*SeqList; 2、完成顺序表中的基本操作的实现 初始化、插入、删除、求表长、按值查找、按位置查找。 实验程序： #include #include #define MAX 100 typedef int datatype; typedef struct { datatype elem[MAX]; int Last; }List,*SeqList; //定义顺序表类型 SeqList InitList() //初始化顺序表 { SeqList L; L=(SeqList)malloc(sizeof(List)); L->Last=-1; return L; }
voidCreateList(SeqListL）//创建顺序表int i,n,printf("请输入你要创建的顺序表元素个数n=");scanf("%d",&n);printf("请输入你要创建的顺序表："),for(i=0;ielem[i]);L->Last++;intLocation(SeqListL,datatypex）//查找某元素所在位置1int i=0,while(L->elem[i]!=x&&iLast)i++;if(i>L->Last)return -1;elsereturn i,voidInsertelem(SeqListL,datatypem）1/插入元素int i,n,printf("请输入你要插入的位置n=");scanf("%d",&n);if(L->Last+1)>MAX)printf("表已满，不能插入");3
3 void CreateList(SeqList L) //创建顺序表 { int i,n; printf("请输入你要创建的顺序表元素个数 n= "); scanf("%d",&n); printf("请输入你要创建的顺序表:"); for(i=0;ielem[i]); L->Last++; } } int Location(SeqList L,datatype x) //查找某元素所在位置 { int i=0; while(L->elem[i]!=x&&iLast) i++; if(i>L->Last) return -1; else return i; } void Insertelem(SeqList L,datatype m) //插入元素 { int i,n; printf("请输入你要插入的位置 n="); scanf("%d",&n); if((L->Last+1)>MAX) printf("表已满,不能插入");
elseL->Last++;for(i=L->Last;i>=n-1;i--)L->elem[i+1]=L->elem[i];L->elem[n-1]=m;void Deleteelem(SeqList L,datatype m)/删除表中某元素int i.j;i=Location(L,m);while(i---1)datatype n;printf("你所查找的元素不在表中,请重新输入你要删除的元素")scanf("%d",&n),i=Location(L,n);for(j=ijLast:j++)L->elem[i]=L->elem[i+1];L->Last--;voidShowList(SeqListL）//显示当前顺序表( int i,printf("当前顺序表元素为：");for(i=0;iLast;i++)printf("%5d",L->elem[i]);4
4 else { L->Last++; for(i=L->Last;i>=n-1;i-) L->elem[i+1]=L->elem[i]; L->elem[n-1]=m; } } void Deleteelem(SeqList L,datatype m) //删除表中某元素 { int i,j; i=Location(L,m); while(i==-1) { datatype n; printf("你所查找的元素不在表中,请重新输入你要删除的元素"); scanf("%d",&n); i=Location(L,n); } for(j=i;jLast;j++) L->elem[j]=L->elem[j+1]; L->Last-; } void ShowList(SeqList L) //显示当前顺序表 { int i; printf("当前顺序表元素为:"); for(i=0;iLast;i++) printf("%5d",L->elem[i]);
/主函数void mainOint Opration;SeqList L,L=InitListO);CreateList(L);printf("输入操作：1为删除某元素2为插入某元素3为查找某元素4为输出当前顺序表5为退出n");while(Opration<=5)(scanf("%d",&Opration);if(Opration=-1)int n,printf("请输入你要删除的元素n=")scanf("%d",&n)Deleteelem(L,n);子if(Opration=--2)1int n;printf("请输入你要插入的元素n=");scanf("%d",&n),Insertelem(L,n);子if(Opration==3)datatype x,printf("请输入你要查找的元素x=");5
5 } void main() //主函数 { int Opration; SeqList L; L=InitList(); CreateList(L); printf("输入操作:1 为删除某元素 2 为插入某元素 3 为查找某元素 4 为输出当前 顺序表 5 为退出\n"); while(Opration<=5) {scanf("%d",&Opration); if(Opration==1) { int n; printf("请输入你要删除的元素 n="); scanf("%d",&n); Deleteelem(L,n); } if(Opration==2) { int n; printf("请输入你要插入的元素 n="); scanf("%d",&n); Insertelem(L,n); } if(Opration==3) { datatype x; printf("请输入你要查找的元素 x=");
scanf("%d",&x);printf("此元素在顺序表中的位置为%d\n:",Location(L,x)+1)7if(Opration==4)ShowList(L);if(Opration=--5)break;11（二）设计实验1、编写一个算法实现两个有序（从小到大）顺序表合并成为一个顺序表，合并后的结果放在第一个顺序表中，不另设新的顺序表存储（假设这两个有序顺序表中没有相同的元素）2、设有一个顺序表A，包含n个元素，要求写出一个将该表逆置的算法，并只允许在原表的存储空间外再增加一个附加的工作单元3、有一个已按递增次序排好序的线性表，今输入一个数，要求按原来的排序规律将它插入到线性表中。实验程序：1、文件名：sq.c#include#define MaxLen 50typedef int elemtype;typedefelemtypesqlist[MaxLen];int create(sqlist A)1/创建顺序表1int i,n;printf("建立顺序表：");printf("输入元素个数：");scanf("%d",&n);6
6 scanf("%d",&x); printf("此元素在顺序表中的位置为%d\n:",Location(L,x)+1); } if(Opration==4) ShowList(L); if(Opration==5) break; } } （二）设计实验 1、编写一个算法实现两个有序（从小到大）顺序表合并成为一个顺序表，合并后 的结果放在第一个顺序表中，不另设新的顺序表存储（假设这两个有序顺序表中 没有相同的元素） 2、设有一个顺序表 A，包含 n 个元素，要求写出一个将该表逆置的算法， 并只允许在原表的存储空间外再增加一个附加的工作单元 3、有一个已按递增次序排好序的线性表，今输入一个数，要求按原来的排序规律 将它插入到线性表中。 实验程序： 1、文件名：sq.c #include #define MaxLen 50 typedef int elemtype; typedef elemtype sqlist[MaxLen]; int create(sqlist A) //创建顺序表 { int i,n; printf("建立顺序表:"); printf("输入元素个数:"); scanf("%d",&n);