第2章 线性表课件

第2章

线性表●线性结构：是n（≥0）个结点的有穷序列，表示为（a1，a2，…，an）；

●起始结点:线性结构中的第一个结点，即a1；

●终端结点:线性结构中的最后一个结点,即an；

●直接前趋：对线性结构中的任意一对相邻的结点ai和ai+1，称结点ai是结点ai+1的直接前趋。●直接后继：对线性结构中的任意一对相邻的结点ai和ai+1，称结点ai+1是结点ai的直接后继；2.1线性表的基本概念

2.1.1线性结构●空表：不含任何结点的线性结构，记为（）或

Φ。

●线性结构的基本特征：若至少含有一个结点，则除起始结点没有直接前趋外，其它结点有且仅有一个直接前趋；除终端结点没有直接后继外，其它结点有且仅有一个直接后继。

●线性表的逻辑结构是线性结构。●表长：线性表的长度，即表中所含结点的个数；●线性表的基本运算有如下几种：

（1）初始化INITIATE（head）:建立一个空线性表。

（2）求表长LENGThead（head）:计算线性表head的表长，即求表中的结点数。（3）读表元GET（head，i）:取线性表head中第i个元素的值。2.1.2线性表（4）定位LOCATE（head，X）:找出线性表head中与值X相符合的第一个元素的地址。

（5）插入INSERT（head，X，i）:在线性表head中第i个元素处插入值为X的新元素。

（6）删除DELETE（head，i）:删除线性表head中第i个元素。2.2线性表的顺序实现

2.2.1顺序表●顺序表是线性表的顺序存储结构。●顺序存储的线性表中，每个元素都相邻排列，因此它们的逻辑顺序与物理顺序是一致的，也可以说顺序表元素间的逻辑关系是由它们的位置关系体现出来的。

●假定顺序表中的数据元素的类型为datatype,则顺序表的类型可定义为：

constintmaxsize=顺序表的容量;（或：#defineMAXSIZE顺序表的容量）

typedefstruct

{datatypedata[maxsize]; /*顺序表元素存放在数组data中*/

intlast;/*顺序表的当前长度*/

}sqlist;/*顺序表的类型名为sqlist*/

sqlistL;/*定义一个顺序表L*/例如，若顺序表的数据元素的类型为float,顺序表容量为100，则该顺序表的类型定义为：#defineMAXSIZE100typedefstruct{floatdata[MAXSIZE];intlast;}sqlist;sqlistL；表空时，L.last=0；表长为L.last。●数据域data[MAXSIZE]是一个一维数组，其中MAXSIZE是根据问题定义的足够大的整数，顺序表中的数据从data[0]开始顺序存放。但当前顺序表的实际元素可能未达到MAXSIZE个，因此还应该用一个变量last来记录当前顺序表中最后一个元素在数组中的位置（下标）。a1a2…ai-1aiai+1…an…01…i-2i-1i…last-1…MAXSIZE-1data数组图2-1顺序表示意图空闲2.2.2基本操作在顺序表上的实现在顺序表中，很容易实现线性表的一些操作。注意：C语言中的数组下标从“0”开始，因此，顺序表中第i个元素是L.data[i-1]。1.插入线性表的插入运算是指在表的第i个位置上，插入一个值为x的新结点。使长度为n的线性表：(a1，a2，…，ai-1，ai，…，an)变成长度为n+1的线性表：(a1，a2，…，ai-1，x，ai，…，an)a1a2aiai+1an01i-1数组下标n-1ina1a2aiai+1an01i-1数组下标n-1inan-1x图2-3顺序表的插入L.lastL.last●插入操作算法voidinsert_sqlist(sqlistL,datatypeX,inti)

