单链表.docx

单链表.docx

《单链表.docx》由会员分享，可在线阅读，更多相关《单链表.docx（8页珍藏版）》请在冰点文库上搜索。

单链表

  线性表操作在单链表上的实现

  如前所述，单链表可以由静态或动态产生的独立结点构成，也可以由静态或动态产生的

数组中的元素结点构成，下面分别对每一种情况给出操作实现，最后给出简单应用举例。

  每个单链表都有一个表头指针，假定用HL表示，由表头指针可以访问到单链表中的任

何结点，所以要对单链表进行操作，必须给出表头指针。

假定以HL为表头指针的单链表是

由LNode类型的动态结点所组成，并且不带有表头附加结点，下面给出对线性表抽象数据类

型中列举的每一操作在单链表上的具体实现（即C++算法）。

  1．初始化单链表

voidlnitList（LNode*&HA）

{

  HL=NULL；//将单链表置空

  2．删除单链表中的所有结点，使之成为一个空表    

  删除单链表中的所有结点，需要遍历单链表，通过delete操作释放被访问的每一个结

点，然后把表头指针置为空。

    voidClearList（LNode*&HL）

LNode*cp，*np；  //用cp作为指向当前结点（即待处理结点）的指针

    //（currentpointer），用叩作为指向当前结点

    //的后继结点的指针（nextpointer）

cp=HL；  //表头指针赋给cp

while（cp!

=NULL）//遍历单链表，向系统交回每一个结点

np=cp->next；//保存下一个结点的指针

deletecp；//删除当前结点      

cp=np；//使下一个结点成为当前结点

HL=null;//置单链表为空

3．得到单链表的长度

  由于在单链表的构成中，没有给出单链表的长度，所以此算法需要遍历单链表，对被访

问的结点进行计数，最后返回这个计数值。

    intListSize（LNode*&HL）／／形参HL最好采用值参，因为算法中不需要。

    //修改HL所对应的实参，另外，调用时只需要复制一个指针（即4

    //个字节），它同使用引用参数传送时需要复制一个实参地址的工

    //作量相同，由此没有增加值参传送的复制量

{LNode*p=HL；    

inti=0；  //用来统计结点的个数

while（p!

=NULL）  //遍历单链表，统计结点数

{i++；

p=p->next；}

returni；

}

4检查单链表是否为空    

intListEmpty（LNode*HL）

return（HL==NULL）；

    5．得到单链表中第pos个结点中的元素

    要访问单链表中的第pos个结点，必须从表头开始依次访问过该结点之前的所有结点

后才能够实现，即只能够采用顺序存取，而不能够随机存取任一个结点。

    ElemTypeGetElem（LNode‘HL，intpos）    ’

{

if（pos<1）{

    cerr<<”posisoutrange!

”<

    exit

（1）;

}

LNode*p=HL；

inti=0；//统计已遍历的结点数

while（p!

=NULL）{

if（i==pos）break；

p=p->nextif（p!

=NULL）  

    returnp->data；

    else{

      cerr<<"posisoutrange!

"<

      exit

（1）;

}

}

6．遍历一个单链表

假定在遍历一个单链表时是打印出每个结点的值。

voidTraverseList（LNode*&HL）

{

LNode*p=HL；

while（p!

=NULl）{

    cout<data<<””；

cout<

}

7从单链表中查找具有给定值的第一个元素

intfind（LNode*HL，  ElemType&item）

LNode*p=HL；    

while（p!

=NULL）//遍历单链表，直到查找成功或查找失败为止

    if（p->data==item）{    

    item=p->data;

    return1；    

    }

    else

    p=p->next;

return0；

}

8.更新单链表中具有给定值的第一个元素

intUpdate（LNode*&HL，constElemType&item）

LNode*p=HL；    

while（p!

=NULL）//查找元素

    if（p->data==item）

    break；

else

    p=p->next；

if（p==NULL）

    return0;//没有被更新的元素，返回0

else//更新元素    ．

p->data=item；

returnl；

    9．向单链表的末尾添加一个元素    

    由于在单链表的构成中没有给出指向表尾结点的指针，所以要向表尾添加元素结点，则

必须从表头开始遍历整个单链表后得到指向表尾结点的指针，然后把新结点的存储地址赋

给表尾结点的指针域完成插入。

voidlnsertRear（LNodew&HL，constElemType&item）

{

LNodewnewptr；

newptr=newLNode；  //为保存新元素分配动态结点，newptr指向这个

    //结点

  if（newptr==NULL）//若未分配到结点，则停止插入，退出程序运行

{cerr<<“MemoryallOcationfailare!

"<

exit

（1）；

}  

newptr->data=item;

newptr->next=NULL;

if（HL==NULL）

把新元素赋给动态结点  *newptr的值域

//给动态结点的指针域置空

HL=newptr；  //向空表插入的结点为表头结点

else{

LNode*p=HL；

while（p->next!

=NULL）//从表头开始遍历到最后一个结点为止

  p=p->next；      

  p->next=newptr；//把新结点链接到表尾

10．向单链表的表头插入一个元素

  此操作不需要像顺序裘（即顺序存储的线性表）那样移动所有元素，只需修改新元素结

点的指针域，使之指向原有单链表，修改表头指针，使之指向新元素结点。

    voidlnsertFront（LNode*&HL，constElemType&item）

{

if（newptr==NULL）//若未分配到结点，则停止插入，退出程序运行

cerr<<"Memoryallocationfailare!

”<

exit

（1）；

newptr->data=item；

newptr->next=HL；

HL=newptr；

11．向单链表中满足条件的位置插入一个元素

其插入过程为：

（1）为新元素动态分配结点并赋值；

（2）从表头开始顺序查找新元素的插入位置，在查找过程中必须保留待查结点的前驱

的指针，以便插入使用；

（3）在插入位置上完成插入操作，插入位置是否在表头，应进行不同处理。

    voidInsert（LNode*&HL，constElemType&item）

{//实现第

（1）步操作  

    LNode*newptr；

    newptr=newLNode；

    if（newptr==NULL）

cerr<<"Memoryallocationfailare!

"

exit

（1）；  

newptr->data=item；

//实现第

（2）步操作      

  LNode*cp；//用cp指向当前结点（即待查结点）

  LNode*ap；//用ap作为指向当前结点的前驱结点的指针（ahead

            //pointer）    

  ap=NULL；cp=HL；

  //令当前结点为表头结点，此时无前驱结点，所以置ap指针为空  

  while{cp！

=NULL）    

    if（itemdata）    

    break；

    else//使当前结点成为前驱结点，使当前结点的后继成为当前结点

    //从而实现顺序向后比较  

ap=cp；

cp=cp->next；

//实现第（3）步操作

  if（ap==NULL）    

  {//把新结点插入到表头，包括原表为空的情况

    newptr->next=HL；

HL=newptr；

{//把新结点插入到非表头位置，即插入到ap和cp结点之间

    newptr->next=cp；  

    ap->next=newptr；  

12．从单链表中删除表头元素  

    从单链表中删除表头元素既不需要查找元素，又不需要移动元素，只需要修改表头指针

且p可。

    ElemTypeDeleteFront（LNode*&HL）    

{

if（HL==NULL）{

    cerr<<"Deletingfromanemptylist!

"<

  exit

（1）；

}  

LNode*p=HL；//暂存表头结点指针，以便使用    

HL=HL->next；//使表头指针指向第2个结点

ElemTypetemp=p->data；//暂存原表头元素，以便返回

deletep；//回收被删除的表头结点

returntemp；//返回第一个元素的值

}    

13．从单链表中删除等于给定值的第一个元素

    删除算法的执行步骤为：

（1）若单链表为空则返回假；    

（2）从单链表中顺序查找与给定值相等的第一个元素，直到查找成功或失败为止，在查

找过程中需要保留待比较结点（即当前结点）的前驱结点的指针，以便删除结点时使用；

    （3）如果查找失败则返回假；

    （4）删除查找到的结点，对表头结点和非表头结点要做不同处理；

    （5）回收被删除的结点；

    （6）返回真表明删除成功。

    intDelete（LNode*&HL，constElemType&item）

{

//实现第

（1）步操作

  if（HL==NULL）{

    cerr<<"HLiSNULL!

"<

    return0；

    }

//实现第

（2）步操作

LNode*ap，*cp;；

ap=NULL；cp=HL；

while（cp!

=NULL）

    if（Cp->data==item）

    break；

else//使前驱指针和当前指针均指向下一个结点

{

ap=cp；

cp=cp->next；

}

//实现第（3）步操作

  if（cp==NULL）{

    cerr<<"DeletedelementiSnotexist!

"<

    return0；    

    }

//实现第（4）步操作    

  if（ap==NULL）  //由cp指向的被删除结点是表头结点

    HL=HL->next;

  else  //由cP指向的被删除结点是非表头结点  ，

    ap->next=cp->next；    

//实现第（5）步操作

  deletecp;

//实现第六步操作

return1;

}

  14．利用单链表进行数据排序

  假定待排序的n个数据存在于一维数组。

a[n]中，当利用单链表进行排序时，从空单链

表开始，每次调用Insert算法向单链表中插入数组a中的一个元素，经n次调用后，单链表成

为包含有数组a中n个元素的有序表，最后遍历单链表，把每个结点的值依次写入到数组a

voidLinkSort（ElemTypea[]，intn）

{

LNode*head=NULL;

inti;

for（i=0；i

    Insert（head，a[i]）

LNode*p=head；

i=0；    

while（p!

=NULL）{

a[i++]：

p->data；

p=p->next；

}

（End）

第1页 第2页 第3页 第4页