《數據結構》復習重點

《數據結構》復習重點

第一章緒論

要求、目標：

了解數據邏輯結構的分類；

掌握算法的特性及估算算法時間復雜度的方法；

熟悉數據結構的基本基本概念和術語。

一、基本概念和術語

1.數據結構：是一門研究非數值計算的程序設計問題中計算機的操作對象

以及它們之間的關系和操作等的學科。

2.數據：是對客觀事物的符號表示，即所有能輸入到計算機中并被計算機

程序處理的符號的總稱。

3.數據項：數據的不可分割的最小單位。

4.數據元素(數據結點)：數據的基本單位，在程序中作為一個整體處理，

由若干數據項組成。

5.數據對象：性質相同的數據元素的集合，是數據的一個子集

如：四季對象是集合：｛春，夏，秋，冬｝

自然數對象是集合：［0,1,2,3,…｝

字母字符對象是集合：｛，A','B',…'Z'｝

6.數據結構的分類：線性結構和非線性結構。

7.數據結構的形式化定義：數據結構是一個二元組，可定義為

Data_Structure=(D,S)

其中：D是數據元素的有限集合，S是D上關系的有限集合

8.序偶：兩個元素間的前后關系。＜a,b＞a是b的前驅結點，b是a的后繼

結點

例：四季的描述B=(D,R)

D=｛春，夏，秋，冬｝

R=｛＜春，夏〉,〈夏，秋＞,＜秋，冬〉｝

9.物理結構(存儲結構或映像)：數據結構在計算機中的表示。

10.存儲結構的分類：

①順序存儲結構：利用元素的相對位置來表示元素間的位置關系，是一

種隨機存取結構，邏輯上相鄰的數據物理上也緊臨，靜態(tài)分配空間；

②鏈式存儲結構：借助元素存儲的指針來表示元素之間的關系，邏輯上

相鄰的數據物理上不一定緊臨，動態(tài)分配空間。

11.邏輯結構和物理結構的關系：是密切相關的兩個方面，任何一個算法的

設計取決于邏輯結構，而算法的實現則依賴于采用的存儲結構。

12.數據類型：是一個值的集合和定義在這個值集上的一組操作的總稱，規(guī)

定了在程序執(zhí)行期間變量或表達式所有可能取值的范圍，以及在這些值

上允許進行的操作。

二、算法和算法分析

1.算法：是對特定問題求解步驟的一種描述，它是指令的有限序列。

2.算法的特性：

①有窮性：算法在執(zhí)行有究步之后結束，每一步在有窮時間內完成。

②確定性：每一條指令必須有確切的含義，不應產生二義性，相同的輸入只

能得出相同的輸出。

③可行性：一個算法可以通過已經實現的基本運算執(zhí)行有限次來實現。

④輸入性：?個算法有零個或多個輸入。

⑤輸出性：一個算法有一個或多個輸出。

3.算法分析考慮的方面：

①正確性②可讀性③健壯性④效率與低存儲量需求

4.語句頻度：一條語句被執(zhí)行的次數

5.漸近時間復雜度：所有語句頻度之和，主要考慮嵌套最深語句的頻度，若頻

度為多項式取指數最高的一項去掉系數即為漸近時間復雜度。

T(n)=O(f(n))--f(n)為時間復雜度值

例：⑴{++x;s=O;}——0(1)

(2)for(i=l;i<=n;i++){++x;s+=x}0(n)

(3)for(j=l;j<=n;j++)-——0(1?)

for(k=l;k<=n;k++){++x;s+=x;}

(4)for(j=l;j<n;j++)

{y=y+l;—頻度：n-1

for(k=0;k<=(2*n);j++)x++;}——頻度：(n-l)*(2n+l)

--時間復雜度為0面)

6.算法分析的兩個主要方面：空間復雜度和時間復雜度。

第一章復習題

一、填空

1、數據結構被形式地定義為(D,S),其中D是數據元素的有限集合,S是

D上關系的有限集合。

2、數據結構是一門研究非數值計算的程序設計問題中計算機的數據元素

以及它們之間的關系和運算等的學科。

3、在數據結構中，邏輯上可以把數據結構分成線性結構和非線性結構。

—―,選立洋牧

1、算法必須具備的五個特性是(B)。

A.輸入性、輸出性、可執(zhí)行性、可移植性和可擴充性

B.輸入性、輸出性、可行性、確定性和有窮性

C.輸入性、輸出性、確定性、有窮性和穩(wěn)定性

D.輸入性、輸出性、可行性、穩(wěn)定性和安全性

2、算法分析的兩個主要方面是(A)o

A.空間復雜度和時間復雜度B.正確性和可讀性

C.簡單性和文檔性D.數據復雜性和程序復雜性

三、計算，求下列算法的漸近時間復雜度及帶@語句的頻度

1.voidsort(int*x,intn)

{inti,j,k,t;

for(i=l,i<=n-l;i++)

{k=i;

for(j=i+l;j<n;j++)

if(x[j]>x[k])k=j;@

if(k!=i)

{t=x[i];x[i]=x[k];x[k]=t;}}}

