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

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

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

3、法的基本特性：輸入、輸出、有窮性、確定性、可行性◆算法設(shè)計(jì)要求。算法設(shè)計(jì)要求。①正確性、②可讀性、③健壯性、④效率與低存儲(chǔ)量需求◆算法分析。算法分析。時(shí)間復(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)、物理（存儲(chǔ)）結(jié)構(gòu)物理（存儲(chǔ)）結(jié)構(gòu)及在及在這種結(jié)構(gòu)上所定義的操作這種結(jié)構(gòu)上所定義的操作（運(yùn)算）（運(yùn)算）?！粲糜?jì)算語(yǔ)句頻度來(lái)估算算法的時(shí)間復(fù)雜度。用計(jì)算語(yǔ)句頻度來(lái)估算算法的時(shí)間復(fù)雜

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

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