第二章线性表(2)

1、适莽苍者，三飡而反，腹犹果然；适百里适莽苍者，三飡而反，腹犹果然；适百里者，宿舂粮；适千里者，三月聚粮。者，宿舂粮；适千里者，三月聚粮。同学们，你打算为自己的将来准备多少资粮？同学们，你打算为自己的将来准备多少资粮？第二章 线性表主要内容主要内容n2.1 线性表的基础知识线性表的基础知识n2.2 顺序表顺序表n2.3 单链表单链表n2.4 线性链表的其它变形线性链表的其它变形n2.5 单链表的应用：多项式乘法单链表的应用：多项式乘法n2.6 静态链表静态链表2.1.2 线性结构线性结构n线性结构可以定义为二元组线性结构可以定义为二元组B=(K,R) , 其中其中K = a0, a1, an-1

2、,R= 前驱前驱/后继关系后继关系 u有一个唯一的开始节点有一个唯一的开始节点，它没有前驱它没有前驱，有一个唯一的直接有一个唯一的直接后继后继。u一个唯一的一个唯一的 终止节点终止节点，它有一个唯一的直接前驱它有一个唯一的直接前驱，而，而没没有后继有后继。u其它的结点皆称为内部结点，其它的结点皆称为内部结点，每一个内部结点都有且仅有每一个内部结点都有且仅有一个唯一的直接有前驱，也有一个唯一的直接后继一个唯一的直接有前驱，也有一个唯一的直接后继，如：，如：，ai是是ai+1的前驱，的前驱，ai+1是是ai的后继。的后继。u前驱前驱/后继关系后继关系r，具有，具有 反对称性反对称性 和和 传递性传

3、递性2.1.2 线性结构线性结构n线性结构的特点线性结构的特点均匀性：虽然不同线性表的数据元素可以是各种各样的，均匀性：虽然不同线性表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型但对于同一线性表的各数据元素必定具有相同的数据类型和长度和长度 有序性：各数据元素在线性表中都有自己的位置，且数有序性：各数据元素在线性表中都有自己的位置，且数据元素之间的相对位置是线性的据元素之间的相对位置是线性的2.1.3 线性表的三个方面线性表的三个方面n线性表的逻辑结构线性表的逻辑结构n线性表的存储结构线性表的存储结构n线性表的操作线性表的操作存存储储逻逻辑辑操作操作线性线性表

4、表2.1.3 线性表的三个方面：逻辑结构线性表的三个方面：逻辑结构a0，a1，an-2，an-1u有一个唯一的开始节点有一个唯一的开始节点a0 ，它没有前驱它没有前驱，有一个唯一的直有一个唯一的直接后继接后继a1 。u一个唯一的一个唯一的 终止节点终止节点an-1 ，它有一个唯一的直接前驱它有一个唯一的直接前驱，而，而没有后继没有后继an-2 。u其它的结点皆称为内部结点，其它的结点皆称为内部结点，每一个内部结点都有且仅有每一个内部结点都有且仅有一个唯一的直接有前驱，也有一个唯一的直接后继一个唯一的直接有前驱，也有一个唯一的直接后继，如：，如：，ai是是ai+1的前驱，的前驱，ai+1是是ai

5、的后继。的后继。2.1.3 线性表的三个方面：存储结构线性表的三个方面：存储结构n 顺序存储表示：顺序表顺序存储表示：顺序表0123456789a1a2a3a4a5n链接存储表示：链表链接存储表示：链表*a1a7a6a5a4a3a2a10a9a82.1.3 线性表的三个方面：操作线性表的三个方面：操作u建立线性表建立线性表 u清除线性表清除线性表 u插入一个新元素插入一个新元素 u删除某个元素删除某个元素 u修改某个元素修改某个元素 u排序排序 u检索（查找）检索（查找）n线性表上的关键操作如下：线性表上的关键操作如下：2.3 单链表单链表n2.3.1 单链表的定义单链表的定义n2.3.2 单

