第二章线性表

1、若结构是非空有限集，则有且仅有一个开始结若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a a1 1 , a, a2 2 , , a, , an n） 只有一个首结点和尾结点；只有一个首结点和尾结点； 除首尾结点外，其他结点只有一个直接前驱和一除首尾结点外，其他结点只有一个直接前驱和一个直接后继。个直接后继。线性结构表达式：（线性结构表达式：（a a1 1 , a, a2 2 , , a, , an n） 线性结构包括线性表、堆栈、队列、字符串

2、、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最典型、最常用的是线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一 的的第第2 2章线性表章线性表1. 1. 了解线性结构的特点了解线性结构的特点2. 2. 掌握顺序表的定义、查找、插入和删除掌握顺序表的定义、查找、插入和删除 3. 3. 掌握链表的定义、创建、查找、插入和删除掌握链表的定义、创建、查找、插入和删除 4. 4. 能够从时间和空间复杂度的角度比较两种存储结能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合构的不同特点及其

3、适用场合 教学目标教学目标2.1 2.1 线性表的定义和特点线性表的定义和特点2.2 2.2 案例引入案例引入2.3 2.3 线性表的类型定义线性表的类型定义2.4 2.4 线性表的顺序表示和实现线性表的顺序表示和实现2.5 2.5 线性表的链式表示和实现线性表的链式表示和实现2.6 2.6 顺序表和链表的比较顺序表和链表的比较2.7 2.7 线性表的应用线性表的应用2.8 2.8 案例分析与实现案例分析与实现教学内容教学内容（a1, a2, ai-1，ai, ai1 ，, an）线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0n=0时称为时称为数据元素数据元

4、素起点起点a ai i的直接前趋的直接前趋a ai i的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n n为元素总个为元素总个数，即表长数，即表长空表空表终点终点2.1 2.1 线性表的定义和特点线性表的定义和特点 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级141810205141810205于春梅于春梅女女 18 181414级计算机级计算机1 1班班141810260141810260何仕鹏何仕鹏男男 19 191414级计算机级计算机2 2班班141810284141810284王王 爽爽女女 19

5、191414级计算机级计算机3 3班班141810360141810360王亚武王亚武男男 18 181414级计算机级计算机4 4班班： ：数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母; 元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性2.2 2.2 案例引入案例引入Pn(x) = p0 + p1x + p2x2 + + pnxn线性表线性表P = (p0,p1,p2,pn)指数（下标i）01234系数pi105-432P(x) = 10 + 5x - 4x2 + 3x3 + 2x4数

6、组表示数组表示（每一项的指数（每一项的指数i隐含隐含在其系数在其系数pi的序号中）的序号中）Rn(x) = Pn(x) + Qm(x)线性表线性表R = (p0 + q0,p1 + q1,p2 + q2,pm + qm,pm+1,pn)稀疏多项式稀疏多项式S(x) = 1 + 3x10000 + 2x20000下标i0123下标i012系数ai7395系数bi822-9指数01817指数178多项式非零项非零项的数组表示 （a）A(x) = 7 + 3x + 9x8 + 5x17 （b）B(x) = 8x + 22x7 9x8 线性表线性表P =(p1, e1), (p2, e2),(pm,

7、em)l创建一个创建一个新数组新数组c cl分别从头遍历比较分别从头遍历比较a a和和b b的每一项的每一项指数相同指数相同，对应系数相加，若其和不为零，则在，对应系数相加，若其和不为零，则在c c中增加一个新项中增加一个新项指数不相同指数不相同，则将指数较小的项复制到，则将指数较小的项复制到c c中中l一个多项式已遍历一个多项式已遍历完毕完毕时，将另一个剩余项依次复制到时，将另一个剩余项依次复制到c c中即可中即可（1 1）查找）查找（2 2）插入）插入（3 3）删除）删除（4 4）修改）修改（5 5）排序）排序（6 6）计数）计数图书顺序表图书顺序表图书链表图书链表线性表的重要基本操作线性

8、表的重要基本操作1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 删除删除2.3 2.3 线性表的类型定义线性表的类型定义2.4 2.4 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻顺序存储方法：顺序存储方法：用用一组地址连续一组地址连续的存储单元依次存储的存储单元依次存储线性表的元素，可通过线性表的元素，可通过数组数组VnVn来实现。来实现。顺序存储定义：顺序存储定义：把逻辑上相邻的数据元素存储

