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

1、2 數(shù)據(jù)結(jié)構(gòu)第二章 數(shù)據(jù)結(jié)構(gòu)1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) 程序程序=數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+算法算法l例例1 書目自動檢索系統(tǒng)書目自動檢索系統(tǒng)登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠(yuǎn)祥L01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書S02書目文件按書名按作者名按分類號高等數(shù)學(xué)001，003理論力學(xué)002，.線性代數(shù)004，.樊映川001,華羅庚002,.欒汝書004,.L002,S001,003,索引表線性表l數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)定義: 是一門研究是一門研究非數(shù)值計算非數(shù)值計算的程序設(shè)的程序設(shè)計問題中計算機(jī)的計問題中計算機(jī)的

2、操作對象操作對象以及它們之間的以及它們之間的關(guān)系關(guān)系和和操作操作等等的學(xué)科等等的學(xué)科l2 基本概念和術(shù)語基本概念和術(shù)語l數(shù)據(jù)（數(shù)據(jù)（data)所有能輸入到計算機(jī)中去的所有能輸入到計算機(jī)中去的描述客觀事物的描述客觀事物的符號符號l數(shù)據(jù)元素（數(shù)據(jù)元素（data element）數(shù)據(jù)的數(shù)據(jù)的基本單位基本單位，也稱節(jié)點(diǎn)，也稱節(jié)點(diǎn)（node）或記錄（或記錄（record）l數(shù)據(jù)項(xiàng)（數(shù)據(jù)項(xiàng)（data item）有獨(dú)立含義的數(shù)據(jù)有獨(dú)立含義的數(shù)據(jù)最小單位最小單位，也稱，也稱域域(field)l數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（data structure)數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合集合根據(jù)數(shù)據(jù)元素

3、間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)（集合集合）數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系線性結(jié)構(gòu)線性結(jié)構(gòu)一個對一個，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)樹形結(jié)構(gòu)一個對多個，如樹圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)多個對多個，如圖l數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象反映數(shù)據(jù)元素的只抽象反映數(shù)據(jù)元素的邏輯關(guān)系邏輯關(guān)系l數(shù)據(jù)的存儲（物理）結(jié)構(gòu)數(shù)據(jù)的存儲（物理）結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)機(jī)存儲器中的實(shí)現(xiàn)存儲器中的實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)密切相關(guān)算法設(shè)計 邏輯結(jié)構(gòu)算法實(shí)現(xiàn) 存儲結(jié)構(gòu)存儲結(jié)構(gòu)分為：順序存儲結(jié)構(gòu)借助元素在存儲器中的相對位置相對位置來表示 數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯Y(jié)構(gòu)借助指示元素存儲地址的指

4、針指針表示數(shù)據(jù) 元素間的邏輯關(guān)系元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲地址存儲內(nèi)容存儲內(nèi)容Loc(元素元素i)=Lo+（i-1)*m順序存儲順序存儲1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存儲地址存儲地址 存儲內(nèi)容存儲內(nèi)容 指針指針 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 . . . . . 14001400 元素元素2 2 1536 1536 . . . . . 1536 1536 元素元素3 3 1346

5、 1346 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?h 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 順序存儲順序存儲 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?線性表線性表?xiàng)ｊ?duì)隊(duì)樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面：數(shù)據(jù)結(jié)構(gòu)的三個方面：l數(shù)據(jù)類型數(shù)據(jù)類型高級語言中指數(shù)據(jù)的高級語言中指數(shù)據(jù)的取值范圍取值范圍及其上及其上可進(jìn)行的可進(jìn)行的操作操作的總稱的總稱例 C語言中，提供int, char, float, double等基本等基本 數(shù)據(jù)類型數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉 等構(gòu)造數(shù)