解：語句頻度為：("-1)+(n-2)++1="—―

漸近時間復雜度：0(n2)

2.sum(intn);

{intsum=O,i,j;

for(i=l;i<=n;i++)

{p=l；

for(j=l;j<=i;j++)

P*二j；@

sum+=p;}

returnsum;}

解：語句頻度為：1+2+3+…+"=險土。

2

漸近時間復雜度：0(/)

3.sum(intn)

{inti,sum=0;

for(i=l;i<=n;i++)

sum+=i;@

printf("%dn,sum);}

解：語句頻度為：n

漸近時間復雜度：0(n)

第二章線性表

要求、目標：

了解線性表的基本概念；

掌握順序存儲和鏈式存儲結構的描述方法；

掌握循環(huán)單鏈表、雙鏈表的特點

一、線性表概述

1.線性表：具有相同類型的n個數據元素的有限序列，可表示為0,a2,…,a0)

2.線性表長度：數據元素個數n。

3.空線性表：長度為零的線性表。

4.關鍵字/犍：能惟一標識元素的字段。

5.相鄰元素關系：ai為az前驅元素，4”為④后繼元素，存在序偶關系。

為無前驅元素，a.無后繼元素。

例：字母表：(A,B,C,…,Z)

學生成績表：(790631,790632,…，790645)每個元素為一條記錄，由若干

數據項組成，線性表中可只寫關鍵字。

二、線性表的順序存儲

1.順序存儲：線性表的各個元素依次存儲在一組地址連續(xù)的存儲單元里。

2.元素位置確定：LOC(ai)=LOC(ai)+(i-l)*L其中aI為線性表第一個元素的存

儲位置，L為每個元素所占字節(jié)數。

例：已知ai的地址為1000,每個元素占2字節(jié)，求as的地址

LOC(a5)=1000+(5-1)*2=1008

3.順序表的特點

(1)是一種隨機存取的存儲結構

(2)邏輯上相鄰的元素物理位置必定緊鄰

(3)存儲空間是靜態(tài)分配的

(4)適用于事先能確定線性表的大小，存取速度快

(5)插入和刪除操作時需移動大量的元素，

4.插入或刪除元素時移動次數

(1)向含有n個元素的線性表第i個位置插入元素，需移動n-i+1次元素，平均

移動巴次

2

(2)刪除含有n個元素的線性表第i個位置的元素，需移動n-i次元素，平均移

動0次

2

5.存儲結構的描述

#definelist_max100

typedefstruct{intdata[list_max];

intlen;}sqlist;

6.順序結構線性表的運算

(1)線性表的初始化

voidInitList(sqlist*L)

{L.len=0;}

(2)求線性表的長度

intListLen(sqlist*L)

{returnL.len;}

(3)在線性表中查詢某個個結點，返回結點在線性表中的位置

intsearch(intx;sqlist*L;intn)

{inti;

for(i=0;i<n;i++)

if(x==L.data[i])break;

if(i==n)retum(0);

retum(i+l);}

(4)在順序線性表中第I個位置前插入一新元素

intinsert_sq(sqlist*L;inti;inte)

{intp;

if(i<HII>L.len)return1;

if(L.len>list_max-1)return2;

for(p=L.len;p>i;p-)

L.data[p]=L.data[p-1];

L.data[i]=e;

L.len++;

return0;}

(5)在順序線性表中刪除第i個元素

intdelete_sq(sqlist*L,inti)

{intp;

if(i<llli>L.len)return1;

for(p=i+l;p<L.Ien;p++)

L.data[p-1]=L.data[p];

L.len-;

return0;}

(6)合并兩個遞增有序的順序線性表，合并后仍為遞增有序

intmergelist(sqlist*LA,sqlist*LB,sqlist*LC)

{intI=0,j=0,k=0;

while(I<LA.len&&j<LB.len)

{if(LA.data[I]<LB.data[j])

LC.data[k++]=LA.data[I++];

elseif(LA.data[I]==LB.data[j])

{LC.da皿k++]=LA.data[I++];

LC.data[k++]=LB.datafj++];}

else

LC.data[k++]=LB.data[j++];}

while(I<La.len)

LC.data[k++]=LA.data[I++];

while(j<LB.len)

LC.data[k++]=LB.data[j++];

returnk;}

三、線性表的鏈式存儲

(-)線性鏈表

1.特點

1)邏輯上相鄰的元素，物理上不一定緊鄰

2)插入和刪除操作時，不需移動大量元素，只需修改有限的指針變量

3)動態(tài)分配和釋放存儲單元，避免了空間浪費

4)不具備隨機存取的優(yōu)點，查找結點需從表頭開始，結點的存儲利用率較低

5)適用于經常進行插入、刪除操作或事先不能確定結點的最大數量

2.線性鏈表：具有鏈式存儲結構的線性表

3.單鏈表：每個結點只包含一個指針域

4.結點結構：datanext

5.結點類型

typedefstructnode

{intdata;

structnode*next;}NODE;

6.頭指針：指向鏈表的頭結點或第一個結點的位置

7.頭結點：在鏈表第一個結點之前附設的結點，其數據域可不存任何信息或存

表長，指針域保存第一個結點的地址

