《数据结构教程》-第二章

第2章线性表

2.3.2线性表上基本运算的实现

2.3.3循环链表

2.3.4双向链表上一页2.1线性表的定义与运算2.1.1线性表的定义线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，通常记为其中，n为表长;n=0时称为空表。在线性表中相邻元素之间存在着顺序关系。对于元素ai而言，ai-1称为ai的直接前趋ai+1称为ai的直接后继。即:(1)有且仅有一个开始结点(a1)，它没有直接前趋;(2)有且仅有一个终端结点(an)，它没有直接后继;(3)除了开始结点和终端结点以外，其余的结点都有且仅有一个直接前驭和一个直接后继。下一页返回2.1线性表的定义与运算2.线性表举例(1)简单的线性表例如一年12个月:(1,2,3,4,5,6,7,8,9,10,11,12)在C或C++语言中可以把它们定义为数值型。又例如26个英文字母表:(a，b，c，d，e，f,g,，…，x，y,，z)在C或C++语言中可以把它们定义为字符型。(2)复杂的线性表例如一个学生人学情况表可以是用户自定义的学生类型(如C语言中的结构体或数据库管理系统中的记录)。由于表格中各记录之间存在“一对一”的关系，所以它也是一种线性表。下一页返回上一页2.1线性表的定义与运算3.线性表的二元组表示Linearity=(D，R)数据对象:D={ai|1≤i≤nn≥0}数据关系：{<ai-1,ai>|2≤i≤n}关系中<ai-1,ai>是一个序偶的集合，它表示线性表中数据元素的相邻关系，即ai-1领先ai,ai领先ai+1。下一页返回上一页2.1线性表的定义与运算2.1.2线性表的基本操作数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的，因此，下面定义的线性表的基本运算作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。线性表上的基本操作有以下几种。(1)创建线性表:CreateList()。初始条件:表不存在操作结果:构造一个空的线性表下一页返回上一页2.1线性表的定义与运算(2)求线性表的长度:LengthList(L)。初始条件:表L存在操作结果:返回线性表中的所含元素的个数(3)按值查找:SearchList(L，x),x是给定的一个数据元素。初始条件:线性表L存在操作结果:在表L中查找值为x的数据元素，其结果返回在L中首次出现的值为x的那个元素的序号或地址，称为查找成功;否则，在L中未找到值为x的数据元素，返回一个特殊值表示查找失败。(4)插人操作:InsList(L,i,x)。初始条件:线性表L存在，插人位置正确(1≤i≤n+1,n为插入前的表长)。操作结果:在线性表L的第i个位置上插人一个值为x的新元素，这样使原序号为i,i+1，...，n的数据元素的序号变为i+1，i+2，...，n+1，插入后表长=原表长+1。下一页返回上一页2.1线性表的定义与运算(5)删除操作:DelList(L,i)。初始条件:线性表L存在，l≤i≤n。操作结果:在线性表L中删除序号为i的数据元素，删除后使序号为i+1,i+2，...，n的元素变为序号为i,i+1，...，n-1，新表长=原表长-1。(6)显示操作:ShowList(L)初始条件:线性表L存在，且非空。操作结果:显示线性表L中的所有元素。返回上一页2.2

线性表的顺序存储2.2.1顺序表线性表的顺序存储是指在用一组地址连续的存储单元依次存储线性表的数据元素，把用这种存储形式存储的线性表称为顺序表。顺序表的逻辑顺序和物理顺序是一致的，如图2-1所示。设a1的存储地址LOC(a1)为首地址B，每个数据元素占d个存储单元，则第i个数据元素的地址为即下一页返回2.2

线性表的顺序存储这就是说只要知道顺序表首地址和每个数据元素所占存储单元的个数，就可以求出第L个数据元素的存储地址来，这也是顺序表具有按数据元素的序号随机存取的特点。在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，可以用一维数组来表示:Dataypedata[MAXLEN];intlast;图2-1顺序表中，设表长为last+1，则数据元素分别存放在，data[0]到data[last]中。从结构性上考虑，通常将data和last封装成一个结构作为顺序表的类型:下一页返回上一页2.2

