湖南涉外經濟學院

教案

學院信息科學與工程學院

系/教研室軟件工程系

課程名稱數據結構

主講教師鄒競

湖南涉外經濟學院

講授章節第12345講緒論

授課時數2

I

:教學目的：

91.了解數據結構課程的重要性和課程的基本要求，以及本課程涵蓋的內容；

2.掌握數據結構的基本概念；

3.理解算法描述和簡單的算法分析。

I

教學內容(講授提綱)

S++；

1從后序課(數據庫、操作系統、編譯原理、人工智能)的需要和考研兩方面介紹數據結構課程

的重要性。

2通過三個例子講解數據結構研究的內容。

3介紹基本概念：數據的三個層次，數據結構的三個要素，數據結構的分類，四種存

6儲結構，抽象數據類型，算法，算法的五個特性，對算法設計的要求，算法描述和算法分析，時間復

雜度和空間復雜度。

4從百錢買百雞”(一百元錢買一百支筆”的算法例子說明選擇算法的重要性：

方案1:

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

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

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

?

it(i+j+k==100&&3*i+2*j+0.5*k==100)printf("i=%dj=%d，k=%d”,i,j,k)

萬案2：

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

for(j=0;j<=34-i;j++)if(3*i+2*j+(100-i-j)*0.5==100)printf("i=%d,j=%d,k=%d°,i-j-

0j)po

方案1內層循環超過1oo萬次，在某機器上運行了50分鐘；方案2的if語句執行525

次，運行了2秒鐘，相差1500倍。

I

5算法分析舉例

(1)常量階：時間復雜度為。(1)

++X；

s=0;

I

語句頻度為1,時間復雜度為0(1)。

for(j=1;j<=10000;++j){++x;s+=x;}

語句頻度為10000，時間復雜度為0(1)。

(2)對數階：時間復雜度為O(logn)

s=0;

forG=1;j<=n;j*=2)

語句頻度為logn，所以時間復雜度為O(logn)。

(3)線性階：時間復雜度為O(logn)

s=o；

for(j=1;jv=n;++j)

s++;

語句頻度為n,所以時間復雜度為0(n)<,

(4)時間復雜度為O(nlogn)

s=0;

for(j=1;j<=n;j*=2)

for(k=1;kv=n;++k)

1++;

時間復雜度為O(nlogn)

(5)平方階：時間復雜度為O(logn)

s=0;

for(j=1;j<=n;++j)

for(k=1;k<=n;++k)

!s++;

語句頻度為n2，所以口寸間復雜度為0(n2)。

s=0;

for(j=1;j<=n;j++)

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

|s++；

語句頻度為n(n+1)/2，所以時間復雜度仍為0(M)。

(6)立方階：時間復雜度為0(n》

例：矩陣乘法:nxn

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

for(j=0;j<n;j++)〃n(n+1)

{c[i]D]=0:〃M

for(k=0;k<n;j++)//n2(n+1)

c[i]U]=c[i]U]+a[i][k]*b[k]D];//n3

)

說明：各語句行后的數字是該語句重復執行的次數；

本算法時間復雜度為0(n3)

6.空間復雜度

算法原地(就地)工作：

若所用額外存儲空間相對于輸入數據量來說是常數，則稱此算法為原地(就地)工作。

本章節的教學重點、難點：

1.重點是數據結構的基本概念

2.難點是時間復雜度分析

教考方法、教學手段：一

1.介紹到算法概念（45分鐘）

2.算法分析和舉例（45分鐘）使用教具：計算機和投影儀

作業、討論題、思考題：

編寫最耳算法，從小到大依次輸出順序讀人的三個整數。要求：

最佳情況：比較2次，無移動；最差情況：比較3次，7次移動

參考資料：

1.陳守孔等著《算法與數據結構C語言版》機械工業出版社2007

2.陳守孔等著《算法與數據結構考研試題精析》機械工業出版社2008

3?嚴蔚敏等著《數據結構C語言版》清華大學出版社2005

4.D.E.Knuth著《計算機程序設計技巧》第一、三卷管紀文譯國防出版社

教學目的：

講授章節第2講線性表一一順序表

授課時數2

。1.理解非空線性結構的四個特征。

2.線性表是重要的線性結構，要掌握線性表的定義。

I

3.掌握線性表的操作在順序表中的實現。

I

教學內容(講授提綱)

