數(shù)據(jù)結構復習要點(整理版)

1、第一章數(shù)據(jù)結構概述基本概念與術語1數(shù)據(jù)：數(shù)據(jù)是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中并被計算機程序所處理的符號的總稱。2.數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個集合中的個體，也稱之為元素，結點，頂點記錄。 （補充：一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。）3數(shù)據(jù)對象：數(shù)據(jù)對象是具有相同性質的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。（有時候也叫做屬性。）4數(shù)據(jù)結構：數(shù)據(jù)結構是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。（1）數(shù)據(jù)的邏輯結構：數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間存在的固有邏輯關系，常稱為數(shù)據(jù)結構。數(shù)據(jù)的邏輯結構是從數(shù)據(jù)元素之間存在的

2、邏輯關系上描述數(shù)據(jù)與數(shù)據(jù)的存儲無關，是獨立于計算機的。 依據(jù)數(shù)據(jù)元素之間的關系，可以把數(shù)據(jù)的邏輯結構分成以下幾種：1.集合：數(shù)據(jù)中的數(shù)據(jù)元素之間除了“同屬于一個集合“的關系以外，沒有其他關系。2.線性結構：結構中的數(shù)據(jù)元素之間存在“一對一“的關系。若結構為非空集合，則除了第一個元素之外，和最后一個元素之外，其他每個元素都只有一個直接前驅和一個直接后繼。3.樹形結構：結構中的數(shù)據(jù)元素之間存在“一對多“的關系。若數(shù)據(jù)為非空集，則除了第一個元素（根）之外，其它 每個數(shù)據(jù)元素都只有一個直接前驅，以及多個或零個 直接后繼。4.圖狀結構：結構中的數(shù)據(jù)元素存在“多對多”的關系。若結構為非空集，折每個數(shù)據(jù)可有

3、多個（或零個）直接后繼。（2）數(shù)據(jù)的存儲結構：數(shù)據(jù)元素及其關系在計算機內的表示稱為數(shù)據(jù)的存儲結構。想要計算機處理數(shù)據(jù)，就必須把數(shù)據(jù)的邏輯結構映射為數(shù)據(jù)的存儲結構。邏輯結構可以映射為以下兩種存儲結構：1.順序存儲結構：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置也相鄰的存儲單元中，借助元素在存儲器中的相對位置來表示數(shù)據(jù)之間的邏輯關系。2.鏈式存儲結構：借助指針表達數(shù)據(jù)元素之間的邏輯關系。不要求邏輯上相鄰的數(shù)據(jù)元素物理位置上也相鄰。 5.時間復雜度分析：1.常量階：算法的時間復雜度與問題規(guī)模n無關系T(n)=O(1) 2.線性階：算法的時間復雜度與問題規(guī)模n成線性關系T(n)=O(n) 3.平方階和立方階

4、：一般為循環(huán)的嵌套，循環(huán)體最后條件為i+時間復雜度的大小比較：O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n )<O(n!)<O(n n)6.算法與程序：（1）算法的5個特性1、 輸入：有零個或多個輸入2、 輸出：有一個或多個輸出3、有窮性：要求序列中的指令是有限的；每條指令的執(zhí)行包含有限的工作量；整個指令序列的執(zhí)行在有限的時間內結束。（程序與算法的區(qū)別在于，程序不需要有有窮性）4、確定性：算法中的每一個步驟都必須是確定的，而不應當含糊、模棱兩可。沒有歧義。5、可行性：算法中的

5、每一個步驟都應當能被有效的執(zhí)行，并得到確定的結果。（2）.算法設計的要求： 1、正確性（達到預期效果，滿足問題需求） 2、健壯性（能處理合法數(shù)據(jù)，也能對不合法的數(shù)據(jù)作出反應，不會產生不可預期的后果） 3、可讀性（要求算法易于理解，便于分析） 4、可修改可擴展性 5、高效率（較好的時空性能 ）補充內容：1、名詞解釋：數(shù)據(jù)結構、二元組數(shù)據(jù)結構就是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。二元組就是一種用來表示某個數(shù)據(jù)對象以及各個元素之間關系的有限集合。2、根據(jù)數(shù)據(jù)元素之間關系的不同，數(shù)據(jù)的邏輯結構可以分為集合、線性結構、樹形結構和圖狀結構四種類型。3、常見的數(shù)據(jù)存儲結構一般有兩種類型，它們分