8.設置頭結點的作用：插入或刪除首元素時不必對頭指針進行修改

9.第一個結點：第一個實際存儲數據的結點

10.單鏈表的結構

1）不帶頭結點

11.建立帶頭結點的單鏈表,在表尾插入，以-1結束

NODE*creat()

{NODE*h,*p,*r;

intx;

h=r=(NODE*)malloc(sizeof(NODE));

scanf("％d'',&x);

while(x!=-l)

{p=(NODE*)malloc(sizeof(NODE));

p->data=x;

r->next=p;

r=p；

scanf("%d'',&x);}

r->next=NULL;

retum(h);}

12.建立帶頭結點的單鏈表,在表頭插入，以-1結束

NODE*creat()

{NODE*h,*p;

intx;

h=(NODE*)malloc(sizeof(NODE));

h->next=NULL;

scanf("%d”,&x);

while(x!=-l)

{p=(NODE*)malloc(sizeof(NODE));

p->data=x;

p->next=h->next;

h->next=p;

scanf("％d”,&x);}

retum(h);}

13.在單鏈表第I個結點前插入一個元素

intinsert_L(NODE*h,intI,intx)

{NODE*p=h,*s;

intj=0;

s=(NODE*)malloc(sizeof(NODE));

s->data=x;

while(p!=NULL&&j<I-l)

{p=p->next;j++;}

if(!pllj>I-l)return1;

s->next=p->next;

p->next=s;

return0;}

14.刪除單鏈表中第I個結點

intdelete_L(NODE*h,intI,int*e)

{NODE*p=h,*q;

intj=0;

while(p->next&&j<I-1)

{p=p->next;j++;}

if(!(p->next)llj>I-l)retum1;

q=p->next;

*e=q->data;

p->next=q->next;

free(q);

return0;}

15.查找與給定值相同的第一個結點

NODE*locatenode(NODE*h,intkey)

{NODE*p=h->next;

while(p&&p->data!=key)

p=p>>next;

returnp;}

16.合并兩個遞減有序的鏈表，合并后仍為遞減有序

NODE*merge_L(NODE*ha,NODE*hb)

{NODE*p=ha->next,*q=hb->next,*r,*s;

s=(NODE*)malloc(sizeof(NODE));

s->next=NULL;

r=s;

while(p!=NULL&&q!=NULL)

if(p->data>q->data)

{r->next=p;r=p;p=p->next;}

else

{r->next=q;r=q;q=q->next;}

if(p==NULL)r->next=q;

elser->next=p;

returns;}

(-)循環(huán)鏈表

1.定義：最后一個結點的指針域指向鏈表的頭結點或第一個結點。

2.優(yōu)點：解決了無法從指定結點到達該結點的前驅結點的問題。

3.結構：

4.判別是否為空

1）帶頭結點：當h->next==h時為空

2）不帶頭結點：當h==NULL時為空

5.刪除第一個結點

1）帶頭結點：h->next=h->next->next

2）不帶頭結點：h=h->next

6.建立循環(huán)鏈表

將尾結點r->next=NULL;改為r->next=h;

（三）雙向鏈表

1.特點：兩個指針域，可用于表示樹型結構，一個指向前驅，一個指向后繼

2.結點類型：typedefstructdnode

{intdata;

structdnode*prior,*next;}DNODE;

3.結構：

h

4.建立雙鏈表（以0結束）

DNODE*creatd()

{DNODE*h,*p,*q;

intx;

h=p=(*DNODE)malloc(sizeof(DNODE));

scanf("%d",&x);

while(x!=0)

{q=(*DNODE)malloc(sizeof(DNODE));

q->data=x;

p->next=q;

q->prior=p;

p=q；

scanf("%d",&x);}

p->next=NULL;h->prior=NULL;

returnh;}

5.在雙鏈表的第I個結點之后后插入一新結點

voidinsertd(DNOD**h,intI,intx)

{DNODE*s,*p;

intj;

s=(DNODE*)malloc(sizeof(DNODE));

s->data=x;

if(I==0)

{s->next=*h;*h->prior=s;*h=s;*h->prior=NULL;}

else

{p=*h;

j=l;

while(p!=NULL&&j<i)

{j++;p=p->next;}

if(p!=NULL)

if(p->next==NULL)

{p->next=s;s->prior=p;s->next=NULL;}

else

{s->next=p->next;p->next->prior=s;s->prior=p;p->next=s;}

else

printf("Nofound\n");}}

6.刪除雙鏈表中值為x的結點

voiddelete(DNODE**h,intx)

{DNODE*p;

if(*h==NULL)printf("overflow\rT);

if(*h->data==x)

{p=*h;*h=*h->next;*h->prior=NULL;free(p);}

else

{p=*h->next;

while(p!=NULL&&p->data!=x)

p=p>>next;

if(p!=NULL)

if(p->next==NULL)

{p->prior->next=NULL;free(p);}

else

{p->prior->next=p->next;p->next->prior=p->prior;free(p);}

else

printf("Nofound\n");}}

第二章復習題

一、填空

1.在線性結構中元素之間存在一對一關系,第一個結點皿—前驅結點，其

余每個結點有且只有」一個前驅結點；最后一個結點沒有后繼結點,其余每個

結點有且只有個后繼結點。

2.線性結構的順序存儲結構是一種隨機存取的存儲結構,邏輯上相鄰的元素

物理位置上必緊臨；其鏈式存儲結構是一種現在在的存儲結構，邏輯上相

鄰的元素物理存儲位置不關連續(xù)。

——*2璉2E-徉￡Z.

1.在一個單鏈表中，若P所指結點不是最后結點，在P之后插入S所指結點,

則執(zhí)行（B）。

A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;

C.s->next=p->next;p=s;D.p->next=s;s->next=p;

2.在一個單鏈表中，若刪除p所指結點的后續(xù)結點，則執(zhí)行（A）o

A.p->next=p->next->next;B.p->next=p->next;

C.p=p->next;p->next=p->next->next;D.p=p->next->next;

3.在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之

間插入s結點，則執(zhí)行（C）。

A.s->next=p->next;p->next=s;

B.p->next=s->next;s->next=p;

C.s->next=p;q->next=s;

D.p->next=s;s->next=q;

4.非空的循環(huán)單鏈表頭指針為front,p指向尾結點，則應滿足（C）。

A.p->next==NULL;B.p二二NULL;C.p->next==front;D.p==front;

5.帶頭結點的單鏈表頭指針front為空的判定條件是（B）。

A.front==NULLB.front->next==NULL

C.front->next==frontD.front!=NULL

6.不帶頭結點的單鏈表頭指針front為空的判定條件是（A）。

A.front==NULLB.front->next==NULL

C.front一〉next二二frontD.front!=NULL

7.在循環(huán)雙鏈表的p所指結點之后插入s所指結點的操作是（D）0

A.p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

B.p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

C.s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;

D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;

8.在雙鏈表的p所指結點之前插入s所指結點的操作是（A）0

A.s->prior=p->prior;s->next=p;p->prior->next=s;p->prior=s;

B.s->next=p;s->prior=p->prior;p->prior=s;p->prior->next=s;

C.p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior;

D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;

9.刪除雙鏈表中p所指結點的操作是(C)o

A.p->prior=p->prior->prior;p->prior->next=p;free(p);

B.p->next=p->next->next;p->next->prior=p;free(p);

C.p->prior->next=p->next;p->next->prior=p->prior;free(p);

D.p->next->prior=p->prior;p->prior->next=p;free(p)

三、編程

1.含n個元素的順序表X按升序排列，刪除線性表中值介于a與b之間的元素。

voiddel(intx[],int*n,inta,intb)

{inti=0,k;

while(i<*n)

if(x[i]>a&&x[i]<b)

{for(k=i;k<*n;k++)

x[k]=x[k+l];

(*n)一;}

elsei++;}

2.含n個元素的順序表A按升序排列，刪除線性表中多余的值相同的元素。

intdel(inta[],intn)

{inti=0,j;

while(i<=n"l)

if(a[i]!=a[i+l])i++;

else

{for(j=i;j<n;j++)

a[j]=a[j+l];

n-;}

returnn;}

3.含n個元素的順序表A中元素按升序排列，插入一個元素x后，使A中元素

仍有序。

intinsert(inta[],intn,intx)

{inti,j;

if(x>=a[n-l])a[n]=x;

else{i=0;

while(x>=a[i]i++;

for(j=n-l;j>=i;j—)

a[j+l]=a[j];

a[i]=x;

n++;}

returnn;}

4.求單鏈表的長度

intcount(NODE*h)

{intn=0;

NODE*p;

p=h;

if(h==NULL)n=0;

else

while(p!=NULL)

{n++;p=p->next;}

returnn;}

第三章棧和隊列

要求、目標：

熟悉棧和隊列特點、數據結構的定義

掌握在棧上的各種操作、使用數組和鏈表實現棧

掌握用數組和鏈表實現隊列

掌握循環(huán)隊列的相關操作

一、棧

（-）概述

1.堆棧：只允許在表的一端進行插入和刪除操作的線性表。

2.棧頂：允許進行添加或刪除元素的一端

3.棧底：不允許進行添加或刪除元素的一端

4.空棧：沒有元素的棧

5.入棧（進棧/壓棧）（pus/l）：棧的插入運算

6.出棧（退棧/彈出）（pop）：棧的刪除運算

7.棧的特點：后進先出（LIFO）

is入

在棧中插入和刪除的示例

（-）棧的順序存儲結構

1.棧類型的定義

?defineSTACKMAX100

inttop;

intstack[STACKMAX];

2.棧的初始化

top值為下一個進棧元素在數組中的下標值，入棧操作是先壓棧再移動棧頂

指針，出棧操作是先移動棧頂指針再取出元素

1）?？?top==0

2）棧滿：top==STACKMAX

3.進棧與出棧順序

若進棧序列為a、b、c,則全部可能出棧的序列為（，一，表示進，’一，表示出）：

①afa-b—c—c—即abc

②afbfb—c—c-a―即bca

③a—a*b—cfc-b-即acb

④afbfb-a-c—c―即bac

⑤afb-*c~*c-b-a―即cba

4.判定棧是否為空

intempty()

{if(top==0)return1;

elsereturn0;}

5.壓棧的實現

inttop=0;

intpush(intx)

{if(top>=STACKMAX)rerurn1;

stack[top++]=x;

return0;}

6.出棧的實現

intpop(int*p)

{if(top==0)rreturn1;

*p=stack[—topi;

return0;}

7,讀棧頂元素

voidreadtop(int*p)

{if(top==0)printfC'Noelement\n")；

else*p=stack[—top];

top++;}

(三)棧的鏈式存儲結構

1.鏈棧：用線性鏈表表示的棧

2.棧頂指針：鏈棧的表頭指針

3.棧的變化

1)?？眨簍op==NULL

2)非空：top指向鏈表的第一個結點，棧底結點的指針域為空

?無棧滿情況

4.結點類型

typedefstructsnode

{intdata;

structsnode*next;}SNODE;

5.進棧的實現

SNODE*top=NULL;

voidpush_L(intx)

{SNODE*p;

p=(SNODE*)malloc(sizeof(SNODE));

p->data=x;

p->next=top;

top=p；}

6.判鏈棧是否為空

intempty_L(SNODE*top)

{if(top==NULL)return1;

elsereturn0;}

7.出棧的實現

intpop_L(SNODE*top,int*p)

{SNODE*q;

if(top==NULL)return1;

*p=top->data;

q=top;

top=top->next;

free(q);

return0;}

8.求鏈棧中結點的個數

intcount_L(SNODE*top)

{SNODE*p;

intn=0;

p=top;

while(p!=NULL)

{n++;p=p>next;}

returnn;}

(四)棧的應用

1.數數制轉換(十進制一八進制)

voidconvert()

{intx,n,m;

top=0;

scanf(u%d,,,&n);

while(n)

{m=push(n%8);

if(m)printf(overflow\n);

elsen/=8;}

while(!empty())

{m=pop(&x);

if(m)printfC'Noelement\n^^);

elseprintf("%d”,x);}}

2.表達式求值

1)算術表達式的中綴表示：運算符放在兩個操作數中間的算術表達式

例：a+b*c+d/e*f

2)中綴表示在計算機處理中的的問題

受括號、優(yōu)先級和結合律的限制，不一定按運算符出現的先后順序執(zhí)行，完

成運算需對表達式進行多遍掃描，浪費時間。

3)算術表達式的后綴表示(逆波蘭表示法)

例：a+b-ab+a*b-ab*

4)中綴表達式到后綴表達式的轉換規(guī)則

①找出最先運算的運算符，將其移至兩個操作數的后面，若有括號則刪掉

②把得到的后綴表達式作為一個整體放在原表達式中

③找下一個要運算的運算符，重復上述轉換直到所有運算符處理完畢

例：a+b*c-d/（e*f）fa+b*c-d/ef*fa+bc*-def*/fabc*+-def*/fabc*+def*/-

5.后綴表達式的求值

從左一右掃描，遇到運算符將該運算符前面兩個數取出運算，結果帶回后綴

表達式參與后面的運算，直到掃描到最后一個運算符并計算得最終結果

例：345/6*+2--30.86*+2--34.8+2--7.82--5.8

6.運用棧完成后綴表達式求值

運用棧保存操作數和結果，從左一右掃描，若為操作數則將其入棧，若為運

算符則彈出兩個數進行運算，并將結果入棧,直到掃描到表達式的最后一個字符,

棧頂的值為最終的結果。

7.運用棧完成中綴表達式到后綴表達式的轉換

運用棧保存運算符、取中綴表達式中的一字符，若為數字則輸出；

若為（則入棧；若為運算符當其優(yōu)先級高于棧頂運算符的棧中優(yōu)先級時則入棧，

否則棧頂運算符出棧并輸出；若為'）'則依次退出棧中運算符并輸出直到'（'，

將'（'退棧但不輸出；若為'\0'則依次退棧并輸出

二、隊列

（-）概述

1.隊列：只允許在表的一端進行插入操作而在另一端進行刪除操作的線性表

2.隊尾：允許進行插入操作的一端

3.隊首：允許進行刪除操作的一端

4.特點：先進先出（FIFO）

（二）隊列的順序存儲結構

1.順序隊列的類型

#defineQUEUEMAX100

charqueuefQUEUEMAX];

intfront,rear;

2.順序隊列的變化

front指向隊首元素的前一個位置，rear指向隊尾元素的位置，入隊操作是先

移動隊尾指針，再插入元素；出隊操作是先移動隊首指針，再取出元素

1)空：front==rear==-l

2)非空：rear>front

3)滿：rear==QUEUEMAX-1

3.判別隊列是否為空

intempty()

{if(front==rear)return1;

elsereturn0;}

4.初始化隊列

voidinit()

{intfront=-1,rear=-1;}

5.入隊的實現

intins_queue(charx)

{if(rear==QUEUEMAX-1)return1;

queue[++rear]=x;

return0;}

6.出隊的實現

intdel_queue(char*p)

{if(front==rear)return1;

*p=queue[++front];

return0;}

7.假溢出

1)假滿：當rear==QUEUEMAX-1時，數組前端有空閑單元，出現假滿

2)解決方案：

①一個元素出隊時，將所有元素依次向隊首方向移動一個位置，修改頭尾指針，

使空閑單元留在后面，此方案花費時間較多

②出隊時隊列不移動，當出現假溢出時，將所有元素依次向隊首方向移動，此方

案也要花費較多時間

③把隊列看作是?個首尾衍接的循環(huán)隊列，這是最有效的解決方案

（三）循環(huán)隊列

1.特點：空閑單元單元總是在尾指針后面，front指向隊首前一個位置

2.循環(huán)隊列的變化

隊列的隊首

隊列的隊尾

ARRAYMAX-1

CIRCULARMAX=16

CIRCULARMAX-1

隊列的隊首隊列的隊尾

I)仝隊：front==rear

