數(shù)據(jù)結(jié)構(gòu)教案

湖南涉外經(jīng)濟(jì)學(xué)院

教案

學(xué)院信息科學(xué)與工程學(xué)院

系/教研室軟件工程系

課程名稱數(shù)據(jù)結(jié)構(gòu)

主講教師鄒競(jìng)

湖南涉外經(jīng)濟(jì)學(xué)院

講授章節(jié)第12345講緒論

授課時(shí)數(shù)2

I

:教學(xué)目的：

91.了解數(shù)據(jù)結(jié)構(gòu)課程的重要性和課程的基本要求，以及本課程涵蓋的內(nèi)容；

2.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念；

3.理解算法描述和簡(jiǎn)單的算法分析。

I

教學(xué)內(nèi)容(講授提綱)

S++；

1從后序課(數(shù)據(jù)庫(kù)、操作系統(tǒng)、編譯原理、人工智能)的需要和考研兩方面介紹數(shù)據(jù)結(jié)構(gòu)課程

的重要性。

2通過(guò)三個(gè)例子講解數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。

3介紹基本概念：數(shù)據(jù)的三個(gè)層次，數(shù)據(jù)結(jié)構(gòu)的三個(gè)要素，數(shù)據(jù)結(jié)構(gòu)的分類，四種存

6儲(chǔ)結(jié)構(gòu)，抽象數(shù)據(jù)類型，算法，算法的五個(gè)特性，對(duì)算法設(shè)計(jì)的要求，算法描述和算法分析，時(shí)間復(fù)

雜度和空間復(fù)雜度。

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

方案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)

萬(wàn)案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內(nèi)層循環(huán)超過(guò)1oo萬(wàn)次，在某機(jī)器上運(yùn)行了50分鐘；方案2的if語(yǔ)句執(zhí)行525

次，運(yùn)行了2秒鐘，相差1500倍。

I

5算法分析舉例

(1)常量階：時(shí)間復(fù)雜度為。(1)

++X；

s=0;

I

語(yǔ)句頻度為1,時(shí)間復(fù)雜度為0(1)。

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

語(yǔ)句頻度為10000，時(shí)間復(fù)雜度為0(1)。

(2)對(duì)數(shù)階：時(shí)間復(fù)雜度為O(logn)

s=0;

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

語(yǔ)句頻度為logn，所以時(shí)間復(fù)雜度為O(logn)。

(3)線性階：時(shí)間復(fù)雜度為O(logn)

s=o；

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

s++;

語(yǔ)句頻度為n,所以時(shí)間復(fù)雜度為0(n)<,

(4)時(shí)間復(fù)雜度為O(nlogn)

s=0;

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

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

1++;

時(shí)間復(fù)雜度為O(nlogn)

(5)平方階：時(shí)間復(fù)雜度為O(logn)

s=0;

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

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

!s++;

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

s=0;

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

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

|s++；

語(yǔ)句頻度為n(n+1)/2，所以時(shí)間復(fù)雜度仍為0(M)。

(6)立方階：時(shí)間復(fù)雜度為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

)

說(shuō)明：各語(yǔ)句行后的數(shù)字是該語(yǔ)句重復(fù)執(zhí)行的次數(shù)；

本算法時(shí)間復(fù)雜度為0(n3)

6.空間復(fù)雜度

算法原地(就地)工作：

若所用額外存儲(chǔ)空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù)，則稱此算法為原地(就地)工作。

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn)：

1.重點(diǎn)是數(shù)據(jù)結(jié)構(gòu)的基本概念

2.難點(diǎn)是時(shí)間復(fù)雜度分析

教考方法、教學(xué)手段：一

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

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

作業(yè)、討論題、思考題：

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

最佳情況：比較2次，無(wú)移動(dòng)；最差情況：比較3次，7次移動(dòng)

參考資料：

1.陳守孔等著《算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》機(jī)械工業(yè)出版社2007

2.陳守孔等著《算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析》機(jī)械工業(yè)出版社2008

3?嚴(yán)蔚敏等著《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》清華大學(xué)出版社2005

4.D.E.Knuth著《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一、三卷管紀(jì)文譯國(guó)防出版社

教學(xué)目的：

