數(shù)據(jù)結(jié)構(gòu)知識點全面總結(jié)—精華版

1、第 1 章 緒論 緒論 內(nèi)容提要： 內(nèi)容提要：◆ 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。針對非數(shù)值計算的程序設(shè)計問題，研究計算機的操作對象以及它們之間的關(guān)系和操作。數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容：◆ 基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型。 基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型。數(shù)據(jù)——所有能被計算機識別、存儲和處理的符號的集合。數(shù)據(jù)元素——是數(shù)據(jù)的基本單位，具有完整確定的實際意

2、義。數(shù)據(jù)對象——具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)——是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：Data_Structure=（D, R）數(shù)據(jù)類型——是一個值的集合和定義在該值上的一組操作的總稱。抽象數(shù)據(jù)類型——由用戶定義的一個數(shù)學模型與定義在該模型上的一組操作，它由基本的數(shù)據(jù)類型構(gòu)成?！?算法的定義及五個特征。 算法的定義及五個特征。算法——是對特定問題求解步驟的一種描述，它是指令的有限序列，是一

3、系列輸入轉(zhuǎn)換為輸出的計算步驟。算法的基本特性：輸入、輸出、有窮性、確定性、可行性 ◆ 算法設(shè)計要求。 算法設(shè)計要求。①正確性、②可讀性、③健壯性、④效率與低存儲量需求◆ 算法分析。 算法分析。時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性學習重點： 學習重點：◆ 數(shù)據(jù)結(jié)構(gòu)的“三要素”： 數(shù)據(jù)結(jié)構(gòu)的“三要素”：邏輯結(jié)構(gòu) 邏輯結(jié)構(gòu)、物理（存儲）結(jié)構(gòu) 物理（存儲）結(jié)構(gòu)及在 及在這種結(jié)構(gòu)上所定義的操作 這種結(jié)構(gòu)上所定義的操作（運算） （運算） 。◆ 用計算語

4、句頻度來估算算法的時間復(fù)雜度。 用計算語句頻度來估算算法的時間復(fù)雜度。順序表刪除一元素的時間效率為:T（n)=(n-1)/2 ≈O(n) 順序表插入、刪除算法的平均空間復(fù)雜度為 O(1)單鏈表： 單鏈表：（1）用單鏈表結(jié)構(gòu)來存放 26 個英文字母組成的線性表（a，b，c，…，z）,請寫出 C 語言程序。#include#includetypedef struct node{char data; struct node *next;}no

5、de; node *p,*q,*head; //一般需要 3 個指針變量int n ; // 數(shù)據(jù)元素的個數(shù)int m=sizeof(node); /*結(jié)構(gòu)類型定義好之后，每個 node 類型的長度就固定了，m 求一次即可*/void build( ) //字母鏈表的生成。要一個個慢慢鏈入{ int i;head=(node*)malloc

6、(m); //m=sizeof(node) 前面已求出p=head;for( i=1; idata=i+‘a(chǎn)’-1; // 第一個結(jié)點值為字符 ap->next=(node*)malloc(m); //為后繼結(jié)點“挖坑”！p=p->next；} //讓指針變量 P 指向后一個結(jié)點p->data=i+‘a(chǎn)’-1; //最后一個元素要單