考研-数据结构

2.1

线性表的基本概念线性表特点：在数据元素的非空有限集存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素集合中的每个数据元素均只有一个素均只有一除第一个外前驱除最后一个外，集合中的每个数据个后继线性表是类型相同的元素有限序列，记作：（a1,

...,

ai

1,

ai,

ai+1,

„

,

an）2.1

线性表的基本概念设

A=（a1,

a2,

...

,

ai-1, ai

, ai+1,

…,

an）是一线性表

1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；2

在表中ai-1

领先于ai，ai

领先于ai+1，称ai-1

是ai的直接前趋，ai+1

是ai

的直接后继；3性表中，除第一个元素和最后一个元外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。线性表是一种线性数据结构；元素的个数n

称为表的长度，n=0时称为空表；ai

是表的第

i

个元素，称i

为数据元素ai

的序号，每个元素性表中的位置，仅取决于它的序号。可在表的任意位置进行 和删除操作。32.1

线性表的基本概念对线性表的ADT描述ADT

List

{数据对象：D

=

{

ai

|

ai

ElemSet,

i=1,

,n n≥0

}数据关系R1

=

{

<ai-1,

ai>

|

ai-1,ai

D,

i=2, ,n

}基本操作InitList

(&L)操作结果 构造一个空的线性表L。DetroyList

(&L)初始条件：线性表L已经存在。操作结果：销毁线性表L。}ADTList2.1

线性表的基本概念对线性表的基本操作初始化操作InitList(&L)功能：建立空的线性表L；销毁操作DetroyList(&L)空间；功能：回收为线性表L动态分配的置空操作ClearList(&L)功能：L中已存在，重新将其置成空表；判空操作ListEmpty(L)功能：判断线性表L是否为空表，若为空表返回TRUE，否则返回FALSE；求表长操作ListLength(L)功能：返回线性表L的表长；2.1

线性表的基本概念取元素操作：Ge em

(

L,

i,

&e)功能：将线性表L中第i个元素赋值给e；查找操作LocateElem(L,

e,compare())功能： 性表

L

中查找与元素e

满足compare()的第

1个元素，返回该元素在表中的序号（或位置），若表中不存在这样的元素，则返回0；查找前驱PriorElem(L,cur_e,&pre_e)功能：若cur_e是

L 中的数据元素且不是第一个，则用pre_e返回它的前驱，否则失败，pre_e无定义。2.1

线性表的基本概念查找后继

Nex em

( L,

cur_e,

&next_e

)功能：若cur_e是L中的数据元素且不是最后一个，则用next_e返回它的后继，否则失败，next_e无定义。操作ListInsert(&L,i,e)功能：

性表L的第i个元

前

1个新元素e；删除操作

ListDelete( &L,i,

&e

)功能：删除线性表L的第i个元素，并用e返回；遍历操作

ListTraverse

(

L,visit(

)

)功能：依次对线性表L的每个元素调用函数visit()。若visit()失败，则返回ERROR，否则返回OK；2.1

线性表的基本概念说明基本操作是一种数据结构中最常见的操作它具有明确的逻辑意义。可以将基本操作看成一个整体，使用基本操作来解决新的问题，设计新的算法。使可以在高的层次上进行抽象，在更高的基础上进行设计。3、在算法的程序实现的过程中，基本操作需要通过编制公共函数进行具体实现。可以为基本操作建立公共函数库。2.1

线性表的基本概念利用基本操作进行算法设计例1：若有两个集合A

和B

分别用两个线性表LA和LB

表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合：A＝A∪B。问题分析上述问题可以演绎为：扩大线性表LA，将存在于线性表LB

中而不存在于线性表

LA

中的数据元素到线性表LA

中去。92.1

线性表的基本概念利用基本操作进行算法设计Ge em(

LB,

i

)

→

eLocateElem

(

LA,

e,

equal(

)

)ListInsert

(

LA,

n+1,

e

)2.1

线性表的基本概念利用基本操作进行算法设计void

union

(

List

&La, List

Lb)La_len=ListLength

(La);

//求线性表的长度Lb_len

=

ListLength

