7.2 链表与链表的基本操作链表与链表的基本操作 线性表线性表是最简单，最常用的一种数据结构。线性表的是最简单，最常用的一种数据结构。线性表的逻辑结构是逻辑结构是n个数据元素的有限序列（个数据元素的有限序列（a1,a2,an）。而）。而线性表的线性表的物理结构物理结构包括：顺序表包括：顺序表(数组数组)，链表链表 。7.2.1 单链表基本算法单链表基本算法 7.2.3 双向链表双向链表(选读选读)浓甫筋嚼厘难幸行草沦掖热炬脂犬兔唱兔苔据损劈环署怪汝埔祭玛素叶毯链表与链表的基本操作链表与链表的基本操作7.2.1 单链表基本算法单链表基本算法单链表单链表（Singly Linked list）：）： 有有若若干干结结点点（Node）组组成成。一一个个结结点点包包含含info和和link两两个个域域，info域域存存放放数数据据，类类型型由由应应用用决决定定；link存存放放指指向向该该链链表中下一个结点的地址。表中下一个结点的地址。结点定义如下：结点定义如下： typedef int DataType; /数据为整型数据为整型struct Node DataType info; Node *link;在在C/C+中允许一个类型（结构体或类）的数据成员是中允许一个类型（结构体或类）的数据成员是自身自身的指针类型的指针类型，但决不能是自身类型但决不能是自身类型，这会导致一个无穷递归，这会导致一个无穷递归的定义。的定义。 桩龄咸玄伙裕受淡铂鹰批险锨喻捐咸祷桩喧碴污面然孙手腻竭停津悦启梢链表与链表的基本操作链表与链表的基本操作 7.2.1 单链表基本算法单链表基本算法通常使用表头指针通常使用表头指针head指向单链表的第一个结点，指向单链表的第一个结点，head在在使用中千万不可丢失，否则链表整个丢失，内存也发生泄漏。使用中千万不可丢失，否则链表整个丢失，内存也发生泄漏。infon-1 info2 info1 info0 head图图7.3 单链表结构单链表结构 单链表的插入与删除：单链表的插入与删除： 只要改变链中结点指针的值，无需移动表中的结点，就只要改变链中结点指针的值，无需移动表中的结点，就能实现插入和删除操作。能实现插入和删除操作。若考虑在链表中包含数据若考虑在链表中包含数据info的结点之前插入一个新元的结点之前插入一个新元素，则有素，则有三种三种情况：情况：info位于第一个结点；位于中间某个结点；没找到位于第一个结点；位于中间某个结点；没找到info。 碧幽升棘勃祸娄盅庭红功赐批嚣扁阁作坍考粪蛊烁撅萍郧梢蕊积救厌纺陈链表与链表的基本操作链表与链表的基本操作7.2.1 单链表基本算法单链表基本算法infoxinfo0info1headhead插在链首：插在链首： 首首先先新新结结点点的的link指指针针指指向向info0所所在在结结点点，然然后后，head指指向向新结点。即：新结点。即：newnode-link=head；head=newnode； /注意：链表操作次序非常重要注意：链表操作次序非常重要newnodenewnodehead注意：访问符注意：访问符“.”与与“-”的的区别。区别。p-link: p为结点指针；为结点指针；n.link: n为结点为结点;p-link等价于等价于(*p).link。忧韵卷词邑起框斥啃佰册函虽宵滦抿伎钧鸳摘徊剩皇任籍监咎怀惰熊隘桌链表与链表的基本操作链表与链表的基本操作7.2.1 单链表基本算法单链表基本算法infoxinfoi-1infoinewnodenewnode插在中间：插在中间： 结点型指针结点型指针q为为指向指向infoi-1的工作指针，的工作指针，则：则：newnode-link=q-link；q-link=newnode；脆纽沫暇器襟岸腋唇山胳酿悲携航超妇再栽撞君瓷慈辐诱匿尼督垛绷价惫链表与链表的基本操作链表与链表的基本操作7.2.1 单链表基本算法单链表基本算法infoinfox x newnodenewnodepinfoinfon-1n-1 插在队尾：插在队尾：只要工作指针只要工作指针p找到队尾，即可链在其后：找到队尾，即可链在其后：p-link=newnode；newnode-link=NULL;训抒己街妓沾拴藤罪恒下纫钝链能溢振酋瓮邵跟捆往颧稚舅纠挛犬裴旬册链表与链表的基本操作链表与链表的基本操作7.2.1 单链表基本算法单链表基本算法带表头结构的链表：带表头结构的链表：通通过过给给每每一一个个链链表表加加上上一一个个表表头头结结点点，可可以以提提高高结结点点插插入入操操作作的通用性。的通用性。空表如下：空表如下：headinfo0Infon-1info1head 下面将介下面将介绍绍带带表表头结头结构构的的链链表的各种基本算法。表的各种基本算法。 tailhead遣侯妙蚁馆蔑终蔚懊龚喝抠开毁怔夕愉轮赎漂球蜂演钮究颂渣腊线疗鸥平链表与链表的基本操作链表与链表的基本操作7.2.1 单链表基本算法单链表基本算法tailpinfo1tailptail1.1.建立链表头节点建立链表头节点Node* CreatHead() Node *head,*tail; head=new Node; /建立链表头建立链表头 tail=head; head-link=NULL; return head;2.2.链表向后生长一个结点链表向后生长一个结点Node*GrowDN(Node*tail,DataType data) Node* p=new Node; /建立结点建立结点 p-info=data; tail-link=p; tail=p; tail-link=NULL; return tail;headtailinfo0head顷筷梆伶头周官瑶玩物芋馆辞胚粱芥提滩鲍床沧樱篙于魔肖槐层奇守艰继链表与链表的基本操作链表与链表的基本操作7.2.1 单链表基本算法单链表基本算法headinfo0 PPinfo13.3.链表向前生长一结点链表向前生长一结点void GrowUP(Node*head,DataType data) Node* p=new node; p-info=data; p-link= head-link ; /新结点放在原链表前方新结点放在原链表前方 head-link=p; /头结点放新结点之前头结点放新结点之前 马贺屎幢隘挖灸酸席芳珐希属肠帚券版疡颅盔兹托梗猩姿唯队该案躁乏讣链表与链表的基本操作链表与链表的基本操作7.2.1 单链表基本算法单链表基本算法4. 4. 链表遍历查找链表遍历查找( (按关键字按关键字) )Node*TravFind(Node*head, DataType key)Node *p=head-link;while(p!=NULL&p-info!=key)p=p-link; /移动移动p preturn p; /返回指针返回指针p p，指向找到的结点，或者未找到，返回，指向找到的结点，或者未找到，返回NULLNULL5. 5. 链表节点链表节点p p后插入新节点后插入新节点：注意与向前向后生长算法的区别！注意与向前向后生长算法的区别！void InsertAfter(Node*p, DataType x)Node *q=new Node;q-info=x;q-link=p-link;p-link=q;沂辗炒频熄呐膏午聘冠豪调痪巍奖煽减移探职嗡曙拢宅葬押苞毖虎臻猎盂链表与链表的基本操作链表与链表的基本操作7.2.1 单链表基本算法单链表基本算法6. 6. 删除结点删除结点p p后的结点后的结点void RemoveAfter(Node*p) Node*q; q=p-link; if(q!=NULL) p-link=q-link; delete q; q=NULL;/如果该结点还要用，则不要释放，将如果该结点还要用，则不要释放，将q q返回返回7. 7. 删除指定结点删除指定结点p pvoid RemoveCur(Node*head, Node*p) Node*q=head; while(q-link!=NULL & q-link!=p) q=q-link; /遍历查找遍历查找 RemoveAfter(q);/删除删除q q后面的结点后面的结点p p卤晨新惫户秧示梁枯侈铰悸伊瘁静痰扦考遮荚芍柞创引凄侩碌华义绿孤营链表与链表的基本操作链表与链表的基本操作7.2.1 单链表基本算法单链表基本算法8.8.清空单链表清空单链表, ,保留表头结点保留表头结点void MakeEmpty(Node* head)Node*p;while(head-link!=NULL)/未到尾节点未到尾节点p=head-link;head-link=p-link; /头结点后第一个结点从链中脱落头结点后第一个结点从链中脱落delete p; p=NULL;/删除脱离下来的结点删除脱离下来的结点讼弊乘檀附汉愉娥换暗卵肆姥改快阉准掺同吼灭督叔苔珐孺庶砂嗅吨沽讶链表与链表的基本操作链表与链表的基本操作7.2.2 单链表类设计单链表类设计不同于不同于【例【例7.5_h】的】的单链表类单链表类定义结点类：定义结点类：typedef int DataType;class Node DataType info; /数据域数据域 Node *link; /指针域指针域public: Node(); /生成生成空结点的构造函数空结点的构造函数 Node(const Datatype &); /生成生成一般结点的构造函数一般结点的构造函数 void PrintNode(); /打印当前结点的信息域打印当前结点的信息域 friend class SLList; /以以SLList为为Node友元类，友元类，SLList可直接访问可直接访问Node私有数据，私有数据，比结构安全比结构安全;杰观辕艰皆伴韭哼铆粹哮温渭恋恶技鼠韧侄踩杰脉秆托码肢勾既音臆酞韧链表与链表的基本操作链表与链表的基本操作例例7.5_h 结点类结点类Node:Node()link=NULL;Node:Node(const DataType & data)info=data;link=NULL; void Node:PrintNode()coutinfolink!=NULL) /把头结点后的第一个结点从链中脱离把头结点后的第一个结点从链中脱离 p=head-link; head-link=p-link; delete p; p=NULL; /删除删除(释放释放)脱离下来的结点脱离下来的结点 tail=head; /表头指针与表尾指针均指向表头结点，表示空链表头指针与表尾指针均指向表头结点，表示空链抛芹棚惯喂肩窘陷侈餐找姿耐汛岗枉甘诌帘影韩减竿颁禄嗽扮劲谦川注庐链表与链表的基本操作链表与链表的基本操作例例7.5_h 单链表类单链表类链表类成员函数：链表类成员函数：Node* SLList:TravFind(DataType key) Node*p=head-link; while(p!=NULL&p-info!=key)p=p-link; return p;/搜索成功返回该结点地址，不成功返回搜索成功返回该结点地址，不成功返回NULL void SLList:PrintSLL() /显示链表显示链表 Node* p=head-link; while(p!=NULL) coutinfolink; coutlink=head-link;head-link=p; /新结点始终在头结点之后新结点始终在头结点之后void SLList:GrowDN(const DataType& data)Node* p=new Node(data);tail-link=p;tail=p;tail-link=NULL;听叮淌陈闻椰离钟簇漫肪脂榨紧蝴及诸烙快锨坠大霜葬臣皇琉闻堡策闯畴链表与链表的基本操作链表与链表的基本操作链表类成员函数：链表类成员函数：void SLList:RemoveAfter(Node*p)Node*q;q=p-link; if(q!=NULL) p-link=q-link; delete q; q=NULL;例例7.5_h 单链表类单链表类void SLList:RemoveCur(Node*p)Node*q=head;while(q-link!=NULL & q-link!=p) q=q-link;/遍历查找遍历查找if(q-link=tail) tail=q;/已经找到末尾已经找到末尾RemoveAfter(q);/删除删除q后面的结点后面的结点p斥蹲咳毒啸镑辅琉递宵黍酞并牧太缄肪旋绽监谍汕佯氟嵌盘廓荡爪拿皂氢链表与链表的基本操作链表与链表的基本操作例例7.5_h 主函数主函数void int main()SLList L1; Node n, *tmp;for(int j=0;j10;j+) L1.GrowDN(j); /向后生向后生成链表成链表cout初始链表初始链表:; L1.PrintSLL(); /打印表打印表L1.GrowUP(20);/向前插入到头结点后向前插入到头结点后cout插入结点后的链表插入结点后的链表:; L1.PrintSLL(); /打印打印tmp=L1.TravFind(20); /查找插入的结点查找插入的结点n=*tmp;cout找到结点的信息域找到结点的信息域:; n.PrintNode();L1.RemoveCur(tmp);/删除插入的结点删除插入的结点coutlink;head=tail=new Node();while(p!=NULL)GrowDN(p-info);/向后生长一个结点向后生长一个结点p=p-link;拭郡淫摔捶去咸幼集惭愁丙咯谗秽瘤焚霖歪卵然晦叶拈披扁爽绎忌设予紊链表与链表的基本操作链表与链表的基本操作7.2.2 单链表类单链表类讨论复制构造函数：讨论复制构造函数：/拷贝赋值运算符拷贝赋值运算符SLList& SLList:operator=(SLList & ls)Node* p=ls.head-link;if(tail!=NULL) MakeEmpty();/提高安全性提高安全性while(p!=NULL)GrowDN(p-info);/向后生长一个结点向后生长一个结点p=p-link;return *this;镶汛苯掩嗽皂牌窗萍靠社抚唾壕测绅膨野烤头等爱袱槛酵坟可悉藐氯币讫链表与链表的基本操作链表与链表的基本操作7.3 栈与队列的基本操作及其应用栈与队列的基本操作及其应用 栈和队都是特殊的线性表，限制存取位置的线性结构，可以由顺序表实现，也可以由链表实现。 7.3.1 栈栈 7.3.3队列队列 7.3.2 栈的应用（选读）栈的应用（选读） 广诚碗斯斥桨吗蹈器蚊映蔡瞥迁旧朔炳市婪梧炽庇耶症哇察径钎绍哉汾暂链表与链表的基本操作链表与链表的基本操作