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

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

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

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

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

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

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

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

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

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

10、lem表示的是一個變量或者結(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ù)元素的個數(shù)，隨著線性表插入和刪除操作的進行，這個量是變化的；數(shù)組的長度是存放線性表的

11、存儲空間的長度，一旦存儲空間分配后，這個量確定不變。存儲結(jié)構(gòu)是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示存取結(jié)構(gòu)是在某種數(shù)據(jù)結(jié)構(gòu)上對訪問操作時間性能的描述B順序表是一種隨機存取的存儲結(jié)構(gòu)”的含義為：在順序表這種存儲結(jié)構(gòu)上進行訪問 操作，其時間性能為 0(1)。順序存儲：順序表(重點掌握) sqlist隨機存儲結(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è)這是一個線性表，它儲存的元素的數(shù)據(jù)類型為 ElemType (就像整型，浮點型，或者是自定義型等等)，表長為LIST-INIT-SIZE L是一個線性表，L的elem成員是這個線性表的首元素的地址，這個表達式的意思就是 分配一個長度為 LIST-INIT-SIZ帝ElemType長度的空間并強制轉(zhuǎn)換為ElemType類型的指針，將該指針的地址賦給 L.elem。這樣L就是一個已經(jīng)分配過空間的線性表了， 它已經(jīng)有了一個空的存儲空間，可以放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;(因為C/C+中數(shù)組的下標是從 0開始，所以當查找失敗時不能返回0,而應(yīng)該返回一個有效下標之外的整數(shù) )/LocateElem_Sq

14、 4)前插(時間復雜度為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)整先判斷當前的指針是否有足夠的連續(xù)空間，如果有，擴 大，并且將 mem_address 返回，如果空間不夠，先按照 newsize 指定的大小分 配空間。B： malloc動態(tài)內(nèi)存分布 向系統(tǒng)申請分配指定 size個字節(jié)的內(nèi)存空間。 返回類型 是void*類型。void*表示未確定類型的指針。 C,C+規(guī)定，void*類型可以通 過類型轉(zhuǎn)換強制轉(zhuǎn)換為任何其它類型的指針C： sizeof C語言中判斷數(shù)據(jù)類型或者表達式長度符D： i

16、ncrementsize增量大小，增補一段空間 )E： calloc動態(tài)內(nèi)存分配并清零：功 能:在內(nèi)存的動態(tài)存儲區(qū)中分配n個長度為size的連續(xù)空間，函數(shù)返回一個指向分配起始地址的指針；如果分配不成功，返回 NULLF: _alloca，內(nèi)存分配函數(shù)， 與malloc,calloc,realloc類似，但是注意一個重要的 區(qū)別，_alloca是在棧(stack)上申請空間，用完馬上就釋放。(5)刪除(時間復雜度為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;(元素依次向前移，同時線性表長度減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 為順序表的長度，遍歷就是打印出這個表里的所有數(shù)據(jù)元 素)Traverse 橫穿(拓展：cout<<setw(10)是給下一個輸出的量，設(shè)定輸出場寬為10個字符,輸出量不足 10 個字符時在左面填空白，輸出量寬于 10個字符，則按實際需要 全部輸出， eg，A： cout<<setfill('*')<<setw(5)<<'a'<<endl;則輸出：*a 4個*和字符a共占5個位置)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ù)據(jù)元素中， 所需移動數(shù)據(jù)元素的個數(shù)和兩個因素有關(guān)：插或被刪元素在順序表中的位置以插入為例，假設(shè)Pi為在第i（i從0開始）個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素的概率，則在長度為n的順序表中插入一個數(shù)據(jù)元素時所需移動數(shù)據(jù)元素的平均次數(shù)E =乞P"-補i-0假設(shè)在順序表的任何位置上插入數(shù)據(jù)元素都是等概率的同理，可推出在順序表中刪除一個數(shù)據(jù)元素的平均移動次數(shù)為n IE =2鏈式存儲：鏈表 Linklist（1） 定義用一

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

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

23、:單鏈表的邏輯表示：頭結(jié)點：單鏈表中第一個結(jié)點。表頭指針：存放單鏈表中第一個結(jié)點的地址。表尾結(jié)點：單鏈表中最后一個結(jié)點，表尾結(jié)點的指針域指針為空。開始結(jié)點：存放線性表的第一個元素的結(jié)點。頭結(jié)點在鏈表中并不是必須的，僅僅是為了操作上的方便。 單鏈表(linklist非隨機存儲結(jié)構(gòu)，重點掌握)(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->運算符叫做“指向結(jié)構(gòu)體成員運算符”，是C語言和C+語言的一個運算符，用處是使用一個指向結(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，當p

25、為NULL的時候會出異常。)p=p->next; return p;/ LocateElem_L(4)插入圖2. 11單鏈表插入操作示意圖基本語句土®s->next=p->next;/把結(jié)點p的后繼作為結(jié)點£的后罐(Shj-nex l=s ./把結(jié)點s作為結(jié)點d的后繼兩個語句順序不可以改變，否則不可以進行插入操作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 ,邏輯運算符；&與運算，eg :1&0=0,1 &1=1,0&0=0,0&仁0 ;邏輯或運算，一個滿足則true)(5)刪除圖£ 12存單鏈表中刪除一亍結(jié)點的過程裁本語句；(l)p->

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