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

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

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

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

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

順序存儲

鏈式存儲線性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面：數(shù)據(jù)類型—高級語言中指數(shù)據(jù)的取值范圍及其上可進行的操作的總稱例C語言中，提供int,char,float,double等基本數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(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í)行指令速度同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同，———所以使用絕對時間單位衡量算法效率不合適時間復(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)特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼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線性表的順序存儲結(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)：可用一維數(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ù)元素不是簡單類型時,可定義結(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)個元素后移算法內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標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)個元素前移算法內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標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ù)先分配空間需按最大空間分配，利用不充分表容量難以擴充3線性表的鏈式存儲結(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)typedef

structnode{

datatype

data;

structnode*link;}JD;JD*h,*p;datalinkp結(jié)點（*p）(*p)表示p所指向的結(jié)點(*p).datap->data表示p指向結(jié)點的數(shù)據(jù)域(*p).linkp->link表示p指向結(jié)點的指針域生成一個JD型新結(jié)點：p=(JD*)malloc(sizeof(JD));系統(tǒng)回收p結(jié)點：free(p)線性鏈表定義：結(jié)點中只含一個指針域的鏈表叫~，也叫單鏈表h空表^頭結(jié)點：在單鏈表第一個結(jié)點前附設(shè)一個結(jié)點叫~頭結(jié)點指針域為空表示線性表為空頭結(jié)點ha1a2an^……單鏈表的基本運算查找：查找單鏈表中是否存在結(jié)點X，若有則返回指向X結(jié)點的指針；否則返回NULL算法描述While循環(huán)中語句頻度為若找到結(jié)點X，為結(jié)點X在表中的序號否則，為npabxs算法評價插入：在線性表兩個數(shù)據(jù)元素a和b間插入x，已知p指向as->link=p->link;p->link=s;算法描述算法評價算法描述算法評價刪除：單鏈表中刪除b，設(shè)p指向ap->link=p->link->link;pabc動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針算法描述算法評價h頭結(jié)點0^頭結(jié)點han^0頭結(jié)點han-10an^頭結(jié)點a2…...han-10an^頭結(jié)點ha1a2an^…...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é)點定義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線性表的應(yīng)用舉例一元多項式的表示及相加一元多項式的表示：可用線性表P表示但對S(x)這樣的多項式浪費空間一般其中用數(shù)據(jù)域含兩個數(shù)據(jù)項的線性表表示其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表單鏈表的結(jié)點定義coefexpnext-1A703198517^-1B81227-98^-1C70111227517^一元多項式相加typedef

structnode{int

coef,exp;

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

structnode{intdata;

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