6、链表的特点单链表的特点n2.3.3 单链表的实现策略单链表的实现策略n2.3.4 单链表模板的定义单链表模板的定义n2.3.5 单链表上的操作单链表上的操作n2.3.6 带头结点的单链表带头结点的单链表2.3.1 单链表的定义单链表的定义n单链表是包含单链表是包含0个或多个元素的线性结构个或多个元素的线性结构，其中每个元素（也称为节点）包含两个域：其中每个元素（也称为节点）包含两个域：数据域和链域数据域和链域。u数据域用于存储线性表的一个数据元素，数据域用于存储线性表的一个数据元素，其数据类型由其数据类型由应用问题决定应用问题决定。u链域用于存放一个指针，该指针指示链表中下一个结点链域用于存放

7、一个指针，该指针指示链表中下一个结点的开始存储地址。的开始存储地址。表头表头表尾表尾表尾没有直接后继，其链域设置为空。课件中用表尾没有直接后继，其链域设置为空。课件中用表示空。表示空。a1a2a3a4a5firstdata next元素：元素：2.3.1 单链表的特点单链表的特点u结点之间可以连续，可以不连续存储。结点之间可以连续，可以不连续存储。u结点的逻辑顺序与物理顺序可以不一致。结点的逻辑顺序与物理顺序可以不一致。u表的长度可以很方便的进行扩充。表的长度可以很方便的进行扩充。a1a2a3a4firsta1a3a2a4first2.3.3 单链表的实现策略单链表的实现策略n单链表单链表中有

8、中有0个或多个个或多个节点节点，支持节点的增，支持节点的增删查改。删查改。n节点包含数据域和链域。a1a2a3a4first如何定义结点？如何在结点的基础上定义单链表？如何定义结点？如何在结点的基础上定义单链表？2.3.3单链表的实现策略单链表的实现策略/结点的定义结点的定义struct ListNode /链表结点类链表结点类 int data; /结点数据域结点数据域 ListNode * next; /结点链接指针域结点链接指针域 ; /链表的定义链表的定义class List private: ListNode *first; /表头指针表头指针 ; uListNode类与类与List

9、类是类是包含（具包含（具体讲是聚合）的关系体讲是聚合）的关系。 uListNode中的数据域和链域是中的数据域和链域是public成员，成员，List类可以通过对象类可以通过对象直接访问它们。直接访问它们。u链表中的结点属于链表私有，别链表中的结点属于链表私有，别人无法访问。人无法访问。2.3.3单链表的实现策略单链表的实现策略n单链表分为单链表分为不带头结点单链表不带头结点单链表和和带头结点带头结点单链表单链表两种，两种，本课件先介绍不带头结点单本课件先介绍不带头结点单链表链表。2.3.4单链表模板的定义单链表模板的定义n结点模板的定义结点模板的定义templatestruct LinkNo

10、de T data; LinkNode* next; LinkNode(const T& item, LinkNode* ptr=NULL); LinkNode(LinkNode* ptr=NULL);templateclass Listprivate: LinkNode * first;public: List(); List(const List& L); List& operator=(const List& L); List(); void InputFront(const T& elem); void InputRear(const T&

11、; elem); bool Insert(int i, const T& x); bool Remove(int i, T& x); LinkNode* Search(const T& x); LinkNode* Locate(int i); bool GetData(int i, T& x)const; void SetData(int i, const T& x); void MakeEmpty(); void CopyList(const List& L); int Length() const; bool IsEmpty() const;

12、 bool IsFull() const; void Sort(); friend ostream& operator(ostream& out, const List& L); friend istream& operator(istream& in, List& L);n单链表模板的定义单链表模板的定义构造函数，拷贝构构造函数，拷贝构造函数，赋值运算造函数，赋值运算符函数，析构函数符函数，析构函数单链表的增删查改单链表的增删查改清空复制链表节点清空复制链表节点链表自身状态链表自身状态2.3.5 单链表的操作单链表的操作n创建空链表创建空链表L

