第2章顺序表1学生

第2章线性表

【教学重点】顺序结构，链式结构，基本操作

【教学难点】链式结构，双向链表，应用举例

【课外作业】选择，判断，填空，分析，设计

【上机实践】验证，分析，设计，编程，运行

【删除内容】静态线性表不予讲授，内容过时第2章讲解内容2.1线性表的类型定义2.2顺序表的表示和实现

2.3链式表的表示和实现

2.4线性表的应用举例

本章小结——习题课

2.1线性表的类型定义2.1.1线性表的基本概念一、线性结构特点

数据元素之间一对一关系，而且：

(1)集合中必然存在一个唯一的“第一元素”。(2)集合中必然存在一个唯一的“最后元素”。(3)除最后元素外，均有一个唯一的“后继”。(4)除第一元素外，均有一个唯一的“前驱”。

2.1线性表的类型定义

再次指出，数据元素只是一个抽象符号，可以代表各种各样的事物，随具体问题而定。例如，一个数据元素可以代表一个学生、一个公交站点、一个城市、一个棋盘布局。

单值元素：一个数据元素只有一个数据项。

举例：大写英文字母{A，B，C，D，E，…，Z}

多值元素：一个数据元素包含多个数据项。

举例：“学生信息”表中的数据元素。2.1线性表的类型定义二、线性表的定义

线性表举例（线性表为圆括号，集合为花括号）：【实例1】大写英文字母：(A，B，C，…，X，Y，Z)【实例2】有限整数数列：(11，13，15，17，19，21)【实例2】扑克牌的点数：(2，3，…，10，J，Q，K，A)【实例4】每年中的月份：(1,2,3,4,5,6,7,8,9,10,11,12)【实例5】学生基本信息：(s1，s2，s3，s4，s5，s6，s7，s8)【实例6】十六进制数码：(0，1,…,9，A，B，C，D，E，F)2.1线性表的类型定义

线性表(LinearList)：

n(n≥0)个特性相同的数据元素的有限序列。n为线性表的长度，当n=0时，为空表。当n>0时，线性表记作：

(a1，a2，…，ai-1，ai，ai+1，…，an)

①特性相同：n个数据元素属于同一个数据对象，代表同一类事物；

②有限：所有数据元素构成一个有限集合；

③有序：相邻的数据元素构成有序对（序偶关系）。2.1线性表的类型定义

下标编号：下标为数据元素的序号，编号从1开始，a1为第一个数据元素(首结点)，an为最后一个数据元素(尾结点)，ai为第i个数据元素，中间结点。

直接后继(简称后继)：从前向后，a1的后继是a2，a2的后继是a3，…，an没有后继。一般情况：ai的后继是ai+1(1≤i≤n-1)。

直接前驱(简称前驱)：从后先前，an的前驱是an-1，an-1的直接前驱是an-2，…，a1没有前驱。一般：ai的前驱是ai-1(2≤i≤n)。2.1线性表的类型定义2.1.2线性表的逻辑结构

线性表逻辑结构的描述：D={a1，a2,...,an}枚举法R1={<a1,a2>，<a2,a3>，…，<an-1,an>}枚举法或者D={ai|ai∈ElemSet，i=1,2,…,n，n≥0}描述法R1={<ai-1,ai>|ai-1,ai∈D，i=1,2,…,n}描述法

ElemSet代表一般数据元素的集合，根据实际问题，代表不同的集合。2.1线性表的类型定义线性表的抽象数据类型：ADTList{数学模型：线性表的逻辑结构描述

基本操作：12个基本操作（函数名称）}ADTList或者ADTList{数据对象：D={ai|ai∈ElemSet，i=1,2,…,n，n≥0}

数据关系：R1={<ai-1,ai>|ai-1,ai∈D，i=1,2,…,n}

基本操作：12个基本操作（讲解10个）}ADTList2.1线性表的类型定义2.1.3线性表的基本操作12个基本操作，讲授10个：①构建线性表：StatusInitList(SqList&L)

初始条件：无

操作结果：构建一个空的线性表L。②遍历元素：StatusListTraverse(SqListL)

初始条件：线性表L已经存在。

操作结果：逐个输出数据元素。③销毁线性表：StatusDestroyList(SqList&L)

初始条件：线性表L已经存在。

操作结果：销毁线性表L，释放线性表占用的内存空间。2.1线性表的类型定义④清空线性表：StatusClearList(SqList&L)

初始条件：线性表L已经存在。

操作结果：将线性表L置空，线性表长度n=0。⑤线性表判空：StatusListEmpty(SqListL)

初始条件：线性表L已经存在。

操作结果：L为空(n=0)，函数返回TRUE，否则FALSE。⑥求取长度：intListLength(SqListL)

初始条件：线性表L已经存在。

