二十世纪人类最伟大的科技成就之一

第二章线性表2.1线性表抽象数据类型2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4静态链表2.5算法设计举例1回顾与思考:1什么是数组?为何需要数组?2数组中元素之间是什么关系?3数组中如何查找,删除元素?4本班同学的信息如何保存?

以上问题归属于线性表，线性表是线性结构的一种(最简单的一种），下面先来介绍线性结构2线性表是最常用且最简单的一种数据结构。它有两种存储结构,即顺序表与链表。如果能将线性表中的查找、插入、删除掌握好,可以方便地解决该课程中其他章节的相关问题,如栈、队列、图状结构、查找表、排序等。3线性结构的定义：

若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为：（a1,a2,……,an）

简言之，线性结构反映结点间的逻辑关系是

的。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------线性表一对一(1:1)4思考：如何解决Josephus(约瑟夫)问题？问题描述:

编号为1，2，......，n的n个人按照顺时针方向围坐一圈，每个人有且只有一个密码（正整数）。一开始任选一个正整数作为报数上限值，从第一个人开始顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。5问题分析：这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。

6一种简化的情况72.1线性表的基本概念１、线性表它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据元素操作的，由n（n≥0)个相同类型数据元素a0,a1,…,an-1组成的线性结构。逻辑关系如下图所示，各结点表示元素，结点间的连线表示元素间的关系。8线性表例：9（a0,a1,…ai-1，ai,ai＋1

，…,an-1）线性表的逻辑结构：n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点10

（A,B,C,D,……,Z）学号姓名性别年龄班级012003010622陈建武男192003级电信0301班012003010704赵玉凤女182003级电信0302班012003010813王泽男192003级电信0303班012003010906薛荃男192003级电信0304班012003011018王春男

192003级电信0305班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：

数据元素都是同类型（字母），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！例1分析26个英文字母组成的英文表是什么结构。11２、线性表抽象数据类型

它包括两个方面：数据集合：｛a0,a1,…,an-1｝ai的数据类型为DataType

操作集合：(1)ListInitiate(L)

初始化线性表

(2)ListInsert(L,i,x)

插入数据元素

(3)ListLength(L)

求当前数据元素个数

(4)ListDelete(L,i,x)

删除数据元素

(5)ListGet(L,i,x)

取数据元素

等123、线性表的存储结构(1)顺序存储结构:它是使用一片地址连续的有限内存单元空间存储数据元素的一种计算机存储数据方法。特点：(任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻)逻辑上相邻的元素，物理上也相邻。(2)链式存储结构:它是把数据元素和指针定义成一个存储体，使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法。特点：任意两个在逻辑上相邻的数据元素在物理上不一定相邻，数据元素的逻辑次序是通过链中的指针链接实现的。132.2线性表的顺序表示和实现顺序存储的线性表，称为顺序表一、顺序表的存储结构二、顺序表的实现三、顺序表的运算效率分析14一、顺序表的存储结构表示

1、顺序表：用一组地址连续的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数据元素的存储。可以利用数组V[n]来实现注意：在C语言中数组的下标是从0开始，即：

V[n]的有效范围是从V[0]～V[n-1]15顺序存储示例16(1)

逻辑上相邻的数据元素，其物理上也相邻；(2)

若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。设首元素a0的存放地址为LOC(a0)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：

LOC(ai+1)=LOC(ai

)+L

LOC(ai

)=LOC(a0)+L*i对上述公式的解释如图所示2、线性表顺序存储特点：17a0a1……aiai+1……an-1

地址内容元素在表中的位序0i1n-1空闲区i+1Lb=LOC(a0)b+Lb+iLb+(n-1)Lb+(MaxSize-1)LLOC(ai

)=LOC(a0)+L*i3、线性表的顺序存储结构示意图184、用C语言描述

typedef

struct

{

DateType

list[MaxSize];

intsize;}SeqList;

/*MaxSize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size≤

MaxSize，SeqList是该结构体的名字。*/19设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是多少？113LOC(M[3])=98+5×3=113解：已知地址计算通式为：LOC(ai)=LOC(a0)+L*i例120二、

顺序表的实现（或操作）数据结构的基本运算：修改、插入、删除、查找、排序1)修改通过数组的下标便可访问某个特定元素并修改之。核心语句:

V[i]=x;显然，顺序表修改操作的时间效率是O(1)21动画演示：

2插入在线性表（n个元素）的第i个位置前插入一个元素22实现步骤：将第n至第i位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。注意：事先应判断:插入位置i是否合法?表是否已满?

for(j=n-1;j>=i;j--)a[j+1]=a[j];

