數據結構知識點全面總結—精華版

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

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

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

4、句頻度來估算算法的時間復雜度。 用計算語句頻度來估算算法的時間復雜度。順序表刪除一元素的時間效率為:T（n)=(n-1)/2 ≈O(n) 順序表插入、刪除算法的平均空間復雜度為 O(1)單鏈表： 單鏈表：（1）用單鏈表結構來存放 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 ; // 數據元素的個數int m=sizeof(node); /*結構類型定義好之后，每個 node 類型的長度就固定了，m 求一次即可*/void build( ) //字母鏈表的生成。要一個個慢慢鏈入{ int i;head=(node*)malloc

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