第二章 线性表

1、1上堂课要点回顾上堂课要点回顾2若结构是非空有限集，则有且仅有一个开始结若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为：（可表示为：（a1 , a2 , , an） 线性结构的定义：3线性结构的特点：线性结构的特点：线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最典型、最常用的是-线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一

2、 的的见第2章4第第2章章 线性表线性表5（a1, a2, ai-1，ai, ai1 ，, an）2.1 线性表的类型定义线性表的类型定义 1. 线性表的定义：线性表的定义：n个数据元素的有限序列个数据元素的有限序列n=0时称为空表数据元素线性起点ai的直接前趋ai的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长线性终点6例例1 分析分析26 个英文字母组成的英文表个英文字母组成的英文表学号学号姓名姓名性别性别年龄年龄班级班级2001011810205于春梅于春梅女女 182001级电信级电信016班班2001

3、011810260何仕鹏何仕鹏男男 182001级电信级电信017班班2001011810284王王 爽爽女女 182001级通信级通信011班班2001011810360王亚武王亚武男男 182001级通信级通信012班班： ：例例2 分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母; 元素间关系是线性同一线性表中的元素必定具有相同同一线性表中的元素必定具有相同特性特性例如：例如：7练：判断下列叙述的正误：练：判断下列叙述的正误：82.线性表的类型定义线性表的类型定义（详见课本（详见课本P19）9358112689111

4、520Ep2-1lalb10Ep2-2Ep2-2LALA（3,5,8,113,5,8,11）和）和LB=LB=（2,6,8,9,11,15,202,6,8,9,11,15,20）；）；35811268911 15 2023568891111 15 20归并：归并：112.2 线性表的顺序表示和实现线性表的顺序表示和实现2.2.1 顺序表的表示2.2.2 顺序表的实现2.2.3 顺序表的运算效率分析122.2.1 顺序表的表示顺序表的表示线性表的顺序表示又称为顺序存储结构或顺序映像。线性表的顺序表示又称为顺序存储结构或顺序映像。线线性表顺顺序存储储特点：1. 逻辑上相邻的数据元素，其物理上也相邻

5、；逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元素若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（存放位置亦可求出（利用数组下标利用数组下标）。）。设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称称为首地址为首地址），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为： LOC(ai) = LOC(a1) + L *（i-1） LOC(ai+1) = LOC(ai)+L 13线性表的顺序存储结构示意图线性表的顺序存储结构示意图a

6、a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L Lb +(max-1)+(max-1)L L14113例例1因此：LOC( M3 ) = 98 + 5 (3-0) =113解：地址计算通式为：解：地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）由于第一个元素的位置是0，所以公式变成：LOC(ai) = LOC(a1) + L *（i-0）15顺序存储方法

7、： 由于高级程序设计语言中的数组类型也有随机存由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。顺序存储结构。 在此，由于线性表的长度可变，且所需最大存储在此，由于线性表的长度可变，且所需最大存储空间随问题的不同而不同，在空间随问题的不同而不同，在C语言中可用动态分配的语言中可用动态分配的一维数组。一维数组。16#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10typedef structElemType *elem;Int length;Int

