1、學(xué)生信息處理學(xué)生的信息包括：學(xué)號、姓名、性別、年齡、專業(yè)等數(shù)據(jù)項。功能要求 插入：將某學(xué)生的基本信息插入到表中； 刪除：將滿足條件的基本信息刪除； 修改：對基本信息的數(shù)據(jù)項進行修改； 查詢：查找滿足條件的學(xué)生； 輸出：將信息表中的全部（或滿足條件）基本信息輸出。2022/10/111學(xué)生信息處理學(xué)生的信息包括：2022/10/101思考：數(shù)據(jù)元素之間的關(guān)系是什么？數(shù)據(jù)如何表示？數(shù)據(jù)如何存儲？數(shù)據(jù)如何處理？2022/10/112思考：數(shù)據(jù)元素之間的關(guān)系是什么？數(shù)據(jù)如何表示？數(shù)據(jù)如何存第2章 線性表本章的基本內(nèi)容是：線性表的基本概念線性表的順序存儲及實現(xiàn)線性表的鏈?zhǔn)酱鎯皩崿F(xiàn)順序表和單鏈表的比較2

2、022/10/113第2章 線性表本章的基本內(nèi)容是：2022/10/1032.1 線性表的基本概念線性表的邏輯結(jié)構(gòu)線性表是具有相同數(shù)據(jù)類型的n（n0）個數(shù)據(jù)元素組成的有限序列，通常記為L=(a1，a2，ai1，ai，ai+1，an)a1a3a4ana22022/10/1142.1 線性表的基本概念線性表的邏輯結(jié)構(gòu)線性表是具有相同數(shù)2.1 線性表的基本概念非空線性表的特性 (P12)有且僅有一個表頭結(jié)點a1，它沒有前驅(qū)，而僅有一個后繼a2；有且僅有一個表尾結(jié)點an，它沒有后繼，而僅有一個前驅(qū)an1；其余的結(jié)點ai（2in1）都有且僅有一個前驅(qū)a i1和一個后繼a i+1。線性表的存儲結(jié)構(gòu) (P1

3、2)順序存儲鏈?zhǔn)酱鎯?022/10/1152.1 線性表的基本概念非空線性表的特性 (P12)線性表2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn)存儲要點用一段地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素 0 i-2 i-1 n-1 MaxSize-1 a1 ai-1 ai an 空閑 2022/10/1162.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn)存儲要點用一段地址連續(xù)的如何求得任意元素的存儲地址？2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn) a1 ai-1 ai an 空閑 dLoc(ai) 0 i-2 i-1 n-1 MaxSize-1 Loc(a1)Loc(ai)=Loc(a1) + (i -1)d隨機存?。涸贠(

4、1)時間內(nèi)存取數(shù)據(jù)元素2022/10/117如何求得任意元素的存儲地址？2.2 線性表的順序存儲結(jié)構(gòu)及2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn) 0 i-2 i-1 n-1 MaxSize-1 a1 ai-1 ai an 空閑 如何描述順序表？順序表的內(nèi)存分配：一維數(shù)組data順序表的容量（最大長度）：MaxSize順序表的當(dāng)前長度：lengthlengthdata2022/10/1182.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn) 0 2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的類模板 P13template class SeqList T dataMaxSize; /用于存放數(shù)據(jù)元素的數(shù)組 int length

5、; /順序表中元素的個數(shù)public: SeqList( ); /無參構(gòu)造函數(shù) SeqList(T a, int n); /有參構(gòu)造函數(shù) int ListLength(); /求線性表的長度 T Get(int pos); /按位查找 int Locate(T item); /按值查找 void PrintSeqList(); /遍歷順序表 void Insert(int i, T item); /在順序表中第i個位置插入值為item的元素 T Delete(int i); /刪除順序表的第i個元素;2022/10/1192.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的類模板 2.2 線性表的順序存

6、儲結(jié)構(gòu)及實現(xiàn)順序表的操作算法 P16-201、初始化操作 無參構(gòu)造函數(shù)：創(chuàng)建空表 有參構(gòu)造函數(shù)2、求順序表長度3、按位查找4、按值查找5、遍歷順序表6、插入7、刪除2022/10/11102.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的操作算法 2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的優(yōu)點： 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間； 隨機存?。嚎梢钥焖俚卮嫒”碇腥我晃恢玫脑?。 順序表的缺點： 插入和刪除操作需要移動大量元素； 表的容量難以確定，表的容量難以擴充； 造成存儲空間的碎片。 2022/10/11112.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的優(yōu)點：2022/2.3 線性表的

7、鏈?zhǔn)酱鎯Y(jié)構(gòu)及實現(xiàn)存儲思想：用一組任意的存儲單元存放線性表的元素。靜態(tài)存儲分配 順序表事先確定容量 鏈?zhǔn)絼討B(tài)存儲分配 運行時分配空間 連續(xù)不連續(xù)零散分布存儲特點： 邏輯次序和物理次序不一定相同；元素之間的邏輯關(guān)系用指針表示。2022/10/11122.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實現(xiàn)存儲思想：用一組任意的存2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實現(xiàn)2.3.1單鏈表 P14 data next單鏈表的結(jié)點結(jié)構(gòu)：數(shù)據(jù)域指針域template struct Node T data; Node *next; 2022/10/11132.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實現(xiàn)2.3.1單鏈表 Pheada1a2an非空表

