【正文】 i+1 last . . . . . . . . . . . . . . . . . . 2021/12/1 16 template class Type int SeqlistType::Insert(Type amp。 if (ilast) return –1。amp。 x) const //查找 x 在表中位置，若查找成功，函數(shù)返回 x 的位置 //否則返回－ 1 { int i=0。 // last+1=0 , 表明表中無元素，空表 data=new Type[Maxsize]。順序表不僅僅包含存放其數(shù)據(jù)元素的數(shù)組，它還應(yīng)包括一些有用的數(shù)據(jù)成員，以及相應(yīng)的操作，它們是一個(gè)整體： 2021/12/1 12 順序表之整體概念： data 0 1 last Maxsize last 數(shù)組下標(biāo) 數(shù)組 變量 操作算法 Maxsize1 初始化操作 插入操作 刪除操作 查找操作 排序操作 . . . . . . . . . . . . . . . 2021/12/1 13 順序表的基本操作（算法） （ 1）順序表初始化操作算法 template class Type SeqlistType::Seqlist(int sz) //構(gòu)造函數(shù)，通過指定參數(shù) sz 定義數(shù)組的長度，并將 last 置為 –1 //即置空表 { if(sz0) { Maxsize=sz。 }// last 為表中最后元素的下標(biāo)， last=1 時(shí)表示空表 2021/12/1 11 上述順序表定義中的數(shù)據(jù)成員 Maxsize 是為判斷順序 表是否為滿而設(shè)， last 是為便于判斷順序表是否為空、求 表長、置空表而設(shè)： last=Maxsize –1表示順序表已滿，此時(shí)再進(jìn)行插入操作會(huì)導(dǎo)致上溢錯(cuò)誤； last=1 表示順序表為空表，此時(shí)再進(jìn)行刪除操作會(huì)導(dǎo)致下溢錯(cuò)誤； last+1 代表順序表的表長； 將 last 賦值為 –1 可實(shí)現(xiàn)置空表操作。 // 用數(shù)組存放線性表 ——順序存貯結(jié)構(gòu) int Maxsize。 Get( int i ) {return i 0 || i last ? NULL : data[i]。} int Isfull( ) {return last = =MaxSize – 1 。 x)。 x,int i)。 x) const。} int Length( ) const {return last+1。 順序表的類定義： 利用數(shù)組作為順序表的存儲結(jié)構(gòu)， 它被封裝在類的私有域中 2021/12/1 10 template class Type class SeqList { Public: SeqList(int MaxSize=defaultSize)。 1 線性表的邏輯結(jié)構(gòu) 定義 ： 由相同種類的數(shù)據(jù)元素組成的一個(gè)有窮序列稱為一個(gè)線性表。通?？捎脠D形表示，圓圈表示數(shù)據(jù)元素，箭頭表示關(guān)系： ? 物理結(jié)構(gòu)： 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的具體表示和實(shí)現(xiàn)， 又稱存儲結(jié)構(gòu) E i E i+1 數(shù)據(jù)元素 數(shù)據(jù)元素 關(guān)系 2021/12/1 5 數(shù)據(jù)結(jié)構(gòu)的分類 ? 按邏輯結(jié)構(gòu)分類： 純集合型結(jié)構(gòu) :數(shù)據(jù)元素之間除了 “ 同屬于一個(gè)集合 ” 這一 關(guān)系外，別無其他關(guān)系 線性結(jié)構(gòu)： 數(shù)據(jù)元素之間存在 “ 一個(gè)跟著一個(gè) ” 的序列關(guān)系 樹型結(jié)構(gòu)： 數(shù)據(jù)元素之間存在 “ 每個(gè)元素只能跟著一個(gè)元素 但可以有多個(gè)元素跟著它 ” 的層次關(guān)系 圖狀結(jié)構(gòu)： 任意兩個(gè)數(shù)據(jù)元素之間都可能存在關(guān)系 ? 按存儲結(jié)構(gòu)分類： 順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu) 索引存貯結(jié)構(gòu) 2021/12/1 6 基本操作： 任一數(shù)據(jù)結(jié)構(gòu)均有一組相應(yīng)的基本操作， 有時(shí)操作不同，用途迥異（如棧和隊(duì)列） 常用的基本操作有插入、 刪除、查找、 更新、排序等 算 法： 算法是為了解決給定的問題而規(guī)定的一個(gè) 有限長的操作步驟序列，則重于解決問題 的方法和步驟。數(shù)據(jù)元素可以由 若干數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)可以由若干 更小的款項(xiàng)（組合項(xiàng)、原子項(xiàng)）組成。2021/12/1 1 數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用 （用面向?qū)ο蠓椒ㄅc C＋＋描述） 2021/12/1 2 第一章 概述 研究對象： 信息的表示方法、數(shù)據(jù)的組織方法、操作算法設(shè)計(jì) 意義地位： 數(shù)據(jù)結(jié)構(gòu)＋算法＝程序 程序設(shè)計(jì)的基礎(chǔ) 系統(tǒng)軟件的核心 發(fā)展過程： 數(shù)值計(jì)算 非數(shù)值計(jì)算 建立數(shù)學(xué)模型 客體及其關(guān)系的表示 設(shè)計(jì)數(shù)值計(jì)算方法 數(shù)據(jù)的組織 操作算法的設(shè)計(jì) 非數(shù)值計(jì)算應(yīng)用的發(fā)展，促進(jìn)了數(shù)據(jù)結(jié)構(gòu) 的研究和發(fā)展以及其體系的完善。 2021/12/1 3 基本術(shù)語 ? 數(shù) 據(jù)： 描述客觀事物的且能由計(jì)算機(jī)處理的數(shù) 值、字符等符號 ? 數(shù)據(jù)元素： 數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常 作為一個(gè)整體進(jìn)行考慮和處理（記錄、 結(jié)點(diǎn)、表目、元素） ? 數(shù) 據(jù) 項(xiàng)： 數(shù)據(jù)元素的某一屬性。 數(shù)據(jù)項(xiàng)又稱域、字段 ? 關(guān) 鍵 碼： 能起唯一標(biāo)識（數(shù)據(jù)元素）作用的數(shù)據(jù)項(xiàng) ? 數(shù)據(jù)結(jié)構(gòu)： 一組同類的數(shù)據(jù)元素、其間的關(guān)系及其上的 一組操作所構(gòu)成的整體，稱為一個(gè)數(shù)據(jù)結(jié)構(gòu) 2021/12/1 4 數(shù)據(jù)結(jié)構(gòu)的描述方式 ? 邏輯結(jié)構(gòu)： 是對數(shù)據(jù)元素之間邏輯關(guān)系（拋開具體的關(guān)系含義以及存儲方式等）的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的幾個(gè)關(guān)系來表示。當(dāng)算法由計(jì)算機(jī)語言表示 時(shí)稱為程序（代碼） 算法設(shè)計(jì)目標(biāo)： 可維護(hù)性 可靠性（正確性、健壯行） 可讀性 高效率（時(shí)間、空間） 2021/12/1 7 第二章 線性表 2。 “ 一個(gè)跟著一個(gè) ” 符號表示法： L＝（ e1,e2,… en） 圖形表示法： e2 en e1 2021/12/1 8 其中： ei 表示線性表 L 的第 i 個(gè)數(shù)據(jù)元素 n 表示線性表 L 的表長（ n=0） n=0 時(shí)的線性表稱為空表 ei1 稱為 ei 的前驅(qū)， ei+1 稱為 ei 的后繼 線性表的基本操作： （ 1）初始化（置空表） ——可由構(gòu)造函數(shù)實(shí)現(xiàn) （ 2）求表長（ Length ） （ 3）查找或定位（ Find ） （ 4）插入（ Insert ） （ 5）刪除（ Remove ） （ 6）排序（ Sort ） （ 7）判空（ IsEmpty） 2021/12/1 9 線性表的順序存儲結(jié)構(gòu) 要實(shí)現(xiàn)在計(jì)算機(jī)內(nèi)表示一個(gè)數(shù)據(jù)結(jié)構(gòu)，要解決兩種信息的存貯問題： 數(shù)據(jù)元素本身的存貯 數(shù)據(jù)元素之間關(guān)系的存貯 定義： 利用內(nèi)存物理結(jié)構(gòu)上的鄰接特點(diǎn)，實(shí)現(xiàn)線性表 的 “ 一個(gè)跟著一個(gè) ” 這一序列關(guān)系的存貯方式， 稱為線性表的順序存貯結(jié)構(gòu)，其上的線性表稱 為順序表。 ~SeqList( ) {delete [ ] data。} int Find(Type amp。 int Insert(Type amp。 int Remove(Type amp。 int IsEmpty( ) {return last = = 1。} Type amp。} Private: Type * data。 // 數(shù)組大小，但順序表的長度為 last+1 int last。 由上可知：合理地設(shè)置數(shù)據(jù)成員可大大簡化算法的設(shè)計(jì)及提高算法的效率。 last=1。 } } 2021/12/1 14 （ 2）順序表查找操作 template class Type int SeqlistType::Find(Type amp。 while(i=last amp。 data[i]!=x) i++。 else return i。 x, int i) //將 x 插入表中 i 處，若成功返回 1 ，否則返回 0 { if (i0||ilast+1||last==Maxsize1) return 0。 for(int j=last。j) data[j]=data[j1]。 return 1。 x) //將 x 從表中刪除。 if (i=0) { last。j=last。 return 1。 } 2021/12/1 19 順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn) ? 優(yōu)點(diǎn)： （ 1）算法簡單、可讀性好、開發(fā)代價(jià)低 ? 缺點(diǎn)： （ 1）插入、刪除操作時(shí)需要移動(dòng)大量元素， 效率較低； （ 2）最大表長難以估計(jì)，太大了浪費(fèi)空間， 太小了容易溢出。 LA,Seqlist Type amp。 { int n=()。 for (int i=0。i++) { Type x=(i)。 // 在順序表 LA 中查找該元素 if (k==1) // 未找到 { ( x ,n)。 } } } 2021/12/1 21 template class Type void Intersection( Seqlist Type amp。 LB) // 求順序表 LA 與 LB 的共同元素，結(jié)果在 LA 中 { int n = ( )。 int i = 0。 // 從 LA 中取一元素 int k = ( x )。 n。 } } 2021/12/1 22 多項(xiàng)式及其運(yùn)算 A(x)