操作结果：函数返回线性表L中的数据元素个数。2.1线性表的类型定义⑦获取元素：StatusGetElem(SqListL,inti,ElemType&e)

初始条件：线性表L已经存在，且非空。

操作结果：给定元素位置i，得到第i个数据元素的值。⑧定位元素：intLocateElem(SqListL,ElemTypee)

初始条件：线性表L已经存在，且非空。

操作结果：给定数据元素的值，返回元素的位序。⑨插入元素：StatusListInsert(SqList&L,inti,ElemTypee)

初始条件：线性表L已经存在。

操作结果：在第i个位置，插入数据元素e，L长度加1。⑩删除元素：StatusListDelete(SqList&L,inti,ElemType&e)

初始条件：线性表L已经存在，且非空。

操作结果：删除第i个位置的数据元素，L长度减1。2.2线性表的顺序表示和实现

2.2.1线性表的机内表示

逻辑结构：数据结构的书面表达形式，两层含义：数据元素取值的集合，数据元素之间的逻辑关系（相邻关系）。

物理结构：逻辑结构的机内表示，又称存储结构，或逻辑结构的机内映像。

书面表示：逻辑结构——数据元素(元素取值，逻辑相邻)

机内表示：物理结构——

结点(存储内容，地址相邻)

物理结构需要表达两层含义：

（1）数据元素取值的机内存储；

（2）元素相邻关系的机内表示。2.2线性表的顺序表示和实现

数据元素存放在地址连续的存储单元，逻辑相邻的数据元素在存储器中的物理位置也相邻，用存储单元的物理位置来表示数据元素之间的相邻关系。逻辑相邻与物理相邻一致，物理位置体现数据元素之间的相邻关系。

线性表的这种机内表示称为线性表的顺序存储结构或顺序映像，通常称为线性表的顺序表。2.2线性表的顺序表示和实现

假设一个数据元素占用l个存储单元，l中的第1个存储单元作为数据元素的存储位置。

第1个数据元素a1的存储地址——LOC(a1)

（基地址）

第2个数据元素a2的存储地址——LOC(a2)+

l

第i个数据元素ai的存储地址——LOC(ai)+(i-1)×l

第n个数据元素an的存储地址——LOC(a1)+(n-1)×l2.2线性表的顺序表示和实现

要点小结：

（1）通常用一维数组存储线性表的数据元素，C/C++数组下标从0开始，数据元素的编号从1开始。第i个数据元素的数组下标维(i-1)

。

（2）基址Loc(a1)加上一个常数，得到其它数据元素的存储地址，因此可以随机存取线性表中的任意数据元素。

（3）问题规模不同，所需存储空间也不同，因此要求线性表的长度可变。在C语言中，用动态分配的一维数组来实现。2.2线性表的顺序表示和实现存储结构定义：

typedefstruct{ElemType*elem;//指针变量，指向基址intlength;//当前数据元素个数intlistsize;//当前存储空间大小}SqList;//SqList为类型名，不是变量名

ElemType泛指一般数据类型，应用程序中确定具体的数据类型，如int、char等。

Elem为ElemType类型的指针，指向线性表的基址，通过基址随机存取数据元素。

2.2线性表的顺序表示和实现

2.2.2线性表的操作实现

一、构建顺序表（算法2.3）

算法思想：

①动态分配一个数组空间，数组大小预先定义。

②内存分配成功，指针变量elem指向顺序表的基址；内存分配失败，elem值为NULL，结束程序运行。

③当前表长设为0，当前存储空间大小设为LIST_INIT_SIZE。2.2线性表的顺序表示和实现算法描述：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10StatusInitList(SqList&L)//引用类型，双向传递{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//分配失败，结束程序

L.length=0;//空表，表长为0L.listsize=LIST_INIT_SIZE;//初始存储容量

returnOK;}//InitList

2.2线性表的顺序表示和实现算法分析：O(1)

，没有循环

语法复习：引用类型参数双向传递，内存分配函数；C语言中的运算符sizeof，用来计算变量或类型所占用的内存字节数。exit函数用来结束程序运行。voidmain(){SqListL;InitList(L);}

InitList(SqList&L)//虚实结合，双向传递，L双向赋值，返回主函数2.2线性表的顺序表示和实现二、遍历数据元素

从第1个元素开始，依次显示输出所有数据元素。为简明起见，未按教材编写算法。voidListTraverse(SqListL)//单向传递{for(i=1;i<=L.length;i++)//i为数据元素编号printf(L.elem[i-1]);//或printf(L.elem+i-1);}

算法分析：O(n)

问题规模为当前表长L.length，即当前表长n；只有一层循环，执行n次。2.2线性表的顺序表示和实现三、求取表长

intListLength(SqListL)//单向传递，访问，不修改{returnL.length;}//时间复杂度：O(1)四、清空顺序表

StatusClearList(SqList&L)//双向传递，线性表改变