13、ist();空链表即链表中没有结点。空链表即链表中没有结点。List() first=NULL;2.3.5 单链表的操作单链表的操作n新建链表：头插法新建链表：头插法头插法是每次插入新节点总是在表的表头位置，这头插法是每次插入新节点总是在表的表头位置，这样插入的结果，链表中各节点中数据的逻辑顺序与样插入的结果，链表中各节点中数据的逻辑顺序与输入数据的顺序正好相反。主要步骤为：输入数据的顺序正好相反。主要步骤为：u从一个空表开始，重复读入数据，执行以下步骤：从一个空表开始，重复读入数据，执行以下步骤： （1）. 生成新节点，将读入数据存放到新节点的生成新节点，将读入数据存放到新节点的data域中

14、；域中； （2）. 将该新节点插入到链表的表头位置。将该新节点插入到链表的表头位置。 void InputFront(const T& elem);2.3.5 单链表的操作单链表的操作n新建链表：头插法（例子）新建链表：头插法（例子）u从一个空表开始，重复读入数据，执行以下步骤：从一个空表开始，重复读入数据，执行以下步骤： （1）. 生成新节点，将读入数据存放到新节点的生成新节点，将读入数据存放到新节点的data域中；域中； （2）. 将该新节点插入到链表的表头位置。将该新节点插入到链表的表头位置。first空表：空表：输入数据：输入数据： 25,34,57,16,47,09,632.

15、3.5 单链表的操作单链表的操作:头插法头插法当前表：当前表：34插入新节点后：插入新节点后：first2534first255757newNode：first当前表：当前表：25first25插入新节点后：插入新节点后：newNode：当前表：当前表：34first25插入新节点后：插入新节点后：first2534newNode：newNode-next=first; first=newNode;2.3.5 单链表的操作单链表的操作n新建链表：尾插法新建链表：尾插法尾插法：指每次新节点总是插入到链表的表尾位置，尾插法：指每次新节点总是插入到链表的表尾位置，这样插入的结果，链表中各节点中数据的

16、逻辑顺序这样插入的结果，链表中各节点中数据的逻辑顺序与输入数据的顺序完全一致。与输入数据的顺序完全一致。u从一个空表开始，重复读入数据，执行以下步骤：从一个空表开始，重复读入数据，执行以下步骤： （1）. 生成新节点，将读入数据存放到新节点的生成新节点，将读入数据存放到新节点的data域中；域中； （2）. 将该新节点插入到链表的表尾位置。将该新节点插入到链表的表尾位置。void InputRear(const T& elem);2.3.5 单链表的操作单链表的操作n新建链表：尾插法（例子）新建链表：尾插法（例子）u从一个空表开始，重复读入数据，执行以下步骤：从一个空表开始，重复读入数

17、据，执行以下步骤： （1）. 生成新节点，将读入数据存放到新节点的生成新节点，将读入数据存放到新节点的data域中；域中； （2）. 将该新节点插入到链表的表尾位置。将该新节点插入到链表的表尾位置。first空表：空表：输入数据：输入数据： 25,34,57,16,47,09,63当前表：当前表：34first25插入新节点后：插入新节点后： first255734571616newNode：当前表：当前表：34first25插入新节点后：插入新节点后：first25573457newNode：当前表：当前表：34first25插入新节点后：插入新节点后： first2534newNode：f

18、irst当前表：当前表：first25插入新节点后：插入新节点后：25newNode：尾插法空表和非空表插入操作时的情况不一致。尾插法空表和非空表插入操作时的情况不一致。当前表：当前表：34first25插入新节点后：插入新节点后： first255734571616newNode：当前表：当前表：34first25插入新节点后：插入新节点后：first25573457newNode：当前表：当前表：34first25插入新节点后：插入新节点后： first2534newNode：first当前表：当前表：first25插入新节点后：插入新节点后：25newNode：原因：尾插法总是在表尾节点

