数据结构 单链表讲授

数据结构——第2章线性表掌握线性表的顺序存储的实现及顺序表的存储类型定义。掌握顺序表的创建、查找、插入和删除算法及算法的分析（时间复杂度）。复习本章内容2.1线性表的逻辑结构2.2线性表的顺序存储及运算实现2.3线性表的链式存储及运算实现2.3线性表的链式存储和运算实现

2.3.1单链表

2.3.2单链表上基本运算的实现

2.3.3循环链表和双向链表

2.3.4静态链表

2.3.5单链表应用举例2.3.1单链表线性表以链式存储方式存储时称为链表。存储实现：◆用一组任意的存储单元存储线性表的元素；◆利用指针存放逻辑上相邻的元素间的关系。结论：每个数据元素，除存储本身信息外，还需存储其直接后继的地址。结点

数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域2.3.1单链表相关术语单链表头指针值域指针域NULL头结点结点类型定义：

typedef

structnode{ DataType

data;

structnode*next;}LNode，*LinkList；举例：LNode*L;LinkListL;2.3.2单链表上基本运算的实现1、单链表的创建（头插入法和尾插入法）2、单链表的查找3、单链表的插入4、单链表的删除2.3.2单链表上基本运算的实现1、单链表的创建用头插入法建立单链表

◆创建一个新结点的语句◆创建一个带头结点的单链表

◆创建单链表的过程

◆结点间的连接语句2.3.2单链表上基本运算的实现1、单链表的创建用头插入法建立单链表

◆创建一个新结点的语句

LNode*s;s=newLNode;s->data=x;◆创建一个带头结点的单链表

◆创建单链表的过程

◆结点间的连接语句2.3.2单链表上基本运算的实现1、单链表的创建用头插入法建立单链表

◆创建一个新结点的语句◆创建一个带头结点的单链表

LinkListL;L=newLNode;L->next=NULL;

◆创建单链表的过程

◆结点间的连接语句2.3.2单链表上基本运算的实现1、单链表的创建用头插入法建立单链表

◆创建一个新结点的语句◆创建一个带头结点的单链表

◆创建单链表的过程

◆结点间的连接语句

