數據就是指能夠被計算機識別、存儲和加工處理的信息的載體。
數據元素是數據的基本單位，有時一個數據元素可以由若干個數據項組成。數據項是具有獨立含義的最小標識單位。如整數這個集合中，10這個數就可稱是一個數據元素.又比如在一個數據庫(關系式數據庫)中，一個記錄可稱為一個數據元素，而這個元素中的某一字段就是一個數據項。
數據結構的定義雖然沒有標準，但是它包括以下三方面內容：邏輯結構、存儲結構、和對數據的操作。這一段比較重要，我用自己的語言來說明一下，大家看看是不是這樣。
比如一個表(數據庫)，我們就稱它為一個數據結構，它由很多記錄(數據元素)組成，每個元素又包括很多字段(數據項)組成。那么這張表的邏輯結構是怎么樣的呢? 我們分析數據結構都是從結點(其實也就是元素、記錄、頂點，雖然在各種情況下所用名字不同，但說的是同一個東東)之間的關系來分析的，對于這個表中的任一個記錄(結點)，它只有一個直接前趨，只有一個直接后繼(前趨后繼就是前相鄰后相鄰的意思)，整個表只有一個開始結點和一個終端結點，那我們知道了這些關系就能明白這個表的邏輯結構了。
而存儲結構則是指用計算機語言如何表示結點之間的這種關系。如上面的表，在計算機語言中描述為連續存放在一片內存單元中，還是隨機的存放在內存中再用指針把它們鏈接在一起，這兩種表示法就成為兩種不同的存儲結構。(注意，在本課程里，我們只在高級語言的層次上討論存儲結構。)
第三個概念就是對數據的運算，比如一張表格，我們需要進行查找，增加，修改，刪除記錄等工作，而怎么樣才能進行這樣的操作呢? 這也就是數據的運算，它不僅僅是加減乘除這些算術運算了，在數據結構中，這些運算常常涉及算法問題。
弄清了以上三個問題，就可以弄清數據結構這個概念。
(答案及點評) 3.4 設長度為n的鏈隊用單循環鏈表表示，若設頭指針，則入隊出隊操作的時間為何? 若只設尾指針呢?
3.4答：當只設頭指針時，出隊的時間為1，而入隊的時間需要n，因為每次入隊均需從頭指針開始查找，找到最后一個元素時方可進行入隊操作。若只設尾指針，則出入隊時間均為1。因為是循環鏈表，尾指針所指的下一個元素就是頭指針所指元素，所以出隊時不需要遍歷整個隊列。
第四章：串(包括習題與答案及要點)
轉摘www.Ezikao.com
--------------------------------------------------------------------------------
本章介紹了串的邏輯結構，存儲結構及串上的基本運算，由于在高級語言中已經提供了較全善的串處理功能，因此本章的重點是掌握在串上實現的模式匹配算法。同時這也是本章的難點。但是從全書來講，這屬于較簡單的一章內容。
--------------------------------------------------------------------------------
1.串及其運算(領會)(這些內容比較容易理解，不用死記)
串就是字符串，是一種特殊的線性表，它的每個結點僅由一個字符組成。
空串：是指長度為零的串，也就是串中不包含任何字符(結點)。
空白串：指串中包含一個或多個空格字符的串。不同與空串，它的結點就是一個空格字符。
在一個串中任意個連續字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。子串在主串中的序號就是指子串在主串中首次出現的位置。如A="I love you" B="love",則B在A中的序號為3，注意空格也是字符。
空串是任意串的子串，任意串是他自身的子串。
串分為兩種：串常量和串變量。串常量在程序中不能改變，串變量則可以。
關于串的基本運算，基本上在C語言中已經學過，主要有
求串長strlen(char *s)、
串復制strcpy(char *to,char *from)、
串聯接strcat(char *to,char *from)、
串比較charcmp(char *s1,char *s2)
和字符定位strchr(char *s, char c)等
這些基本運算通過練習來掌握。
--------------------------------------------------------------------------------
2.串的存儲結構(簡單應用)
串是特殊的線性表(結點是字符)，所以串的存儲結構與線性表的存儲結構類似。
串的順序存儲結構簡稱為順序串，順序串又可按存儲分配的不同分為靜態存儲分配的順序串和動態存儲分配的順序串。
靜態的意思可簡單地理解為一個確定的存儲空間，它的長度是不可變的。如直接使用定長的字符數組來定義一個串。它的優點是涉及串長的操作速度快，因為它的最大長度是不變的。
動態存儲分配就是在定義串時不分配存儲空間，直到需要使用時按所需串的長度分配存儲單元給它，并且在運行中還可以根據需要變化串的長度，這就是動態分配。不過這樣的串仍是順序存儲的，也就是說指針指向串的首地址，后面的結點是連續存儲的。
串的鏈式存儲就是用單鏈表的方式存儲串值，串的這種鏈式存儲結構簡稱為鏈串。鏈串與單鏈表的差異只是它的結點數據域為單個字符。這種存儲結構方便于串的插入和刪除操作，但是空間利用率不高，因為存放每一個字符要"搭配"一個指向下一字符的地址,而地址所占空間是比較大的。為了解決這種"存儲密度"過低的狀況，可以讓一個結點存儲多個字符，事實上這是順序串和鏈串的綜合(折衷)。
--------------------------------------------------------------------------------
本章的重點和難點就是串運算的實現，特別是順序串上子串定位的運算。
子串定位運算又稱串的"模式匹配"或"串匹配"，就是在主串中查找出子串出現的位置，這在應用中非常廣泛，比如文本編輯中的"查找和替換"用到的就是子串定位運算的算法。
在串匹配中，將主串稱為目標(串)，子串稱為模式(串)，我們這樣想象，子串就如同一個模板(樣本)，用它在目標上對比，從頭往后比較，凡是遇到一模一樣的那么一段，就算找到一個位置了(我們就說，從這個位置開始的匹配成功)。用很專業的很酷的話說就是"模式在目標中出現"(我想起了警匪片里的對話),如果這個模板對應的目標串中有不一樣的字符出現，那么這個位置就匹配失敗。
當我們用這個模子依次從目標的頭部往后移,移動到的位置就叫位移，如果每次向右移動1格，那么每次的位移就加上1。
每次移動后要看看模板里的字符和目標中相應的字符是否相等，如果都相同，這次位移就叫有效位移(其實就是從這個位置開始的匹配成功)
另外有一個合法位移和不合法位移的概念，就是說，移動一個位置后，如果模板的最后一個字符還沒有超出目標串中最后一個字符時，這個位移就是合法位移，如果超出了，那么就沒有比較的意義了，這時就是不合法位移。
這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標串T中首次出現的有效位移或者是全部有效位移。
具體的串匹配算法也不是很難理解，就是用兩個循環，外循環用于進行模式的位移，內循環進行模板內每個字符的比較(判斷是否有效位移)。關于串匹配的時間復雜度，在最壞的情況下就是目標串和模式串分別是"a^n-1b"和"a^m-1b"的形式，就是說，每一次合法位移后，在內循環中都要比較m個字符才知道是不是有效位移(前面的字符都是一樣的)。所以最壞的情況下時間復雜度是O((n-m+1)m),假如m與n同階的話則它是O(n^2)。