I

非空線性結構的四個特征。

■:1.

2.線性表的定義

3.給定線性表的邏輯結構就可以設計算法：

■(1)遍歷線性表L

(2)合并線性表1:設La和Lb是元素屬于同一數據對象且非遞減有序的兩個線

g性表，現要求將兩個線性表合并成一個新的非遞減有序的線性表Lc。

(3)合并線性表2:設La和Lb是元素屬于同一數據對象的兩個線性表，試將線性表Lb合

并到線性表La中。要求Lb中元素和La中元素相同的不再合并。

}SeqList;

I

要分析為什么(2)和(3)的時間復雜度分別是。(m*n)和。

I

4.線性表的順序表示和實現

■

#defineMAXSIZE100〃順序表的最大容量

I

I

；typedefstruct

{ElemType〃存放線性表的數組

EHAV/C1-7L1.

intlast;〃last是線性表的長度

?5.線性表的操作在順序表中的實現。

I

I

(1)定義的線性表的10個操作在順序表中的實現。

(2)分析在插入和刪除操作中的時間復雜度。

I

6.幾個算法舉例：

■

(1)順序結構線性表LA與LB的結點關鍵字為整數。LA與LB的元素按非遞減有序，線性

表空間足夠大。試給出一種高效算法，將LB中元素合到LA中，使新的LA的元素仍保

持非遞減有序。高效指最大限度的避免移動元素。

(2)請寫一個算法將順序表(a1,…,an)逆置為(an,...,a1)。

(3)已知長度為n的線性表A采用順序存儲結構，請寫一時間復雜度為0(n)、空間

9復

雜度為0(1)的算法，該算法刪除線性表中所有值為item的數據元素。

(0(1)表示算法的輔助空間為常量)。

(4)設將n(n>1)個整數存放到一維數組R中。

試設計一個在時間和空間兩方面

|都盡可能高效的算法，將R中保存的序列循環左移P(0<P<n)個位置，即將R

中的數據由(X0,據，…,Xn-1)變換為(Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1)。要求：

(1)給出算法的基本設計思想。

(2)根據設計思想，采用C或C++或JAVA語言描述算法，關鍵之

處給出注釋。

(3)說明你所設計算法的時間復雜度和空間復雜度。

|解答：

(1)算法設計思想：按照下標。到P-1>P到n-1、0到n-1的順序，將這三段分別逆置，最后的結果即為

所求。

(2)voidleftshift(intR[],intp,intn)

〃將有n個元素的一維數組R的序列循環左移p(0<pvn)個位置

{elemtypet;//t和數組R中的元素具有相同類型

for(i=0;i<p/2;i++)//逆置O..p-1段

{t=R[i]；R[i]=R[p-1-i];R(p-1-i]=t;}

for(i=p;i<(n+p)/2;i++)//逆置p..n-1段

{t=R[i];R[i]=R[n-1-i+p];R[n-1-i+p]=t;}

for(i=0;i<n/2;i++)//逆置O..n-1段，即整個數組逆置

{t=R[i];R[i]=R[n-1-i];R[n-1-i]=t;}

}〃算法初始調用：leftshift(R,p,n)，各參數意義如上。

(3)算法執行了兩趟逆置，時間復雜度為0(n);用了一個輔助變量空間，空間復雜度為0(1)。

討論：若采用直接左移P位，空間復雜度仍為0(1)>但時間復雜度為O(np),

本章節的教學重點、難點：

重點是順序表的定義，基本操作的實現。

難點是高效算法設計，例如國家2010年碩士研究生入學考試算法題就有5種解法

教學方法、教學手段：

1.開始到順序表中各種操作實現(45分鐘)

2?順序表算法舉例(45分鐘)

使用教具：計算機和投影儀

作業、討論題、思考題：

2.3分析在順序存儲結構下插入和刪除結點時平均需要移動多少個結點。

原2.16順序表la與lb非遞減有序，順序表空間足夠大。試設計一種高效算法，將lb中元素合到

la中，使新的la的元素仍保持非遞減有序。高效指最大限度地避免移動元素-■

改為2.16順序表la非遞減有序，lb非遞增有序，順序表空間足夠大。試設計一種高效算法，將lb

中元素合到la中，使新的la的元素仍保持非遞減有序?高效指最大限度地避免移動元素。

參考資料：

1.陳守孔等著《算法與數據結構C語

言版》機械工業出版社2007

2.陳守孔等著《算法與數據結構考研試題精析》

機械工業出版社2008

3?嚴蔚敏等著《數據結構C語言版》清華大學出版社2005

4.D.E.Knuth著《計算機程序設計技巧》第一、三卷管紀文譯國防出版社

講授章節第3講單鏈表

授課時數2

教學目的：

1從順序存儲結構的優缺點，引出鏈表的必要性。

2.掌握鏈表的類型定義。

3.掌握線性表的操作在單鏈表中的實現。

4.掌握單鏈表的建立方法，特別是頭插法和尾插法。

5.了解單鏈表的應用。

教學內容(講授提綱)

1順序存儲結構的缺點：

插入和刪除必須大量移動兀素；必須預先確;E空間；表空間不易擴充。

2.鏈表的類型定義。

typedefstructNode

{ElemTypedata;

structNode*next;

}LNode,*LinkedList;

幾個概念：結點，首兀結點，第一兀素結點，頭結點，指針，頭指針

3.掌握線性表的操作在單鏈表中的實現。

ListInit(L)；ListLength(L)；

ListGet(LJ);ListLocate(L,x);

ListClear(L);ListEmpty(L)；

ListPrior(L,e)；ListNext(L,e)；

Listlnsert(L,i,e);ListDelete(LJ);

4.掌握單鏈表的建立方法，特別是頭插法和尾插法。

(1)頭插法

LinkedListLinkedListCreat1()

{〃用頭插法建立帶頭結點的單鏈表

LinkedListL;

L=(LNode*)malloc(sizeof(LNode));〃申請結點

L->next=NULL;〃初始化一個空鏈表，L為頭指針

seanf(&x);//x是和鏈表元素具有相同類型的變量

while(x!=flag)//flag為結束輸入的標志

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

p->data=x;n輸入元素值

p->next=L->next;〃鏈接到表中

L->next=p;〃插入到表頭

seanf(&x);〃讀入下一個元素的值

returnL;

)

(2)尾插法

LinkedListLinkedListCreat2()

{〃用尾插法建立帶頭結點的單鏈表

LinkedListL;

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

L->next=NULL;r=L;

seanf(&x);

while(x!=flag)〃設置結束標志

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

p->data=x;〃賦值元素值

r_>n〃在尾部插入新結

瞰P；點〃r指向新的尾結點

seanf(&x);

r->〃最后結點的指針域放空指

rwiM業ILL;針

)

(3)單鏈表的遍歷

voidprint(LinkedListla)〃非遞歸

{LinkedListp=la->next;

while(p)

{printf(；%c,p->data);//正序輸出

p=p->next;

voidout(LinkedListp)〃遞歸

攸p)

}//end

本章節的教學重點、難點：

1.動態存儲（單鏈表）的概念。

2?單鏈表的算法設計。

教學方法、教學手段：

1.鏈表的定義和基本操作的實現（45分鐘）

2?鏈表生成和鏈表應用的算法設計（45分鐘）

使用教具：計算機和投影儀

作業、討論題、思考題：

2.1試述頭指針、頭結點、元素結點、首元結點的區別，說明頭指針和頭結點的作用。

2.2分析順序存儲結構和鏈式存儲結構的優缺點，說明何時應該利用何種結構。

2.4為什么在單循環鏈表中常使用尾指針，若只設頭指針，插入元素的時間復雜度如何？

2.5在單鏈表、雙鏈表、單循環鏈表中，若知道指針p指向某結點，能否刪除該結點，時間復雜度如何？

2.6下面算法的功能是什么？

LinkedListUnknown（LinkedListla）

{LNode*q，

1（la&&la->next）

；{q=la;la=la->next;p=la;

〔while（p->next）p=p->next;

p->next=q;q->next=null;

}

卜eturnla;一

}

2.7選擇題：在循環雙鏈表的*p結點之后插入*s結點的操作是（)

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;

