数据结构单链表.ppt

《数据结构单链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表——链表单链表定义特点C描述基本形态基本操作实现一组数据项的集合，其中每个数据项都是一个结点的一部分，每个结点都包含指向下一个结点的链接（即指针）。1.数据元素在“逻辑关系上的相邻”用“指针”来表示。2.单链表中访问数据元素时需从头开始“顺序访问”。3.比顺序表的优势在于，提供高效地重排数据项的能力。a1a2a3a4……anL^单链表的C描述typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList;LinkListL；//L为单

2、链表的头指针头指针指向单链表中的第一个结点用指针表示链接，用结构体表示结点，结点是由数据项和链接组成的，链接是指向下一结点的指针。单链表的基本形态空表非空表为了操作方便，在第一个结点之前虚加一个“头结点”哑元结点L^L->next==NULL;不允许删除操作a1a2a3……anL^可以进行插入、删除操作单链表基本操作1、初始化（动态分配）StutasInitList(LinkList&L){L=(LinkList)malloc(sizeof(LNode));if(!L)exit(overflow);L->next=NULL;retu

3、rnOK;}L头结点L211830754256∧pppj123单链表基本操作2、取单链表中指定位序的数据元素演示例子：取单链表中第3个元素值取元素的基本操作单链表是一种“顺序访问”的结构，为找第i个数据元素，必须先找到第(i-1)个数据元素。1.指针p始终指向单链表中第j个结点；2.移动指针，比较j和i，相等则找到。StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素}//GetElem_L算法时间复杂度为:O(ListLength(L))p=L->

4、next;j=1;//p指向第一个结点，j为计数器while(p&&jnext;j++;}//顺指针向后查找，直到p指向第i个元素//或p为空if(p&&j==i){e=p->data;returnOK;//取得第i个元素}else{//第i个元素不存在returnERROR;}与顺序表相比，链表不适合于查找第i个元素的操作。单链表基本操作3、插入（在第i个元素前插入e）单链表中：ai-1有序对改变为和eaiai-1在单链表中插入结点只需要修改指针。若要在第i个结点之前

5、插入元素，修改的是第(i-1)个结点的指针。StatusListInsert_L(LinkList&L,inti,ElemTypee){//L为带头结点的单链表的头指针，本算法//在链表中第i个结点之前插入新的元素e}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))……}elsereturnERROR;p=L;j=0;while(p&&jnext;++j;}//寻找第(i-1)个结点if(p&&j==i-1){s=(LinkList)malloc(sizeof(LNode));

6、//生成新结点s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sp有序对和改变为ai-1aiai+1ai-1单链表基本操作4、删除（第i个元素）在单链表中删除第i个结点时，要找到单链表中第(i-1)个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p->next;p->next=q->next;e=q->data;free(q);pqStatusListDelete_L(LinkList&L,

7、inti,ElemType&e){//删除以L为头指针(带头结点)的单链表中第i个结点}//ListDelete_L算法的时间复杂度为:O(ListLength(L))p=L;j=0;while(p->next&&jnext;++j;}//寻找第i-1个结点，并令p指向它。if(p->next&&j==i-1){q=p->next;p->next=q->next;//删除并释放结点e=q->data;free(q);returnOK;}elsereturnERROR;//删除位置不合理对比单链表和顺序表的基本操

8、作插入和删除的简单性是链表存在的理由只修改相关结点的指向保持链表特性单链表的访问方式是顺序访问查找第i个数据项的代价，沿着链表，一个一个结点地访问，直到找的这个数据项算法时间复杂度：O(ListLength(L))单链表基本操作5、清