数据结构 课件 第2章 线性表(1定义及顺序表示)

2.1线性表的定义和操作2.2线性表的顺序表示1/472.3线性表的链式表示2.4有序表CONTENTS提纲第2章线性表线性表是一个具有相同特性的数据元素的有限序列。

2.1.1线性表的定义线性表中所含元素的个数叫做线性表的长度，用n表示，n≥0。n=0时，表示线性表是一个空表，即表中不包含任何元素。有穷性：数据元素个数是有限的。一致性：所有元素性质相同，即属于同一数据类型。序列性：数据元素由逻辑序号唯一确定。一个线性表中可以有相同值的元素。逻辑关系：元素之间为1对1的关系。2/472.1线性表的定义和操作(a1，a2，…，ai，ai+1，…，an)ai（1≤i≤n）表示第i（i表示逻辑位序）个元素。表头元素表尾元素(a1，a2，…，ai，ai+1，…，an)3/47线性表的逻辑表示为：

一个汽车线性表

一个小人线性表

不胜枚举4/47线性表是客观事物的抽象

初始化线性表InitList(&L)：构造一个空的线性表L。

销毁线性表DestroyList(&L)：释放线性表L占用的内存空间。

判线性表是否为空表ListEmpty(L)：若L为空表，则返回真，否则返回假。

求线性表的长度ListLength(L)：返回L中元素个数n。

线性表的9个基本运算如下:5/472.1.2线性表的基本操作

输出线性表DispList(L)：线性表L不为空时，顺序显示L中各结点的值域。

求线性表L中指定位置的某个数据元素GetElem(L，i，&e)：用e返回L中第i（1≤i≤n）个元素的值。

定位查找LocateElem(L，e)：返回L中第一个值域与e相等的逻辑位序。若这样的元素不存在，则返回值为0。

插入一个数据元素ListInsert(&L，i，e)：在L的第i（1≤i≤n）个元素之前插入新的元素e，L的长度增1。

删除数据元素ListDelete(&L，i，&e)：删除L的第i（1≤i≤n）个元素，并用e返回其值，L的长度减1。6/47ADTList{

数据对象：D={ai|1≤i≤n，n≥0，ai为ElemType类型}//ElemType是自定义类型标识符

数据关系：R={<ai，ai+1>|ai、ai+1∈D，i=1，…，n-1}

基本运算：9个运算}7/47线性表的抽象数据类型：数据基本运算1基本运算n…应用程序程序员可以直接使用它来存放数据作为存放数据的容器。程序员可以直接使用它的基本运算

完成更复杂的功能。线性表的作用实现了的线性表8/47示例一个整数线性表L=(1,3,1,4,2)ListLength(L)

返回5ListEmpty(L)

返回falseGetElem(L，3，e)

e=1LocateElem(L，1)

1ListInsert(L，4，5)L=(1,3,1,5,4,2)ListDelete(L，3)L=(1,3,5,4,2)9/47线性表的知识结构线性表的概念线性表的存储结构线性表的应用特殊的线性表—有序表顺序存储结构顺序表中基本运算的实现链式存储结构单链表单链表中基本运算的实现双链表双链表中基本运算的实现循环链表循环链表中基本运算的实现线性表ADT=

逻辑结构+运算定义（运算描述）10/47

线性表顺序存储结构：把线性表中的所有元素按照顺序存储方法进行存储。2.2.1顺序表的定义按逻辑顺序依次存储到存储器中一片连续的存储空间中。11/472.2线性表的顺序表示线性表(a1,a2,…,ai,…,an)直接映射a1a2…ai…an…nMaxSize-101i-1n-1datalength顺序表逻辑结构存储结构12/47typedefstruct{ElemTypedata[MaxSize];

intlength;}SqList; //顺序表类型其中data成员存放元素，length成员存放线性表的实际长度。顺序表类型声明：说明：注意逻辑位序和物理位序相差1。这里，假设ElemType为int类型13/47示例一个整数线性表L=(1,3,1,4,2)MaxSize-113142…5012datalength顺序表L34L.data[1]L.length14/47L->data[1]L->lengthMaxSize-113142…5012datalength顺序表指针L3415/47一个整数线性表L=(1,3,1,4,2)voidCreateList(SqList*&L，ElemTypea[]，intn)

//整体建立顺序表{inti=0,k=0;

L=(SqList*)malloc(sizeof(SqList));

while(i<n) //i扫描a中元素{L->data[k]=a[i];k++;i++; //k记录插入到L中的元素个数}

L->length=k;}1、建立顺序表a[0..n-1]

顺序表L─整体创建顺序表。传递顺序表指针16/472.2.2顺序表基本运算的实现顺序表？？？L1010