Cs->prior=p;s->next=p->next;p->next:=s;p->next->prior=s;

Ds->prior=p;s>next=p>next;p>next->prior=s;p->next=s;

原：2.9設ha和hb分別是兩個帶頭結點的非遞減有序單鏈表的頭指針，試設計算法，將這兩個有序鏈

表合并成一個非遞增有序的單鏈表。要求使用原鏈表空間，表中無重復數據。

改：2.9設ha和hb分別是兩個帶頭結點的非遞減有序單鏈表的頭指針，試設計算法，將這兩個有

序鏈表合并成一個非遞減有序的單鏈表。要求使用原鏈表空間，表中無重復數據“

參考資料：

1.陳守孔等著《算法與數據結構C

語言版》機械工業出版社2007

2.陳守孔等著《算法與數據結構考研試題精析》

機械工業出版社2008

3?嚴蔚敏等著《數據結構C語言版》清華大學出版社2005

4.D.E.Knuth著《計算機程序設計技巧》第一、三卷管紀文譯國防出版社

講授章節第4講循環鏈表雙鏈表

授課時數2

I

i

Q教學目的：

1?掌握循環鏈表引入的背景：從任一結點開始可以訪問鏈表中的全部結點。

2?掌握循環鏈表(單循環鏈表，雙循環鏈表)和雙鏈表。