{intj;if（L.last==maxsize）error(“表满”);if（i<1||i>L.last+1）error（“非法位置）;/*插入在表外，出错*/for（j=L.last;j>=i;j--） L.data[j]=L.data[j-1];/*依次后移*/L.data[i-1]=X;/*插入新元素X*/L.last=L.last+1;/*表长增一*/}2.删除线性表的删除运算是指将表的第i(1≦i≦n)个结点删除，使长度为n的线性表：(a1，…，ai-1，ai，ai+1，…，an)变成长度为n-1的线性表:(a1，…，ai-1，ai+1，…，an)a1a2aiai+1an-101i-1数组下标n-2in-1a1a2ai+201i-1数组下标n-2ian图2-4顺序表的删除ai+1ani-2ai-1i-2ai-1●删除操作算法voiddelete_sqlist(sqlistL，inti){intj;if(i<1||i>L.last+1)printf("非法位置");for(j=i+1;j<=L.last;j++)L.data[j-2]=L.data[j-1];L.last=L.last-1;}3.定位(按值查找)顺序表的定位运算(按值查找)是指在表中查找与给定值X相等的结点。a1a2aiai+1an-101i-1数组下标n-2in-1顺序表的按值查找ani-2ai-1给定值为x定位(按值查找)算法intlocate_sqlist(sqlistL,datatypex){inti=1;while(i<=L.last&&L.data[i-1]!=x)i++;if(i<=L.last)returni;elsereturn0;}2.2.3顺序实现的算法分析

●插入算法的时间复杂度算法的规模是表的长度n，算法的时间主要化费在结点的移动上，因此以“结点移动”为标准操作。插入算法所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。当i=n+1时，数据不需要移动，移动次数为0；当i=1时，需移动表中所有数据，移动次数为n。则平均时间复杂度为：T(n)=O(n)在等概率情况下，平均移动结点的次数为：Ein=20+n=2n●删除算法的时间复杂度删除算法所需移动的次数不仅依赖于表的长度，而且还与删除位置有关。当i=n时，数据不需要移动，移动次数为0；当i=1时，需移动表中其余所有数据，移动次数为n-1；则平均时间复杂度为：

T(n)=O(n)在等概率情况下，平均移动元素的次数为：Ede=2n-1●定位(按值查找)算法的时间复杂度定位算法的时间主要化费在数据的比较上，所需比较的次数与x在表中的位置有关。当a1=x时，比较一次成功，比较次数为1；当an=x时，比较次数为n；T(n)=O(n)\在等概率情况下，平均比较元素的次数为：Elo=2n+12.3线性表的链接实现由于顺序表的特点是用物理位置上的相邻关系来表示结点间的逻辑相邻关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点。为避免大量结点的移动，现介绍线性表的另一种存储方式：链式存储结构，简称为链表(LinkedList)。链表是指用一组任意的存储单元来存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，因此，链表中结点的逻辑次序和物理次序不一定相同。为此在存储数据元素时，对每个数据元素ai，除了存放数据元素的自身信息ai外，还必须存放后继数据元素ai+1的地址。2.3.1单链表

其中：data域是数据域，next是指针域。由于上述链表的每一个结点只有一个指向后继的指针，所以称为单链表。datanext存放数据元素自身信息的单元称为“数据域”，存放后继元素地址的单元称为“指针域”，这两部分组成了链表中的结点结构：单链表存储结构示意图……a5200……a2190a1150……a3210a6260a4110……a8NULL……a7240160例：线性表(a1，a2，a3，a4，a5，a6，a7，a8)…110…150160…190200210…240…260地址datanextheadhead…a1a2an∧图2-5单链表示意图单链表的示意图通常表示为:…a1150a2190a8∧160160150240head单链表中的开始结点无前趋，故应设“头指针变量”（比如head）,该变量的值是指向单链表的第一个结点的指针，称为头指针。由于终端结点无后继结点，故终端结点的指针域为空，即NULL（图示中也可用∧表示)。实际应用中，通常用“头指针变量”来标识一个单链表。例如：若头指针变量是head，则把单链表称为“表head”或“head表”。头指针变量中存放的是单链表第一个结点的地址，头指针为“NULL”表示空表。C语言描述的单链表的结点定义如下：typedefstructnode{datatypedata；structnode*next；}LNode,*lklist,*pointer；定义头指针变量：lklisthead；或pointerhead；或LNode*head；单链表的结点是动态生成的。先定义一个指针变量p： pointer

