数据结构与算法第3讲

华中

理学院

章

英zy数据结构与算法2/40第三讲单链表本讲知识点：(1)熟悉单链表的创建方法(2)掌握单链表的各类操作(3)了解链表的相关应用重点：单链表的操作难点：单链表的应用已知线性链表la和lb中的数据元素按值递增，现要将la和lb合并为新的线性表lc，使lc中的数据元素仍然递增有序。la提出问题281219……13/4037∧lb线性链表的形成需要什么的支撑？如何初始化，使其

起来？合并时指针的移动规则是什么？分析问题4/40链表中的结点解决问题ZHAOQIANSUNLIZHOUWUZHENGWANG^HWU5/406/40template

<class

ElemType>struct

Node{//数据成员:ElemType

data;

//数据域Node<ElemType>

*next;

//指针域//构造函数:Node();

//无参数的构造函数Node(ElemType

item,

Node<ElemType>

*link

=NULL);//已知数据域和指针域建立结构};结点类参见文件夹S2_3里的文件node.h7/40申请一个结点空间Node*p；p

=

new

Node;或者p=new

Node(“WU”,NULL);WU^p例如：8/40template

<class

ElemType>class

SimpleLinkList{protected://

链表实现的数据成员:Node<ElemType>*head;

//头结点指针//辅助函数Node<ElemType>

*Ge emPtr(int

position)

const;//返回指向第position个结点的指针void

Init();

//初始化线性表……

……简单线性链表类参见文件夹S2_3里的文件simple_lk_list.h9/40后面的数据暂且不看，前者的形成：Node*la,*lb；la

=new

Node;lb=

new

Node;例如：137

∧la281219……lb一、单链表之初始化void

SimpleLinkLisemType>::SimpleLinkList()//操作结果：构造一个空链表{Init();}构造函数template

<class

ElemType>10/40一、单链表之初始化template

<class

ElemType>void

SimpleLinkLis

emType>::Init()//操作结果：初始化单链表{head

=

new

Node<ElemType>;//构造头指针}head11/40头插法

演示HsC1C2HCi-1Ci-2C1^……sCix^二、单链表之创建12/40s

=

new

Node<ElemType>(e,

h->next);//生成新结点h->next

=

s;//将s

到链表的头结点之后头插法代码实现13/40法

演示H^sC1

r

CiHCi-1C1C2……r

xC1H

sr14/40^二、单链表之创建法代码实现r

=

h;s

=

new

Node<ElemType>(e,

h->next);//生成新结点r->next

=

s;//

将s

到最后r=r->next;

//或者r=s;//r后移r=h;放在循环外面仅需执行一次15/40三、单链表之查找指针定位：根据已给的表头指针，按由前向后的次序

单链表的各个结点，定位到需要的位置处。heada1a2a3a4……123一个数据元素，则指针需要定tmpPtr例如：请在4号位置位到3号位置16/4017/40指针定位过程heada1a2a3a4……tmpPtrcurPosition=012

3tmpPtr=tmpPtr->next;curPosition++;tmpPtr=tmpPtr->next;curPosition++;tmpPtr=tmpPtr->next;curPosition++;tmpPtrtmpPtrtmpPtr第一步tmpPtr=head18/40template<class

ElemType>Node<ElemType>*SimpleLinkLis

emType>::Ge emPtr(int

position)const{Node<ElemType>

*tmpPtr

=

head;int

curPosition

=0;while

(tmpPtr!=

NULL

&&

curPosition

<position){tmpPtr

=

tmpPtr->next;curPosition++;}if

(tmpPtr

!=

NULL

&&

curPosition

==

position)returntmpPtr;{else{return

NULL;//

查找成功

}//

查找失败

}}参见文件夹S2_3里的文件simple_lk_list.hheada1a2a3a4……newPtre×在单链表中第i（1<=i<=Length()+1）个结点之前

一个数据域为x的结点。

演示例如：i=3tmpPtr

tmpPtr

tmpPtr四、单链表之19/40的三个基本操作在单链表上找到

位置，即定位找到第i-1个结点。tmpPtr

=

Ge emPtr(position

-

1);生成一个以e为值的新结点。newPtr

=

new

Node<ElemType>(e,

tmpPtr->next);将新结点链入单链表中。tmpPtr->next

=

newPtr;20/400算法template

<class

ElemType>StatusCode

SimpleLinkLis

emType>::Insert(intposition,

cons

emType

&e){ if

(position

<

1||

position

>

Length()

+

1){else{//position范围错return

RANGE_ERROR;

//

位置不合法

}//position合法Node<ElemType>

*tmpPtr;tmpPtr

=

Ge emPtr(position

-

1);Node<ElemType>

*newPtr;newPtr

=

newNode<ElemType>(e,

tmpPtr->next);tmpPtr->next

=

newPtr;return

SUCCESS;}}本 采用

法创建单链表五、单链表之形成lala1la13la137∧构造函数初始化法创建1法创建3法创建722/40思考数据存放在哪里？int

a[]

=

{1,

3,

7,

9,

12};或者动态录入for(i=0;

i<n;

i++)cin>>a[i];多少个数据结点由int

n

=

5;或者cin>>n;控制？23/40本 采用

法创建单链表template

<class

ElemType>void

Create(SimpleLinkLis

emType>

&la,

ElemTypea[

],

intn)//操作结果:由数组a{la.Clear();的n个元素构造线性表//清空lafor

(intposition

=

1;

position

<=

n;

position++)la.Insert(position,

a[position

-1]);//向la

元素}五、单链表之形成24/40继续解决问题链表已经形成，如何进行合并？la137∧281219……lblc∧25/40解决问题281219……137∧lalblc12aPosition=12小bPosition=1bPosition=2aPosition=21小3小7小3aPosition=37∧aPosition=4越界26/40template

