數(shù)據(jù)結(jié)構(gòu)(C語言)

廣東交通職業(yè)基數(shù)學(xué)院計算機系課件設(shè)計數(shù)據(jù)結(jié)構(gòu)〔C語言〕DATASTRUCTURE

教材數(shù)據(jù)結(jié)構(gòu)〔C語言〕曲建民劉元紅鄭陶然清華大學(xué)出版社參考教材1數(shù)據(jù)結(jié)構(gòu)〔C語言版〕嚴(yán)蔚敏吳偉民清華大學(xué)出版社2數(shù)據(jù)結(jié)構(gòu)題集〔C語言版〕嚴(yán)蔚敏吳偉民清華大學(xué)出版社課程特點及課時分配難度大綜合性強必須下苦功學(xué)習(xí)課程說明考試每周4節(jié)，共20周評分標(biāo)準(zhǔn)：平時成績20％〔包括考勤、課堂答復(fù)以下問題等〕、期中成績30％，期末成績50％教學(xué)內(nèi)容第一章緒論第二章線性表第三章棧和隊列第四章數(shù)組和串第五章樹

第六章圖第七章內(nèi)部排序第八章查找第九章文件第一章緒論主要知識點

數(shù)據(jù)處理的種類和能力

數(shù)據(jù)數(shù)值數(shù)據(jù)：數(shù)(整數(shù),實數(shù))非數(shù)值數(shù)據(jù)：字符字符串文字圖形圖象聲音數(shù)據(jù)：客觀對象的符號表示數(shù)學(xué)中的整數(shù)、實數(shù)，

課程名，地名、書名1.1什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)要解決的問題

數(shù)值問題與非數(shù)值問題1〕數(shù)值問題例1：游泳池的長len和寬wide，求面積area◆設(shè)計求解問題的方法◆編程main(){ intlen,wide,area;

scanf(“%d%d%\n〞,&l,&w);

area=len*wide;

printf(“area=%d〞,area);}◆建模型：

問題涉及的對象：游泳池的長len寬wide，面積area；

對象之間的關(guān)系：area=len

wide1.1什么是數(shù)據(jù)結(jié)構(gòu)

學(xué)號姓名性別出生日期籍貫入學(xué)成績所在班級00201

楊潤生男82/06/01廣州56100計算機2

00102石磊男83/12/21汕頭51200計算機1

00202李梅女83/02/23陽江53200計算機200301馬耀先男82/07/12廣州50900計算機32〕非數(shù)值問題例2某級學(xué)生情況,要求分班按入學(xué)成績排列順序。在這類文檔管理的數(shù)學(xué)模型中,計算機處理的對象之間通常存在著一種最簡單的線性關(guān)系,這類數(shù)學(xué)模型稱為線性模型。1.1什么是數(shù)據(jù)結(jié)構(gòu)城市間交通網(wǎng)問題1.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的研究問題：非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，及如何表示，如何存儲，如何處理。本課程討論的問題：應(yīng)用中常用的幾種數(shù)據(jù)間的結(jié)構(gòu)關(guān)系，及如何表示,如何存儲，如何處理。1.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：客觀對象的符號表示。例如：學(xué)號，姓名，班名都是數(shù)據(jù)。數(shù)據(jù)元素：數(shù)據(jù)的根本單位。相當(dāng)于“記錄〞,在計算機程序中通常作為一個整體考慮和處理數(shù)據(jù)項:相當(dāng)于記錄的“域〞,是數(shù)據(jù)的不可分割的最小單位。如：學(xué)號數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合.例如:所有班名相同的記錄集合數(shù)據(jù)結(jié)構(gòu)：是相互間存在關(guān)系的數(shù)據(jù)元素集合。對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問題：1〕數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的根本操作；

2〕數(shù)據(jù)的存儲結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)根本操作的實現(xiàn)；數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是具體關(guān)系的抽象。數(shù)據(jù)結(jié)構(gòu)的根本操作：指對數(shù)據(jù)結(jié)構(gòu)的加工處理數(shù)據(jù)的存儲結(jié)構(gòu)(物理結(jié)構(gòu))：數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示數(shù)據(jù)結(jié)構(gòu)根本操作的實現(xiàn)：根本操作在計算機上的實現(xiàn)〔方法)數(shù)據(jù)的邏輯結(jié)構(gòu)通常有四種根本結(jié)構(gòu)：集合線性結(jié)構(gòu)樹型結(jié)構(gòu)圖結(jié)構(gòu)一、運算加工型運算插入運算刪除運算更新運算應(yīng)用型運算查找運算讀取運算1.3運算、算法和算法分析二、算法及其描述

算法是對求解某個問題的步驟的一種描述方法或操作序列。算法的根本特征：

1〕輸入：0個或多個輸入；

2〕輸出：1個或多個輸出；

3〕有窮性：算法必須在有限步內(nèi)結(jié)束；

4〕確定性：組成算法的操作必須清晰無二義性。

5〕可行性：組成算法的操作必須能夠在計算機上實現(xiàn)。求兩個正整數(shù)m，n中的最大數(shù)MAX的算法〔1〕假設(shè)m>n那么max=m

〔2〕假設(shè)m<=n那么max=n例1.3運算、算法和算法分析描述算法的書寫規(guī)那么所有算法均以函數(shù)形式給出,算法的輸入數(shù)據(jù)來自參數(shù)表參數(shù)表的參數(shù)在算法之前均進行類型說明有關(guān)結(jié)點結(jié)構(gòu)的類型定義,以及全局變量的說明等均在算法之前進行說明1.3運算、算法和算法分析評價算法標(biāo)準(zhǔn)算法的正確性，易讀性，可維護性，健壯性，高效率等。算法時間復(fù)雜度T〔n〕