9、在物理把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。上相邻的存储单元中的存储结构。元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储#define MAXSIZE 100 /#define MAXSIZE 100 /最大长度最大长度typedef struct typedef struct ElemType ElemType * *elem; /elem; /指向数据元素的基地址指向数据元素的基地址 int length; /i

10、nt length; /线性表的当前长度线性表的当前长度 SqListSqList；顺序表的类型定义顺序表的类型定义#define MAXSIZE 10000/图书表可能达到的最大长度图书表可能达到的最大长度 typedef struct/图书信息定义图书信息定义 char no20;/图书图书ISBN char name50;/图书名字图书名字 float price; /图书价格图书价格Book; typedef struct Book *elem;/存储空间的基地址存储空间的基地址 int length;/图书表中当前图书个数图书表中当前图书个数 SqList;/图书表的顺序存储结构类型

11、为图书表的顺序存储结构类型为SqList图书表的顺序存储结构类型定义图书表的顺序存储结构类型定义1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 删除删除线性表的重要基本操作线性表的重要基本操作重要基本操作的算法实现重要基本操作的算法实现初始化顺序表初始化顺序表 （参数用引用）（参数用引用）Status InitList_Sq(SqList &L) /构造一个空的顺序表构造一个空的顺序表L L.elem=new ElemTypeMAXSIZE; /为顺序表分配空间为顺序表分配空间 if(!L.elem) exit(OVERFLOW); /存

12、储分配失败存储分配失败 L.length=0; /空表长度为空表长度为0 return OK;1 1、初始化顺序表、初始化顺序表 （参数用指针）（参数用指针）Status InitList_Sq(SqList *L) /构造一个空的顺序表构造一个空的顺序表L L- elem=new ElemTypeMAXSIZE; /为顺序表分配空间为顺序表分配空间 if(! L- elem) exit(OVERFLOW); /存储分配失败存储分配失败 L- length=0; /空表长度为空表长度为0 return OK;销毁顺序表销毁顺序表void DestroyList(SqList &L)vo

13、id DestroyList(SqList &L) if (L.elem) deleteL.elem; / if (L.elem) deleteL.elem; /释放存储空间释放存储空间 清空顺序表清空顺序表void ClearList(SqList &L) L.length=0; /将线性表的长度置为将线性表的长度置为0求顺序表的长度求顺序表的长度int GetLength(SqList L) return (L.length); 判断顺序表是否为空判断顺序表是否为空int IsEmpty(SqList L) if (L.length=0) return 1; else re

14、turn 0;补充：几个简单基本操作的算法实现补充：几个简单基本操作的算法实现1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 删除删除线性表的重要基本操作线性表的重要基本操作int GetElem(SqList L,int int GetElem(SqList L,int i,ElemType &ei,ElemType &e) ) if (iL.length) return ERROR; if (iL.length) return ERROR; / /判断判断i i值是否合理，若不合理，返回值是否合理，若不合理，返回ERRORER

15、ROR e=L.elemi-1;e=L.elemi-1; / /第第i-1i-1的单元存储着第的单元存储着第i i个数据个数据 return OK;return OK; 2. 2. 取值取值（根据位置（根据位置i i获取相应位置数据元素的内容）获取相应位置数据元素的内容）随机存取获取顺序表中的某个数据元素的内容获取顺序表中的某个数据元素的内容3.3.查找查找（根据指定数据获取数据所在的位置）（根据指定数据获取数据所在的位置）25 34 57 16 48 09 0 1 2 3 4 5 data查找查找 16 i25 34 57 16 48 09 i25 34 57 16 48 09 i25 34

16、 57 16 48 09 i查找成功查找成功25 34 57 16 48 0 1 2 3 4data查找 50i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i查找失败查找失败3. 3. 查找查找（根据指定数据获取数据所在的位置）（根据指定数据获取数据所在的位置）查找算法时间效率分析查找算法时间效率分析在线性表在线性表L L中查找值为中查找值为e e的数据元素的数据元素int LocateELem(SqList L,ElemType e) for (i=0;i L.length;i+) if (L.elemi=e)

17、 return i+1; return 0;3. 3. 查找查找（根据指定数据获取数据所在的位置）（根据指定数据获取数据所在的位置）2512478936141234567892512479989361499插入插入251247893614251247893614251247893614插第插第 4 4 个结点之前，移动个结点之前，移动 6 64+14+1 次次插在第插在第 i i 个结点之前，移动个结点之前，移动 n-i+1n-i+1 次次4. 4. 插入插入（插在第（插在第 i i 个结点之前）个结点之前）（1 1）判断）判断插入位置插入位置i i 是否合法是否合法。（2 2）判断顺序表的）

