VB教程02.數(shù)據(jù)的線性結(jié)構(gòu)

2數(shù)據(jù)結(jié)構(gòu)第二章數(shù)據(jù)結(jié)構(gòu)1什么是數(shù)據(jù)結(jié)構(gòu)

程序=數(shù)據(jù)結(jié)構(gòu)+算法例1書(shū)目自動(dòng)檢索系統(tǒng)登錄號(hào)：書(shū)名：作者名：分類(lèi)號(hào)：出版單位：出版時(shí)間：價(jià)格：書(shū)目卡片書(shū)目文件按書(shū)名按作者名按分類(lèi)號(hào)索引表線性表數(shù)據(jù)結(jié)構(gòu)定義:是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科2基本概念和術(shù)語(yǔ)數(shù)據(jù)（data)—所有能輸入到計(jì)算機(jī)中去的描述客觀事物的符號(hào)數(shù)據(jù)元素（dataelement）—數(shù)據(jù)的基本單位，也稱節(jié)點(diǎn)（node）或記錄（record）數(shù)據(jù)項(xiàng)（dataitem）—有獨(dú)立含義的數(shù)據(jù)最小單位，也稱域(field)數(shù)據(jù)結(jié)構(gòu)（datastructure)—數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)（集合）——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無(wú)其它關(guān)系線性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹(shù)形結(jié)構(gòu)——一個(gè)對(duì)多個(gè)，如樹(shù)圖狀結(jié)構(gòu)——多個(gè)對(duì)多個(gè)，如圖數(shù)據(jù)的邏輯結(jié)構(gòu)—只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)—數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān) 算法設(shè)計(jì) 邏輯結(jié)構(gòu) 算法實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)——借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)1536元素21400元素11346元素3∧元素41345h存儲(chǔ)地址

存儲(chǔ)內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈?zhǔn)酱鎯?chǔ)

h

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：數(shù)據(jù)類(lèi)型—高級(jí)語(yǔ)言中指數(shù)據(jù)的取值范圍及其上可進(jìn)行的操作的總稱例C語(yǔ)言中，提供int,char,float,double等基本數(shù)據(jù)類(lèi)型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(shù)據(jù)類(lèi)型，還有指針、空(void)類(lèi)型等。用戶也可用typedef

自己定義數(shù)據(jù)類(lèi)型typedef

struct

{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;3算法的描述和算法分析簡(jiǎn)介算法（algorithm）—解決某一特定問(wèn)題的具體步驟的描述，是指令的有限序列算法特性—算法的描述算法的評(píng)價(jià)—衡量算法優(yōu)劣的標(biāo)準(zhǔn)正確性(correctness)可讀性(readability)健壯性(robustness)效率與低存儲(chǔ)量算法效率——用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí)行所消耗的時(shí)間來(lái)度量

1.事后統(tǒng)計(jì)——利用計(jì)算機(jī)內(nèi)記時(shí)功能，不同算法的程序可以用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分缺點(diǎn)：必須先運(yùn)行依據(jù)算法編制的程序所得時(shí)間統(tǒng)計(jì)量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣

2.事前分析估計(jì)——一個(gè)高級(jí)語(yǔ)言程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間取決于：依據(jù)的算法選用何種策略問(wèn)題的規(guī)模程序語(yǔ)言編譯程序產(chǎn)生機(jī)器代碼質(zhì)量機(jī)器執(zhí)行指令速度同一個(gè)算法用不同的語(yǔ)言、不同的編譯程序、在不同的計(jì)算機(jī)上運(yùn)行，效率均不同，———所以使用絕對(duì)時(shí)間單位衡量算法效率不合適時(shí)間復(fù)雜度：基本操作重復(fù)執(zhí)行的次數(shù)的階數(shù)T(n)=o(f(n))空間復(fù)雜度：s(n)=o(f(n))例1：N×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]=c[i][j]+a[i][k]*b[k][j];} 數(shù)據(jù)的線性結(jié)構(gòu)線性結(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è)后繼1線性表的邏輯結(jié)構(gòu)定義：一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列例英文字母表（A,B,C,…..Z)是一個(gè)線性表例數(shù)據(jù)元素特征：元素個(gè)數(shù)n—表長(zhǎng)度，n=0空表1<i<n時(shí)ai的直接前驅(qū)是ai-1，a1無(wú)直接前驅(qū)ai的直接后繼是ai+1，an無(wú)直接后繼元素同構(gòu)，且不能出現(xiàn)缺項(xiàng)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)：可用一維數(shù)組實(shí)現(xiàn)a1a2an01n-112n內(nèi)存V數(shù)組下標(biāo)元素序號(hào)M-1typedef

intDATATYPE;#defineM1000DATATYPEdata[M];例typedef

structcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];備用空間數(shù)據(jù)元素不是簡(jiǎn)單類(lèi)型時(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，使長(zhǎng)度為n的線性表

變成長(zhǎng)度為n+1的線性表

需將第i至第n共（n-i+1)個(gè)元素后移算法內(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è)元素的概率，則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素次數(shù)的平均次數(shù)為：刪除定義：線性表的刪除是指將第i（1in）個(gè)元素刪除，使長(zhǎng)度為n的線性表

變成長(zhǎng)度為n-1的線性表

需將第i+1至第n共（n-i)個(gè)元素前移算法內(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è)元素的概率，則在長(zhǎng)度為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ò)充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)typedef

structnode{

datatype

data;

structnode*link;}JD;JD*h,*p;datalinkp結(jié)點(diǎn)（*p）(*p)表示p所指向的結(jié)點(diǎn)(*p).datap->data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).linkp->link表示p指向結(jié)點(diǎn)的指針域生成一個(gè)JD型新結(jié)點(diǎn)：p=(JD*)malloc(sizeof(JD));系統(tǒng)回收p結(jié)點(diǎn)：free(p)線性鏈表定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫~，也叫單鏈表h空表^頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)叫~頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空頭結(jié)點(diǎn)ha1a2an^……單鏈表的基本運(yùn)算查找：查找單鏈表中是否存在結(jié)點(diǎn)X，若有則返回指向X結(jié)點(diǎn)的指針；否則返回NULL算法描述While循環(huán)中語(yǔ)句頻度為若找到結(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à)算法描述算法評(píng)價(jià)刪除：?jiǎn)捂湵碇袆h除b，設(shè)p指向ap->link=p->link->link;pabc動(dòng)態(tài)建立單鏈表算法：設(shè)線性表n個(gè)元素已存放在數(shù)組a中，建立一個(gè)單鏈表，h為頭指針?biāo)惴枋鏊惴ㄔu(píng)價(jià)h頭結(jié)點(diǎn)0^頭結(jié)點(diǎn)han^0頭結(jié)點(diǎn)han-10an^頭結(jié)點(diǎn)a2…...han-10an^頭結(jié)點(diǎn)ha1a2an^…...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)定義typedef

structnode{

datatypeelement;

structnode*prior,*next;}JD;priorelementnextL空雙向循環(huán)鏈表非空雙向循環(huán)鏈表LABbcapp->prior->next=p=p->next->proir;voiddel_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;bcapvoidins_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插入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)定義coefexpnext-1A703198517^-1B81227-98^-1C70111227517^一元多項(xiàng)式相加typedef

structnode{int

coef,exp;

structnode*next;}JD;設(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^算法描述棧和隊(duì)列棧和隊(duì)列是兩種特殊的線性表，是操作受限的線性表，稱限定性DS1棧（stack）棧的定義和特點(diǎn)定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧特點(diǎn)：先進(jìn)后出（FILO）或后進(jìn)先出（LIFO）ana1a2……...棧底棧頂...出棧進(jìn)棧棧s=(a1,a2,……,an)棧的存儲(chǔ)結(jié)構(gòu)順序棧實(shí)現(xiàn)：一維數(shù)組s[M]top=-1123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置，初值為-1top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=-1,?？眨藭r(shí)出棧，則下溢（underflow)top=M-1,棧滿，此時(shí)入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop棧空入棧算法出棧算法鏈棧棧頂^…...topdatalink棧底結(jié)點(diǎn)定義入棧算法出棧算法typedef

structnode{intdata;

structnode*link;}JD;^…...棧底toptopxptop^…...棧底topq回文游戲：順讀與逆讀字符串一樣（不含空格）dadtop1.讀入字符串2.去掉空格（原串）3.壓入棧4.原串字符與出棧字符依次比較若不等，非回文若直到?？斩枷嗟?，回文多進(jìn)制輸出：字符串：“madamim

adam”例把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)(159)10=(237)81598198280237余7余3余2toptoptop7top73732棧的應(yīng)用2隊(duì)列隊(duì)列的定義及特點(diǎn)定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表隊(duì)尾(rear)——允許插入的一端隊(duì)頭(front)——允許刪除的一端隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO)a1a2a3…….an入隊(duì)出隊(duì)frontrear隊(duì)列Q=(a1,a2,……,an)雙端隊(duì)列a1a2a3…….an端1端2入隊(duì)出隊(duì)入隊(duì)出隊(duì)鏈隊(duì)列結(jié)點(diǎn)定義typedef

structnode{intdata;

structnode*link;}JD;頭結(jié)點(diǎn)^…...front隊(duì)頭隊(duì)尾rear設(shè)隊(duì)首、隊(duì)尾指針front和rear,front指向頭結(jié)點(diǎn)，rear指向隊(duì)尾frontrearx入隊(duì)^xfrontreary入隊(duì)x^yf