第3章 线性表

1、第三章 线性表本章主要内容3.1 线性表的定义和基本操作n线性表的定义n线性表是由n（n0）个类型相同的数据元素组成的有限序列。nL=( a1, a2,.,ai-1,ai,ai+1,.,an)；其中：L为表名，习惯用大写书写；ai为该线性表的数据元素，习惯用小写书写；n线性表中数据元素的个数被称为线性表的长度，当n=0时，称为空线性表。 线性表特点n特点n除第一个和最后一个元素外，其他元素都存在唯一的前驱、后继关系n举例 n La=（34，89，765，12，90，-34，22） 数据元素类型为int。n Ls=(Hello,World, China, Welcome) 数据元素类型为stri

2、ng。 n举例n Lb=(book1,book2,.,book100) 数据元素类型为下列所示的结构类型： struct bookinfo int No; /图书编号 char *name; /图书名称 char *auther; /作者名称 .; 在现实中，这种类型的数据结构很多很多，如学生档案学籍系统、图书管理系统、仓库管理系统、设备管理系统等线性表的基本操作n1. 初始化线性表L void InitList( ) n2. 求线性表的长度：int Length()n3.取表元：DataType Get(int i)n4.按值查找：int Locate(DataType x)n5.插入操作：

3、int Insert(DataType x, int i)n6.删除操作：int Deleted(int i) 返回2.2 线性表的顺序存储结构存储地址内存单元.da1d+La2d+2La3.d+(i-1)Lai.d+(n-1)Lan.n顺序存储结构n指用一组连续的存储单元依次存储线性表中的每个数据元素。如右图所示：说明：说明：L为每个数据元素所占据的存储单元数目。为每个数据元素所占据的存储单元数目。顺序表元素在内存的存储地址 n相邻两个数据元素的存储位置计算公式 LOC(ai+1)=LOC(ai)+Ln线性表中任意一个数据元素的存储位置的计算 公式为：LOC(ai+1)=LOC(a1)+(i

4、-1)*L 顺序存储结构的特点n逻辑与物理一致： 逻辑上相邻，物理上也相邻利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系n随机存取： 可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址顺序存储结构的类型定义n在C+中，线性表的顺序存储定义如下: #define MAXSIZE 100typedef int DataType;class SequenList public: void Initiate(); int Length(); int Insert(DataType x,int i); int Deleted(int i); int Locate(DataT

5、ype x); DataType Get(int i); private: DataType dataMAXSIZE; int len; 典型操作的算法实现1.顺序表的初始化顺序表的初始化即构造一个数据元素个数为0的空表，算法如下:算法3-1 顺序表的初始化void SequenList:Initiate() len=0;典型操作的算法实现2.插入运算 插入运算是指在顺序表的第i个位置上插入一个值为x的新元素，插入后使原表为n的顺序表（a1，a2，ai-1，ai，ai+1，an）变为表长为n+1的顺序表 （a1，a2，ai-1，x，ai，ai+1，an ） 其中，i 的合理取值范围为1in+1

6、。int SequenList:Insert(DataType x,int i) /在线性表的第i个数据元素之前插入一个新的数据元素x int j; if(len=MAXSIZE) coutoverflow!endl; /数据溢出 return 0; else if(ilen+1) /如果插入位置不合法 cout position is not correct!=i; j-) dataj=dataj-1; /元素后移 datai-1=x; /插入元素 len+; /表长度增加1 return 1; 插入算法的时间性能分析： 时间主要消耗在数据元素的移动上。在第i个位置上插入x，从第i个到第n个

7、元素都要向后移动一个位置，共需要移动n-(i-1)，即n-i1个数据元素。而i的取值范围为1in+1，即有n1个位置可以插入。设在第i个位置上做插入操作的概率为Pi，则平均移动数据元素的次数为： 在等概率情况下，Pi=1/(n+1)，则1i1(1)niniEP ni 11111(1)(1)12nniniiinEP ninin 时间复杂度为O(n) 典型操作的算法实现3. 删除运算 线性表的删除运算是指将表中第i个元素从线性表中删除，使原表长为n的线性表（a1，a2，ai-1，ai，ai+1，an）变成表长为n-1的线性表（a1，a2，ai-1，ai+1，an）i的取值范围为1in。在顺序表上完

