1、數據結構概述東北師大附中谷方明為什么學數據結構算法 + 數據結構 = 程序N.Wirth基本概念數據：數據(data)是對客觀事物的符號表示。在計算機領域，數據是指所有能輸入到計算機中，并能被計算機存儲、處理和輸出的一切信息，如文字、圖形、圖像、聲音、視頻等。數據類型：數據類型是指數據的不同種類，如整形、實型、字符型、字符串等數據的物理結構例：學生成績表數據結構數據結構：數據及數據之間的相互關系，即數據的組織形式。一般包括： 1、數據的邏輯結構 數據間抽象化的邏輯關系。 通常所說的數據結構是指數據的邏輯結構。 2、數據的物理結構（存儲結構） 數據及其關系在計算機存儲器內的表示 3、數據的運算

2、對數據施加的操作。 數據的邏輯結構DS=（D，R）D：數據(元素)的集合 R: 關系的集合數據之間的關系，取決于對數據的操作例1D= s1，s2，s3，s4，s5R=空集特點：數據之間，除了同一集合關系之外，無其它關系。集合結構例2D=s1，s2，s3，s4，s5R=(s1,s2)，(s2,s3)，(s3,s4)，(s4,s5)特點：數據之間的關系呈直線狀。 除了第一個和最后一個元素，每個元素都有唯一前驅和唯一后繼。數據之間的關系是1：1的聯系線性結構例3D=s1，s2，s3，s4，s5R=(s1,s2)，(s1,s3)，(s2,s4)，(s3,s5)特點：數據之間的關系呈現層次狀。除了第一個

3、數據沒有前驅數據，其它數據元素都有唯一前驅；所有數據可以有0個或多個后繼。數據元素之間的關系是1：N的關系。層次結構(樹)例4D=s1，s2，s3，s4，s5R=(s1,s2)，(s1,s3)，(s2,s4)，(s3,s5)，(s1,s4)，(s1,s5)特點：數據之間的關系呈現網狀。每個數據元素可以有0個或多個前驅和0個或多個后繼。數據元素之間的關系是M：N的關系。網狀結構(圖)小結集合結構線性結構層次結構網狀結構非線性結構：層次結構和網狀結構數據之間的關系是由對數據的操作決定的順序存儲把邏輯上相鄰的數據元素存儲在相鄰的存儲單元中。在C+中，一般用數組描述。優點：便于查找，缺點：插入和刪除時

4、會引起數據的大量移動鏈式存儲邏輯上相鄰的數據元素在存儲空間內不連續，相鄰關系通過存放地址維持和體現。在C+中，一般用指針來描述。優點：便于插入和刪除；缺點：查找費時索引首先把一個線性表（主表）按照一定的條件劃分成若干個子表，為每個子表分別建立一個索引項，由這些索引項構成一個索引表。優點：查找方便；缺點：插入、刪除、修改時需要維護索引表。 散列以線性表中的每個元素的關鍵字k為自變量，通過一種函數h(k)計算出函數值，把這個函數值解釋為一塊連續存儲空間上（數組）的地址值（下標）。這個函數成為hash函數，也叫散列函數、哈希函數。優點：查找快； 缺點：插入、刪除、修改時需要解決沖突。 小結數據的物理

5、結構順序存儲鏈式存儲索引散列線性表線性表是最簡單、最常用的一種數據結構。 (1,2,3,4,5) (a,b,c,d,，z)姓名學號總分孫雪暉201302xx1000尚柯宇201303xx1000線性表中元素的個數n稱為線性表的長度。當n=0時，稱線性表為空表。在非空線性表(a1,a2,，an)中，a1是第一個元素，稱為表頭元素；an是最后一個元素，稱為表尾元素。第i個數據ai在ai-1后，在ai+1前(1in)，這種位置上的有序性就是一種線性關系。除a1外，每個數據元素只有一個前驅；除an外每個數據元素只有一個后繼。A1A2A3A4AN-1AN線性表的基本操作初始化：設置一個空的線性表求長度：

6、求線性表中元素的個數獲取元素：取出線性表中的某個數據元素查找：搜索線性表中滿足某一條件的數據元素插入：插入給定元素到線性表中刪除：刪除線性表中的元素判空：判斷線性表是否空判滿：判斷線性表是否滿線性表的順序結構實現struct Stduent string name; int sco;Student lisMAXL;int len;練習1 電話號碼查詢系統 設有一個電話號碼薄，它記錄了N個人的名字和其相應的電話號碼，假定按如下形式安排： (a1，b1)(a2，b2)(an，bn) 其中ai，bi(i=1，2n) 分別表示某人的名字和對應的電話號碼。要求設計一個程序，完成以下功能： 1）輸入N個人

7、的名字及電話號碼 2）查找某個人的電話號碼 3）加入一個人及其電話號碼 4）刪除某個人及其電話號碼 5）按名字對號碼簿排序 6）輸出號碼上所有人的名字和電話號碼練習2插入線性表元素 a和b分別表示兩個線性表，它們的數據元素類型相同，現要講b中存在而a中不存在的元素插入到線性表a中。設線性表a的長度與線性表b的長度之和不超過線性表a允許的最大長度。練習3合并線性表 已知線性表a和線性表b中的數據元素按遞增的順序排列，現要求將a和b合并成一個新的線性表c，c中的數據元素仍按遞增排列。練習4(Joseph問題)N只猴子選大王，選舉辦法如下：所有的猴子以順時針按1到N編號圍坐一圈，從編號為1的猴子開始按順時針方向以1，2，M報數，M1，凡報M的人退出圈外，如此循環報數，直到圈內只剩下一只猴子就是大王，編程求出大王的