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

《《数据结构》实验指导书20.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实验指导书南京工程学院信息管理与信息系统教研室2011年3月实验一线性表操作一、实验目的1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。3.掌握线性表的链式存储结构——单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构——单链表中的各种基本操作。二、实验内容1.顺序线性表的建立、插入及删除。2.链式线性表的建立、插入及删除。三、实验步骤1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，

2、31}，然后在第i个位置插入元素68。3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。四、实现提示1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。在此，我们利用C语言的结构体类型定义顺序表：#defineMAXSIZE 1024typedef int elemtype;   /* 线性表中存放整型元素 */typedefstruct{elemtypevec[MAXSIZE]; intlen;            /* 顺序表的长度 */ }sequenlist;将此

3、结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下：   typedefintelemtype;typedefstructnode   {elemtypedata;  //数据域     structnode*next;//指针域    }linklist;   注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数mal

4、loc()，如给指针变量p分配一个结点的地址：p=(linklist*)malloc(sizeof(linklist));该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。五、思考与提高1.如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2.在main函数里如果去掉L=&a语句，会出现什么结果？实验二栈和队列的应用一、实验目的1.掌握栈的顺序表示和实现2.掌握队列的链式表示和实现二、实验内容1.编写一个程序实现顺序栈的各种基本运算。2.实现队列的链式表示和实

5、现。三、实验步骤1.初始化顺序栈2.插入元素3.删除栈顶元素4.取栈顶元素5.遍历顺序栈6.置空顺序栈7.初始化并建立链队列8.入链队列9.出链队列10.遍历链队列四、实现提示1./*定义顺序栈的存储结构*/typedefstruct{    ElemTypestack[MAXNUM];    inttop;}SqStack;/*初始化顺序栈函数*/voidInitStack(SqStack*p){q=(SqStack*)malloc(sizeof(SqStack)/*申请空间*/)/*入栈函数*/voidPush(SqStack*p,ElemTypex){if(p->top

6、)    {p->top=p->top+1;    /*栈顶+1*/     p->stack[p->top]=x;} /*数据入栈*/}/*出栈函数*/ElemTypePop(SqStack*p){x=p->stack[p->top];/*将栈顶元素赋给x*/p->top=p->top-1;}/*栈顶-1*//*获取栈顶元素函数*/ElemTypeGetTop(SqStack*p){x=p->stack[p->top];}/*遍历顺序栈函数*/voidOutStack(SqStack*p){for(i=p->top;i>=0;i--)printf("第%d个数据元素是：%6d",i,p-

7、>stack[i]);}/*置空顺序栈函数*/voidsetEmpty(SqStack*p){p->top=-1;}2./*定义链队列*/typedefstructQnode{  ElemTypedata;    structQnode*next;}Qnodetype;typedefstruct{  Qnodetype*front;    Qnodetype*rear;}Lqueue;/*初始化并