本課程采用以求解問題的根本操作的執(zhí)行次數(shù)作為算法時間的度量算法的空間復(fù)雜度S(n)一個算法所需要輔助存儲空間的多少為空間復(fù)雜度O〔n3〕稱為矩陣相乘算法時間復(fù)雜度；O〔n3〕表示矩陣相乘算法執(zhí)行時間與n3成正比,即O〔n3〕與n3同一數(shù)量級；n階矩陣相乘的算法For(i=1;i<=n;i++)

For(j=1;j<=n;j++){c[i][j]=0;

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

c[i][j]+=a[i][k]*b[k][j]}

乘法加法執(zhí)行次數(shù)均為n3

例1.3運算、算法和算法分析有些算法，根本操作執(zhí)行次數(shù)與問題的輸入數(shù)據(jù)有關(guān)，這時可考慮

〔1〕算法平均時間復(fù)雜度

〔2〕算法在最壞情況下的時間復(fù)雜度算法的時間復(fù)雜度一般來說，設(shè)算法中根本操作的執(zhí)行次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間復(fù)雜度記作：

T(n)=O(f(n))

它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率與f(n)的增長率相同。1.3運算、算法和算法分析算法的時間復(fù)雜度為O(N3)

100元買100支筆,其中鋼筆3元/支,圓珠筆2元/支,鉛筆0.5元/支.寫算法輸出各種組合方案解法1#defineN100voidscheme(){inti,j,k,count,money;for(i=0;i<=N;i++)

for(j=0;j<=N;j++)for(k=0;k<=N;k++){count=i+j+k;money=3*i+2*j+0.5*k;

if(count==N&&money==N)printf(“%d,%d,%d\n%”,i,j,k);

}

}例1.3運算、算法和算法分析2算法空間復(fù)雜度

在本課程中，用執(zhí)行算法所需的輔助空間的大小作為算法所需空間的度量。

設(shè)執(zhí)行算法所需的輔助空間是問題規(guī)模n的某個函數(shù)g(n),那么算法空間復(fù)雜度記作：S〔n〕=O(g(n))表示算法輔助空間的增長率與g(n)的增長率相同1.3運算、算法和算法分析計算解法1先計算x的冪,存于power[]中,再分別乘以相應(yīng)的系數(shù)#defineN100floatevaluate(floatcoef[],floatx,intn){floatpower[N],f;inti;for(power[0]=1,i=1;i<=n;i++)power[i]=x*power[i-1];

for(f=0,i=0;i<=N;i++)f=f+coef[i]*power[i];return(f);}1.3運算、算法和算法分析例問題規(guī)模為n,算法時間復(fù)雜度:O(n)空間復(fù)雜度：O(N)解法2#defineN100floatevaluate(floatcoef[],floatx,intn){floatf;inti;for(f=coef[n],i=n-1;i>=0;i--)f=f*x+coef[i];return(f);}時間復(fù)雜度為O(n).空間復(fù)雜度為O(1)1.3運算、算法和算法分析第二章線性表2.1線性表的定義和根本運算2.2線性表的順序存儲結(jié)構(gòu)2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.1單鏈表

2.3.2循環(huán)鏈表

2.3.3雙向鏈表2.4線性表的應(yīng)用舉例主要內(nèi)容第二章線性表線性結(jié)構(gòu)特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個〞的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個〞的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼2.1線性表的邏輯結(jié)構(gòu)定義：一個線性表是n個數(shù)據(jù)元素的有限序列例英文字母表〔A,B,C,…..Z)是一個線性表數(shù)據(jù)元素特征：元素個數(shù)n—表長度，n=0空表1<i<n時ai的直接前驅(qū)是ai-1，a1無直接前驅(qū)ai的直接后繼是ai+1，an無直接后繼元素同構(gòu)，且不能出現(xiàn)缺項2.2線性表的順序存儲結(jié)構(gòu)順序表：定義：用一組地址連續(xù)的存儲單元存放一個線性表叫~元素地址計算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一個元素占用的存儲單元個數(shù)LOC(ai)—線性表第i個元素的地址特點：實現(xiàn)邏輯上相鄰—物理地址相鄰實現(xiàn)隨機存取實現(xiàn)：可用C語言的一維數(shù)組實現(xiàn)a1a2an01n-112n內(nèi)存V數(shù)組下標(biāo)元素序號M-1typedefintDATATYPE;#defineM1000DATATYPEdata[M];例typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];

備用空間數(shù)據(jù)元素不是簡單類型時,可定義結(jié)構(gòu)體數(shù)組動態(tài)申請和釋放內(nèi)存Datatype*pData=(DATATYPE*)malloc(M*sizeof(DATATYPE));free(pData);插入定義：線性表的插入是指在第I〔1in+1〕個元素之前插入一個新的數(shù)據(jù)元素x，使長度為n的線性表

變成長度為n+1的線性表需將第i至第n共〔n-i+1)個元素后移Ch2_1.c內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1an-1x算法時間復(fù)雜度T(n)設(shè)Pi是在第i個元素之前插入一個元素的概率，那么在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：算法刪除定義：線性表的刪除是指將第i〔1in〕個元素刪除，使長度為n的線性表

變成長度為n-1的線性表需將第i+1至第n共〔n-i)個元素前移Ch2_2.c內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標(biāo)01i-1n-2in-112i元素序號i+1n-1nanai+2算法評價設(shè)Qi是刪除第i個元素的概率，那么在長度為n的線性表中刪除一個元素所需移動的元素次數(shù)的平均次數(shù)為：故在順序表中插入或刪除一個元素時，平均移動表的一半元素，當(dāng)n很大時，效率很低算法順序存儲結(jié)構(gòu)的優(yōu)缺點優(yōu)點邏輯相鄰，物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點插入、刪除操作需要移動大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴充2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)特點：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息結(jié)點 數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲位置數(shù)據(jù)域指針域結(jié)點ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針實現(xiàn)typedefstructnode{

datatype

data;structnode

*link;}JD;JD*h,*p;datalinkp結(jié)點（*p）(*p)表示p所指向的結(jié)點(*p).data

