实验1单链表实验报告.doc

实验一 单链表 1、 实验目的1、 掌握单链表中元素的前驱、后续的概念。2、 掌握单链表的建立、插入元素、删除表中某元素的算法。3、对单链表相应算法的时间复杂度进行分析。4、理解单链表数据结构的特点（优缺点）。 二、实验内容说明以下概念单链表：用一组任意的存储单元存储线性表的数据元素。以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素或数据元素的映象)指针域数据域 结点结点和单链表的 C 语言描述typedef struc LNode / 定义单链表结点 ElemType data; struct LNode *next； / 指向后继的指针域LNode, *LinkList(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).nextp-next表示p指向结点的指针域1、线性表的操作ListInsert(&L, i, e) 在单链表中的实现：有序对 改变为 和ai-1 eai-1 e eai-1 eai-1ai-1ai-1 eai-1ai-1ai-1 eai-1ai-1ai在单链表中第 i 个结点之前进行插入的基本操作为: 找到线性表中第i-1个结点，然后修改其指向后继的指针。算法的时间复杂度为: O(ListLength(L)2、线性表的操作ListDelete (&L, i, &e) 在链表中的实现:在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。有序对 和 改变为 q = p-next; p-next = q-next; e = q-data; free(q);ai-1aiai+1ai-1pai-1aiai+1ai-1pai-1aiai+1ai-1pai-1aiai+1ai-1pai-1pai-1aiai+1ai-1ai-1aiai+1ai-1ai-1aiai+1ai-1ai-1aiai+1ai-1ai-1qai-1aiai+1ai-1ai-1aiai+1ai-1ai-1aiai+1ai-1ai-1aiai+1ai-1ai-1 算法的时间复杂度为: O(ListLength(L)3、 单链表的优点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间插入、删除操作方便4、单链表的缺点指针占用额外存储空间不能随机存取，查找速度慢5、插入函数程序int ListInsert(LinkList L,int i,ElemType e) LNode *p,*s; int j; p=L; j=0; while(p&jnext;+j;if(!p|ji-1) return ERROR;s=(LinkList) malloc ( sizeof(LNode) );s-data=e; s-next=p-next; p-next=s;return OK;4、删除函数程序int ListDelete(LinkList L,int i)LNode *p,*q; int j; p=L; j=0;while(p-next&jnext;+j;if(!(p-next)