线性表的顺序存储typedefstruct{dataypedata[MAXLEN];intlast;}SeqList;定义一个顺序表:SeqListL;如图2-2所示。2.2.2顺序表上基本运算的实现1.顺序表的初始化顺序表的初始化即构造一个空表，将L设为指针参数，动态分配存储空间，然后，将表中last指针置为-1，表示表为空。算法如下:下一页返回上一页2.2

线性表的顺序存储2.插入运算线性表的插人是指在表的第i个位置上插人一个值为x的新元素，插入后使原表长为的表，成为表长为n+1的表。顺序表插入结点运算的步骤如下:(1)将an~ai之间的所有结点依次后移，为新元素让出第i个位置;下一页返回上一页2.2

线性表的顺序存储(2)将新结点x插入到第i个位置;(3)修改last指针(相当于修改表长)，使之仍指向最后一个元素。算法如下:下一页返回上一页2.2

线性表的顺序存储下一页返回上一页2.2

线性表的顺序存储要注意以下几个问题。(1)顺序表中数据区域有MAXLEN个存储单元，所以在插入时先检查顺序表是否已满，在表满的情况下不能再做插入，否则产生溢出错误。(2)检验插入位置的有效性，这里a的有效范围是:1≤i≤n+1，其中n为原表长。(3)注意数据的移动方向，必须从原线性表最后一个结点(an)起往后移动，如图2-3所示。顺序表插入操作需移动表中一半数据元素，其时间复杂度为O(n)。下一页返回上一页2.2

线性表的顺序存储3.删除运算线性表的删除运算是指将表中第i个元素从线性表中去掉，删除后使原表长为n的线性表变为表长为n-1的线性表i的取值范围为:l≤i≤n。顺序表删除结点运算的步骤如下:下一页返回上一页2.2

线性表的顺序存储(1)将ai+1~an之间的结点依次顺序向上移动。(2)修改last指针(相当于修改表长)使之仍指向最后一个元素。顺序表中的删除元素ai前后的情况如图2-4所示。算法如下:下一页返回上一页2.2

线性表的顺序存储本算法应注意以下问题。(1)首先要检查删除位置的有效性，删除第i个元素，i的取值为:1≤i≤n。(2)当表空时不能做删除，因表空时L->last的值为-1，条件(i<1||i>L->last+1)也包括了对表空的检查。(3)删除ai之后，该数据则已不存在，如果需要，必须先取出ai后，再将其删除。删除算法的时间性能分析:与插入运算相同，其时间主要消耗在了移动表中元素上(大约需要移动表中一半的元素)，显然该算法的时间复杂度为:O(n)。下一页返回上一页2.2

线性表的顺序存储4.按值查找线性表中的按值查找是指在线性表中查找与给定值x相等的数据元素。算法如下:下一页返回上一页2.2

线性表的顺序存储上述算法的主要运算是比较。当ai=x时,比较一次成功;当an=x时，比较n次成功)。平均比较次数为(n+1)/2，时间复杂度为:O(n)。返回上一页2.3

线性表的链式存储通过前面的学习，可以总结以下几点。(1)顺序存储的优点①可以随机存取表中任意一个元素。②存储位置可以用公式:B+(i-1)×d计算。③节约存储空间。(2)顺序存储的缺点①对顺序表作插入、删除时需要通过移动大量的数据元素，影响了运行效率。②线性表预先分配空间时，必须按最大空间分配，存储空间得不到充分的利用。③表的容量难以扩充(对有些高级语言而言)。下一页返回2.3

线性表的链式存储下面介绍线性表的链式存储结构，它不需要用地址连续的存储单元来实现。因为它不需要逻辑上相邻的两个数据元素物理上也相邻。链式存储结构的线性表对于插入、删除等操作不再需要移动数据元素，但顺序表随机存取的优点一也随之失去了。2.3.1线性链表1.线性链式存储结构的特点(1)用一组任意的存储单元存储线性表的数据元素。(2)单链表的每个结点由一个数据域和一个指针域组成:结点中存放数据元素信息的域称为数据域;存放其后继地址的域称为指针域。单链表节点结构如图2-5所示。(3)单链表的存取必须从头指针开始，如图2-6所示。下一页返回上一页2.3