講授章節(jié)第2講線性表一一順序表

授課時(shí)數(shù)2

。1.理解非空線性結(jié)構(gòu)的四個(gè)特征。

2.線性表是重要的線性結(jié)構(gòu)，要掌握線性表的定義。

I

3.掌握線性表的操作在順序表中的實(shí)現(xiàn)。

I

教學(xué)內(nèi)容(講授提綱)

I

非空線性結(jié)構(gòu)的四個(gè)特征。

■:1.

2.線性表的定義

3.給定線性表的邏輯結(jié)構(gòu)就可以設(shè)計(jì)算法：

■(1)遍歷線性表L

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

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

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

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

}SeqList;

I

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

I

4.線性表的順序表示和實(shí)現(xiàn)

■

#defineMAXSIZE100〃順序表的最大容量

I

I

；typedefstruct

{ElemType〃存放線性表的數(shù)組

EHAV/C1-7L1.

intlast;〃last是線性表的長(zhǎng)度

?5.線性表的操作在順序表中的實(shí)現(xiàn)。

I

I

(1)定義的線性表的10個(gè)操作在順序表中的實(shí)現(xiàn)。

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

I

6.幾個(gè)算法舉例：

■

(1)順序結(jié)構(gòu)線性表LA與LB的結(jié)點(diǎn)關(guān)鍵字為整數(shù)。LA與LB的元素按非遞減有序，線性

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

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

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

(3)已知長(zhǎng)度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫一時(shí)間復(fù)雜度為0(n)、空間

9復(fù)

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

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

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

試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面

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

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

(1)給出算法的基本設(shè)計(jì)思想。

(2)根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語(yǔ)言描述算法，關(guān)鍵之

處給出注釋。

(3)說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

|解答：

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

所求。

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

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

{elemtypet;//t和數(shù)組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段，即整個(gè)數(shù)組逆置

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

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

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

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

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn)：

重點(diǎn)是順序表的定義，基本操作的實(shí)現(xiàn)。

難點(diǎn)是高效算法設(shè)計(jì)，例如國(guó)家2010年碩士研究生入學(xué)考試算法題就有5種解法

教學(xué)方法、教學(xué)手段：

1.開(kāi)始到順序表中各種操作實(shí)現(xiàn)(45分鐘)

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

使用教具：計(jì)算機(jī)和投影儀

作業(yè)、討論題、思考題：

2.3分析在順序存儲(chǔ)結(jié)構(gòu)下插入和刪除結(jié)點(diǎn)時(shí)平均需要移動(dòng)多少個(gè)結(jié)點(diǎn)。

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

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

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

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

參考資料：

1.陳守孔等著《算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)

言版》機(jī)械工業(yè)出版社2007

2.陳守孔等著《算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析》

機(jī)械工業(yè)出版社2008

3?嚴(yán)蔚敏等著《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》清華大學(xué)出版社2005

4.D.E.Knuth著《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一、三卷管紀(jì)文譯國(guó)防出版社

講授章節(jié)第3講單鏈表

授課時(shí)數(shù)2

教學(xué)目的：

1從順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)，引出鏈表的必要性。

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

3.掌握線性表的操作在單鏈表中的實(shí)現(xiàn)。

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

5.了解單鏈表的應(yīng)用。

教學(xué)內(nèi)容(講授提綱)

1順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：

插入和刪除必須大量移動(dòng)兀素；必須預(yù)先確;E空間；表空間不易擴(kuò)充。

2.鏈表的類型定義。

typedefstructNode

{ElemTypedata;

structNode*next;

}LNode,*LinkedList;

幾個(gè)概念：結(jié)點(diǎn)，首兀結(jié)點(diǎn)，第一兀素結(jié)點(diǎn)，頭結(jié)點(diǎn)，指針，頭指針

3.掌握線性表的操作在單鏈表中的實(shí)現(xiàn)。

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()

{〃用頭插法建立帶頭結(jié)點(diǎn)的單鏈表

LinkedListL;

L=(LNode*)malloc(sizeof(LNode));〃申請(qǐng)結(jié)點(diǎn)

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

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

while(x!=flag)//flag為結(jié)束輸入的標(biāo)志

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

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

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

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

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

returnL;

)