(Lb);for

(i

=

1; i

<=

Lb_len; i++

)

{;

//取Lb中第i个数据元素赋给eif

(

!

equal(

)

)//

La中不存在和

e

相同的数据元素，则

之}//

union2.1

线性表的基本概念例2-1：已知一个非纯集合B

试构造一个纯集合

A使

A B

中所有值各不相同的数据元素。问题分析：采用线性表表示集合算法策略：从集合B

取出物件放入集合A。要求集合A

中同样的物件不能有两件以上。2.1

线性表的基本概念利用基本操作进行算法设计void

union

(

List

&La, List

Lb

)La_len=ListLength

(La); Lb_len=ListLength

(Lb);for

(i

=

1; i

<=

Lb_len; i++

)

{;

//取Lb中第i个数据元素赋给eif

(

!

equal(

)

)//

La中不存在和

e

相同的数据元素，则

之}//

union2.1

线性表的基本概念例2-2：已知一个非纯集合B

试构造一个纯集合

A使

A B

中所有值各不相同的数据元素。问题分析：采用有序表表示集合有序表：若线性表中的数据元素相互之间可以比较，并且数据元素

性表中依值非递减或非递增有序排列，即：ai≥ai-1或

ai≤ai-1

(i=2,3,„,n)则称该线性表为有序表(Ordered

List)。2.1

线性表的基本概念例如：（2，3，3，5，6，6，6，8

12）对集合B

而言，。值相同的数据元素必定相邻；对集合A

而言，数据元素依值从小至大的顺序因此，数据结构改变了，解决问题的策略也要相应进行改变。2.1

线性表的基本概念利用基本操作进行算法设计for

(i

=

1; i

<=

Lb_len; i++

)

{Ge em(Lb,i,e);//取Lb中第i个数据元素赋给eif()

{||ListInsert

(

La,

++La_len,

e

);en=e;} //La中不存在和e

相同的数据元素，则之}172.2

线性表的顺序表示与实现线性结构的顺序表示是指使用一组地址连续的单元依次

线性表的数据元素。线性表的起始地址，称作线性表的

址a1a2…ai-1ai…an线性表元

间的逻辑关系，通过元素的

顺序反映（表示）出来；假设：线性表中每个数据元素占用k

个元，那么，在顺序

结构中，线性表的第单i个元素的

位置与第

1个元素的

位置的关系：Loc

(ai

)

=

Loc

(

a1

)+

(i

–

1)

k2.2

线性表的顺序表示与实现线性表的顺序表示地址内存状态元素位序顺序表的特点用连续的 单元存放线性表的元素元素

顺序与元素的逻辑顺序一致2.2

线性表的顺序表示与实现顺序表的类型定义#define

LIST_INIT_SIZE

100空间的初始分配量//

线性表10//线性表空间的分配增量#define

LISTINCREMENTtypedef

struct