a[i]=x;n++;//元素后移一个位置//插入x//表长加1核心语句：23在线性表的第i个位置前插入一个元素的示意图如下：121321242830427712132124252830427712345678123456789插入2524实现步骤：将第i+1

至第n位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i是否合法?删除线性表的第i个位置上的元素for(j=i+1;j<=n-1;j++)a[j-1]=a[j];n--;//元素前移一个位置//表长减1核心语句：3)删除25123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：26删除元素演示：27三、顺序表操作的效率分析算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）

T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的位置.思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。时间效率分析:28推导：假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移n次；若在a1后面插入，要后移n-1个元素，后移次数为n-1;……若在an-1后面插入，要后移1个元素；若在尾结点an之后插入，则后移0个元素；所有可能的元素移动次数合计：0+1+…+n=n(n+1)/2

故插入时的平均移动次数为：n(n+1)/2÷（n+1）＝n/2≈O(n)

共有多少种插入形式?——连头带尾有n+1种!29同理可证：顺序表删除一元素的时间效率为:T（n)=(n-1)/2≈O(n)

插入效率：删除效率：即插入、删除算法的平均时间复杂度为O(n)30链式存储结构本节小结线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素。解决问题的思路：改用另一种线性存储方式：31简单回顾

线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点:可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素;

需要预先确定数据元素的最大个数。解决问题的思路：改用另一种线性存储方式：链式存储结构322.3线性表的链式表示和实现一、单链表的存储结构二、单链表的操作实现三、链表的运算效率分析33思考：1、顺序表删除和插入为何效率低下？2、有没有一种办法使得元素删除和插入时不需要移动元素？34１、单链式及表示方法(1)单链表:构成链表的结点只有一个指向直接后继结点的指针。其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。如何实现？通过指针来实现！让每个存储结点都包含两部分：数据域和指针域指针域数据域nextdata或样式：数据域：存储元素数值数据指针域：存储直接后继的存储位置设计思想：牺牲空间效率换取时间效率一、单链表的存储结构35定义单链表结点的结构体如下:

typedef

structNode

{

DataTypedata;

structNode*next;

}SLNode;

其中,data域用来存放数据元素,next域用来存放指向下一个结点的指针。

36例：请画出26个英文字母表的链式存储结构。该字母表在内存中链式存放的样式举例如下：解：该字母表的逻辑结构为：（a,b,…,y,z）链表存放示意图如下：a1heada2/\an……讨论1

：每个存储结点都包含两部分：数据域和

。讨论2：在单链表中，除了首元结点外，任一结点的存储位置由

指示。其直接前驱结点的链域的值指针域(链域)371）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表：

结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表（但未必是双向链表）；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。a1heada2an……循环链表示意图head(2)与链式存储有关的术语：384）头指针、头结点和首结点的区别头指针头结点首结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首结点是指链表中存储线性表第一个数据元素a０的结点。示意图如下：39答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表示空表？头结点即在链表的首结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；^头指针无头结点^头指针头结点有头结点有头结点时，当头结点的指针域为空时表示空表。头结点不计入链表长度！40一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31称：头指针H的值是31２、带头结点单链表和不带头结点单链表的比较例：41上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①无头结点②有头结点头结点不计入链表长度！42

对比带头结点的单链表的插入、删除过程和不带带头结点的单链表的插入、删除过程，可以得知：若设计的单链表带头结点，则无论是在第一个数据元素结点前插入还是在其他数据元素结点前插入都不会改变头指针的数值。若设计的单链表不带头结点，则在第一个数据元素结点前插入与在其他数据元素结点前插入其算法的处理方法不同。在单链表中删除一个结点时类似。因此，单链表一般构造成带头结点的单链表。43讨论:

链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。答：以26个字母的链表为例，每个结点都有两个分量：字符型指针型设每个结点用变量node表示，其指针用p表示，两个分量分别用data和*next表示，这两个分量如何赋值？p*nextdatanode方式1：直接表示为

node.data＝'a'；node.next=q方式2：p指向结点首地址，然后p->data='a';p->next=q;方式3：p指向结点首地址，然后(*p).data='a'；(*p).next＝q‘a’‘b’qp44设p为指向链表的第i个元素的指针,则第i个元素的数据域写为

，指针域写为

