数据结构(c语言版)-严蔚敏版-第2章-线性表-信大(第2讲)

绪论要点回顾数据结构定义——指互相有关联的数据元素的集合，用D_S=(D,S)数据结构是相互之间存在着一种或多种特定关系的数据元素的集合。数据结构内容——数据的逻辑结构、存储结构和运算

算法效率指标——时间效率和空间效率数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构近期

上课

内容第2章线性表第3章栈和队列第4章串第5章数组和广义表

线性结构(逻辑、存储和运算)

若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：(a1,a2,……,an)线性结构的定义：线性结构的特点：①只有一个首结点和尾结点；②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是------简言之，线性结构反映结点间的逻辑关系是一对一

的第二章线性表第2章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现图2.1线性表的逻辑结构2.1线性表的类型定义2.1.1线性表的逻辑结构（a1,a2,…ai-1，ai,ai＋1

，…,an）线性表的定义：是n个数据元素的有限序列n=0时称为数据元素表头ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表表尾例1分析26个英文字母组成的英文表

（A,B,C,D,……,Z）例2分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性同一线性表中的元素必定具有相同特性

线性表的特点可概括如下：同一性有穷性有序性

线性表是最常见的数据结构，因为矩阵、数组、字符串、堆栈、队列等都符合线性条件。练：判断下列叙述的正误：1.数据的逻辑结构是指数据元素之间的逻辑关系，是用户按使用需要建立的。2.线性表的逻辑结构定义是唯一的，不依赖于计算机。3.数据结构是指相互之间存在一种或多种关系的数据元素的全体。4.线性结构反映结点间的逻辑关系是一对一的。5.一维向量是线性表，但二维或N维数组不是。6.“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。√×√√××例2-1两个集合La和Lb的合并假设两个集合La{7,2,3}Lb{8,4,5,6}怎样将他们合并呢？1，首先知道La的长度是3和Lb的长度是42，之后把Lb集合中的元素依次和La中的元素进行比对形成一个循环，首先Lb中的8与La的元素依次比对，8与所有La中元素不同，将8插入La中，3，2与2相同进入Lb的下一个元素，都不相同，之后将元素合并到La中，例2-2两个非递减有序的线性表La和Lb的合并

如La{2,4,6}Lb{4,7,9,10}合并1，定义Lc,长度是La长度+Lb长度2，La中2与Lb中4，把小La中的2的插入Lc，La进入下一个元素3,La中4与Lb中4比较，把La的4插入Lc,LaLb都下一个元素4,La中6与Lb中7比较，把小的La中的6的插入Lc，La进入下一个元素，无元素了5，就将Lb中剩余元素依次加入Lc中LaLbLc2.2线性表的顺序表示和实现2.2.1线性表的顺序存储结构用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。顺序存储定义：顺序存储方法：简言之，逻辑上相邻，物理上也相邻线性表顺序存储特点：1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是：设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：

LOC(ai)=LOC(a1)+L*(i-1)LOC(ai+1)=LOC(ai)+L它是一种随机存取的数据结构。

注意：C语言中的数组的下标从0开始，即：V[n]的有效范围是V[0]～V[n-1]线性表的顺序存储结构示意图

地址内容元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)L一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是98，则Ｍ[３]的第一个字节的地址是

113例1因此：LOC(M[3])=98+5×(3-0)=113解：地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）用数组V来存放26个英文字母组成的线性表(a，b，c，…，z)，写出在顺序结构上生成和显示该表的C语言程序。

voidbuild()/*字母线性表的生成，即建表操作*/{inti;V[0]='a';for(i=1;i<=n-1;i++)

V[i]=V[i-1]+1;

}核心语句：法1V[i]=V[i-1]+1;法2V[i]=’a’+i;法3V[i]=97+i;例2voidbuild();voiddisplay();#define n26intV[n];voidmain(void)/*主函数，字母线性表的生成和输出*/{

build();

display();}voiddisplay()/*字母线性表的显示，即读表操作*/{inti;for(i=0;i<=n-1;i++)printf("%c",V[i]);printf("\n");}执行结果：abcdefghijklmnopqrstuvwxyz26个字母另一种写法#include<stdio.h>intmain(){ inti; for(i=0;i<26;i++) if(i%2==0) printf("%c",'A'+i); else printf("%c",'a'+i); printf("\n"); return0;}2.2.2线性表顺序存储结构上的基本运算回忆：数据结构基本运算操作有：

修改、插入、删除、查找、排序1.修改操作

