資源描述：
《第2章 線性表及線性表的順序存儲 ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第2章線性表及線性表的順序存儲問題思考：1、什么是線性表2、線性表結(jié)構(gòu)特點3、如何利用線性表結(jié)構(gòu)的知識解決實際問題，確定線性表邏輯結(jié)構(gòu)的應(yīng)用題目。上機：線性表結(jié)構(gòu)案例理解，完成課程設(shè)計報告?？己朔绞剑赫n程報告作業(yè)題目：依據(jù)選定的線性表結(jié)構(gòu)實用案例題目，設(shè)計完成題目。例如：課程任務(wù)實例“學(xué)生名冊信息管理“。主要知識點●線性表的定義、線性表中數(shù)據(jù)元素之間的邏輯關(guān)系，以及計算機中順序存儲結(jié)構(gòu)?！耥樞虼鎯Y(jié)構(gòu)物理結(jié)構(gòu)的C語言描述方法、特點，采用程序設(shè)計語言實現(xiàn)線性表結(jié)構(gòu)基本操作，在實際應(yīng)用中選用適合的線性表物理結(jié)構(gòu)?！衲軌驈臅r間和空間復(fù)雜
2、度的角度比較線性表不同存儲結(jié)構(gòu)的特點以及使用場合。教學(xué)重點與難點重點：熟練掌握順序表的各種基本算法，以及相關(guān)的時間性能分析。難點：根據(jù)本章基本知識設(shè)計設(shè)計有效算法解決線性表相關(guān)實際問題。2.1線性表的定義2.1.1線性表實例案例：學(xué)生名冊信息管理，數(shù)據(jù)信息特征由姓名、學(xué)院、所在專業(yè)、學(xué)號表示。需求分析：1、需要準(zhǔn)備一張大小適當(dāng)?shù)挠涗浖垺?、登記在冊學(xué)生情況。3、取消登記（已調(diào)轉(zhuǎn)）。4、將記錄銷毀或存檔。表2.1學(xué)生名冊表姓名學(xué)院所在專業(yè)學(xué)號聶洪波應(yīng)院計算機20097554李豆豆應(yīng)院計算機20097550王曉雪應(yīng)院計算機200975
3、70肖瑤應(yīng)院計算機20097585…2.1線性表的定義數(shù)據(jù)關(guān)系分析：學(xué)生名冊數(shù)據(jù)表是（“聶洪波”，“李豆豆”，“王曉雪”，“肖瑤”)數(shù)據(jù)表三元組表示：名冊表=(D,R,F)數(shù)據(jù)集合：D={“聶洪波”，“李豆豆”，“王曉雪”，“肖瑤”};數(shù)據(jù)關(guān)系集合：R={<“聶洪波”，“李豆豆”>,<“李豆豆”，“王曉雪”>,<“王曉雪”，“肖瑤”>}數(shù)據(jù)關(guān)系表示：聶洪波->李豆豆->王曉雪->肖瑤2.1.1線性表實例2.1.1線性表實例任務(wù)操作分析F的集合：創(chuàng)建一個空的線性表（準(zhǔn)備一張白紙）插入一個新的元素（書寫一個新學(xué)生的信息）刪除一個元素（
4、劃掉一個調(diào)轉(zhuǎn)的學(xué)生的信息）查找指定的元素（在劃掉的信息之前，需要查找有關(guān)的信息是否存在）清空線性表（將紙張銷毀或存檔）2.1.2線性表的定義線性表（LinearList）的定義：線性表是具有相同類型的n個數(shù)據(jù)元素組成的有限序列，通常記為(a1，a2，…ai-1，ai，ai+1，…an)。其中，ai是表中元素，n是表的長度，當(dāng)n=0時線性表為空表。當(dāng)n≠0時，a1是第一個元素，也稱為表頭元素，an是最后一個元素，也稱為表尾元素。a1是a2的直接前驅(qū)元素，a2是a3的直接前驅(qū)元素，而a2是a1的直接后繼元素，a3是a2的直接后繼元素。
5、從集合論的觀點出發(fā)，線性表是由三個集合構(gòu)成的一個三元組。LinearList=(D,R,F)其中，D={ai
6、ai∈ElemSet,i=1,2,…,nn≥1}R={
7、ai,ai+1i∈D,i=1,2,…，n}F={操作1，操作2，操作3，…}Elemset為某一數(shù)據(jù)對象集；n為線性表的長度。n=0時，線性表為空表。2.1.2線性表的定義表2.1所示的學(xué)生名冊表是一個線性表，其數(shù)據(jù)元素是由姓名、學(xué)院、所在專業(yè)、學(xué)號四個數(shù)據(jù)項構(gòu)成，是復(fù)雜的結(jié)構(gòu)類型。由26個英文字母構(gòu)成的表（a,b,c,…,z）是一個線性表；由學(xué)生成
8、績構(gòu)成的表（99,100,88,76,89,56,96,98）是線性表。2.1.2線性表的定義表2.1學(xué)生名冊表姓名學(xué)院所在專業(yè)學(xué)號聶洪波應(yīng)院計算機20097554李豆豆應(yīng)院計算機20097550王曉雪應(yīng)院計算機20097570肖瑤應(yīng)院計算機20097585…2.1線性表的定義2.1.3線性表的基本操作及基本運算的描述線性表的基本操作包括：1、創(chuàng)建空的線性表；2、求線性表的長度；3、插入一個新的元素；4、刪除一個元素；5、求指定元素的位置6、查找指定的元素；7、清空線性表。(1)InitList(l)，初始化創(chuàng)建空的線性表線性表l
9、。(2)ListLength(l)，求線性表l的長度。(3)InsList(l,i,e)，在l中第i個元素(位置)之前插入數(shù)據(jù)元素e。(4)DelList(l,i)，刪除l中的第i個數(shù)據(jù)元素。(5)Locate(l,e)，求線性表l中元素e的位置。(6)GetData(l,i)，返回線性表l中第i個元素的值。(7)EmptyList(l)，判斷線性表l是否為空表，如果l為空表則返回1，否則返回0。線性表基本運算的描述注意：以上所提及的運算是邏輯結(jié)構(gòu)上定義的運算。只要給出這些運算的功能是"做什么"，至于"如何做"等實現(xiàn)細節(jié)，只有待確
10、定了存儲結(jié)構(gòu)之后才考慮。2.1.3線性表的基本操作及基本運算的描述2.1線性表的定義及運算問題思考:（1）線性表的基本運算與實用任務(wù)案例功能需求的關(guān)系。（2）如何采用C語言程序設(shè)計實現(xiàn)線性表的基本運算。任務(wù)2-1：結(jié)合案例選定的線性表結(jié)構(gòu)實用題目，
