1、1单链表数据结构电子教案数据结构电子教案2 2n特点特点u 每个元素每个元素(表项表项)由结点由结点(Node)构成。构成。u 线性结构线性结构u结点之间可以连续，可以不连续存储结点之间可以连续，可以不连续存储u结点的逻辑顺序与物理顺序可以不一致结点的逻辑顺序与物理顺序可以不一致u表可扩充表可扩充data linka1a2a3a4a5first3 3单链表的存储映像单链表的存储映像free(a)可利用存储空间可利用存储空间a0a2a1a3 freefirst(b)经过一段运行后的单链表结构经过一段运行后的单链表结构4 4单链表的结构定义单链表的结构定义n在在C中定义单链表的结构十分简单中定义单
2、链表的结构十分简单：typedef int T;/结点数据的类型结点数据的类型 typedef struct node /结点结构定义结点结构定义 T data;/结点数据域结点数据域 struct node*link;/结点链接指针域结点链接指针域 ChainNode;/结点命名结点命名n这是一个递归的定义。这是一个递归的定义。n在结构定义时不考虑操作，以后在定义和在结构定义时不考虑操作，以后在定义和实现链表操作时直接使用结构的成分。实现链表操作时直接使用结构的成分。5 5单链表的类定义单链表的类定义6 6 class Chain;/复合方式 class ChainNode /链表结点类 f
3、riend class Chain;/链表类为其友元类 private:int data;/结点数据,ChainNode*link;/结点指针;class Chain /链表类 private:ChainNode*first;/表头指针;7 7class Chain /嵌套方式private:class ChainNode /嵌套链表结点类 public:int data;ChainNode*link;ChainNode*first;/表头指针public:/链表操作;8 8/链表类和链表结点类定义链表类和链表结点类定义(继承方式继承方式)class ChainNode /链表结点类 prot
4、ected:int data;ChainNode*link;class Chain:public class ChainNode /链表类,继承链表结点类的数据和操作 private:ChainNode*first;/表头指针;9 9n在在复合方式复合方式中，链表结点类中声明链表类是中，链表结点类中声明链表类是它的友元类，这样可以它的友元类，这样可以“奉献奉献”它的私有成它的私有成员给链表类。这种方式灵活。员给链表类。这种方式灵活。n在在嵌套方式嵌套方式中，链表结点类是链表类的私有中，链表结点类是链表类的私有成员，这样限制了链表结点类的应用范围。成员，这样限制了链表结点类的应用范围。n在在继承
5、方式继承方式中，链表类声明为链表结点类的中，链表类声明为链表结点类的派生类，这在实现上是可行的。但在逻辑上派生类，这在实现上是可行的。但在逻辑上是有问题的，如是有问题的，如三角形三角形 is 多边形（继承关系）多边形（继承关系）链表链表 is 链表结点（显然概念不准确）链表结点（显然概念不准确）1010/链表类和链表结点类定义链表类和链表结点类定义(结构方式结构方式)struct ChainNode /链表结点类 int data;ChainNode*link;class Chain /链表类,直接使用链表结点类的数据和操作 private:ChainNode*first;/表头指针;/链表中
6、的结点属于链表私有，别人无法访问11 11单链表中的插入与删除操作单链表中的插入与删除操作n插入插入第一种情况：在链表最前端插入第一种情况：在链表最前端插入 newnode-link=first;first=newnode;firstnewnodenewnodefirst1212u 第二种情况：在链表中间插入第二种情况：在链表中间插入 newnode-link=current-link;current-link=newnode；newnodecurrentnewnodecurrent1313第三种情况：在链表末尾插入第三种情况：在链表末尾插入 newnode-link=current-link
7、;current-link=newnode；newnodenewnodecurrentcurrent 1414单链表的插入算法单链表的插入算法bool Chain:Insert(int i,int x)/将新元素 x 插入到第 i 个结点之后。i 从1开始，/i=0 表示插入到首元结点之前。if(first=NULL|i=0)/空表或首元结点前 ChainNode*newNode=new ChainNode(x);/建立一个新结点 newNode-link=first;first=newNode;/新结点成为首元结点 else /否则，寻找插入位置 ChainNode*current=firs
8、t;int k=1;1515 while(k link;k+;if(current=NULL&first!=NULL)/链短 cerr link=current-link;current-link=newNode;return true;1616n删除删除u第一种情况第一种情况:删除表中第一个元素删除表中第一个元素u第二种情况第二种情况:删除表中或表尾元素删除表中或表尾元素在单链表中删除含在单链表中删除含 的结点的结点ai-1ai-1aiaiai+1ai+1pq删除前删除后1717单链表的删除算法单链表的删除算法bool Chain:Remove(int i,int&x)/将链表中的第 i 个
9、元素删去,i 从1开始。ChainNode*del;/暂存删除结点指针if(i link;else ChainNode*current=first;k=1;/找i-1号结点 while(k link;k+;if(current=NULL|current-link=NULL)cout link;/删中间/尾结点 current-link=del-link;x=del-data;delete del;/取出被删结点数据 return true;n实现单链表的插入和删除算法，不需要移动实现单链表的插入和删除算法，不需要移动元素，只需修改结点指针，比顺序表方便。元素，只需修改结点指针，比顺序表方便。n
10、情况复杂，要专门讨论空表和在表头插入的情况复杂，要专门讨论空表和在表头插入的特殊情形。特殊情形。n寻找插入或删除位置只能沿着链顺序检测。寻找插入或删除位置只能沿着链顺序检测。1919带表头结点的单链表带表头结点的单链表n表头结点位于表的最前端，本身不带数据，表头结点位于表的最前端，本身不带数据，仅标志表头。仅标志表头。n设置表头结点的目的是设置表头结点的目的是统一空表与非空表的统一空表与非空表的操作操作，简化链表操作的实现简化链表操作的实现。0an-1a1firstfirst02020 newnode-link=p-link;p-link=newnode;firstnewnodefirstne
11、wnode插入firstnewnode0firstnewnode0插入pppp2121 q=p-link;p-link=q-link;delete q;(非空表）非空表）(空表）空表）firstfirstfirst0first0pqpq2222单链表的模板类单链表的模板类n类模板将类的数据成员和成员函数设计得类模板将类的数据成员和成员函数设计得更完整、更灵活。更完整、更灵活。n类模板更易于复用。类模板更易于复用。n在单链表的类模板定义中，增加了在单链表的类模板定义中，增加了表头结表头结点点。2323 用模板定义的单链表类用模板定义的单链表类template /定义在“LinkedChain.h
12、”struct ChainNode /链表结点类的定义 T data;/数据域 ChainNode*link;/链指针域 ChainNode()link=NULL;/构造函数 ChainNode(T item,ChainNode*ptr=NULL)data=item;link=ptr;/构造函数 bool operator=(T x)return data=x;/重载函数，判相等 bool operator!=(T x)return data!=x;2424template class Chain/单链表类定义,不用继承也可实现protected:ChainNode*first;/表头指针pu
13、blic:Chain()first=new ChainNode;/构造函数 Chain(T x)first=new ChainNode(x);Chain(Chain&L);/复制构造函数 Chain()/析构函数 void makeTmpty();/将链表置为空表 int Length()const;/计算链表的长度2525 ChainNode*Search(T x);/搜索含x元素ChainNode*Locate(int i);/定位第i个元素 T*getData(int i);/取出第i元素值 void setData(int i,T x);/更新第i元素值bool Insert(int
14、i,T x);/在第i元素后插入bool Remove(int i,T&x);/删除第i个元素 bool IsTmpty()const /判表空否 return first-link=NULL?true:false;ChainNode*getFirst()const return first;void setFirst(ChainNode*f)first=f;void Sort();/排序;2626template void Chain:makeTmpty()ChainNode*q;while(first-link!=NULL)q=first-link;/保存被删结点 first-link=q
15、-link;/从链上摘下该结点 delete q;/删除 ；链表置空算法（保留表头结点）链表置空算法（保留表头结点）2727firstqfirstfirstqqfirsta0a1a1a2a2a2current2828template int Chain:Length()const ChainNode*p=first-link;/检测指针 p 指示第一号结点 int count=0;while(p!=NULL)/逐个结点检测 p=p-link;count+;return count;求单链表的长度的算法求单链表的长度的算法2929firstpa0a1a2c=0firstpa0a1a2c=1fir
16、stpa0a1a2c=2firstpa0a1a2c=33030单链表的搜索算法单链表的搜索算法template ChainNode*Chain:Search(T x)/在表中搜索含数据x的结点,搜索成功时函数返/该结点地址;否则返回NULL。ChainNode*current=first-link;while(current!=NULL¤t-data!=x)current=current-link;/沿着链找含x结点 return current;3131单链表的定位算法单链表的定位算法template ChainNode*Chain:Locate(int i)/函数返回表中第 i
17、 个元素的地址。若i 0或 i 超/出表中结点个数，则返回NULL。if(i 0)return NULL;/i不合理 ChainNode*current=first;int k=0;while(current!=NULL&k link;k+;return current;/返回第 i 号结点地址或NULL;3232单链表的插入算法单链表的插入算法template bool Chain:Insert(int i,T x)/将新元素 x 插入在链表中第 i 个结点之后。ChainNode*current=Locate(i);if(current=NULL)return false;/无插入位置Ch
18、ainNode*newNode=new ChainNode(x);/创建新结点 newNode-link=current-link;/链入 current-link=newNode;return true;/插入成功;3333单链表的删除算法单链表的删除算法template bool Chain:Remove(int i,T&x)/删除链表第i个元素,通过引用参数x返回元素值 ChainNode*current=Locate(i-1);if(current=NULL|current-link=NULL)return false;/删除不成功 ChainNode*del=current-link;current-link=del-link;x=del-data;delete del;return true;3434其余操作见课本139页ninsertBacknConcatenatenreverse
