数据结构 线性表

1、主要内容主要内容n线性表的定义线性表的定义n抽象链表类抽象链表类n单链表单链表n循环链表循环链表12.1 线性表的定义线性表的定义n线性表的逻辑结构线性表的逻辑结构n线性表的顺序存储表示线性表的顺序存储表示n线性表的链式存储表示线性表的链式存储表示12.1.1 线性表的逻辑结构线性表的逻辑结构n线性表是线性表是n=0个数据元素个数据元素a1，a2an-1，an的的有序集合有序集合。表中每个元素。表中每个元素ai在表中的位置仅在表中的位置仅取决于元素本身的序号取决于元素本身的序号i。当。当1in时，时，ai的直的直接前驱为接前驱为ai-1，ai的直接后继为的直接后继为ai+1。也就是说，。也就是

2、说，除表中第一个元素除表中第一个元素a1与最后一个元素与最后一个元素an外，其外，其他每个元素他每个元素ai有且仅有一个直接前驱和一个直有且仅有一个直接前驱和一个直接后继；第一个元素接后继；第一个元素a1仅有一个直接后继，最仅有一个直接后继，最后一个元素后一个元素an仅有一个直接前驱。仅有一个直接前驱。 上述这种结构的特点是数据元素之间存在上述这种结构的特点是数据元素之间存在一对一一对一的关系，这种特点的数据结构称为线性的关系，这种特点的数据结构称为线性结构，也称为结构，也称为线性表线性表。 一个线性表可以用一个一个线性表可以用一个标识符标识符来命名。例来命名。例如：如： L=( a1，a2，

3、a3an-1，an ) 注意：同一线性表中的元素必定具有注意：同一线性表中的元素必定具有相同的相同的特性特性，都属于同一数据对象。，都属于同一数据对象。 线性表中的数据元素在不同情况下可能线性表中的数据元素在不同情况下可能有不同的具体含义。有不同的具体含义。 如如 L1 ( 1.2，-2.3，56，0，45.7 ) L2 ( a，d，c，g，j，l ) 在稍微复杂的线性表中，一个数据元素在稍微复杂的线性表中，一个数据元素可以由可以由若干个数据项若干个数据项组成。组成。例如：学生名册：例如：学生名册：010501黎明黎明17男男010502王烟王烟18女女010503曲柳曲柳17女女010504

4、何旦何旦 旦旦19男男010505李美李美16女女12.1.2 线性表的顺序存储方式线性表的顺序存储方式n在计算机内部可以采用两种不同方法来在计算机内部可以采用两种不同方法来表示一个线性表，它们分别是表示一个线性表，它们分别是顺序表表顺序表表示法示法和和链表表示法链表表示法。n 顺序表示法的定义；顺序表示法的定义；n 元素的地址表示；元素的地址表示；n 顺序表示法的优、缺点。顺序表示法的优、缺点。 顺序表示法的定义顺序表示法的定义n顺序表示法用一组顺序表示法用一组地址连续地址连续的存储单的存储单元依次存储线性表的数据元素，这种元依次存储线性表的数据元素，这种存储结构称为线性表的顺序存储结构，存

5、储结构称为线性表的顺序存储结构，并称此时的线性表为并称此时的线性表为顺序表顺序表。 线性表的顺序表示线性表的顺序表示最简单的一种顺序映象方法是：最简单的一种顺序映象方法是： 令令 y y 的存储位置和的存储位置和 x x 的存储位置的存储位置相邻相邻。 顺序映象顺序映象 以以 x 的存储位置和的存储位置和 y 的存储位置的存储位置之间某种关系表示逻辑关系之间某种关系表示逻辑关系。 用一组用一组地址连续地址连续的存储单元的存储单元 依次存放依次存放线性表中的数据元素线性表中的数据元素 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址称作线性表的称作线性表的基地址基地址以以“存储位

6、置相邻存储位置相邻”表示有序对表示有序对 即：即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量一个数据元素所占存储量所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)C 基地址基地址逻辑地址逻辑地址数据元素数据元素存储地址存储地址 数据元素数据元素0k0Loc(k0)k01k1Loc(k0)+ck1ikiLoc(k0)+i*ckin-1kn-1Loc(k0)+(n-1)*ckn-1线性表的顺序存储结构示意图线性表的顺序存储结构示意图 元素的地址表示元素的地址

