(数据结构)实验指导书

实验一 线性表的基本操作及应用

一、实验目的

1．通过实际操作掌握定义线性表的顺序存储类型，熟悉线性表的基本操作的算法实现(具体的函数定义)，掌握单链表的结点类型的定义及单链表的基本操作算法实现(具体的函数定义)。 2．顺序存储和链式存储的应用。 二、实验要求

1．认真阅读和掌握所给的程序。 2．上机运行程序，并对程序进行分析。 3．完成自编程序，并上机调试运行。 三、实验内容

1．建立顺序表，及其基本操作（包括查找、插入、删除等），并且用数据进行测试。 （1）建立工程

启动Visual C++，选择“文件|新建”弹出如图1所示的对话框，选择Project选项卡中的Win32 Console Application选项，在Project name文本框中输入工程的名字“SeqList”，在Location中输入工程存放的路径，如“D:\数据结构实验\SeqList”。设置如图1所示。然后选择“OK按钮”，弹出如图2所示对话框，单击“Finish”按钮弹出如图3所示对话框，单击“OK”按钮，则创建工程成功，界面如图4所示。

图1 选择新建弹出的对话框

图

2

图3

图4

（2）创建"common.h"头文件

选择“文件|新建”弹出如图5所示的对话框，选择“Files”选项卡中的“C/C++ Header File”，在“File”文本框中输入头文件的名字“common”，如图5所示。选择“OK”按钮。头文件中包含文件包含命令和宏定义，在“common.h”中输入如下内容：

#include <stdio.h> #include <stdlib.h> #include <malloc.h>

#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0

图5

（3）创建“seqlist.h”头文件

“seqlist.h”头文件中主要包含了顺序表的定义以及基本操作。创建方法与创建“common.h”文件相同。“seqlist.h”文件内容如下：

#define ElemType int #define

MAXSIZE 100 /*此处的宏定义常量表示线性表可能达

到的最大长度*/

typedef struct {

ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/

}SeqList;

int Locate(SeqList L, ElemType e) {

int i=0; /*i为扫描计数器，初值为0，即从第一个元素

开始比较*/

}

while ((i<=st)&&(L.elem[i]!=e))

i++;

/*顺序扫描表，直

到找到值为key的元素, 或扫描到表尾而没找到*/

if (i<=st)

return(i+1); /*若找到值为e的元素，则返回其序号*/ return(-1); /*若没找到，则返回空序号*/ else

/*在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L->last+1，i的合法取值范围是 1≤i≤L->last+2 */

int InsList(SeqList *L,int i,ElemType e) { }

int k;

if((i<1) || (i>L->last+2)) /*首先判断插入位置是否合法*/ { }

if(L->last>= MAXSIZE-1) { }

for(k=L->last;k>=i-1;k--) /*为插入元素而移动位置*/

L->elem[k+1]=L->elem[k];

L->elem[i-1]=e; /*在C语言数组中，第i个元素的下标为i-1*/ L->last++; return(OK);

printf("表已满无法插入"); return(ERROR);

printf("插入位置i值不合法"); return(ERROR);

int DelList(SeqList *L,int i,ElemType *e)

/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤st+1 */

{ */

}

void Display(SeqList L) /*显示顺序表L中的数据元素*/ { }

（4）创建“seqlist.c”文件

完成顺序表的创建、查找、插入、删除等操作。选择“文件|新建”弹

int k;

if((i<1)||(i>L->last+1)) { }

*e = L->elem[i-1]; /* 将删除的元素存放到e所指向的变量中for(k=i; k<=L->last; k++)

L->elem[k-1] = L->elem[k]; /*将后面的元素依次前移*/ L->last--; return(OK);

printf("删除位置不合法!"); return(ERROR);

int i;

for(i=0; i<=st; i++) { }

printf("\n");

printf("%d ",L.elem[i]);

出如图6所示的对话框，选择“Files”选项卡中的“C++ Source File”，在“File”文本框中输入文件的名字“seqlist.c”，如图6所示，然后选择“OK”按钮。

图6

在文件“seqlist.c”中输入代码如下： #include "common.h" #include "seqlist.h" void main() {

SeqList *l; int p,r,q; int *e; int i;

l = (SeqList*)malloc(sizeof(SeqList)); e = (int*)malloc(sizeof(int)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1;

}

printf("请输入线性表的各元素值:\n"); for(i=0; i<=l->last; i++) { }

/*在顺序表中查找*/