p->data表示p指向結(jié)點的數(shù)據(jù)域(*p).link

p->link表示p指向結(jié)點的指針域生成一個JD型新結(jié)點：p=(JD*)malloc(sizeof(JD));系統(tǒng)回收p結(jié)點：free(p)2.3.1線性鏈表定義：結(jié)點中只含一個指針域的鏈表叫~，也叫單鏈表頭結(jié)點：在單鏈表第一個結(jié)點前附設(shè)一個結(jié)點叫~頭結(jié)點指針域為空表示線性表為空ha1a2頭結(jié)點an^…...h空表^單鏈表的根本運算查找：查找單鏈表中是否存在結(jié)點X，假設(shè)有那么返回指向X結(jié)點的指針；否那么返回NULL算法描述While循環(huán)中語句頻度為若找到結(jié)點X，為結(jié)點X在表中的序號否則，為npabxs算法評價插入：在線性表兩個數(shù)據(jù)元素a和b間插入x，p指向as->link=p->link;p->link=s;算法描述算法評價算法描述pabc算法評價刪除：單鏈表中刪除b，設(shè)p指向ap->link=p->link->link;動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針?biāo)惴枋鏊惴ㄔu價h頭結(jié)點an^0h頭結(jié)點an-10an^a2…...h頭結(jié)點an-10an^ha1a2頭結(jié)點an^…...0Ch2_3.ch頭結(jié)點0^單鏈表特點它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用不需預(yù)先分配空間指針占用額外存儲空間不能隨機存取，查找速度慢循環(huán)鏈表(circularlinkedlist)循環(huán)鏈表是表中最后一個結(jié)點的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高查找效率操作與單鏈表根本一致,循環(huán)條件不同單鏈表p或p->link=NULL循環(huán)鏈表p或p->link=Hhh空表雙向鏈表〔doublelinkedlist〕單鏈表具有單向性的缺點結(jié)點定義typedefstructnode{datatypeelement;structnode*prior,*next;}JD;priorelementnextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LABbcapp->prior->next=p=p->next->proir;bcaPvoiddel_dulist(JD*p){p->prior->next=p->next;

p->next->prior=p->prior;free(p);}刪除算法描述算法評價：T(n)=O(1)p->prior->next=p->next;p->next->prior=p->prior;voidins_dulist(JD*p,intx){JD*s;s=(JD*)malloc(sizeof(JD));s->element=x;

s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;}算法描述算法評價：T(n)=O(1)xSbaP插入1循環(huán)鏈表的概念

循環(huán)鏈表是線性表的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，它的特點是將線性鏈表的最后一個結(jié)點的指針指向鏈表的第一個結(jié)點2循環(huán)鏈表圖示(a)非空表〔b〕空表headheada1an2.3.2循環(huán)鏈表單向循環(huán)鏈表說明·在解決某些實際問題時循環(huán)鏈表可能要比線性鏈表方便些。如將一個鏈表鏈在另一個鏈表的后面；·循環(huán)鏈表與線性鏈表操作的主要差異是算法中循環(huán)結(jié)束的條件不是p或p->link是否為NULL,而是它們是否等于首指針；

·對循環(huán)鏈表，有時不給出頭指針，而是給出尾指針aa1an給出尾指針的循環(huán)鏈表2.3.2循環(huán)鏈表baa1anbb1bnaa1anb1bnqqppp=a->link;q=b->link;a->link=q->link;b->link=p;free(q);2.3.2循環(huán)鏈表1雙向鏈表的概念

(a)結(jié)點圖示數(shù)據(jù)域指針域指針域結(jié)點存儲數(shù)據(jù)元素data存儲后繼結(jié)點的地址next存儲前趨結(jié)點的地址prior

雙向鏈表中，每個結(jié)點有兩個指針域，一個指向直接后繼元素結(jié)點，另一個指向直接前趨元素結(jié)點。2.3.3雙向鏈表2雙向鏈表圖示head

(b)空的雙向循環(huán)鏈表（c）非空的雙向循環(huán)鏈表headabtypestructdulnode*pointer;Typestructdulnode{datatypedata;pointerprior,next;}dulnode;2.3.3雙向鏈表在雙向鏈表中刪除結(jié)點時指針變化情況在雙向鏈表中插入一個結(jié)點時指針的變化情況pai-1x①②③④aipaiai+1①②ai-13、雙向鏈表的根本操作算法2.3.3雙向鏈表p1〕插入操作算法(在p所指結(jié)點之后插入q結(jié)點的過程)

q=(NODE*)malloc(sizeof(NODE));q->data=x;q->rlink=p->rlink;q->llink=p;p->rlink=q;(q->rlink)->llink=q;2.3.3雙向鏈表2〕刪除操作算法(p->llink)->rlink=p->rlink;(p->rlink)->llink=p->llink;free(p);aiai+1p①②ai-12.3.3雙向鏈表2.4線性表的應(yīng)用舉例一元多項式的表示及相加一元多項式的表示：可用線性表P表示但對S(x)這樣的多項式浪費空間一般其中用數(shù)據(jù)域含兩個數(shù)據(jù)項的線性表表示其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表單鏈表的結(jié)點定義typedefstructnode{intcoef,exp;structnode*next;}JD;coefexpnext-1A703198517^-1B81227-98^-1C70111227517^一元多項式相加設(shè)p,q分別指向A,B中某一結(jié)點，p,q初值是第一結(jié)點比較p->exp與q->expp->exp<q->exp:p結(jié)點是和多項式中的一項p后移,q不動p->exp>q->exp:q結(jié)點是和多項式中的一項將q插在p之前,q后移,p不動p->exp=q->exp:系數(shù)相加0：從A表中刪去p,釋放p,q，p,q后移

