数据结构上机实验题.doc

《数据结构上机实验题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章排序数据结构上机实验题内容概要：对于计算机学科而言，实践非常重要，它是检验读者对理论知识的掌握程度，同时加深读者对所学知识的理解和运用，本附录为读者布置了七道上机实验题，分别对应于教材的第二章至第四章及第六章至第九章的内容。279第9章排序实验一线性表实验目的：1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。3.掌握线性表的链式存储结构——单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构——单链表中的各种基本操作。实验内容：1.顺序线性表的建立、插入及删除。2.

2、链式线性表的建立、插入及删除。实验步骤：1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。实现提示：1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。在此，我们利用C语言的结构体类型定义顺序表：#defineMAXSIZE1024typedefintelemtype;/*线性表中存

3、放整型元素*/typedefstruct{elemtypevec[MAXSIZE];intlen;/*顺序表的长度*/}sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下：typedefintelemtype;typedefstructnode{elemtypedata;//数据域structnode*ne

4、xt;//指针域}linklist;注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：279第9章排序p=(linklist*)malloc(sizeof(linklist));该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。思考与提高：1.如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2.在main函数里如果去掉L=&a语句，会出现什么结果？实验二栈实验目的：

5、掌握栈的顺序表示和实现实验内容：编写一个程序实现顺序栈的各种基本运算。实验步骤：1.初始化顺序栈2.插入元素3.删除栈顶元素4.取栈顶元素5.遍历顺序栈6.置空顺序栈实现提示：/*定义顺序栈的存储结构*/typedefstruct{Datatypestack[MAXNUM];inttop;}SqStack;/*初始化顺序栈函数*/voidInitStack(SqStack*p){q=(SqStack*)malloc(sizeof(SqStack)/*申请空间*/}/*入栈函数*/voidPush(SqStack*p,Datatypex){if(p->top

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

7、tack[i]);}/*置空顺序栈函数*/voidsetEmpty(SqStack*p){p->top=-1;}思考与提高：读栈顶元素的算法与退栈顶元素的算法有何区别？实验三队列实验目的：掌握队列的链式表示和实现实验内容：实现队列的链式表示和实现。实验步骤：1.初始化并建立链队列2.入链队列3.出链队列4.遍历链队列实现提示：/*定义链队列*/typedefstructQnode{Datatypedata;structQnode*next;}Qnodetype;typedefst