6、據(jù)類型構(gòu)造數(shù)據(jù)類型，還有指針、空(void)類 型等。用戶也可用typedef 自己定義數(shù)據(jù)類型自己定義數(shù)據(jù)類型typedef struct int num; char name20; float score;STUDENT;STUDENT stu1,stu2, *p;l3 算法的描述和算法分析簡介算法的描述和算法分析簡介l算法（算法（algorithm）解決某一特定問題的解決某一特定問題的具體步具體步驟的描述驟的描述，是指令的有限序列，是指令的有限序列l(wèi)算法特性算法特性輸出一個算法有零個或多個輸出輸入一個算法有零個或多個輸入算法是能行的可行性義性切定義的，不能產(chǎn)生二算法的每一步必須是確確定性

7、限步驟之后結(jié)束一個算法必須在執(zhí)行有有窮性算法的描述算法的評價衡量算法優(yōu)劣的標(biāo)準(zhǔn)v正確性(correctness)v可讀性(readability)v健壯性(robustness)v效率與低存儲量算法效率算法效率用依據(jù)該算法編制的程序在計算機(jī)上執(zhí)行所用依據(jù)該算法編制的程序在計算機(jī)上執(zhí)行所消耗消耗的時間的時間來度量來度量1.事后統(tǒng)計事后統(tǒng)計利用計算機(jī)內(nèi)記時功能，不同算法的程序可以用一組或利用計算機(jī)內(nèi)記時功能，不同算法的程序可以用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)分多組相同的統(tǒng)計數(shù)據(jù)區(qū)分 缺點(diǎn)：缺點(diǎn)：必須先運(yùn)行依據(jù)算法編制的程序必須先運(yùn)行依據(jù)算法編制的程序 所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法

8、本所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本 身的優(yōu)劣身的優(yōu)劣 2.事前分析估計事前分析估計一個高級語言程序在計算機(jī)上運(yùn)行所消耗的時間取一個高級語言程序在計算機(jī)上運(yùn)行所消耗的時間取決于：決于： 依據(jù)的算法選用何種策略依據(jù)的算法選用何種策略 問題的規(guī)模問題的規(guī)模 程序語言程序語言 編譯程序產(chǎn)生機(jī)器代碼質(zhì)量編譯程序產(chǎn)生機(jī)器代碼質(zhì)量 機(jī)器執(zhí)行指令速度機(jī)器執(zhí)行指令速度 同一個算法用不同的語言、不同的編譯程序、在不同的計算機(jī)上運(yùn)行，同一個算法用不同的語言、不同的編譯程序、在不同的計算機(jī)上運(yùn)行，效率均不同，效率均不同，所以使用所以使用絕對時間單位絕對時間單位衡量算法效率衡量算法效率不合適不合適

