第一章、緒論

1、數(shù)據(jù)結(jié)構(gòu)三要素：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)（物理結(jié)構(gòu)）、數(shù)據(jù)的運算。

(1)邏輯結(jié)構(gòu)：是指數(shù)據(jù)元素之間的邏輯關(guān)系，即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。

(2)存儲結(jié)構(gòu)（物理結(jié)構(gòu)）：是指數(shù)據(jù)在計算機中的表示（又稱映像），是用計算機語言實現(xiàn)的邏輯結(jié)構(gòu)，它依賴于計算機語言。

• 順序存儲：把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)（e.g.數(shù)組）。
  • 優(yōu)點：①可以實現(xiàn)隨機存取；② 每個元素占用最少的存儲空間；
  • 缺點：只能使用相鄰的一整塊存儲單元，因此可能產(chǎn)生較多的外部碎片；
• 鏈?zhǔn)酱鎯Γ翰灰筮壿嬌舷噜彽脑卦谖锢砦恢蒙弦蚕噜?，借助指示元素存儲地址的指針來表示元素之間的邏輯關(guān)系（e.g.鏈表）。
  • 優(yōu)點：不會出現(xiàn)碎片現(xiàn)象，能充分利用所有存儲單元；
  • 缺點：①每個元素因存儲指針而占用額外的存儲空間；②只能實現(xiàn)順序存取；
• 索引存儲：在存儲元素信息的同時，還建立附加的索引表。索引表中的每項稱為索引項，索引項的一般形式是（關(guān)鍵字，地址）。
  • 優(yōu)點：檢索速度快；
  • 缺點：①附加的索引表額外占用存儲空間；②增加和刪除數(shù)據(jù)時也要修改索引表，因而會花費較多的時間（對索引表進行維護的時間開銷）；
• 散列存儲：又稱哈希（Hash）存儲，根據(jù)元素的關(guān)鍵字直接計算出該元素的存儲地址。
  • 優(yōu)點：檢索、增加和刪除結(jié)點的操作都很快；
  • 缺點：若散列函數(shù)（也稱哈希（Hash）函數(shù)）不好，則可能出現(xiàn)元素存儲單元的沖突，而解決沖突會增加時間和空間的開銷；

(3)數(shù)據(jù)的運算：包括運算的定義和實現(xiàn)。

• 運算的定義：是針對邏輯結(jié)構(gòu)的，指出運算的功能；
• 運算的實現(xiàn)：是針對存儲結(jié)構(gòu)的，指出運算的具體操作步驟。

2、數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，通常作為一個整體進行考慮和處理。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成，數(shù)據(jù)項是構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。例如：學(xué)生記錄就是一個數(shù)據(jù)元素，它由學(xué)號、姓名、性別等數(shù)據(jù)項組成。

3、數(shù)據(jù)對象：是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。

4、數(shù)據(jù)類型：是一個值的集合和定義在此集合上的一組操作的總稱。

• （1）原子類型：其值不可再分的數(shù)據(jù)類型；
• （2）結(jié)構(gòu)類型：其值可再分解為若干成分（分量）的數(shù)據(jù)類型；
• （3）抽象數(shù)據(jù)類型（ADT（Abstract Data Type））：抽象數(shù)據(jù)組織及與之相關(guān)的操作。描述了數(shù)據(jù)的邏輯結(jié)構(gòu)和抽象運算，通常用（數(shù)據(jù)對象，數(shù)據(jù)關(guān)系，基本操作集）這樣的三元組來表示，從而構(gòu)成一個完整的數(shù)據(jù)結(jié)構(gòu)定義。

5、數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

6、算法（Algorithm）：是對特定問題求解步驟的一種描述，它是指令的有限序列，其中的每條指令表示一個或多個操作。一個算法應(yīng)具有5個特性：

• （1）有窮性：一個算法必須總在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)完成；
• （2）確定性：算法中每條指令必須有確切的含義，對于相同的輸入只能得出相同的輸出；
• （3）可行性：算法中描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)；
• （4）輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定的對象的集合；
• （5）輸出：一個算法有一個或多個輸出，這些輸出是與輸入有著某種特定關(guān)系的量。

通常，設(shè)計一個“好”的算法應(yīng)考慮達到以下目標(biāo)：

• （1）正確性：算法應(yīng)能夠正確地解決求解問題；
• （2）可讀性：算法應(yīng)具有良好的可讀性，以幫助人們理解；
• （3）健壯性：輸入非法數(shù)據(jù)時，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果；
• （4）效率與低存儲量需求：效率是指算法執(zhí)行的時間，存儲量需求是指算法執(zhí)行過程中所需要的最大存儲空間，這兩者都與問題的規(guī)模有關(guān)。

7、時間復(fù)雜度