2)隊滿：front==rear

3.問題：當隊列空和滿時條件相同，無法判定隊列是空還是滿

4.最好的解決方案

設置一個空閑單元，則可用單元為QUEUEMAX-1個，當判別隊列是否滿時,

確定rear的下一個單元的位置是否為front所指的單元

隊滿條件：(rear+1)%QUEUEMAX==front

隊空條件：rear==front

5.循環(huán)隊列指針的移動

插入或刪除元素時，指針按逆時針方向進1

隊首指針進1：front=(front+l)%QUEUEMAX

隊尾指針進1：rear=(rear+l)%QUEUEMAX

6.入隊的實現

intfront=0,rear=0;

intcir_ins_queue(charx)

{if((rear+l)%QUEUEMAX==front)return1;

rear=(rear+l)%QUEUEMAX;

queue[rear]=x;

return0;}

7.出隊的實現

intcir_del_queue(char*p)

{if(rear==front)return1;

front=(front+l)%QUEUEMAX;

*p=queue[front];

return0;}

(四)隊列的鏈式存儲結構

1.鏈隊：用線性鏈表表示的隊列

2.結構形式

front

rear

3.操作：在尾結點后插入，在首結點處刪除

4.結點類型：

typedefstructnode

{chardata;

structnode*next;}QNODE;