printf("请输入要查找的元素值:\n"); scanf("%d",&q); p=Locate(*l,q); if(p == -1)

printf("在此线性表中没有该元素!\n"); printf("该元素在线性表中的位置为:%d\n",p); else

/*顺序表的插入操作*/

printf("请输入要插入的位置:\n"); scanf("%d",&p);

printf("请输入要插入的元素值:\n"); scanf("%d",&q); InsList(l,p,q);

printf("插入后的顺序表为："); Display(*l);

/*顺序表的删除操作*/

printf("请输入要删除的元素位置:\n"); scanf("%d",&p); DelList(l,p,e);

printf("删除后的顺序表为："); Display(*l);

printf("删除的元素值为:%d\n",*e);

scanf("%d",&l->elem[i]);

（5）测试数据

输入线性表的长度为：5

输入线性表的各元素值：12 23 56 45 67 输入要查找的元素值：23 输入要插入的位置：2 输入要插入的元素值：33 输入要删除的元素位置：3 （6）运行结果

图7 运行结果图

2．建立单链表，实现其基本操作（包括创建、查找、插入、删除等），并且用数据进行测试。【提示】实现方法同顺序表。

3．若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市的位置坐标。要求：

（1）给定一个城市名，返回其位置坐标。

（2）给定一个位置坐标P和距离D，返回所有距P的距离小于等于D的城市。

4．约瑟夫环问题。

约瑟夫问题的一种描述是：编号为1，2， ，n的n个人按顺时针方

向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m，从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。

利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。

例如m的初值为20；n=7，7个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5。

实验二 栈和队列的基本操作实现

一、实验目的

1．掌握栈的基本操作和具体的函数定义。 2．掌握队列的基本操作和具体的函数定义。 3．栈的应用。 二、实验要求

1．认真阅读和掌握本实验内容所给的程序。

2．上机运行实验内容中的程序，并对程序进行分析。 3．完成自编程序，并上机调试运行。 三、实验内容

1．以顺序栈为存储结构，实现栈的基本操作，包括初始化栈、进栈、出栈、判断栈空等。 2．数制转换。

编写程序，将十进制整数N转换为d进制数，其转换步骤是重复以下两步，直到N等于0。

X=N mod d （其中mod为求余运算） N=N p d （其中p为整除运算） 测试数据：以十进制到二进制转换为例 输出结果为：（789）10→（1100010101）2

注意：要求使用栈的基本运算（包括InitStack（S），Pop（S），Push（S），IsEmpty（S）。应引用栈的头文件实现）。

3．编写程序，判别表达式中左、右括号是否配对。

4．回文判断。称正读与反读都相同的字符序列为“回文”序列。 试编写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属于该模式的字符序列，而‘1+3&3-1’则不是。

实验三 串和数组的应用

一、实验目的

1．掌握串的定义和基本操作。 2．掌握数组的顺序存储及操作。 二、实验要求

1．认真阅读和掌握本实验内容所给的程序。

2．上机运行实验内容中的程序，并对程序进行分析。 3．完成自编程序，并上机调试运行。

三、实验内容

1．运行如下程序。 程序一：串的操作。

以下程序实现用于判定串s2是否是串s1的子串。若是子串，返回其在主串中的位置；否则返回-1。

#include “stdio.h” #include “string.h” #define MaxLen 20 typedef struct {

char ch[MaxLen]; int len; }strtype;

void create(strtype *s,char str[]) //建立字符串 {strcpy(s->ch,str); s->len=strlen(str); }

int index (strtype *s1,strtype *s2) //模式匹配 {int i=0,j,k;

while(i<s1->len) {j=0;

if(s1->ch[i]==s2->ch[j]) {k=i+1;j++;

while(k<s1->len&&s2->len&&s1->ch[k]==s2->ch[j]) {k++;j++;}

if(j==s2->len) break;

else i++; }

else i++; }

if(i>=s->len) return –1; else return (i+1);

}

void main() //主程序 {strtype *s1,*s2; int n;

char str[MaxLen];

s1=(strtype*)malloc(sizeof(strtype)); s2=(strtype*)malloc(sizeof(strtype)); printf(“the string：”); gets(str); create(s1,str);

printf(“the substring：”); gets(str); create(s2,str); n=index(s1,s2); if(n>0)

printf(“the substring’s location：%d\n”,n); else

printf(“no substring.\n”); }

2．对于二维数组A[m][n]，其中m≤80,n≤80，读入m和n，然后读该数组的全部元素，对如下二种情况分别编写相应函数：

