在此幻燈片插入公司的徽標(biāo)從“插入”菜單選擇圖片找到徽標(biāo)文件單擊“確定”重新設(shè)置徽標(biāo)大小單擊徽標(biāo)內(nèi)任意位置?；諛?biāo)外部出現(xiàn)的方框是“調(diào)整控點(diǎn)”使用這些重新設(shè)置對(duì)象大小如果在使用尺寸調(diào)整控點(diǎn)前按下shift鍵，則對(duì)象改變大小但維持原比例。DATA1065865姓名學(xué)號(hào)成績班級(jí)李紅976105995機(jī)97.6ABCDEFG數(shù)據(jù)結(jié)構(gòu)dlmu21.什么是線性結(jié)構(gòu)？簡單地說，線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的序列。2.棧和隊(duì)列：特殊的線性表2．3棧和隊(duì)列dlmu32.3.1棧2.3.1.1棧的定義棧：限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表

(FILO)。a1a2….an進(jìn)棧出棧

棧頂

棧底設(shè)棧s=（a1，a2，...,ai，...，an），其中a1是棧底元素，棧頂（top)：允許插入和刪除的一端；棧底（bottom):不允許插入和刪除的一端。dlmu4棧的基本操作1、初始化2、進(jìn)棧3、退棧4、取棧頂元素5、判棧是否非空dlmu52.3.1.2棧的存儲(chǔ)結(jié)構(gòu)——順序棧、鏈棧topstacksizea2a1指示當(dāng)前棧頂?shù)奈恢胐lmu6用圖表示順序棧如下：

圖中的順序棧的最大容量當(dāng)前棧中元素個(gè)數(shù)棧頂指針總是指在棧頂元素的后面一個(gè)位置上。

dlmu7S[4]2310

10S[4]2310

30

25

10S[4]2310

40

30

25

10S[4]2310top=4toptop＝0s[top]=xtop=top+1toptop=stacksizetopdlmu8·進(jìn)棧算法#definestacksize100intpush(ints[],intx,int

*ptop){ inttop;

top=*ptop;

if(top==stacksize){printf("overflow");return(0);} else{

s[top]=x;

*ptop=++top; return(1); }}a2a3a4987654321a10topvoidmain(){ ints[100]={4}; inttop=1,result,i;

result=push(s,101,&top); if(result==1){printf("success!\n");printf("top=%d\n",top);} elseprintf("failure\n");

for(i=0;s[i]!='\0';i++) printf("%d",s[i]);}*ptop=top++;*ptop=top;top=top+1;S[top]=x;top=top+1;dlmu9退棧算法：intpop(ints[],int*ptop,int*py){ inttop; top=*ptop; if(top==0){printf("stackempty");return(0);} else{

--top; *py=s[top]; *ptop=top; return(1); }}a2a3a4987654321a10topvoidmain(){ staticints[20]={10,20,30}; inttop=3,result,y;

result=pop(s,&top,&y); if(result==1) {printf("success!\n"); printf("top=%d,y=%d",top,y);} elseprintf("failure");}溢出問題dlmu10x

∧S

進(jìn)棧算法

出棧算法用指針來實(shí)現(xiàn)的棧叫鏈棧。棧的容量事先不能估計(jì)時(shí)采用的存儲(chǔ)結(jié)構(gòu)。鏈棧的類型說明如下：typedefstructlnode{LElemTypedata；Structlnode

next；}lnode；（2）鏈棧dlmu11e∧SP進(jìn)棧算法VoidStatusPush(lnode*s,LElemTypee){p=(lnode*)malloc(sizeof(lnode));

p->data=e;p->next=s;s=p;}Sdlmu12x

S·出棧算法VoidStatusPop(lnode*s,LElemType*e){

if(s!=NULL){*e=s->data;s=s->next;}}sdlmu132.3.1.3棧的應(yīng)用(1)

過程的嵌套r主程序srrrs子過程1rst子過程2rst子過程3dlmu14例:voidprint(intw)for(i=1;i<=w;i++){inti;if(w!=0){print(w-1）；printf(“%3d”,w);printf(“\n”);

}}

(2)

遞歸算法：

1(n=0,1)n!=n(n-1)！(n>1)dlmu15遞歸調(diào)用執(zhí)行情況如下：主程序(1)print(w);w=3;3print(2);（1）w=3top(2)輸出：3,3,3w2print(1);（2）w=2（1）w=3top(3)輸出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)輸出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)輸出：2,2(2)2(1)3top(4)輸出：1(3)1(2)2(1)3top(2)輸出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0結(jié)束(1)dlmu162.3.2隊(duì)列（一種特殊的線性結(jié)構(gòu)，限定在一端插入，一端刪除）2.3.2.1隊(duì)列的定義與運(yùn)算

a1,

a2,

a3,

a4,…………

an-1,

an

隊(duì)列示意圖隊(duì)頭隊(duì)尾先進(jìn)先出FIFO隊(duì)列的主要運(yùn)算（1）設(shè)置一個(gè)空隊(duì)列；（2）插入一個(gè)新的隊(duì)尾元素，稱為進(jìn)隊(duì)；（3）刪除隊(duì)頭元素，稱為出隊(duì)；（4）讀取隊(duì)頭元素；dlmu172.3.2.2隊(duì)列的存儲(chǔ)結(jié)構(gòu)（1）順序存儲(chǔ)結(jié)構(gòu)(a)線性隊(duì)列e4e3

e3e2e1

3210(a)(b)(c)rear=front=-1（初始化）rearfrontrear+1=MAX(隊(duì)滿)frontrearrear=front（隊(duì)空）front=reardlmu18(b)循環(huán)隊(duì)列

rearfront

0123(3)隊(duì)空

front(1)一般情況rear

0123e4e3

(2)隊(duì)滿fronte3

e43012reare5隊(duì)滿條件：(rear+1)%MAX=frontrear=front（隊(duì)空）dlmu19循環(huán)隊(duì)列中加入一個(gè)元素的算法：intenqueue(intq[],intx,int*pf,*pr){intfront,rear;front=*pf;rear=*pr;if((rear+1)%MAX==front)return(0);else{rear=(rear+1)%MAX;

q[rear]=x;

*pr=rear;return(1);}}dlmu20循環(huán)隊(duì)列中刪除一個(gè)元素的算法：intdequeue(intq[],int*py,int*pf,*pr){intfront,rear;front=*pf;rear=*pr;

if((rear==front)return(0);else{front=(front+1)%MAX;

*py=q[front];

*pf=front;return(1);}}

dlmu21鏈隊(duì)列的類型定義：

typedefstructQnode{QElemTypedata;StructQnode

next;}Qnode,

QueuePtr;typedefstruct{

QueuePtrfront;//隊(duì)頭指針

QueuePtrrear;//隊(duì)尾指針

}LinkQueue;ana2a1

Q.frontQ.rear鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)dlmu22an^a2a1

Q.frontQ.reara1a2

e

^anQ.frontan^a2a1

Q.frontQ.rear

刪除

一個(gè)元素

添加一個(gè)元素Q.rearQ.reardlmu23鏈?zhǔn)疥?duì)列插入算法:（在隊(duì)尾加入）

voidEnQueue(LinkQueue&Q,QElemTypee){

p=(QueuePtr)malloc(sizeof(Qnode));

if(!p)printf(“ERROR”);

else{

p->data=e;

p->next=NULL;

Q.rear->next=p;Q.rear=p;

}}dlmu24刪除一個(gè)元