0：修改p系數(shù)域,釋放q，p,q后移直到p或q為NULL若q==NULL，結(jié)束若p==NULL，將B中剩余部分連到A上即可運算規(guī)那么q-1pa703198517^-1pb81227-98^ppreq-1pa703198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppre-1pa70111227517^Ch2_7.c算法描述數(shù)據(jù)結(jié)構(gòu)第三章棧和隊列主要內(nèi)容

棧的定義棧的存儲結(jié)構(gòu)及其運算的實現(xiàn)棧是限定僅能在表尾一端進行插入、刪除操作的線性表〔a1,a2,...,ai-1,ai,ai+1,…,an〕插入刪除一

什么是棧3.1.1棧的定義第一個進棧的元素在棧底，

最后一個進棧的元素在棧頂，第一個出棧的元素為棧頂元素，最后一個出棧的元素為棧底元素。不含元素的棧稱為空棧。出棧Pop進棧Push棧頂棧底二.棧的邏輯結(jié)構(gòu)topbottom空棧topbottoman...a2a1bottomtopbottomtopAABCDEAB

棧操作圖示A進棧

BCDE進棧EDC出棧CDEtoptoptop棧的特點后進先出LIFO入棧與出棧topbottomtopbottomtoptoptop思考：假設(shè)有A,B,C三個元素進S棧的順序是A,B,C，寫出所有可能的出棧序列。CBAACBABCCABBACBCA如果是4個元素，那么它不可能的出棧序列有哪些？可能的出棧序列：

12431324134221342143231424313241321434214321不可能出現(xiàn)的出棧序列：

2413312434124123423142134312棧是一種線性表，它的特點是A。設(shè)用一維數(shù)組A[1，…，n]來表示一個棧，令A(yù)[n]為棧底。用整型變量T指示當(dāng)前棧頂位置，A[T]為棧頂元素。往棧中推入〔PUSH〕一個新元素時，變量T的值B，從棧中彈出〔POP〕一個元素時，變量T的值C。設(shè)?？諘r，有輸入序列a,b,c，經(jīng)過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素序列是D，變量T的值是E。A：1〕先進先出2)后進先出3〕進優(yōu)于出4〕出優(yōu)于進5〕隨機進出B、C：1〕加12〕減13〕不變4〕清05〕加26〕減2D：1〕a,b 2〕b,c3〕c,a4〕b,a5〕c,b6〕a,c E：1〕n+1 2〕n+23〕n4〕n-15〕n-2水平考試試題設(shè)有四個數(shù)據(jù)元素a1,a2,a3和a4，對它們進行棧操作。在進棧操作時，按a1、a2、a3、a4次序每次進入一個元素。假設(shè)棧的初始狀態(tài)都是空?，F(xiàn)要進行棧操作是進棧兩次，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是A，第二次出棧得到的元素是B經(jīng)操作后，最后在棧中的元素還有C個。供選擇的答案A：1〕a12〕a23〕a3 4〕a4B：1〕a12〕a23〕a3 4〕a4 C：1〕12〕23〕3 4〕0水平考試試題棧屬于加了限制條件的線性結(jié)構(gòu)；棧是后進先出的線性表；進棧和出棧只能從棧的一個端點進行；棧中的元素個數(shù)可以是0，此時是空棧；棧的元素的個數(shù)是可以變化的，可以是多個，但不能是無窮多個；每個棧中的元素的類型相同.棧的特性棧的應(yīng)用實現(xiàn)數(shù)制轉(zhuǎn)換實現(xiàn)函數(shù)的遞歸行編輯：接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)表達式求值：一個程序設(shè)計語言應(yīng)該允許設(shè)計者根據(jù)需要用表達式描述計算過程，編譯器那么應(yīng)該能分析表達式并計算出結(jié)果Flash演示三棧的根本操作

初始化IniStack(S):構(gòu)造一個空棧S，準(zhǔn)備存放數(shù)據(jù)；進棧操作Push(S,x)：將數(shù)據(jù)元素x插入棧S，使x成為S的棧頂元素；出棧操作Pop(S)：當(dāng)棧不空時返回棧頂元素為該函數(shù)的值，然后刪除棧頂元素；取棧頂元素GetTop(S)：當(dāng)棧不空時返回棧頂元素為該函數(shù)的值，但棧頂保持不變；判?？誆mptyStack(S)：假設(shè)S為空棧那么該函數(shù)值為1，否那么為0。一、棧的順序存儲結(jié)構(gòu)用一個一維數(shù)組和一個整型變量來實現(xiàn)。structstack{datatypearray[maxlen];inttop;}棧數(shù)組array[maxlen]用來存放棧中所有元素；整型變量top的整數(shù)值表示棧頂元素在數(shù)組array中的位置，也稱為棧頂指針。3.1.2棧的存儲結(jié)構(gòu)及其運算的實現(xiàn)約定棧頂指針指向向棧頂元素的位置當(dāng)棧用順序結(jié)構(gòu)存儲時，棧的基本操作如建空棧、進棧、出棧等操作如何實現(xiàn)？？順序棧的圖示topMAX-1nn-1n-210anan-1a2a1?？眨簵M：Top=-1Top=maxlen-11)初始化棧viodinitstack(structstacks){s.top=-1;}