7、表示n假设线性表的每个元素占用假设线性表的每个元素占用C个存储单元，那个存储单元，那么，在顺序存储结构中，线性表的第么，在顺序存储结构中，线性表的第i+1个数据个数据元素元素ai+1的存储位置与第的存储位置与第i个数据元素个数据元素ai的存储位的存储位置之间满足如下关系：置之间满足如下关系： LOC(ai+1) = LOC(ai)+C LOC(ai) = LOC(a0)+i*CLOC(a0)为线性表的为线性表的首地址或基地址首地址或基地址。 以元素在计算机内存中的以元素在计算机内存中的“物理位置相邻物理位置相邻”来表示线性表中数据元素之间的逻辑关系，来表示线性表中数据元素之间的逻辑关系，只要确

8、定了首地址，线性表中任意数据元只要确定了首地址，线性表中任意数据元素都可以随机存取素都可以随机存取 顺序表示法的优缺点顺序表示法的优缺点优点优点：1）存储密度大、空间利用率高；）存储密度大、空间利用率高；2）数据元素逻辑位置相邻，物理位置也相邻。）数据元素逻辑位置相邻，物理位置也相邻。可随机存取，所以称为随机存取结构。可随机存取，所以称为随机存取结构。缺点缺点：1）插入和删除时要移动大量的元素；）插入和删除时要移动大量的元素；2）长度较大的线性表须按最大需要的空间来）长度较大的线性表须按最大需要的空间来分配存储空间。分配存储空间。12.1.3 线性表的链式存储表示线性表的链式存储表示n链式存储

9、表示的定义链式存储表示的定义n链式存储表示的实现链式存储表示的实现n链式存储表示的特点链式存储表示的特点 线性表的链式表示线性表的链式表示 用一组用一组地址任意地址任意的存储单元存放线性的存储单元存放线性表中的数据元素表中的数据元素以以元素元素(数据元素的映象数据元素的映象) + 指针指针(指示后继元素存储位置指示后继元素存储位置) = 结点结点 (表示数据元素表示数据元素 或或 数据元素的映象数据元素的映象)以以“结点的序列结点的序列”表示线性表表示线性表 称作称作链表链表数据域数据域指针域指针域 结点：数据元素的存储映象，由数据域结点：数据元素的存储映象，由数据域和指针域构成和指针域构成

10、设设a ai i的存储位置为的存储位置为p,p,则则a ai+1i+1的地址的地址q q是：是：q=p-next;q=p-next;a1a2a3a4a5a6an 链式存储方式链式存储方式 链式存储结构不要求逻辑上相邻的数据元素在物链式存储结构不要求逻辑上相邻的数据元素在物 理位置上也相邻；理位置上也相邻；链表：链表：是用一组是用一组地址任意的地址任意的存储单元存储单元存放存放线性线性表的各个表的各个数据元素数据元素，通过保存直接后继的存储位通过保存直接后继的存储位置来表示元素之间的逻辑关系；置来表示元素之间的逻辑关系；所有的所有的数据元素数据元素都分别都分别保存在保存在具有相同数据结构具有相同

11、数据结构的的结点结点中中, ,结点是链表的基本存储单位结点是链表的基本存储单位, ,结点与数结点与数据元素据元素一一对应一一对应；每个结点每个结点在链表中在链表中使用使用一块一块连续的存储空间连续的存储空间, ,而而相邻结点之间不必使用连续的存储空间。相邻结点之间不必使用连续的存储空间。 链式存储表示的特点链式存储表示的特点n逻辑上相邻的元素对应的存储位置是通过逻辑上相邻的元素对应的存储位置是通过指针指针反反映的，不要求物理上相邻。进行插入、删除运算映的，不要求物理上相邻。进行插入、删除运算时，只需修改被插入位置指针域。时，只需修改被插入位置指针域。n一般一般不预先分配不预先分配好足够的存储空

12、间以备使用，当好足够的存储空间以备使用，当有元素插入时，需临时分配一个空的结点空间，有元素插入时，需临时分配一个空的结点空间，填上信息，插入到线性链表中；当某个结点不再填上信息，插入到线性链表中；当某个结点不再使用时，应将其存储空间释放。使用时，应将其存储空间释放。 n不足之处不足之处：每个结点设有一个指针域，存储空间：每个结点设有一个指针域，存储空间的开销较大。的开销较大。12.2 抽象链表类抽象链表类n线性链表的实现线性链表的实现n抽象链表类的定义抽象链表类的定义n抽象链表类中典型成员函数的实现抽象链表类中典型成员函数的实现 链式存储的实现链式存储的实现n 数据元素的存储结构结点数据元素的

13、存储结构结点结点结点 (表示 数据元素的映象数据元素的映象) =元素元素 + 指针指针(指示后继元素的存储位置指示后继元素的存储位置) ai数据域数据域data指针域指针域next结点结点如果结点中只包如果结点中只包含一个指针域，含一个指针域，称为单链表称为单链表n链表是链表是动态数据动态数据结构，通过结构，通过指针（链）指针（链）将将结点结点链接在一起。链接在一起。结点结点包括两部分：包括两部分：数据信息数据信息和链和链接结点的接结点的指针指针；结点分为表头结点和表结点；结点分为表头结点和表结点；n指向链表表头结点的指针指向链表表头结点的指针(表头指针表头指针，也称为，也称为头头指针指针)；

