數(shù)據(jù)結(jié)構(gòu)知識點(diǎn)部分整理

1、1. 數(shù)據(jù)結(jié)構(gòu)的產(chǎn)生(1) 計(jì)算機(jī)的發(fā)展：一速度T快V 計(jì)算機(jī)存儲容量T大應(yīng)用范圍不斷拓寬-價(jià)格T降早期計(jì)算機(jī)T主要用于科學(xué)計(jì)算T處理對象：純數(shù)值性的信息。(2) 計(jì)算機(jī)的應(yīng)用：情報(bào)檢索60年代后y 企業(yè)管理乃至人類社會活動的一切領(lǐng)一系統(tǒng)工程(3) 計(jì)算機(jī)的處理對象：數(shù)值性和非數(shù)值性(包括字符、圖像、聲音)算法（還是要掌握好的一部分）1. 概念：是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示 一個(gè)或多個(gè)操作。2. 算法的特性（1）有窮性：指有窮的步數(shù)，以及有窮的時(shí)間（2）確定性：每條指令必須有確切的含義，且算法只有唯一的一條執(zhí)行路徑，相同 的輸入只能是相同的輸出（3）可

2、行性：可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。（ 4） 輸入：一個(gè)算法有零個(gè)或多個(gè)的輸入。（5） 輸出：有一個(gè)或者多個(gè)的輸出，輸出的是同輸入有著某些特定關(guān)系的量。3. 算法的描述方法：自然語言、程序流程圖、偽代碼（又有自然語言又有程序語言） 、程 序設(shè)計(jì)語言。4. 算法的設(shè)計(jì)目標(biāo)（1）正確性：明確的無歧義的描述（2）可讀性：便于閱讀理解（ 3） 健壯性：輸入數(shù)據(jù)非法時(shí)，算法也能做出處理，而不產(chǎn)生不可預(yù)料的結(jié)果（4）高時(shí)間效率：算法時(shí)間盡量短（5）低儲存量需求：指算法執(zhí)行過程中所需要的最大存儲空間要低。5. 算法效率的度量（1）時(shí)間復(fù)雜度：算法的執(zhí)行時(shí)間是指根據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)

3、行時(shí)所 消耗的時(shí)間總量?；菊Z句：執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行次數(shù)成正比的語句，多數(shù)情況下它是最 深層循環(huán)內(nèi)的語句。T（n）= O（f（n）Eg：語句的執(zhí)行次數(shù)（就是循環(huán)的次數(shù)）為n2+1，則算法的時(shí)間復(fù)雜度為T（n）=）O（ n2）（2）空間復(fù)雜度：算法的空間復(fù)雜度是對一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲空間大小的度量，它也是衡量算法有效性的一個(gè)指標(biāo)。算法的空間復(fù)雜度是對算法的執(zhí)行過程需要的輔助空間進(jìn)行度量。通常記作 S（n）=O（f（n）其中 n 為問題的規(guī)模（或大?。?，表示隨著問題規(guī)模 n 的增大，算法運(yùn)行所需存 儲量的增長率與f（n）的增長率相同。線性表（重點(diǎn)掌握）1線性表的定義：線性表（l

4、inearlist）是n（n >0）個(gè)相同類型的數(shù)據(jù)元素構(gòu)成的有限序列。其中 稱n為線性表的長度，當(dāng) n=0時(shí)，表示線性表是一個(gè)空表，即表中不包含任何元素。一個(gè)有 n 個(gè)數(shù)據(jù)元素的線性表常表示為：（al , a2,，an）則常把線性表中使用的元素類型用一種通用數(shù)據(jù)類型標(biāo)識符ElemType進(jìn)行抽象，實(shí)際使用時(shí)可以通過 typedef 語句把它定義為任何一種具體類型。若線性表中的元素為整數(shù)，則可通 過下列語句把它定義為整數(shù)類型：typedef int ElemType2. 線性表的定義：(1) 序列的順序性，限制順序，第一個(gè)元素?zé)o前期，最后一個(gè)無后繼，其他元素有 且僅有一個(gè)前驅(qū)和后繼(2)