通过数组的下标便可访问某个特定元素并修改之。核心语句:

V[i]=x;显然，顺序表修改操作的时间效率是T(n)=O(1)2.存取操作在这种结构中容易实现随机存取第i个数据元素，C语言中数组的下标从0开始，所以ai应在L.elem[i-1]中存取。

3.插入操作在表的第i(1≤i≤n+1)个位置，插入一个新元素e，使长度为n的线性表(e1，…，ei-1，ei，…，en)变成长度为n+1的线性表（e1，…,ei-1，e，ei，…，en）。实现步骤：将第n至第i位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。注意：事先应判断:插入位置i是否合法?表是否已满?长度为n的线性表变为长度为n+1的线性表（a1,a2,…,ai-1,ai,…,an）（a1,a2,…,ai-1,x,ai,…,an）

例如：已知线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”，则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，如图2.3所示。请注意区分元素的序号和数组的下标。图2.3顺序表中插入元素

插入元素时，时间主要耗费在移动元素上。移动个数取决于插入位置。for(j=n;j>=i;j--)a[j+1]=a[j];a[i]=x;n++;//元素后移一个位置//插入x//表长加1

4.删除操作指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表(e1，…,ei-1，ei，ei+1，…，en)变成长度为n-1的线性表(e1，…,ei-1，ei+1，…，en)。

实现步骤：将第i+1至第n位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i是否合法?图2.4顺序表中删除元素例如：线性表(4,9,15,21,28,30,30,42,51,62)删除第5个元素，则需将第6个元素到第10个元素依次向前移动一个位置，如图2.4所示。for(j=i+1;j<=n;j++)a[j-1]=a[j];n--;//元素前移一个位置//表长减1核心语句：线性表顺序表示的优点是：(1）无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）；(2）可方便地随机存取表中的任一元素。其缺点是：（1）插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低;（2）预分配空间（浪费）；（3）表的扩充不方便。

2.3线性表的链式表示和实现链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。如何实现？通过指针来实现注意：每个存储结点都包含两部分：

数据域和指针域例1画出26个英文字母表的链式存储结构。该字母表在内存的链式存放示意图如下：

解：该字母表的逻辑结构为：(a,b,…,y,z)aheadb/\z……各结点由两个域组成：数据域：存储元素数值数据；指针域：存储直接后继或者直接前驱的存储位置。指针数据指针数据指针或样式：与链式存储有关的术语：1、结点：数据元素的存储映像。由数据域和指针域两部分组成；2、链表：

n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3、单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。a1heada2an……head循环链表示意图：4、头指针、头结点和首元结点

示意图如下：头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点是指链表中存储线性表第一个数据元素a1的结点。特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外还需存储其直接后继的信息结点 数据域：元素本身信息指针域：指示直接后继的存储位置2.3.1单链表由于链表的每个结点只有一个指针域，故将这种链表又称为单链表。单链表中第一个结点无前趋，应设一个头指针H指向第一个结点。单链表中最后一个结点没有直接后继，则指定最后一个结点的指针域为“空”（NULL）。

整个链表的存取必须从头指针开始。

例如：图2.5所示为线性表（A,B,C,D,E,F,G）的单链表存储结构，整个链表的存取需从头指针开始进行，依次顺着每个结点的指针域找到线性表的各个元素。图2.5单链表的示例图图2.6单链表的逻辑状态图2.7带头结点单链表图示一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？例：答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31∴头指针的值是31上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①无头结点②有头结点答：讨论1.

在链表中设置头结点有什么好处？讨论2.

如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表。^头指针^头指针头结点无头结点有头结点讨论3.头结点的数据域内装的是什么？头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。答：讨论4.链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，所以要采用结构体数据类型。答：什么是结构类型？如何书写表达？——补充C语言内容