a.求数组A靠边元素之和；

b.当m=n时，分别求两条对角线上的元素之和，否则打印出m≠n的信息。

3．编写程序，实现将A[0…n-1]中所有奇数移到偶数之前。要求不另增存储空间，且时间复杂度为为O(n)。

4．以下是一个5×5阶螺旋方阵。编写程序实现输出该形式的n×n(n<10)阶方阵(顺时针方向旋进)。

1 2 3 4 5 16 17 18 19 6

15 24 25 20 7

14 23 22 21 8 13 12 11 10 9

实验四 二叉树的操作

一、实验目的

掌握二叉树的遍历操作及应用。 二、实验要求

1．认真阅读和掌握本实验内容所给的程序。

2．上机运行实验内容中的程序，并对程序进行分析。 3．完成自编程序，并上机调试运行。 三、实验内容

1．以二叉链表作存储结构，实现前序、中序、后序遍历操作，打印输出遍历结果。

基本要求：从键盘接受输入先序序列，建立二叉树（以先序来建立）。 测试数据：ABC@@DE@G@@F@@@（其中@表示空格字符） 输出结果：先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA

2．以二叉链表作存储结构，按层次顺序遍历二叉树。

【提示】本算法采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，如此直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。

3．试编写交换以二叉链表作存储结构的二叉树中所有结点的左、右子树的算法(采用广义表的形式输出二叉树)。

4．二叉树采用二叉链表存储，试编写算法，实现： (1)计算二叉树的所有叶子结点。 (2)求二叉树的深度。

实验五 图的操作

一、实验目的

1．熟悉图的存储表示； 2．掌握图的操作及应用。 二、实验要求

1．认真阅读和掌握所给的程序。 2．上机运行程序，并对程序进行分析。 3．完成自编程序，并上机调试运行。 三、实验内容

1.实现以邻接矩阵存储的图的深度和广度优先遍历。

2.建立一个带权无向图(用邻接矩阵表示)，判断此图是否连通，若是连通图，用Prim算法输出该图的最小生成树。

[提示：将图的深度优先遍历或广度优先遍历算法稍加改造，设置一个变量m保存访问的顶点个数，若已访问顶点个数m小于图中顶点个数n，则图G不连通，否则为连通。深度优先遍历用非递归算法。]

3.软件专业的学生要学习一系列课程，其中有些课程必须在其先修课程完成后才能学习，具体关系见下表：

假设每门课程的学习时间为一学期，试为该专业的学生设计教学计划，使他们能在最短的时间内修完这些课程。

[提示：以顶点代表课程，弧代表课程的先后修关系，按表中条件建立有向无环图，并以邻接表结构表示；统计初始入度为0的顶点，得用拓扑排序算法来进行课程安排。假定一个进修班的学生必须完成所列的全部课程。在这里，课程代表活动，学习每门课的先决条件是学完它的全部先修课程，如“编译原理”课程就必须在它的两门先修课程“数据结构”和“语言的设计和分析”之后，“高等数学”课程则可以在后修课程之前随时安排，因为它是基础课程。]

4.校园导游程序。

用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求实现以下功能：

(1)查询各景点的相关信息。

(2)查询图中任意两个景点间的最短路径。 (3)查询图中任意两个景点间的所有路径。

实验六 查找算法实现

一、实验目的

1．掌握二分查找的算法。 2．掌握二叉排序树的各种操作。 3．熟悉哈希查找方法。 二、实验要求

1．认真阅读和掌握所给的程序。 1．上机运行程序，并对程序进行分析。 2．完成自编程序，并上机调试运行。 三、实验内容 1．运行如下程序。

程序一：二叉排序树的操作。

二叉排序树操作的头文件binSearchTreel.h

typedef int ElemType; //定义二叉排序树结点值的类型为整型 struct BSTNode //定义二叉排序树的结点类型 {ElemType data; BSTNode *left; BSTNode *right; };

void InitBSTree(BSTNode *&BST); //初始化二叉排序树 bool BSTreeEmpty(BSTNode *BST); //判断二叉排序树是否为空 bool Find(BSTNode *BST,ElemType &item);//从二叉树排序树中查找元素

void Insert(BSTNode *&BST,const ElemType &item);//向二叉排序树中插入元素

bool Delete(BSTNode *&BST,const ElemType &item);//从二叉排序树中删除元素

本文来源：https://www.bwwdw.com/article/g9fq.html