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

1、第1章緒論緒論內(nèi)容提要：內(nèi)容提要：◆數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。針對非數(shù)值計(jì)算的程序設(shè)計(jì)問題，研究計(jì)算機(jī)的操作對象以及它們之間的關(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ù)——所有能被計(jì)算機(jī)識別、存儲和處理的符號的集合。數(shù)據(jù)元素——是數(shù)據(jù)的基本單位，具有完整確定的實(shí)際意義。數(shù)據(jù)對象——具有相同

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

3、法的基本特性：輸入、輸出、有窮性、確定性、可行性◆算法設(shè)計(jì)要求。算法設(shè)計(jì)要求。①正確性、②可讀性、③健壯性、④效率與低存儲量需求◆算法分析。算法分析。時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性學(xué)習(xí)重點(diǎn)：學(xué)習(xí)重點(diǎ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)上所定義的操作（運(yùn)算）（運(yùn)算）?！粲糜?jì)算語句頻度來估算算法的時間復(fù)雜度。用計(jì)算語句頻度來估算算法的時間復(fù)雜

4、度。順序表刪除一元素的時間效率為:T（n)=(n1)2≈O(n)順序表插入、刪除算法的平均空間復(fù)雜度為O(1)單鏈表：單鏈表：（1）用單鏈表結(jié)構(gòu)來存放26個英文字母組成的線性表（a，b，c，…，z）請寫出C語言程序。#include#includetypedefstructnodedatastructnodenextnodenodepqhead一般需要3個指針變量intn數(shù)據(jù)元素的個數(shù)intm=sizeof(node)結(jié)構(gòu)類型定義好之后

5、，每個node類型的長度就固定了，m求一次即可voidbuild()字母鏈表的生成。要一個個慢慢鏈入intihead=(node)malloc(m)m=sizeof(node)前面已求出p=headf(i=1idata=i‘a(chǎn)’1第一個結(jié)點(diǎn)值為字符apnext=(node)malloc(m)為后繼結(jié)點(diǎn)“挖坑”！p=pnext；讓指針變量P指向后一個結(jié)點(diǎn)pdata=i‘a(chǎn)’1最后一個元素要單獨(dú)處理pnext=NULL單鏈表尾結(jié)點(diǎn)的指針域要