5、 有限性：元素個(gè)數(shù)的有限，計(jì)算機(jī)處理的對象是有限的(3) 相同性：元素取自同一個(gè)數(shù)據(jù)對象，每個(gè)元素占相同數(shù)量的存儲單元。(4) 抽象性：元素的類型是抽象的、不具體的，看具體問題。(5) 線性表的邏輯結(jié)構(gòu)：元素之前的前驅(qū)后繼關(guān)系A(chǔ)i稱為ai+i的前驅(qū)，后者是前者的后繼3. 抽象數(shù)據(jù)類型(掌握)InitList ( &L, maxsize, incresize)構(gòu)造一個(gè)容量為 maxsize 的空線性表 LClearList( &L)線性表L存在的前提下將線性表重置為空表ListEmpty( L)在線性表存在的前提下，若L為空表，則返回true，否則返回falseListLengt

6、h( L)在線性表L存在的前提下，返回L中元素的個(gè)數(shù)，即線性表的長度LocateElem( L，e)在表中找到與 e相等的第一個(gè)值的位序PriorElem ( L， cure，&pre -e) cur-e是L的元素，但不是第一個(gè)，就用pre-e返回它的前驅(qū)，若操作失敗，則pre-e無定義。NextElem ( L， cur-e，&next_e ) cur_e是L的元素，但不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無定義ListInsert (&L, i, e)線性表 L已存在且 K i<LengthList(L)，操作結(jié)果是在 L的第i