5.鏈隊的指針：QNODE*front,*rear;

6.隊列的變化

1)隊空：front==rear==NULL

2)非空：rear->next==NULL

7.入隊的實現

QNODE*front=NULL,*rear=NULL;

Voidins_queue_L(charx)

{QNODE*p;

p=(QNODE*)malloc(sizeof(QNODE));

p->data=x;

p->next=NULL;

if(front==NULL)front=p;

elserear->next=p;

rear=p;}

8.出隊的實現

intdel_queue_L(char*p)

{QNODE*q;

if(front==NULL)return1;

*p=front->data;

q=front;

front=front->next;

free(q);

return0;}

第三章復習題

一、填空

1.表達式a+b*c-d/(e*f)等價的后綴表達式為abc*+def*/-,后綴表達式

3452*/+2-的值為L4。

2.表達式a+(b-c)*d等價的后綴表達式為abc-d*+,后綴表達式345/6*+2-

的值為5.8。

3.設棧頂指針為下一個待壓入元素的下標值，則向棧中壓入元素的操作是先壓

入元素再移動棧頂指針，設隊首指針指向隊首元素的前一個位置，隊尾指針

指向隊尾元素，則對隊列進行出隊的操作是先移動隊首指針，再取出元素。

4.在循環(huán)隊列中，設隊首指針為front,隊尾指針為rear,共有M個單元，可