14、n表头结点表头结点(链表的第一个结点链表的第一个结点)，一般不存放数，一般不存放数据元素的信息；据元素的信息；n表结点表结点（数据结点数据结点，也称为，也称为结点结点，保存数据信保存数据信息息）。）。 链表结点与组成链表结点与组成线性链表的相关术语线性链表的相关术语n表头指针：表头指针：存放线性链表中第一个结点的存存放线性链表中第一个结点的存储地址；储地址；n空指针：空指针：不指向任何结点，线性链表最后一不指向任何结点，线性链表最后一个结点的指针通常是指针；个结点的指针通常是指针；n表头结点：表头结点：线性链表的第一线性链表的第一数据数据元素结点前元素结点前面的一个附加结点，称为头结点。头结点

15、不面的一个附加结点，称为头结点。头结点不保存数据。保存数据。n带表头结点的线性链表：带表头结点的线性链表：第一元素结点前面第一元素结点前面增加一个附加结点的线性链表称为带头结点增加一个附加结点的线性链表称为带头结点的线性链表。的线性链表。n 链表的图示链表的图示NULL表头指针表头指针表头结点表头结点数据结点数据结点数据结点数据结点数据结点数据结点数据结点数据结点template class ListNode public: ListNode( ) next = Null;/无参数，构造一个空结点无参数，构造一个空结点 ListNode(const type &item, ListNo

16、de *next1=NULL) /带参数，构造一个非空结点带参数，构造一个非空结点 data=item; next=next1; /包含数据域和指针域包含数据域和指针域 type data; /结点的数据域结点的数据域 ListNode *next; ;/结点的指针域结点的指针域 datanext 链表结点类的定义链表结点类的定义n 获取表头指针；获取表头指针；n 求链表的长度；求链表的长度；n 寻找第寻找第i个数据元素；个数据元素；n 根据关键字值求数据元素在链表中的位根据关键字值求数据元素在链表中的位置；置；n 插入数据元素；插入数据元素；n 修改数据元素的值；修改数据元素的值；n 删除数

17、据元素。删除数据元素。 链表的常用操作链表的常用操作12.2.2 抽象链表类的定义抽象链表类的定义n线性链表有线性链表有3种：单链表、循环链表与双向种：单链表、循环链表与双向链表；链表；n抽象出上述三种线性链表的相同点（结点、抽象出上述三种线性链表的相同点（结点、指针和相同操作），建立一个抽象链表类，指针和相同操作），建立一个抽象链表类，再由此抽象链表类派生出新的链表类（单链再由此抽象链表类派生出新的链表类（单链表和循环链表）；表和循环链表）；n采用类模板机制；采用类模板机制；n增加表头结点，统一空表和非空表的操作。增加表头结点，统一空表和非空表的操作。 抽象链表类定义抽象链表类定义templ

18、ate /抽象类链表的定义抽象类链表的定义class ablist public: ListNode*GetHead( ) /获得表头结点指针获得表头结点指针 return head; /取出链表中的第取出链表中的第i个元素个元素 type Get(int i); 抽象链表类定义抽象链表类定义 /将链表中第将链表中第i个结点元素值设置为个结点元素值设置为x bool Set(type x, int i); /寻找数据元素值为寻找数据元素值为value的结点地址的结点地址 ListNode*Find1(type value); /寻找链表中第寻找链表中第i个结点元素的地址个结点元素的地址 Lis

19、tNode*Find(int i); void MakeEmpt( ); /将链表置为空表将链表置为空表 /纯虚纯虚函数，取得结点函数，取得结点n n的下一个结点位置的下一个结点位置 virtual ListNode *GetNext (ListNode&n)=0; /纯虚函数，将新元素纯虚函数，将新元素value插入到第插入到第i个位置个位置 virtual int Insert(type value, int i)=0; /纯虚函数纯虚函数，将新元素将新元素value插入到链表表头处插入到链表表头处 virtual int Insert(type value)=0; /纯虚函数，将