MAX-1nn-1n-210建立空棧top2)進棧操作viodPush(structstacks,datatypex){s.top=s.top+1;s.array[top]=x；}

MAX-1nn-1n-210anan-1a2a1x進棧前topx進棧后MAX-1nn-1n-210topxanan-1a2a13〕出棧操作intpop(structstacks)

{return(array[s.top]);s.top--;}

出棧操作前MAX-1nn-1n-210anan-1a2a1top

出棧操作后MAX-1nn-1n-210anan-1a2a1top棧在運算過程中可能發(fā)生“溢出〞現(xiàn)象：上溢下溢topMAX-1nn-1n-210anan-1a2a1MAX-1nn-1n-210top2〕進棧操作viodPush〔structstacks,datatypex〕{

s.top=s.top+1;s.array[top]=x；

}if〔s.top=MAXlen-1〕error(“棧滿〞)else{}3〕出棧操作intpop〔structstacks〕

{return〔array[s.top]〕;s.top－－;}if〔s.top==-1〕Error〔“emptystack〞〕；else{}順序棧的缺乏：存在棧滿以后就不能再進棧的問題〔這是因為用了定長的數(shù)組存儲棧的元素〕解決方法：使用鏈?zhǔn)酱鎯Y(jié)構(gòu)。二、棧的鏈?zhǔn)酱鎯蛯崿F(xiàn)棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)，也稱鏈棧。其各結(jié)點的結(jié)構(gòu)與單鏈表中的結(jié)點結(jié)構(gòu)完全相同。如下圖：在前面學(xué)習(xí)了線性鏈表的插入刪除操作算法，不難寫出鏈?zhǔn)綏３跏蓟?、進棧、出棧等操作的算法結(jié)點結(jié)構(gòu)定義：Typedefstructnode{elemtypedata;structnode*next;}node,*pointer;Datanexts棧頂（單鏈表的表頭）棧底an-1a1an(1)初始化棧Voidinitstack〔pointers〕{s=null;}^sDatanexts棧頂棧底an-1a1anDatanext棧頂棧底an-1a1an

xps進棧前進棧后(2)進棧進棧算法Voidpush(pointers,datatypex){p=(pointer*)malloc(sizeof(node));p->data=x;p->next=s->next;s->next=p;}出棧前出棧后Datanext棧頂棧底an-1a1ansDatanextp棧頂棧底an-1a1an

xs

(3)出棧出棧算法Datatypepop(pointers){if(s->next==null)return(null);else{p=s->next;x=p->data;s->next=p->next;free(p);return(x);}}3.2.1隊列的定義隊列是限定僅能在表頭進行刪除，表尾進行插入的線性表〔a1,a2,...,ai-1,ai,ai+1,…,an〕插入刪除3.2隊列

a1a2a3……an入隊列隊頭隊尾出隊列隊列的示意圖隊列的特點先進先出說明：第一個入隊的元素在隊頭，

最后一個入隊的元素在隊尾，第一個出隊的元素為隊頭元素，最后一個出隊的元素為隊尾元素3.2隊列rearfrontJ1J2rearfrontJ2〔a)空隊列(b)J1,J2相繼入隊列(c)J1出隊(d)J3,J4和J5相繼入隊之后,J2出隊rearfront-101234rearfrontJ5J4J3front,rear均為整數(shù)用箭頭指示只是為了直觀又有J6入隊,怎么辦？

？3.2隊列3.2.2隊列的根本操作1〕初始化操作initQueue(Q)：建立一個空隊列Q，準(zhǔn)備存放數(shù)據(jù)；2〕入隊操作enQueue(Q,x)：將數(shù)據(jù)x插入到隊列Q的隊尾，隊列的長度加1；

3〕出隊操作outQueue(Q)：當(dāng)隊列為空時，返回隊列頭元素的值，同時刪除隊列頭元素，隊列的長度減1；4〕取隊頭元素操作GetQueue(Q)：當(dāng)隊列為空時，返回隊列頭元素的值，但不刪除隊列頭元素；

5〕判空操作：假設(shè)隊列為空，那么返回的值為1，否那么為0。3.2隊列3.2.3隊列的存儲結(jié)構(gòu)及其根本運算的實現(xiàn)1.鏈?zhǔn)酱鎯Y(jié)構(gòu)3.2隊列frontrear∧空鏈隊列a1∧fronta2∧鏈隊列圖示structnode//鏈隊列結(jié)點的類型定義

{intdata;

structnode*link;};typedefstructnodeNODENODE*front,*rear;1〕進隊列運算Voidaddqlink(intx){NODE*p;p=(NODE*)malloc(sizeof(NODE));p->data=x;p->link=NULL;rear->link=p;rear=p;}3.2隊列2〕出隊列運算NODE*deleqlink(){NODE*p;if(front==rear)return(NULL);p=front->link;front->link=p->link;if(front->link==NULL)rear=front;return(p);}3.2隊列3〕隊列的應(yīng)用1〕解決計算機主機與外設(shè)不匹配的問題；

2〕解決由于多用戶引起的資源競爭問題；3〕離散事件的模擬----模擬實際應(yīng)用中的各種排隊現(xiàn)象；