• （1）一個語句的頻度是指該語句在算法中被重復(fù)執(zhí)行的次數(shù)；
• （2）算法中所有語句的頻度之和記為T(n)，它是該算法問題規(guī)模n的函數(shù)，時間復(fù)雜度主要分析T(n)的數(shù)量級；
• （3）算法中基本運算（最深層循環(huán)內(nèi)的語句）的頻度與T(n)同數(shù)量級，因此通常采用算法中基本運算的頻度f(n)來分析算法的時間復(fù)雜度；
  • 取f(n)中隨n增長最快的項，將其系數(shù)置為1作為時間復(fù)雜度的度量。例如，f(n) = an³ + bn² + cn的時間復(fù)雜度為O(n³)；
• （4）算法的時間復(fù)雜度記為T(n) = O(f(n))；
  • 式中O的含義是T(n)的數(shù)量級，其嚴(yán)格的數(shù)學(xué)定義是：若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則存在正常數(shù)C和n0，使得當(dāng)n≥n0時，都滿足0≤T(n)≤Cf(n)。
• （5）算法的時間復(fù)雜度不僅依賴于問題的規(guī)模n，也取決于待輸入數(shù)據(jù)的性質(zhì)。
  • 最壞時間復(fù)雜度是指在最壞情況下，算法的時間復(fù)雜度；
  • 平均時間復(fù)雜度是指所有可能輸入實例在等概率出現(xiàn)的情況下，算法的期望運行時間；
  • 最好時間復(fù)雜度是指在最好情況下，算法的時間復(fù)雜度；
  • 一般總是考慮在最壞情況下的時間復(fù)雜度，以保證算法的運行時間不會比它更長；
• （6）在分析一個程序的時間復(fù)雜性時，有以下兩條規(guī)則：
  • 加法規(guī)則：T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n)，g(n)))；
  • 乘法規(guī)則：T(n) = T1(n) × T2(n) = O(f(n)) × O(g(n)) = O(f(n) × g(n))；
• （7）常見的漸近時間復(fù)雜度為：
  • O(1) < O(logn)（以2為底，后同） < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)；

8、空間復(fù)雜度

• （1）算法的空間復(fù)雜度S(n)定義為該算法所耗費的存儲空間，它是問題規(guī)模n的函數(shù)，記為S(n) = O(g(n))；
• （2）一個程序在執(zhí)行時除需要存儲空間來存放本身所用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要一些對數(shù)據(jù)進行操作的工作單元和存儲一些為實現(xiàn)計算所需信息的輔助空間；
• （3）若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需分析除輸入和程序之外的額外空間；
• （4）算法原地工作是指算法所需的輔助空間為常量，即O(1)；

第二章、線性表

1、知識框架
2、線性表的定義

• 線性表是具有相同數(shù)據(jù)類型的 n（n ≥ 0）個數(shù)據(jù)元素的有限序列，其中 n 為表長，當(dāng)n = 0時線性表是一個空表。
• 若用L命名線性表，則其一般表示為：
  • L = (a₁, a₂, …, a_i, a_i+1, …, a_n)；
  • a₁是唯一的“第一個”數(shù)據(jù)元素，又稱表頭元素；
  • a_n是唯一的“最后一個”數(shù)據(jù)元素，又稱表尾元素；
  • 除第一個元素外，每個元素有且僅有一個直接前驅(qū)；
  • 除最后一個元素外，每個元素有且僅有一個直接后繼；

3、線性表的特點

• 表中元素的個數(shù)有限；
• 表中元素具有邏輯上的順序性，表中元素有其先后次序；
• 表中元素都是數(shù)據(jù)元素，每個元素都是單個元素；
• 表中元素的數(shù)據(jù)類型相同，這意味著每個元素占有相同大小的存儲空間；
• 表中元素具有抽象性，即僅討論元素間的邏輯關(guān)系，而不考慮元素究竟表示什么內(nèi)容；
• 線性表是一種邏輯結(jié)構(gòu)，表示元素之間一對一的相鄰關(guān)系。順序表和鏈表是線性表這一邏輯結(jié)構(gòu)在內(nèi)存中的不同組織形式（存儲結(jié)構(gòu)）；

4、線性表的基本操作

• InitList(&L);初始化表，構(gòu)造一個空的線性表；
• Length(L);求表長，返回線性表 L 的長度，即 L 中數(shù)據(jù)元素的個數(shù)；
• LocateElem(L, e);按值查找操作，在表 L 中查找具有給定關(guān)鍵字值的元素；
• GetElem(L, i);按位查找操作，獲取表 L 中第 i 個位置的元素的值；
• ListInsert(&L, i, e);插入操作，在表 L 中的第 i 個位置上插入指定元素 e；
• ListDelete(&L, i, &e);刪除操作，刪除表 L 中第 i 個位置的元素，并用 e 返回刪除元素的值；
• PrintList(L);輸出操作，按前后順序輸出線性表L的所有元素值；
• Empty(L);判空操作，若 L 為空表，則返回true，否則返回false；
• DestroyList(&L);銷毀操作，銷毀線性表，并釋放線性表 L 所占用的內(nèi)存空間；
• 注意：基本操作的實現(xiàn)取決于采用哪種存儲結(jié)構(gòu)，存儲結(jié)構(gòu)不同，算法的實現(xiàn)也不同。

5、線性表的順序表示—順序表

