《第2章线性表07》由会员分享，可在线阅读，更多相关《第2章线性表07（56页珍藏版）》请在金锄头文库上搜索。
1、孙克雷制作第第2 2章章 线线 性性 表表学习要点学习要点q 了解线性表的逻辑结构。了解线性表的逻辑结构。q 熟练掌握线性表的两种存储结构：顺序存储结熟练掌握线性表的两种存储结构：顺序存储结构和链式存储结构。构和链式存储结构。q 熟练掌握线性表的基本算法：查找、插入、删熟练掌握线性表的基本算法：查找、插入、删除等。除等。孙克雷制作线性表是一种最简单的线性结构线性表是一种最简单的线性结构线性结构线性结构的基本特征为的基本特征为:1存在唯一的一个存在唯一的一个“第一元素第一元素”；2存在唯一的一个存在唯一的一个 “最后元素最后元素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后继；唯一的
2、后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱。唯一的前驱。在数据元素的在数据元素的非空有限集中非空有限集中& 简简 介介孙克雷制作2.1 线性表的基本概念线性表的基本概念2.3 线性表的链式表示及其运算线性表的链式表示及其运算2.4 各种线性表的比较各种线性表的比较2.2 线性表的顺序表示及其运算线性表的顺序表示及其运算第二章第二章 线性表线性表孙克雷制作v 什么是线性表？什么是线性表？ 线性表就是具有相同特性的数据元素的有限集合，线性表就是具有相同特性的数据元素的有限集合，其元素可以是数值、符号或是由包含许多不同的数其元素可以是数值、符号或是由包含许多不同的数据项组成的复杂信
3、息。线性表中数据元素的类型可据项组成的复杂信息。线性表中数据元素的类型可以根据需要进行具体定义，但在同一个线性表中每以根据需要进行具体定义，但在同一个线性表中每个元素都应具有相同的数据类型。个元素都应具有相同的数据类型。2.1 线性表的基本概念线性表的基本概念孙克雷制作例例1. 261. 26个英文字母组成的字母表个英文字母组成的字母表 （A A，B B，C C，Z Z）例例2 2. .扑克牌的点数扑克牌的点数（2,3,4,5,6,7,8,9,10,J,Q,K,A2,3,4,5,6,7,8,9,10,J,Q,K,A）可以构成一个线）可以构成一个线性表，其中每一张牌的点数是一个数据元素。性表，其
4、中每一张牌的点数是一个数据元素。 在较为复杂的线性表中，一个数据元素可以由在较为复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素若干个数据项组成。在这种情况下，常把数据元素称为记录（称为记录（recordrecord），或称结点，由大量记录构成），或称结点，由大量记录构成的线性表又称为文件（的线性表又称为文件（filefile）。）。2.1.1 线性表的定义和特性线性表的定义和特性孙克雷制作设设 A=（a1, a2, . , ai -1, ai , ai+1, , an ）是一线性表是一线性表1.同一线性表的数据元素必须是同一类型。同一线性表的数据元素必须是同一类
5、型。2.在表中在表中ai-1 是是ai 的直接前趋，的直接前趋，ai+1 是是ai 的直接后继。的直接后继。3.除第一个元素和最后一个元素之外，其他元素都有且仅除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。有一个直接前趋，有且仅有一个直接后继。4.线性表中元素的个数线性表中元素的个数n称为线性表的长度，称为线性表的长度，n=0时称为时称为空表。空表。5.ai 是是线性表的第线性表的第i个元素，称个元素，称i 为数据元素为数据元素ai 的序号。的序号。& 线性表的特征线性表的特征孙克雷制作nInitList(L)操作结果：操作结果：构造一个空的线性表构造一
6、个空的线性表L。nListEmpty(L)初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：若若L为空表，则返回为空表，则返回TRUE，否则，否则返回返回FALSE。nListLength(L)初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：返回返回L中数据元素的个数。中数据元素的个数。2.1.1 线性表的抽象数据类型线性表的抽象数据类型孙克雷制作& 线性表的基本操作线性表的基本操作nListInsert(L,i,e)初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：在在L中第中第i个位置之前插入新的数个位置之前插入新的数据元素据元
7、素e，L的长度加的长度加1。nListDelete(L,i,e)初始条件：初始条件：线性表线性表L已存在且非空。已存在且非空。操作结果：操作结果：删除删除L的第的第i个元素，个元素，L的长度减的长度减1。nGetElem(L,i,e)初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：用用e返回返回L中第中第i个数据元素的值。个数据元素的值。孙克雷制作& 线性表的基本操作举例线性表的基本操作举例n已知线性表已知线性表L中的元素按元素值非递减有序排列，编中的元素按元素值非递减有序排列，编写一个函数删除线性表中多余的值相同的元素。写一个函数删除线性表中多余的值相同的元素。 voi
8、d DeleteSame(List &L) i=0; Len=ListLength(L); while(ilen) GetElem(L,i,a1); GetElem(L,i+1,a2); if(a1!=a2)i+; else ListDelete(L,i,b); Len-; 孙克雷制作存储线性表，至少要保存两类信息：存储线性表，至少要保存两类信息：1）线性表中的数据元素；）线性表中的数据元素；2）线性表中数据元素的顺序关系；）线性表中数据元素的顺序关系；如何在计算机中存储线性表？如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？如何在计算机中实现线性表的基本操作？孙克雷制作2.2
9、线性表的顺序线性表的顺序存储结构及其操作存储结构及其操作 在内存中用一组地址连续的存储单元依次存储线性表中在内存中用一组地址连续的存储单元依次存储线性表中的各个数据元素。这种存储结构是顺序存储，又称为的各个数据元素。这种存储结构是顺序存储，又称为顺序表顺序表。 假设线性表的每个元素需占用假设线性表的每个元素需占用L个存储单元，并以所占个存储单元，并以所占的第一个单元的存储地址作为数据元素的起始存储位置，则的第一个单元的存储地址作为数据元素的起始存储位置，则线性表中第线性表中第i+1个数据元素的存储位置个数据元素的存储位置Loc(ai+1)和第和第i个数据个数据元素的存储位置元素的存储位置Loc
10、(ai)之间满足下列关系：之间满足下列关系： Loc(ai+1) = Loc(ai) + L 线性表的第线性表的第i个元素个元素ai的存储位置为：的存储位置为： Loc(ai) = Loc(a1) + (i-1)*L Loc(a1)是线性表的第一个数据元素是线性表的第一个数据元素a1的存储位置。的存储位置。孙克雷制作v 用用“物理位置物理位置”相邻来表示线相邻来表示线性表中数据元素之间的逻辑关系。性表中数据元素之间的逻辑关系。v 根据线性表的顺序存储结构的根据线性表的顺序存储结构的特点，只要确定了存储线性表的起特点，只要确定了存储线性表的起始位置，线性表中任一数据元素都始位置，线性表中任一数据
11、元素都可随机存取，所以，线性表的顺序可随机存取，所以，线性表的顺序存储结构是一种存储结构是一种随机存取随机存取的存储结的存储结构。构。a1a2ai-1aiai+1an线性表线性表(a1,a2, a3, . an)的顺序存储结构的顺序存储结构2.2.1 顺序表的定义和特点顺序表的定义和特点 孙克雷制作 由于由于C语言中的一维数组也是采用顺序存储表示，故可语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长表的元素之外，顺序表还应该用一个变量来表示线性表
12、的长度属性，所以我们用结构类型来定义顺序表类型。度属性，所以我们用结构类型来定义顺序表类型。 #define LIST_SIZE100 线性表的存储空间线性表的存储空间typedef struct ElemType *elem; 存储空间基址存储空间基址 int length; 当前线性表长度当前线性表长度 SqList;& 顺序表的定义和特点顺序表的定义和特点 孙克雷制作v 初始化操作初始化操作 InitList_Sq( SqList &L) 功能：建立空的顺序表功能：建立空的顺序表L。01i-2i-1in-199L.elemL.lengthL.listsize100 02.2.2 顺序表的
13、基本操作顺序表的基本操作 孙克雷制作v 初始化操作算法初始化操作算法 Status InitList_Sq(SqList &L) /构造一个空的顺序表构造一个空的顺序表L L.elem=(ElemType*)malloc (LIST_INIT_SIZE*sizeof(ElemType); if (! L.elem) exit(OVERFLOW); /存储分配失败存储分配失败 L. length=0; /空表长度为空表长度为0 L.listsize=LIST_INIT_SIZE; /初始存储容量初始存储容量 Return OK; /InitList_Sq& 顺序表的基本操作顺序表的基本操作孙克雷
14、制作v 插入操作插入操作 ListInsert_Sq ( &L, i, e ) 功能：在顺序表功能：在顺序表L的第的第i个元素之前插入一个新元素个元素之前插入一个新元素e。 a1 a2 ai-1 ai ai+1 an01i-2i-1in-199L.elemL.lengthL.listsizen100 a1 a2 ai-1 e ai an01i-2i-1in99L.elemL.lengthL.listsizen+1100插入前插入前插入后插入后& 顺序表的基本操作顺序表的基本操作孙克雷制作插入操作基本步骤：插入操作基本步骤：（1）若）若i不合法或表不合法或表L已满，算法结束并返回已满，算法结束并
15、返回ERROR；否则转到（否则转到（2）；）；（2）将第）将第i个元素及之后的所有元素均后移一个位置；个元素及之后的所有元素均后移一个位置；（3）将新元素写入空出的位置；）将新元素写入空出的位置；（4）表长）表长+1。& 顺序表的基本操作顺序表的基本操作孙克雷制作v插入操作算法插入操作算法Status ListInsert_Sq(SqList &L, int i , ElemType e) if (iL.length+1) return ERROR; / i值不合法值不合法 if (L.length=L.listsize) return ERROR; /顺序表已顺序表已满满 for ( j=L
16、.length-1 ; j= i-1 ; - -j) L.elemj+1= L.elem j; /插入位置及之后的元素后移一个位置插入位置及之后的元素后移一个位置 L.elemi-1 =e; /插入插入e +L.length; /表长增表长增1 return OK; /ListInsert_Sq& 顺序表的基本操作顺序表的基本操作孙克雷制作v 删除操作删除操作 ListDelete_Sq ( SqList &L, int i, ElemType &e ) 功能：删除顺序表功能：删除顺序表L的第的第i个元素，并用个元素，并用e返回。返回。 a1 a2 ai-1 ai ai+1 an01i-2i-
17、1in-199L.elemL.lengthL.listsizen100 a1 a2 ai-1 ai+1 ai+2 an01i-2i-1in-299L.elemL.lengthL.listsizen+1100删除前删除前删除后删除后& 顺序表的基本操作顺序表的基本操作孙克雷制作删除算法的主要步骤：删除算法的主要步骤：（1）若）若i不合法或表不合法或表L空，算法结束，并返回空，算法结束，并返回ERROR；否则转到（否则转到（2）；）；（2）将第）将第i个元素赋值给个元素赋值给e；（3）将第将第i个元素之后的元素（不包括第个元素之后的元素（不包括第i个元素）依次个元素）依次向前移动一个位置；向前移动
18、一个位置；（4）表长）表长 1。& 顺序表的基本操作顺序表的基本操作孙克雷制作v删除操作算法删除操作算法Status ListDelete_Sq(SqList &L, int i, ElemType &e) if(iL.length) return ERROR; / i值不合法或表值不合法或表空空 p=&(L.elemi-1); /p为被删除元素的位置为被删除元素的位置 e=*p; /被删除元素的值赋给被删除元素的值赋给e q=&(L.elemL.length-1); /表尾元素的位置表尾元素的位置 for (+ +p; pnext指向第指向第i+1个结点个结点ai+1。即：即：p-data=
19、ai，p-next-data=ai+1； 在单链表中，取得第在单链表中，取得第 i 个结点必须从头指针出发寻找，是个结点必须从头指针出发寻找，是非随机存取结构。非随机存取结构。ai-1aiai+1p& 线性链表的描述线性链表的描述孙克雷制作如何在线性链表上实现线性表如何在线性链表上实现线性表的基本操作？的基本操作？如何建空表？如何插入？删除？如何建空表？如何插入？删除？2.3.2 单链表的操作单链表的操作孙克雷制作& 初始化操作初始化操作v 初始化操作初始化操作 InitList_L (LinkList &L) 功能：建空线性链表功能：建空线性链表LStatus InitList_L (Lin
20、kList &L) L = (LinkList)malloc(sizeof(LNode); if (!L) exit(OVERFLOW); L-next = NULL; Return OK; / InitList_L LL = (Lnode *)malloc(sizeof(LNode);孙克雷制作& 建立链表（头插法建表）建立链表（头插法建表）在链表表头插入新结点，结点次序与输入次序相反。在链表表头插入新结点，结点次序与输入次序相反。void CreateList_L(LinkList &L, int n) LinkList p;L=(LinkList)malloc(sizeof(LNode)
21、;L-next = NULL;for (int i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode);scanf(%d,&p-data);p-next = L-next; L-next=p; 孙克雷制作&头插法建表示意图头插法建表示意图LpLLpLp孙克雷制作& 建立链表（尾插法建表）建立链表（尾插法建表） 将新结点插到链表尾部，须增设一个尾指针将新结点插到链表尾部，须增设一个尾指针last，使其始使其始终指向当前链表的尾结点，结点次序与输入次序相同。终指向当前链表的尾结点，结点次序与输入次序相同。void CreateList_L(LinkList &L,
22、int n) LinkList p，last; L=(LinkList)malloc(sizeof(LNode); last = L; for (i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode);scanf(%d,&p-data);last-next = p; last=p; last-next=NULL; 孙克雷制作LlastLplastLlastp& 尾插法建表示意图尾插法建表示意图孙克雷制作& 插入操作插入操作v插入操作插入操作 ListInsert_L(LinkList &L, int i, ElemType e) 功能：在线性链表功能：在线性链表
23、L的第的第i个结点之前插入一个新结点。个结点之前插入一个新结点。 步骤：步骤：1.查找链表查找链表L的第的第i-1个结点；个结点；2.建立新结点；建立新结点；3.修改第修改第i-1个结点的指针和新结点指针完成插入。个结点的指针和新结点指针完成插入。ai-1aiai-1eai插入前插入前插入后插入后孙克雷制作& 插入操作插入操作插入过程的描述：插入过程的描述： 在线性表两个数据元素在线性表两个数据元素a和和b间插入间插入e，已知已知p指向指向a。pabes s-next=p-next; p-next=s; s=(LinkList)malloc(sizeof(LNode); s-data=e;孙克
24、雷制作& 插入操作插入操作Status ListInsert_L(LinkList &L, int i, ElemType e) p=L; j=0 while ( p & jnext; +j; /寻找第寻找第i-1个结点个结点 if( !p | ji-1 ) return ERROR; / i大于表长或者小于大于表长或者小于1 s=(LinkList)malloc(sizeof(LNode); /分配新结点分配新结点 s-data=e; s-next=p-next; p-next=s; /插入新结插入新结点点 return OK; /LinstInsert_L孙克雷制作& 删除操作删除操作v
25、删除操作删除操作 ListDelete_L(LinkList &L, int i, ElemType &e) 功能：删除线性链表功能：删除线性链表L中的第中的第i个结点，并且用个结点，并且用e返回其值返回其值 步骤：步骤：1. 查找链表的第查找链表的第i-1个结点个结点2. 修改第修改第i-1个结点的指针，摘除第个结点的指针，摘除第i个结点个结点3. 将第将第i个结点的数据元素值赋给个结点的数据元素值赋给e4. 回收被删除结点的空间回收被删除结点的空间ai-1ai删除前删除前删除后删除后ai+1ai-1aiai+1孙克雷制作删除过程的描述：删除过程的描述： 在单链表中删除在单链表中删除b，设设
26、p指向指向a。 p-next=q-nextpabcq q=p-next free(q)& 删除操作删除操作孙克雷制作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; / i不合法不合法 q=p-next; p-next=q-next; /摘除结点摘除结点 e =q-data; free(q); /释放结点空间释放结点空间 return OK; /LinstDelete_L& 删除操作删除操作
27、孙克雷制作2.3.3 循环链表循环链表v 循环链表的概念循环链表的概念 循环链表是线性表的另一种链式存储结构，它的特点是循环链表是线性表的另一种链式存储结构，它的特点是表中最后一个结点的指针指向头结点，整个链表形成一个环。表中最后一个结点的指针指向头结点，整个链表形成一个环。从表中任一结点出发均可找到表中其它结点。从表中任一结点出发均可找到表中其它结点。v 循环链表图示循环链表图示a1Ha2anH非空表非空表空空 表表孙克雷制作v 说明说明 循环链表与线性链表操作的主要差别是算法中循环结束循环链表与线性链表操作的主要差别是算法中循环结束的条件；单链表的结束条件是的条件；单链表的结束条件是p-n
28、ext=NULL，而循环链表的而循环链表的结束条件是结束条件是p-next=H。 对循环链表，有时不给出头指针，而是给出尾指针，此对循环链表，有时不给出头指针，而是给出尾指针，此时在解决某些实际问题时循环链表可能要比线性链表方便些。时在解决某些实际问题时循环链表可能要比线性链表方便些。如：查找开始结点如：查找开始结点a1和终端结点和终端结点an都很方便，它们的存储位都很方便，它们的存储位置分别是置分别是p-next-next和和p。a1Ha2anp p& 循环链表循环链表孙克雷制作BABAp=B-next； B-next=A-next；A-next=p-next； A=B；例：将一个链表链在另
29、一个链表的后面。例：将一个链表链在另一个链表的后面。& 循环链表循环链表孙克雷制作 双向链表中，每个结点有两个指针域，一个指向直接后双向链表中，每个结点有两个指针域，一个指向直接后继结点，另一个指向直接前趋结点。继结点，另一个指向直接前趋结点。数据域数据域指针域指针域指针域指针域存储数据存储数据元素元素存储前趋结存储前趋结点的地址点的地址存储后继结存储后继结点的地址点的地址2.3.4 双向链表双向链表孙克雷制作L L 非空非空的双向循环链表的双向循环链表 空的双向链表和空的双向循环链表空的双向链表和空的双向循环链表L LabL Labc& 双向链表图示双向链表图示孙克雷制作ptypedef s
30、truct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode , *DuLinkList;v 设设p为为DuLinkList型变量，则结点的指针：型变量，则结点的指针： p-next-prior = p-prior-next = pabc& 双向链表的类型定义双向链表的类型定义孙克雷制作插入结点时指针的变化情况插入结点时指针的变化情况p删除结点时指针变化情况删除结点时指针变化情况aiai+1ai-1 s-prior = p-prior p-prior-next = s s-next = p p
31、-prior = s p-prior-next = p-next p-next-prior = p-priorai-1pxais& 双向链表的基本操作算法双向链表的基本操作算法孙克雷制作ai-1peaisStatus ListInsert_DuL(DuLinkList &L, int i, ElemType e)p=GetElemP_DuL(L,i) /在在L中确定第中确定第i个元素的位置个元素的位置pif (!p) return ERROR; /p=NULL，即第即第i个元素不存在个元素不存在if ( !(s=(DuLinkList)malloc(sizeof(DuLNode) ) retu
32、rn ERROR;s-data=e; s-prior=p-prior; p-prior-next=s; /完成插入完成插入图示中的图示中的 s-next=p; p-prior=s; /完成插入完成插入图示中的图示中的return OK; /LinstInsert_DuL& 插入操作算法插入操作算法孙克雷制作Status ListDelete_DuL(DuLinkList &L, int i, ElemType&e)if( !(p=GetElemP_DuL(L,i) ) /在在L中确定第中确定第i个元素的位置指针个元素的位置指针preturn ERROR; /p=NULL，第，第i个元素不存在个
33、元素不存在e = p-data;p-prior-next=p-next; /完成删除完成删除图示中的图示中的 p-next-prior=p-prior; /完成删除完成删除图示中的图示中的 free(p); return OK; /LinstDelete_DuL& 删除操作算法删除操作算法aiai+1ai-1孙克雷制作在数学上，一个一元多项式在数学上，一个一元多项式Pn（x） 可以表示为可以表示为 ： Pn（x）=p0+p1x+p2x2+pnxn 分析：分析：v n阶多项式阶多项式Pn(x)有有n+1项。项。u 系数系数 p0， p1，p2， pnu 指数指数 0，1，2， n。按升幂排列按升
34、幂排列v 在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示 uP=（p0，p1， ，pn） 2.5 实例解析实例解析孙克雷制作& 一元多项式的表示及相加一元多项式的表示及相加v多项式的几种存储结构多项式的几种存储结构1.全部系数顺序存储结构：全部系数顺序存储结构：2. 将多项式的所有幂的系数将多项式的所有幂的系数pi（i=0,1,n）依次存放在数组依次存放在数组中。对幂很高，而系数为零的项也很多时，存储空间浪费很大。中。对幂很高，而系数为零的项也很多时，存储空间浪费很大。 如：如： P6（x）=3+4x-5x2+8x4 +2x5 -7x6 可以表示成：（可以表示成：（3，4
35、，-5，0，8，2，-7）2. 非零系数单链表存储结构：非零系数单链表存储结构： 适合于多项式的次数很高且适合于多项式的次数很高且“0”系数项很多的情况。用单链表系数项很多的情况。用单链表表示一元多项式时，每个结点有三个域：系数域、指数域、指针域。表示一元多项式时，每个结点有三个域：系数域、指数域、指针域。 如：如：P20000（x）= 3 - 5x50 + 14x20000 可以表示成可以表示成 : (3,0)，(-5,50)，(14,20000)孙克雷制作A(x) = 7+3x+9x8+5x17B(x) = 8x+22x7-9x8C(x) = A(x)+B(x)=7+11x+22x7+5x
36、17A& 应用举例：实现两个多项式相加应用举例：实现两个多项式相加7031985 17 -1B8122 7-9 8 -1C7011 122 75 17 -1孙克雷制作 假设指针假设指针qa和和qb分别指向多项式分别指向多项式A (x)和多项式和多项式B(x)中当前进行中当前进行比较的某个结点，则比较两个结点的数据域的指数项，有三种情况：比较的某个结点，则比较两个结点的数据域的指数项，有三种情况：1. 指针指针qa所指结点的指数值指针所指结点的指数值指针qb所指结点的指数值时，则保所指结点的指数值时，则保留留qb指针所指向的结点，指针所指向的结点，qa指针后移；指针后移；2. 指针指针qa所指结点的指数值指针所指结点的指数值指针qb所指结点的指数值时，则将所指结点的指数值时，则将qb指针所指向的结点插入到指针所指向的结点插入到qa所指结点前，所指结点前，qb指针后移；指针后移；3. 指针指针qa所指结点的指数值指针所指结点的指数值指针qb所指结点的指数值时，将两所指结点的指数值时，将两个结点中的系数相加，若和不为零，则修改个结点中的系数相加，若和不为零，则修改qa所指结点的系数值，所指结点的系数值，同时释放同时释放qb所指结点；反之，从多项式的链表中删除相应结点，并所指结点；反之，从多项式的链表中删除相应结点，并释放指针释放指针qa和和qb所指结点。所指结点。& 运算规则运算规则
