第1章 緒論
1.1什么是數據結構

1.1.1數據結構的定義
數據：描述客觀事物的數和字符的集合。
數據項：具有獨立含義的數據最小單位，也成字段或域。
數據對象:數據的一個子集。
數據結構:數據+結構。存在某種特定關系的數據元素的集合。

數據結構包括:
邏輯結構logical structure（數據和元素邏輯關系）
存儲結構storage structure（數據的物理結構，存儲表示）
運算operation（施加在數據上的操作）

1.1.2邏輯結構
1.邏輯結構的表示
圖表表示（圖形表示時，一個結點對應一個數據元素，兩結點之間帶箭頭連線表示相鄰關系）
二元組表示（B=(D,R)。R中序偶集合r中任意序偶〈x,y〉表示相鄰關系，x為y的前驅元素，y為x的后繼元素。若某個元素沒有前驅元素，則稱該元素為開始元素，若無后繼元素，則稱為終端元素。
對稱序偶在用圖形表示邏輯關系時，用不帶箭頭連線表示）
2.邏輯結構的類型
集合（除了同屬于一個集合，別無其他關系）
線性結構（數據元素存在一對一的關系。開始元素和終端元素都是唯一的。其余元素有且僅有一個前驅元素和后繼元素。線性表）
樹形結構（每個元素僅有一個前驅元素。除了終端元素，每個元素有一個或多個后繼元素。二叉樹）
圖形結構（數據元素之間多對多關系。可能無開始元素和終端元素也可能有多個）

1.1.3存儲結構
1.順序存儲結構:將數據的邏輯結構直接映射到存儲結構。
優點:存儲效率高，可實現隨機存取，由序號直接計算元素的存儲地址。
缺點:不便于數據修改，插入或刪除需要移動一系列元素。
Stud用于唯一標識順序存儲結構，作為數組的起始地址。Stud［i］放在Stud[i+1]之前。
2.鏈式存儲結構:給每個結點附加指針域用于存放相鄰結點的存儲地址，也就是通過指針域將所有結點鏈接起來。
優點：便于數據修改，對元素插入刪除僅需修改相應結點指針域，不必移動結點。
缺點:存儲空間利用率較低，不可隨機存取。
首結點指針為head，尾結點指針域為空.一個結點的next指向后繼結點。每個結點采用StudType類型單獨存儲。
3.索引存儲結構:存儲數據元素信息的同時還建立附加的索引表。
優點：查找效率高
缺點：需要建立索引表，增加空間開銷。
4.哈希存儲結構：根據元素的關鍵字通過哈希函數直接計算一個值，并將這個值作為元素的存儲地址。（只適合要求對數據能夠快速查找和插入的場合）
有點：查找速度快，根據關鍵字計算存儲地址。

1.1.4數據運算
檢索、插入、刪除、更新、排序
運算定義<——>邏輯結構——>存儲結構<——>運算實現

1.1.5數據類型和抽象數據類型
一、數據類型
1.C/C++常用數據類型
（1）基本數據類型：int、bool、float、double、char。
int取值范圍-32768~32767，可用±*/運算符

（2）C/C++指針類型
int i,*p ;

int i=2,*p=&i ;

（3）C/C++數組類型
int a[10]包含a[0]~a[9]

(4)C/C++結構體類型
Teacher結構類型：
struct Teacher
{int no ;
char name[8];
int age;};

定義Teacher的一個結構體變量t并賦值：
struct Teacher;
t.no=85;
strcpy(t.name,“張敏”)；
t.age=42;
引用no 成員t.no,引用name成員t.name,引用age成員t.age.
t變量所分配的內存空間大小為所有成員占用的內存空間之和。
（5）C/C++共用體類型
一個共用體類型Tag：
union Tag
{ short int n;
char ch[2];
};

一個共用體變量u賦值：
union Tag u；
u.n=0x4142;
引用n成員u.n，引用ch成員ch[0]為u.ch[0]
u變量所分配的內存空間大小為所有成員占用空間的最大值。
（6）C語言中自定義類型
typedef char ElemType;

2.存儲空間的分配
（1）靜態存儲空間的分配
int a[10];
(2)動態存儲空間的分配
char *p;
p=(char * )malloc(10 * sizeof(char));//動態分配10個連續字符的空間
strcpy(p,“China”)；//將“China”存放到p所指的空間中
printf("%c\n",*p);//輸出首字符C
printf("%s\n",p);//輸出字符串“China”
free§;//釋放p所指的空間

二、抽象數據類型
ATD抽象數據類型名
{ 數據對象：數據對象的聲明
數據關系：數據關系的聲明
基本運算：基本運算的聲明
}
基本運算聲明格式為：
基本運算名（參數表）：運算功能描述

一個復數抽象數據類型Complex定義如下：
ATD complex
{
數據對象：
D={e1,e2|e1,e2均為實數}
數據關系：
R={<e1,e2>|e1是復數的實數部分，e2是復數的虛數部分}
基本運算：

}

1.2算法及其描述
1.2.1什么是算法
五個重要特性：有窮性、確定性、可行性、有輸入、有輸出

1.2.2算法設計的目標
正確性、可使用性、可讀性、健壯性、高效率與低存儲量需求

1.2.3算法描述
1.算法描述的一般格式與計算步驟
（1）分析算法功能
（2）確定輸入輸出
（3）設計函數體
2.輸出型參數的設計
將輸出型形參設計為引用型形參：
void swap（int &x,int &y）
{
int tmp=x;
x=y;y=tmp;
}

1.3算法分析
1.3.1算法分析CPU時間和內存空間
時間性能分析和空間性能分析

1.3.2算法時間性能分析
1.兩種分析方法：事后統計法、事前估算法
2.算法時間復雜度分析：
（1）計算算法的頻度T（n）
算法時間分析就是求出所有原操作的執行次數（也稱頻度），它是問題規模的函數，用T（n）表示。
算法執行時間=原操作所需時間*T(n).因此T(n)與算法執行時間成正比。
（2）T（n）用“O”表示
時間復雜度O（f(n)）為T（n）數量級。記作T（n）=O(f(n))

(3)簡化的算法時間復雜度的分析
基本操作所需時間*運算次數
（4）時間復雜度的求和、求積定理
3.算法最好、最壞、和平均時間復雜度
4.遞歸算法時間復雜度分析

1.3.3算法空間性能分析
1.算法空間復雜度分析（存儲空間大小的量度）
S（n）=O(g(n))
只考慮臨時空間，不考慮形參。
占用存儲空間大小與問題規模n無關。
2.遞歸算法空間復雜度分析

總結

以上是生活随笔為你收集整理的数据结构教程 李春葆主编 （第5版）绪论笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。