4〕用于處理程序中具有先進先出特征的過程；在操作系統(tǒng)課程中會講到3.2隊列2.順序存儲結(jié)構(gòu)將front和rear兩個整型變量作為c語言結(jié)構(gòu)體的兩個成員，該結(jié)構(gòu)體定義如下：Structsq_queue{Datatypedata[maxlen];Intfront,rear;}3.2隊列1)初始化運算initqueue〔structsq_queuesq〕得到一個長度為maxsize的空隊列sq，此時sq->front=0;sq->rear=0.2)進隊列運算enqueue〔structsq_queuesq,datatypex)sq->rear=sq->rear+1,sq->rear.data=x3)出隊列運算outqueue〔structsq_queuesq〕sq->front=sq->front-14)讀隊列頭元素運算gethead(structsq_queuesq〕返回的函數(shù)值為sq->rear.data,sq隊列沒有改變5〕判斷隊列是否是空emptyqueue(structsq_queuesq〕3.2隊列3.循環(huán)隊列frontrearJ6J4J5312405rear540312frontJ6J7J8J9J4J5frontrear540312(b)隊空(c)隊滿隊空、隊滿都有front=rear如何判斷循環(huán)隊列隊空、隊滿？

？J7rear3.2隊列有兩種方法：

1〕另設(shè)一個標(biāo)志位以區(qū)分隊空、隊滿。

2〕少用一個存儲單元，隊滿條件:front=rear+1;front540312J6J7J8J4J5〔d〕rear3.2隊列1〕初始化操作功能：建一個空隊列Q；算法：Intqueue[MAX];Intfront,rear;intInitQueue_Sq(){

//構(gòu)造一個空隊列Q

front=0;rear=0;

Return(1)}循環(huán)隊列的根本操作算法frontrear540312建一個空隊列Q3.2隊列2〕入隊操作功能：將元素x插入隊尾frontrear540312J1J3J2xfrontrear540312J1J3J2元素x入隊前元素x入隊后3.2隊列求余運算intinsert_queue(intx)/*入隊列*/{if((rear+1)%MAX==front)return(0);rear=(rear+1)%MAX;queue[rear]=x;return(1);}3〕出隊操作功能：刪除隊頭元素；

frontrear540312J1J3J2出隊操作前frontrear540312J1J3J2出隊操作后3.2隊列intdel_queue()/*出隊列*/

{if(rear==front)return(0);

front=(front+1)%MAX;

return(queue[front]);

}小結(jié)和作業(yè)作業(yè):課后習(xí)題1、2、3實訓(xùn)題：參見://第四章數(shù)組和串主要內(nèi)容4.1數(shù)組4.1.1數(shù)組的概念和運算4.1.2數(shù)組的順序存儲和訪問4.1.3矩陣的壓縮存儲4.2串4.2.1串的根本概念4.2.2串的根本運算4.2.3串的存儲結(jié)構(gòu)4.1.1數(shù)組的概念運算數(shù)組是由一組個數(shù)固定，類型相同的數(shù)據(jù)元素組成陣列。以二維數(shù)組為例：二維數(shù)組中的每個元素都受兩個線性關(guān)系的約束即行關(guān)系和列關(guān)系，在每個關(guān)系中，每個元素aij都有且僅有一個直接前趨，都有且僅有一個直接后繼。Am

n=a00

a01……a0n-1a10

a11……a1n-1

………………am-10

am-11……am-1n-1在行關(guān)系中aij直接前趨是aij-1aij直接后繼是aij+1在列關(guān)系中aij直接前趨是ai-1jaij直接后繼是ai+1j4.1數(shù)組 二維數(shù)組也可看作這樣的線性表：其每一個數(shù)據(jù)元素也是一個線性表 A=〔0,1,2,3,4,……,p) 其中每一個數(shù)據(jù)元素j是一個列向量的線性表 j=〔a0j,a1j,a2j,a3j,……,am-1j) 或i是一個行向量的線性表i=〔ai0,ai1,ai2,ai3,……,ain-1)4.1數(shù)組數(shù)組的根本操作訪問：給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素。修改：給定一組下標(biāo)，修改相應(yīng)數(shù)據(jù)元素中的某個數(shù)據(jù)項的值。 操作方法根據(jù)其存儲結(jié)構(gòu)決定4.1數(shù)組4.1.2數(shù)組的順序存儲和訪問一維數(shù)組在內(nèi)存中的存放很簡單，只要順序存放在連續(xù)的內(nèi)存單元即可。二維數(shù)組，如何用順序結(jié)構(gòu)表示？內(nèi)存地址是一維的，而數(shù)組是二維的，要將二維數(shù)組擠入一維的地址中，有兩個策略： 以行為主序〔C語言使用〕以列為主序4.1數(shù)組a00

a01……a0n-1a10

a11……a1n-1

………………am-10

am-11……am-1n-1設(shè)A是一個具有m行n列的元素的二維數(shù)組:以行為主序的方式：a00a01a0n-1

a10a11a1n-1am-11am-1n-101n-1nn+12n-1mn-1a00a10am-10

a01

a11am-11

a0n-1a1n-1

am-1n-101m-1mm+12m-1nm-1以列為主序的方式：Am

n=a00

a01……a0n-1a10

a11……a1n-1

………………am-10

am-11……am-1n-14.1數(shù)組4.1.3矩陣的壓縮存儲

一特殊矩陣的壓縮存儲二稀疏矩陣的壓縮存儲

1三元組表的存儲結(jié)構(gòu)2十字鏈表的存儲結(jié)構(gòu)4.1數(shù)組數(shù)組元素存儲地址的計算假設(shè)二維數(shù)組A每個元素占用s個存儲單元，Loc(aij)為元素aij的存儲地址，Loc(a00)是a00存儲位置,也是二維數(shù)組A的基址。假設(shè)以行序為主序的方式存儲二維數(shù)組，那么元素aij的存儲位置可由下式確定：Loc(aij)=Loc(a00)+〔ni+j)s假設(shè)以列序為主序的方式存儲二維數(shù)組，那么元素aij的存儲位置可由下式確定：Loc(aij)=Loc(a00)+〔mj+i)s一般在程序設(shè)計過程中，一維數(shù)組和二維數(shù)組使用較普遍，超過二維以上的多維數(shù)組使用相對較少，對于高維數(shù)組的順序存儲方法，可以將二維的情形加以推廣便能夠得到。4.1數(shù)組矩陣是許多科學(xué)與工程計算問題中常常涉及到的一種運算對象。一個m行n列的矩陣是一平面陣列，有m

