实验1单链表实验报告

《实验1单链表实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验一单链表一、实验目的1、掌握单链表中元素的前驱、后续的概念。2、掌握单链表的建立、插入元素、删除表中某元素的算法。3、对单链表相应算法的时间复杂度进行分析。4、理解单链表数据结构的特点（优缺点）。二、实验内容说明以下概念单链表：用一组任意的存储单元存储线性表的数据元素。以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素或数据元素的映象)指针域数据域结点结点和单链表的C语言描述typedefstrucLNode{//定义单链表结点ElemTypedata;structLNode*next；//指向后继的指针域}LNode,*LinkList(*p)表示p所指向的结点(

2、*p).dataÛp->data表示p指向结点的数据域(*p).nextÛp->next表示p指向结点的指针域1、线性表的操作ListInsert(&L,i,e)在单链表中的实现：有序对改变为和ai-1eai-1eeai-1eai-1ai-1ai-1eai-1ai-1ai-1eai-1ai-1ai在单链表中第i个结点之前进行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。算法的时间复杂度为:O(ListLength(L))2、线性表的操作ListDelete(&L,i,&e)在链表中的实现:在单链表中删除第i个结点的基本操作

3、为:找到线性表中第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算法的时间复杂

4、度为:O(ListLength(L))3、单链表的优点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间插入、删除操作方便4、单链表的缺点指针占用额外存储空间不能随机存取，查找速度慢5、插入函数程序intListInsert(LinkListL,inti,ElemTypee){LNode*p,*s;intj;p=L;j=0;while(p&&jnext;++j;}if(!p

5、

6、j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return

7、OK;}4、删除函数程序intListDelete(LinkListL,inti){LNode*p,*q;intj;p=L;j=0;while(p->next&&jnext;++j;}if(!(p->next)

8、

9、j>i-1)returnERROR;q=p->next;p->next=q->next;free(q);returnOK;}三、运行结果