。练习：p->dataai的值p->nextai+1的地址附1：介绍C的三个有用的库函数/算符（都在<stdlib.h>中）：sizeof(x)——计算变量x的长度（字节数）；malloc(m)—开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)——释放指针p所指变量的存储空间，即彻底删除一个变量。45sizeof(x)——计算x的长度malloc(m)—开m字节空间free(p)——删除一个变量问1：自定义结构类型变量node的长度m是多少？问2：结构变量node的首地址(指针p）是多少？问3：怎样删除结构变量node？*nextdatanode，长度为m字节pm＝sizeof(node)//单位是字节p＝(node*)malloc(m)free(p)//只能借助node的指针删除！P->data=‘a’;p->next=q464748②对于指向结构类型的指针变量，可说明为：

SLNode*p,*q;

//或用

struct

SLNode

*p,*q;//注：上面已经定义了SLNode为用户自定义的Node类型。①类型定义和变量说明可以合写为：typedef

structNode//Node是自定义结构类型名称{

DataType

data;//定义数据域的变量名及其类型

structNode*next;//定义指针域的变量名及其类型}SLNode，*p;//SLNode是Node结构类型的类型替代,

*p是指针型的Node结构类型的替代附2：补充结构体类型的C表示法49typedef

structNode{

DataTypedata;

structNode*next;}SLNode,*LinkList;教材P37对于线性表的单链表存储结构描述:问1：第一行的Node与最后一行的SLNode是不是一回事？答1：不是。前者Node是结构名，后者SLNode是对整个struct类型的一种“缩写”，是一种“新定义名”，它只是对现有类型名的补充，而不是取代。请注意：typedef不可能创造任何新的数据类型，而仅仅是在原有的数据类型中命名一个新名字，其目的是使你的程序更易阅读和移植。50Typedef

struct

Lnode{

ElemTypedata;

struct

Lnode*next;}Lnode,*LinkList;注意：student和student同名但不同意。同名是为了表述起来方便。例如，若结构名为student，其新定义名缩写也最好写成student，因为描述的对象相同，方便阅读和理解。问2：结构体中间的那个structNode是何意？答2：在“缩写”SLNode还没出现之前，只能用原始的structNode来进行变量说明。此处说明了指针分量的数据类型是structNode。typedef

structstudent{charname;

intage;}student,*pointer;

51例：单链表的建立和输出例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z）,请写出C语言程序。实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。先挖“坑”,后种“萝卜”！52#include<stdio.h>#include<stdlib.h>typedef

structnode{chardata;structnode*next;}node;将全局变量及函数提前说明：node*p,*q,*head;//一般需要3个指针变量intn;//数据元素的个数intm=sizeof(node);/*结构类型定义好之后，每个node类型的长度就固定了，m求一次即可*/53新手特别容易忘记！！{inti;head=(node*)malloc(m);//m=sizeof(node)前面已求出p=head;for(i=1;i<26;i++)//因尾结点要特殊处理，故i≠26{p->data=i+‘a’-1;//第一个结点值为字符ap->next=(node*)malloc(m);//为后继结点“挖坑”！p=p->next；}//让指针变量P指向后一个结点p->data=i+‘a’-1;//最后一个元素要单独处理p->next=NULL;}//单链表尾结点的指针域要置空！voidbuild()

//字母链表的生成。要一个个慢慢链入54{p=head;while(p)//当指针不空时循环（仅限于无头结点的情况）

{printf("%c",p->data);

p=p->next;//让指针不断“顺藤摸瓜”

}}讨论：要统计链表中数据元素的个数，该如何改写？

sum++;sum=0;voiddisplay()/*字母链表的输出*/55voidmain()

{

build();

display();

}

问：上述建立的单链表带头结点吗？

56二、单链表的操作实现定义单链表结点的结构体如下:

typedef

structNode

{

DataTypedata;

structNode*next;

}SLNode;１、初始化voidListInitiate(SLNode**head)／*初始化*/{ /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/ if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1); (*head)->next=NULL;

/*置链尾标记NULL*/}57２、求单链表中数据元素的个数

int

ListLength(SLNode*head)

{

SLNode*p=head;

/*p指向头结点*/

intsize=0;

/*size初始为0*/

while(p->next!=NULL)/*循环计数*/

{

p=p->next;

size++;

}

returnsize;

}58插入元素动画演示：３、向单链表中插入一个元素59在链表中插入一个元素X的示意图如下：Xqabp链表插入的核心语句：Step1：q->next=p->next;Step2：p->next=q；p->nexts->next思考：Step1和2能互换么？X结点的生成方式：m=sizeof(SLNode);q=(SLNode

*)malloc(m);q->data=X;q->next=?bap插入X60int

