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

廣東交通職業(yè)基數(shù)學(xué)院計(jì)算機(jī)系課件設(shè)計(jì)數(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é)出版社課程特點(diǎn)及課時(shí)分配難度大綜合性強(qiáng)必須下苦功學(xué)習(xí)課程說明考試每周4節(jié)，共20周評(píng)分標(biāo)準(zhǔn)：平時(shí)成績20％〔包括考勤、課堂答復(fù)以下問題等〕、期中成績30％，期末成績50％教學(xué)內(nèi)容第一章緒論第二章線性表第三章棧和隊(duì)列第四章數(shù)組和串第五章樹

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

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

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

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

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

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

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

area=len*wide;

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

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

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

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

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

楊潤生男82/06/01廣州56100計(jì)算機(jī)2

00102石磊男83/12/21汕頭51200計(jì)算機(jī)1

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

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

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

1〕輸入：0個(gè)或多個(gè)輸入；

2〕輸出：1個(gè)或多個(gè)輸出；

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

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

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

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

本課程采用以求解問題的根本操作的執(zhí)行次數(shù)作為算法時(shí)間的度量算法的空間復(fù)雜度S(n)一個(gè)算法所需要輔助存儲(chǔ)空間的多少為空間復(fù)雜度O〔n3〕稱為矩陣相乘算法時(shí)間復(fù)雜度；O〔n3〕表示矩陣相乘算法執(zhí)行時(shí)間與n3成正比,即O〔n3〕與n3同一數(shù)量級(jí)；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運(yùn)算、算法和算法分析有些算法，根本操作執(zhí)行次數(shù)與問題的輸入數(shù)據(jù)有關(guān)，這時(shí)可考慮

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

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

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

它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率與f(n)的增長率相同。1.3運(yùn)算、算法和算法分析算法的時(shí)間復(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運(yùn)算、算法和算法分析2算法空間復(fù)雜度

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

設(shè)執(zhí)行算法所需的輔助空間是問題規(guī)模n的某個(gè)函數(shù)g(n),那么算法空間復(fù)雜度記作：S〔n〕=O(g(n))表示算法輔助空間的增長率與g(n)的增長率相同1.3運(yùn)算、算法和算法分析計(jì)算解法1先計(jì)算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運(yùn)算、算法和算法分析例問題規(guī)模為n,算法時(shí)間復(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);}時(shí)間復(fù)雜度為O(n).空間復(fù)雜度為O(1)1.3運(yùn)算、算法和算法分析第二章線性表2.1線性表的定義和根本運(yùn)算2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.3.1單鏈表

2.3.2循環(huán)鏈表

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

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

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

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

datatype

data;structnode

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

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

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

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

·對(duì)循環(huán)鏈表，有時(shí)不給出頭指針，而是給出尾指針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é)點(diǎn)圖示數(shù)據(jù)域指針域指針域結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)元素data存儲(chǔ)后繼結(jié)點(diǎn)的地址next存儲(chǔ)前趨結(jié)點(diǎn)的地址prior

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

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

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)用舉例一元多項(xiàng)式的表示及相加一元多項(xiàng)式的表示：可用線性表P表示但對(duì)S(x)這樣的多項(xiàng)式浪費(fèi)空間一般其中用數(shù)據(jù)域含兩個(gè)數(shù)據(jù)項(xiàng)的線性表表示其存儲(chǔ)結(jié)構(gòu)可以用順序存儲(chǔ)結(jié)構(gòu)，也可以用單鏈表單鏈表的結(jié)點(diǎn)定義typedefstructnode{intcoef,exp;structnode*next;}JD;coefexpnext-1A703198517^-1B81227-98^-1C70111227517^一元多項(xiàng)式相加設(shè)p,q分別指向A,B中某一結(jié)點(diǎn)，p,q初值是第一結(jié)點(diǎn)比較p->exp與q->expp->exp<q->exp:p結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng)p后移,q不動(dòng)p->exp>q->exp:q結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng)將q插在p之前,q后移,p不動(dòng)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上即可運(yùn)算規(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)第三章棧和隊(duì)列主要內(nèi)容

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

