一、基礎概念

1、數據結構：相互之間存在一種或多種特定關系的數據元素的集合。（特定關系有邏輯關系與線性關系）

（1）邏輯結構

????????集合，所有數據在同一個集合中，關系平等（數組）

????????線性，數據和數據之間是一對一的關系（數組）

????????樹，?一對多

????????圖，多對多

注：數組屬于線性表的一種形式；

（2）物理結構(在內存當中的存儲關系)

????????順序存儲，數據存放在連續的存儲單位中，邏輯關系和物理關系一致；

????????鏈式存儲（鏈表），數據存放的存儲單位是隨機或任意的，可以連續也可以不連續??（一般認為不連續）

2、數據、?數劇項、數據元素、數據對象

（1）數據：可輸入輸出，具備一些操作（相當于C語言中的變量）

（2）數據項：給變量賦予一定的含義

（3）數據元素：多個基礎的數據項拼在一起（C語言中用struct自定義表示）

（4）數據對象：數據元素的集合

eg：

struct?Per //數據元素
{
char?name;//數據項
int?age;
char?phone;
}
struct?Per?list[100];?//數據對象

3、數據的類型，ADT????abstruct?datatype

（1）ADT：是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。

????????原子類型，int，char，float

????????結構類型，sturct，?union，

（2）抽象數據類型，?數學模型?+?操作。

4、數據結構角度解釋程序：（程序?=??數據（被加工對象） +?算法（函數））

（1）算法的定義：是解決特定問題求解步驟的描述，計算機中表現為指令的有限序

列，每條指令表示一個或多個操作。

（2）算法的特征：
????????輸入，輸出特性：輸入時可選的，輸出時必須的（調用函數后要發生一些變化）；

????????有窮性：執行的步驟會自動結束，不能是死循環，并且每一步是在可以接受的時間

內完成；? ??

?????????確定性：同一個輸入，會得到唯一的輸出；

?????????可行性：每一個步驟都是可以實現的（用編程語言實現）。

（3）算法的設計：

?????????正確性：語法正確；

???????????????????????合法的輸入能得到合理的結果；

? ? ? ? ? ? ? ? ? ? ? ?對非法的輸入，給出滿足要求的規格說明；

? ? ? ? ? ? ? ? ? ? ? ?對精心選擇，甚至刁難的測試都能正常運行，結果正確（加必要的判? ? ? ? ???????????????????????斷）；

????????可讀性：便于交流，閱讀，理解（適當注釋，編寫項目文檔）

????????健壯性：輸入非法數據，能進行相應的處理，而不是產生異常

????????高效性：存儲低，效率高 （時間與空間兩個方面）

5、算法時間復雜度

（1）是執行這個算法所花時間的度量，eg：O(n)???O(1)

（2）推時間復雜度：

????????用常數1?取代運行時間中的所有加法常數；

????????在修改后的運行函數中，只保留最高階項；

????????如果最高階存在且不是1，則取除這個項相乘的常數。

（3）時間復雜度排序：

????????O(1)<O(logn)<O(N)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

二、線性表

1、定義：有零個或多個數據元素的有限序列；

2、元素之間是有順序的，如果存在多個元素，第一個元素無前驅，最有一個沒有后

繼，其他的元素只有一個前驅和一個后繼；

3、當線性表元素的個數n（n>=0）定義為線性表的長度，當n=0時，為空表。在非空的

表中每個元素都有一個確定的位置，如果a1是第一個元素，那么an就是第n個元素。

4、線性表中的順序表：

表頭結構（數組當前狀態，后期方便應用管理）

typedef struct list {
? ? DATATYPE *head;//指針
? ? int tlen;//總長度
? ? int clen;//當前長度（數組元素個數）（未使用空間時為0）
}SeqList//順序表;

5、sudo：以管理員身份運行命令；

6、memcpy函數：需要包含頭文件#incude<string.h>

? ? ? ? 更通用的一個函數（整個內存空間發到需要的地方）

????????函數形式：void *memcpy(void *restrict_dest, void *restrict_src, unsigned n);