教學內容(講授提綱)

1.比較順序表和單鏈表操作的優缺點，使用范圍。

2?介紹單循環鏈表。指出：單循環鏈表往往只設尾指針。

3.講解兩個只設尾指針的單循環鏈表合并成一個單循環鏈表的例子。

4.雙鏈表的定義：

typedefstructDLNode

{ElemTypedata;

structDLNode*prior,*next;}DLNode,*DLinkedList;

5.雙鏈表和雙循環鏈表是兩種鏈表。

6.線性表的操作在雙鏈表中的實現

凡涉及一個方向的指針時，如求長度，取元素，元素定位等，其算法描述和單鏈表基本相同。

但是在插入或刪除結點時，一個結點就要修改兩個指針域，所以要比單鏈表復雜。由于雙鏈表有兩個

指針域，求前驅和后繼都很方便。

6.算法設計舉例：

(1)將單循環鏈表改為雙循環鏈表

假設一個單循環鏈表，其結點含有三個域pre、data、next。其中data為數據域；pre為

0指針域，它的值為空指針(null)；next為指針域，它指向后繼結點。請設計算法，將此表改成雙向

循環鏈表。

voidSToDouble(LinkedListla)

{while(la->next->pre==null)

{la->next->pre=la;〃將結點la后繼的pre指針指向la

la=la->next；//la指針后移

)

)"算法結束

(2)已知一雙向循環鏈表，從第二個結點至表尾遞增有序，(設a1<x<an)如下圖。試

編寫算法，將第一個結點刪除并插入表中適當位置，使整個鏈表遞增有序

voidDinsert(DLinkedListL)