线性表的链式存储2.关于头指针、头结点和开始结点(1)头指针—指向链表中第一个结点(头结点或无头结点时的开始结点)的指针。(2)头结点—在开始结点之前附加的一个结点。(3)开始结点—在链表中，存储第一个数据元素(a1)的结点。3.在C(或C++)中可以用“结构体指针”来描述单链表由一个个结点构成，其结点的定义如下:下一页返回上一页2.3

线性表的链式存储下一页返回上一页2.3

线性表的链式存储上面定义的Node是结点的类型，LinkList是指向Node类型结点的指针类型。为了增强程序的可读性，通常将标识一个链表的头指针说明为LinkList类型的变量，如LinkListL;当L有定义时，值要么为NULL，则表示一个空表;要么为第一个结点的地址，即链表的头指针;将操作中用到指向某结点的指针变量说明为Node*类型，如Node*p;则语句:p=(Node*)malloc(sizeof(Node));完成了申请一块Node类型的存储单元的操作，并将其地址赋值给变量P(如图2-7所示)。下一页返回上一页2.3

线性表的链式存储p所指的结点为*p,*p的类型为Node型，所以该结点的数据域为(*p).data或P->data,指针域为(*p).next或P->next。free(p)则表示释放p。2.3.2线性表上基本运算的实现1.建立线性链表先考虑如何建立单链表。假设通过一个含有n个数据的数组来建立单链表。建立单链表的常用方法有以下两种。(1)在链表的头部建立线性表该方法从一个空表开始，读取数组中的元素，生成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插人到当前链表的表头上，直到结束为止(如图2-8所示)。2.3

线性表的链式存储在链表的头部入结点建立线性表的算法:下一页返回上一页2.3

线性表的链式存储下一页返回上一页2.3

线性表的链式存储(2)在链表的尾部插人结点建立线性表算法头插法建立链表虽然算法简单，但生成的链表中结点的次序和原数组元素的顺序相反。若希望两者次序一致，可采用尾插法建立。该方法是将新结点插到当前链表的表尾上，为此必须增加一个尾指针p，使其始终指向当前链表的尾结点，如图2-9所示。在链表的尾部插入结点建立线性表的算法:下一页返回上一页2.3

线性表的链式存储下一页返回上一页2.3

线性表的链式存储下一页返回上一页2.3

线性表的链式存储为了方便操作，有时在链表的头部加入一个“头结点”，头结点的类型与数据结点一致，标识链表的头指针变量L中存放该结点的地址，这样即使是空表，头指针变量L也不为空。头结点的加人使得在任何位置上插人结点都同样处理，不必考虑在链表中插人第一个结点的情况。使得插入结点的过程统一起来。头结点的加入完全是为了运算的方便，它的数据域无定义，指针域中存放的是第一个数据结点的地址，如图2-10所示。带头节点在链表的尾部插入结点建立线性表的算法:下一页返回上一页2.3

线性表的链式存储下一页返回上一页2.3

线性表的链式存储下一页返回上一页2.3

线性表的链式存储2.求表长算法思路:设一个移动指针p和计数器n，初始化后，p所指结点后面若还有结点，p向后移动，计数器加1。(1)设L是带头结点的线性链表(线性表的长度不包括头结点)。算法如下:下一页返回上一页2.3

线性表的链式存储(2)设L是不带头结点的线性链表。算法如下:下一页返回上一页2.3

线性表的链式存储在以后的算法中不加说明则认为线性链表是带头结点的。上述算法的时间复杂度均为O(n)。3.查找操作(1)序号查找SearchList1(L,i)算法思路:从链表的第一个元素结点开始，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续下一个，直到链表结束。若没有第i个结点则返回空。下一页返回上一页2.3

线性表的链式存储下一页返回上一页2.3

