数据结构实验指导.docxVIP

数据结构实验指导

宁黎华编

数学与计算科学学院

2

目录

实验一顺序表的基本操作 1

实验二链表的基本操作 4

实验三栈的基本运算 8

实验四二叉树的操作 11

实验五马踏棋盘问题 14

实验六二叉检索树 16

实验七排序 18

附录一TURBOTC出错信息一览 21

附录二实验报告的一般格式 24

1

实验一顺序表的基本操作

1、实验目的

（1）掌握顺序表的基本运算，熟悉对顺序表的一些基本操作和具体函数的定义。

（2）掌握顺序存储的概念，学会定义线性表的顺序存储类型。

（3）熟悉c语言程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。

（4）熟悉c语言环境的使用及程序的输入、编辑、调试和运行的全过程。

（5）加深对顺序存储结构的理解，逐步培养解决实际问题的编程能力。

2、实验要求

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

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

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

3、实验内容

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

4、实验方法

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

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

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

1）insert(L,i,x)在顺序表的第i个元素之前插入一个新元素x.

2）deletet(L,i)删除顺序表的第i个元素。

3）listprint(L)输出顺序表。

注意：每完成一个步骤，必须及时输出线性表元素，以便于观察操作结果。

#defineMAXSIZE100/*宏定义*/

#defineOK1

#defineOVERFLOW-2

#includestdio.h/*包含输入输出文件*/

typedefintelemtype;

typedefstruct/*定义顺序表的结构*/

{elemtypevec[MAXSIZE];/*顺序表数据成员所占据的存储空间*/

intlast;/*顺序表中最后一个元素在数组中的下标（或向量中的位置）从0开始*/

}sequenlist;

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

sequenlist*L;inti;

elemtypex;{intj;

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

2

{printf(thelistisoverflow!\n);return(0);/*溢出判断*/

}else

if((i1)||(i(*L).last+1))

{printf(positionisnotcorrect!\n);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);}

voiddelete(L,i)/*删除顺序表的第i个元素*/

sequenlist*L;inti;

{intj;

if((i1)||(i(*L).last+2))

printf(deletefail\n);

else

{for(j=i;j=(*L).last;j++)

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

}}

voidlistprint(sequenlist*L)/*输出线性表*/{inti;

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

printf(i,e=%d,%d\n,i,L-vec[i]);}

main(){

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

inti,j,x;elemtypee;

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

printf(pleaseinputtheinsertpositio