{ElemType

*

elem;intintlength;listsize;//线性表 空间基址//当前线性表长度//当前分配的表空间大小//（以sizeof(ElemType)为单位）}SqList;2.2

线性表的顺序表示与实现设 A

=（a1，a2，a3，...，an）是一线性表，L是SqList类型的结构变量，用于存放线性表

A，则 L在内存中的状态：存放线性表元素的一维数组顺序表通过元素的

顺序反映线性表元素间的逻辑关系a1a2ai-1aiai+1

an01i-2i-1in-199L.elemL.lenghtL.listsizen100202.2

线性表的顺序表示与实现顺序表基本操作的算法初始化操作InitList_Sq(SqList

&L)功能：建立空的顺序表L参数：L:顺序表01...i...99L.elemL.lenghtL.listsize01002.2

线性表的顺序表示与实现两个C函数之一：malloc(int

size)单元，并返回功能：在内存中分配长度为size个字节的该空间的基址。使用方法：int

m

=

100, float

*p;p

=

(float

*)

malloc

(

m*sizeof(float

)

);01...i...99p2.2

线性表的顺序表示与实现p调用free(p)两个C函数之二：free(p)功能：回收指针p

所指向的内存空间使用方法：int

m

=100, float

*p;p

=

(float

*)

malloc

(m*sizeof(float)

);//一旦不再需要p所指向的内存空间//调用free()回收之free(p);2.2

线性表的顺序表示与实现初始化操作InitList

Sq(SqList

&L)Status

InitList_Sq

(

SqList

&L{ //构造一个空的顺序表LL.elem(

ElemType

*

)malloc(LIST_INIT_SIZE

*sizeof(ElemType));if

(

!L.elem)exit

(

OVERFLOW

);L.length=

0;

//空表长度为0L.listsize

=LIST_INIT_SIZE;return

OK;}

//InitList_Sq2.2

线性表的顺序表示与实现顺序表基本操作的算法销毁操作DetroyList_Sq(SqList

&L)功能：销毁顺序表LL.elemL.lenghtL.listsizeNULL002.2

线性表的顺序表示与实现销毁操作DetroyList_Sq(SqList

&L)Status

DetroyList_Sq

(

SqList

&L){ free

(L.elem);L.elem

=

NULL;L.length

=

0;L.Listsize

=

0;return

OK;} //

DetroyList_Sq2.2

线性表的顺序表示与实现操作定义：线性表的

是指在第

i

1i

n+1）个元 前插入一个新的数据元素x，使长度为n的线性表A=（a1,a2,...,ai-1, ai

, ai+1,…,

an）n+1的线性表：A

=（a1,

a2,

...

,

ai-1,

x, ai

, ai+1,

…,

an）需将第

i至第

n

共（n-i+1）

元素后移2.2

线性表的顺序表示与实现操作：ListInsert_Sq(SqList

&L,

int ,

ElemType

e)L.elemL.lenghtL.listsizen1000199n-1na1a2...ai-1aiai+1...ani

2i

1iL.elemL.lenghtL.listsizen0199n

1na1a2...ai-1eai......ani

2ii+12.2

线性表的顺序表示与实现e2.2

线性表的顺序表示与实现操作：基本算法Status

ListInsert_Sq

(SqList

& int

i,

ElemType

e){

//在顺序线性表L中第

i

个位置之前 新的元素e,if

(

i<1

||

i>L.length+1

)return

ERROR;

//i

超出表长则不合法q

=&(L.elem[i-1]);

//q

指向位置for

(

p=&(L.elem[L.length-1]);

p>=q; p

)//初始化时p指向最后一个数据元素//

e//表长增1*(p+1)=*p;*q

=e;++L.length;return

OK;}

//

ListInsert_Sq2.2

线性表的顺序表示与实现Status

ListInsert_Sq(SqList

&L,int{//在顺序线性表L中第i

个位置之前ElemType

e)新的元素e,if(i<1

||

i>L.length+1) return

ERROR;

//i不合法if(L.length>=L.listsize)

//空间已满，重新分配空间{

newbase

=

(ElemType*)

realloc

(L.elem,(L.listsize+L.incresize)

*

sizeof(ElemType)

);if(!newbase)

exit(OVERFLOW);

//

分配失败L.elem

=

newbase;L.listsize+=

L.incresize;//新基址//增加

容量}q=

&

(

L.elem[i-1]

//

q为

位置for(p=&(L.elem[L.length-1]);p>=q;--p)

//p指向尾元// e

，表长增1*

(p+1)

=

*p;*q=e;

++L.length;return

OK;}

//ListInsert_Sq2.2

线性表的顺序表示与实现删除操作ListDelete Sq

(SqList

&L,

int

i,

ElemType

&e)在顺序线性表L i个元素，并用e返回.L.elemL.lenghtL.listsizen10001n

2n-1a1a2...ai-1aiai+1...an-1ani

2i-1iL.elemL.lenghtL.listsizen-110001n-1na1a2...ai-1ai+1ai+2...an9999i-2i

1iaie2.2

线性表的顺序表示与实现Status

ListDelete

Sq(SqList

&L,int

i,ElemType

&e){

//在顺序线性表L中删除第i

个元素，并用e

返回其值。i的合法值为1≤i≤L.length。if

(

(i<1)

||

(i>L.Length)

) return

ERROR;p

=

&

(

L.elem[i-1]

);e

=

*p;//p为被删除元素的位置//被删除元素的值赋给eq=L.elem[L.length-1];

//表尾元素的位置for

(

++p;

p<=q;

++p

)//被删除元 后的元素前移//表长减1*(p-1)

*p;-

L.length;return

OK;}

//ListDelete_Sq2.2

线性表的顺序表示与实现利用基本操作建立顺序表void

Crea ist_Sq

(

SqList

&L,

int

n

){

//输入n个元素的值建立一个顺序表LInitList_Sq

(

SqList

L

);for

(

i=1;

i<=n;

i

){

read(e);

//输入一个数据eListInsert_Sq

(

L,

i,

e

);}}

//Creaist_L2.3

线性表的链式

与实现线性表的链式

结构特点：1

用一组任意的 单元线性表的数据元素。单元存放逻辑上相邻的一2、利用指针实现了用不相邻的组元素除 本身信息外 还需 其直接后3、每个数据元素ai继的信息（指针）。结点数据域：数据元素本身的信息指针域：指示直接后继的 位置结点指2.3

线性表的链式

与实现例：(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)ZHAANLIZHENG^H43N13UN1NULLWU37Z

A7Z

E19Z

O2511937头指针头指针假设：数据域占5

个字节，指针域占1

个字节2.3

线性表的链式

与实现头指针：存放线性链表中第一个结点的

地址；空指针：不指向任何结点，线性链表最后一个结点的指针通常是指针；头结点：线性链表的第一数据元素结点前面的一个附加结点，称为头结点。头结点不保存数据。结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为 结点的线性链表；L是头指针ai-1aia2a1ai+1anL线性链表的每个结点中只有一个指针域故也称为单链表头结点空指针数据结点2.3

线性表的链式

与实现结点的形式定义Typedef

struct LNode

{//数据域//指针域ElemTypestruct

Lnodedata;*next;}

LNode

*

LinkListLinkList

L；//L

为单链表的头指针，是LinkList

类型的变量L是头指针L空表头结点2.3

线性表的链式

与实现ai-1aia2a1ai+1an相关术语： 结点的单向链表LL空表怎样判断 结点的单向链表是否为空表？如果

L->next

==

NULL

成立，则

L

为空表。等价：如果：L->next!=NULL成立，则L不是空表。2.3

线性表的链式

与实现ai-1aia2a1ai+1an相关术语：不

结点的单向链表LL空表：怎样判断不 结点的单向链表是否为空表？如果 L

==

NULL

成立，则

L 为空表。等价：如果：L

!=

NULL

成立，则

L 不是空表。2.3

线性表的链式

与实现a2a4a2a5结点之间的基本关系p

qrs则下列关系成立：qs

==q->

next->nextp

>next

==r->next

====p

>

next->next->next通过当前结点p要指针为：通过当前结点p要下一个结点 则指向下一个结点的p

>next下一个结点的下一个p

>next

>next2.3

线性表的链式

与实现线性链表的基本操作取数据元素操作

Ge em

(

L,

i,

&e)功能：取带有头结点的线性链表

L

中第i 个元素结点其值存入

e。主要步骤查找到第i1个元素结点取值存入eL∧32.3

线性表的链式

与实现单链表操作的特点单链表是一种顺序存取的结构为找第i

个数据元素，必须先找到第i-1个数据元素因此，查找第

i

个数据元素的基本操作为：移动指针

比较

j

和

i

。令指针p

始终指向线性表中第j

个数据元素。2.3

线性表的链式

与实现i结点的链表的头指针，以e返回第i个元素//L是pwhile=

//p

指向第1个结点，j为计数器p

U

&&

i

//沿指针向后查找{

p p->}//