• （1）用一組地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素，從而使得邏輯上相鄰的兩個元素在物理位置上也相鄰；
• （2）特點：表中元素的邏輯順序與其物理順序相同；
• （3）隨機存?。S機訪問），即根據(jù)首地址和元素序號可在O(1)時間內(nèi)找到指定的元素；
• （4）假定線性表的元素類型為ElemType，則線性表的順序存儲類型描述為：

//數(shù)組空間靜態(tài)分配，可能會產(chǎn)生溢出
#define MaxSize 50//定義線性表的最大長度
typedef struct {
   
	ElemType data[MaxSize];//順序表的元素數(shù)組
	int length;//順序表的當(dāng)前長度
} SqList;//順序表的類型定義

//數(shù)組空間動態(tài)申請
#define InitSize 100//表長度的初始定義
typedef struct {
   
	ElemType *data;//指示動態(tài)分配數(shù)組的指針
	int MaxSize, length;//數(shù)組的最大容量和當(dāng)前個數(shù)
} SeqList;//動態(tài)分配數(shù)組的順序表的類型定義

動態(tài)申請得到的內(nèi)存是連續(xù)的，同樣屬于順序存儲結(jié)構(gòu)。C的初始動態(tài)分配語句為：

SeqList L;
L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);

C++的初始動態(tài)分配語句為：

L.data = new ElemType[InitSize];

• （5）順序表的存儲密度高，每個結(jié)點只存儲數(shù)據(jù)元素；
• （6）順序表邏輯上相鄰的元素物理上也相鄰，所以插入和刪除操作需要移動大量元素；

6、順序表上基本操作的實現(xiàn)

（1）插入操作

• 在順序表L的第 i（1<= i <= L.length + 1）個位置插入新元素 e 。若 i 的輸入不合法，則返回false，表示插入失?。环駝t，將第 i 個元素及其后的所有元素依次往后移動一個位置，騰出一個空位置插入新元素 e，順序表長度增加1，插入成功，返回true。

bool ListInsert(SqList &L, int i, ElemType e) {
   
	if( i < 1 || i > L.length + 1 )//判斷i的范圍是否有效
		return false;
	if( L.length >= MaxSize )//當(dāng)前存儲空間已滿，不能插入
		return false;
	for( int j = L.length; j >= i; j -- )//將第i個元素及之后的元素后移
		L.data[j] = L.data[j - 1];
	L.data[i - 1] = e;//在位置i處放e
	L.length ++;//線性表長度加1
	return true;
}

• 時間復(fù)雜度分析（假設(shè)順序表長度為n）：
  • 最好情況：在表尾插入（即 i = n + 1），元素后移語句將不執(zhí)行，時間復(fù)雜度為O(1)；
  • 最壞情況：在表頭插入（即 i = 1），元素后移語句將執(zhí)行 n 次，時間復(fù)雜度為O(n)；
  • 平均情況：在第 i 個位置插入元素的概率p_i = 1/(n+1)，元素后移語句要執(zhí)行n-i+1次，所以移動結(jié)點的平均次數(shù)為 p_i * (n-i+1)（ i 從1到n+1求和）= n/2，所以平均時間復(fù)雜度為O(n)。
    

（2）刪除操作

• 刪除順序表L中第 i（1 <= i <= L.length）個位置的元素，用引用變量e返回。若 i 的輸入不合法，則返回false；否則將被刪除元素賦給引用變量e，并將第 i + 1個元素及其后的所有元素依次往前移動一個位置，返回true。

bool ListDelete(SqList &L, int i, ElemType &e) {
   
	if( i < 1 || i > L.length )//判斷i的范圍是否有效
		return false;
	e = L.data[i-1];//將被刪除的元素賦值給e
	for( int j = i - 1; j < L.length - 1; j ++)//將第i個位置后的元素前移
		L.data[j] = L.data[j + 1];
	L.length --;//線性表長度減1
	return ture;
}

• 時間復(fù)雜度分析（假設(shè)順序表長度為n）：
  • 最好情況：刪除表尾元素（即 i = n），無需移動元素，時間復(fù)雜度為O(1)；
  • 最壞情況：刪除表頭元素（即 i = 1），需移動除表頭元素外的所有元素，時間復(fù)雜度為O(n)；
  • 平均情況：刪除第 i 個元素的概率p_i = 1/n，需移動n-i個元素，所以移動元素的平均個數(shù)為p_i * (n - i)( i從1到n求和）= (n - 1)/2，所以平均時間復(fù)雜度為O(n)。
    

可見，順序表中插入和刪除操作的時間主要耗費在移動元素上，而移動元素的個數(shù)取決于插入和刪除元素的位置。

(3)按值查找（順序查找）文章來源地址http://www.zghlxwxcb.cn/news/detail-440203.html

• 在順序表L中查找第一個元素值等于 e 的元素，并返回其位序。

int LocateElem(SqList L, ElemType e) {
   
	for( int i = 0; i < L.length; i ++ ) {
   
		if( L.data[i] == e )
			

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)筆記NO.1（緒論、線性表、棧隊列和矩陣的壓縮存儲）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！