什么是棧3.1.1棧的定義第一個(gè)進(jìn)棧的元素在棧底，

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

棧操作圖示A進(jìn)棧

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

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

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

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

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

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

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

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

出棧操作后MAX-1nn-1n-210anan-1a2a1top棧在運(yùn)算過程中可能發(fā)生“溢出〞現(xiàn)象：上溢下溢topMAX-1nn-1n-210anan-1a2a1MAX-1nn-1n-210top2〕進(jìn)棧操作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{}順序棧的缺乏：存在棧滿以后就不能再進(jìn)棧的問題〔這是因?yàn)橛昧硕ㄩL的數(shù)組存儲(chǔ)棧的元素〕解決方法：使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二、棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也稱鏈棧。其各結(jié)點(diǎn)的結(jié)構(gòu)與單鏈表中的結(jié)點(diǎn)結(jié)構(gòu)完全相同。如下圖：在前面學(xué)習(xí)了線性鏈表的插入刪除操作算法，不難寫出鏈?zhǔn)綏３跏蓟?、進(jìn)棧、出棧等操作的算法結(jié)點(diǎn)結(jié)構(gòu)定義：Typedefstructnode{elemtypedata;structnode*next;}node,*pointer;Datanexts棧頂（單鏈表的表頭）棧底an-1a1an(1)初始化棧Voidinitstack〔pointers〕{s=null;}^sDatanexts棧頂棧底an-1a1anDatanext棧頂棧底an-1a1an

xps進(jìn)棧前進(jìn)棧后(2)進(jìn)棧進(jìn)棧算法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隊(duì)列的定義隊(duì)列是限定僅能在表頭進(jìn)行刪除，表尾進(jìn)行插入的線性表〔a1,a2,...,ai-1,ai,ai+1,…,an〕插入刪除3.2隊(duì)列

a1a2a3……an入隊(duì)列隊(duì)頭隊(duì)尾出隊(duì)列隊(duì)列的示意圖隊(duì)列的特點(diǎn)先進(jìn)先出說明：第一個(gè)入隊(duì)的元素在隊(duì)頭，

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

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

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

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

{intdata;

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

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

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

？J7rear3.2隊(duì)列有兩種方法：

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

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

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

front=0;rear=0;

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

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

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

front=(front+1)%MAX;

return(queue[front]);

}小結(jié)和作業(yè)作業(yè):課后習(xí)題1、2、3實(shí)訓(xùn)題：參見://第四章數(shù)組和串主要內(nèi)容4.1數(shù)組4.1.1數(shù)組的概念和運(yùn)算4.1.2數(shù)組的順序存儲(chǔ)和訪問4.1.3矩陣的壓縮存儲(chǔ)4.2串4.2.1串的根本概念4.2.2串的根本運(yùn)算4.2.3串的存儲(chǔ)結(jié)構(gòu)4.1.1數(shù)組的概念運(yùn)算數(shù)組是由一組個(gè)數(shù)固定，類型相同的數(shù)據(jù)元素組成陣列。以二維數(shù)組為例：二維數(shù)組中的每個(gè)元素都受兩個(gè)線性關(guān)系的約束即行關(guān)系和列關(guān)系，在每個(gè)關(guān)系中，每個(gè)元素aij都有且僅有一個(gè)直接前趨，都有且僅有一個(gè)直接后繼。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ù)組也可看作這樣的線性表：其每一個(gè)數(shù)據(jù)元素也是一個(gè)線性表 A=〔0,1,2,3,4,……,p) 其中每一個(gè)數(shù)據(jù)元素j是一個(gè)列向量的線性表 j=〔a0j,a1j,a2j,a3j,……,am-1j) 或i是一個(gè)行向量的線性表i=〔ai0,ai1,ai2,ai3,……,ain-1)4.1數(shù)組數(shù)組的根本操作訪問：給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素。修改：給定一組下標(biāo)，修改相應(yīng)數(shù)據(jù)元素中的某個(gè)數(shù)據(jù)項(xiàng)的值。 操作方法根據(jù)其存儲(chǔ)結(jié)構(gòu)決定4.1數(shù)組4.1.2數(shù)組的順序存儲(chǔ)和訪問一維數(shù)組在內(nèi)存中的存放很簡單，只要順序存放在連續(xù)的內(nèi)存單元即可。二維數(shù)組，如何用順序結(jié)構(gòu)表示？內(nèi)存地址是一維的，而數(shù)組是二維的，要將二維數(shù)組擠入一維的地址中，有兩個(gè)策略： 以行為主序〔C語言使用〕以列為主序4.1數(shù)組a00