8、 listsize;sqList;/线性表存储空间的初始分配量/线性表存储空间的分配增量/存储空间的基址/当前长度/当前分配的存储容量以（sizeof(ElemType)为单位）线性表的动态分配顺序存储结构线性表的动态分配顺序存储结构通过通过sqList定义变量：定义变量：sqList sq;访问此变量中的成员：访问此变量中的成员：sq.elem sq.length sq.listsize17Status InitList_Sq(SqList &L) / 算法算法2.3 / 构造一个空的线性表构造一个空的线性表L。 L.elem =(ElemType*)malloc(LIST_INIT

9、_SIZE*sizeof(ElemType); if (!L.elem) exit(OVERFLOW); / 存储分配失败存储分配失败 L.length = 0; / 空表长度为空表长度为0 L.listsize = LIST_INIT_SIZE; / 初始存储容量初始存储容量 return OK; / InitList_Sq初始化函数：初始化函数：182.2.2 顺序表的实现（或操作）顺序表的实现（或操作）回忆：数据结构基本运算操作有： 修改、插入、删除、查找、排序修改 通过数组的下标便可访问某个特定元素并修改之。核心语句: Vi=x;显然，顺序表修改操作的时间效率是T(n)=O(1)192

10、)插入 在线性表的第i个位置前插入一个元素实现步骤：(n为表长） 将第n至第i 位的元素向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。注意：事先应判断: 插入位置i 是否合法?表是否已满? 应当有1in+1 或 i=1,n+1for (p=&(L.elemn-1);p=q;-p)for (p=&(L.elemn-1);p=q;-p)* *(p+1)=(p+1)=* *p;p;* *q=e; q=e; +n;+n;/ / 元素后移一个位置元素后移一个位置/ / 插入插入e e / / 表长加表长加1 1 核心语句：1235678q20在线性表的第i个位置前插入一个

11、元素的示意图如下：121321242830427712132124252830427712345678123456789插入25213)删除 删除线性表的第i个位置上的元素P=&L.elemi-1;P=&L.elemi-1;for (p+;p=q;+p)for (p+;plength+1,e); scanf(%d,&e); (1)输入数据262求线性表长度求线性表长度Getlen(L)的实现的实现 求线性表的长度算法如下：求线性表的长度算法如下： int Getlen(sqList L) return L.length; 该算法的时间复杂度为该算法的时间复杂度为O(1)