顺序表指针的含义顺序表的空间顺序表LSqList*L;L=(SqList*)malloc(sizeof(SqList));1010通过顺序表指针L操作顺序表17/47算法参数说明

顺序表指针引用voidCreateList(SqList*&L，ElemTypea[]，intn)引用参数：将执行结果回传给实参引用符号“&”放在形参L的前面。输出型参数均为使用“&”，不论参数值是否改变。引用参数SqList*&L

将顺序表地址L回传给对应的实参18/47voidCreateList(SqList*&L，ElemTypea[]，intn){inti=0,k=0;

L=(SqList*)malloc(sizeof(SqList));

while(i<n) //i扫描a中元素{L->data[k]=a[i];k++;i++; //k记录插入到L中的元素个数}

L->length=k;}voidmain(){SqList*h;intn=5;ElemTypea[]={1,3,1,4,2};

CreateList(h,a,n);

//对顺序表h进行其他操作}？？？h131425Lh指向有效顺序表，可以操作19/47如果使用引用：voidCreateList(SqList*L，ElemTypea[]，intn){inti=0,k=0;

L=(SqList*)malloc(sizeof(SqList));

while(i<n) //i扫描a中元素{L->data[k]=a[i];k++;i++; //k记录插入到L中的元素个数}

L->length=k;}为什么用顺序表指针引用如果不使用引用：voidmain(){SqList*h;intn=5;ElemTypea[]={1,3,1,4,2};

CreateList(h,a,n);

//对顺序表h进行其他操作}？？？h131425Lh仍然是垃圾值，操作错误20/47（1）初始化线性表InitList(L)

构造一个空的线性表L。实际上只需将length成员设置为0即可。

voidInitList(SqList*&L){L=(SqList*)malloc(sizeof(SqList));

//分配存放线性表的顺序表空间

L->length=0;}21/472、顺序表基本运算算法voidDestroyList(SqList*&L){

free(L);}（2）销毁线性表DestroyList(L)

释放线性表L占用的内存空间。Lfree(L)释放L所指向的空间顺序表顺序表采用指针传递，有两个优点：更清楚看到顺序表创建和销毁过程（malloc/free）；在算法的函数之间传递更加节省空间（在函数体内不必创建值形参即整个顺序表的副本）。22/47boolListEmpty(SqList*L){

return(L->length==0);}（3）判定是否为空表ListEmpty(L)

返回一个值表示L是否为空表。若L为空表，则返回true，否则返回false。23/47intListLength(SqList*L){

return(L->length);}（4）求线性表的长度ListLength(L)返回顺序表L的长度。实际上只需返回length成员的值即可。24/47（5）输出线性表DispList(L)

该运算当线性表L不为空时，顺序显示L中各元素的值。

voidDispList(SqList*L){for(inti=0;i<L->length;i++)printf("%d"，L->data[i]);printf("\n");}25/47boolGetElem(SqList*L，inti，ElemType&e){

if(i<1||i>L->length)

returnfalse;

e=L->data[i-1];

returntrue;}（6）求某个数据元素值GetElem(L，i，e)

该运算返回L中第i（1≤i≤ListLength(L)）个元素的值，存放在e中。体现顺序表的随机存取特性本算法的时间复杂度为O(1)。26/47intLocateElem(SqList*L，ElemTypee){inti=0;while(i<L->length&&L->data[i]!=e)

i++;

if(i>=L->length)return0;elsereturni+1;}（7）按元素值查找LocateElem(L，e)

顺序查找第1个值域与e相等的元素的逻辑位序。若这样的元素不存在，则返回值为0。27/47在顺序表L的第i（1≤i≤ListLength(L)+1）个位置上插入新的元素e。

01i-1n-1nia1a2…aiai+1…anei+1插入完成lengthnn+128/47（8）插入数据元素ListInsert(L，i，e)boolListInsert(SqList*&L，inti，ElemTypee){intj;

if(i<1||i>L->length+1||L->length==MaxSize)returnfalse; //参数错误时返回false

i--; //将顺序表逻辑序号转化为物理序号

for(j=L->length;j>i;j--) //将data[i..n]元素后移一个位置

L->data[j]=L->data[j-1];

L->data[i]=e; //插入元素e

L->length++; //顺序表长度增1

returntrue; //成功插入返回true}a1a2…ai…an…ai+1ian-1anai+1eai29/47

对于本算法来说，元素移动的次数不仅与表长L->length=n有关，而且与插入位置i有关：

算法最好时间复杂度为O(1)算法最坏时间复杂度为O(n)当i=1时，移动次数为n，达到最大值。当i=n+1时，移动次数为0；30/47该运算删除顺序表L的第i（1≤i≤ListLength(L)）个元素。

01i-1n-1ia1a2…ai+1…anaien-2an-1lengthnn-1删除完成31/47（9）删除数据元素ListDelete(L，i，e)boolListDelete(SqList*&L，inti，ElemType&e){intj;

if(i<1||i>L->length||L->length==0)

//参数错误时返回falsereturnfalse;

i--; //将顺序表逻辑序号转化为物理序号

e=L->data[i];

for(j=i;j<L->length-1;j++) //将data[i..n-1]元素前移

L->data[j]=L->data[j+1];

L->length--; //顺序表长度减1

returntrue; //成功删除返回true}a1a2…ai…an…ai+1ianai+1ai+232/47#include<stdio.h>#include<malloc.h>#defineMaxSize50typedefintElemType;typedefstruct{ElemTypedata[MaxSize]; //存放顺序表元素

intlength; //存放顺序表的长度}SqList; //顺序表的类型//包含前面的9个基本运算函数33/47将顺序表类型声明及其基本运算函数放在sqlist.cpp文件中：#include"sqlist.cpp" //包含顺序表基本运算算法voidmain(){SqList*L;printf("初始化L\n");InitList(L);printf("ListEmpty(L)=%d\n",ListEmpty(L));printf("L的位置1插入元素1\n");ListInsert(L,1,1);printf("L的位置2插入元素3\n");ListInsert(L,2,3);printf("L的位置3插入元素1\n");ListInsert(L,3,1);printf("L的位置4插入元素4\n");ListInsert(L,4,4);printf("L的位置5插入元素2\n");ListInsert(L,5,2);printf("L:");DispList(L);printf("ListLength(L)=%d\n",ListLength(L));printf("ListEmpty(L)=%d\n",ListEmpty(L));inte;GetElem(L,3,e);printf("L的第3个元素:%d\n",e);printf("第1个值为1的元素的逻辑序号:%d\n",LocateElem(L,1));printf("L的位置4插入元素5\n");ListInsert(L,4,5);printf("L:");DispList(L);printf("删除第3个元素\n");ListDelete(L,3,e);printf("L:");DispList(L);printf("销毁L\n");DestroyList(L);}34/47顺序表存储结构特征顺序表元素操作方式顺序表9个基本运算算法设计35/47

顺序表应用算法设计：数据采用顺序表存储，利用顺序表的基本操作来完成求解任务。36/473、顺序表的应用示例

【例2-1】假设一个线性表采用顺序表表示，设计一个算法，删除其中所有值等于a的元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)。37/47解法一：设删除L中所有值等于a元素后的顺序表为L1，显然L1包含在L中，为此L1重用L的空间。扫描顺序表L，重建L中只包含不等于a的元素，算法过程是置k=0（k用来记录新表中的元素个数），用i从左到右扫描L中所有的元素，当i指向的元素为a时跳过它；否则将其放置在k的位置，即L->data[k]=L->data[i],k++。01baaa删除所有x=a的元素（k记录保留的元素个数，初值=0）：2345k=3，L->length=k=3clength63删除完成dk=0k=1k=2k=3以整体建立顺序表算法为基础！38/47删除顺序表中所有值为x的元素（方法1）演示voiddelnode1(SqList*&L，charx){intk=0，i; //k记录值不等于x的元素个数

for(i=0;i<L->length;i++)if(L->data[i]!=x) //若当前元素不为x，将其插入A中

{L->data[k]=L->data[i];k++; //不等于x的元素增1

}

L->length=k;

//顺序表L的长度等于k}39/47对应的算法如下：

解法二：扫描顺序表L，用i从左到右扫描L中的所有元素，用k记录L中当前等于a的元素的个数，一边扫描L一边统计当前k的值，当i指向的元素为a时k增加1；否则将不为a的元素前移k个位置，即L->data[i-k]=L->data[i]。最后修改L的长度。算法如下：40/4701baada删除所有x=a的元素（k记录删除的元素个数，初值=0）2345k=0，前移0个位置ck=1k=1，前移1个位置k=2k=2，前移2个位置k=3顺序表长度=6-k=3length63删除完成41/47删除顺序表中所有值为x的元素（方法2）演示voiddelnode2(SqList*&L，charx){intk=0，i=0; //k记录值等于x的元素个数

while(i<L->length)

{if(L->data[i]==x) //当前元素值为x时k增1 k++;

else

//当前元素不为x时将其前移k个位置

L->data[i-k]=L->data[i];

i++;

}

L->length-=k; /顺序表L的长度递减k}42/47对应的算法如下：

【例2-2】设有一个整数顺序表L。设计一个算法，以第一个元素为分界线（基准），将所有小于等于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。x无序整数序列≤xx>x43/470812273145536476809pivotijpivot=L->data[0]（基准）j从后向前找≤pivot的元素i从前向后找>pivot的元素3两者交换31

0

2

3

3

5

7

4

6

844/47解法1voidpartition1(SqList*&L){inti=0