用的存儲單元數為MT,當front=rear時，判別隊列是空還是滿的解決辦法

是設置一個空閑單元，移動隊首指針的操作是front=(front+l)燦1。

5.棧和隊列都是具有線性結構的數據結構，棧的特點是后進先出，隊列的特

點是先進先出。

6.在一個循環(huán)隊列中隊首指針指向隊首元素的前一個位置，設隊首指針為

front,隊尾指針為rear,共有M個單元，則隊列為滿的條件是

(rear+1)惻==front,隊列為空的條件是rear==f~ronl。

7.棧和隊列都是操作受限的線性表，棧只能在棧頂插入和刪除元素,隊列只

能在隊尾插入元素在隊首刪除元素。使用循環(huán)隊列是一種解決順序存儲

的隊列假溢出問題的有效方法。

—*、

1.設有編號1,2,3的三輛列車，順序進入一個棧式結構的站臺，這三輛列車

開出車站的不可能的順序是(D)。

A.1,2,3B.3,2,1C.1,3,2D.3,1,2

2.若棧頂指針top指向棧頂元素的位置，棧的存儲單元數為m,則棧滿的條件

是(C)。

A.top==0B.top==-lC.top==m-lD.top==m

3.一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是(D)。

A.4,3,2,1B.1,4,3,2C.3,2,4,1D.1,2,3,4

4.在一個非空鏈隊中，假設front和rear分別為隊首和隊尾指針，則向隊列中

插入P所指結點的運算應執(zhí)行（B

A.front->next=p;rear=p;B.rear->next=p;rear=p;

C.rear->next=p;front=p;D.front->next=p;front=p;