9、時間復(fù)雜度：基本操作重復(fù)執(zhí)行的次數(shù)的階數(shù) T(n)=o(f(n) 空間復(fù)雜度：s(n)=o(f(n)例1：NN矩陣相乘for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; 33)(nOnTnnf數(shù)據(jù)的線性結(jié)構(gòu)數(shù)據(jù)的線性結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)特點(diǎn)特點(diǎn)：在數(shù)據(jù)元素的非空有限集中：在數(shù)據(jù)元素的非空有限集中l(wèi)存在存在唯一唯一的一個被稱作的一個被稱作“第一個第一個”的數(shù)據(jù)元素的數(shù)據(jù)元素l存在存在唯一唯一的一個被稱作的一個被稱作“最后一個最后一個”的數(shù)據(jù)元素的數(shù)據(jù)元素l除第一個外，集合中的每個數(shù)據(jù)元素均除第一個外，集合

10、中的每個數(shù)據(jù)元素均只有一個只有一個前驅(qū)前驅(qū)l除最后一個外，集合中的每個數(shù)據(jù)元素均除最后一個外，集合中的每個數(shù)據(jù)元素均只有一只有一個后繼個后繼l1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)l定義：一個線性表是定義：一個線性表是n個數(shù)據(jù)元素的有限序列個數(shù)據(jù)元素的有限序列niaaaa,21如例 英文字母表（A,B,C,.Z)是一個線性表例學(xué)號姓名年齡001張三18002李四19數(shù)據(jù)元素特征：v元素個數(shù)n表長度，n=0空表v1idata表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).linkp-link表示p指向結(jié)點(diǎn)的指針域生成一個JD型新結(jié)點(diǎn)：p=(JD *)malloc(sizeof(JD);系統(tǒng)回收p結(jié)點(diǎn)：free(p

11、)線性鏈表v定義：結(jié)點(diǎn)中只含一個指針域的鏈表叫，也叫單鏈表h空表 頭結(jié)點(diǎn)：在單鏈表第一個結(jié)點(diǎn)前附設(shè)一個結(jié)點(diǎn)叫頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空頭結(jié)點(diǎn)ha1a2an 單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算 查找：查找單鏈表中是否存在結(jié)點(diǎn)X，若有則返回指向X結(jié)點(diǎn)的指針；否則返回NULL 算法描述While循環(huán)中語句頻度為若找到結(jié)點(diǎn)X，為結(jié)點(diǎn)X在表中的序號否則，為n nOnTpabxsu算法評價l 插入：在線性表兩個數(shù)據(jù)元素a和b間插入x，已知p指向as-link=p-link;p-link=s; 1OnTu算法描述u算法評價 算法描述 1OnTu算法評價l刪除：單鏈表中刪除b，設(shè)p指向ap-link=p-l

12、ink-link;pabc nOnTl動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針u算法描述u算法評價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)單鏈表特點(diǎn) 它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用 不需預(yù)先分配空間 指針占用額外存儲空間 不能隨機(jī)存取，查找速度慢l循環(huán)鏈表循環(huán)鏈表(circular linked list)循環(huán)鏈表是表中最后一個結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，循環(huán)鏈表是表中最后一個結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀使鏈表構(gòu)成環(huán)狀特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)特點(diǎn)

13、：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率，提高查找效率操作與單鏈表基本一致操作與單鏈表基本一致,循環(huán)條件不同循環(huán)條件不同 單鏈表p或p-link=NULL 循環(huán)鏈表p或p-link=Hhh空表l雙向鏈表（雙向鏈表（double linked list）單鏈表具有單向性的缺點(diǎn)單鏈表具有單向性的缺點(diǎn)結(jié)點(diǎn)定義結(jié)點(diǎn)定義typedef struct node datatype element; struct node *prior,*next;JD;prior element nextL空雙向循環(huán)鏈表非空雙向循環(huán)鏈表 LABbcapp-prior-next= p= p-next-proir

14、;void del_dulist(JD *p)p-prior-next=p-next; p-next-prior=p-prior; free(p);v刪除l算法描述l算法評價：T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;bcapvoid ins_dulist(JD* p,int x)JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;l算法描述l算法評價：T(n)=O(1)xSbaPv插入l4

15、線性表的應(yīng)用舉例線性表的應(yīng)用舉例l 一元多項(xiàng)式的表示及相加一元多項(xiàng)式的表示及相加l一元多項(xiàng)式的表示：一元多項(xiàng)式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用線性表P表示200001000231)(xxxS但對S(x)這樣的多項(xiàng)式浪費(fèi)空間一般emmnxPxPxPxPee2121)(其中為非零系數(shù)）（iPemee210用數(shù)據(jù)域含兩個數(shù)據(jù)項(xiàng)的線性表表示emPePePm，2121其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表l單鏈表的結(jié)點(diǎn)定義單鏈表的結(jié)點(diǎn)定義coefexpnext17787178522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxx

16、A-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多項(xiàng)式相加typedef struct node int coef,exp; struct node *next;JD;設(shè)p,q分別指向A,B中某一結(jié)點(diǎn)，p,q初值是第一結(jié)點(diǎn)比較p-exp與q-expp-exp exp: p結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng) p后移,q不動p-exp q-exp: q結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng) 將q插在p之前,q后移,p不動p-exp = q-exp: 系數(shù)相加0：從A表中刪去p, 釋放p,q，p,q后移0：修改p系數(shù)域, 釋放q，p,q后移直到p或q為

