的数据结构第二章线性表

第二章线性表

2.1线性表的类型定义☞

2.2线性表的链式表示和实现2.3线性表类型链式存储

☞2.3.1链表的基本概念

2.3.2单链表

2.3.3单循环链表

2.3.4双向循环链表

2.3.5改进的链表及基本操作

2.3.6链表的应用

2.3.1链表的基本概念☞什么是链表

链表的存储结构

什么是链表？链表——

链式存储的线性表用一组地址任意的存储单元存放线性表中的数据元素（这组存储地址可以连续或者非连续）以线性表中第一个数据元素a1的存储地址作为线性表的地址，为线性表的头指针2.3.1链表的基本概念2.3.1链表的基本概念

什么是链表☞

链表的存储结构

2.3.1链表的基本概念链表的存储结构链表中的每个数据元素称为结点

每个结点包括：

数据域——存放数据元素ai的值；

指针域——存放ai的直接后继ai＋1的地址链表正是通过每个结点的指针域将表中n个数据元素按其逻辑顺序链接在一起的链表中数据元素的逻辑顺序与其物理存储顺序不一定相同；【例】设有一组线性排列的数据元素（zhao,qian,sun,li,zhou,wu,zheng,wang），其链接存储形式下页图所示：讨论：在该存储方式下，如何找到表中任一元素？答：在链接存储方式下（链表中），每一个数据元素的存储地址是存放在其直接前驱结点的next域中，只要知道第一个数据元素（结点）zhao的存储地址，就可以“顺藤摸瓜”找到其后续的所有结点。存储地址数据域指针域………………………………………zhaolizhouzhengqianwang100sunwu160170200210220310320320210160310200220100∧头指针H170zhaozhouzhengqianlisunwuwang∧H通常情况下，我们用箭头来表示指针域中的指针，忽略每一个结点的实际存储位置，而重点突出链表中结点间的逻辑顺序，将链表直观地画成用箭头链接起来的结点序列。

2.3.1链表的基本概念

☞2.3.2单链表

2.3.3单循环链表

2.3.4双向循环链表

2.3.5改进的链表及基本操作

2.3.6链表的应用

2.3线性表类型链式存储2.3.2单链表一、定义链表的每个结点只有一个指针域——单链表data2nextdata1datanext可以有多个数据域二、单链表结点的C语言描述typedefstructLNod

{ElemTypedata;//数据域

//LNode*next;//指针域

structLNod*next;}LNode,*LinkList;

datanextLNodes;LinkListL;LNode*L;注意2者区别？？zhaozhouqianlisunzhengwuwang∧H称H为该单链表的头指针。若已知单链表的头指针，则可以搜索到表中任一结点；也就是说，单链表由头指针唯一确定。因此，单链表可以用头指针的名字来命名。上图所示的单链表可称为单链表H。

若有：在单链表的第一个结点之前设一个头结点头结点的数据域不存储数据头结点的指针域存储第一个结点的地址空链表L->next=NULL三、带头结点的单链表L28597L为什么要设头结点？答：头结点即在链表的首元素结点之前附设的一个结点，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元素结点进行统一处理，编程更方便。讨论.在链表中设置头结点有什么好处？Status

GetElem_L

(LinkListL,intpos,ElemType&e)StatusListInsert_L

(LinkListL,intpos,ElemTypee)

StatusListDelete_L(LinkListL,intpos,ElemType&e)voidCreateList_L(LinkList&L,intn)

voidCreateList_L(LinkList&L)

四、带头结点的单链表基本操作的实现

（1Union_LinkList.cpp）取第i个元素GetElem_L（L,i,&e）i=3思路：要取第i个数据元素，关键是要先找到该结点的指针p,然后输出p地址存储的数据元素的值p->data。难点：单链表中想取得第i个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取。a1a2a3anL∧PStatus

GetElem_L(LinkListL,intpos,ElemType&e){/*将第pos个数据元素的值赋给e并返回OK，否则返回ERROR*/

LinkListp=L->next;//

p指向第一个结点

j=1;//j为计数器

while(p&&j<pos){//顺指针向后查找，直到p为空或p指向第pos个元素

p=p->next;j++;}if(!p||j>pos)returnERROR;//第pos个元素不存在

e=p->data;//取第pos个元素

returnOK;}//GetElem_Lpos=3pL28597

StatusListInsert_L(LinkList&L,intpos,ElemTypee){//在带头结点的单链表L中第pos个数据元素之前插入数据元素e

LinkListp=L->next; intj=1;while(p&&j<pos-1)//寻找第pos-1个结点

{p=p->next;j++;}if(!p)returnERROR;//pos小于1或者大于表长

s=(LinkList)malloc(sizeof(LNode));//生成新结点

s->data=e;s->next=p->next;p->next=s;

//插入L中

returnOK;}

//LinstInsert_Lpos=3e=4

4spL28575StatusListDelete_L(LinkListL,intpos,ElemType&e){//在带头结点的单链表L中，删除第pos个元素，并由e返回其值

LinkListp=L->next,q; intj=1; while(p!=NULL&&j<pos) {//寻找第pos个结点，并令p指向其前趋

q=p; p=p->next; j++; } if(p==NULL||j>pos)returnERROR;//删除位置不合理

q->next=p->next;//删除并释放结点

e=p->data; free(p); returnOK;}//ListDelete_Lqpos=3pL25785voidCreateList_L(LinkList&L,intn){//逆位序输入n个元素的值，建立带表头结点的单链线性表L。

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的单链表