8、成删除运算的步骤如下:（1）将数据元素ai+1an依次向前移动一个位置。（2）修改len值，使之仍指向最后一个数据元素的下一个位置。 int SequenList:Deleted(int i) /删除顺序表的第i个数据元素 int j; if(ilen) /若删除位置不合法 coutposition is not correct!endl; return 0; else for(j=i; jlen; j+) dataj-1=dataj; /元素前移 len-; /表长度减1 return 1; 本算法应注意以下问题 （1）删除第i个数据元素，i的取值为1in（即len），否则第i个元素不存在。

9、因此，要检查删除位置的有效性。（2）删除ai之后，该数据不再存在；如果需要，可先取出ai，再做删除。删除算法的时间性能分析：n与插入运算相同，其时间主要消耗在移动表中元素上。删除第i个元素时，其后面的元素ai+1an都要向前移动一个位置，共移动n-i个元素，所以平均移动数据元素的次数为n在等概率情况下，Pi=1/n，则n这说明，在顺序表上做删除运算时大约需要移动表中一半元素。显然，该算法的时间复杂度为O(n)。1()ndeiiEP ni1111()()2nndeiiinEP ninin典型操作的算法实现4.按值查找 在线性表中查找与给定值相等的数据元素。方法是：从第一个元素a1起依次和比较，直

10、到找到值相等的数据元素，返回它在顺序表中的位置值（下标+1）；或者查遍整个表都没有找到，返回0。 int SequenList:Locate(DataType x) /返回值为x的数据元素的位序值 int j=0; while(jlen)& (dataj!=x)j+; if(jlen)return j+1; else return 0; 算法主要运算是比较。次数与 x在表中的位置有关，也与表长有关。 当a1=x时，比较一次成功；当an=x时，比较n次成功。在查找成功的情况下，平均比较次数为（n+1）/2，时间复杂度为O(n)返回顺序表查询算法int Location_SeqList (

11、PSeqList PL, DataType x) /*顺序表检索，入口参数：为顺序表指针，检索元素，顺序表检索，入口参数：为顺序表指针，检索元素， 返回元素位置，返回元素位置，-1表示表不存在，表示表不存在，0表示查找失败表示查找失败*/ int i=0; if (!PL) printf(表不存在表不存在); return(-1); /*表不存在，不能检索表不存在，不能检索*/ while (i length & PL-datai!= x) i+; if (i=PL- length) return 0; else return (i +1); 典型操作的算法实现5. 顺序表的插入运算n

12、定义： 顺序表的插入是指在表的第i个位置上插入一个值为x的新元素，即在第i元素之前插入 x，使原表长为n的表：(e1，e2，. ，ei-1，ei，ei+1，. ，en) 变为表长为 n+1 表：(e1，e2，.，ei-1，x，ei，ei+1，.，en) 。其中i：1in+1。 n(1)检查待插入的表是否存在，若不存在退出；n(2)判断顺序表是否满(即表长length是否大于等于MAXSIZE)？若满，退出；否则执行(3)；n(3)检查插入位置的合法性( i 满足1=i length = MAXSIZE) printf(“表溢出表溢出”); return(-1); /*表空间已满，不能插入表空间

13、已满，不能插入*/ if (i PL- length +1) /*检查插入位置的合法性检查插入位置的合法性*/ printf(“插入位置不合法插入位置不合法”); return(0); for(j= PL - length -1; j=i-1; j-) PL -dataj+1= PL -dataj; /* 移动元素移动元素 */ PL-datai-1=x; /*新元素插入新元素插入*/ PL- length +; /*表长加表长加 1*/ return (1); /*插入成功，返回插入成功，返回*/ n设插入的位置为i ，则把ei到en元素向后移动一个位置共需要移动 ni1个元素。n设在第i个