n個元素。可以對矩陣作加、減、乘等運算。只有少數(shù)程序設(shè)計語言提供了矩陣運算。通常程序員是用二維數(shù)組存儲矩陣。由于這種存儲方法可以隨機地訪問矩陣的每個元素，因而能較為容易地實現(xiàn)矩陣的各種運算。4.1數(shù)組Am

n=a00

a01……a0n-1a10

a11……a1n-1

………………am-10

am-11……am-1n-1應(yīng)用中常遇到一些階數(shù)很高的矩陣，矩陣中有許多值相同的元素或零元素。二維數(shù)組存儲矩陣會浪費很多的存儲單元。例如，設(shè)一個10001000的矩陣中有800個非零元素，假設(shè)用二維數(shù)組存儲需要106個存儲單元。因此，需要使用高效的存儲方法，減少數(shù)據(jù)的存儲量，即對原矩陣，根據(jù)數(shù)據(jù)分布特征進行壓縮存儲。本章將討論兩類矩陣的壓縮存儲：1特殊矩陣的壓縮存儲

2稀疏矩陣的壓縮存儲4.1數(shù)組Am

n=a00

a01……a0n-1a10

a11……a1n-1

………………am-10

am-11……am-1n-1一特殊矩陣 值相同元素或者零元素分布有一定規(guī)律的矩陣稱為特殊矩陣?yán)簩ΨQ矩陣、上〔下〕三角矩陣都是特殊矩陣a00a10a20…an-10a10a11a21an-10an-11an-1n-1a00a01a0n-10

a11a1n-1000

an-1n-14.1數(shù)組

特殊矩陣壓縮存儲(以對稱矩陣為例)對稱矩陣是滿足下面條件的n階矩陣:

aij=

aji0

i,j

n-1