(2)尾插法

LinkedListLinkedListCreat2()

{〃用尾插法建立帶頭結(jié)點(diǎn)的單鏈表

LinkedListL;

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

L->next=NULL;r=L;

seanf(&x);

while(x!=flag)〃設(shè)置結(jié)束標(biāo)志

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

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

r_>n〃在尾部插入新結(jié)

瞰P；點(diǎn)〃r指向新的尾結(jié)點(diǎn)

seanf(&x);

r->〃最后結(jié)點(diǎn)的指針域放空指

rwiM業(yè)ILL;針

)

(3)單鏈表的遍歷

voidprint(LinkedListla)〃非遞歸

{LinkedListp=la->next;

while(p)

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

p=p->next;

voidout(LinkedListp)〃遞歸

攸p)

}//end

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn)：

1.動(dòng)態(tài)存儲(chǔ)（單鏈表）的概念。

2?單鏈表的算法設(shè)計(jì)。

教學(xué)方法、教學(xué)手段：

1.鏈表的定義和基本操作的實(shí)現(xiàn)（45分鐘）

2?鏈表生成和鏈表應(yīng)用的算法設(shè)計(jì)（45分鐘）

使用教具：計(jì)算機(jī)和投影儀

作業(yè)、討論題、思考題：

2.1試述頭指針、頭結(jié)點(diǎn)、元素結(jié)點(diǎn)、首元結(jié)點(diǎn)的區(qū)別，說(shuō)明頭指針和頭結(jié)點(diǎn)的作用。

2.2分析順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)，說(shuō)明何時(shí)應(yīng)該利用何種結(jié)構(gòu)。

2.4為什么在單循環(huán)鏈表中常使用尾指針，若只設(shè)頭指針，插入元素的時(shí)間復(fù)雜度如何？

2.5在單鏈表、雙鏈表、單循環(huán)鏈表中，若知道指針p指向某結(jié)點(diǎn)，能否刪除該結(jié)點(diǎn)，時(shí)間復(fù)雜度如何？

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選擇題：在循環(huán)雙鏈表的*p結(jié)點(diǎn)之后插入*s結(jié)點(diǎn)的操作是（)

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設(shè)ha和hb分別是兩個(gè)帶頭結(jié)點(diǎn)的非遞減有序單鏈表的頭指針，試設(shè)計(jì)算法，將這兩個(gè)有序鏈

表合并成一個(gè)非遞增有序的單鏈表。要求使用原鏈表空間，表中無(wú)重復(fù)數(shù)據(jù)。

改：2.9設(shè)ha和hb分別是兩個(gè)帶頭結(jié)點(diǎn)的非遞減有序單鏈表的頭指針，試設(shè)計(jì)算法，將這兩個(gè)有

序鏈表合并成一個(gè)非遞減有序的單鏈表。要求使用原鏈表空間，表中無(wú)重復(fù)數(shù)據(jù)“

參考資料：

1.陳守孔等著《算法與數(shù)據(jù)結(jié)構(gòu)C

語(yǔ)言版》機(jī)械工業(yè)出版社2007

2.陳守孔等著《算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析》

機(jī)械工業(yè)出版社2008

3?嚴(yán)蔚敏等著《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》清華大學(xué)出版社2005

4.D.E.Knuth著《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一、三卷管紀(jì)文譯國(guó)防出版社

講授章節(jié)第4講循環(huán)鏈表雙鏈表

授課時(shí)數(shù)2

I

i

Q教學(xué)目的：

1?掌握循環(huán)鏈表引入的背景：從任一結(jié)點(diǎn)開(kāi)始可以訪問(wèn)鏈表中的全部結(jié)點(diǎn)。

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

教學(xué)內(nèi)容(講授提綱)

1.比較順序表和單鏈表操作的優(yōu)缺點(diǎn)，使用范圍。

2?介紹單循環(huán)鏈表。指出：?jiǎn)窝h(huán)鏈表往往只設(shè)尾指針。

3.講解兩個(gè)只設(shè)尾指針的單循環(huán)鏈表合并成一個(gè)單循環(huán)鏈表的例子。

4.雙鏈表的定義：