5.若棧頂指針top指向下一個進棧元素的位置，棧的存儲單元數為m,則棧滿

的條件是（D）。

A.top==0B.top==-lC.top==m-lD.top==m

6.一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是（B）o

A.edcbaB.dceabC.decbaD.abcde

7.在一個鏈隊中，假設front和rear分別為隊首和隊尾指針，若用x保存被刪

結點的值，則刪除一個結點的運算應執(zhí)行（B）。

A.front=front->next;x=front->data;B.x=front->data;front=front->next

C.x=rear->data;rear=rear->next;D.rear=front->next;x=rear->data;

第四章串

要求、目標：

了解串的基本術語；

熟悉兩個串相等的充要條件及其特殊性，串的各種運算的實現；

掌握串的存儲結構，串的比較、連接、求串長、取子串的算法實現

一、基本概念

>,,,

1.串：由零個或多個字符組成的有限序列，記為：S=ala2-an（n>0）

2.子串：一個串中任意個連續(xù)字符組成的子序列。

3.主串：包含子串的字符串為主串

4.空串：含零個字符的串，其長度為0。形式：

5.空格串：由一個或多個空格字符組成的串，其長度為空格的個數

6.位置：字符在序列中的序號從左一右依次為：1,2,3,…，n

?子串在主串中的位置以子串的第一個字符在主串中的位置來表示

例：A=”"B=""C="DataStructure"D=''Bei"E=''Jing"F="BeiJing”

其長度分別為：A：0,B：1,C：14,D：3,E：4,F：8

D在F中的位置為1,E在F中的位置為5

7.長度：串中字符的個數

8.特殊性：數據元素是一個字符

9.兩個串相等的充要條件：長度相等且對應位置的字符相同

二、串的存儲

1.串的存儲方式：順序存儲和鏈式存儲

2.串的鏈式存儲的結點類型

typedefstructnode

{chardata;

structnode*next;}SNODE;

三、串的運算

1.求串長度

1)順序存儲的實現

intsjen(charstring[])

{intI;

for(I=0;string[I]!=,\O,;I++);

returnI;}

2)鏈式存儲的實現

intL_len(SNODE*h)

{SNODE*p=h;

intn;

for(n=0;p!=NULL;n++)

p=p->next;

returnn;}

2.串的比較

1)順序存儲的實現

ints_cmp(charsl[],chars2[])

{intj=0;

while(s1[j]==s2[j]&&s1[j]!=,\0,&&s2[j]!='\0')j++；

returnslfj]-s2fj];}

2)鏈式存儲的實現

intL_cmp(SNODE*hl,SNODE*h2)

{SNODE*pl,*p2;

pl=hl;

p2=h2;

while(pl->data==p2->data&&p1!=NULL&&p2!=NULL)

{pl=pl->next;p2=p2->next;}

if(p1==NULL&&p2==NULL)return0;

elseif(pl==NULL)return-1;

elseif(p2==NULL)return1;

else

returnp1->data-p2->data;}

3.串的連接

1)順序存儲的實現

#defineM100

ints_cat(charsl[],chars2[])

{intI,j,k;

I=strlen(sl);

j=strlen(s2);

if(I+j>=M)trturn1;

for(k=0;k<=j;k++)

sl[I+k]=s2[k];

return0;}

2)鏈式存儲的實現

voidL_cat(SNODE**hl,SNODE*h2)

{SNODE*p;

if(*sl==NULL)*sl=s2;

else

{pl=*sl;

while(pl->next!=NULL)

pl=pl->next;

pl->next=s2;}}

4.取子串

1)順序存儲的實現

ints_sub(charsl[],intI,intk,chars2[])

{intm;

if(I<11II>(m=strlen(s1)))return1;

if(k<OIII+k>m+l)return1;

for(m=0;m<k;m++)

s2[m]=sl[I-l+m];

s2[ml=,\0,;

return0;}

2)鏈式存儲的實現

intL_sub(SNODE*hl,intI,intk,SNODE**h2)

{SNODE*p,*q,*r;

intm;

if(I<lllI>(m=L_len(hl)))return1;

if(k<OIII+k>irn-l)return1;

if(k==O)*h2=NULL;

else

{p=sl；

for(m=l;m<I;m++)p=p->next;

q=(SNODE*)malloc(sizeof(SNODE));

q->data=p->data;

*s2=q;

r=q；

for(m=l;m<k;m++)

{p=p->next;

q=(SNODE*)malloc(sizeof(SNODE));

q->data=p->data;

r->next=q;

r=q;}

r->next=NULL;}

reurn0;}

第四章復習題

一、填空

1.串是一種特殊的線性表，其特殊性體現在串中每個元素是一個字符；兩個

串相等的充分必要條件是長度相等且對應位置的字符相同。

2.空格串是由一個或多個空格字符組成的串，其長度等于空格的個數。

3.串的兩種最基本的存儲方式是順序存儲方式和鏈接存儲方式。

4.空串是零個字符的串,其長度等于零。

一-*、地漁徉43t

1.設串S='ABCDEFG',t='HIJK',函數con(x,y)返回x和y串的連接串,