{L.length=0;returnOK;}//时间复杂度：O(1)五、顺序表判空

StatusListEmpty(SqListL)//单向传递{returnL.length==0?TRUE:FALSE;}

时间复杂度：O(1)2.2线性表的顺序表示和实现六、销毁顺序表

清空线性表：线性表中没有数据元素，长度为0，还可以再插入数据元素。

销毁线性表：线性表已经不存在，无法访问线性表，不能插入数据元素。

StatusDestroyList(SqList&L)//双向传，线性表改变{free(L.elem);returnOK;}

算法分析：O(1)

【课堂演示1-顺序表简单操作，插入操作先用后讲】2.2线性表的顺序表示和实现七、插入数据元素（算法2.4）

假设，插入一个数据元素e，为了保证逻辑结构和物理结构一致，在第i个位置插入，要求1≤i≤n+1。1≤i≤n：需要移动数据元素插入前：(a1，a2，…，ai-1，ai，…，an)插入后：(a1，a2，…，ai-1，e，ai，…，an)i＝n+1：无需移动数据元素插入前：(a1，a2，…，ai-1，ai，…，an)插入后：(a1，a2，…，ai-1，ai，…，an，e)2.2线性表的顺序表示和实现

2.2线性表的顺序表示和实现算法思想：

（1）检查插入位置：在第i个位置插入，1≤i≤n+1，否则i值不合法，返回ERROR。

（2）检查存储空间：存储空间够用，执行后面操作，如果不够用，则增加存储空间。

（3）移动数据元素：依次后移数据元素an，an-1，…，ai，在第i个位置插入，移动数据元素个数为(n-i+1)。

（4）插入数据元素：执行数据元素的赋值操作，将插入的数据元素放在第i个位置。

（5）增加表的长度：插入成功，表长加1，返回OK。2.2线性表的顺序表示和实现

确切说法：在第i个位置插入，1≤i≤n+1。

模糊说法：在第i个位置之前插入。说法不妥原因：

（1）在第n+1个位置插入，为第n个位置之后。（2）插入后才是“之前”，插入前是“第i个位置”。

数据元素的访问：

【课堂演示2-顺序表插入操作】2.2线性表的顺序表示和实现算法描述：不判断存储空间

StatusListInsert(SqList&L,inti,ElemTypee)//算法2.4{ElemType*p,*q;//辅助变量，算法描述可以省略

if(i<1||i>L.length+1)returnERROR;//i值是否合法

//此处为if语句，判断当前存储空间是否已满q=L.elem+i-1;//指针变量q为插入位置for(p=L.elem+L.length-1;p>=q;--p)*(p+1)=*p;//右移或后移数据元素*q=e;++L.length;//插入e，表长增1returnOK;

}//ListInsert2.2线性表的顺序表示和实现判断存储空间程序代码：if(L.length>=L.listsize)//当前存储空间是否已满

{newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType))if(!newbase)exit(OVERFLOW);//分配失败，程序结束L.elem=newbase;//新基址L.listsize=L.listsize+LISTINCREMENT;//增加存储容量}2.2线性表的顺序表示和实现

算法量级估算：

算法执行时间主要是移动数据元素，函数中有一个循环，用来移动数据元素。因此时间复杂度T(n)=O(n)。

最坏情况分析：

最好情况，在第n+1个位置插入，移动0个数据元素，执行0次基本操作；最坏情况，在第1个位置插入，移动n个数据元素，执行n次基本操作。时间复杂度均按最坏情况考虑，间复杂度T(n)=O(n)。2.2线性表的顺序表示和实现平均移动次数：

移动次数之和：0+1+2，…，+n-1+n=n(n+1)/2

两端项相加为n，项数(n+1)/2

假定每个位置的插入概率相等，n+1个插入位置：pi=1/(n+1)

每个位置平均移动次数（数学期望值expectedvalue）：

Eins=pi

×n(n+1)/2=n/2

时间复杂度T(n)=O(n)

2.2线性表的顺序表示和实现八、删除数据元素（算法2.5）

为了保证逻辑结构和物理结构一致，删除第i个位置的数据元素ai，需要依次移动第i个位置后面的数据元素。

删除前：(a1，a2，…，ai-1，ai，…，an)

删除后：(a1，a2，…，ai-1，ai+1，…，an)算法思想：

（1）检查删除位置：第i个位置1≤i≤n；

（2）移动数据元素：第i个位置，移动次数（n-i）；

（3）减小表的长度：删除成功，表长减1。

2.2线性表的顺序表示和实现算法描述：StatusListDelete(SqList&L,inti,ElemType&e)//算法2.5{ElemType*p,*q;//算法描述中可以省略if(i<1||i>L.length)returnERROR;p=L.elem+i-1;//p为删除位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p)//左移*(p-1)=*p;L.length--;//表长减1retu