typedefstructDLNode

{ElemTypedata;

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

5.雙鏈表和雙循環(huán)鏈表是兩種鏈表。

6.線性表的操作在雙鏈表中的實(shí)現(xiàn)

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

但是在插入或刪除結(jié)點(diǎn)時(shí)，一個(gè)結(jié)點(diǎn)就要修改兩個(gè)指針域，所以要比單鏈表復(fù)雜。由于雙鏈表有兩個(gè)

指針域，求前驅(qū)和后繼都很方便。

6.算法設(shè)計(jì)舉例：

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

假設(shè)一個(gè)單循環(huán)鏈表，其結(jié)點(diǎn)含有三個(gè)域pre、data、next。其中data為數(shù)據(jù)域；pre為

0指針域，它的值為空指針(null)；next為指針域，它指向后繼結(jié)點(diǎn)。請(qǐng)?jiān)O(shè)計(jì)算法，將此表改成雙向

循環(huán)鏈表。

voidSToDouble(LinkedListla)

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

{la->next->pre=la;〃將結(jié)點(diǎn)la后繼的pre指針指向la

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

)

)"算法結(jié)束

(2)已知一雙向循環(huán)鏈表，從第二個(gè)結(jié)點(diǎn)至表尾遞增有序，(設(shè)a1<x<an)如下圖。試

編寫算法，將第一個(gè)結(jié)點(diǎn)刪除并插入表中適當(dāng)位置，使整個(gè)鏈表遞增有序

voidDinsert(DLinkedListL)

{s=L；//s暫存第一結(jié)點(diǎn)的指針

P=L->next；//將第一結(jié)點(diǎn)從鏈表上摘下

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

while(p->data<x)

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

s->next=p；〃插入原第一結(jié)點(diǎn)S

s->prior=p->prior；

p->prior->next=s；

p->prior=s;

〃算法結(jié)束

(3)鏈表的匹配逆置

L1與L2分別為兩單鏈表頭結(jié)點(diǎn)地址指針，且兩表中數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)域均為一個(gè)字

母。設(shè)計(jì)把L1中與L2中數(shù)據(jù)相同的連續(xù)結(jié)點(diǎn)順序完全倒置的算法。

LinkedListPatternlnvert(LinkedListL1,LinkedListL2)

{P=L1;//p是每趟匹配時(shí)L1中的起始結(jié)點(diǎn)前驅(qū)的指針

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;}〃對(duì)應(yīng)字母相等，指針后移。

else//失配時(shí)L1起始結(jié)點(diǎn)后移，L2從首結(jié)點(diǎn)開(kāi)始。

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

if(s==NULL”/匹配成功，這時(shí)p為L(zhǎng)1中與L2中首字母結(jié)點(diǎn)相同數(shù)據(jù)域結(jié)點(diǎn)//的前驅(qū)，

q為L(zhǎng)1中與L2最后一個(gè)結(jié)點(diǎn)相同數(shù)據(jù)域結(jié)點(diǎn)的后繼。

{r=p->next;〃r為L(zhǎng)1的工作指針，初始指向匹配的首字母結(jié)點(diǎn)。

p->next=q；〃將P與q結(jié)點(diǎn)的鏈接。

while(r!=q)；〃逐結(jié)點(diǎn)倒置。

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

r->next=p->next;〃將r所指結(jié)點(diǎn)倒置。

p_>next=r；

r=s;〃恢復(fù)r為當(dāng)前結(jié)點(diǎn)。

}

}一

elseprintf(JL2并未在L1中出現(xiàn)”

)〃算法結(jié)束

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn):

1.循環(huán)鏈表和雙鏈表的概念。

2.難點(diǎn)是循環(huán)鏈表和雙鏈表的應(yīng)用算法設(shè)計(jì)。

教學(xué)方法、教學(xué)手段：

1?循環(huán)鏈表和雙鏈表（45分鐘）

2.算法設(shè)計(jì)（45分鐘）

使用教具：計(jì)算機(jī)和投影儀

作業(yè)、討論題、思考題：

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

序。

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

2.12設(shè)計(jì)一算法，將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式各自僅有奇次

察或偶次舞項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間來(lái)構(gòu)造這兩個(gè)鏈表。