7、個(gè)元 素之前插入新的元素e, L的長度增1。ListDelete (&L, i, e)線性表 L已存在且非空，1 < i < LengthList(L),操作結(jié)果是刪除L的第i個(gè)元素，并用e返回其值，L的長度減1。GetElem(L , i, &e)線性表L已存在，且 K i< LengthList(L),操作結(jié)果是用 e返回L中 第i個(gè)元素的值。ListTraverse(L線性表L已存在，操作結(jié)果是依次輸出L中的每個(gè)數(shù)據(jù)元素。DestroyList(&L)線性表L已存在，操作結(jié)果是撤銷線性表L。4. 順序表(重點(diǎn)掌握)(1 )順序表的定義：用一組地址

8、連續(xù)的存儲單元一次存儲線性表里各個(gè)元素的存儲結(jié) 構(gòu)稱為線性表的順序存儲結(jié)構(gòu)。(常用程序設(shè)計(jì)語言中的一維數(shù)組來描述順序表中數(shù)據(jù)元素的存儲區(qū)域，也就是把線性表中相鄰的元素存儲在數(shù)組中相鄰的位置) 特點(diǎn):邏輯上相鄰的數(shù)據(jù)元素，其物理位置上也是相鄰的。(2)順序表中程序的存儲首址L. elew -aiV » «亜牛1p下標(biāo):01i-11fL.lengthL<丄 1假設(shè)每個(gè)數(shù)據(jù)元素占用k個(gè)存儲單元，loai)表示數(shù)據(jù)元素ai的存儲首址，則線性表中相鄰的兩個(gè)元素 ai與ai+1的存儲首址1oc(ai)與loc(ai+1)滿足下面的關(guān)系： loc(a+1)=1oc(a)+k (K

9、i < n)線性表中第i個(gè)元素ai的存儲首址為：1oc(a)=1oc(ai)+(i-1)*k(K i < n)由于表中每個(gè)元素的存儲首址都可由上面的公式計(jì)算求得，且計(jì)算所需的時(shí)間也是相同的，所以訪問表中任意元素的時(shí)間都相等，具有這一特點(diǎn)的存儲結(jié)構(gòu)稱為隨機(jī)存取結(jié)構(gòu)。(3)拓展：ElemType(也有的書上稱之為elemtp)是數(shù)據(jù)結(jié)構(gòu)的書上為了說明問題而用的一個(gè)詞。它是element type ("元素的類型”)的簡化體，ElemType的默認(rèn)是int型。In creme ntsize貌似是增加線性表空間大小的意思L. elem表示訪問L結(jié)構(gòu)體中的成員 elem , L_e

10、lem表示的是一個(gè)變量或者結(jié)構(gòu)體的名字靜態(tài)存儲分配的順序表：# define LIST_INIT_SIZE 100 typedef struct ElemType elem LIST_INIT_SIZE;int len gth; SSqList;動態(tài)存儲分配的順序表：# define LISTINCREMENT 10typedef struct ElemType *elem;int len gth;int listsize;int in creme ntsize; SqList;辨析A線性表的長度是線性表中數(shù)據(jù)元素的個(gè)數(shù)，隨著線性表插入和刪除操作的進(jìn)行，這個(gè)量是變化的；數(shù)組的長度是存放線性表的

11、存儲空間的長度，一旦存儲空間分配后，這個(gè)量確定不變。存儲結(jié)構(gòu)是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示存取結(jié)構(gòu)是在某種數(shù)據(jù)結(jié)構(gòu)上對訪問操作時(shí)間性能的描述B順序表是一種隨機(jī)存取的存儲結(jié)構(gòu)”的含義為：在順序表這種存儲結(jié)構(gòu)上進(jìn)行訪問 操作，其時(shí)間性能為 0(1)。順序存儲：順序表(重點(diǎn)掌握) sqlist隨機(jī)存儲結(jié)構(gòu)(1) 初始化void lnitList_Sq( SqList &L, int xsize=LIST_INIT_SIZE,intincresize=LISTINCREMENT ) L.elem=(ElemType *)malloc(maxsize*sizeof(ElemType);/(這

12、里是某種數(shù)據(jù)結(jié)構(gòu)，就假設(shè)這是一個(gè)線性表，它儲存的元素的數(shù)據(jù)類型為 ElemType (就像整型，浮點(diǎn)型，或者是自定義型等等)，表長為LIST-INIT-SIZE L是一個(gè)線性表，L的elem成員是這個(gè)線性表的首元素的地址，這個(gè)表達(dá)式的意思就是 分配一個(gè)長度為 LIST-INIT-SIZ帝ElemType長度的空間并強(qiáng)制轉(zhuǎn)換為ElemType類型的指針，將該指針的地址賦給 L.elem。這樣L就是一個(gè)已經(jīng)分配過空間的線性表了， 它已經(jīng)有了一個(gè)空的存儲空間，可以放LIST-INIT-SIZ帝ElemType類型的數(shù)據(jù))if(!L.elem) exit(1);L.length=0;Li stsize

13、=maxsize;L.incrementsize=incresize; InitList_Sq( 2)求表長( O(1)int ListLength_Sq(SqList L)return L.length;/ ListLength_Sq( 3)查找( O(n)int LocateElem_Sq( SqList L, ElemType e)for(int i=0;i<L. length;i+) if(L.elemi=e) return i;return -1;(因?yàn)镃/C+中數(shù)組的下標(biāo)是從 0開始，所以當(dāng)查找失敗時(shí)不能返回0,而應(yīng)該返回一個(gè)有效下標(biāo)之外的整數(shù) )/LocateElem_Sq

14、 4)前插(時(shí)間復(fù)雜度為O(n)bool ListInsert_Sq(SqList &L, int i, ElemType e) int j;if(i<0|i>L.length) return false; if(L.length>=L.listsize) L.elem=(ElemType *)realloc(L.elem,(L.listsize+L.incrementsize)*sizeof(ElemType);if(!L.elem) exit(1); L.listsize+=L.incrementsize; for(j=L.length;j>i;j-) L.

15、elemj=L.elemj-1;L.elemi=e;L.length+; return true;/ ListInsert_Sq(拓展：A： realloc動態(tài)內(nèi)存調(diào)整先判斷當(dāng)前的指針是否有足夠的連續(xù)空間，如果有，擴(kuò) 大，并且將 mem_address 返回，如果空間不夠，先按照 newsize 指定的大小分 配空間。B： malloc動態(tài)內(nèi)存分布 向系統(tǒng)申請分配指定 size個(gè)字節(jié)的內(nèi)存空間。 返回類型 是void*類型。void*表示未確定類型的指針。 C,C+規(guī)定，void*類型可以通 過類型轉(zhuǎn)換強(qiáng)制轉(zhuǎn)換為任何其它類型的指針C： sizeof C語言中判斷數(shù)據(jù)類型或者表達(dá)式長度符D： i

16、ncrementsize增量大小，增補(bǔ)一段空間 )E： calloc動態(tài)內(nèi)存分配并清零：功 能:在內(nèi)存的動態(tài)存儲區(qū)中分配n個(gè)長度為size的連續(xù)空間，函數(shù)返回一個(gè)指向分配起始地址的指針；如果分配不成功，返回 NULLF: _alloca，內(nèi)存分配函數(shù)， 與malloc,calloc,realloc類似，但是注意一個(gè)重要的 區(qū)別，_alloca是在棧(stack)上申請空間，用完馬上就釋放。(5)刪除(時(shí)間復(fù)雜度為O(n)bool ListDelete_Sq(SqList &L,int i, ElemType &e)int j;if(i<0|i>=L.length)

17、return false; if(L.length<=0) return false;( 首先判斷刪除的位置是否合理)e=L.elemi;for(j=i+1;j<=L.length-1;j+)L.elem j-1=L.elem j;(元素依次向前移，同時(shí)線性表長度減1)L.length-;return true;/ ListDelete_Sq ( 6)取數(shù)據(jù)元素bool GetElem_Sq(SqList L,int i, ElemType &e) if(i<0|i>L.length) return false; if(L.length<=0) retur

18、n false;e=L.elemi;return true;/ GetElem_Sq (7)順序表的遍歷( O(n)， n 為順序表的長度，遍歷就是打印出這個(gè)表里的所有數(shù)據(jù)元 素)Traverse 橫穿(拓展：cout<<setw(10)是給下一個(gè)輸出的量，設(shè)定輸出場寬為10個(gè)字符,輸出量不足 10 個(gè)字符時(shí)在左面填空白，輸出量寬于 10個(gè)字符，則按實(shí)際需要 全部輸出， eg，A： cout<<setfill('*')<<setw(5)<<'a'<<endl;則輸出：*a 4個(gè)*和字符a共占5個(gè)位置)B

19、：char x="12345678"char y="123456789abcd" cout<<setw(10)<<x<<endl; / 輸出：白白 12345678 cout<<x<<endl; / 輸出： 12345678cout<<setw(10)<<y<< endl; / 輸出： 123456789abcd( 8)撤銷順序表 void DestroyList_Sq(SqList &L)free(L.elem); L.elem=NULL;L.lis

20、tsize=0;L.length=0;/ DestroyList_Sq 在順序表上的各種操作中，插入和刪除是時(shí)間復(fù)雜度最高的操作，時(shí)間主要消費(fèi)在移其一是順序表的長度； 其二是被動數(shù)據(jù)元素中， 所需移動數(shù)據(jù)元素的個(gè)數(shù)和兩個(gè)因素有關(guān)：插或被刪元素在順序表中的位置以插入為例，假設(shè)Pi為在第i（i從0開始）個(gè)數(shù)據(jù)元素之前插入一個(gè)數(shù)據(jù)元素的概率，則在長度為n的順序表中插入一個(gè)數(shù)據(jù)元素時(shí)所需移動數(shù)據(jù)元素的平均次數(shù)E =乞P"-補(bǔ)i-0假設(shè)在順序表的任何位置上插入數(shù)據(jù)元素都是等概率的同理，可推出在順序表中刪除一個(gè)數(shù)據(jù)元素的平均移動次數(shù)為n IE =2鏈?zhǔn)酱鎯Γ烘湵?Linklist（1） 定義用一

21、組任意的存儲單元存儲在線性表里的各元素，這些存儲單元可以連續(xù)也可以不 連續(xù)，為了反映元素在線性表中的前后位置關(guān)系，除了元素本身的信息外還需要添 加一個(gè)或者多個(gè)指針域，來表示另一個(gè)數(shù)據(jù)元素在內(nèi)存中的存儲首址，這叫做線性 表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，且其特點(diǎn)是邏輯上相鄰的元素其物理位置不一定相鄰。 T 103000200 F *£ a i 、r u*0300A鏈表的結(jié)點(diǎn)結(jié)構(gòu)存儲數(shù)據(jù)元素的數(shù)據(jù)域和存儲另一數(shù)據(jù)元素的地址的指針域組成了數(shù)據(jù)元素的存儲映像，稱為結(jié)點(diǎn) 鏈表的分類A:根據(jù)指針個(gè)數(shù)，單鏈表（結(jié)點(diǎn)中一個(gè)指針域）；多重鏈表（結(jié)點(diǎn)中多個(gè)指針域）B:根據(jù)結(jié)點(diǎn)中指針的鏈接方式：普通鏈接和循環(huán)鏈接（2）

22、單鏈表A:定義最簡單的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，一個(gè)結(jié)點(diǎn)只含一個(gè)指針域，指針域用來存放其后繼 結(jié)點(diǎn)的地址。datanex t存啟數(shù)抵信息存枚F個(gè)絡(luò)點(diǎn)時(shí)眥址B：結(jié)點(diǎn)結(jié)構(gòu)描述(node結(jié)點(diǎn))typedef struct Node ElemType data;struct Node *next;LNode,*LinkList； typedef為C語言的關(guān)鍵字，作用是為一種數(shù)據(jù)類型定義一個(gè)新名字。 這里的數(shù)據(jù)類型包括內(nèi)部數(shù)據(jù)類型(int,char等)和自定義的數(shù)據(jù)類型(struct等)。在編程中使用typedef目的一般有兩個(gè)，一個(gè)是給變量一個(gè)易記且意義明確的新名字， 另一個(gè)是簡化一些比較復(fù)雜的類型聲明。)C

23、:單鏈表的邏輯表示：頭結(jié)點(diǎn)：單鏈表中第一個(gè)結(jié)點(diǎn)。表頭指針：存放單鏈表中第一個(gè)結(jié)點(diǎn)的地址。表尾結(jié)點(diǎn)：單鏈表中最后一個(gè)結(jié)點(diǎn)，表尾結(jié)點(diǎn)的指針域指針為空。開始結(jié)點(diǎn)：存放線性表的第一個(gè)元素的結(jié)點(diǎn)。頭結(jié)點(diǎn)在鏈表中并不是必須的，僅僅是為了操作上的方便。 單鏈表(linklist非隨機(jī)存儲結(jié)構(gòu)，重點(diǎn)掌握)(1) 初始化void InitList_L(LinkList &L) L=(LNode *)malloc(sizeof(LNode);if(!L) exit(1); L->next=NULL;/ InitList_L(2) 求表長int ListLength_L( LinkList L ) L

24、inkList p;int k=0;p=L->next;while(p) k+; p=p->next; return k;/ ListLength_L->運(yùn)算符叫做“指向結(jié)構(gòu)體成員運(yùn)算符”，是C語言和C+語言的一個(gè)運(yùn)算符，用處是使用一個(gè)指向結(jié)構(gòu)體或?qū)ο蟮闹羔樤L問其內(nèi)成員。(3) 查找LNode *LocateElem_L(LinkList L,ElemType e) LinkList p; p=L->next;while(p&&p->data!=e )(意思就是 p != NULL的意思，先判斷 p不為NULL，否則直接 p->data，當(dāng)p

25、為NULL的時(shí)候會出異常。)p=p->next; return p;/ LocateElem_L(4)插入圖2. 11單鏈表插入操作示意圖基本語句土®s->next=p->next;/把結(jié)點(diǎn)p的后繼作為結(jié)點(diǎn)£的后罐(Shj-nex l=s ./把結(jié)點(diǎn)s作為結(jié)點(diǎn)d的后繼兩個(gè)語句順序不可以改變，否則不可以進(jìn)行插入操作bool Listlnsert_L( LinkList L, int i, ElemType e)LinkList p,s;int j;P=L； j=0；while(p->next&&jvi-1) p=p->next;

26、j+; if(j!=i-1) return false;if(s=(LNode *)malloc(sizeof(LNode)=NULL) exit(1);s->data=e; s->next=p->next; p->next=s; return true;/ ListInsert_L(&&兩邊都要是true才會true ,邏輯運(yùn)算符；&與運(yùn)算，eg :1&0=0,1 &1=1,0&0=0,0&仁0 ;邏輯或運(yùn)算，一個(gè)滿足則true)(5)刪除圖£ 12存單鏈表中刪除一亍結(jié)點(diǎn)的過程裁本語句；(l)p->

27、;next-7/結(jié)點(diǎn)口的后縷成為結(jié)點(diǎn)d的后案c q->datn;/淺劇兀倉的值賦給©free(q) ;7/釋放叢(除結(jié)點(diǎn)的空間bool ListDelete_L( LinkList L, int i, ElemType &e)LinkList p,q;int j;p=L; j=0;while(p->next&&p->next->next&&j<i-1) p=p->next; j+; if(j!=i-1) return false;q=p->next; p->next=q->next;e=q->data; free(q); return true;/ ListDelete_L (while 中的條件表達(dá)式中的“ p->next->next ”是為了保證第 結(jié)點(diǎn)存在)6) 取元素bool GetElem_L(LinkList L,int i, ElemType &e)LinkList p;int j;p=L; j=0; while(p->n