退出循环时，p

指向第i个元素

p

为空if

(

p

==

Lu

rn

E

O//第i个元素不存在//取得第

i个元素e p->dataet

rn}

//

Ge

em_L2.3

线性表的链式

与实现线性链表的基本操作操作

ListInser L

(

&L

i,

e

)功能：在带有头结点的线性链表

L

的第

i个元素结点之前一个新元素结点e主要步骤查找第i-1个元素结点建立新结点e修改指针 新结点2.3

线性表的链式

与实现主要步骤p指向第i

1个元素结点s指向新结点e修改指针

新结点ai-1a1ai+1anLs->next=p->next;e×aiai-1aia1ai+1anLe2.3

线性表的链式

与实现Status

ListInsert_L(LinkList

&L,

int

i,

ElemType

e){

//在 结点的链表第i结点之前

e，1i表长+1p=L;

j=0;

//

p

指向头结点while

(

p!=NULL

&&

j<i-1

)

//

寻找第

i-1

个数据结点{

p=p->next;

++j;}

//

退出循环时

p

为NULL

或

指向第

i-1个结点if

(

p==NULL

j>i-1

)return

ERROR;

//i<1

或i>表长+1s=(LinkList)malloc(sizeof(LNode));

//建新结点s

>data

=

e;s->next

=

p->next;//

新结点p->next

=

s;return

OK;}

//ListInsert_L问题：何进行如操作2.3

线性表的链式

与实现线性链表的基本操作删除操作

ListDelete_L

(

&L

i,

e

)并由e

返回功能：删除线性链表L中的第i个元素结点主要步骤查找第i

1个元素结点修改指针删除第i

个元素结点回收被删除结点2.3

线性表的链式

与实现ai-1a1ai+1an主要步骤p

指向第i

1

个元素结点，q指向被删除结点修改指针删除第i

个元素结点回收被删除结点Lq

=

p->next;ai-1a1ai+1anL×ai2.3

线性表的链式

与实现Status

ListDelete L(LinkList

&L,

int

i,

ElemType

&e){

//

在 结点的链表L中，删除第

i

个元素，由

e

返回其值。1i表长。p=L;

j=0;while(p->next!=NULL

&&

j<i-1)//寻找第i-1个结点{

p=p

>next;

+

j;}//

退出循环时，p为NULL

或

指向第

i

1

个结点if

(

!p

>next

||

j>i-1

) return

ERROR;p->next=q->next;

//删除结点//回收结点空间q=p->next;e=q->data;free(q);return

OK;}

//ListDelete_L问题：如何进行删除操作2.3

线性表的链式

与实现建立 结点的线性链表//建空表m

f

ot

N

LL;for

i>0

//逆序输入n个元素}}

//Crea

ist_LLanan-1a1{rea

(e);

//读入元素(

Lis

) c

(

zeo

N

);p ta

=->nex

=

; t=p;//插到表头Lep×a42.3

线性表的链式

与实现静态链表用数组实现的链式结构

称为静态链表。1345789a40a3a18a23a3a2a1L通过下标，记录结点之间的关系2.3

线性表的链式

与实现线性链表的特点用一组任意的 单元 线性表中数据元素；通过指针保存直接后继元素的 地址来表示数据元素之间的逻辑关系；通过头指针（或首结点）给出线性链表；链表中结点空间是动态分配的；删除操作通过修改结点的指针实现；只能顺序存取元素，不能直接存取元素。2.3

线性表的链式

与实现循环链表（带有头结点的单向环表）最后一个结点的指针域的指针又指回第一个结点（头结点

的链表判别条件继是否为头结点后空表判断为是否空表的条件：h->next

==

h2.3

线性表的链式

与实现ai-1aia1ai+1an循环链表的特点从一个结点可找到链表中的任意一个结点；判断是否为表尾结点的条件：p->next==L。有时 用表尾指针表示循环链表。Lai-1aia1ai+1an2.3

线性表的链式

与实现双向链表typedef

struct DuLNode

{//数据域//指向前驱的指针域//指向后继的指针域ElemType

data;struct

DuLNode

*prior;struct

DuLNode

*next;}

DuLNode,

*DuLinkList;iorlem空双向循环链表：L非空双向循环链表：LA2.3

线性表的链式

与实现p->prior->next

=p

=

p->next->proir;p2.4

线性表的应用实例一元多项式的表示及相加P

(

x

)

P

Px

P

x

2

P

xnn