8、head=NULL空表 不帶頭結(jié)點的單鏈表2.3.1單鏈表頭指針：指向第一個結(jié)點的地址。2022/10/1114heada1a2an非空表head=NULL空表 不帶頭結(jié)頭結(jié)點：在單鏈表的第以一個元素結(jié)點之前附設(shè)一個類型相同的結(jié)點，以便空表和非空表處理統(tǒng)一。 非空表heada1a2an空表head2.3.1單鏈表帶頭結(jié)點的單鏈表2022/10/1115頭結(jié)點：在單鏈表的第以一個元素結(jié)點之前附設(shè)一個類型相同的結(jié)點2.3.1單鏈表template class LinkList public: LinkList( )； LinkList(T a , int n); LinkList( ); int

9、Length( ); T Get(int pos); int Locate(T x); void Insert(int i, T item); T Delete(int i); void PrintList( ); private: Node *head; ;單鏈表的類模板2022/10/11162.3.1單鏈表template 單鏈表的2.3.1單鏈表單鏈表的基本操作算法 P21-261、初始化操作 無參構(gòu)造函數(shù) 有參構(gòu)造函數(shù)2、求單鏈表長度3、按位查找4、按值查找5、遍歷單鏈表表6、插入7、刪除2022/10/11172.3.1單鏈表單鏈表的基本操作算法 P21-2612.3.1單鏈表單鏈

10、表的其他操作 P26-281、單鏈表的逆置2、合并有序單鏈表2022/10/11182.3.1單鏈表單鏈表的其他操作 P26-281、單循環(huán)鏈表：將單鏈表的首尾相接，將終端結(jié)點的指針域由空指針改為指向頭結(jié)點，構(gòu)成單循環(huán)鏈表，簡稱循環(huán)鏈表。2.3.2 線性表的其他鏈?zhǔn)酱鎯Y(jié)構(gòu)雙向鏈表：在單鏈表的每個結(jié)點中再設(shè)置一個指向其前驅(qū)結(jié)點的指針域。2022/10/1119循環(huán)鏈表：將單鏈表的首尾相接，將終端結(jié)點的指針域由空指針改為1、求集合的并集 順序表的應(yīng)用2.4 線性表的應(yīng)用2、一元多項式相加 單鏈表的應(yīng)用2022/10/11201、求集合的并集2.4 線性表的應(yīng)用2、一元多項式相加2022.5 順序

11、表和單鏈表的比較存儲分配方式比較順序表采用順序存儲結(jié)構(gòu)，即用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過存儲位置來實現(xiàn)。單鏈表采用鏈接存儲結(jié)構(gòu)，即用一組任意的存儲單元存放線性表的元素。用指針來反映數(shù)據(jù)元素之間的邏輯關(guān)系。2022/10/11212.5 順序表和單鏈表的比較存儲分配方式比較2022/10/2.5 順序表和單鏈表的比較時間性能比較 時間性能是指實現(xiàn)基于某種存儲結(jié)構(gòu)的基本操作（即算法）的時間復(fù)雜度。 按位查找：順序表的時間為(1)，是隨機存??；單鏈表的時間為(n)，是順序存取。插入和刪除：順序表需移動表長一半的元素，時間為(n)；單鏈表不需要移動元素，在

12、給出某個合適位置的指針后，插入和刪除操作所需的時間僅為(1)。2022/10/11222.5 順序表和單鏈表的比較時間性能比較 2022/10/12.5 順序表和單鏈表的比較空間性能比較 空間性能是指某種存儲結(jié)構(gòu)所占用的存儲空間的大小。 定義結(jié)點的存儲密度： 數(shù)據(jù)域占用的存儲量整個結(jié)點占用的存儲量存儲密度2022/10/11232.5 順序表和單鏈表的比較空間性能比較 數(shù)據(jù)域占用的存儲2.5 順序表和單鏈表的比較空間性能比較 結(jié)點的存儲密度：順序表中每個結(jié)點的存儲密度為1（只存儲數(shù)據(jù)元素），沒有浪費空間；單鏈表的每個結(jié)點的存儲密度1（包括數(shù)據(jù)域和指針域），有指針的結(jié)構(gòu)性開銷。整體結(jié)構(gòu)：順序表需要預(yù)分配存儲空間，如果預(yù)分配得過大，造成浪費，若估計得過小，又將發(fā)生上溢；單鏈表不需要預(yù)分配空間，只要有內(nèi)存空間可以分配，單鏈表中的元素個數(shù)就沒有限制。2022/10/11242.5 順序表和單鏈表的比較空間性能比較 2022/10/12.5 順序表和單鏈表的比較若線性表需頻繁查找卻很少進行插入和刪除操作，或其操作和元素在表中的位置密切相關(guān)時，宜采用順序表作為存儲結(jié)構(gòu)；若線性表需頻繁插入和刪除