头结点的数据域H补充结构数据类型及其C语言表示法①类型定义和变量说明可以合写为：typedefstructCh{chardata;//定义数据域的变量名及其类型structCh*next;//定义指针域的变量名及其类型}test，*head;/*test是Ch结构类型的变量,*head是Ch结构类型的头指针*/以26个字母的链表为例，每个结点都有两个分量：假设每个结点用变量test表示，其中两个分量分别用data和*next表示，则：*nextdatatest补充：结构类型的C语言表示法②对于指向结构变量test首地址的指针，还可说明为：structtest*p,*q;(或用structCh*L；)//注：刚才已经定义了test为用户自定义的Ch类型③每个结点的分量如何表示？*nextdatatestp方式1：直接用test.data＝'a'；test.next=q方式2：先让指针变量p指向该结点的首地址，然后用：

p->data='a';p->next=q;方式3：先让指针变量p指向该结点的首地址，然后用：(*p).data='a'；(*p).next＝q单链表可以由头指针唯一确定。单链表的存储结构描述如下：typedef

struct

LNode

{

ElemType

data;struct

LNode

*next;}LNode

,*LinkList;/*LinkList为结构指针类型*/

假设L是LinkList型的变量，则L是一个结构指针，即单链表的头指针，它指向表中第一个结点。若L=NULL（对于带头结点的单链表为L->next=NULL），则表示单链表为一个空表，其长度为0。若不是空表，对于带头结点的单链表L，p=L->next指向表中的第一个结点a1，即p->data=a1，而p->next->data=a2。其余依此类推。1.查找算法描述：查找第i个结点，从头指针L出发，顺着链域扫描。用指针p指向当前扫描到的结点，用j做计数器，累计当前扫描过的结点数。当j==i时，指针p所指的结点就是要找的第i个结点。2.3.2单链表上的基本运算2.单链表插入操作算法描述：

要在第i个位置插入元素e，需要找到第i-1个结点并由指针p指示，然后申请一个新的结点并由指针s指示，其数据域的值为e。

修改第i-1个结点的指针使其指向s，使s结点的指针域指向原第i个结点。插入：s->next=p->next;

p->next=s;在链表中插入一个元素的示意图如下：xsbapabp插入步骤（即核心语句）：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next元素x结点应预先生成：s=(LinkList)malloc(m);s->data=x;s->next=p->next;p->next=s;3.删除在链表中删除某元素的示意图如下：cabp删除步骤（即核心语句）：q=p->next;//保存b的指针，靠它才能指向cp->next=q->next;//a、c两结点相连free(q)；//删除b结点，彻底释放p->next思考：省略free(q)语句行不行？(p->next)->next××4.建立单链表图2.10头插法建立单链表图示2）尾插法建表图2.11尾插法建表图示5.应用举例：两个链表的归并(教材P31)算法要求：已知：线性表A、B，分别由单链表LA,LB存储，其中数据元素按值非递减有序排列，要求：将A，B归并为一个新的线性表C,C的数据元素仍按值非递减排列。设线性表C由单链表LC存储。假设：A=(3，5，8，11)，B=(2，6，8，9，11)预测：合并后C=(2,3,5,6,8,8,9,11，11)用链表可表示为：3511/\8

La2611/\8

Lb92365

Lc8头结点算法分析：算法主要包括：搜索、比较、插入三个操作：搜索：需要两个指针搜索两个链表；比较：比较结点数据域中数据的大小；插入：将两个结点中数据小的结点插入新链表。La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

Pc指向新链表当前结点Lc

…

Pa3

PcPa5

Pc11^Pc2

PbPcPa思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表插到La表中，如何编程？2、要求不能有重复的数据元素，如何编程？6，其他形式的链表讨论1：用一维数组也能存放链表吗？怎样实现？答：能。只要定义一个结构类型(含数据域和指示域)数组，就可以完全描述链表，这种链表称为静态链表。注：数据域含义与前面相同，指示域相当于前面的指针域。静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。具体实现过程见教材P31-34。讨论2：链表能不能首尾相连？怎样实现？答：能。只要将表中最后一个结点的指针域指向头结点即可(P->next=head;)。这种形成环路的链表称为循环链表。特别：带头结点的空循环链表样式H参见教材P35

特点：

1、从任一结点出发均可找到表中其他结点。

2、操作仅有一点与单链表不同：循环条件单链表-----p=NULL或p->next=NULL循环链表-----p=head或p->next=head图2.13循环链表讨论3：单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？答：能。只要把单链表再多开一个指针域即可(例如用*next和*prior;)。双向链表在非线性结构(如树结构)中将大量使用。这种有两个指针的链表称为双向链表。其特点是可以双向查找表中结点。参见教材P35—39。特别：带头结点的空双向链表样式：图2.14双向链表的结点结构

由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。

设指针p指向双链表中某一结点，则有下式成立：p->prior->next=p=p->next->prior图2.15双向循环链表图示1.双向链表的前插操作图2.16双向链表插入操作2.双向链表的删除操作算法描述：图2.17双向链表的删除操作要点回顾链表的表示(包括有关术语、结构数据类型等)链表的实现(建表、输出、修改、插入、删除)