LinkListL;s->next=L->next;L->next=s;2.3.2单链表上基本运算的实现1、单链表的创建LinkListCreat_LinkList1(){LinkListL；L=newLNode;L->next=NULL;

Lnode*s;DataTypex;

cin>>x;while(x!=flag)//flag是结束标志！

{s=newLNode;s->data=x;s->next=L->next;L->next=s;

cin>>x;}returnL;}2.3.2单链表上基本运算的实现1、单链表的创建LinkListCreat_LinkList1(){LinkListL；L=newLNode;L->next=NULL;

Lnode*s;DataTypex;

cin>>x;while(x!=flag)//flag是结束标志！

{s=newLNode;s->data=x;s->next=L->next;L->next=s;

cin>>x;}returnL;}LinkListCreat_LinkList1(){LinkListL；

L=newLNode;L->next=NULL;

Lnode*s;DataTypex;

cin>>x;2.3.2单链表上基本运算的实现1、单链表的创建LinkListCreat_LinkList1(){LinkListL；L=newLNode;L->next=NULL;

Lnode*s;DataTypex;

cin>>x;while(x!=flag)//flag是结束标志！

{s=newLNode;s->data=x;s->next=L->next;L->next=s;

cin>>x;}returnL;}while(x!=flag)//flag是结束标志！

{s=newLNode;s->data=x;s->next=L->next;L->next=s;

cin>>x;}returnL;2.3.2单链表上基本运算的实现1、单链表的创建用尾插入法建立单链表

◆创建一个新结点的语句◆创建一个带头结点的单链表

◆创建过程

◆结点间的连接语句

Lnode*r;

//指向已建成单链表的最后一个结点

s->next=NULL;r->next=s;r=s;LinkListCreat_LinkList2(){LinkListL;L=newLNode;L->next=NULL;

Lnode*s,*r=L;DataTypex;cin>>x;while(x!=flag){s=newLNode;s->data=x;r->next=s;r=s;

cin>>x;}r->next=NULL;returnL;}2.3.2单链表上基本运算的实现

LinkListCreat_LinkList2(){LinkListL;L=newLNode;L->next=NULL;

Lnode*s,*r=L;

DataTypex;cin>>x;LinkListCreat_LinkList2(){LinkListL;L=newLNode;L->next=NULL;

Lnode*s,*r=L;DataTypex;cin>>x;while(x!=flag){s=newLNode;s->data=x;r->next=s;r=s;

cin>>x;}r->next=NULL;returnL;}2.3.2单链表上基本运算的实现

while(x!=flag){s=newLNode;s->data=x;r->next=s;r=s;

cin>>x;}r->next=NULL;returnL;2.3.2单链表上基本运算的实现1、单链表的创建用尾插入法或头插入法建立的单链表都是带头结点的。如何用头插入法和尾插入法建立不带头结点的单链表，两种算法有什么区别？结论：？创建带头结点的单链表可简化链表操作。2.3.2单链表上基本运算的实现2、查找操作按序号查找

◆查找成功返回指向该结点的指针，不成功返回空值。

◆查找过程◆特殊情况判断2.3.2单链表上基本运算的实现2、查找操作按序号查找

◆查找成功返回指向该结点的指针，不成功返回空值。

◆查找过程

Lnode*p=L->next;intj=1;

while(p!=NULL&&j<i){p=p->next;j++;}◆特殊情况判断2.3.2单链表上基本运算的实现2、查找操作按序号查找

◆查找成功返回指向该结点的指针，不成功返回空值。

◆查找过程◆特殊情况判断

（1）单链表是空表（2）i不合法（1<=i<=单链表长度）LNode*Get_LinkList(LinkListL,inti){LNode*p=L->next;

intj=1;

if(i<1)returnNULL;while(p!=NULL&&j<i){p=p->next;j++;}if(p!=NULL)returnp;elsereturnNULL;}2、查找操作2.3.2单链表上基本运算的实现2.3.2单链表上基本运算的实现2、查找操作按值查找Locate_LinkList(L,x)

◆查找成功返回指向该结点的指针，不成功返回空值。

◆查找过程

◆特殊情况判断：单链表是否是空表

◆实现算法LNode*Locate_LinkList(LinkListL,DataTypex){LNode*p=L->next;while(p!=NULL&&p->data!=x)p=p->next;returnp;}2、查找操作2.3.2单链表上基本运算的实现3、插入操作插入运算：Insert_LinkList(L,i,x)插入结点：将新结点s插入到p结点（第i个）位置2.3.2单链表上基本运算的实现3、插入操作插入结点过程首先要找到p的前驱q，然后将s插入在q之后。操作：q=L;//单链表头指针为Lwhile(q->next!=p)q=q->next;s->next=q->next;q->next=s；2.3.2单链表上基本运算的实现3、插入操作插入运算：Insert_LinkList(L,i,x)插入过程：1、创建新结点，找到第i-1个结点，进行插入。2、插入位置不合法（1<=i<=单链表的长度+1）算法实现2.3.2单链表上基本运算的实现2.3.2单链表上基本运算的实现3、插入操作int

Insert_LinkList(LinkListL,inti,DataTypex){LNode*p,*s;

p=Get_LinkList(L,i-1);

if(p==NULL){cout<<“参数i错”<<endl;return0;}else{s=newLNode;s->data=x;s->next=p->next;p->next=s;return1;}}有没有问题？2.3.2单链表上基本运算的实现3、插入操作int

Insert_LinkList(LinkListL,inti,DataTypex){LNode*p,*s;

if(i==1)p=L;elsep=Get_LinkList(L,i-1);

if(p==NULL){cout<<“参数i错”<<endl;return0;}else{s=newLNode;s->data=x;s->next=p->next;p->next=s;return1;}}3、插入操作插入运算：Insert_LinkList(L,i,x)插入过程：算法实现：性能分析：时间复杂度为o(n)2.3.2单链表上基本运算的实现4、删除操作删除运算：Del_LinkList(L,i)算法过程：1、找到第i-1个结点；进行删除；释放空间。2、删除位置不合法（1<=i<=单链表长度）算法实现：2.3.2单链表上基本运算的实现2.3.2单链表上基本运算的实现4、删除操作int

Del_LinkList(LinkList

L,inti){LNode*p=L,*q;intj=0;

if(i<1){cout<<“结点不存在!”;return-1;}

while((p->next!=NULL)&&(j<i-1)){p=p->next;j++;}if(p->next==NULL){cout<<“结点不存在!”;return0;}else{q=p->next;p->next=q->next;deleteq;return1;}}4、删除操作删除运算：Del_LinkList(L,i)算法过程：1、找到第i-1个结点；进行删除；释放空间。2、删除位置不合法（1<=i<=单链表长度）

3、需要保留被删除元素。算法实现：2.3.2单链表上基本运算的实现2.3.2单链表上基本运算的实现3、插入操作int

Del_LinkList(LinkList

L,int

i,DataType

&x){LNode*p=L,*q;intj=0;

if(i<1){cout<<“结点不存在!＂;return-1;}

while((p->next!=NULL)&&(j<i-1)){p=p->next;j++;}if(p->next==NULL){cout<<“结点不存在!＂;return0;}else{q=p->next;x=q->data;

p->next=q->next;deleteq;return1;}}4、删除操作删除运算：Del_LinkList(L,i)算法过程：算法实现：性能分析：时间复杂度O(n)2.3.2单链表上基本运算的实现总结：创建新结点时动态分配空间。查找结点只能顺序查找，不能随机查找。进行插入和删除操作时都需要先找到进行插入和删除的结点的前驱结点，通过移动指针实现。链表进行操作时，不要随意移动头指针。与位置相关的操作一定要判断位置的合法性。2.3.2单链表上基本运算的实现2.3线性表的链式存储和运算实现

2.3.1单链表

2.3.2单链表上基本运算的实现

2.3.3循环链表和双向链表

2.3.4静态链表

2.3.5单链表应用举例2.3.3循环链表和双向链表循环单链表是指将链表中最后一个结点的指针指向表头结点或第一个结点，使链表构成环状。特点：从表中任一结点出发均可找到表中其他结点，提高查找效率。HH2.3.3循环链表和双向链表循环单链表的操作与单链表基本一致，不同之处在于算法中对链表为空的判断条件发生变化：单链表：p->next=NULL循环链表：p->next=LHH^2.3.3循环链表和双向链表双向链表：构成链表的结点中包含两个指针域，分别指向该结点的前驱结点和后继结点。H

^^H^^2.3.3循环链表和双向链表

双向链表结点类型定义：typedef

struct

dnode{

DataTypedata;

struct

dnode

*prior,*next;}DLNode,*DLinkList;2.3.3循环链表和双向链表

双向链表主要操作

双向链表中通过某结点的指针p即可以直接得到它的后继结点的指针p->next，也可以直接得到它的前驱结点的指针p->prior。p->prior->next==p==p->next->prior2.3.3循环链表和双向链表

双向链表主要操作

双向链表插入：将新结点s插入在p的前面。①s->prior=p->prior;②p->prior->next=s;③s->next=p;④p->prior=s;

2.3.3循环链表和双向链表

双向链表主要操作

双向链表删除：删除p结点。①p->prior->next=p->next;②p->next->prior=p->prior;③deletep;2.3线性表的链式存储和运算实现

2.3.1单链表

2.3.2单链表上基本运算的实现

2.3.3循环链表和双向链表

2.3.4静态链表

2.3.5单链表应用举例2.3.4静态链表

静态链表

将单链表中结点的指针用相对地址来描述，即数组的下标。2.3.4静态链表

静态链表

数组sd定义：

#defineMAXSIZE…typedef

struct

{DataTypedata;

intnext;}SNode;SNode

sd[MAXSIZE];

intSL,AV;