第022讲单链表

《第022讲单链表》由会员分享，可在线阅读，更多相关《第022讲单链表（38页珍藏版）》请在装配图网上搜索。

1、第第02-2讲单链表讲单链表Essential of Lecture Two-TwoEssential of Lecture Two-Two：一、线性链表一、线性链表 二、二、单链表单链表及其基本操作及其基本操作 三、单链表实战应用三、单链表实战应用难点难点2 2 用一组用一组任意的任意的存储单元存储线性表的数据元素；存储单元存储线性表的数据元素；利用利用指针指针实现了用不相邻的存储单元存放逻辑上相邻实现了用不相邻的存储单元存放逻辑上相邻的元素；的元素；每个数据元素每个数据元素ai，除存储本身信息外，还需存储其直接除存储本身信息外，还需存储其直接后继的信息。后继的信息。一、线性链表一、线性链表

2、 (Linked List(Linked List)链式存储结构的特点：链式存储结构的特点：3 3 数据域：元素本身信息数据域：元素本身信息 指针域：指示直接后继的存储位置指针域：指示直接后继的存储位置存储地址存储地址1713192531374343131NULL3719257例例 线性表线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)头指针头指针 31head结点包括：结点包括：数据域数据域指针域指针域LIQIANSUNWANGWUZHAOZHENGZHOU4 4例例 线性表线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)Z

3、HAOQIANSUNLIZHOUWUZHENGWANGH逻辑上的示意图：逻辑上的示意图：5 5单链表定义：单链表定义：单链表定义：单链表定义：结点中只含一个指针域的链表叫线性链表。结点中只含一个指针域的链表叫线性链表。结点如何实现？结点如何实现？(*p)表示表示p所所指向的指向的结点结点(*p).data表示表示p指向指向结点的数据结点的数据域域(*p).next表示表示p指向指向结点的指针结点的指针域域6 6在单链表第一个结点前附设一个结点叫在单链表第一个结点前附设一个结点叫 头结点指针域为空表示线性表为头结点指针域为空表示线性表为空空ha1a2头结点头结点an .h空表空表头结点：头结点：

4、7 7实战：实战：1 1、单选、单选、单选、单选下面关于线性表的叙述中，错误的是（下面关于线性表的叙述中，错误的是（）。）。A 顺序表必须占用一片地址连续的存储单元顺序表必须占用一片地址连续的存储单元B 链表不必占用一片地址连续的存储单元链表不必占用一片地址连续的存储单元C 顺序表可以随机存取任一元素顺序表可以随机存取任一元素D 链表可以随机存取任一元素链表可以随机存取任一元素8 8类模板将类的数据成员和成员函数设计得更完类模板将类的数据成员和成员函数设计得更完类模板将类的数据成员和成员函数设计得更完类模板将类的数据成员和成员函数设计得更完整、更灵活。整、更灵活。整、更灵活。整、更灵活。类模板

5、更易于复用。类模板更易于复用。类模板更易于复用。类模板更易于复用。在单链表的类模板定义中，增加了表头结点。在单链表的类模板定义中，增加了表头结点。在单链表的类模板定义中，增加了表头结点。在单链表的类模板定义中，增加了表头结点。C+中链式结构的存储：中链式结构的存储：9 9template template structstruct Node Node /数据成员数据成员数据成员数据成员:ElemType data;ElemType data;/数据域数据域数据域数据域Node*next;Node*next;/指针域指针域指针域指针域/构造函数构造函数构造函数构造函数:Node();Node()

6、;/无参数的构造函数无参数的构造函数无参数的构造函数无参数的构造函数Node(ElemType item,Node*link=Node(ElemType item,Node*link=NULL);NULL);/已知数据域和指针域建立结构已知数据域和指针域建立结构已知数据域和指针域建立结构已知数据域和指针域建立结构;结点类结点类参见文件夹参见文件夹S2_3里的文件里的文件node.h1010template template classclass SimpleLinkList SimpleLinkList protected:protected:/链表实现的数据成员链表实现的数据成员链表实现的数

7、据成员链表实现的数据成员:Node*head;Node*head;/头结点指针头结点指针头结点指针头结点指针/辅助函数辅助函数辅助函数辅助函数Node*GetElemPtr(int position)const;Node*GetElemPtr(int position)const;/返回指向第返回指向第返回指向第返回指向第positionposition个结点的指针个结点的指针个结点的指针个结点的指针void Init();void Init();/初始化线性表初始化线性表初始化线性表初始化线性表简单线性链表类简单线性链表类参见文件夹参见文件夹S2_3里的文件里的文件simple_lk_lis

8、t.h1111public:public:/抽象数据类型方法声明及重载编译系统默认方法声明抽象数据类型方法声明及重载编译系统默认方法声明抽象数据类型方法声明及重载编译系统默认方法声明抽象数据类型方法声明及重载编译系统默认方法声明:SimpleLinkList();SimpleLinkList();/无参数构造函数无参数构造函数无参数构造函数无参数构造函数virtual SimpleLinkList();virtual SimpleLinkList();/析构函数析构函数析构函数析构函数int Length()const;int Length()const;/求线性表长度求线性表长度求线性表长度