p;则语句：p=(pointer)malloc(sizeof(LNode));完成了申请一块LNode类型的存储单元的操作，并将其首地址赋值给指针变量p。一旦p所指的结点变量不再需要了，又可通过标准函数free(p)释放该结点的存储空间。pp->datap->next图2-6申请一个结点2.3.2单链表的简单操作●带“头结点”的单链表在单链表中，第一个结点的处理与其它结点是不同的。原因是第一个结点的地址是存放在头指针变量中，而其余结点的地址是存放在其前趋结点的指针域中。“第一个结点”在单链表的很多操作（如插入、删除等）中都会遇到问题。如插入结点时，插在第一个位置和其他位置是不同的；删除结点时，删除第一个结点和其他结点也是不同的。为了方便操作，在单链表的第一个结点前增设一个类型相同的结点，称为“头结点”，其它结点称为表结点。表结点中的第一个结点称为首结点。表结点中的最后一个结点称为尾结点。头结点的数据域无定义，指针域中存放第一个结点（“首结点”）的地址；当单链表为空表时，该指针域为NULL。图2-7带“头结点”的单链表

head

…a1a2

∧

an∧——空表头结点首结点尾结点表结点head

带“头结点”的单链表有两个优点：a、由于第一个结点的地址被存放在头结点的指针域中，所以在链表的第一个结点上的操作就和在表的其它结点上的操作一致，无需进行特殊处理；b、无论链表是否为空，其头指针总是指向头结点，因此空表和非空表的处理也就统一了。●程序中与指针p有关的代码含义：(1)p->：p所指向的结点。(2)p->data:p所指向结点的数据域。(3)p->next:①p所指向结点的指针域。②p所指结点的下一个结点。(4)p=p->next:p移动，指向下一个结点。1.初始化（建立空表）算法如下：lklistinitiate_lklist(){ lklistt; t=malloc(size);t->next=NULL;returnt;}t

∧

2.求单链表的表长(1)求带头结点的单链表的表长intLength_lklist(lklisthead){lklistp=head;intj=0;while(p->next!=NULL){p=p->next;j++;}returnj;}

headp94516∧程序段的运行示意图：j=0;while(p->next!=NULL){p=p->next;j++;}j012345

ppppp94516∧headp3.按序号查找在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，沿着指针域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。按序号查找算法如下：pointerfind_lklist(lklisthead,inti);{p=head; j=0;while(p->next!=NULL&&j<i){p=p->next;j++;}if(j==i)returnp;elsereturnNULL;}i3j0while(p->next!=NULL&&j<i){p=p->next;j++;}

ppppp94516∧headp

2.3.3基本运算在单链表上的实现

1.定位（按值查找）按值查找是在链表中，查找是否有结点值等于给定值X，若有的话，则返回首次找到的其值为X的结点的地址；否则返回NULL。查找过程从首结点出发，顺着链表逐个将结点的值与给定值X作比较。定位（按值查找）算法intLocate_lklist(lklisthead,datatypex){p=head;j=0;while(p->next!=NULL&&p->data!=x){p=p->next;j++;}if(p->data==x)returnj;elsereturn0;}以(4,9,1,5,6)为例，查找x=5

pppp94516∧headp2.删除删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p；然后令q=p–>next指向结点ai，再令p–>next指向ai的后继结点ai+1，最后把ai从链上摘下，释放结点ai的存储空间。pai-1ai+1×