20、链表中第纯虚函数，将链表中第i个结点删去个结点删去 virtual int Remove(int i)=0; /纯虚函数，将元素值为纯虚函数，将元素值为value的结点删去的结点删去 virtual int Remove(type value)=0; protected: /链表的数据成员：头指针和表长链表的数据成员：头指针和表长 ListNode *head; int length; ;12.2.3 抽象链表成员函数的实现抽象链表成员函数的实现n设置函数设置函数：将第：将第i个结点数据元素值设个结点数据元素值设为为x。templatebool ablist:Set(type x, int i

21、) ListNode *p = Find(i); /寻找第寻找第i个结点位置个结点位置 if(p=NULL|p=head) /i值不合法或为空表，返回值不合法或为空表，返回false return false; else p-data=x; /修改第修改第i个结点的数据元素值个结点的数据元素值 return ture;n 取值函数：取值函数：返回第返回第i个结点的数据元素值。个结点的数据元素值。templatetype ablist:Get(int i) /寻找指向第寻找指向第i个结点位置个结点位置 ListNode *p=Find(i); assert (p & p!=head);

22、/p不空也不为表头不空也不为表头 return p-data; /返回第返回第i个结点的数据元素值个结点的数据元素值n 清空链表清空链表：用：用q指向第一个结点，当链表不空指向第一个结点，当链表不空时，循链逐个删除，仅保留表头结点。时，循链逐个删除，仅保留表头结点。templatevoid ablist:MakeEmpty() ListNode *q=head-next; int i=1; /链表不空，所以至少有一个结点链表不空，所以至少有一个结点 while(i+ next=q-next; delete q; /循链逐个删除，仅保留表头结点循链逐个删除，仅保留表头结点 q=head-next

23、; length=0;n 搜索数据元素值为搜索数据元素值为value的结点的结点templateListNode*ablist:Find1(type value) ListNode *p=head-next; int i=1; /循环条件包含空链表的情况循环条件包含空链表的情况 while (i+ data!=value) p=p-next; /循链找数据元素值循链找数据元素值value的结点的结点 return p;n 定位函数定位函数：返回链表中第：返回链表中第i个元素结点的地址个元素结点的地址templateListNode*ablist:Find(int i) if(ilength)

24、return NULL; if(i=0) return head; /i=0时返回表头结点的地址时返回表头结点的地址 ListNode*p=head-next; /让检测指针让检测指针p指向表指向表 中第中第1个结点个结点 int j=1; while(p!=NULL & jnext; j+; return p; /返回第返回第i个结点地址个结点地址12.3 单链表单链表n单链表的定义单链表的定义n单链表类的定义单链表类的定义n单链表常用成员函数的实现单链表常用成员函数的实现n单链表举例：一元多项式加法单链表举例：一元多项式加法12.3.1 单链表的定义单链表的定义n单链表的定义单链表

25、的定义n带表头结点的单链带表头结点的单链表表 单链表的定义单链表的定义n单链表用一组任意的存储单元来存储线性单链表用一组任意的存储单元来存储线性表的各个数据元素，这些存储单元可以是表的各个数据元素，这些存储单元可以是连续的，也可以是不连续的；连续的，也可以是不连续的；n为了表示线性表中每个元素与其直接后继为了表示线性表中每个元素与其直接后继元素之间的逻辑关系，单链表由一个个结元素之间的逻辑关系，单链表由一个个结点组成，每个点组成，每个结点结点作为数据元素的存储结作为数据元素的存储结构，包含数据域（构，包含数据域（data）和指针域（）和指针域（next）两部分。两部分。 以线性表中第一个数据元

26、素以线性表中第一个数据元素 的存的存储地址储地址作为线性表的地址，称作线性表作为线性表的地址，称作线性表的的头指针头指针。1a头结点头结点 a1 a2 . an 头指针头指针 有时为了操作方便，在第一个结点之有时为了操作方便，在第一个结点之前虚加一个前虚加一个“头结点头结点”，以，以指向头结点指向头结点的指针的指针为链表的头指针为链表的头指针。空指针线性表为空表时，线性表为空表时，头结点的指针域为空头结点的指针域为空 线性表的线性表的n个数据元素对应的个数据元素对应的n个结点通过链个结点通过链接方式链接成一个链表，每个结点只有一个指接方式链接成一个链表，每个结点只有一个指针域，所以称为针域，所

27、以称为单链表单链表。 可以将线性表（可以将线性表（a1，a2，a3.an-1，an）直）直观地表示成用指针相链接的结点序列。观地表示成用指针相链接的结点序列。a ai-1i-1a ai ia a2 2a a1 1a ai+1i+1na an nheadhead 整个单链表可以由一个称为整个单链表可以由一个称为头结点头结点的的head来指出，标明单链表的来指出，标明单链表的首地址首地址； 当链表为空时，当链表为空时，head =NULL； 单链表可以由头结点指针唯一确定；单链表可以由头结点指针唯一确定； 链表中任意结点的存储位置都可以从链表中任意结点的存储位置都可以从head开始，通过对链表进行

28、遍历得到；开始，通过对链表进行遍历得到； 设设p指向元素指向元素ai，则元素，则元素ai+1的地址的地址q是：是： q=p-next 带表头结点的单链表带表头结点的单链表n为了算法设计的方便，往往为每一个链表加为了算法设计的方便，往往为每一个链表加上一个表头结点上一个表头结点 。NULL表头结点表头结点表头指针表头指针head( (不含数据结点的空链表不含数据结点的空链表)p表头指针表头指针表头结点表头结点head数据结点数据结点name1NULLn带头结点的单向链表带头结点的单向链表a ai-1i-1a ai ia a2 2a a1 1a ai+1i+1na an nheadheadnhea

29、dhead空表空表怎样判断怎样判断带头结点的单向链表带头结点的单向链表是否为空表？是否为空表？ 如果：如果：head-next = NULL head-next = NULL 成立，则为空表。成立，则为空表。等价：等价： 如果：如果：head-next != NULL head-next != NULL 成立，则不是空表。成立，则不是空表。n不带头结点的单向链表不带头结点的单向链表a ai-1i-1a ai ia a2 2a a1 1a ai+1i+1na an nheadheadNULLNULLheadhead空表：空表：head=NULL怎样判断怎样判断不带头结点的单向链表不带头结点的单向

30、链表是否为空表？是否为空表？ 如果：如果：head = NULL head = NULL 成立，则为空表。成立，则为空表。等价：等价： 如果：如果：head != NULL head != NULL 成立，则不是空表。成立，则不是空表。n结点之间的基本关系结点之间的基本关系a a3 3a a4 4a a2 2a a5 5p pp-next =q qr rs sq则下列关系成立：则下列关系成立：r-next =s=q- next-next=p- next-next-next通过当前结点通过当前结点 p p 要访问要访问下一个下一个结点，则指向结点，则指向下一下一个个结点的指针为：结点的指针为：p

31、-nextp-next通过当前结点通过当前结点 p p 要访问要访问下一个下一个结点的结点的下一个下一个：p-next-nextp-next-next12.3.2 单链表类的定义单链表类的定义n单链表是简单的链表，可以直接从抽象链表类派单链表是简单的链表，可以直接从抽象链表类派生出来，定义如下：生出来，定义如下：class List：public ablist public： List（）（） /构造函数，建立一个空链表构造函数，建立一个空链表 head = new ListNode ；length = 0； /构造函数，用于通过一个现有链表建立新链表构造函数，用于通过一个现有链表建立新链表

32、List（List & l） Copy（l）；）； List（）（）/析构函数析构函数 MakeEmpty( ); delete head; /将链表置空将链表置空 /将新元素插入在链表中第将新元素插入在链表中第i个位置个位置 bool Insert(type value, int i); type Remove(int i); /将链表中第将链表中第i个结点删去个结点删去 type Remove1(type value); /删去表中值为删去表中值为value的结点的结点 /取得结点取得结点n n的下一个结点位置的下一个结点位置 ListNode *GetNext(ListNode

33、& n); List & Copy(List & l); /拷贝函数拷贝函数 /重载赋值运算符重载赋值运算符, 同类型链表赋值同类型链表赋值 List & operator =(List & l); /重载输出运算符重载输出运算符 friend ostream & operator (ostream &, List &); ;说明：说明：（1） 定义了两个构造函数定义了两个构造函数, 一个用来构造一个用来构造一个空链表，仅生成一个头结点（头结点一个空链表，仅生成一个头结点（头结点数据域中可以为空，也可以来放一些和链数据域中可以为空

34、，也可以来放一些和链表相关的数据），并将表头表相关的数据），并将表头head初始化为初始化为NULL；另一个是利用一个现有链表建立新；另一个是利用一个现有链表建立新链表；析构函数用来回收元素结点所占的链表；析构函数用来回收元素结点所占的内存；内存；说明：说明：（2） 对于在抽象链表中定义三个纯虚函数：对于在抽象链表中定义三个纯虚函数：Insert（type，int）、）、Remove（int）、）、Remove1（type）。在单链表中，应给出其具）。在单链表中，应给出其具体实现，用来实现链表的插入、删除操作；体实现，用来实现链表的插入、删除操作；（3） 重载了二个运算符，赋值运算符用于同重载

35、了二个运算符，赋值运算符用于同类型链表赋值，输出运算符用于输出一个链类型链表赋值，输出运算符用于输出一个链表；还有一个拷贝函数用于同类型单链表的表；还有一个拷贝函数用于同类型单链表的拷贝。拷贝。12.3.3 单链表常用成员函数实现单链表常用成员函数实现n在第在第i个位置插入一个新结点个位置插入一个新结点n删除链表指定位置删除链表指定位置i处的结点处的结点n删除数据元素为删除数据元素为value的结点的结点n拷贝链表拷贝链表n取得结点取得结点n的下一个位置的下一个位置n重载赋值运算符重载赋值运算符*n重载输出运算符重载输出运算符* 在单链表第在单链表第i个位置插入一个新结点个位置插入一个新结点n

36、基本原理基本原理: :寻找插入点的寻找插入点的前一个位置前一个位置i-1i-1; ;若为空表，应将表尾指针指向新结点若为空表，应将表尾指针指向新结点; ;从内存中从内存中申请一个新的空结点申请一个新的空结点，将数据信，将数据信息置于新结点的数据域内。息置于新结点的数据域内。n插入新结点步骤：插入新结点步骤：v链接后面指针链接后面指针 p-next = q-next ;v 链接前面指针链接前面指针 q-next = p ;v定位定位 指针指针 q 指向第指向第 i-1 个结点，个结点，指针指针 p 指向需要指向需要插入插入的结点。的结点。headD3D2D1D0表头结点表头结点 数据结点数据结点

37、 数据结点数据结点 数据结点数据结点 数据结点数据结点pqxtemplatebool List:Insert(type value，int i) ListNode *q=Find(i-1); /定位插入点的前一位置定位插入点的前一位置 if(q=NULL) return false; /i值不合理，返回值不合理，返回false /创建新元素结点创建新元素结点 ListNode *p= new ListNode (value,p-next); assert(p); p-next=q-next; q-next=p; length+; return true; 删除指定位置删除指定位置i i处的结点

38、处的结点n利用利用Find(i-1)函数找到函数找到第第i-1个个元素结点；元素结点；n保留被删结点保留被删结点的数据值，的数据值，重新拉链重新拉链(摘链摘链)；n若被删结点为表尾结点时，修改表尾指针若被删结点为表尾结点时，修改表尾指针;n最后应最后应释放释放被删结点的内存空间被删结点的内存空间;n将链表长度减将链表长度减1。 n在链表中删除第在链表中删除第 i 个结点个结点（基本原理基本原理）headD3D2D1D0表头结点表头结点数据结点数据结点数据结点数据结点数据结点数据结点数据结点数据结点pqxv 摘链摘链 p-next = q-next ;v 释放释放 q节点节点 delete q

39、;v 定位定位 指针指针 p 指向第指向第 i-1 个结点，指针个结点，指针 q 指向被指向被删除删除的结点的结点templatetype List:Remove(int i) /p定位于第定位于第i-1个元素结点个元素结点 ListNode *p=Find(i-1), *q; assert(p & p-next); /p不为空且不为最后一个元素地址不为空且不为最后一个元素地址 q=p-next; /q指向将被删除的元素指向将被删除的元素 p-next=q-next; /重新链接（摘链）重新链接（摘链） type value=q-data; /保留被删除结点的数据值保留被删除结点的数据

40、值 delete q; /释放被删结点的空间释放被删结点的空间 length-; return value; 删除元素值为删除元素值为value的结点的结点n循链寻找数据值为循链寻找数据值为value的的前一结点；前一结点；n若已至表尾，且其值不为若已至表尾，且其值不为value，返回，返回NULL；n否则，否则，重新拉链重新拉链，将此结点断开（摘链）；，将此结点断开（摘链）；n若被删结点为表尾结点时，应修改表尾指针；若被删结点为表尾结点时，应修改表尾指针；n回收回收被删结点的内存空间，将链表长度减被删结点的内存空间，将链表长度减1。templatetype List:Remove1(type

41、 value) ListNode *q，*p=head; /循链寻找数据值为循链寻找数据值为valuevalue的前一结点的前一结点 while(p-next!=NULL & p-next-data!=value) p=p-next; assert(p-next); /p不是表尾，继续不是表尾，继续 q=p-next; /q指向将删除的元素指向将删除的元素 p-next=q-next; /重新接链，删除此结点重新接链，删除此结点 delete q; length-; return value; 拷贝链表：拷贝链表：将链表将链表l l拷贝给当前链表对象拷贝给当前链表对象算法：算法：n判断

42、链表判断链表l是否为空，若链表是否为空，若链表l为空，返回；为空，返回；n若不空，为当前链表头结点分配存储空间；若不空，为当前链表头结点分配存储空间；n将链表将链表l头结点内容复制给当前链表头结点；头结点内容复制给当前链表头结点；n循链进行结点间的赋值；循链进行结点间的赋值；n赋值过程为：建立一个新结点、给结点赋值、将其赋值过程为：建立一个新结点、给结点赋值、将其链接到当前链表表尾，将当前链表指针链接到当前链表表尾，将当前链表指针p后移，再后移，再将链表将链表l指针指针q后移。后移。templateList& List:Copy(List &l) ListNode *p，*q，

43、*r; length = l.length; /复制链表长度复制链表长度 head=NULL; if(!l.head) /若链表若链表1为空，返回为空，返回 return *this;/为当前链表头结点分配存储为当前链表头结点分配存储head=new ListNode; if(!head) return *this; /若分配失败，返回若分配失败，返回head-data=(l.head)-data; /将链表将链表1头结点内容头结点内容 复制给当前链表头结点复制给当前链表头结点 head-next=NULL; r=NULL;p=head; / p指向当前链表头指向当前链表头 /将将q指向链表指

44、向链表1的第二个结点的第二个结点q=l.head-next; while(q) /从第二个结点至链尾进行结点间的赋值从第二个结点至链尾进行结点间的赋值 r=new ListNode; /建立一个新结点建立一个新结点 if(!r) return *this; /失败，返回失败，返回 r-data=q-data; /给结点赋值给结点赋值 r-next=NULL; p-next=r; /将新结点链接到当前链表头结点后面将新结点链接到当前链表头结点后面 p=p-next; /当前链表指针后移，当前链表指针后移，p指向第一个结点指向第一个结点 q=q-next; /链表链表1指针后移指针后移 retur

45、n *this; template /函数模板函数模板ListNode * List:GetNext(ListNode & n) ListNode *p=&n; if(p=NULL | n.next=NULL) /n不合法不合法,函数返回函数返回NULL return NULL; return n.next; 取得结点取得结点n的下一个位置的下一个位置GetNext12.3.5 单链表举例单链表举例nnnxPxPxPPxP2210)(),(210nPPPPP可用线性表可用线性表P P表示表示200001000231)(xxxS但对但对S(x)S(x)多项式浪费空间多项式浪费空间

46、一般一般emmnxPxPxPxPee2121)(其中其中为非零系数）（iPemee210用数据域含两个数据项的线性表表示用数据域含两个数据项的线性表表示emPePePm，2121其存储结构可以用顺序存储结构，也可以用单链表其存储结构可以用顺序存储结构，也可以用单链表一元多项式的表示及相加一元多项式的表示及相加12.3.5 单链表举例单链表举例coefexpnext 如果在线性链表中仅存储系数非零的那些项，则多如果在线性链表中仅存储系数非零的那些项，则多项式中的每个系数非零项对应一个具有三个域的链表项式中的每个系数非零项对应一个具有三个域的链表结点，结点的结构如下：结点，结点的结构如下： coe

47、f存放系数，存放系数， exp存放指数，存放指数， next域存放指向下域存放指向下一项所在结点的指针。一项所在结点的指针。12.3.5 单链表举例单链表举例假设假设Bm(x)为一元为一元m阶多项式，阶多项式， An(x)为一元为一元n阶多项式，则阶多项式，则Bm(x)与与An(x)的相加运算的相加运算Cn(x)= An(x) +Bm(x)，用线性表表示为：，用线性表表示为：C=(an, an-1, , am+1, am+bm, am-1+bm-1, , a0+b0)式中，假设式中，假设nm12.3.5 单链表举例单链表举例178728717259229117)()()(9228)(5937)

48、(xxxxxxBxAxCxxxxBxxxxA-1A7 0 3 1 9 2 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 9 2 22 7 5 17 -9 8 一元多项式加法运算一元多项式加法运算两个多项式中所有指数相同的项对应的两个多项式中所有指数相同的项对应的系数相加，若系数和不为零，则构成系数相加，若系数和不为零，则构成“和多和多项式项式”中的一项，而将所有指数不相同的那中的一项，而将所有指数不相同的那些项复制到些项复制到“和多项式和多项式”中。中。 算法中可设置两个活动指针变量算法中可设置两个活动指针变量p和和q，它们分别沿着它们分别沿着A链表与链表与B链表依次访问

49、链链表依次访问链表中的结点，表中的结点，p的初值为的初值为A，q的初值为的初值为B，即分别指向各自链表的第一个结点。即分别指向各自链表的第一个结点。 算法的核心：算法的核心： 比较比较p和和q所指结点的所指结点的exp域的值。域的值。若相同，则将两结点的系数域值相加，若相加的结若相同，则将两结点的系数域值相加，若相加的结果不为果不为0，则把这个结果和相应指数分别存入，则把这个结果和相应指数分别存入C链表中链表中新分配的空结点的系数域和指针域；新分配的空结点的系数域和指针域；若若p与与q所指的结点指数不同，先将指数较低的哪一所指的结点指数不同，先将指数较低的哪一项复制到项复制到C链表中，然后将链

50、表中，然后将p或者或者q移向下一个结点；移向下一个结点；重复上述步骤，当重复上述步骤，当p=NULL（或（或q=NULL）时，就）时，就将将B链表（或链表（或A链表）中剩余的部分复制到链表）中剩余的部分复制到C链表中，链表中，直到直到p、q均为空时算法结束。均为空时算法结束。12.4 循环链表循环链表n循环链表循环链表（带有头结点的单向环表）（带有头结点的单向环表） 最后一个结点的指针域的指针又指回第一个结最后一个结点的指针域的指针又指回第一个结点（头结点）的链表。点（头结点）的链表。 a1 a2 . an 与单向链表的差别仅在于，与单向链表的差别仅在于，判别判别链表中最后一链表中最后一个结点

51、的个结点的条件条件不再是不再是“后继是否为空后继是否为空”，而是，而是“后后继是否为头结点继是否为头结点”。h空表空表判断为是否空表的条件：判断为是否空表的条件：h-next = h12.4 循环链表循环链表n循环链表的特点循环链表的特点1.从一个结点可找到链表中的任意一个结点；从一个结点可找到链表中的任意一个结点；2.判断是否为表尾结点的条件：判断是否为表尾结点的条件：p-next = h。3.有时，用表尾指针表示循环链表。有时，用表尾指针表示循环链表。pa ai-1i-1a ai ia a1 1a ai+1i+1na an nh hra ai-1i-1a ai ia a1 1a ai+1i

52、+1na an nJosephusJosephus问题问题n n个人围坐在一圆桌周围，现从第个人围坐在一圆桌周围，现从第s s个人开始报数，个人开始报数，数到第数到第m m的人出列，然后从出列的下一个人重新开始的人出列，然后从出列的下一个人重新开始报数，数到第报数，数到第m m的人又出列，如此反复直到所有的人的人又出列，如此反复直到所有的人全部出列为止。全部出列为止。JosephusJosephus问题是：对于任意给定的问题是：对于任意给定的n,sn,s和和m m，求出按出列次序得到的，求出按出列次序得到的n n个人员的序列。个人员的序列。现以现以n=8n=8，s=1s=1，m=4m=4为例，

53、问题的求解过程如下列为例，问题的求解过程如下列图所示。图中图所示。图中s s1 1指向开始报数位置，带圆圈的是本次指向开始报数位置，带圆圈的是本次应出列人员。若初始顺序为应出列人员。若初始顺序为n1n1，n2n2，n3n3，n4n4，n5n5，n6n6，n7n7，n8n8，则问题的解为，则问题的解为n4n4，n8n8，n5n5，n2n2，n1n1，n3n3，n7n7，n6n6。 (c) n4 n8 n5 (d) n4 n8 n5 n2 (c) n4 n8 n5 (d) n4 n8 n5 n2 (a) n4 (b) n4 n8 (e) n4 n8 n5 n2 n1 (f) n4 n8 n5 n2

54、 n1 n3 (g) n4 n8 n5 n2 n1 n3 n7 (h) n4 n8 n5 n2 n1 n3 n7 n6(g) n4 n8 n5 n2 n1 n3 n7 (h) n4 n8 n5 n2 n1 n3 n7 n6步骤：步骤：1. 1. 建立顺序表：建立顺序表：利用线性表的一些运算如利用线性表的一些运算如创建空线性表、插入元素等构造创建空线性表、插入元素等构造JosephusJosephus表表 2. 2. 出列：出列：从从JosephusJosephus表中的第表中的第s s个结点开始个结点开始寻找、输出和删除表中的第寻找、输出和删除表中的第m m个结点，然后个结点，然后再从该结点后

55、的下一结点开始寻找、输出和再从该结点后的下一结点开始寻找、输出和删除表中的第删除表中的第m m个结点，重复此过程，直到个结点，重复此过程，直到JosephusJosephus表中的所有元素都删除表中的所有元素都删除 顺序表方式实现顺序表方式实现 循环链表方式实现循环链表方式实现步骤步骤1. 1. 建立循环单链表建立循环单链表2. 2. 寻找第寻找第s s个结点，输出并删除第个结点，输出并删除第m m个节点个节点本章小结本章小结1.了解线性表的逻辑结构特性是数据元素之间存了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。的线性表简称为链表。2. 熟练掌握这两类存储结构的描述方法，以及线熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。性表的各种基本操作的实现。3. 能够从时间和空间复杂度的角度综合比较线性能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合表两种存储结构的不同特点及其适用场合。动态申请内存操作符 newnew 类型