9、求线性表长度 bool Empty()const;bool Empty()const;/判断线性表是否为空判断线性表是否为空判断线性表是否为空判断线性表是否为空void Clear();void Clear();/将线性表清空将线性表清空将线性表清空将线性表清空void Traverse(void(*Visit)(const ElemType&)void Traverse(void(*Visit)(const ElemType&)const;const;/遍历线性表遍历线性表遍历线性表遍历线性表StatusCode GetElem(int position,ElemType&e)StatusC

10、ode GetElem(int position,ElemType&e)const;const;/求指定位置的元素求指定位置的元素求指定位置的元素求指定位置的元素StatusCode SetElem(int position,const ElemTypeStatusCode SetElem(int position,const ElemType&e);&e);/设置指定位置的元素值设置指定位置的元素值设置指定位置的元素值设置指定位置的元素值1212StatusCode Delete(int position,ElemType&e);StatusCode Delete(int position,

11、ElemType&e);/删除元素删除元素删除元素删除元素StatusCode Insert(int position,const ElemType&e);StatusCode Insert(int position,const ElemType&e);/插入元素插入元素插入元素插入元素SimpleLinkList(const SimpleLinkListSimpleLinkList(const SimpleLinkList©);©);/复制构造函数复制构造函数复制构造函数复制构造函数SimpleLinkList&operator=(constSimpleLinkList&op

12、erator=(const SimpleLinkList©);SimpleLinkList©);/赋值语句重载赋值语句重载赋值语句重载赋值语句重载;1313根据已给的表头指针，按由前向后的次根据已给的表头指针，按由前向后的次序访问单链表的各个结点。序访问单链表的各个结点。1.查找查找heada1a2a3a4tmpPtrcurPosition=0123tmpPtrtmpPtrtmpPtr二、单链表的基本操作二、单链表的基本操作1414templateNode*SimpleLinkList:GetElemPtr(int position)constNode*tmpPtr=head;

13、int curPosition=0;while(tmpPtr!=NULL&curPosition next;curPosition+;if(tmpPtr!=NULL&curPosition=position)return tmpPtr;/查找成功查找成功elsereturn NULL;/查找失败查找失败参见文件夹参见文件夹S2_3里的文件里的文件simple_lk_list.h15152.初始化初始化二、单链表的基本操作二、单链表的基本操作headtemplate void SimpleLinkList:Init()/操作结果：初始化线性表操作结果：初始化线性表head=new Node;/构

14、造头指针构造头指针1616头插法头插法 演示演示3.建表、插入操作建表、插入操作H sC1C2HCi-1Ci-2C1 sCix1717尾插法尾插法 演示演示3.建表、插入操作建表、插入操作H sC1 rCi HCi-1 C1C2rx sC1 Hrr1818 在单链表中第在单链表中第i（1=i=Length()+1）个结个结点之前插入一个数据域为点之前插入一个数据域为x的结点。的结点。3.插入插入heada1a2a3a4tmpPtrtmpPtrtmpPtrnewPtre 例如：例如：i=31919(1)在单链表上找到插入位置，即找到第在单链表上找到插入位置，即找到第i-1个结点。个结点。(2)生

15、成一个以生成一个以e为值的新结点。为值的新结点。(3)将新结点链入单链表中。将新结点链入单链表中。插入的三个基本操作插入的三个基本操作2020插入算法插入算法template StatusCode SimpleLinkList:Insert(int position,const ElemType&e)if(position Length()+1)/position范围错范围错return RANGE_ERROR;/位置不合法位置不合法 else/position合法合法Node*tmpPtr;tmpPtr=GetElemPtr(position-1);Node*newPtr;newPtr=ne

16、w Node(e,tmpPtr-next);tmpPtr-next=newPtr;return SUCCESS;2121本教材采用尾插法创建单链表本教材采用尾插法创建单链表(1)先先GetElemPtr(position-1)定位指针定位指针(2)再产生结点及插入再产生结点及插入template void Create(SimpleLinkList&la,ElemType a,int n)/操作结果操作结果:由数组由数组a存储的存储的n个元素构造线性表个元素构造线性表la.Clear();/清空清空lafor(int position=1;position=n;position+)la.Ins

17、ert(position,aposition-1);/向向la插入元素插入元素2222删除单链表中第删除单链表中第position个位置的元素。个位置的元素。两个基本操作：两个基本操作：两个基本操作：两个基本操作：1)在单链表上找到前驱结点。在单链表上找到前驱结点。2)从单链表上删除该结点。从单链表上删除该结点。演示演示4.删除删除heada1a2a3a4tmpPtrtmpPtrtmpPtr例如：例如：i=3nextPtr2323删除算法删除算法template StatusCode SimpleLinkList:Delete(int position,ElemType&e)if(positi

18、on Length()/position范围错范围错return RANGE_ERROR;else/position合法合法Node*tmpPtr;tmpPtr=GetElemPtr(position-1);Node*nextPtr=tmpPtr-next;tmpPtr-next=nextPtr-next;e=nextPtr-data;delete nextPtr;return SUCCESS;2424由前向后遍历，并统计即可。由前向后遍历，并统计即可。5.求表长求表长 heada1a2a3a4 tmPtr tmPtr count=1 tmPtr count=2 tmPtr count=3in

19、t count=0;for(Node*tmpPtr=head-next;tmpPtr!=NULL;tmpPtr=tmpPtr-next)count+;count=0 tmPtr count=42525例：合并有序单链表例：合并有序单链表la和和lb到到lc中去。中去。P57三、单链表的应用三、单链表的应用281219137 lalb2626281219137 lalblc 1 2 aPosition=1bPosition=1 bPosition=2aPosition=22727template void MergeList(const SimpleLinkList&la,const Simpl

20、eLinkList&lb,SimpleLinkList&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 2828while(aPosition=aLength&bPosition=bLength)/取出取出la和和lb中数据元素进行归并中数据元素进行归并la.GetElem(aPosition,aItem)

21、;lb.GetElem(bPosition,bItem);if(aItem bItem)/归并归并aItemlc.Insert(lc.Length()+1,aItem);aPosition+;else/归并归并bItemlc.Insert(lc.Length()+1,bItem);bPosition+;2929 while(aPosition=aLength)/归并归并la中剩余数据元素中剩余数据元素la.GetElem(aPosition,aItem);lc.Insert(lc.Length()+1,aItem);aPosition+;while(bPosition=bLength)/归并归

22、并lb中剩余数据元素中剩余数据元素lb.GetElem(bPosition,bItem);lc.Insert(lc.Length()+1,bItem);bPosition+;3030实战：北京理工大学实战：北京理工大学20022002年考研题年考研题程序阅读题程序阅读题程序阅读题程序阅读题阅读下面的程序，在空白处填上恰当的内容。阅读下面的程序，在空白处填上恰当的内容。void Addpolyn(Slink&Ha,Slink&Hb)/*用用带带节节点点的的单单链链表表存存储储多多项项式式，Ha和和Hb分分别别是是两两个个多多项式链表的指针项式链表的指针*/*多项式加法算法：将多项式多项式加法算法

23、：将多项式Hb加到加到Ha上，上，Ha=Ha+Hb，利用两个多项式节点构成，利用两个多项式节点构成“和多项式和多项式”*/pa=Ha;pb=Hb;qa=panext;qb=pbnext;/*qa和和qb分分别别指指向向Ha和和Hb的的当当前前节节点点，pa和和pb分分别别指指向向Ha和和Hb当前节点的前一个节点当前节点的前一个节点*/3131HaHbpapbqbqacoef域域 exp域域1）系数相加不为）系数相加不为02）系数相加为）系数相加为0（1）Ha的指数小的指数小（2）Hb的指数小的指数小（3）Ha与与Hb的指数相等的指数相等3232while(qa!=NULL)&(qb!=NULL

24、)a=qadata;b=qbdata;switch(cmp(a,b)case -1:/*多项式多项式Ha当前节点的指数值小当前节点的指数值小*/pa=qa;qa=qanext;break;case 0:/*两者值相等两者值相等*/sum=a.coef+b.coef;if(sum!=0.0)qadata=sum;pa=qa;else panext=qanext;free(qa);(1);pbnext=qbnext;free(qb);qb=pbnext;break;3333 case 1:/*多项式多项式Hb当前节点的指数值小当前节点的指数值小*/pbnext=qbnext;(2);(3);(4)

25、;break;/*switch end*/*while end*/if(qb!=NULL)(5);free(pb);/*释放释放Hb的头节点的头节点*/3434小结：顺序表与链表的比较小结：顺序表与链表的比较基于时间的比较基于时间的比较n存取方式存取方式u顺序表可以随机存取，也可以顺序存取顺序表可以随机存取，也可以顺序存取u链表是顺序存取的链表是顺序存取的n插入插入/删除时移动元素个数删除时移动元素个数u顺序表平均需要移动近一半元素顺序表平均需要移动近一半元素u链表不需要移动元素，只需要修改指针链表不需要移动元素，只需要修改指针u若插入若插入/删除仅发生在表的两端，宜采用带尾指针的删除仅发生在

26、表的两端，宜采用带尾指针的循环链表循环链表3535本本 讲讲 小小 结结重点：重点：1、线性链表基本概念、线性链表基本概念 2、单链表基本操作、单链表基本操作难点：难点：1、单链表的应用、单链表的应用3636Homework:1、程序填空，具体见、程序填空，具体见02-2讲单链表作业讲单链表作业.doc2、写算法：、写算法：P87 9。请调试通过后将核心算法的函数写到作业本上请调试通过后将核心算法的函数写到作业本上。3737Word Puzzles POJ 1204题目大意：题目大意：给出一个给出一个N*L的字符矩阵，再给出的字符矩阵，再给出M个字个字符串，问这符串，问这M个字符串在这个字符矩阵中出现的位置。个字符串在这个字符矩阵中出现的位置。欢迎对编程感兴趣的同学加入欢迎对编程感兴趣的同学加入ACM队伍！队伍！MARGARITA ALEMA BARBECUE 数据范围：数据范围：N,L=1000M=1000时间限制：时间限制：5s3838