6、別是順序存儲結構、鏈式存儲結構6.在一般情況下，一個算法的時間復雜度是問題規(guī)模的函數(shù)7.常見時間復雜度有：常數(shù)階O（1）、線性階O（n）、對數(shù)階O（log 2 n）、平方階O(n2)、指數(shù)階O(2n)。通常認為，具有常數(shù)階量級的算法是好算法，而具有指數(shù)階量級的算法是差算法。第二章線性表定義：線性表是n個數(shù)據(jù)元素的有限序列。 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。1.順序表結構線性表的順序存儲是指在內存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素，用這種存儲形式存儲的線性表稱為順序表。 2.單鏈表（1）鏈表結點結構線性表中的數(shù)據(jù)元素可以用任意的一組存儲單元來存儲，用指針表示邏輯關系邏輯相鄰的兩元

7、素的存儲空間可以是不連續(xù)的。（2）鏈表操作算法：初始化、插入、輸出、刪除、遍歷初始化：p=(struct student *)malloc(sizeof(struct student);插入： p->next=head->next; head->next=p;輸出：printf(“%d”,p->data);刪除：q=p->next; p->next = q->next ; free(q);結點遍歷： for(p=head;p;p=p->next);補充內容：1、線性表中，第一個元素沒有直接前驅，最后一個元素沒有直接后驅。2、在一個單鏈表中，若p所

8、指結點是q所指結點的前驅結點，則刪除結點q的操作語句為 P->next = q->next ; free(q);3、在長度為N的順序表中，插入一個新元素平均需要移動表中N/2個元素，刪除一個元素平均需要移動（N-1）/2個元素。4、若線性表的主要操作是在最后一個元素之后插入一個元素或刪除最后一個元素，則采用順序表存儲結構最節(jié)省運算時間。5、已知順序表中每個元素占用3個存儲單元，第13個元素的存儲地址為336，則順序表的首地址為300。（第n個元素的地址即首地址+(n-1)*每個元素的存儲空間，如a12（第13個元素）的地址=a0+12*3）6、設有一帶頭結點單鏈表L，請編寫該單鏈表

9、的初始化，插入、輸出和刪除函數(shù)。（函數(shù)名自定義）結點定義：typedef int datatype;/結點數(shù)據(jù)類型，假設為inttypedef struct node /結點結構 datatype data; struct node *next; /雙向鏈表還應加上*previous Lnode, * pointer ; /結點類型,結點指針類型typedef pointer lklist;/單鏈表類型，即頭指針類型1.初始化：lklist initlist() pointer head; head=new node;/這是C+做法 /head=( pointer)malloc(sizeof(

10、Lnode); 這是C語言做法 head->next=NULL; /循環(huán)鏈表則是head->next=head;/雙向鏈表應加上head->previos=NULL; return head; 2.插入：（C語言中需要把head轉化為全局變量才能實現(xiàn)此程序）int insert(lklist head,datatype x,int i) pointer q,s; q=get(head,i-1);/找第i-1個點 if(q=NULL) /無第i-1點，即i<1或i>n+1時cout<<”非法插入位置!n”; /這是C+做法，即C語言中的 printf(“

11、非法插入位置!n”);return 0; s=new node;/生成新結點 即C語言中的 s=( pointer)malloc(sizeof(Lnode); s->data=x; s->next=q->next; /新點的后繼是原第i個點 q->next=s;/原第i-1個點的后繼是新點 return 1;/插入成功3.刪除：（C語言中需要把head轉化為全局變量才能實現(xiàn)此程序）int delete(lklist head,int i) pointer p,q; q=get(head,i-1);/找待刪點的直接前趨 if(q=NULL | q->next=NUL

12、L)/即i<1或i>n時 cout<<”非法刪除位置!n”;return 0; p=q->next;/保存待刪點地址 q->next=p->next;/修改前趨的后繼指針 delete p;/釋放結點 即C語言中的 free(p); return 1;/刪除成1.不帶頭結點的單鏈表head為空的判定條件是(A )A. head=NULL B. head->next=NULL C. head->next=head D. head!=NULL2.帶頭結點的單鏈表head為空的判定條件是(B )A. head=NULL B. head->n

13、ext=NULL C. head->next=head D. head!=NULL3.在一個單鏈表中，若p所指結點不是最后結點，在p之后插入s所指結點，則執(zhí)行(B )A. s->next=p; p->next=s; B. s->next=p->next; p->next=s;C. s->next=p->next; p=s; D. p->next=s; s->next=p;4.在一個單鏈表中，若刪除p所指結點的后續(xù)結點，則執(zhí)行(A )A. p->next=p->next->next;B. p=p->next; p

14、->next=p->next->next;C. p->next=p->next D. p=p->next->next5.從一個具有n個結點的有序單鏈表中查找其值等于x結點時，在查找成功的情況下，需平均比較（B ）個結點。A. n B. n/2 C. (n-1)/2 D. O(n2n) 6.給定有n個元素的向量，建立一個有序單鏈表的時間復雜度（B）A.O(1) B.O(n) C.O(n2) D.O(n2n)7.在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是(B)A.O(1) B.O(n) C.O(n2) D.O(n2n)8. 在一

15、個單鏈表中刪除q所指結點時，應執(zhí)行如下操作：q=p->next; p->next=( p->next->next ); free(q);/這種題目靠一根指針是沒有辦法完成的，必須要借助第二根指針。9. 在一個單鏈表中p所指結點之后插入一個s所指結點時，應執(zhí)行：s->next=( p->next ) p->next=(s)操作。10. 對于一個具有n個節(jié)點的單鏈表 ,在已知所指結點后插入一個新結點的時間復雜度是(O（1）)；在給定值為x的結點后插入一個新結點的時間復雜度是（O(n)）。11.問答題線性表可用順序表或鏈表存儲。試問：(1) 兩種存儲表示各有

16、哪些主要優(yōu)缺點?順序表的存儲效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個運行期間不會發(fā)生改變，因此，不易擴充。同時，由于在插入或刪除時，為保持原有次序，平均需要移動一半(或近一半)元素，修改效率不高。鏈接存儲表示的存儲空間一般在程序的運行過程中動態(tài)分配和釋放，且只要存儲器中還有空間，就不會產生存儲溢出的問題。同時在插入和刪除時不需要保持數(shù)據(jù)元素原來的物理順序，只需要保持原來的邏輯順序，因此不必移動數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時，只能循鏈順序訪問，因此存取效率不高。 (2) 若表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素，

17、這時，應采用哪種存儲表示？為什么？應采用順序存儲表示。因為順序存儲表示的存取速度快，但修改效率低。若表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素，這時采用順序存儲表示較好。第三章棧和隊列1.棧（1）棧的結構與定義定義：限定僅在表尾進行插入或刪除操作的線性表。結構：typedef struct list int listsize; /棧的容量 struct list *head; /棧頂指針 struct list *base; /棧底指針（2）順序棧操作算法：入棧、出棧、判斷棧空等（這個是使用數(shù)組進行操作的，具體內容參照書本P46-47）（3）鏈棧的結構與定義2.隊

18、列（1）隊列的定義定義：只允許在表的一端進行插入，而在另一端刪除元素。-補充內容：1、一個棧的入棧序列為“ABCDE”，則以下不可能的出棧序列是（B）A. BCDAEB. EDACBC. BCADED. AEDCB2、棧的順序表示中，用TOP表示棧頂元素，那么?？盏臈l件是（D）A. TOP=STACKSIZEB. TOP=1C. TOP=0D. TOP=-13、允許在一端插入，在另一端刪除的線性表稱為隊列。插入的一端為表頭，刪除的一端為表尾。4、棧的特點是先進后出，隊列的特點是先進先出。5、對于棧和隊列，無論他們采用順序存儲結構還是鏈式存儲結構，進行插入和刪除操作的時間復雜度都是O(1)（即與

19、已有元素N無關）。6、已知鏈棧Q，編寫函數(shù)判斷棧空，如果?？談t進行入棧操作，否則出棧并輸出。（要求判斷?？铡⒊鰲?、入棧用函數(shù)實現(xiàn)）（詳看考點2）7.出隊與取隊頭元素的區(qū)別：出隊就是刪除對頭的數(shù)據(jù)元素，取隊頭元素是獲取對頭的數(shù)據(jù)元素值，不需要刪除。8.鏈棧與順序棧相比，比較明顯的優(yōu)點是：（D）A.插入操作比較容易 B.刪除操作比較容易 C.不會出現(xiàn)?？盏那闆r D.不會出現(xiàn)棧滿的情況考點1：隊列的編程：結構：typedef struct QNode int date; struct QNode *next; QNode,*QueuePtr;typedef struct QueuePtr front

20、; QueuePtr rear; LinkQueue;創(chuàng)建：LinkQueue InitQueue(LinkQueue Q) Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); Q.front->next=NULL; return (Q);入隊：LinkQueue EnQueue(LinkQueue Q,int e) QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); p->date=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return (Q)

21、; 出隊：LinkQueue DeQueue(LinkQueue Q) int e; QueuePtr p; p=Q.front->next; e=p->date; Q.front=p->next; printf("%d",e); if(Q.rear=p)Q.rear=Q.front=NULL; free(p); return (Q); 考點2：棧的編程：創(chuàng)建：struct list *creat() struct list *p; p=(struct list *)malloc(LEN); p->next=NULL; return(p); 入棧：s

22、truct list *push(struct list *head,int a) struct list *p; p=(struct list *)malloc(LEN); p->num=a; p->next=head; return(p);出棧：struct list *pop(struct list *head) struct list *p; p=head->next; free(head); return(p);判斷?？眨篿nt listempty(struct list *head)if(head->next)return 0;else return 1;第

23、四章 串 （不是重點內容）1.串是由零個或多個字符組成的有限序列2.串的賦值：x=abc;或x =abc;第五章 數(shù)組和廣義表 （不是重點內容）1. 多維數(shù)組中某數(shù)組元素的position求解。一般是給出數(shù)組元素的首元素地址和每個元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個元素所在的位置。2. 明確按行存儲和按列存儲的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲方式求解1中類型的題。3. 將特殊矩陣中的元素按相應的換算方式存入數(shù)組中。這些矩陣包括：對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式：三元組，帶輔助行向量的二元組，十字鏈表存儲。掌握將

24、稀疏矩陣的三元組或二元組向十字鏈表進行轉換的算法。補充內容：三元組：結構：typedef struct int i,j; /元素行下標及列下標 int e; /元素值 Triple;typedef struct int mu,nu,tu; /矩陣的行數(shù)、列數(shù)、非零元素個數(shù) Triple dataMAXSIZE+1; /矩陣包含的三元組表，data0未用 TSMatrix;十字鏈表：typedef struct OLNode int i,j; /元素行下標及列下標 int e; /元素值 struct OLNode *right,*down; /行的后繼以及列的后繼 OLNode，*OLink;

25、typedef struct int mu,nu,tu; /矩陣的行數(shù)、列數(shù)、非零元素個數(shù) OLink *rhead,*chead; /行和列的表頭指針組的首地址 CrossList;CrossList Creat（CrossList M） int m,n,t; scanf(“%d%d%d”,&m,&n,&t); M.mu=m;M.nu=n;M.tu=t; M.rhead=( OLink *)malloc(m+1)*sizeof(OLink); /開辟行表頭指針組 M.chead=( OLink *)malloc(n+1)*sizeof(OLink); /開辟行列頭指針

26、組 M.rhead=M.chead=NULL; /初始化 /接下來就是賦值和入鏈第六章 樹和二叉樹1樹（1）樹的概念及術語樹：n（n0）個結點的有限集合。當n0時，稱為空樹；任意一棵非空樹滿足以下條件： 有且僅有一個特定的稱為根的結點； 當n1時，除根結點之外的其余結點被分成m（m>0）個互不相交的有限集合T1,T2, ,Tm，其中每個集合又是一棵樹，并稱為這個根結點的子樹。（2） 結點的度：結點所擁有的子樹的個數(shù)。樹的度：樹中所有結點的度的最大值。（3） 葉子結點：度為0的結點，也稱為終端結點。分支結點：度不為0的結點，也稱為非終端結點。（4）孩子、雙親：樹中某結點的子樹的根結點稱為這

27、個結點的孩子結點，這個結點稱為它孩子結點的雙親結點；兄弟： 具有同一個雙親的孩子結點互稱為兄弟。 （5）路徑： 如果樹的結點序列n1, n2, , nk有如下關系：結點ni是ni+1的雙親（1<=i<k），則把n1, n2, , nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個數(shù)稱為路徑長度。 （6）祖先、子孫：在樹中，如果有一條路徑從結點x到結點y，那么x就稱為y的祖先，而y稱為x的子孫。（7）結點所在層數(shù)：根結點的層數(shù)為1；對其余任何結點，若某結點在第k層，則其孩子結點在第k+1層。樹的深度： 樹中所有結點的最大層數(shù)，也稱高度。（8）層序編號：將樹中結點按照從上層到下層、同層

28、從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。（9）有序樹、無序樹：如果一棵樹中結點的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據(jù)結構中討論的一般都是有序樹 （10）樹通常有前序（根）遍歷、后序（根）遍歷和層序（次）遍歷三種方式（樹，不是二叉樹，沒中序遍歷。)2二叉樹（1）二叉樹的定義：二叉樹是n（n0）個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。滿二叉樹：在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上。（滿二叉樹的特點：葉子只能出現(xiàn)在最下一層；只有度

