數(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í)際意

2、義。數(shù)據(jù)對(duì)象——具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)——是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：Data_Structure=（D, R）數(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)題求解步驟的一種描述，它是指令的有限序列，是一

3、系列輸入轉(zhuǎn)換為輸出的計(jì)算步驟。算法的基本特性：輸入、輸出、有窮性、確定性、可行性 ◆ 算法設(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ǔ)

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

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

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