线性表的链式存储(2)值查找即定位SearchList2(L,x)算法思路:从链表的第一个元素结点开始，判断当前结点其值是否等于x，若是，返回该结点的指针，否则继续下一个，直到链表结束。若找不到则返回空。算法如下:下一页返回上一页2.3

线性表的链式存储以上两个算法的时间复杂度均为O(n)。4.插入(1)后插结点:设p指向线性链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面，插人示意图如图2-11所示。插入结点操作:①s->next=p->next;②p->next=s;//注意:两个指针的操作顺序不能交换(2)前插结点:设p指向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面，插入示意图如图2-12所示。下一页返回上一页2.3

线性表的链式存储与后插不同的是:首先要找到*p的前驱*q，然后再完成在*q之后插入*s，设线性链表头指针为L，操作如下:q=L;while(q->next!=p)q=q->next;S->next=q->next;Q->next=s;后插操作的时间复杂性为O(1)，前插操作因为要找*p的前驱，时间性能为O(n);其实这时更关心的是数据元素之间的逻辑关系，所以仍然可以将*s插人到*p的后面，然后将p->data与s->data交换即可，这样即满足了逻辑关系，也能使得时间复杂性为O(1)。下一页返回上一页2.3

线性表的链式存储(3)插入运算InsList(i,x)。算法思路:①找到第i-1个结点;若存在继续下一步，否则结束;②申请一个新结点，并赋值;③将新结点插入;④结束。算法如下:voidInsList(LinkListhead，inti，charx)

//插入结点元素，head为头指针，指向头结点下一页返回上一页2.3

线性表的链式存储下一页返回上一页2.3

线性表的链式存储下一页返回上一页2.3

线性表的链式存储这个算法的时间复杂度为O(n)。5.删除(1)删除结点设p指向线性链表中某结点，删除*p。操作示意图如图2-13所示。通过图2-13可见，要实现对结点*p的删除，首先要找到*p的前驱结点*q，然后完成指针的操作即可。指针的操作由下列语句实现:q->next=p->next;delete(p);下一页返回上一页2.3

线性表的链式存储显然找*p前驱的时间复杂性为O(n)。若要删除*p的后继结点(假设存在)，则可以直接完成。s=p->next;p->next=s->next;delete(s);该操作的时间复杂性为O(1)。(2)删除运算DelList(L,x)算法思路:①如果链表为空，则不能进行删除操作;②查找值为x的结点，并得到其前趋结点;③将值为x的结点从链表中删除。下一页返回上一页2.3

线性表的链式存储算法如下:下一页返回上一页2.3

线性表的链式存储下一页返回上一页2.3

线性表的链式存储算法的时间复杂度为O(n)。通过上面的学习可知:①在线性链表上插入、删除一个结点，必须知道其前驱结点;②线性链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。下一页返回上一页2.3

线性表的链式存储2.3.3循环链表1.特点将线性单链表中最后一个结点的指针域指向头结点，整个链表头尾结点相连形成一个环，就构成了单循环链表，如图2-14所示。2.在循环链表上的操作循环链表上的操作和非循环链表上的操作基本相同，差别在于算法中循环条件不是判断指针是否为空(P->NEXT==NULL)，而是判断指针是否为头指针:P->NEXT==head下一页返回上一页2.3

线性表的链式存储3.在循环链表中设尾指针可以简化某些操作线性链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针T来标识，可以提高操作效率。当知道其尾指针T后，其另一端的第一个结点的指针是T->next->next(表中有头结点)，仅改变两个指针值即可，其运算时间复杂度为O(1)。例如:对两个单循环链表H1、H2的连接操作，是将H2的第一个数据结点接到H1的尾结点，如用头指针标识，则需要找到第一个链表的尾结点，其时间复杂性为O(n)，而链表若用尾指针T1,T2来标识，则时间性能为O(1)(如图2-15所示)。操作如下:下一页返回上一页2.3

线性表的链式存储4.关于存储密度(1)存储密度是指结点数据本身所占的存储空间和整个结点结构所占的存储空间之比。即: