考研-數(shù)據(jù)結(jié)構(gòu)

2.1

線性表的基本概念線性表特點：在數(shù)據(jù)元素的非空有限集存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素集合中的每個數(shù)據(jù)元素均只有一個素均只有一除第一個外前驅(qū)除最后一個外，集合中的每個數(shù)據(jù)個后繼線性表是類型相同的元素有限序列，記作：（a1,

...,

ai

1,

ai,

ai+1,

?

,

an）2.1

線性表的基本概念設(shè)

A=（a1,

a2,

...

,

ai-1, ai

, ai+1,

…,

an）是一線性表

1）線性表的數(shù)據(jù)元素可以是各種各樣的，但同一線性表中的元素必須是同一類型的；2

在表中ai-1

領(lǐng)先于ai，ai

領(lǐng)先于ai+1，稱ai-1

是ai的直接前趨，ai+1

是ai

的直接后繼；3性表中，除第一個元素和最后一個元外，其他元素都有且僅有一個直接前趨，有且僅有一個直接后繼。線性表是一種線性數(shù)據(jù)結(jié)構(gòu)；元素的個數(shù)n

稱為表的長度，n=0時稱為空表；ai

是表的第

i

個元素，稱i

為數(shù)據(jù)元素ai

的序號，每個元素性表中的位置，僅取決于它的序號?？稍诒淼娜我馕恢眠M行 和刪除操作。32.1

線性表的基本概念對線性表的ADT描述ADT

List

{數(shù)據(jù)對象：D

=

{

ai

|

ai

ElemSet,

i=1,

,n n≥0

}數(shù)據(jù)關(guān)系R1

=

{

<ai-1,

ai>

|

ai-1,ai

D,

i=2, ,n

}基本操作InitList

(&L)操作結(jié)果 構(gòu)造一個空的線性表L。DetroyList

(&L)初始條件：線性表L已經(jīng)存在。操作結(jié)果：銷毀線性表L。}ADTList2.1

線性表的基本概念對線性表的基本操作初始化操作InitList(&L)功能：建立空的線性表L；銷毀操作DetroyList(&L)空間；功能：回收為線性表L動態(tài)分配的置空操作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；查找前驅(qū)PriorElem(L,cur_e,&pre_e)功能：若cur_e是

L 中的數(shù)據(jù)元素且不是第一個，則用pre_e返回它的前驅(qū)，否則失敗，pre_e無定義。2.1

線性表的基本概念查找后繼

Nex em

( L,

cur_e,

&next_e

)功能：若cur_e是L中的數(shù)據(jù)元素且不是最后一個，則用next_e返回它的后繼，否則失敗，next_e無定義。操作ListInsert(&L,i,e)功能：

性表L的第i個元

前

1個新元素e；刪除操作

ListDelete( &L,i,

&e

)功能：刪除線性表L的第i個元素，并用e返回；遍歷操作

ListTraverse

(

L,visit(

)

)功能：依次對線性表L的每個元素調(diào)用函數(shù)visit()。若visit()失敗，則返回ERROR，否則返回OK；2.1

線性表的基本概念說明基本操作是一種數(shù)據(jù)結(jié)構(gòu)中最常見的操作它具有明確的邏輯意義?？梢詫⒒静僮骺闯梢粋€整體，使用基本操作來解決新的問題，設(shè)計新的算法。使可以在高的層次上進行抽象，在更高的基礎(chǔ)上進行設(shè)計。3、在算法的程序?qū)崿F(xiàn)的過程中，基本操作需要通過編制公共函數(shù)進行具體實現(xiàn)?？梢詾榛静僮鹘⒐埠瘮?shù)庫。2.1

線性表的基本概念利用基本操作進行算法設(shè)計例1：若有兩個集合A

和B

分別用兩個線性表LA和LB

表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員?，F(xiàn)要求一個新的集合：A＝A∪B。問題分析上述問題可以演繹為：擴大線性表LA，將存在于線性表LB

中而不存在于線性表

LA

中的數(shù)據(jù)元素到線性表LA

中去。92.1

線性表的基本概念利用基本操作進行算法設(shè)計Ge em(

LB,

i

)

→

eLocateElem

(

LA,

e,

equal(

)

)ListInsert

(

LA,

n+1,

e

)2.1

線性表的基本概念利用基本操作進行算法設(shè)計void

union

(

List

&La, List

Lb)La_len=ListLength

(La);

//求線性表的長度Lb_len

=

ListLength

(Lb);for

(i

=

1; i

<=

Lb_len; i++

)

{;

//取Lb中第i個數(shù)據(jù)元素賦給eif

(

!

equal(

)

)//

La中不存在和

e

相同的數(shù)據(jù)元素，則

之}//

union2.1

線性表的基本概念例2-1：已知一個非純集合B

試構(gòu)造一個純集合

A使

A B

中所有值各不相同的數(shù)據(jù)元素。問題分析：采用線性表表示集合算法策略：從集合B

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

中同樣的物件不能有兩件以上。2.1

線性表的基本概念利用基本操作進行算法設(shè)計void

union

(

List

&La, List

Lb

)La_len=ListLength

(La); Lb_len=ListLength

(Lb);for

(i

=

1; i

<=

Lb_len; i++

)

{;

//取Lb中第i個數(shù)據(jù)元素賦給eif

(

!

equal(

)

)//

La中不存在和

e

相同的數(shù)據(jù)元素，則

之}//

union2.1

線性表的基本概念例2-2：已知一個非純集合B

試構(gòu)造一個純集合

A使

A B

中所有值各不相同的數(shù)據(jù)元素。問題分析：采用有序表表示集合有序表：若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素

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

ai≤ai-1

(i=2,3,?,n)則稱該線性表為有序表(Ordered

List)。2.1

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

12）對集合B

而言，。值相同的數(shù)據(jù)元素必定相鄰；對集合A

而言，數(shù)據(jù)元素依值從小至大的順序因此，數(shù)據(jù)結(jié)構(gòu)改變了，解決問題的策略也要相應進行改變。2.1

線性表的基本概念利用基本操作進行算法設(shè)計for

(i

=

1; i

<=

Lb_len; i++

)

{Ge em(Lb,i,e);//取Lb中第i個數(shù)據(jù)元素賦給eif()

{||ListInsert

(

La,

++La_len,

e

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

相同的數(shù)據(jù)元素，則之}172.2

線性表的順序表示與實現(xiàn)線性結(jié)構(gòu)的順序表示是指使用一組地址連續(xù)的單元依次

線性表的數(shù)據(jù)元素。線性表的起始地址，稱作線性表的

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

間的邏輯關(guān)系，通過元素的

順序反映（表示）出來；假設(shè)：線性表中每個數(shù)據(jù)元素占用k

個元，那么，在順序

結(jié)構(gòu)中，線性表的第單i個元素的

位置與第

1個元素的

位置的關(guān)系：Loc

(ai

)

=

Loc

(

a1

)+

(i

–

1)

k2.2

線性表的順序表示與實現(xiàn)線性表的順序表示地址內(nèi)存狀態(tài)元素位序順序表的特點用連續(xù)的 單元存放線性表的元素元素

順序與元素的邏輯順序一致2.2

線性表的順序表示與實現(xiàn)順序表的類型定義#define

LIST_INIT_SIZE

100空間的初始分配量//

線性表10//線性表空間的分配增量#define

LISTINCREMENTtypedef

struct

{ElemType

*

elem;intintlength;listsize;//線性表 空間基址//當前線性表長度//當前分配的表空間大小//（以sizeof(ElemType)為單位）}SqList;2.2

線性表的順序表示與實現(xiàn)設(shè) A

=（a1，a2，a3，...，an）是一線性表，L是SqList類型的結(jié)構(gòu)變量，用于存放線性表

A，則 L在內(nèi)存中的狀態(tài)：存放線性表元素的一維數(shù)組順序表通過元素的

順序反映線性表元素間的邏輯關(guān)系a1a2ai-1aiai+1

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

線性表的順序表示與實現(xiàn)順序表基本操作的算法初始化操作InitList_Sq(SqList

&L)功能：建立空的順序表L參數(shù)：L:順序表01...i...99L.elemL.lenghtL.listsize01002.2

線性表的順序表示與實現(xiàn)兩個C函數(shù)之一：malloc(int

size)單元，并返回功能：在內(nèi)存中分配長度為size個字節(jié)的該空間的基址。使用方法：int

m

=

100, float

*p;p

=

(float

*)

malloc

(

m*sizeof(float

)

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

線性表的順序表示與實現(xiàn)p調(diào)用free(p)兩個C函數(shù)之二：free(p)功能：回收指針p

所指向的內(nèi)存空間使用方法：int

m

=100, float

*p;p

=

(float

*)

malloc

(m*sizeof(float)

);//一旦不再需要p所指向的內(nèi)存空間//調(diào)用free()回收之free(p);2.2

線性表的順序表示與實現(xiàn)初始化操作InitList

Sq(SqList

&L)Status

InitList_Sq

(

SqList

&L{ //構(gòu)造一個空的順序表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

線性表的順序表示與實現(xiàn)順序表基本操作的算法銷毀操作DetroyList_Sq(SqList

&L)功能：銷毀順序表LL.elemL.lenghtL.listsizeNULL002.2

線性表的順序表示與實現(xiàn)銷毀操作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

線性表的順序表示與實現(xiàn)操作定義：線性表的

是指在第

i

1i

n+1）個元 前插入一個新的數(shù)據(jù)元素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

線性表的順序表示與實現(xiàn)操作：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

線性表的順序表示與實現(xiàn)e2.2

線性表的順序表示與實現(xiàn)操作：基本算法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指向最后一個數(shù)據(jù)元素//

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

=e;++L.length;return

OK;}

//

ListInsert_Sq2.2

線性表的順序表示與實現(xiàn)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

線性表的順序表示與實現(xiàn)刪除操作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

線性表的順序表示與實現(xiàn)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

線性表的順序表示與實現(xiàn)利用基本操作建立順序表void

Crea ist_Sq

(

SqList

&L,

int

n

){

//輸入n個元素的值建立一個順序表LInitList_Sq

(

SqList

L

);for

(

i=1;

i<=n;

i

){

read(e);

//輸入一個數(shù)據(jù)eListInsert_Sq

(

L,

i,

e

);}}

//Creaist_L2.3

線性表的鏈式

與實現(xiàn)線性表的鏈式

結(jié)構(gòu)特點：1

用一組任意的 單元線性表的數(shù)據(jù)元素。單元存放邏輯上相鄰的一2、利用指針實現(xiàn)了用不相鄰的組元素除 本身信息外 還需 其直接后3、每個數(shù)據(jù)元素ai繼的信息（指針）。結(jié)點數(shù)據(jù)域：數(shù)據(jù)元素本身的信息指針域：指示直接后繼的 位置結(jié)點指2.3

線性表的鏈式

與實現(xiàn)例：(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)ZHAANLIZHENG^H43N13UN1NULLWU37Z

A7Z

E19Z

O2511937頭指針頭指針假設(shè)：數(shù)據(jù)域占5

個字節(jié)，指針域占1

個字節(jié)2.3

線性表的鏈式

與實現(xiàn)頭指針：存放線性鏈表中第一個結(jié)點的

地址；空指針：不指向任何結(jié)點，線性鏈表最后一個結(jié)點的指針通常是指針；頭結(jié)點：線性鏈表的第一數(shù)據(jù)元素結(jié)點前面的一個附加結(jié)點，稱為頭結(jié)點。頭結(jié)點不保存數(shù)據(jù)。結(jié)點的線性鏈表：第一元素結(jié)點前面增加一個附加結(jié)點的線性鏈表稱為 結(jié)點的線性鏈表；L是頭指針ai-1aia2a1ai+1anL線性鏈表的每個結(jié)點中只有一個指針域故也稱為單鏈表頭結(jié)點空指針數(shù)據(jù)結(jié)點2.3

線性表的鏈式

與實現(xiàn)結(jié)點的形式定義Typedef

struct LNode

{//數(shù)據(jù)域//指針域ElemTypestruct

Lnodedata;*next;}

LNode

*

LinkListLinkList

L；//L

為單鏈表的頭指針，是LinkList

類型的變量L是頭指針L空表頭結(jié)點2.3

線性表的鏈式

與實現(xiàn)ai-1aia2a1ai+1an相關(guān)術(shù)語： 結(jié)點的單向鏈表LL空表怎樣判斷 結(jié)點的單向鏈表是否為空表？如果

L->next

==

NULL

成立，則

L

為空表。等價：如果：L->next!=NULL成立，則L不是空表。2.3

線性表的鏈式

與實現(xiàn)ai-1aia2a1ai+1an相關(guān)術(shù)語：不

結(jié)點的單向鏈表LL空表：怎樣判斷不 結(jié)點的單向鏈表是否為空表？如果 L

==

NULL

成立，則

L 為空表。等價：如果：L

!=

NULL

成立，則

L 不是空表。2.3

線性表的鏈式

與實現(xiàn)a2a4a2a5結(jié)點之間的基本關(guān)系p

qrs則下列關(guān)系成立：qs

==q->

next->nextp

>next

==r->next

====p

>

next->next->next通過當前結(jié)點p要指針為：通過當前結(jié)點p要下一個結(jié)點 則指向下一個結(jié)點的p

>next下一個結(jié)點的下一個p

>next

>next2.3

線性表的鏈式

與實現(xiàn)線性鏈表的基本操作取數(shù)據(jù)元素操作

Ge em

(

L,

i,

&e)功能：取帶有頭結(jié)點的線性鏈表

L

中第i 個元素結(jié)點其值存入

e。主要步驟查找到第i1個元素結(jié)點取值存入eL∧32.3

線性表的鏈式

與實現(xiàn)單鏈表操作的特點單鏈表是一種順序存取的結(jié)構(gòu)為找第i

個數(shù)據(jù)元素，必須先找到第i-1個數(shù)據(jù)元素因此，查找第

i

個數(shù)據(jù)元素的基本操作為：移動指針

比較

j

和

i

。令指針p

始終指向線性表中第j

個數(shù)據(jù)元素。2.3

線性表的鏈式

與實現(xiàn)i結(jié)點的鏈表的頭指針，以e返回第i個元素//L是pwhile=

//p

指向第1個結(jié)點，j為計數(shù)器p

U

&&

i

//沿指針向后查找{

p p->}//

退出循環(huán)時，p

指向第i個元素

p

為空if

(

p

==

Lu

rn

E

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

i個元素e p->dataet

rn}

//

Ge

em_L2.3

線性表的鏈式

與實現(xiàn)線性鏈表的基本操作操作

ListInser L

(

&L

i,

e

)功能：在帶有頭結(jié)點的線性鏈表

L

的第

i個元素結(jié)點之前一個新元素結(jié)點e主要步驟查找第i-1個元素結(jié)點建立新結(jié)點e修改指針 新結(jié)點2.3

線性表的鏈式

與實現(xiàn)主要步驟p指向第i

1個元素結(jié)點s指向新結(jié)點e修改指針

新結(jié)點ai-1a1ai+1anLs->next=p->next;e×aiai-1aia1ai+1anLe2.3

線性表的鏈式

與實現(xiàn)Status

ListInsert_L(LinkList

&L,

int

i,

ElemType

e){

//在 結(jié)點的鏈表第i結(jié)點之前

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

j=0;

//

p

指向頭結(jié)點while

(

p!=NULL

&&

j<i-1

)

//

尋找第

i-1

個數(shù)據(jù)結(jié)點{

p=p->next;

++j;}

//

退出循環(huán)時

p

為NULL

或

指向第

i-1個結(jié)點if

(

p==NULL

j>i-1

)return

ERROR;

//i<1

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

//建新結(jié)點s

>data

=

e;s->next

=

p->next;//

新結(jié)點p->next

=

s;return

OK;}

//ListInsert_L問題：何進行如操作2.3

線性表的鏈式

與實現(xiàn)線性鏈表的基本操作刪除操作

ListDelete_L

(

&L

i,

e

)并由e

返回功能：刪除線性鏈表L中的第i個元素結(jié)點主要步驟查找第i

1個元素結(jié)點修改指針刪除第i

個元素結(jié)點回收被刪除結(jié)點2.3

線性表的鏈式

與實現(xiàn)ai-1a1ai+1an主要步驟p

指向第i

1

個元素結(jié)點，q指向被刪除結(jié)點修改指針刪除第i

個元素結(jié)點回收被刪除結(jié)點Lq

=

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

線性表的鏈式

與實現(xiàn)Status

ListDelete L(LinkList

&L,

int

i,

ElemType

&e){

//

在 結(jié)點的鏈表L中，刪除第

i

個元素，由

e

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

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

&&

j<i-1)//尋找第i-1個結(jié)點{

p=p

>next;

+

j;}//

退出循環(huán)時，p為NULL

或

指向第

i

1

個結(jié)點if

(

!p

>next

||

j>i-1

) return

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

//刪除結(jié)點//回收結(jié)點空間q=p->next;e=q->data;free(q);return

OK;}

//ListDelete_L問題：如何進行刪除操作2.3

線性表的鏈式

與實現(xiàn)建立 結(jié)點的線性鏈表//建空表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

線性表的鏈式

與實現(xiàn)靜態(tài)鏈表用數(shù)組實現(xiàn)的鏈式結(jié)構(gòu)

稱為靜態(tài)鏈表。1345789a40a3a18a23a3a2a1L通過下標，記錄結(jié)點之間的關(guān)系2.3

線性表的鏈式

與實現(xiàn)線性鏈表的特點用一組任意的 單元 線性表中數(shù)據(jù)元素；通過指針保存直接后繼元素的 地址來表示數(shù)據(jù)元素之間的邏輯關(guān)系；通過頭指針（或首結(jié)點）給出線性鏈表；鏈表中結(jié)點空間是動態(tài)分配的；刪除操作通過修改結(jié)點的指針實現(xiàn)；只能順序存取元素，不能直接存取元素。2.3

線性表的鏈式

與實現(xiàn)循環(huán)鏈表（帶有頭結(jié)點的單向環(huán)表）最后一個結(jié)點的指針域的指針又指回第一個結(jié)點（頭結(jié)點

的鏈表判別條件繼是否為頭結(jié)點后空表判斷為是否空表的條件：h->next

==

h2.3

線性表的鏈式

與實現(xiàn)ai-1aia1ai+1an循環(huán)鏈表的特點從一個結(jié)點可找到鏈表中的任意一個結(jié)點；判斷是否為表尾結(jié)點的條件：p->next==L。有時 用表尾指針表示循環(huán)鏈表。Lai-1aia1ai+1an2.3

線性表的鏈式

與實現(xiàn)雙向鏈表typedef

struct DuLNode

{//數(shù)據(jù)域//指向前驅(qū)的指針域//指向后繼的指針域ElemType

data;struct

DuLNode

*prior;struct

DuLNode

*next;}

DuLNode,

*DuLinkList;iorlem空雙向循環(huán)鏈表：L非空雙向循環(huán)鏈表：LA2.3

線性表的鏈式

與實現(xiàn)p->prior->next

=p

=

p->next->proir;p2.4

線性表的應用實例一元多項式的表示及相加P

(

x

)

P

Px

P

x

2

P

xnn