設(shè)循環(huán)鏈表表示的多項(xiàng)式的結(jié)點(diǎn)結(jié)構(gòu)為：

typedefstructnode

{intpower;〃幕

floatcoef;〃系數(shù)

〃其他信息

ElemTypeother;struct

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

nkedList:

2.18設(shè)la是帶頭結(jié)點(diǎn)的非循環(huán)雙向鏈表的指針，其結(jié)點(diǎn)中除有prior>data和next夕卜，還有一訪問(wèn)頻度域freq，

其值在鏈表初始使用時(shí)為0。當(dāng)在鏈表中進(jìn)行ListLocate（la，x）運(yùn)算時(shí)，若查找失敗，則在

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

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

的ListLocate（la，x）運(yùn)算的算法，返回找到結(jié)點(diǎn)的指針。

參考資料：

1?陳守孔等《算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》機(jī)械工業(yè)出版社2007

箸?陳守孔等著《算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析》機(jī)械工業(yè)出版社2008

3?嚴(yán)蔚敏等著《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》清華大學(xué)出版社2005

4.D.E.Knuth著《計(jì)算機(jī)程序設(shè)計(jì)技巧》第管紀(jì)文譯國(guó)防出版社

講授章節(jié)第5講線性表的算法設(shè)計(jì)舉例

授課時(shí)數(shù)2

教學(xué)目的：

1.以線性表為具體例子深刻理解線性結(jié)構(gòu)。

2.加深對(duì)算法設(shè)計(jì)的理解。

教學(xué)內(nèi)容(講授提綱)

1先.介紹線性表的應(yīng)用：一兀n次多項(xiàng)式的表示。

2.選擇題6——14

3.五個(gè)算法設(shè)計(jì)例子

(1)鏈表的逆置

(2)循環(huán)鏈表的分解

已知L為無(wú)頭結(jié)點(diǎn)單鏈表中第一個(gè)結(jié)點(diǎn)的指針，每個(gè)結(jié)點(diǎn)數(shù)據(jù)域存放一個(gè)字符，該字

符可能是央文子母子符或數(shù)子子符或其它子符，編與算法構(gòu)造一個(gè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示的線

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

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

在一個(gè)非遞減有序的線性表中，有數(shù)值相同的元素存在。若存儲(chǔ)方式為單鏈表，設(shè)計(jì)算法去掉

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

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

設(shè)head是帶頭結(jié)點(diǎn)的單鏈表的頭指針，試寫出算法，按遞增次序輸出單鏈表中各結(jié)點(diǎn)的數(shù)據(jù)元

素，并釋放結(jié)點(diǎn)所占的存儲(chǔ)空間。要求不允許使用數(shù)組作輔助空間。

(5)鏈表的分解

將單鏈表L1拆成二個(gè)鏈表，其中以L1為頭的鏈表保持原來(lái)向后的鏈接，另一個(gè)鏈表

的表頭為L(zhǎng)2，其鏈接方向與L1相反，L1包含原鏈表的奇數(shù)序號(hào)的結(jié)點(diǎn)，L2包含原鏈表

的偶物序號(hào)的結(jié)占。

本早節(jié)的教學(xué)重點(diǎn)、難點(diǎn)：

1?鏈表是本章重點(diǎn)。

2.難點(diǎn)是鏈表的算法設(shè)計(jì)。

教學(xué)方法、教學(xué)手段：

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

2.算法設(shè)計(jì)(60分鐘)

使用教具：計(jì)算機(jī)和投影儀

作業(yè)、討論題、思考題：

完成本章所留習(xí)題

參考資料：

1.陳守孔等著《算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》機(jī)械工業(yè)出版社

2007

2.陳守孔等著《算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析》機(jī)械工業(yè)出版社2008

3?嚴(yán)蔚敏等著《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》清華大學(xué)出版社2005

4.D.E.Knuth著《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一'三卷管紀(jì)文譯國(guó)防出版社

講授章節(jié)第6講棧

授課時(shí)數(shù)2

教學(xué)目的：

1理解棧和隊(duì)列仍屬于線性結(jié)構(gòu)，其操作是線性表操作的子集，是操作受限的線性表。但從數(shù)據(jù)

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

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

3.掌握棧的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，及在這兩種結(jié)構(gòu)下實(shí)現(xiàn)棧的操作。

4.棧的應(yīng)用：表達(dá)式求值。

教學(xué)內(nèi)容(講授提綱)

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

2?棧的抽象數(shù)據(jù)類型定義

3?順序棧及棧的操作在順序棧中的實(shí)現(xiàn)。

#defineMAXSIZE1024

typedefstruct

{ElemTypedata[MAXSIZE];

inttop;

}SeqStack；

4.雙向棧的定義和使用

#definem64

typedefstruct

{ElemTypedata[m];

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

JTStack;

5.鏈棧及棧的操作在順序棧中的實(shí)現(xiàn)。

typedefstructStackNode

{ElemTypedata;

structStackNode*next;

JStackNode,*LinkedStack;

6.棧的應(yīng)用

過(guò)程調(diào)用

遞歸

(1)使用棧進(jìn)行數(shù)制轉(zhuǎn)換十進(jìn)制轉(zhuǎn)為八進(jìn)制

voidconversion()

{〃把十進(jìn)制轉(zhuǎn)換為八進(jìn)制一一非遞歸

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

{〃把十進(jìn)制n轉(zhuǎn)換為八進(jìn)制--遞歸

計(jì)(n!=0)

|{Convert(n/8);

pritf("％d,n%8);

|}一

(2)中綴表達(dá)式的求值

算術(shù)表達(dá)式中運(yùn)算符(+,?,*,/等)的優(yōu)先規(guī)則

設(shè)置兩個(gè)工作棧：運(yùn)算符棧S1和操作數(shù)棧S2。S2存放表達(dá)式的運(yùn)算結(jié)果。

算法思想:

1首先置操作數(shù)棧S2為空棧，置運(yùn)算符棧的棧底為表達(dá)式的起始符#(優(yōu)先級(jí)最低)。

2依次讀人表達(dá)式的每個(gè)字符ch,直至表達(dá)式結(jié)束:

若ch是操作數(shù)，則進(jìn)S2棧；

|若ch是運(yùn)算符，若其優(yōu)先級(jí)不高于棧頂運(yùn)算符的優(yōu)先級(jí)時(shí)，則取出棧S2的棧頂和

次棧頂?shù)膬蓚€(gè)元素以及瓦5丁襁頂運(yùn)算符'，進(jìn)行租而的運(yùn)算>笄恪結(jié)果放入棧S2中；如

此下去，直至ch的優(yōu)先級(jí)高于棧頂運(yùn)算符的優(yōu)先級(jí)，將ch入S1棧。

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn)：

1.棧的概念和基礎(chǔ)知識(shí)。

2.難點(diǎn)：中綴表達(dá)式求值，

教學(xué)方法、教學(xué)手段：

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

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

使用教具：計(jì)算機(jī)和投影儀

作業(yè)、討論題、思考題：

3.1有五個(gè)數(shù)依次進(jìn)棧：1,2.3,4,5。在各種出棧的序列中，以3,4先出的序列有哪幾

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

3.2.路進(jìn)行列車調(diào)度時(shí)，常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)，若進(jìn)站的六輛列車順序?yàn)椋篖2,3,

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

|說(shuō)明為什么不能；如果能，說(shuō)明如何得到(即寫出“進(jìn)棧"或“出?！钡男蛄?。

3.14雙向棧S是在一個(gè)數(shù)組空間V[m]內(nèi)實(shí)現(xiàn)的兩個(gè)棧，棧底分別處于數(shù)組空間的兩端。試

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

指示棧號(hào)。

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

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

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

參考資料：

1.陳守孔等著《算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》機(jī)械工業(yè)出版社2007

2.陳守孔等著《算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析》機(jī)械工業(yè)出版社2008

3?嚴(yán)蔚敏等著《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》清華大學(xué)出版社2005

4.D.E.Knuth著《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一、三卷管紀(jì)文譯國(guó)防出版社

講授章節(jié)第7講棧的應(yīng)用遞歸

教學(xué)目的：

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

頂端。

授課時(shí)數(shù)2

0

2.掌握棧的應(yīng)用：中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式，并求值。

t

1

1

13.掌握遞歸過(guò)程的應(yīng)用。

1

1

1

1教學(xué)內(nèi)容(講授提綱)

1

■

■

11.棧的本質(zhì)是：LIFO。

1

1

1

12.中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式

1

a1

i概念：前級(jí)表達(dá)式中級(jí)表達(dá)式，后綴表達(dá)式+ab,a+b,ab+

I

1

I卜設(shè)中級(jí)表達(dá)式和后綴表達(dá)式分別在向量IFX和PFX申，用棧S實(shí)現(xiàn)中綴式轉(zhuǎn)為后綴

i

:式，對(duì)IFX中表達(dá)式從左到右掃描，設(shè)TOKEN是掃描讀到的符號(hào)，轉(zhuǎn)換算法可描述如下：

1

1

1棧初始化

1

o

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

1

1

1①?gòu)腎PX中取出下個(gè)TOKEN(數(shù)字、運(yùn)算符、左括號(hào)、右括號(hào))；

1

1

1②CASETOKENOF

1

I

I

1'('將TOKEN壓入棧S;

1

1

1艮棧并將退棧兀素送直到碰到左括號(hào)，

1PFX?

1

1

a左括號(hào)退棧不送PFX。

1

1

l操作數(shù)：將操作數(shù)直接送入PFX;

i

■

■操作符：如?？栈騎OKEN比棧頂元素優(yōu)先級(jí)高，將TOKEN進(jìn)棧；否則，退棧并

i

1

1

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

1

■

Q結(jié)束符號(hào)，連續(xù)退棧并送退棧元素到PFX，直至?？?。

1

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

1

1

1表達(dá)式轉(zhuǎn)換的簡(jiǎn)單方法

1

■

1

1中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式有三步：

1

1

■(1)加括號(hào)：將中綴表達(dá)式中所有的子表達(dá)式按計(jì)算規(guī)則用嵌套括號(hào)括起來(lái)；

1

a

i(2)移運(yùn)算符：順序?qū)⒚繉?duì)括號(hào)中的運(yùn)算符移到相應(yīng)括號(hào)的后面；

i

l

1

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

i

i

i

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

l

i

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

I

t

t

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

o

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

1

1

1(2)對(duì)后綴表達(dá)式求值

用實(shí)型數(shù)棧S存放計(jì)算后綴式的中間及最終結(jié)果，求值算法可描述如下。

P=L；〃設(shè)局部變量p=L

while(p)

{printf(p->data);//輸出結(jié)點(diǎn)的值

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

)

}//Outputs

