数据结构实验指导09级

《数据结构实验指导09级》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验一线性表的顺序表示与实现1．实验目的(1)掌握线性表的顺序存储结构；(2)验证顺序表及其基本操作的实现；(3)掌握数据结构及算法的程序实现的基本方法。2．实验内容（1）建立含有若干个元素的顺序表；（2）对已经建立的顺序表实现插入、删除、查找、合并等基本操作。3．实现算法首先，定义顺序存储结构如下：Typedefstruct{Elemtype*elem;Intlength;Intlistsize;}sqlist;其次，建立含有n个元素的顺序表，算法如下：StatusInitList_Sq(SqList&L){//构造一个空的顺序表L.ele

2、m=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZEreturnOK;}最后，对建立的顺序表设计插入、删除、查找等基本操作的算法如下：StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序表L的第i个元素之前插入新的元素eif(i<1

3、

4、i>L.length+1)returnERROR;if(L.length>=L.lis

5、tsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK；}StatusListDelete_Sq(SqList&L,i

6、nti,ElemType&e){//删除算法if((i<1)

7、

8、(i>L.length))returnERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;returnOK;}intlocate_sq(SqListL,elemtypex)//查找算法{for(i=0;i

9、确的结果。实验二线性表的链式表示与实现1．实验目的(1)掌握线性表的链接存储结构；(2)验证单链表及其基本操作的实现；(3)进一步掌握数据结构及算法的程序实现的基本方法。2．实验内容（1）用头插法和尾插法建立含有若干个元素的带头结点的单链表；（2）对已经建立的单链表实现插入、删除、查找等基本操作。3．实现算法…4．根据上面设计的算法，用C/C++语言实现，调试通过并输出正确的结果。实验三、四栈与队列及其应用1．实验目的(1)掌握栈的顺序存储结构和队列的链式存储结构；(2)掌握栈和队列的操作特性；(3)掌握基于顺序栈和链队列的基本操作的实现方法

10、。2．实验内容（1）建立一个空栈；（2）对已经建立的栈实现入栈、出栈、取栈顶元素等基本操作。（3）建立一个空队列；（4）对已经建立的队列实现插入、删除等基本操作3．实现算法…4．根据上面设计的算法，用C/C++语言实现，调试通过并输出正确的结果。实验五二叉树的应用1．实验目的(1)掌握二叉树的逻辑结构；(2)掌握二叉树的二叉链表存储结构；(3)掌握基于二叉链表存储的二叉树的遍历操作的实现。2．实验内容（1）建立一棵含有n个结点的二叉树；（2）前序（或中序、后序）遍历该二叉树；（3）求该树叶子结点个数。3．实现算法…4．根据上面设计的算法，用C

11、/C++语言实现，调试通过并输出正确的结果。实验六图的遍历与应用1．实验目的(1)掌握图的逻辑结构；(2)掌握图的邻接矩阵存储结构和邻接表存储结构；(3)掌握图的邻接矩阵存储结构和邻接表存储结构下遍历算法的实现。2．实验内容（1）建立无向图的邻接矩阵存储；（2）对已经建立的无向图进行深度优先和广度优先遍历操作。（3）建立有向图的邻接表存储；（4）对已经建立的有向图进行深度优先和广度优先遍历操作。3．实现算法…4．根据上面设计的算法，用C/C++语言实现，调试通过并输出正确的结果。实验七查找技术1．实验目的(1)掌握顺序查找和折半查找算法的基本

12、思想；(2)掌握顺序查找和折半查找算法的实现方法；(3)掌握顺序查找和折半查找算法的时间性能。2．实验内容对给定的长度为n的数组，分别使用顺序查找、折半查找查找数组