18、判断顺序表的存储空间是否已满存储空间是否已满。 （3 3）将第）将第n n至第至第i i 位的元素依次位的元素依次向后移动一个位置向后移动一个位置，空，空出第出第i i个位置。个位置。（4 4）将要插入的新元素）将要插入的新元素e e放入第放入第i i个位置个位置。（5 5）表长加表长加1 1，插入成功返回，插入成功返回OKOK。【算法步骤算法步骤】4. 4. 在线性表在线性表L L中第中第i i个数据元素之前插入数据元素个数据元素之前插入数据元素e e Status ListInsert_Sq(SqList &L,int i ,ElemType e) if(iL.length+1)

19、return ERROR; /i值不合法值不合法 if(L.length=MAXSIZE) return ERROR; /当前存储空间已满当前存储空间已满 for(j=L.length-1;j=i-1;j-) L.elemj+1=L.elemj; /插入位置及之后的元素后移插入位置及之后的元素后移 L.elemi-1=e; /将新元素将新元素e放入第放入第i个位置个位置 +L.length; /表长增表长增1 return OK;【算法描述算法描述】221)(1)(1 0)1(11)(11=1nnnnnn1inn1niAMN若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根

20、本无需移动（特别快）；若插入在首结点之前，则表中元素全部后移（特别慢）；若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共若要考虑在各种位置插入（共n+1n+1种可能）的平均移动次种可能）的平均移动次数，该如何计算？数，该如何计算？算法时间主要耗费在移动元素的操作上算法时间主要耗费在移动元素的操作上【算法分析算法分析】251247893614123456789251247361425124736142512473614删除删除5. 5. 删除删除（删除第（删除第 i i 个结点）个结点）删除第删除第 4 4 个结点，移动个结点，移动 6 64 4 次次删除第删除第 i

21、 i 个结点，移动个结点，移动 n-in-i 次次（1 1）判断）判断删除位置删除位置i i 是否合法是否合法（合法值为（合法值为1in1in）。）。（2 2）将欲删除的元素保留在）将欲删除的元素保留在e e中。中。 （3 3）将第）将第i+1i+1至第至第n n 位的元素依次位的元素依次向前移动一个位置向前移动一个位置。（4 4）表长减表长减1 1，删除成功返回，删除成功返回OKOK。【算法步骤算法步骤】5. 5. 将线性表将线性表L L中第中第i i个数据元素删除个数据元素删除Status ListDelete_Sq(SqList &L,int i) if(iL.length) r

22、eturn ERROR; /i值不合法值不合法 for (j=i;jdata=ai, 则则p-next-data=ai+1 a1a2an.L2.5.2 2.5.2 单链表基本操作的实现单链表基本操作的实现1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 删除删除1.1.初始化初始化( (构造一个空表构造一个空表 )【算法步骤算法步骤】（1）生成新结点作头结点，用头指针）生成新结点作头结点，用头指针L指向头结点。指向头结点。（2）头结点的指针域置空。）头结点的指针域置空。L【算法描述算法描述】Status InitList_L(LinkList &a

23、mp;L) L=new LNode; L-next=NULL; return OK; 销毁销毁Status DestroyList_L(LinkList &L) LinkList p; while(L) p=L; L=L-next; delete p; return OK; 补充：几个简单基本操作的算法实现补充：几个简单基本操作的算法实现清空清空Status ClearList(LinkList & & L) / / 将将L L重置为空表重置为空表 LinkList p,q; p=L-next; /p/p指向第一个结点指向第一个结点 while(p) /没到表尾没到表尾

24、 q=p-next; delete p; p=q; L-next=NULL; /头结点指针域为空头结点指针域为空 return OK; 补充：几个简单基本操作的算法实现补充：几个简单基本操作的算法实现pLa1a2. pi01p2pn=NULLan求表长求表长p=L-next; i=0; while(p)i+;p=p-next; 补充：几个简单基本操作的算法实现补充：几个简单基本操作的算法实现“数数”结点：结点：指针指针p依次指向各个结点依次指向各个结点从第一个元素开始从第一个元素开始“数数” 一直一直“数数”到最后一个结点到最后一个结点求表长求表长int ListLength_L(LinkLi

25、st L)/返回返回L L中数据元素个数中数据元素个数 LinkList p; p=L-next; /p/p指向第一个结点指向第一个结点 i=0; while(p)/遍历单链表遍历单链表, ,统计结点数统计结点数 i+; p=p-next; return i; “数数”结点：结点：指针指针p依次指向各个结点依次指向各个结点从第一个元素开始从第一个元素开始“数数” 一直一直“数数”到最后一个结点到最后一个结点判断表是否为空判断表是否为空int ListEmpty(LinkList L) / / /若若L L为空表，则返回为空表，则返回1 1，否则返回，否则返回0 0 if(L-next) / /

26、 /非空非空 return 0; else return 1; 1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 删除删除线性表的重要基本操作线性表的重要基本操作 思考：顺序表里如何找到第思考：顺序表里如何找到第i i个元素？个元素？ 链表的查找：要从链表的头指针出发，链表的查找：要从链表的头指针出发，顺着链域顺着链域nextnext逐个结点往下搜索，直至逐个结点往下搜索，直至搜索到第搜索到第i i个结点为止。因此，链表不是个结点为止。因此，链表不是随机存取结构随机存取结构2. 2. 取值取值（根据位置（根据位置i i获取相应位置数据元素的内容）获

27、取相应位置数据元素的内容）64L211830754256pppj1 2 3pp1i=3i=156p7例：分别取出表中例：分别取出表中i=3和和i=15的元素的元素从第从第1 1个结点（个结点（L-nextL-next）顺链扫描，用指针）顺链扫描，用指针p p指向当指向当前扫描到的结点，前扫描到的结点，p p初值初值p p = = L-nextL-next。j j做计数器，累计当前扫描过的结点数，做计数器，累计当前扫描过的结点数，j j初值为初值为1 1。当当p p指向扫描到的下一结点时，计数器指向扫描到的下一结点时，计数器j j加加1 1。当当j j= = i i时，时，p p所指的结点就是要

28、找的第所指的结点就是要找的第i i个结点。个结点。【算法步骤算法步骤】/获取线性表获取线性表L L中的某个数据元素的内容中的某个数据元素的内容Status GetElem_L(LinkList L,int i,ElemType &e) p=L-next;j=1; /初始化初始化 while(p&jnext; +j; if(!p | ji)return ERROR; /第第i个元素不存在个元素不存在 e=p-data; /取第取第i个元素个元素 return OK; /GetElem_L 2. 2. 取值取值（根据位置（根据位置i i获取相应位置数据元素的内容）获取相应位置数据元

29、素的内容）从第一个结点起，依次和从第一个结点起，依次和e e相比较。相比较。如果找到一个其值与如果找到一个其值与e e相等的数据元素，则返回其相等的数据元素，则返回其在链表中的在链表中的“位置位置”或地址或地址；如果查遍整个链表都没有找到其值和如果查遍整个链表都没有找到其值和e e相等的元素相等的元素，则返回，则返回0 0或或“NULLNULL”。L211830753056pj1x=30p2p3找到，返回找到，返回i ix=51p1p6p7未找到，返回03.3.查找查找（根据指定数据获取数据所在的位置）（根据指定数据获取数据所在的位置）/在线性表在线性表L L中查找值为中查找值为e e的数据元

30、素的数据元素LNode *LocateELem_L (LinkList L，Elemtype e) /返回返回L中值为中值为e的数据元素的的数据元素的地址地址，查找失败返回，查找失败返回NULL p=L-next; while(p &p-data!=e) p=p-next; return p; 【算法描述算法描述】/在线性表在线性表L L中查找值为中查找值为e e的数据元素的数据元素int LocateELem_L (LinkList L，Elemtype e) /返回返回L中值为中值为e的数据元素的的数据元素的位置序号位置序号，查找失败返回，查找失败返回0 p=L-next; j=1

31、; while(p &p-data!=e) p=p-next; j+; if(p) return j; else return 0; 【算法描述算法描述】 将值为将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位个结点的位置上，即插入到置上，即插入到a ai-1i-1与与a ai i之间之间4. 4. 插入插入（插在第（插在第 i i 个结点之前）个结点之前）s-next=p-next; p-next=s思考：步骤思考：步骤1 1和和2 2能互换么？能互换么？ * 【算法步骤算法步骤】（1 1）找到）找到a ai-1i-1存储位置存储位置p p（2 2）生成一个新结点

32、）生成一个新结点* *s s（3 3）将新结点）将新结点* *s s的数据域置为的数据域置为x x（4 4）新结点）新结点* *s s的指针域指向结点的指针域指向结点a ai i（5 5）令结点）令结点* *p p的指针域指向新结点的指针域指向新结点* *s s/在在L L中第中第i i个元素之前插入数据元素个元素之前插入数据元素e e Status ListInsert_L(LinkList &L,int i,ElemType e) p=L;j=0; while(p&jnext;+j;/寻找第寻找第i1个结点个结点 if(!p|ji1)return ERROR;/i大于表长大

33、于表长 + 1或者小于或者小于1 s=new LNode;/生成新结点生成新结点s s-data=e; /将结点将结点s的数据域置为的数据域置为e s-next=p-next; /将结点将结点s插入插入L中中 p-next=s; return OK; /ListInsert_L 【算法描述算法描述】 将表的第将表的第i i个结点删去个结点删去 步骤：步骤：（1 1）找到）找到a ai-1i-1存储位置存储位置p p（2 2）保存要删除的结点的值）保存要删除的结点的值（3 3）令）令p-p-nextnext指向指向a ai i的直接后继结点的直接后继结点（4 4）释放结点）释放结点a ai i的

34、空间的空间5. 5. 删除删除（删除第（删除第 i i 个结点）个结点）5. 5. 删除删除（删除第（删除第 i i 个结点）个结点）5. 5. 删除删除（删除第（删除第 i i 个结点）个结点）p-next = p-next-next ?ai-1ai-1aiaiai+1ai+1pq删除前删除前删除后删除后【算法步骤算法步骤】（1 1）找到）找到a ai-1i-1存储位置存储位置p p（2 2）临时保存结点）临时保存结点a ai i的地址在的地址在q q中，以备释放中，以备释放（3 3）令）令p-nextp-next指向指向a ai i的直接后继结点的直接后继结点（4 4）将）将a ai i的

35、值保留在的值保留在e e中中（5 5）释放）释放a ai i的空间的空间北京林业大学信息学院/将线性表将线性表L L中第中第i i个数据元素删除个数据元素删除 Status ListDelete_L(LinkList &L,int i,ElemType &e) p=L;j=0; while(p-next &jnext; +j; if(!(p-next)|ji-1) return ERROR; /删除位置不合理删除位置不合理 q=p-next; /临时保存被删结点的地址以备释放临时保存被删结点的地址以备释放 p-next=q-next; /改变删除结点前驱结点的指针域改变

36、删除结点前驱结点的指针域 e=q-data; /保存删除结点的数据域保存删除结点的数据域 delete q; /释放删除结点的空间释放删除结点的空间 return OK; /ListDelete_L 【算法描述算法描述】1. 查找查找: 因线性链表只能顺序存取，即在查找时要因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为从头指针找起，查找的时间复杂度为 O(n)。2. 插入和删除插入和删除: 因线性链表不需要移动元素，只要因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为修改指针，一般情况下时间复杂度为 O(1)。 但是，如果要在单链表中进行前插或删除操作，但是

37、，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为由于要从头查找前驱结点，所耗时间复杂度为 O(n) 。链表的运算时间效率分析链表的运算时间效率分析n从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：u生成新结点生成新结点u将读入数据存放到新结点的数据域中将读入数据存放到新结点的数据域中u将该新结点插入到链表的前端将该新结点插入到链表的前端单链表的建立（前插法）单链表的建立（前插法） L L L L L e e a b L d c e d e b c d e c d LpLanan-1anLp单链表的建立（前插法）单链表的建立（前插法）void Creat

38、eList_F(LinkList &L,int n) L=new LNode; L-next=NULL; /先建立一个带头结点的单链表先建立一个带头结点的单链表 for(i=n;i0;-i) p=new LNode; /生成新结点生成新结点 cinp-data; /输入元素值输入元素值 p-next=L-next;L-next=p; /插入到表头插入到表头 /CreateList_F 【算法描述算法描述】n从一个空表从一个空表L开始，将新结点逐个插入到链表的尾部，尾指开始，将新结点逐个插入到链表的尾部，尾指针针r指向链表的尾结点。指向链表的尾结点。n初始时，初始时，r同同L均指向头结点

39、。每读入一个数据元素则申请一均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，个新结点，将新结点插入到尾结点后，r指向新结点。指向新结点。单链表的建立（尾插法）单链表的建立（尾插法） L L L L L L a r r a b r a c r b a e r b c d a d r b c void CreateList_L(LinkList &L,int n) /正位序输入正位序输入n个元素的值，建立带表头结点的单链表个元素的值，建立带表头结点的单链表L L=new LNode; L-next=NULL; r=L; /尾指针尾指针r指向头结点指向头结点 for

40、(i=0;ip-data; /输入元素值输入元素值 p-next=NULL; r-next=p; /插入到表尾插入到表尾 r=p; /r指向新的尾结点指向新的尾结点 /CreateList_L 【算法描述算法描述】优点优点数据元素的个数可以自由扩充数据元素的个数可以自由扩充 插入、删除等操作不必移动数据，只需插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高修改链接指针，修改效率较高链表的优缺点链表的优缺点缺点缺点存储密度小存储密度小存取效率不高，必须采用存取效率不高，必须采用顺序存取顺序存取，即存，即存取数据元素时，只能按链表的顺序进行访问取数据元素时，只能按链表的顺序进行访问（顺

41、藤摸瓜）（顺藤摸瓜）链表的优缺点链表的优缺点练习练习1.1.链表的每个结点中都恰好包含一个指针。链表的每个结点中都恰好包含一个指针。 2.2.顺序表结构适宜于进行顺序存取，而链表顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。适宜于进行随机存取。3.3.顺序存储方式的优点是存储密度大，且插顺序存储方式的优点是存储密度大，且插入、删除运算效率高。入、删除运算效率高。4.4.线性表若采用链式存储时，结点之间和结线性表若采用链式存储时，结点之间和结点内部的存储空间都是可以不连续的。点内部的存储空间都是可以不连续的。 5.5.线性表的每个结点只能是一个简单类型，线性表的每个结点只能是一个简单类

42、型，而链表的每个结点可以是一个复杂类型而链表的每个结点可以是一个复杂类型 2.5.3 2.5.3 循环链表循环链表L-next=L.H(a) (a) 非空单循环链表非空单循环链表LH(b) (b) 空表空表L说明说明从循环链表中的任何一个结点的位置都可从循环链表中的任何一个结点的位置都可以找到其他所有结点，而单链表做不到；以找到其他所有结点，而单链表做不到；循环条件：循环条件：p!=NULLp!=L p-next!=NULLp-next!=L循环链表中没有明显的尾端循环链表中没有明显的尾端 如何避免死循环如何避免死循环.H对循环链表，有时不给出头指针，而给出对循环链表，有时不给出头指针，而给出

43、尾指针尾指针可以更方便的找到可以更方便的找到第一个和最后一个第一个和最后一个结点结点reara1ai-1anai如何查找开始结点和终端结点？如何查找开始结点和终端结点？开始结点：开始结点：rear-next-next终端结点：终端结点：rear说明说明TaTaa a1 1a an nTbTbb b1 1b bn n循环链表的合并循环链表的合并a a1 1a an nb b1 1b bn npTaTaTbTb示例示例a a1 1a an nb b1 1b bn npTaTaTbTbLinkList Connect(LinkList Ta,LinkList Tb)/假设假设Ta、Tb都是非空的单循

44、环链表都是非空的单循环链表 /p p存表头结点存表头结点 /TbTb表头连结表头连结TaTa表尾表尾 /释放释放TbTb表头结点表头结点 /修改指针修改指针 return Tb;p=Ta-next;Ta-next=Tb-next-next;deleteTb-next; Tb-next=p; 示例示例priordatanextdatanexttypedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinkList2.5.4 2.5.4 双向链表双向链表L(a) (

45、a) 空双向循环链表空双向循环链表LABC(b) (b) 双向循环链表双向循环链表d-next-prior = d-prior-next = dL-next=Lab.pxs双向链表的插入双向链表的插入1. s-prior=p-prior;双向链表的插入双向链表的插入a ab bx x.1 1p ps s双向链表的插入双向链表的插入1. s-prior=p-prior;2. p-prior-next=s;abx.12ps双向链表的插入双向链表的插入abx.123ps1. s-prior=p-prior;2. p-prior-next=s;3. s-next=p;双向链表的插入双向链表的插入4.

46、p-prior=s;abx.1234ps1. s-prior=p-prior;2. p-prior-next=s;3. s-next=p;Status ListInsert_DuL(DuLinkList &L,int i,ElemType e) if(!(p=GetElemP_DuL(L,i) return ERROR; s=new DuLNode; s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return OK;双向链表的插入双向链表的插入ab.pc双向链表的删除双向链表的删除ab.1pc1. p-p

47、rior-next=p-next;双向链表的删除双向链表的删除双向链表的删除双向链表的删除ab.12pc1. p-prior-next=p-next;2. p-next-prior=p-prior;Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e) if(!(p=GetElemP_DuL(L,i) return ERROR; e=p-data; p-prior-next=p-next; p-next-prior=p-prior; delete p; return OK;双向链表的删除双向链表的删除北京林业大学信息学院2.

48、6 2.6 顺序表和链表的比较顺序表和链表的比较存储结构比较项目顺序表链表空间存储空间预先分配，会导致空间闲置或溢出现象动态分配，不会出现存储空间闲置或溢出现象存储密度不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1需要借助指针来体现元素间的逻辑关系，存储密度小于1时间存取元素随机存取，按位置访问元素的时间复杂度为O(1)顺序存取，按位置访问元素时间复杂度为O(n)插入、删除平均移动约表中一半元素，时间复杂度为O(n)不需移动元素，确定插入、删除位置后，时间复杂度为O(1)适用情况 表长变化不大，且能事先确定变化的范围 很少进行插入或删除操作，经常按元素位置序号访问数据元素 长度

49、变化较大 频繁进行插入或删除操作2.7 2.7 线性表的应用线性表的应用2.7.1 2.7.1 线性表的合并线性表的合并问题描述：问题描述： 假设利用两个线性表假设利用两个线性表LaLa和和LbLb分别表示两分别表示两个集合个集合A A和和B,B,现要求一个新的集合现要求一个新的集合 A=ABLa=(7, 5, 3, 11)Lb=(2, 6, 3)La=(7, 5, 3, 11, 2, 6) .依次取出依次取出Lb Lb 中的每个元素，执行以下操作：中的每个元素，执行以下操作：在在LaLa中查找该元素中查找该元素如果找不到，则将其插入如果找不到，则将其插入La的最后的最后【算法步骤算法步骤】v

50、oid union(List &La, List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); for(i=1;i=Lb_len;i+) GetElem(Lb,i,e); if(!LocateElem(La,e) ListInsert(&La,+La_len,e); )()(LBListLengthLAListLengthO【算法描述算法描述】问题描述：问题描述： 已知线性表已知线性表La La 和和LbLb中的数据元素按值中的数据元素按值非递减非递减有有序排列序排列, ,现要求将现要求将LaLa和和LbLb归并为一个新的线

51、性表归并为一个新的线性表LcLc, ,且且LcLc中的数据元素仍按值非递减有序排列中的数据元素仍按值非递减有序排列. .La=(1 ,7, 8)Lb=(2, 4, 6, 8, 10, 11)Lc=(1, 2, 4, 6, 7 , 8, 8, 10, 11) 2.7.2 2.7.2 有序表的合并有序表的合并(1) (1) 创建一个空表创建一个空表LcLc(2) 依次从依次从 La La 或或 Lb Lb 中中“摘取摘取”元素值较小元素值较小的结点插入到的结点插入到 Lc Lc 表的最后，直至其中一个表表的最后，直至其中一个表变空为止变空为止(3) (3) 继续将继续将 La La 或或 Lb L

52、b 其中一个表的剩余结点其中一个表的剩余结点插入在插入在 Lc Lc 表的最后表的最后【算法步骤算法步骤】有序的顺序表合并有序的顺序表合并void MergeList_Sq(SqList LA,SqList LB,SqList &LC) pa=LA.elem; pb=LB.elem; /指针指针pa和和pb的初值分别指向两个表的第一个元素的初值分别指向两个表的第一个元素 LC.length=LA.length+LB.length; /新表长度为待合并两表的长度之和新表长度为待合并两表的长度之和 LC.elem=new ElemTypeLC.length; /为合并后的新表分配一个数组空

53、间为合并后的新表分配一个数组空间 pc=LC.elem; /指针指针pc指向新表的第一个元素指向新表的第一个元素 pa_last=LA.elem+LA.length-1; /指针指针pa_last指向指向LA表的最后一个元素表的最后一个元素 pb_last=LB.elem+LB.length-1; /指针指针pb_last指向指向LB表的最后一个元素表的最后一个元素 while(pa=pa_last & pb=pb_last) /两个表都非空两个表都非空 if(*pa=*pb) *pc+=*pa+; /依次依次“摘取摘取”两表中值较小的结点两表中值较小的结点 else *pc+=*pb

54、+; while(pa=pa_last) *pc+=*pa+; /LB表已到达表尾表已到达表尾 while(pbdata data )pc-next = pa;PaLa(Lcbpb有序链表合并有序链表合并( pa-data data )pc-next = pa;pc= pa;1PcLa(Lcbpb有序链表合并有序链表合并( pa-data data )pc-next = pa;pc= pa;1Pcpa = pa-next;PaLa(Lcbpb有序链表合并有序链表合并( pa-data pb-data )pc-next

55、 = pb;1PcpaLa(Lcbpb有序链表合并有序链表合并( pa-data pb-data )pc-next = pb;1paPcpc= pb;2La(Lcb有序链表合并有序链表合并( pa-data pb-data )pc-next = pb;1paPcpc= pb;2pb =pb-next;pbLa(Lc)12467881011有序链表合并有序链表合并pc- next=pa?pa:pb; pa(NULL)pbpcLa(Lc)12467881011合并后合并后delete Lb;有序链表合并有序链表合并void MergeList_L

56、(LinkList &La,LinkList &Lb,LinkList &Lc) pa=La-next; pb=Lb-next; pc=Lc=La; /用用La的头结点作为的头结点作为Lc的头结点的头结点 while(pa & pb) if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next; elsepc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb; /插入剩余段插入剩余段 delete Lb; /释放释放Lb的头结点的头结点 T(n)=S(n)= O(1)()(LBListLengt

57、hLAListLengthO【算法描述算法描述】有序的链表合并有序的链表合并思考思考1：要求合并后的表无重复数据，如何实现？：要求合并后的表无重复数据，如何实现？提示：要单独考虑提示：要单独考虑pa-data = =pb-data La(Lc)12467881011要求结果链表仍使用原来两个链表的存储空要求结果链表仍使用原来两个链表的存储空间间, , 不另外占用其它的存储空间。不另外占用其它的存储空间。表中允许有重复的数据。表中允许有重复的数据。 思考思考2：将两个非递减的有序链表合并为一个非递：将两个非递减的有序链表合并为一个非递增的有序链表，如何实现？增的有序链表，如何实现？(1)Lc(1

58、)Lc指向指向LaLa(2) 依次从依次从 La La 或或 Lb Lb 中中“摘取摘取”元素值较小元素值较小的结点插入到的结点插入到 Lc Lc 表的表的表头结点之后表头结点之后，直至其，直至其中一个表变空为止中一个表变空为止(3) (3) 继续将继续将 La La 或或 Lb Lb 其中一个表的剩余结点其中一个表的剩余结点插入在插入在 Lc Lc 表的表的表头结点之后表头结点之后(4) (4) 释放释放 Lb Lb 表的表头结点表的表头结点【算法步骤算法步骤】2.8 2.8 案例分析与实现案例分析与实现指数（下标i）01234系数pi105-432P(x) = 10 + 5x - 4x2

59、+ 3x3 + 2x4数组表示数组表示（每一项的指数（每一项的指数i隐含隐含在其系数在其系数pi的序号中）的序号中）Rn(x) = Pn(x) + Qm(x)线性表线性表R = (p0 + q0,p1 + q1,p2 + q2,pm + qm,pm+1,pn)北京林业大学信息学院下标i0123下标i012系数ai7395系数bi822-9指数01817指数178多项式非零项非零项的数组表示 （a）A(x) = 7 + 3x + 9x8 + 5x17 （b）B(x) = 8x + 22x7 9x8 线性表线性表P =(p1, e1), (p2, e2),(pm, em)l创建一个创建一个新数组新

60、数组c cl分别从头遍历比较分别从头遍历比较a a和和b b的每一项的每一项指数相同指数相同，对应系数相加，若其和不为零，则在，对应系数相加，若其和不为零，则在c c中增加一个新项中增加一个新项指数不相同指数不相同，则将指数较小的项复制到，则将指数较小的项复制到c c中中l一个多项式已遍历一个多项式已遍历完毕完毕时，将另一个剩余项依次复制到时，将另一个剩余项依次复制到c c中即可中即可A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABl顺序存储结构存在问题顺序存储结构存在问题存储空间分配不灵活存储空间分配不灵活运算的空间复杂度高运算的空间复杂度高链式存储结构链式存储结构typedef struct PNode float coef;/系数系数 int expn;/指数指数 struct PNode *next;/指针域指针域PNode,*Polynomial; 创建一个只有头结点