14、位置上作插入的概率为Pi，n由于 1 i n+1，共有 n1个位置可以插入，即在情况下pi=1/ (n+1)，则：n算法的时间复杂度为(n)11111E(1 )(1 )12nniniiinp n in in 顺序表插入运算的效率分析删除的存储示意如下页所示典型操作的算法实现6. 顺序表的删除运算是指将表中第 i 个元素从线性表中去掉 删除前：表长n (e1，e2，. ，ei-1，ei，ei+1，.，en) 删除后：表长 n -1 (e1，e2，. ，ei-1， ei+1，. ，en) 其中i：1 i n。删除前删除后下页给出删除的算法删除的操作步骤:n（1）检查表是否存在，若不存在退出n（2）

15、检查删除位置的合法性（ i 是否为1ilength）若不满足，退出n（3）将ei+1en 顺序向上移动一位，ei+1占据ei 位置，（注意数据的移动方向）n（4）修改表长下页给出算法C语言描述顺序表删除算法int Delete_SeqList(PSeqList PL，int i) /*顺序表删除，入口参数：顺序表指针，删除元素位置，顺序表删除，入口参数：顺序表指针，删除元素位置，返回标志返回标志1表示成功，表示成功，0表示删除位置不合法，表示删除位置不合法，-1表示表不存在表示表不存在*/ int j; if (!PL) printf(表不存在表不存在); return(-1); /*表不存在

16、，不能删除元素表不存在，不能删除元素*/ if(i PL - length) /*检查删除位置的合法性检查删除位置的合法性*/ printf (删除位置不合法删除位置不合法); return(0); for(j=i; j length; j+) PL -dataj-1= PL-dataj; /*向上移动向上移动*/ PL- length -; return (1); /*删除成功删除成功*/ 删除算法的效率分析n在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为： n1idl21ni)(nn1E结论n顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数

17、据元素n当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，消耗的时间代价较大返回返回2.3 线性表的链式存储结构n线性表顺序存储结构的优点：n逻辑上相邻、物理上相邻，结构简单n可以根据元素的下标存取，速度便捷 n线性表顺序存储结构的缺点：n在做插入或删除元素的操作时，会产生大量的数据元素移动n对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用n线性表的容量难以扩充为此我们引入线性表的链式存储线性表的链式存储n逻辑上相邻的元素之间的物理位置是通过指针的指向来实现的，这种指向一般是通过的动态的地址指针来实现的（也可以通过静态的伪地址指针来实现）n每个

18、数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息下页给出链式存储的内存示意图：下页给出链式存储的内存示意图：headd cba存储地址内容直接后继存储地址100b120.120c160.144a100.160dNULL.首元素位置线性表链式存储结构示意图线性表链式存储结构示意图链式存储n表示每个数据元素的两部分信息组合在一起被称为结点, 其中表示数据元素内容的部分被称为数据域data；表示直接后继元素存储地址的部分被称为指针或指针域next n单链表中最后一个结点没有直接后继结点，它的指针域放入一个特殊的值NULLn为了简化对链表的操作，人们经常在链表的第一个结点

19、之前附加一个结点，并称为头结点headd cba带头结点的单链表结构示意图带头结点的单链表结构示意图n链式存储结构的特点n线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致n通过头指针进入链表，通过结点的指针域访问后继结点，寻找第一个结点和寻找最后一个结点所花费的时间不等，存取方式被为顺序存取方式对比顺序存储为对比顺序存储为随即存取方式随即存取方式链式存储链式存储的几种形式n单链表n循环链表n双向链表typedef int DataType;class Item public: DataType data; Item * next; Item()next=NULL;单链表的定义cla

20、ss Link public: Item *head; Link()head=NULL; Link()DeleteAll(); void Initiate(); void DeleteAll(); void HeadCreate(int n); void TailCreate(int n); void HeadCreateWithHead(int n); void TailCreateWithHead(int n); int Length(); Item *Locatex(DataType x); Item *Locatei(int i); DataType Get(int i); bool

21、Insert(DataType x,int i); bool Deleted(int i); void Print(); ;单链表的逻辑结构示意图单链表的几种形态单链表的基本操作1.初始化 void Link:Initiate() DeleteAll(); head=NULL;2.建立单链表 （1）从表尾到表头建立单链表（不带有空白头结点） void Link:HeadCreate(int n) DeleteAll(); Item *s,*p; int i; p=NULL; for(i=1; is-data; s-next=p; p=s; head=p;（2）从表头到表尾建立单链表（不带有空白

22、头结点） 头void Link:TailCreate(int n) Item *s,*r,*p; int i; DeleteAll(); p=NULL; for(i=1; is-data; s-next=NULL; if(p=NULL)p=r=s; else r-next=s; r=s; head = p;（3）从表尾到表头建立单链表（带有空白头结点） void Link:HeadCreateWithHead(int n) Item *s,*p; int i; DeleteAll(); p=new Item(); p-next=NULL; for(i=1; is-data; s-next=p-

23、next; p-next=s; head= p;（4）从表头到表尾建立单链表（带有空白头结点）void Link:TailCreateWithHead(int n) Item *s,*r,*p; int i; DeleteAll(); p=new Item(); p-next=NULL; r=p; for(i=1; is-data; r-next=s; r=s; r-next=NULL; head= p;3求表长 设定一个移动指针p和计数器j，初始化后，p所指结点后面若还有结点，p向后移动，计数器加1。 int Link:Length() int j; Item *p; j=1; p=head

24、-next; while(p!=NULL) j+; p=p-next; return -j;4查找操作 （1）按序号查找 从单链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针；否则继续下一个结点的查找，直到表结束为止。若没有第i个结点，则返回空；如果i=0；则返回头指针。 Item * Link:Locatei(int i) int j=1; Item *p; if(i=0)return head; p=head-next; while(p!=NULL)& (jnext; j+; if(j=i)return p; else coutposition is no

25、t correct!next; while(p!=NULL)& (p-data!=x)p=p-next; if(p) return p; else coutx is not exist!next; while(jnext; if(p=NULL)| (ji) coutposition is not correct!data;5插入(前插) 设p指向链表中某结点，s指向待插入的值为x的新结点，将*s插入*p的前面插入算法 找到第i-1个结点；若存在，继续步骤，否则结束。 申请新结点，将数据填入新结点的数据域。 将新结点插入。 bool Link:Insert(DataType x,int

26、i) Item *p,*s; p=Locatei(i-1); if(p=NULL) coutposition is not correct!data=x; s-next=p-next; p-next=s; return true;返回 循环链表循环链表为循环链表为空的情形空的情形特点：特点： 1.可以通过链表中任意节点遍历整个链表 2.可以通过尾指针访问到头节点 3.循环链表的操作基本上和单链表相同 返回双向链表如何定义双向链表的节点，请看下页双向链表的节点定义typedef int DataType;class DualItem public: DataType data; DualItem

27、 *next; DualItem *prior; DualItem()next=NULL; prior=NULL;在此定义基础之上，双向链表的插入、删除运算是如何实现的呢？双向链表的节点插入n设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面，n步骤如下：s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;双向链表的节点删除n设p指向双向链表中某结点，删除*p。n操作示意图如图2-17所示。n操作步骤如下：p-prior-next=p-next;p-next-prior=p-prior; free(p) 1、2的顺序可

28、以调换返回 2.3 线性表的应用举例 1. 要求在时间复杂度为O(n)的条件下将顺序表（a1，a2,an）重新排列为以a1为界的两部分：a1前面的值都比a1小，a1后面的值都比a1大 定义i、j分别指向第一个元素和最后一个元素，从最后一个元素aj开始逐一向前扫描每一个数据元素 （1）条件ij：若当前结点的数据元素aj比a大，表明它已经在a的后面，不必改变它的位置，继续比较aj前一个数据元素；若当前结点的数据元素aj比a小，说明它应该在a的前面，将aj保存到ai所在位置。（2）条件ij：若当前结点的数据元素ai比a小，说明它已经在a的前面，不必改变它的位置，继续比较ai后一个数据元素；若当前结点的数据元素ai比a大，说明它应该在a的后面，将ai保存到aj所在位置，重新执行步骤（1）。 #define MAXSIZE 100typedef int DataType;class SequenList public: friend void Part(Seque