29、為0和度為2的結點。） 完全二叉樹：對一棵具有n個結點的二叉樹按層序編號，如果編號為i（1in）的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中的位置完全相同。完全二叉樹的特點：1.在滿二叉樹中，從最后一個結點開始，連續(xù)去掉任意個結點，即是一棵完全二叉樹。2.葉子結點只能出現(xiàn)在最下兩層，且最下層的葉子結點都集中在二叉樹的左部；3. 完全二叉樹中如果有度為1的結點，只可能有一個，且該結點只有左孩子。4. 深度為k的完全二叉樹在k-1層上一定是滿二叉樹。（3）二叉樹的性質：性質1：二叉樹的第i層上最多有2i-1個結點（i1）。 性質2： 一棵深度為k的二叉樹中，最多有2k-1個結點，最少有k個

30、結點。深度為k且具有2k-1個結點的二叉樹一定是滿二叉樹性質3：在一棵二叉樹中，如果葉子結點數(shù)為n0，度為2的結點數(shù)為n2，則有: n0n21。（一個結點的度就是指它放出的射線） 性質4：具有n個結點的完全二叉樹的深度為 log2n +1。 性質5： 對一棵具有n個結點的完全二叉樹中從1開始按層序編號，則對于任意的序號為i（1in）的結點（簡稱為結點i），有： （1）如果i1，則結點i的雙親結點的序號為 i/2；如果i1，則結點i是根結點，無雙親結點。 （2）如果2in，則結點i的左孩子的序號為2i；如果2in，則結點i無左孩子。 （3）如果2i1n，則結點i的右孩子的序號為2i1；如果2i1