a00a01a0n-1a10a11a1n-1an-10an-11an-1n-1對稱矩陣元素可以只存儲下三角局部，共需n(n+1)/2個單元的空間(三角矩陣的存儲方式類似〕a00a10a11a20a21a22

an-10an-11an-1n-1a00

a10

a11

a20

a21a22

an-10an-11

an-1n-1k=012345n(n+1)/2-14.1數(shù)組k=i(i+1)/2+j當(dāng)i

jj(j+1)/2+i當(dāng)i

j以一維數(shù)組sa[]作為n階對稱矩陣A的存儲結(jié)構(gòu)，A中任意一元素aij與它的存儲位置sa[k]之間存在著如下對應(yīng)關(guān)系：a00

a10

a11

a20

a21a22

an-10an-11

an-1n-1k=012345n(n+1)/2-1例如，

a53在sa[]中的存儲位置是：k=5*(5+1)/2+3=18sa[18]=a534.1數(shù)組壓縮存儲的對稱矩陣的取值算法intget_M(inti,intj){if(i>=j)return(sa[i*(i+1)/2+j])elsereturn(sa[j*(j+1)/2+i]);}壓縮存儲的對稱矩陣的賦值算法voidassign_M(inti,intj,intvalue){if(i>=j)sa[i*(i+1)/2+j]=value;elsesa[j*(j+1)/2+i]=value;}4.1數(shù)組

帶狀矩陣

所有非0元素都集中在以主對角線為中心的帶狀區(qū)域，半帶寬為d時,非0元素有(2d+1)*n-(1+d)*d個a00a01a020

0

0

0

0

0

0

0

0

a10a11a12a130

0

00

0

0

0

0a20a21a22a23a24000

0

0

0

00

a31a32a33a34a3500

0

0

0

00

0

a42a43a44a45a460

0

0

0

00

0

0a53a54a55a56a5700

0

0

0

0

00

a64a65a66a67a680

0

00

00

0

0

a75a76a77a78a790

0

00

0

0

0

0a86a87a88a89a810

0

00

0

0

0

0

0

a97

a98a99a910a91100

0

0

0

0

0

0

a108a109a1010a101100

0

0

0

0

0

0

0

a119a1110a1111d4.1數(shù)組a00a010

0

0

a10a11a1200

0

a21a22a2300

0

a32a33a340

0

0a43a44K=01234567891011121314為計算方便，認(rèn)為每一行都有2d+1個非0元素，假設(shè)少那么用0補足，所以，存放矩陣的數(shù)組sa[]有n(2d+1)個元素數(shù)組元素sa[k]與矩陣元素aij之間有關(guān)系k=i*(2d+1)+d+(j-i)a00前為何放一個0？你會放d=2,n=6的帶狀矩陣嗎？？4.1數(shù)組0a00

a01

a10

a11a12a21a22a23a32a33a34a43a440壓縮存儲的帶狀矩陣的取值算法intget_Md(inti,intj){if(abs(i-j)<=d〕return(sa[i*(2*d+1)+d+(j-i)])；elsereturn(0);}壓縮存儲的帶狀矩陣的賦值算法voidassign_Md(inti,intj,intvalue){if(abs(i-j)<=d〕sa[i*(i+1)/2+j]=value;}4.1數(shù)組稀疏矩陣

1什么是稀疏矩陣

有較多值相同元素或較多零元素，且值相同元素或者零元素分布沒有一定規(guī)律的矩陣稱為稀疏矩陣。

例

A

=012900000000000-3000014000240000018000001500-7000A有42〔67〕個元素有8個非零元素如何進行稀疏矩陣的壓縮存儲？？4.1數(shù)組2稀疏矩陣的壓縮存儲〔只討論有較多零元素矩陣的壓縮存儲〕1〕三元組表〔i,j,aij)A=((0,1,12),(0,2,9),(2,0,-3),(2,5,14),(3,2,24),(4,1,18),(5,0,15),(5,3,-7))加上行、列數(shù)6，7A

=012900000000000-3000014000240000018000001500-7000表示非零元的三元組4.1數(shù)組2〕三元組順序表

假設(shè)以順序存儲結(jié)構(gòu)來表示三元組表，那么可得稀疏矩陣的一種壓縮存儲方式——我們稱之為三元組順序表。稀疏矩陣的三元組順序表的類型定義structnode{introw,col;//非零元的行下標(biāo)和列下標(biāo)intvalue;//非零元值};typedefstructnodeNODE;NODEma[MAX]；ma[0]用于存儲矩陣行數(shù)、列數(shù)、非零元個數(shù)用于存儲非零元三元組的結(jié)構(gòu)4.1數(shù)組A的三元組順序表圖示A

=012900000000000-3000014000240000018000001500-7000rowcolvalue01234567820-3501501124118029322453-72514678例如ma[1].row=0,ma[1].col=1,ma[1].value=124.1數(shù)組3)轉(zhuǎn)置運算算法轉(zhuǎn)置運算是一種最常用的矩陣運算。對于一個m行n列的矩陣A，它的轉(zhuǎn)置矩陣B是一個n行m列的矩陣。例如，以下圖中的矩陣A和B互為轉(zhuǎn)置矩陣。A

=012900000000000-3000014000240000018000001500-7000B

=00-3001512000180900240000000-70000000014000000000

4.1數(shù)組

A第0列第一列第二列第三列第四列第五列第六列….

B第0行第一行第二行第三行第四行第五行第六行….轉(zhuǎn)置運算算法4.1數(shù)組矩陣B矩陣Arowcolvalue01234567820-3501501124118029322453-72514678rowcolvalue012345678101235-702-32324051520952141418768分析：〔1〕將矩陣的行列數(shù)的值交換〔2〕將每一個三元組的i和j相互調(diào)換〔3〕重排三元組之間的次序4.1數(shù)組轉(zhuǎn)置運算算法按照A的列序來進行轉(zhuǎn)換的根本思想對ma[]從頭至尾掃描： 第一次掃描時，將ma[]中列號為0的所有元組交換行列值后，依次賦值到mb[]中 第二次掃描時，將ma[]中列號為1的所有元組交換行列值后，依次賦值到mb[]中依此類推，直至將ma[]的所有三元組賦值到mb[]中4.1數(shù)組ijv011202920-3251432244118501553-7ijv20-3141802-3501505150112101241180292093224232453-735-725145214A矩陣B矩陣對A六次掃描完成轉(zhuǎn)置運算第一次掃描查找第0列元素第一次掃描結(jié)束第二次掃描結(jié)束第二次掃描查找第1列元素第三次掃描查找第2列元素第四次掃描查找第3列元素第五次掃描查找第4列元素第六次掃描查找第5列元素轉(zhuǎn)置運算算法圖示0123456786787684.1數(shù)組轉(zhuǎn)置算法:采用三元組表存儲表示，求稀疏矩陣A的轉(zhuǎn)置矩陣Binttranspose(NODEma[],NODEmb[]){inti,j,k;if(ma[0].value==0)return(0);mb[0].row=ma[0].col;mb[0].col=ma[0].row;mb[0].value=ma[0].value;k=1;//k為當(dāng)前三元組在mb[]存儲位置(下標(biāo))

for(i=0;i<ma[0].col;i++)//找ma[]中第i列所有非0元素for(j=1;j<=ma[0].value;j++)//j為掃描ma[]的“指示器〞//j“指向〞三元組稱為當(dāng)前三元組

if(ma[j].col==i){mb[k].row=ma[j].col;mb[k].col=ma[j].row;

mb[k].value=ma[j].value;k++;}

return(1);}4.1數(shù)組時間復(fù)雜度分析算法的根本操作為將ma[]中的三元組賦值到mb[]，是在兩個循環(huán)中完成的，故算法的時間復(fù)雜度為O(nt),其中n為A矩陣的列數(shù),t為非0元素個數(shù)。當(dāng)非零元的個數(shù)t和矩陣元素個數(shù)mn同數(shù)量級時，即t≈mn，轉(zhuǎn)置運算算法的時間復(fù)雜度為O〔nmn〕。由此可見：在這種情況下，用三元組順序表存儲矩陣，雖然可能節(jié)省了存儲空間，但時間復(fù)雜度提高了，因此算法僅適于t<<mn的情況。該算法效率不高的原因是：對為實現(xiàn)A到B的轉(zhuǎn)置，該算法對ma[]進行了屢次掃描。其特點是：以B矩陣的三元組為中心，在A矩陣的三元組中通盤查找適宜的結(jié)點置入mb[k]中能否在對ma[]一次掃描的過程中，完成A到B的轉(zhuǎn)置？4.1數(shù)組十字鏈表的存儲結(jié)構(gòu)以三元組表示的稀疏矩陣，在運算中，假設(shè)非0元素的位置發(fā)生變化，會引起數(shù)組元素的頻繁移動。為解決這個問題，采用十字鏈表的存儲結(jié)構(gòu)在十字鏈表中，表示非0元素的結(jié)點除了三元組，還有兩個指針域： 向下域〔down)鏈接同一列下一個非0元素 向右域(right)鏈接同一行下一個非0元素稀疏矩陣中同一行的非0元素結(jié)點通過向右域，鏈接成一個帶頭結(jié)點的行循環(huán)鏈表同一