资源描述：
《《算法与数据结构(实践)》.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、辽宁省高等教育自学考试软件技术（应用本科）专业课程设计报告书课程名称算法与数据结构（实践）助学单位信息技术学院姓名刘佳旭准考证号7成绩二Ｏ一一年四月实验1顺序表的应用实训目的 1、掌握顺序表的定义及操作的C语言实现方法2、掌握相关操作的基本思想及其算法。实验要求1、线性表的基本概念和基本运算。2、顺序表的存储结构和查找、插入、删除等基本运算。3、单链表的存储结构以及单链表的建立、查找、插入删除等操作。4、双向链表的存储结构以及插入、删除操作。5、静态链表的存储结构和基本运算。6、利用线性表的基本运算解决复杂问题。实验步聚1.创建和销毁顺序表存储结构。创建一个顺序
2、表在顺序表的指定位置插入一个元素；在顺序表的指定位置删除一个元素；将两个有序顺序表合并成一个新的有序顺序表-Linearsequenceofstorage,saidtable(structure)andrealizethecreationofachronologicaltable(datafromtheproposed)intheorderoftableelementstoinsertaspecifiedlocationinorderoftableelementstodeleteaspecifiedlocationwillmergetwotablesinanorde
3、rlysequenceintoanewtableinanorderlysequence销毁线性表voidDestroy_SeqList(PSeqListSeqListPoint){/*销毁顺序表，入口参数：为要销毁的顺序表指针地址，无返回值*/if(SeqListPoint)//SeqListPoint=NULL;return; }设调用函数为主函数，主函数对初始化函数和销毁函数的调用如下：main(){PSeqListSeqListPoint;SeqListPoint=Init_SeqList();……Destroy_SeqList(SeqListPoint);
4、}2.实现顺序表的基本操作，如插入、删除、查找和遍历等。 具体插入算法描述如下： InsertList(SeqList*L,inti,DataTypex) {//在顺序表L中第i个位置之前插入一个新结点x if(i<1
5、
6、i>L->length+1) {printf("positionerror");return;} if(L->length>=ListSize) {printf("overflow");return;} for(j=L-length-1;j>=i-1;j--) L->data[j+1]=L->data[j];
7、 //从最后一个结点开始逐一后移 L->data[i-1]=x;//插入新结点x L->length++;//实际表长加1 } 从上述的算法以及插入过程图中可以看出，一般情况下，在第i(1≤i≤n)个结点之前插入一个新结点时，需要进行n-i+1次移动。而该算法的执行时间花在for循环的结点后移上，因此，该算法的时间复杂度不仅依赖于表的长度n，而且还与结点的插入位置i有关。当i=n+1时，for循环不执行，无需移动结点，属于最好情况，其时间复杂度为O(1)；当i=1，循环需要执行n次，即需要移动表中所有结点，属于最坏情况，算法时间复杂度为O(n)。由于插
8、入结点可在表的任何位置上进行，因此需要分析讨论算法的平均移动次数。 假设pi是在第i个结点之前插入一个结点概率，则在长度为n的线性表中插入一个结点时所需要移动结点次数的期望值(平均次数)为: 不失一般性，我们假定在线性表的任何位置上插入结点的机会是相等的，即是等概率的，则有： p1=p2=…=pn+1=1/(n+1)因此，在等概率情况下插入需要移动结点的平均次数为：恰好是表长的一半，当表长n较大时，该算法的效率是相当低的。因为Eis(n)是取决于问题规模n的，它是线性阶的，因此算法的平均时间复杂度是O(n)。 例如，假定一个有序表A=(23,31,46,
9、54,58,67,72,88)，表长n=8。当向其中插入56时，此时的i等于5，因此应插入到第i-1个位置上，从而需要将第i-1个元素及之后的所有元素都向后移动一位，将第i-1个元素位置空出来，插入新元素。插入后的有序表为(23,31,46,54,56,58,67,72,88)。按上述移动次数的计算公式，可知本插入操作需要移动n-i+1=8-5+1=4次。 删除结点运算的算法如下： DataTypeDeleteList(SeqList*L,inti) {//在顺序表L中删除第个结点，并返回删除结点的值 if(i<1
10、
11、i>L->length) {