3)利用棧消除任何遞歸

利用?？梢詫⑷魏芜f歸函數(shù)轉(zhuǎn)換成非遞歸的形式，其步驟大致如下：

入棧處理

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

數(shù)名'局部變量和返回地址。

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

修改確定本次遞歸調(diào)用時(shí)的實(shí)在參數(shù)之新值。

轉(zhuǎn)到函數(shù)的第一個(gè)語(yǔ)句。

退棧處理

若棧空，算法結(jié)束，執(zhí)行正常返回。

若棧不空，從棧中退出參變量賦給原來(lái)人棧時(shí)相對(duì)應(yīng)的參變量，并退出返回地址。

轉(zhuǎn)到執(zhí)行返回地址處的語(yǔ)句，繼續(xù)執(zhí)行。

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn)：

1.中綴表達(dá)式轉(zhuǎn)成前綴、后綴表達(dá)式,，并對(duì)兩種表達(dá)式求值。

2?用遞歸解決的問(wèn)題：?jiǎn)栴}的定義是遞歸的，數(shù)據(jù)結(jié)構(gòu)是遞歸的，以及問(wèn)題的解法是遞歸的，

掌握典型問(wèn)題的算法。將遞歸算法轉(zhuǎn)為非遞歸算法，特別是尾遞歸的消除。

教學(xué)方法、教學(xué)手段：

1.復(fù)習(xí)棧的基本概念、中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式并求值(45分鐘)

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

使用教具：計(jì)算機(jī)和投影儀

作業(yè)、討論題、思考題：

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)〃設(shè)棧中元素類型為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);}