31、n，則結點 i無右孩子。 3二叉樹的遍歷（遞歸調用與訪問的順序不同而產生不同的遍歷方法）（1）先序遍歷void XianXu(BiTree T) if(T) printf("%c",T->data); /先訪問 XianXu(T->lchild); /再繼續(xù)遍歷 XianXu(T->rchild); （2）中序遍歷（3）后序遍歷4.森林與二叉樹的轉換 （1）同級以左為親，即左一結點的右孩子是與它同級的右一結點 （2）只認最左路線為親子路線，即結點的左孩子是它下一級結點的最左的元素5.哈夫曼樹（1）哈夫曼樹的基本概念：哈夫曼樹：給定一組具有確定權值的葉子結點

32、，帶權路徑長度最小的二叉樹。（2）哈夫曼樹的特點：1. 權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。 2. 只有度為0（葉子結點）和度為2（分支結點）的結點，不存在度為1的結點. （3）哈夫曼樹的構造算法思想及構造過程（森林與哈夫曼編碼）就是求各權值和路徑相乘之后疊加的最小值。-1、已知一棵完全二叉樹有47個結點，則該二叉樹有（C）個葉子結點。A. 6B. 12 C. 24 D.48解法如下：1+2+4+8+16=31 計算從第一層到n-1層的結點個數(shù)47-31=16 計算第n層的葉子結點個數(shù)16-16/2=8 計算第n-1層的葉子結點個數(shù)所以，葉子結點數(shù)=16+8=24 計算第n層和第n-1層的總葉子結點數(shù)2、已知遍歷一棵二叉樹的前序序列ABCDEFG和中序序列CBEDAFG，那么是下面哪棵樹（C