19、的后面插入节原因：尾插法总是在表尾节点的后面插入节点，空表时没有表尾节点。点，空表时没有表尾节点。u当链表为空时：当链表为空时：first当前表：当前表：first25插入新节点后：插入新节点后：25newNode：first=newNode;u当链表非空时：当链表非空时：当前表：当前表：34first25插入新节点后：插入新节点后：first25573457newNode：首先找到表尾节点；然后修改表尾节点的首先找到表尾节点；然后修改表尾节点的next域，让它指向新域，让它指向新节点。节点。表尾节点的特点：表尾节点的特点：尾节点的尾节点的next域为空。域为空。rear=first;whil

20、e(rear-next) rear=rear-next;rear-next=newNode;2.3.5 单链表的操作单链表的操作n单链表中插入结点单链表中插入结点bool Insert(int i, const T& x);u在链表的表头插入节点在链表的表头插入节点u在链表的中间插入节点在链表的中间插入节点u在链表的表尾插入节点在链表的表尾插入节点当前表：当前表：34first25插入新节点后：插入新节点后：first2534newNode：表头插入节点：表头插入节点：Insert(1,34);当前表：当前表：57first25插入新节点后：插入新节点后：first25343457ne

21、wNode：表中插入节点：表中插入节点：Insert(2,57);表尾插入节点：表尾插入节点：Insert(4,16);当前表：当前表：34first25插入新节点后：插入新节点后： first255734571616newNode：在链表中插入元素时，需要找到插入位置的直接前驱节点，但在链表中插入元素时，需要找到插入位置的直接前驱节点，但单链单链表的表头节点没有直接前驱表的表头节点没有直接前驱，所以必须单独处理。，所以必须单独处理。2.3.5 单链表的操作单链表的操作n单链表中插入结点单链表中插入结点bool Insert(int i, const T& x);表头插入节点：表头插入

22、节点：Insert(1,34);当前表：当前表：34first25插入新节点后：插入新节点后：first2534newNode：在单链表的头部插入结点时，具体步骤为：在单链表的头部插入结点时，具体步骤为：修改修改newNode所指结点的所指结点的next域，使它的值与域，使它的值与first指针指针的指向相同；的指向相同；1. 修改修改first指针的指向，使它指向指针的指向，使它指向newNode所指结点。所指结点。2.3.5 单链表的操作单链表的操作n单链表中插入结点单链表中插入结点bool Insert(int i, const T& x);表头插入节点：表头插入节点：Inser

23、t(1,34);当前表：当前表：34first25插入新节点后：插入新节点后：first2534newNode：newNode-next=first;first=newNode;2.3.5单链表的操作单链表的操作n单链表中插入节点单链表中插入节点bool Insert(int i, const T& x);表中，表尾插入节点：表中，表尾插入节点：在链表的中间和尾部插入结点时，具体步骤为：在链表的中间和尾部插入结点时，具体步骤为： 定位当前位置的前驱节点定位当前位置的前驱节点pre； 将将pre所指结点的所指结点的next域赋值给域赋值给newNode所指结点的所指结点的next域；域；

24、1. 使使pre所指结点的所指结点的next域指向域指向newNode所指结点。所指结点。当前表：当前表：57first25插入新节点后：插入新节点后：first25343457newNode：表中插入节点：表中插入节点：Insert(2,57);2.3.5单链表的操作单链表的操作n单链表中插入节点单链表中插入节点bool Insert(int i, const T& x);表中，表尾插入节点：表中，表尾插入节点：当前表：当前表：57first25插入新节点后：插入新节点后：first25343457newNode：pre表中插入节点：表中插入节点：Insert(2,57);57new