for(i=n;i>0;i--){p=(LinkList)malloc(sizeof(LNode));//生成新结点

scanf(“%d”,&p->data);//输入元素值

p->next=L->next;L->next=p;

//插入到表头

}}//CreateList_L8Lp8voidCreateList_L(LinkList&L,intn){//逆位序输入n个元素的值，建立带表头结点的单链线性表L。

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的单链表

q=L;//保持q指向当前表尾

for(i=1;i<=n;i++)//n=2{p=(LinkList)malloc(sizeof(LNode));//生成新结点

scanf(“%d”,&p->data);//输入元素值

q->next=p; q=p;

//插入到表尾

}q->next=NULL;}//CreateList_Lcreat之尾插：

2.3.1链表的基本概念

2.3.2单链表☞2.3.3单循环链表

2.3.4双向循环链表

2.3.5改进的链表及基本操作

2.3.6链表的应用

2.3线性表类型链式存储单循环链表最后一个结点的指针域的指针又指回第一个结点的链表怎么样判断链表为空？if(head->next==head)循环链表的操作和单链表基本一致，差别仅在于算法中的循环条件不是p或者p->next是否为空，而是p或者p->next是否等于头指针p->next=heada1headpa2带尾指针的单循环链表：a1anaiRR空表：这时：R->next==R这时：头指针为：R－>next

2.3.1链表的基本概念

2.3.2单链表

2.3.3单循环链表

☞2.3.4双向循环链表

2.3.5改进的链表及基本操作

2.3.6链表的应用

2.3线性表类型链式存储问：链表只能查找结点的直接后继，能不能找到直接前驱？答：能，只要给每个结点多开一个指针域typedefstructDuLNode

{ElemTypedata;//数据域

DuLNode*prior;//指向前驱的指针域

DuLNode*next;//指向后继的指针域}DuLNode,*DuLinkList;priordatanexta1La2a3和单循环链表类似，双向链表也可以有循环链表双向循环链表a1La2a3pp->next->prior==p->prior->next==p一个空的双向循环链表：LL->next==LL->prior==L双向循环链表的操作a1La2a3pstatusListInsert_Dul(DuLinkList&L,inti,ElemTypee)statusListDelete_Dul(DuLinkList&L,inti,ElemTypee)statusListInsert_Dul(DuLinkList&L,inti,ElemTypee)xspai-1aiai+1p->prior

(4)p->prior=s(3)p->prior->next=s(1)s->prior=p->prior(2)s->next=pstatusListInsert_Dul(DuLinkList&L,inti,ElemTypee){if(!(p=GetElemP_Dul(L,i)))returnERROR;if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))returnERROR;

s->data=e;s->prior=p->prior;s->next=p;p->prior->next=s;p->prior=s;returnOK;}//ListInsert_Dulpaiai+1ai-1

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);p->priorp->nextstatusListDelete_Dul(DuLinkList&L,inti,ElemTypee)status

ListDelete_Dul(DuLinkList

&L,inti,ElemTypee){if(!(p=GetElemP_Dul(L,i)))returnERROR;e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);returnOK;}//ListDelete_Dulpai+1ai-1aip－>priorp－>next

2.3.1链表的基本概念

2.3.2单链表

2.3.3单循环链表

2.3.4双向循环链表

☞2.3.4改进的链表及基本操作

2.3.5链表的应用2.3线性表类型链式存储单链表的表长是一个隐含的值；在单链表的最后一个元素最后插入元素时，需遍历整个链表；在链表中，元素的“位序”概念淡化，结点的“位置”概念强化。用上述定义的单链表实现线性表的操作时，存在的问题：增加“表长”和“表尾指针”两个数据域；改进链表的设置：改进的单链表类型typedefstruct

LNode{//结点类型

ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct

{//链表类型

Linkhead,tail;

//指向头结点和最后一个结点

intlen;

//指示链表长度}LinkList;headtaillendatanextheadtailLen4L

2.3.1链表的基本概念

2.3.2单链表

2.3.3单循环链表

2.3.4双向循环链表

2.3.4改进的链表及基本操作

☞2.3.5链表的应用2.3线性表类型链式存储一元多项式的表示

一元多项式pn(x)=p0+p1x+p2x2+……pnxn在计算机中，可以用一个线性表来表示:P=(p0，p1，…，pn)但是对于形如:S(x)=1+3x10000–2x20000的多项式，上述表示也就不恰当了。一般情况下的一元多项式可写成

Pn(x)=p1xe1+p2xe2+……+pmxem其中：pi是指数为ei

的项的非零系数，

0≤e1<e2<……<em=n它可以用其数据元素为(系数项，指数项)的线性表来表示（（p1，e1），(p2，e2)，……，(pm，em)）例如：线性表(

(7,3),(-2,12),(-8,999))表示多项式

P(x)=7x3-2x12-8x999抽象数据