<class

ElemType>void

MergeList(const

SimpleLinkLisemType>

&la,const

SimpleLinkLisemType>

&lb,SimpleLinkLis

emType>

&lc){ElemType

aItem,

bItem;//la和lb中当前数据元素int

aLength

=

la.Length(),

bLength

=

lb.Length();//la和lb的长度int

aPosition

=

1,

bPosition

=

1;//la和lb的当前元素序号lc.Clear();//清空lc算法实现27/4028/40while

(aPosition

<=

aLength

&&

bPosition

<=bLength){

//取出la和lb中数据元素进行归并la.Gelb.Geem(aPosition,

aItem);em(bPosition,

bItem);if(aItem

<

bItem){//归并aItemlc.Insert(lc.Length()+1,aItem);aPosition++;}else{//归并bItemlc.Insert(lc.Length()+1,bItem);bPosition++;}}算法实现while

(aPosition

<=

aLength){ //归并la中剩余数据元素la.Ge em(aPosition,

aItem);lc.Insert(lc.Length()

+

1,aItem);aPosition++;}while

(bPosition

<=

bLength

){

//归并lb中剩余数据元素lb.Ge em(bPosition,

bItem);lc.Insert(lc.Length()

+

1,bItem);bPosition++;}}算法实现29/40实战：

理工2002年考研题程序阅读题阅读下面的程序，在空白处填上恰当的内容。void

Addpolyn(Slink

&Ha,

Slink

&Hb){ /*用带节点的单链表

多项式，Ha和Hb分别是两个多项式链表的指针*//*多项式加法算法：将多项式Hb加到Ha上，Ha=Ha+Hb，利用两个多项式节点构成“和多项式”*/pa=Ha;pb=Hb;qa=pa→next;

qb=pb→next;/*qa和qb分别指向Ha和Hb的当前节点，pa和pb分别指向Ha和Hb当前节点的前一个节点*/30/40HaHbpapb

qb（1）Ha的指数小qacoef域exp域……系数相加不为0系数相加为0Hb的指数小Ha与Hb的指数相等31/40while(

(qa!=NULL)

&&(qb!=NULL)){

a=qa→data;

b=qb→data;switch(cmp(a,b)){case

-1:

/*多项式Ha当前节点的指数值小*/pa=qa;qa=qa→next;break;case

0:

/*两者值相等*/sum=a.coef+b.coef;if(sum!=0.0)

{

qa→data=sum;pa=qa;}else{pa→next=qa→next;free(qa);}

(1)

;pb→next=qb→next;

free(qb);

qb=pb→next;break;32/40case

1:

/*多项式Hb当前节点的指数值小*/pb→next=qb→next;

(2)

;

(3)

;

(4)

;break;}/*

switch end

*/}

/* while

end

*/if(qb!=NULL)free(pb);/*

(5)

;Hb的头节点*/}33/40删除单链表中第position个位置的元素。两个基本操作：在单链表上找到前驱结点。从单链表上删除该结点。34/40演示六、单链表之删除35/40heada1a2a3a4……tmpPtr例如：i=3tmpPtr

tmpPtrnextPtr六、单链表之删除tmpPtr

=

Ge emPtr(position

-

1);Node<ElemType>

*nextPtr

=

tmpPtr->next;tmpPtr->next

=

nextPtr->next;e

=

nextPtr->data;delete

nextPtr;36/40删除算法template

<classElemType>StatusCode

SimpleLinkLis

emType>::Delete(intposition,

ElemType

&e){ if

(position

<

1

||

position

>

Length()){//position范围错returnRANGE_ERROR;

}else{//position合法Node<ElemType>

*tmpPtr;tmpPtr=Ge emPtr(position

-1);Node<Elem