VB教程02.數(shù)據(jù)的線性結構

2數(shù)據(jù)結構第二章數(shù)據(jù)結構1什么是數(shù)據(jù)結構

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

存儲內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈式存儲

h

數(shù)據(jù)的邏輯結構

數(shù)據(jù)的存儲結構數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等

線性結構

非線性結構

順序存儲

鏈式存儲線性表棧隊樹形結構圖形結構數(shù)據(jù)結構的三個方面：數(shù)據(jù)類型—高級語言中指數(shù)據(jù)的取值范圍及其上可進行的操作的總稱例C語言中，提供int,char,float,double等基本數(shù)據(jù)類型，數(shù)組、結構體、共用體、枚舉等構造數(shù)據(jù)類型，還有指針、空(void)類型等。用戶也可用typedef

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

struct

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

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

2.事前分析估計——一個高級語言程序在計算機上運行所消耗的時間取決于：依據(jù)的算法選用何種策略問題的規(guī)模程序語言編譯程序產(chǎn)生機器代碼質(zhì)量機器執(zhí)行指令速度同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同，———所以使用絕對時間單位衡量算法效率不合適時間復雜度：基本操作重復執(zhí)行的次數(shù)的階數(shù)T(n)=o(f(n))空間復雜度：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ù)的線性結構線性結構特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼1線性表的邏輯結構定義：一個線性表是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無直接后繼元素同構，且不能出現(xiàn)缺項2線性表的順序存儲結構順序表：定義：用一組地址連續(xù)的存儲單元存放一個線性表叫~元素地址計算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一個元素占用的存儲單元個數(shù)LOC(ai)—線性表第i個元素的地址特點：實現(xiàn)邏輯上相鄰—物理地址相鄰實現(xiàn)隨機存取實現(xiàn)：可用一維數(shù)組實現(xiàn)a1a2an01n-112n內(nèi)存V數(shù)組下標元素序號M-1typedef

intDATATYPE;#defineM1000DATATYPEdata[M];例typedef

structcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];備用空間數(shù)據(jù)元素不是簡單類型時,可定義結構體數(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)個元素后移算法內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1an-1x算法時間復雜度T(n)設Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：刪除定義：線性表的刪除是指將第i（1in）個元素刪除，使長度為n的線性表

變成長度為n-1的線性表

需將第i+1至第n共（n-i)個元素前移算法內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標01i-1n-2in-112i元素序號i+1n-1nanai+2算法評價設Qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數(shù)的平均次數(shù)為：故在順序表中插入或刪除一個元素時，平均移動表的一半元素，當n很大時，效率很低順序存儲結構的優(yōu)缺點優(yōu)點邏輯相鄰，物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點插入、刪除操作需要移動大量的元素預先分配空間需按最大空間分配，利用不充分表容量難以擴充3線性表的鏈式存儲結構特點：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息結點

數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲位置數(shù)據(jù)域指針域結點ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針實現(xiàn)typedef

structnode{

datatype

data;

structnode*link;}JD;JD*h,*p;datalinkp結點（*p）(*p)表示p所指向的結點(*p).datap->data表示p指向結點的數(shù)據(jù)域(*p).linkp->link表示p指向結點的指針域生成一個JD型新結點：p=(JD*)malloc(sizeof(JD));系統(tǒng)回收p結點：free(p)線性鏈表定義：結點中只含一個指針域的鏈表叫~，也叫單鏈表h空表^頭結點：在單鏈表第一個結點前附設一個結點叫~頭結點指針域為空表示線性表為空頭結點ha1a2an^……單鏈表的基本運算查找：查找單鏈表中是否存在結點X，若有則返回指向X結點的指針；否則返回NULL算法描述While循環(huán)中語句頻度為若找到結點X，為結點X在表中的序號否則，為npabxs算法評價插入：在線性表兩個數(shù)據(jù)元素a和b間插入x，已知p指向as->link=p->link;p->link=s;算法描述算法評價算法描述算法評價刪除：單鏈表中刪除b，設p指向ap->link=p->link->link;pabc動態(tài)建立單鏈表算法：設線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針算法描述算法評價h頭結點0^頭結點han^0頭結點han-10an^頭結點a2…...han-10an^頭結點ha1a2an^…...0單鏈表特點它是一種動態(tài)結構，整個存儲空間為多個鏈表共用不需預先分配空間指針占用額外存儲空間不能隨機存取，查找速度慢循環(huán)鏈表(circularlinkedlist)循環(huán)鏈表是表中最后一個結點的指針指向頭結點，使鏈表構成環(huán)狀特點：從表中任一結點出發(fā)均可找到表中其他結點，提高查找效率操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p->link=NULL循環(huán)鏈表p或p->link=Hhh空表雙向鏈表（doublelinkedlist）單鏈表具有單向性的缺點結點定義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);}刪除算法描述算法評價：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;}算法描述算法評價：T(n)=O(1)xSbaP插入4線性表的應用舉例一元多項式的表示及相加一元多項式的表示：可用線性表P表示但對S(x)這樣的多項式浪費空間一般其中用數(shù)據(jù)域含兩個數(shù)據(jù)項的線性表表示其存儲結構可以用順序存儲結構，也可以用單鏈表單鏈表的結點定義coefexpnext-1A703198517^-1B81227-98^-1C70111227517^一元多項式相加typedef

structnode{int

coef,exp;

structnode*next;}JD;設p,q分別指向A,B中某一結點，p,q初值是第一結點比較p->exp與q->expp->exp<q->exp:p結點是和多項式中的一項

p后移,q不動p->exp>q->exp:q結點是和多項式中的一項將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，結束

若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^算法描述棧和隊列棧和隊列是兩種特殊的線性表，是操作受限的線性表，稱限定性DS1棧（stack）棧的定義和特點定義：限定僅在表尾進行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧特點：先進后出（FILO）或后進先出（LIFO）ana1a2……...棧底棧頂...出棧進棧棧s=(a1,a2,……,an)棧的存儲結構順序棧實現(xiàn)：一維數(shù)組s[M]top=-1123450棧空棧頂指針top,指向?qū)嶋H棧頂后的空位置，初值為-1top123450進棧Atop出棧棧滿BCDEF設數(shù)組維數(shù)為Mtop=-1,?？?，此時出棧，則下溢（underflow)top=M-1,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？杖霔Ｋ惴ǔ鰲Ｋ惴ㄦ湕ｍ擽…...topdatalink棧底結點定義入棧算法出棧算法typedef

structnode{intdata;

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

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

structnode{intdata;

structnode*link;}JD;頭結點^…...front隊頭隊尾rear設隊首、隊尾指針front和rear,front指向頭結點，rear指向隊尾frontrearx入隊^xfrontreary入隊x^yf