subs(s,i,j)返回串S的從序號i的字符開始的j個字符組成的子串，則

con(subs(s,4,2),con(t,subs(s,6,2)))的結果串是(A)0

A.DEHIJKFGB.DEFGHIJKC.DEHIFGJKD.FGDEHIJK

2.設串s='ASAMPLE',t='APP',函數subs(s,i,j)返回串S的從序號i的字

符開始的j個字符組成的子串，repl(s,sl,s2)返回用串s2替換串s中的子串

si,則repl(s,subs(s,3,4),t)的結果串是(B)。

A.ASAPPLEB.AAPPLEC.ASAMPAPPD.AAPP

3.以下敘述中正確的是(A)

A.串是一種特殊的線性表B.串的長度必須大于零

C.串中元素只能是字母D.空串就是空白串

第五章數組

要求、目標：

了解數組的基本基本概念、性質；

掌握二維數組以行序和列序為主序時此元素存儲地址的計算；

掌握矩陣的壓縮存儲、稀疏矩陣的三元組存儲及轉置運算的實現

一、概述

1.數組：具有相同數據類型的若干元素構成的有序集合

2.性質：

①元素個數固定；

②元素類型相同；

③每個元素有惟一的下標值；

④是隨機存取結構

3.二維數組的表示形式(mXn)

?二維數組可看作是一個線性表，其每個元素也是一個線性表

?多維數組的基本操作是存取元素和修改元素值，不能進行插入和刪除操作

“0,0…a0,n-\

A=：?：?

Q/n-1,0?",

二、數組的存儲(mXn)

1.一維數組的存儲

設有定義#define100

inta[M];則第i個元素的地址為：

Loc(ai)=Loc(a0)+i*d其中d為每個元素所占的字節(jié)數，OWiVM

2.二維數組的存儲

1)以行序為主序(第i行j歹U)的元素地址計算

①下標從0開始

loc(ai.j)=loc(ao,o)+(i*n+j)*d

例：設有floata[5][4];起始地址為2000,求a網⑵的地址

loc(a3,2)=loc(aoe)+(i*n+j)*d=2000+(3*4+2)*4=2056

②下標不從0開始(A?…dl,c2…d2])

loc(aj,j)=loc(aci,C2)+[(i-c1)*(d2-c2+l)+(j-c2)]*d

例：設有floata[-20…30,-30“?20],起始地址為200,求a[25][18]的地址

loc(a2548)=loc(a.2o1.30)+[(25+20)*(20+30+l)+(18+30)]*4

=200+「45*51+48]*4

=9572

2)以列序為主序(第i行j歹D的元素地址計算

①下標從0開始

loc(ai,j)=loc(ao,o)+(j*m+i)*d

例：設有floata[5][4];起始地址為2000,求a⑶⑵的地址

loc(a3,2)=loc(ao.o)+0*n+i)*d=2000+(2*5+3)*4=2052

②下標不從0開始(A[cl…dl,c2…d2])

loc(ai,j)=loc(aci,c2)+[(j-c2)*(dl-cl+l)+(i-c1)]*d

例：設有floata[-20…30,-30…20],起始地址為200,求a[-18][-25]的地址

loc(a.18,.25)=loc(a.2O1.3o)+[(-25+3O)*(3O+2O+1)+(-18+20)]*4

=200+[5*51+2]M

=1228

三、特殊矩陣的壓縮存儲

1.壓縮存儲：為多個值相同的非零元素只分配一個存儲空間，對零元素不分配

空間

2.特殊矩陣：值相同的非零元素或零元素的分布有一定規(guī)律的矩陣

3.對稱矩陣：若一個n階方陣A中的元素滿足出尸陽(0Wi,jWn-l)則稱其為n

階對稱矩陣

4.對角矩陣：若一個n階方陣滿足其所有非零元素都集中在以主對角線為中心

的帶狀區(qū)域中，則稱其為n階對角矩陣

5.三角矩陣的壓縮存儲(非對稱)

1)下三角矩陣：上三角(不包括主對角線)中的元素都是0的n階方陣

2)壓縮存儲方法

①只存儲下三角的元素，其余的0不存儲

②下三角矩陣的I?個元素壓縮到險土D個元素的存儲單元中，可用一維數組

2

s@??n(n+l)/2]存放下三:角矩陣中的元素

元素個數：1+2+3+...+"=7二2

2

③按行序為主序進行存儲

3)期的地址計算(行序i，j)

①與s[k]的對應關系

n{n+1)

2

當上三角為常數C時用此單元存放該常數

②計算地址

loc(ai,j)=loc(a0,o)+[+J]*d

例：下三角矩陣A[1…8,1…8]按行存儲，起始地址為1000,每個元素占4個

字節(jié)，求A[7,5]的地址

loc(a7.5)=loc(a0,o)+[(1)(<)+1)+(j-1)]*d

=1000+[6*(6+1)/2+4]*4

=1100

6.對角矩陣的壓縮存儲

1)特點：非零元素分布在主對角線和其它對角線上，其余元素為0

2)半帶寬：主對角線上面或下面的對角線條數，記為b

3)帶寬：所有對角線的條數，記為2b