数据结构课程的实验报告

《数据结构课程的实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验报告实验课程：学生姓名：学号：专业班级：2012年6月5日目录（1）线性表及其应用3（2）栈和队列11（3）数组18（4）二叉树及其应用28（5）图的应用33（6）查找排序38计算机系数据结构实验报告---（1）线性表及其应用学生姓名：学号：专业班级：实验类型：□验证□综合■设计□创新实验日期：2012/3/18实验成绩：一．实验目的帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。二．问题描述1．构造一个空的线性表L；2．在线性表L的第i个元素之前插入新的元素e；

2、3．在线性表L中删除第i个元素，并用e返回其值。三．实验要求1．分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。2．在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。四．算法分析1．插入操作：输入数据：L=()ListInsert(L,1,'k'),正确结果：L=(k)输入数据：L=(EHIKMOP)ListInsert(L,9,'t'),正确结果：returnERROR;L=(EHIKMOP)输入数据：L=(ABCEHKNPQTU)List

3、Insert(L,4,'u'),正确结果：L=(ABCuEHKNPQTU)2．删除操作：输入数据：L=()ListDelete(L,1,e)正确结果：ERROR,L=()输入数据：L=(DEFILMNORU)ListDelete_Sq(L,5,e)正确结果：L=(DEFIMNORU),e='L'输入数据：L=(CD)ListDelete_Sq(L,1,e)正确结果：L=(D),e='C'3．如线性表有n个结点，对两种存储结构下插入和删除的时间复杂度进行分析。五．实验内容和过程顺序存储C程序：#include

4、dio.h>#includetypedefintelemtype;typedefintstatus;#defineERROR-1#defineOK1#defineOVERFLOW2008#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{elemtype*elem;intlength;intlistsize;}sqlist;statusInitList_Sq(sqlist*L){//构造一个空的线性表Lelemtype*a=0

5、;a=(elemtype*)malloc(LIST_INIT_SIZE*sizeof(elemtype));L->elem=a;if(!(*L).elem)returnOVERFLOW;(*L).listsize=LIST_INIT_SIZE;(*L).length=0;returnOK;}statusList_Insert(sqlist*L,inti,elemtypee){//在第i个元素之前插入元素eelemtype*p=0;elemtype*q=0;elemtype*newbase=0;if(i<1

6、

7、i>

8、(*L).length+1)returnERROR;if((*L).length>=(*L).listsize){newbase=(elemtype*)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(elemtype));if(!newbase)return(OVERFLOW);(*L).elem=newbase;(*L).listsize+=LISTINCREMENT;}q=&((*L).elem[i-1]);for(p=&((*L).elem[(*

9、L).length-1]);p>=q;--p)*(p+1)=*p;*q=e;++(*L).length;returnOK;}statusGetElem(sqlist*L,inti,elemtype*e){(*e)=(*L).elem[i-1];returnOK;}statusList_Delete(sqlist*L,inti){//删除线性表的第i个元素if(i<1

10、

11、i>(*L).length)returnERROR;elemtype*p;elemtype*q;p=&((*L).elem[i]);q=p-1;i

12、ntnum;for(num=1;num<=((*L).length-i);num++){(*q)=(*p);p++;q++;}(*L).length--;returnOK;}statusList_Travel(sqlist*L,status(*visit)(elemtypee)){//遍历线性表中的元素inti=1;for(i=1;i<=((*L).length);i++