12、3按序号取元素按序号取元素Getelem(L, i , &e)的实现的实现ElemType Getelem(sqLlist L,int I,ElemType e) if(iL.length) return ERROR; return L.datai-1;27 4查找运算locateElem(L,e)的实现查找操作的具体实现算法如下：int Locate(sqList L,ElemType e) int i; i=0;while(iL.length & L.datai!=e) i+;if(idata=a; p-next=q; 方式3：先让指针变量p指向该结点的首地址，然后用： (

13、*p).data=a； (*p).nextq45设p为指向链表的第i个元素的指针,则第i个元素的数据域写为 ，指针域写为 。练习：p-dataai的值p-nextai+1的地址46补充：结构类型的补充：结构类型的C语言表示法语言表示法问1：自定义结构类型变量test的长度m是多少？问2：结构变量test的首地址(指针p）是多少？问3：怎样删除结构变量test？只能借助其指针删除！*nextdatatest，长度为m字节pmsizeof(test)p(Lnode *)malloc(m)free(p)47Typedef struct Lnode ElemType data; /数据域 struct

14、 Lnode *next; /指针域Lnode, *LinkList; / LinkList为Lnode 类型的指针类型别名n线性表的单链表存储结构：482.3.2 链表的实现链表的实现491. 1. 单链表的建立和输出单链表的建立和输出难点分析：每个数据元素在内存中是“零散”存放的，其首地址怎么找？又怎么一一链接？实现思路：先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将地址送给前面的指针。50void CreateList_L(LinkList &L, int n) / 算法2.11 / 逆位序输入（随机产生）n个元素的值，建立带表头结点的单链线性表L L = (L

15、inkList)malloc(sizeof(LNode); L-next = NULL; / 先建立一个带头结点的单链表 for (i=n; i0; -i) p = (LinkList)malloc(sizeof(LNode); / 生成新结点 scanf(&p-data); /输入元素 p-next = L-next; L-next = p; / 插入到表头 / CreateList_L512. 2. 单链表的修改单链表的修改( (或读取）或读取）难点：难点：单链表中想取得第单链表中想取得第i个元素，必须从头指针出个元素，必须从头指针出 发寻找（顺藤摸瓜），不能随机存取发寻找（顺藤摸

16、瓜），不能随机存取 。核心语句：核心语句：Status GetElem_L(LinkList L, int i, ElemType &e) / L为带头结点的单链表的头指针为带头结点的单链表的头指针 P=L-next; j=1; while( p &j next; +j; if( !p | j i) return ERROR; p-data = e; return OK;52 算法 2.8的基本操作时比较j和i后并后移指p,while循环体中的语句频度与被查元素在表中位置有关，若1in,则频度为i-1,否则频度为n，因此算法2.8的时间复杂度为o(n).533. 3. 单链表的

17、插入单链表的插入在链表中插入一个元素的示意图如下：xsbapabp插入步骤（即核心语句）：Step 1：s-next=p-next;Step 2：p-next=s ；p-nexts-next思考：步骤1和2能互换么？元素x结点应预先生成：S=(Lnode *)malloc(m);S-data=x;S-next=p-nextp-next=s ；544. 4. 单链表的删除单链表的删除在链表中删除某元素的示意图如下：cabp删除步骤（即核心语句）：q = p-next; /保存b的指针，靠它才能指向cp-next=q-next; /a、c两结点相连free(q) ； /删除b结点，彻底释放p-ne

18、xt思考： 省略free(q)语句行不行？(p-next) - next555.5.应用举例：两个链表的归并（教材应用举例：两个链表的归并（教材P31P31）算法要求：已知：线性表 A、B，分别由单链表 LA , LB 存储，其中数据元素按值非递减有序排列要求：将 A ，B 归并为一个新的线性表LC , C 的数据元素仍按值非递减排列 。设线性表 C 由单链表 LC 存储。假设： A=（3，5，8，11），B=（2，6，8，9，11）预测： 合并后 C =（ 2 , 3 , 5 , 6 , 8 , 8 , 9 , 11，11 ）56算法分析：算法分析：算法主要包括：搜索、比较、插入三个操作：搜

19、索：需要两个指针搜索两个链表；比较：比较结点数据域中数据的大小；插入：将两个结点中数据小的结点插入新链表。La3 5 8 Lb2 6 8 13 11 PaPbPa、Pb用于搜索La和Lb， Pc指向新链表当前结点LcpcpcPbpcPapcPapcPbpcPa=NULL58算法实现：算法实现： Void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) /按值排序的单链表LA,LB，归并为LC后也按值排序 free(Lb); /释放Lb的头结点 /MergeList_L pc-next = pa?pa:pb ; /插

20、入剩余段 while(pa&pb) /将pa 、pb结点按大小依次插入C中 if(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next pa=La-next; pb=Lb-next; Lc=pc=La； /初始化 596. 6. 其它链表形式其它链表形式答：能。只要定义一个结构类型（含数据域和指示域）数组，就可以完全描述链表，这种链表称为静态链表。注：数据域含义与前面相同，指示域相当于前面的指针域。讨论1： 用一维数组也能存放链表吗？怎样实现？静态链表的插入与删除操作与普通链表一样，

21、不需要移动元素，只需修改指示器就可以了。具体实现过程见教材P31-34。601Zhao2Qian3Sun4Li5Zhou 6Wu7Zheng8Wang01Zhao2Qian3Sun4Li9Zhou 6Wu7Zheng8Wang0shi501234567891001234567891061讨论讨论2 2： 链表能不能首尾相连？怎样实现？链表能不能首尾相连？怎样实现？答：能。只要将表中最后一个结点的指针域指向头结点即可 (P-next=head;) 。这种形成环路的链表称为循环链表。特别：带头结点的空循环链表样式参见教材P35 1、从任一结点出发均可找到表中其他结点。、从任一结点出发均可找到表中其他结点。 2、操作仅有、操作仅有 一一 点与单链表不同：点与单链表不同：循环条件循环条件单链表单链表 - p = NULL 或或 p -next =NULL 循环链表循环链表- p= head 或或 p-next = headHH62讨论讨论3 3： 单链表只能查找结点的直接后继，能不单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？能查找直接前驱？如何实现？答：能。只要把单链表再多开一个指针域即可(例如用*next和*prior;) 。双向链表在非线性结构（如树结构）中将大量使用。prior datanext这种有两个指针