{s=L；//s暫存第一結點的指針

P=L->next；//將第一結點從鏈表上摘下

p->prior=L_>prior；p->prior->next=p:

while(p->data<x)

p=p->next;〃查插入位置

s->next=p；〃插入原第一結點S

s->prior=p->prior；

p->prior->next=s；

p->prior=s;

〃算法結束

(3)鏈表的匹配逆置

L1與L2分別為兩單鏈表頭結點地址指針，且兩表中數據結點的數據域均為一個字

母。設計把L1中與L2中數據相同的連續結點順序完全倒置的算法。

LinkedListPatternlnvert(LinkedListL1,LinkedListL2)

{P=L1;//p是每趟匹配時L1中的起始結點前驅的指針

q=L1->next；//q是L1中的工作指針。

s=L2->next；//s是L2中的工作指針。

while(p!=null&&s!=null)

if(q->data==s->data)

{q=q->next;s=s->next;}〃對應字母相等，指針后移。

else//失配時L1起始結點后移，L2從首結點開始。

{P=P>next；q=p>next；s=L2>next；}

if(s==NULL”/匹配成功，這時p為L1中與L2中首字母結點相同數據域結點//的前驅，

q為L1中與L2最后一個結點相同數據域結點的后繼。

{r=p->next;〃r為L1的工作指針，初始指向匹配的首字母結點。

p->next=q；〃將P與q結點的鏈接。

while(r!=q)；〃逐結點倒置。

{s=r->next；〃暫存r的后繼。

r->next=p->next;〃將r所指結點倒置。

p_>next=r；

r=s;〃恢復r為當前結點。

}

}一

elseprintf(JL2并未在L1中出現”

)〃算法結束

本章節的教學重點、難點:

1.循環鏈表和雙鏈表的概念。

2.難點是循環鏈表和雙鏈表的應用算法設計。

教學方法、教學手段：

1?循環鏈表和雙鏈表（45分鐘）

2.算法設計（45分鐘）

使用教具：計算機和投影儀

作業、討論題、思考題：

2.10設la是一個雙向循環鏈表，其表中元素遞增有序。試寫一算法插入元素x，使表中元素依然遞增有

序。

改為：設la是一個雙向循環鏈表，其表中元素遞減有序。試寫一算法插入元素x，使表中元素依然遞減有序。

2.12設計一算法，將一個用循環鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式各自僅有奇次

察或偶次舞項，并要求利用原鏈表中的結點空間來構造這兩個鏈表。

設循環鏈表表示的多項式的結點結構為：

typedefstructnode

{intpower;〃幕

floatcoef;〃系數

〃其他信息

ElemTypeother;struct

node*next;}PNode,*PolyLi〃指向后繼的指針

nkedList:

2.18設la是帶頭結點的非循環雙向鏈表的指針，其結點中除有prior>data和next夕卜，還有一訪問頻度域freq，

其值在鏈表初始使用時為0。當在鏈表中進行ListLocate（la，x）運算時，若查找失敗，則在

表尾插入值為X的結點：若查找成功，值為x的結點的freq值增1，并要求鏈表按freq域值非增（遞減）

的順序排列，且最近訪問的結點排在頻度相同的結點的后面，使頻繁訪問的結點總是靠近表頭。試編寫符合上述要求

的ListLocate（la，x）運算的算法，返回找到結點的指針。

參考資料：

1?陳守孔等《算法與數據結構C語言版》機械工業出版社2007

箸?陳守孔等著《算法與數據結構考研試題精析》機械工業出版社2008

3?嚴蔚敏等著《數據結構C語言版》清華大學出版社2005

4.D.E.Knuth著《計算機程序設計技巧》第管紀文譯國防出版社

講授章節第5講線性表的算法設計舉例

授課時數2

教學目的：

1.以線性表為具體例子深刻理解線性結構。

2.加深對算法設計的理解。

教學內容(講授提綱)

1先.介紹線性表的應用：一兀n次多項式的表示。

2.選擇題6——14

3.五個算法設計例子

(1)鏈表的逆置

(2)循環鏈表的分解

已知L為無頭結點單鏈表中第一個結點的指針，每個結點數據域存放一個字符，該字

符可能是央文子母子符或數子子符或其它子符，編與算法構造一個以帶頭結點的單循環鏈表表示的線

性表，使每個表中只含同一類字符。(要求用最少的時間和最少的空間)

(3)刪除有序鏈表中的重復元素

在一個非遞減有序的線性表中，有數值相同的元素存在。若存儲方式為單鏈表，設計算法去掉

數值相同的元素，使表中不再有重復的元素。分析算法的時間復雜度。

(4)按序輸出鏈表中各元素

設head是帶頭結點的單鏈表的頭指針，試寫出算法，按遞增次序輸出單鏈表中各結點的數據元

素，并釋放結點所占的存儲空間。要求不允許使用數組作輔助空間。

(5)鏈表的分解

將單鏈表L1拆成二個鏈表，其中以L1為頭的鏈表保持原來向后的鏈接，另一個鏈表

的表頭為L2，其鏈接方向與L1相反，L1包含原鏈表的奇數序號的結點，L2包含原鏈表

的偶物序號的結占。

本早節的教學重點、難點：

1?鏈表是本章重點。

2.難點是鏈表的算法設計。

教學方法、教學手段：

1.基本概念和算法(30分鐘)

2.算法設計(60分鐘)

使用教具：計算機和投影儀

作業、討論題、思考題：

完成本章所留習題

參考資料：

1.陳守孔等著《算法與數據結構C語言版》機械工業出版社

2007

2.陳守孔等著《算法與數據結構考研試題精析》機械工業出版社2008

3?嚴蔚敏等著《數據結構C語言版》清華大學出版社2005

4.D.E.Knuth著《計算機程序設計技巧》第一'三卷管紀文譯國防出版社

講授章節第6講棧

授課時數2

教學目的：

1理解棧和隊列仍屬于線性結構，其操作是線性表操作的子集，是操作受限的線性表。但從數據

類型的角度看，它們是和線性表大不相向的重要抽象數據類型。

2.掌握棧的定義及操作。棧是只準在一端進行插入和刪除操作的線性表，該端稱為棧的頂端。

3.掌握棧的順序和鏈式存儲結構，及在這兩種結構下實現棧的操作。

4.棧的應用：表達式求值。

教學內容(講授提綱)

1.棧的基本概念：棧、棧頂、棧尾，棧只在棧頂操作。

2?棧的抽象數據類型定義

3?順序棧及棧的操作在順序棧中的實現。

#defineMAXSIZE1024

typedefstruct

{ElemTypedata[MAXSIZE];

inttop;

}SeqStack；

4.雙向棧的定義和使用

#definem64

typedefstruct

{ElemTypedata[m];

inttop[2];〃top[0],top⑴分別是兩個棧的棧頂指針

JTStack;

5.鏈棧及棧的操作在順序棧中的實現。

typedefstructStackNode

{ElemTypedata;

structStackNode*next;

JStackNode,*LinkedStack;

6.棧的應用

過程調用

遞歸

(1)使用棧進行數制轉換十進制轉為八進制

voidconversion()

{〃把十進制轉換為八進制一一非遞歸

SeqStackS;intN;

S.top=-1;

scanf("％d,&N);

while(N)

|{S.data[++S.top]=N%8;

|N=N/8;一

while(S.top!=-1)

printf("%d',S.data{S}top

)

voidConvert(intn

{〃把十進制n轉換為八進制--遞歸

計(n!=0)

|{Convert(n/8);

pritf("％d,n%8);

|}一

(2)中綴表達式的求值

算術表達式中運算符(+,?,*,/等)的優先規則

設置兩個工作棧：運算符棧S1和操作數棧S2。S2存放表達式的運算結果。

算法思想:

1首先置操作數棧S2為空棧，置運算符棧的棧底為表達式的起始符#(優先級最低)。

2依次讀人表達式的每個字符ch,直至表達式結束:

若ch是操作數，則進S2棧；

|若ch是運算符，若其優先級不高于棧頂運算符的優先級時，則取出棧S2的棧頂和

次棧頂的兩個元素以及瓦5丁襁頂運算符'，進行租而的運算>笄恪結果放入棧S2中；如

此下去，直至ch的優先級高于棧頂運算符的優先級，將ch入S1棧。

本章節的教學重點、難點：

1.棧的概念和基礎知識。

2.難點：中綴表達式求值，

教學方法、教學手段：

1.棧的基本概念和順序棧(45分鐘)

2.鏈棧、中綴表達式求值(45分鐘)

使用教具：計算機和投影儀

作業、討論題、思考題：

3.1有五個數依次進棧：1,2.3,4,5。在各種出棧的序列中，以3,4先出的序列有哪幾

個。(3在4之前出棧)。

3.2.路進行列車調度時，常把站臺設計成棧式結構，若進站的六輛列車順序為：L2,3,

4,5,6,那么是否能夠得到435612,325641,154623和135426的出站序列，如果不能，

|說明為什么不能；如果能，說明如何得到(即寫出“進棧"或“出棧”的序列)。

3.14雙向棧S是在一個數組空間V[m]內實現的兩個棧，棧底分別處于數組空間的兩端。試

為此雙向棧設計棧初始化Init(S)、入棧Push(S,i,x)、出棧Pop(S,i)算法，其中i為0或1,用以

指示棧號。

3.18設稱正讀和反讀都相同的字符序列為“回文”，例如，“abba”和"abccba”是“回

文“'"abcde"和"ababab”則不是"回文"，試寫一個算法，判別讀人的一個以@為結

束符的字符序列是否是“回文”。

參考資料：

1.陳守孔等著《算法與數據結構C語言版》機械工業出版社2007

2.陳守孔等著《算法與數據結構考研試題精析》機械工業出版社2008

3?嚴蔚敏等著《數據結構C語言版》清華大學出版社2005

4.D.E.Knuth著《計算機程序設計技巧》第一、三卷管紀文譯國防出版社

講授章節第7講棧的應用遞歸

教學目的：

1.掌握棧的定義的本質：LIF。。棧是只準在一端進行插入和刪除操作的線性表，該端稱為棧的

頂端。

授課時數2

0

2.掌握棧的應用：中綴表達式轉為后綴表達式，并求值。

t

1

1

13.掌握遞歸過程的應用。

1

1

1

1教學內容(講授提綱)

1

■

■

11.棧的本質是：LIFO。

1

1

1

12.中綴表達式轉為后綴表達式

1

a1

i概念：前級表達式中級表達式，后綴表達式+ab,a+b,ab+

I

1

I卜設中級表達式和后綴表達式分別在向量IFX和PFX申，用棧S實現中綴式轉為后綴

i

:式，對IFX中表達式從左到右掃描，設TOKEN是掃描讀到的符號，轉換算法可描述如下：

1

1

1棧初始化

1

o

從左到右掃描向量IFX，重復下述兩步操作，直到表達式尾：

1

1

1①從IPX中取出下個TOKEN(數字、運算符、左括號、右括號)；

1

1

1②CASETOKENOF

1

I

I

1'('將TOKEN壓入棧S;

1

1

1艮棧并將退棧兀素送直到碰到左括號，

1PFX?

1

1

a左括號退棧不送PFX。

1

1

l操作數：將操作數直接送入PFX;

i

■

■操作符：如棧空或TOKEN比棧頂元素優先級高，將TOKEN進棧；否則，退棧并

i

1

1

1將退棧元素送入PFX，然后再將TOKEN與新棧頂元素比較之當遇到中綴表達式

1

■

Q結束符號，連續退棧并送退棧元素到PFX，直至棧空。

1

1舉例：將中綴表達式8-(3+5)*(5-6/2)轉為后綴表達式

1

1

1表達式轉換的簡單方法

1

■

1

1中綴表達式轉為后綴表達式有三步：

1

1

■(1)加括號：將中綴表達式中所有的子表達式按計算規則用嵌套括號括起來；

1

a

i(2)移運算符：順序將每對括號中的運算符移到相應括號的后面；

i

l

1

I(3)刪括號：刪除所有括號。

i

i

i

i例如，將中綴表達式8-(3+5)*(5-6/2)轉為后級表達式。按如上步驟：執行完上面第一步后

l

i

1為：(8-((3+5)*(5-(6/2))));

I

t

t

■執行完上面第二步后為：(8((35)+(5(62)/)-)*)-;

o

1執行完上面第三步后為：835+562/-*-。

1

1

1(2)對后綴表達式求值

用實型數棧S存放計算后綴式的中間及最終結果，求值算法可描述如下。

P=L；〃設局部變量p=L

while(p)

{printf(p->data);//輸出結點的值

|p=p->next;〃向里一層修改變量值

)

}//Outputs

3)利用棧消除任何遞歸

利用棧可以將任何遞歸函數轉換成非遞歸的形式，其步驟大致如下：

入棧處理

設一個工作棧代替遞歸函數中的棧，棧中每個記錄包括函數的所有參數：函

數名'局部變量和返回地址。

所有遞歸調用語句處，改寫成把形參、局部變量和返回地址入棧的語句。

修改確定本次遞歸調用時的實在參數之新值。

轉到函數的第一個語句。

退棧處理

若棧空，算法結束，執行正常返回。

若棧不空，從棧中退出參變量賦給原來人棧時相對應的參變量，并退出返回地址。

轉到執行返回地址處的語句，繼續執行。

本章節的教學重點、難點：

1.中綴表達式轉成前綴、后綴表達式,，并對兩種表達式求值。

2?用遞歸解決的問題：問題的定義是遞歸的，數據結構是遞歸的，以及問題的解法是遞歸的，

掌握典型問題的算法。將遞歸算法轉為非遞歸算法，特別是尾遞歸的消除。

教學方法、教學手段：

1.復習棧的基本概念、中綴表達式轉為后綴表達式并求值(45分鐘)

2.遞歸過程、消除遞歸(45分鐘)

使用教具：計算機和投影儀

作業、討論題、思考題：

3.7指出下面程序段的功能是什么？

(1)voiddemo1(SeqStackS)

{inti,arr[64],n=0;

while(IStackEmpty(S))arr[n++]=Pop(S);

for(i=0;i<n;i++)Push(S,arr[i]);

)

(2)voiddemo2(SeqStackS,intm)〃設棧中元素類型為int型

{intx;SeqStackT;

Stacklnit(T);

while(!StackEmpty(S))

if((x=Pop(S)!=m)Push(T,x);

while(!(StackEmpty(T)){x=Pop(T);Push(S,x);}