a01……a0n-1a10

a11……a1n-1

………………am-10

am-11……am-1n-1設(shè)A是一個(gè)具有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矩陣的壓縮存儲(chǔ)

一特殊矩陣的壓縮存儲(chǔ)二稀疏矩陣的壓縮存儲(chǔ)

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

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

n=a00

a01……a0n-1a10

a11……a1n-1

………………am-10

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

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

n=a00

a01……a0n-1a10

a11……a1n-1

………………am-10

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

a11a1n-1000

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

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

aij=

aji0

i,j

n-1

a00a01a0n-1a10a11a1n-1an-10an-11an-1n-1對(duì)稱矩陣元素可以只存儲(chǔ)下三角局部，共需n(n+1)/2個(gè)單元的空間(三角矩陣的存儲(chǔ)方式類似〕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階對(duì)稱矩陣A的存儲(chǔ)結(jié)構(gòu)，A中任意一元素aij與它的存儲(chǔ)位置sa[k]之間存在著如下對(duì)應(yīng)關(guān)系：a00

a10

a11

a20

a21a22

an-10an-11

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

a53在sa[]中的存儲(chǔ)位置是：k=5*(5+1)/2+3=18sa[18]=a534.1數(shù)組壓縮存儲(chǔ)的對(duì)稱矩陣的取值算法intget_M(inti,intj){if(i>=j)return(sa[i*(i+1)/2+j])elsereturn(sa[j*(j+1)/2+i]);}壓縮存儲(chǔ)的對(duì)稱矩陣的賦值算法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元素都集中在以主對(duì)角線為中心的帶狀區(qū)域，半帶寬為d時(shí),非0元素有(2d+1)*n-(1+d)*d個(gè)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為計(jì)算方便，認(rèn)為每一行都有2d+1個(gè)非0元素，假設(shè)少那么用0補(bǔ)足，所以，存放矩陣的數(shù)組sa[]有n(2d+1)個(gè)元素?cái)?shù)組元素sa[k]與矩陣元素aij之間有關(guān)系k=i*(2d+1)+d+(j-i)a00前為何放一個(gè)0？你會(huì)放d=2,n=6的帶狀矩陣嗎？？4.1數(shù)組0a00

a01

a10