25、NodenewNode-next=pre-next;pre-next=newNode;2.3.5单链表的操作单链表的操作n单链表中插入节点单链表中插入节点bool Insert(int i, const T& x); pre=first; for(int j=1; jnext; if(pre=NULL) cerr无效的插入位置无效的插入位置endl; return false; else newNode=new LinkNode(x); newNode-next=pre-next; pre-next=newNode; 在链表的中间和尾部插入结点时，在链表的中间和尾部插入结点时，具体步骤

26、为：具体步骤为：定位当前位置的前驱节点定位当前位置的前驱节点pre；将将pre所指结点的所指结点的next域赋值域赋值给给newNode所指结点的所指结点的next域；域；1. 使使pre所指结点的所指结点的next域指向域指向newNode所指结点。所指结点。2.3.5单链表的操作单链表的操作n单链表中插入节点：特殊情况单链表中插入节点：特殊情况u插入位置非法插入位置非法 插入位置小于插入位置小于1。 插入位置大于链表长度。插入位置大于链表长度。2.3.5 单链表的操作单链表的操作n单链表中删除结点单链表中删除结点bool Remove(int i, T& x);u在链表的表头删除节

27、点在链表的表头删除节点u在链表的中间删除节点在链表的中间删除节点u在链表的表尾删除节点在链表的表尾删除节点当前表：当前表：34删除节点后：删除节点后：first2534first2557删除表头节点删除表头节点:Remove(1,elem);删除表头节点删除表头节点:Remove(2,elem);当前表：当前表：57first25删除节点后：删除节点后：first253434当前表：当前表：34first25删除节点后：删除节点后：first2557345716删除表尾节点删除表尾节点:Remove(4,elem);在链表中删除元素时，需要找到删除位置的直接前驱节点，但在链表中删除元素时，需要

28、找到删除位置的直接前驱节点，但单链单链表的表头节点没有直接前驱表的表头节点没有直接前驱，所以必须单独处理。，所以必须单独处理。2.3.5 单链表的操作单链表的操作n单链表中删除结点单链表中删除结点表头删除节点：表头删除节点：Remove(1,elem);在单链表的头部删除结点时，具体步骤为：在单链表的头部删除结点时，具体步骤为：将表头节点的数据域赋值给将表头节点的数据域赋值给elem。使使first指向表头节点的指向表头节点的next域。域。1. 释放原表头节点的内存空间。释放原表头节点的内存空间。bool Remove(int i, T& x);当前表：当前表：34删除节点后：删除节

29、点后：first2534first25572.3.5 单链表的操作单链表的操作n单链表中删除结点单链表中删除结点表头删除节点：表头删除节点：Remove(1,elem);bool Remove(int i, T& x);当前表：当前表：34删除节点后：删除节点后：first2534first2557del=first; /del指向被删除节点指向被删除节点x=del-data;first=first-next;delete del;2.3.5单链表的操作单链表的操作n单链表中删除节点单链表中删除节点删除表中，表尾节点：删除表中，表尾节点：在链表的中间和尾部删除结点时，具体步骤为：在链表

30、的中间和尾部删除结点时，具体步骤为： 定位当前位置的前驱节点定位当前位置的前驱节点pre。 将被删除节点的将被删除节点的next域赋值给域赋值给pre所指结点的所指结点的next的域。的域。1. 将被删除节点的数据域赋值给将被删除节点的数据域赋值给elem，释放被删除节点。，释放被删除节点。bool Remove(int i, T& x);Remove(2,elem);当前表：当前表：57first25删除节点后：删除节点后：first2534342.3.5单链表的操作单链表的操作n单链表中删除节点单链表中删除节点删除表中，表尾节点：删除表中，表尾节点：在链表的中间和尾部删除结点时，具

31、体在链表的中间和尾部删除结点时，具体步骤为：步骤为：定位当前位置的前驱节点定位当前位置的前驱节点pre。将被删除节点的将被删除节点的next域赋值给域赋值给pre所指结点的所指结点的next的域。的域。1. 将被删除节点的数据域赋值给将被删除节点的数据域赋值给elem，释放被删除节点。释放被删除节点。bool Remove(int i, T& x); pre=del=first; for(int j=1; jnext; if(NULL=del) break; if(NULL=del) cerr无效的删除位置无效的删除位置next=del-next; x=del-data; delete

32、 del;2.3.5单链表的操作单链表的操作n单链表中删除节点：特殊情况单链表中删除节点：特殊情况u链表为空链表为空 提示链表为空的信息提示链表为空的信息u删除位置非法删除位置非法 删除位置小于删除位置小于1； 删除位置大于链表长度。删除位置大于链表长度。2.3.5单链表的操作单链表的操作n单链表中查找某个元素单链表中查找某个元素LinkNode* Search(const T& x);34first255716Search(57);34first255716iterIter-data=57 ?不成立，访问下一个结点不成立，访问下一个结点34first255716iter Iter-d

33、ata=57 ?不成立，访问下一个结点不成立，访问下一个结点34first255716iter Iter-data=57 ?，返回，返回iter2.3.5单链表的操作单链表的操作n单链表中查找某个元素单链表中查找某个元素LinkNode* Search(const T& x);34first255716Search(17);34first255716iterIter-data=17 ?不成立，访问下一个结点不成立，访问下一个结点34first255716iter Iter-data=17 ?不成立，访问下一个结点不成立，访问下一个结点2.3.5单链表的操作单链表的操作n单链表中查找某个

34、元素单链表中查找某个元素LinkNode* Search(const T& x);34first255716Search(17);34first255716iter Iter-data=17 ?不成立，访不成立，访问下一个结点问下一个结点34first255716iterIter-data=17 ?不成立，访不成立，访问下一个结点问下一个结点在找不到在找不到17的情况下，的情况下，iter指向空。指向空。2.3.5单链表的操作单链表的操作n单链表中查找某个元素单链表中查找某个元素LinkNode* Search(const T& x); LinkNode* iter=first

35、; while(iter) if(iter-data=x) return iter; iter=iter-next; return iter;2.3.5 单链表的操作单链表的操作n返回第返回第i个结点的位置个结点的位置LinkNode* Locate(int i);如果单链表中存在第如果单链表中存在第i个结点，返回第个结点，返回第i个结点的地址，个结点的地址，否则返回空。否则返回空。34first255716设计一个计数器设计一个计数器j；遍历链表，每访问一个节点，；遍历链表，每访问一个节点，j+，直到，直到j=i或或链表遍历完毕。链表遍历完毕。2.3.5 单链表的操作单链表的操作n返回第返回

36、第i个结点的位置个结点的位置LinkNode* Locate(int i); LinkNode * iter=first; int j=1; if(i1) return NULL; while(NULL!=iter&jnext; j+; return iter;2.3.5 单链表的操作单链表的操作n更新某个位置的元素更新某个位置的元素void SetData(int i, const T& x)如果第如果第i个结点存在，将它的数据域设置为个结点存在，将它的数据域设置为x。 LinkNode* nd=Locate(i); if(NULL=nd) return; nd-data=x

37、;2.3.5 单链表的操作单链表的操作n返回某个位置的元素返回某个位置的元素如果第如果第i个结点存在，将它的数据域的值放到个结点存在，将它的数据域的值放到x中，并返回中，并返回真，否则返回假。真，否则返回假。bool List:GetData(int i, T& x)const LinkNode* nd=Locate(i); if(NULL=nd) return false; x=nd-data; return true;2.3.5 单链表的操作单链表的操作n清空单链表清空单链表 void MakeEmpty();34first255716操作前：操作前：操作后：操作后：first2.

38、3.5 单链表的操作单链表的操作n清空单链表清空单链表 void MakeEmpty();34first255716如果如果first不空，令不空，令iter=first，first=first-next;delete iter;34first5716如果如果first不空，令不空，令iter=first，first=first-next;delete iter;first57162.3.5 单链表的操作单链表的操作n清空单链表清空单链表 void MakeEmpty();如果如果first不空，令不空，令iter=first，first=first-next;delete iter;firs

39、t5716first16如果如果first不空，令不空，令iter=first，first=first-next;delete iter;first2.3.5单链表的操作单链表的操作n清空单链表清空单链表 LinkNode* pnd=NULL; while(first!=NULL) pnd=first; first=first-next; delete pnd; void MakeEmpty();2.3.5 单链表的操作单链表的操作n销毁单链表销毁单链表List();templateList:List() MakeEmpty();调用调用MakeEmpty()函数释放单链表所占用的空间。函数释

40、放单链表所占用的空间。2.3.5 单链表的操作单链表的操作n求单链表的长度求单链表的长度int Length() const;设计一个计数器，遍历单链表，访问一个结点，计数器加设计一个计数器，遍历单链表，访问一个结点，计数器加一。一。34first255716iternum=1；34first255716iternum=2；2.3.5 单链表的操作单链表的操作n求单链表的长度求单链表的长度int Length() const;设计一个计数器，遍历单链表，访问一个结点，计数器加设计一个计数器，遍历单链表，访问一个结点，计数器加一。一。34first255716iternum=3；34first2

41、55716iternum=4；2.3.5 单链表的操作单链表的操作n求单链表的长度求单链表的长度int Length() const;设计一个计数器，遍历单链表，访问一个结点，计数器加设计一个计数器，遍历单链表，访问一个结点，计数器加一。一。 LinkNode * iter=first; int num=0; while(iter) num+; iter=iter-next; return num;2.3.5 单链表的操作单链表的操作n判单链表是否为空判单链表是否为空bool IsEmpty() constreturn first=NULL;2.3.5 单链表的操作单链表的操作n复制单链表中结

42、点复制单链表中结点void CopyList(const List& L);参考单链表的尾插法。参考单链表的尾插法。 if(L.first=NULL) return; newNode=new LinkNode(L.first-data); first=newNode; iter=L.first-next; rear=newNode; while(iter) newNode=new LinkNode(iter-data); rear-next=newNode; iter=iter-next; rear=rear-next; 2.3.5 单链表的操作单链表的操作n拷贝构造函数拷贝构造函数

43、first=NULL; CopyList(L);调用调用CopyList函数完成链表的初始化。函数完成链表的初始化。List(const List& L);2.3.5 单链表的操作单链表的操作n赋值运算符函数赋值运算符函数首先判断是否是自复制，如果不是，调用首先判断是否是自复制，如果不是，调用CopyList函数函数完成链表的复制。完成链表的复制。 if(this=&L) return *this; MakeEmpty(); CopyList(L); return *this;List& operator=(const List& L);2.3.5 单链表的操作

44、单链表的操作n对链表中的节点进行排序对链表中的节点进行排序34first25571625first163457同学们想想怎么办？同学们想想怎么办？2.3.6 带头结点的单链表带头结点的单链表25first163457不带头结点的单链表：不带头结点的单链表：带头结点的单链表：带头结点的单链表：25first163457头结点头结点表头表头表尾表尾表头表头表尾表尾头结点的头结点的data域可以不存储任何信息，也可以存放一个特殊域可以不存储任何信息，也可以存放一个特殊标记或表长。标记或表长。2.3.6 带头结点的单链表带头结点的单链表带头结点的单链表：带头结点的单链表：25first163457头结

45、点头结点表头表头表尾表尾带头结点的单链表为空的情形带头结点的单链表为空的情形first头结点头结点2.3.6带头结点的单链表带头结点的单链表带头结点的单链表：带头结点的单链表：25first163457头结点头结点表头表头表尾表尾带头结点的单链表给表头节点强加了一个带头结点的单链表给表头节点强加了一个“直接前驱直接前驱”，这，这样做的原因是什么？样做的原因是什么？当前表：当前表：34first25插入新节点后：插入新节点后： first255734571616newNode：当前表：当前表：34first25插入新节点后：插入新节点后：first25573457newNode：当前表：当前表：

46、34first25插入新节点后：插入新节点后： first2534newNode：first当前表：当前表：first25插入新节点后：插入新节点后：25newNode：回顾：后插法为什么要分情况讨论？回顾：后插法为什么要分情况讨论？原因：尾插法总是在表尾节点的后面插入节点，空表时没有表尾节原因：尾插法总是在表尾节点的后面插入节点，空表时没有表尾节点。点。当前表：当前表：34first插入新节点后：插入新节点后： first34newNode：first当前表：当前表：first25插入新节点后：插入新节点后：25newNode：带头结点单链表后插法演示。带头结点单链表后插法演示。2525当前

47、表：当前表：34first插入新节点后：插入新节点后：first255757newNode：3425带头节点链表空时，头结点可以看成带头节点链表空时，头结点可以看成“表表尾尾”。rear=first;while(rear-next) rear=rear-next;rear-next=newNode;带头结点单链表后插法。带头结点单链表后插法。当前表：当前表：34first插入新节点后：插入新节点后：first255757newNode：3425first当前表：当前表：first25插入新节点后：插入新节点后：25newNode：当前表：当前表：34first25插入新节点后：插入新节点后：f

48、irst2534newNode：表头插入节点：表头插入节点：Insert(1,34);当前表：当前表：57first25插入新节点后：插入新节点后：first25343457newNode：表中插入节点：表中插入节点：Insert(2,57);表尾插入节点：表尾插入节点：Insert(4,16);当前表：当前表：34first25插入新节点后：插入新节点后： first255734571616newNode：在链表中插入元素时，需要找到插入位置的直接前驱节点，但在链表中插入元素时，需要找到插入位置的直接前驱节点，但单链单链表的表头节点没有直接前驱表的表头节点没有直接前驱，所以必须单独处理。，所

49、以必须单独处理。不带头结点链表插入算不带头结点链表插入算法回顾法回顾表头插入节点：表头插入节点：Insert(1,34);表中插入节点：表中插入节点：Insert(2,57);带头结点链表插入算法带头结点链表插入算法当前表：当前表：25first插入新节点后：插入新节点后： first34newNode：2534当前表：当前表：57first插入新节点后：插入新节点后：first253457newNode：3425带头节点单链表中的头结点可以看成第一个节点的直接前驱，使得不必要单独考虑带头节点单链表中的头结点可以看成第一个节点的直接前驱，使得不必要单独考虑在第一个节点处插入节点的情形。在第一个

50、节点处插入节点的情形。表头插入节点：表头插入节点：Insert(1,34);带头结点链表插入算法带头结点链表插入算法当前表：当前表：25first插入新节点后：插入新节点后： first34newNode：2534 pre=first; for(int j=1; jnext; if(pre=NULL) return false; newNode=new LinkNode(x); newNode-next=pre-next; pre-next=newNode; 当前表：当前表：34删除节点后：删除节点后：first2534first2557删除表头节点删除表头节点:Remove(1,elem);

51、删除表头节点删除表头节点:Remove(2,elem);当前表：当前表：57first25删除节点后：删除节点后：first253434当前表：当前表：34first25删除节点后：删除节点后：first2557345716删除表尾节点删除表尾节点:Remove(4,elem);在链表中删除元素时，需要找到删除位置的直接前驱节点，但在链表中删除元素时，需要找到删除位置的直接前驱节点，但单链单链表的表头节点没有直接前驱表的表头节点没有直接前驱，所以必须单独处理。，所以必须单独处理。不带头结点链表删不带头结点链表删除算法回顾除算法回顾当前表：当前表：34删除节点后：删除节点后：first2534first2557删除表头节点删除表头节点:Remove(1,elem);删除表头节点删除表头节点:Rem