17、NULL 若q=NULL，結(jié)束 若p=NULL，將B中剩余部分連到A上即可運(yùn)算規(guī)則q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1p

18、b8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 算法描述棧和隊(duì)列棧和隊(duì)列棧和隊(duì)列是兩種特殊的線性表，是棧和隊(duì)列是兩種特殊的線性表，是操作受限操作受限的線的線性表，稱限定性性表，稱限定性DSl1 棧（棧（stack）l棧的定義和特點(diǎn)棧的定義和特點(diǎn)l定義：限定僅在定義：限定僅在表尾表尾進(jìn)行插入或刪除操作的線性表，表尾進(jìn)行插入或刪除操作的線性表，表尾棧棧頂頂，表頭，表頭棧底棧底，不含元素的空表稱空棧，不含元素的空表稱空棧l特點(diǎn)：先進(jìn)后出（特點(diǎn)：先進(jìn)后出（FILO）或后進(jìn)先出（或后進(jìn)先出（LIFO）ana1a2.棧底棧頂.出棧進(jìn)棧棧s=(a1,a2,an)l棧的存儲

19、結(jié)構(gòu)棧的存儲結(jié)構(gòu)順序棧順序棧 實(shí)現(xiàn)：一維數(shù)組sMtop=-1123450棧空棧頂指針top,指向?qū)嶋H棧頂后的空位置，初值為-1top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=-1,棧空，此時出棧，則下溢（underflow)top=M-1,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？誰入棧算法l出棧算法鏈棧鏈棧棧頂 .topdatalink棧底l結(jié)點(diǎn)定義l入棧算法l出棧算法typedef struct node int data; struct node *link;JD; .棧底

20、toptopxptop .棧底topqv回文游戲：順讀與逆讀字符串一樣（不含空格）dadtop1.讀入字符串2.去掉空格（原串）3.壓入棧4.原串字符與出棧字符依次比較 若不等，非回文 若直到?？斩枷嗟龋匚膙多進(jìn)制輸出：字符串：“madam im adam”例 把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)(159)10=(237)815981982802 3 7 余 7余 3余 2toptoptop7top73732棧的應(yīng)用棧的應(yīng)用 l2 隊(duì)列隊(duì)列l(wèi)隊(duì)列的定義及特點(diǎn)隊(duì)列的定義及特點(diǎn)l定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表行

21、刪除的線性表l 隊(duì)尾(rear)允許插入的一端l 隊(duì)頭(front)允許刪除的一端l隊(duì)列特點(diǎn)：先進(jìn)先出隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO)a1 a2 a3.an 入隊(duì)出隊(duì)frontrear隊(duì)列Q=(a1,a2,an)v雙端隊(duì)列a1 a2 a3.an 端1端2入隊(duì)出隊(duì)入隊(duì)出隊(duì)l鏈隊(duì)列鏈隊(duì)列結(jié)點(diǎn)定義結(jié)點(diǎn)定義typedef struct node int data; struct node *link;JD;頭結(jié)點(diǎn) .front隊(duì)頭隊(duì)尾rear設(shè)隊(duì)首、隊(duì)尾指針front和rear,front指向頭結(jié)點(diǎn)，rear指向隊(duì)尾frontrearx入隊(duì)xfrontreary入隊(duì)xyfrontrearx出隊(duì)xyfrontrear空隊(duì)frontreary出隊(duì)l隊(duì)列的順序存儲結(jié)構(gòu)隊(duì)列的順序存儲結(jié)構(gòu)實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)實(shí)現(xiàn)：用一維