实验编排-宁

数据结构实验指导

宁黎华编

数学与计算科学学院

目录

实验一 顺序表的基本操作 ........................................................................................................... 1 实验二 链表的基本操作 ............................................................................................................... 4 实验三 栈的基本运算 ................................................................................................................... 8 实验四 二叉树的操作 ................................................................................................................. 11 实验五 马踏棋盘问题 ................................................................................................................. 14 实验六 二叉检索树..................................................................................................................... 16 实验七 排序 ................................................................................................................................ 18 附录一 TURBOTC出错信息一览 .................................................................................................. 21 附录二 实验报告的一般格式 ..................................................................................................... 24

2

实验一 顺序表的基本操作

1、实验目的

（1） 掌握顺序表的基本运算，熟悉对顺序表的一些基本操作和具体函数的定义。 （2） 掌握顺序存储的概念，学会定义线性表的顺序存储类型。 （3） 熟悉c语言程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的

相互关系及各自的作用。

（4） 熟悉c语言环境的使用及程序的输入、编辑、调试和运行的全过程。 （5） 加深对顺序存储结构的理解，逐步培养解决实际问题的编程能力。

2、实验要求

（1） 熟练掌握线性表的存储结构及其基本操作。

（2） 理解所给出的算法，掌握线性表在实际中的应用。

（3） 将上机程序调试通过，并能独立完成一至两个拓展题目。

3、实验内容

实现顺序表上的插入、删除等操作。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对有关算法的理解。

4、实验方法

第一步:定义顺序表的存储结构。

第二步：编写顺序表操作的具体函数定义。

第三步：使用定义的顺序表并调用顺序表的一些操作，实现具体运算。 具体函数的定义有：

1） insert(L,i,x)在顺序表的第i个元素之前插入一个新元素x. 2） delete (L,i) 删除顺序表的第i个元素。 3） listprint(L) 输出顺序表。

注意：每完成一个步骤，必须及时输出线性表元素，以便于观察操作结果。 #define MAXSIZE 100 /*宏定义*/ #define OK 1

#define OVERFLOW -2

#include \包含输入输出文件*/

typedef int elemtype;

typedef struct /*定义顺序表的结构*/

{elemtype vec[MAXSIZE]; /*顺序表数据成员所占据的存储空间*/ int last; /*顺序表中最后一个元素在数组中的下标（或向量中的位置）

从0开始*/

}sequenlist;

int insert(L,i,x) /*在顺序表的第i个元素之前插入一个新元素x*/ sequenlist *L; int i;

elemtype x; { int j;

if(((*L).last)>=MAXSIZE-1)

1

{printf(\ return(0); /*溢出判断*/ } else

if((i<1)||(i>(*L).last+1))

{printf(\ return(0); /*插入位置不正确*/ } else

{for(j=(*L).last;j>=i-1;j--) /*后移元素*/ (*L).vec[j+1]=(*L).vec[j];

(*L).vec[i-1]=x; /*插入新元素*/ (*L).last=(*L).last+1;/*修改last的值*/ }

return(1); }

void delete(L,i) /*删除顺序表的第i个元素*/ sequenlist *L; int i; { int j;

if((i<1)||(i>(*L).last+2)) printf(\ else

{for(j=i;j<=(*L).last;j++) (*L).vec[j-1]=(*L).vec[j];/*前移元素，覆盖掉要删除元素的值*/ (*L).last--; /*修改last的值*/ } }

void listprint(sequenlist *L) /*输出线性表*/ {int i;

for(i=0;i<=(*L).last;i++)

printf(\ }

main() {

sequenlist sl={{1,2,3,4,5,6,7,8,9,10},9};//直接给顺序表赋初值 sequenlist *L;/*定义一个指向顺序表类型的指针变量*/ int i,j,x; elemtype e;

L=&sl; /*给指针变量赋值*/

printf(\ scanf(\

2

printf(\ insert(L,i,x); listprint(L);

printf(\ scanf(\ delete(L,j); listprint(L); }

5、预习思考题

调试好上述程序后，试着完成以下拓展内容：

（1） 定义一个定位函数locate(L,x)，具有元素检索的功能。当顺序表中存在一个值为x

的数据元素时，返回第一次找到的数据元素的位序，否则，给出一个值，表示值为x的元素不存在。在主程序中调用该函数，分析操作结果。

（2） 定义一个逆置函数diverse(L),把顺序表进行逆置。在主程序中调用该函数，分析

操作结果。

（3） 定义一个函数delsame(L),把顺序表中重复的元素删除掉，只保留一个。在主程序

中调用该函数，分析操作结果。

6、分析讨论题：

在c语言中，用户向系统申请一块地址连续的有限空间的方法是使用数组。而数组分为动态数组和静态数组。静态数组的存储空间的申请和释放是由系统自动完成的，一旦申请成功，其所占用的内存大小也就固定不变了，一般的申请方式如int a[10];而动态数组存储空间的申请和释放是由用户通过调用系统函数自己完成的，常见的申请方式如int *a; a = new int[10];动态数组的大小运行时给定，但运行过程中可以改变。那么，你知道什么时候使用动态数组，什么时候使用静态数组么？如果顺序表的结构体定义中使用的不是静态数组，而是动态数组，那么有什么问题需要考虑？如果线性表中需要频繁地插入或者删除元素，那么使用哪种数组申请方式好？

3

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