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

邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，線性表是典型的線性結(jié)構(gòu)；集合、樹和圖是典型的非線性結(jié)構(gòu)。

存儲結(jié)構(gòu)主要有順序存儲、鏈式存儲、索引存儲、散列存儲。

二、算法是對特定問題求解步驟的描述。

算法的五個重要特征：

1、有窮性? ??2、確定性? ?3、可行性? ?4、輸入? ?5、輸出

通常設(shè)計一個”好“的算法應(yīng)考慮

1、正確性? ?2、可讀性? ? 3、健壯性? ?4、高效率與低存儲量需求

三、復(fù)雜度

1、時間復(fù)雜度

總是考慮在最壞情況下的時間復(fù)雜度

a）加法法則??

b）乘法法則

常見的漸近時間復(fù)雜度

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

2、空間復(fù)雜度

算法原地工作是指算法所需的輔助空間為常量，即O(1)。

三、線性表

1、線性表是具有相同數(shù)據(jù)類型的n個數(shù)據(jù)元素的有限序列。n=0時為空表

2、第一個數(shù)據(jù)元素為表頭元素，除了表頭元素外，每個元素都有一個直接前驅(qū)。最后一個數(shù)據(jù)元素為表尾元素，除表尾元素外，每一個元素都有直接后繼。

• 表中元素的個數(shù)有限。

• 表中元素具有邏輯上的順序性，表中元素有其先后次序。

• 表中元素都是數(shù)據(jù)元素，每個元素都是單個元素。

• 表中元素的數(shù)據(jù)類型相同，即每個元素占有相同大小的存儲空間。

• 表中元素具有抽象性，即僅討論元素間的邏輯關(guān)系，而不考慮元素究竟表示什么內(nèi)容。

3、線性表是一種邏輯結(jié)構(gòu)。順序表和鏈表是指存儲結(jié)構(gòu)。