a11a12a21a22a23a32a33a34a43a440壓縮存儲(chǔ)的帶狀矩陣的取值算法intget_Md(inti,intj){if(abs(i-j)<=d〕return(sa[i*(2*d+1)+d+(j-i)])；elsereturn(0);}壓縮存儲(chǔ)的帶狀矩陣的賦值算法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〕個(gè)元素有8個(gè)非零元素如何進(jìn)行稀疏矩陣的壓縮存儲(chǔ)？？4.1數(shù)組2稀疏矩陣的壓縮存儲(chǔ)〔只討論有較多零元素矩陣的壓縮存儲(chǔ)〕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è)以順序存儲(chǔ)結(jié)構(gòu)來表示三元組表，那么可得稀疏矩陣的一種壓縮存儲(chǔ)方式——我們稱之為三元組順序表。稀疏矩陣的三元組順序表的類型定義structnode{introw,col;//非零元的行下標(biāo)和列下標(biāo)intvalue;//非零元值};typedefstructnodeNODE;NODEma[MAX]；ma[0]用于存儲(chǔ)矩陣行數(shù)、列數(shù)、非零元個(gè)數(shù)用于存儲(chǔ)非零元三元組的結(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)置運(yùn)算算法轉(zhuǎn)置運(yùn)算是一種最常用的矩陣運(yùn)算。對(duì)于一個(gè)m行n列的矩陣A，它的轉(zhuǎn)置矩陣B是一個(gè)n行m列的矩陣。例如，以下圖中的矩陣A和B互為轉(zhuǎn)置矩陣。A

=012900000000000-3000014000240000018000001500-7000B

=00-3001512000180900240000000-70000000014000000000

4.1數(shù)組

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

B第0行第一行第二行第三行第四行第五行第六行….轉(zhuǎn)置運(yùn)算算法4.1數(shù)組矩陣B矩陣Arowcolvalue01234567820-3501501124118029322453-72514678rowcolvalue012345678101235-702-32324051520952141418768分析：〔1〕將矩陣的行列數(shù)的值交換〔2〕將每一個(gè)三元組的i和j相互調(diào)換〔3〕重排三元組之間的次序4.1數(shù)組轉(zhuǎn)置運(yùn)算算法按照A的列序來進(jìn)行轉(zhuǎn)換的根本思想對(duì)ma[]從頭至尾掃描： 第一次掃描時(shí)，將ma[]中列號(hào)為0的所有元組交換行列值后，依次賦值到mb[]中 第二次掃描時(shí)，將ma[]中列號(hào)為1的所有元組交換行列值后，依次賦值到mb[]中依此類推，直至將ma[]的所有三元組賦值到mb[]中4.1數(shù)組ijv011202920-3251432244118501553-7ijv20-3141802-3501505150112101241180292093224232453-735-725145214A矩陣B矩陣對(duì)A六次掃描完成轉(zhuǎn)置運(yùn)算第一次掃描查找第0列元素第一次掃描結(jié)束第二次掃描結(jié)束第二次掃描查找第1列元素第三次掃描查找第2列元素第四次掃描查找第3列元素第五次掃描查找第4列元素第六次掃描查找第5列元素轉(zhuǎn)置運(yùn)算算法圖示0123456786787684.1數(shù)組轉(zhuǎn)置算法:采用三元組表存儲(chǔ)表示，求稀疏矩陣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[]存儲(chǔ)位置(下標(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ù)組時(shí)間復(fù)雜度分析算法的根本操作為將ma[]中的三元組賦值到mb[]，是在兩個(gè)循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為O(nt),其中n為A矩陣的列數(shù),t為非0元素個(gè)數(shù)。當(dāng)非零元的個(gè)數(shù)t和矩陣元素個(gè)數(shù)mn同數(shù)量級(jí)時(shí)，即t≈mn，轉(zhuǎn)置運(yùn)算算法的時(shí)間復(fù)雜度為O〔nmn〕。由此可見：在這種情況下，用三元組順序表存儲(chǔ)矩陣，雖然可能節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度提高了，因此算法僅適于t<<mn的情況。該算法效率不高的原因是：對(duì)為實(shí)現(xiàn)A到B的轉(zhuǎn)置，該算法對(duì)ma[]進(jìn)行了屢次掃描。其特點(diǎn)是：以B矩陣的三元組為中心，在A矩陣的三元組中通盤查找適宜的結(jié)點(diǎn)置入mb[k]中能否在對(duì)ma[]一次掃描的過程中，完成A到B的轉(zhuǎn)置？4.1數(shù)組十字鏈表的存儲(chǔ)結(jié)構(gòu)以三元組表示的稀疏矩陣，在運(yùn)算中，假設(shè)非0元素的位置發(fā)生變化，會(huì)引起數(shù)組元素的頻繁移動(dòng)。為解決這個(gè)問題，采用十字鏈表的存儲(chǔ)結(jié)構(gòu)在十字鏈表中，表示非0元素的結(jié)點(diǎn)除了三元組，還有兩個(gè)指針域： 向下域〔down)鏈接同一列下一個(gè)非0元素 向右域(right)鏈接同一行下一個(gè)非0元素稀疏矩陣中同一行的非0元素結(jié)點(diǎn)通過向右域，鏈接成一個(gè)帶頭結(jié)點(diǎn)的行循環(huán)鏈表同一