headai…q…p=Get_lklist(head,i-1);q=p->next;p->next=q->next;free(s);删除算法如下：voiddelete_lklist(lklisthead,inti){p=find_lklist(head,i-1); if(p==NULL&&p->next==NULL){q=p->next; p->next=q->next;free(q); } elseerror("不存在第i个结点"）}3.插入插入运算:在单链表L的第i个位置上插入值为x的新元素。pai-1sai×

headx…a1插入算法如下：voidinsert_lklist(lklisthead,datatypex,inti){p=find_lklist(head,i-1);if(p==NULL) error("不存在第i个位置"）else { s=malloc(size); s->data=x; s->next=p->next; p->next=s; }}2.5其它链表

2.5.1循环链表循环链表：循环链表与单链表的区别仅仅在于其尾结点的链域值不是null，而是一个指向头结点的指针，使得链表的头尾结点相接。循环链表的优点:

从表中任一结点出发都能通过后移操作而扫描整个循环链表。但对单链表来说,只有从头结点开始才能扫描表中全部结点。在图2-13(a)中，为要找到尾结点，必须从头指针出发扫描表中所有结点。改进的方法是不设头指针而改设尾指针，

如图2-13(c)所示。这样，无论是找头结点还是尾结点都很方便，它们的存贮位置分别是rear->next->next和rear。

由于在某些应用中链表的头结点和尾结点使用频繁，在这种场合使用带尾指针的循环链表比较合适。

head…■a1an图2-13（a）带头指针的循环链表rear…■a1an图2-13（b）带尾指针的循环链表2.5.2双链表

在单链表中,每个结点所含的指针指向其后继结点，故从任一结点找其后继很方便。但要找前趋结点则比较困难，其时间消耗是O(n)。若在每个结点中增加一个指针域，所含指针指向前趋结点，则可克服上述困难。这样构成的链表中有两

个方向不同的链，称为双链表。priordatanext双链表的结点形式为：

其中，指针prior和next分别指向数据域datd所含数据data所含数据元素的直接前趋和直接后继所在的结点。所有结点通过前趋指针和后继指针链接在一起，再加上起标识作用的头指针，就得到双向循环链表，简称双链表。双链表一般也是由头指针唯一确定的；增加头结点也能使双链表上的某些运算变得方便；将头结点和尾结点链接起来也能构成循环链表,称之为双向循环链表。

…a1

a2head图2-14带头结点的双向循环链表示意图ana3双链表结点的类型定义为：typedefstructdnode{datatypedata;structdnode*prior，*next;}*dlklist;

（1）双链表结点的摘除操作：设指针p指向某结点，摘除*p。操作如下：①p->prior->next=p->next；②p->next->prior=p->prior；free(p)；p①②图2-15双链表上结点的摘除××(2)双链表结点的链入操作:设指针p指向某结点,q指向待插入的新结点，将*q插到*p的后面。pq①②③④X图2-16双链表上结点的链入××●双链表结点链入操作的代码如下：①q->prior=p;②q->next=p->next;③p->next->prior=q;④p->next=q;pq①②③④X××2.6顺序实现与链接实现的比较

2.6.1空间性能的比较存储结点中数据域占用的存储量与整个存储结点占用存储量之比称为存储密度。显然，顺序表的存储密度(=1)高于链表的存储密度(<1)。因此，顺序实现的空间利用率高于链接实现。但是，顺序实现要求事先估计容量，有时比较困难。估计过大造成存储空间的浪费，估计过小导致溢出。相反，链接实现不需要事先估计“容量”，链表占用的存储空间可以随时改变。

2.6.2时间性能的比较1.定位运算在顺序表和单链表上的实现算法的时间复杂性是同量级的，均为O(n)。2.读表元运算在顺序表占只需常数时间O(1)便可实现：而在链表上实现读表元运算必须对表结点进行扫描，其平均时间复杂性为O(n)。3.插入、删除运算在链表上的实现可在O(1)时间内完成，而在顺序表上必须移动其他有关结点，平均时间复杂性为O(n)。

顺序表和单链表时间性能的比较T(n)读表元定位插入删除顺序表O(1)O(n)O(n)O(n)链表O(n)O(n)O(1)O(1)2.7串以字符为数据元素、以线性结构为逻辑结构的数据称为字符串。2.7.1串的基本概念(1)串是由零个或多个字符组成的有穷序列。含0个字符的串称为空串，用Ø表示。其他串称为非空串。串中所含字符的个数称为串的长度(或串长)。空串的长度为0。

通常将一个串表示成"a1a2…an"(n>=0)。注意：空串和空格串是两个不同的串，前者是长度为零的空串，后者是长度不为零的仅含空格符的非空串。(2)两个串是相等的，当且仅当它们的长度相等并且各个对应位置上的字符都相同。一个串中任意个连续字符组成的子序列称为该串的子串，该串称为它的所有子串的主串。例如，"D"、"A"、"AT"和"DAT"等等都是"DATA"的子串。(3)空串是任意串的子串。任意串是其自身的子串。(4)串变量和串常量。串常量在程序的说明部分加以命名，例如

const

s="data";

或： #defines"data"定义s为了一个串常量，即在该程序中s将代表串"data"。这样，

在程序中每当需要用到串"data"时，可以简单地用s代替，这就大大简化了程序的书写。

Ｃ语言规定，字符串常量按字符数组处理，它的值在程序的执行过程中是不能改变的，而串变量与其他变量不一样，不能由赋值语句对其进行整体赋值。2.7.2串的基本运算①赋值ASSIGN(S,T)，加工型运算。其作用是将串变量或串常量T的值(一个串)传给串变量S。

②判等E