ListInsert(SLNode*head,inti,DataTypex)/*在带头结点的单链表head的数据元素ai（0≤i≤size）结点前*//*插入一个存放数据元素x的结点*/{

SLNode*p,*q;

intj; p=head; /*p指向首元结点*/ j=-1; /*j初始为-1*/

while(p->next!=NULL&&j<i-1) /*最终让指针p指向数据元素ai-1结点*/ { p=p->next; j++; }61if(j!=i-1) {

printf("插入位置参数错！"); return0; } /*生成新结点由指针q指示*/

if((q=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1); q->data=x; q->next=p->next; /*给指针q->next赋值*/ p->next=q; /*给指针p->next重新赋值*/ return1;}62删除元素动画演示：４、从单链表中删除一个元素63在链表中删除某元素b的示意图如下：cabp删除动作的核心语句（要借助辅助指针变量q）：q=p->next;//首先保存b的指针，靠它才能找到c；p->next=q->next;//将a、c两结点相连，淘汰b结点；free(q)；//彻底释放b结点空间p->next思考：省略free(q)语句行不行？(p->next)->next××q64三、单链表的操作效率分析（1）查找

因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为

O(n)。时间效率分析（2）插入和删除

因线性链表不需要移动元素，只要修改指针，仅就插入或删除而言，时间复杂度为

O(1)。但是，如果要在单链表中进行在某结点前插或删除操作，因为要从头查找前驱结点，所以一般情况下，单链表插入和删除操作的时间复杂度是

O(n)（同顺序表）。65四、应用举例例１、编程实现：建立一个单链表，首先依次输入数据元素１,２,…,10，然后删除数据元素５，最后依次显示当前表中的数据元素。

#include<stdio.h>#include<stdlib.h>#include<malloc.h>

typedef

int

DataType; #include"LinList.h"重点是链表66voidmain(void)

{SLNode*head;

inti,x;

ListInitiate(&head);

for(i=0;i<10;i++){

if(ListInsert(head,i,i+1)==0)

{printf("错误!\n");return;}

}

if(ListDelete(head,4,&x)==0){

printf("错误!\n");

return;

}

67

for(i=0;i<ListLength(head);i++)

{

if(ListGet(head,i,&x)==0)

{ printf("错误!\n");

return;}

elseprintf("%d",x);

}

Destroy(&head);

}

68五、循环单链表xheada0an……

循环链表示意图：循环单链表是单链表的另一种形式，其结构特点是链表中的最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。问：带头结点的循环单链表的插入、删除算法如何写？head69例2：试用C语言编写一个算法，将一循环单链表就地逆置。操作前：（a1,a2,…ai-1，ai,ai+1

，…,an）操作后：（an,…ai+1

，ai,ai-1

，…,a2,a1

）70六、双向链表１、双向链表的存储结构双向链表：链表中每个结点除后继指针域和数据域外还有一个前驱指针域。其结点的结构为：双向链表结点的结构体定义如下：

typedef

structNode{DataTypedata;

structNode*next;

structNode*prior;}DLNode;priordatanext71sa0

a1

an

带头结点的双向循环链表的结构示意图。

head…与单链表类同，双向链表分带头结点和不带头结点两种，也分有循环和非循环两种结构。下面仅讨论带头结点的双向循环链表。722、双向链表的操作实现(1)前插设p已指向第i元素，请在第i元素前插入元素xx

sai-1

ai

p指针域的变化：①ai-1的后继从ai

(指针是p)变为x（指针是s):s->next=p;p->prior->next=s;②ai

的前驱从ai-1(指针是p->prior)变为x(指针是s);s->prior=p->prior;p->prior=s;73

p指针域的变化：

后继方向：ai-1的后继由ai

(指针p)变为ai+1(指针p->next);p->prior->next=p->next;

前驱方向：ai+1的前驱由ai

(指针p)变为ai-1(指针p->prior);p->next->prior=p->prior;(2)双向链表的删除操作设p指向第i个元素，删除第i个元素ai-1

ai

ai+1

742.4静态链表静态链表：在数组中增加一个（或两个）指针域，这些指针域用来存放下一个（或上一个）数据元素在数组中的下标，从而构成用数组构造的单链表（或双链表）。静态链表中的指针又称仿真指针。75例1：一线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用静态链表如何表示？data1ZHAO3LI5QIAN6WU0ZHOU4SUN2…………0123456…1000cur说明1：假设S为SLinkList型变量，则S[MAXSIZE]为一个静态链表；S[0].next则表示第1个结点在数组中的位置。说明2：如果数组的第i个分量表示链表的第k个结点，则：S[i].data表示第k个结点的数据；S[i].next表示第k+1个结点(即k的直接后继)的位置。i头结点76说明3：静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。例如：在线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之间插入新元素LIU，可以这样实现：S[7].next=S[3].next；Step2:将QIAN的游标换为新元素LIU的下标：S[3].next=7Step1:将QIAN的游标值存入next的游标中：data……2SUN4ZHOU0WU6QIAN5LI3ZHAO101234561000curi头结点LIU67777例2：试用C或类C语言编写一高效算法，将一顺序存储的线性表（设元素均为整型量）中所有零元