【文章內(nèi)容簡(jiǎn)介】 … … … … … … … … … 特點(diǎn)： 存儲(chǔ)空間：中（若學(xué)生沒有選該課程，對(duì)應(yīng)空間仍存在） 算法時(shí)間：少 算法簡(jiǎn)潔性差：算法完全依賴數(shù)據(jù)結(jié)構(gòu) 設(shè)計(jì)方案 2：將學(xué)生的全部數(shù)據(jù)項(xiàng)放在一個(gè)表中，但一個(gè)學(xué)生的一門課程成績(jī)對(duì)應(yīng)一條記錄。這樣成績(jī)項(xiàng)只需要一個(gè)，為了區(qū)分不同課程成績(jī)，需增加一個(gè)課程編號(hào)項(xiàng)。對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下： struct stud { int no。 /*學(xué)號(hào) */ char name[10]。 /*姓名 */ int bno。 /*班號(hào) */ int o。 /*課程編號(hào) */ int deg。 /*課程分?jǐn)?shù) */ }。 no name bno o deg 1 張斌 9901 1 78 1 張斌 9901 2 82 1 張斌 9901 3 63 1 張斌 9901 4 92 1 張斌 9901 5 85 1 張斌 9901 6 83 8 劉麗 9902 1 65 8 劉麗 9902 2 95 8 劉麗 9902 3 72 8 劉麗 9902 4 78 8 劉麗 9902 5 80 8 劉麗 9902 6 79 … … … … … 特點(diǎn)： 存儲(chǔ)空間：大 算法時(shí)間：多 算法簡(jiǎn)潔性：好 設(shè)計(jì)方案 3： 將學(xué)生的學(xué)號(hào)、姓名和班號(hào)放在一個(gè)表中，將成績(jī)數(shù)據(jù)放在另一個(gè)表中，兩者通過學(xué)號(hào)關(guān)聯(lián)。前者一個(gè)學(xué)生對(duì)應(yīng)一個(gè)記錄，后者一門課程成績(jī)對(duì)應(yīng)一條記錄。對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下： struct stud1 { int no。 /*學(xué)號(hào) */ char name[10]。 /*姓名 */ int bno。 /*班號(hào) */ }。 struct stud2 { int no。 /*學(xué)號(hào) */ int o。 /*課程編號(hào) */ int deg。 /*分?jǐn)?shù) */ }。 no name bno 1 張斌 9901 8 劉麗 9902 … … … no o deg 1 1 78 1 2 82 1 3 63 1 4 92 1 5 85 1 6 83 8 1 65 8 2 95 8 3 72 8 4 78 8 5 80 8 6 79 … … … 特點(diǎn)： 存儲(chǔ)空間：少 算法時(shí)間：中 算法簡(jiǎn)潔性：好 最佳方案 數(shù)據(jù)結(jié)構(gòu) 算法 數(shù)據(jù)類型 i j k 求解問題編寫程序的代碼： i＊ j＊ k種 優(yōu) 選 最佳方案 本課程的目標(biāo) 本章小結(jié) 本章介紹了數(shù)據(jù)結(jié)構(gòu)的基本概念 ,主要學(xué)習(xí)要點(diǎn)如下： (1) 數(shù)據(jù)結(jié)構(gòu)的定義 ,數(shù)據(jù)結(jié)構(gòu)包含的邏輯結(jié)構(gòu) 、存儲(chǔ)結(jié)構(gòu)和運(yùn)算三方面的相互關(guān)系 。 (2) 各種邏輯結(jié)構(gòu)即線性結(jié)構(gòu) 、 樹形結(jié)構(gòu)和圖形結(jié)構(gòu)之間的差別 。 (3) 數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型的差別和聯(lián)系 。 (4) 算法的定義及其特性 。 (5) 算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析。 練習(xí)題 1： 習(xí)題 習(xí)題 5和習(xí)題 6。 上機(jī)題： 熟悉 VC++ 第 2章 線性表 線性表的基本概念 線性表的順序存儲(chǔ) 線性表的鏈?zhǔn)酱鎯?chǔ) 線性表的應(yīng)用 本章小結(jié) 有序表 線性表的基本概念 線性表的定義 線性表的運(yùn)算 線性表的定義 線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。 該序列中所含元素的個(gè)數(shù)叫做線性表的長(zhǎng)度 ,用 n表示 ,n≥0。 當(dāng) n=0時(shí) ,表示線性表是一個(gè)空表 ,即表中不包含任何元素。設(shè)序列中第 i(i表示位序 )個(gè)元素為ai(1≤i≤n)。 線性表的一般表示為 : (a1,a2,… ai,ai+1,… ,an) 其中 a1為第一個(gè)元素 ,又稱做表頭元素 ,a2為第二個(gè)元素 ,an為最后一個(gè)元素 ,又稱做表尾元素 。 例如 ,在線性表 (1,4,3,2,8,10) 中 ,1為表頭元素 ,10為表尾元素。 線性表的運(yùn)算 線性表的基本運(yùn)算如下 : (1) 初始化線性表 InitList(amp。L):構(gòu)造一個(gè)空的線性表 L。 (2) 銷毀線性表 DestroyList(amp。L):釋放線性表 L占用的內(nèi)存空間 。 (3) 判線性表是否為空表 ListEmpty(L):若 L為空表 ,則返回真 ,否則返回假 。 (4) 求線性表的長(zhǎng)度 ListLength(L):返回 L中元素個(gè)數(shù) 。 (5) 輸出線性表 DispList(L):當(dāng)線性表 L不為空時(shí) ,順序顯示 L中各結(jié)點(diǎn)的值域 。 (6) 求線性表 L中指定位置的某個(gè)數(shù)據(jù)元素GetElem(L,i,amp。e):用 e返回 L中第 i(1≤i≤ListLength(L))個(gè)元素的值 。 (7) 定位查找 LocateElem(L,e):返回 L中第 1個(gè)值域與 e相等的位序 。 若這樣的元素不存在 ,則返回值為 0。 (8) 插入數(shù)據(jù)元素 ListInsert(amp。L,i,e):在 L的第i(1≤i≤ListLength(L)+1)個(gè)元素之前插入新的元素 e,L的長(zhǎng)度增 1。 (9) 刪除數(shù)據(jù)元素 ListDelete(amp。L,i,amp。e):刪除 L的第i(1≤i≤ListLength(L))個(gè)元素 ,并用 e返回其值 ,L的長(zhǎng)度減 1。 例 假設(shè)有兩個(gè)集合 A 和 B 分別用兩個(gè)線性表 LA 和 LB 表示 ,即線性表中的數(shù)據(jù)元素即為集合中的成員 。 編寫一個(gè)算法求一個(gè)新的集合 C=A∪ B,即將兩個(gè)集合的并集放在線性表 LC中 。 解 :本算法思想是 :先初始化線性表 LC,將 LA的所有元素復(fù)制到 LC中 ,然后掃描線性表 LB,若 LB的當(dāng)前元素不在線性表 LA中 ,則將其插入到 LC中。算法如下 : void unionList(List LA,List LB,List amp。LC) { int lena,lenc,i。 ElemType e。 InitList(LC)。 for (i=1。i=ListLength(LA)。i++) /*將 LA的所有元素插入到 Lc中 */ { GetElem(LA,i,e)。 ListInsert(LC,i,e)。 } lena=ListLength(LA)。 /*求線性表的長(zhǎng)度 */ lenB=ListLength(LB)。 for (i=1。i=lenb。i++) { GetElem(LB,i,e)。 /*取 LB中第 i個(gè)數(shù)據(jù)元素賦給 e*/ if (!LocateElem(LA,e)) ListInsert(LC,++lenc,e)。 /*LA中不存在和 e相同者 ,則插入到 LC中 */ } } 由于 LocateElem(LA,e) 運(yùn) 算的時(shí)間復(fù)雜度為O(ListLength(LA)),所以本算法的時(shí)間復(fù)雜度為 : O(ListLength(LA)*ListLength(LB))。 線性表的順序存儲(chǔ) 線性表的順序存儲(chǔ) —順序表 順序表基本運(yùn)算的實(shí)現(xiàn) 線性表的順序存儲(chǔ) —順序表 線性表的順序存儲(chǔ)結(jié)構(gòu)就是 :把線性表中的所有元素按照其邏輯順序依次存儲(chǔ)到從計(jì)算機(jī)存儲(chǔ)器中指定存儲(chǔ)位置開始的一塊連續(xù)的存儲(chǔ)空間中。 這樣 ,線性表中第一個(gè)元素的存儲(chǔ)位置就是指定的存儲(chǔ)位置 ,第 i+1個(gè)元素 (1≤i≤n1)的存儲(chǔ) 位置緊接在第 i個(gè)元素的存儲(chǔ)位置的后面。 線性表 ? 邏輯結(jié)構(gòu) 順序 表 ? 存儲(chǔ)結(jié)構(gòu) 假定線性表的元素類型為 ElemType,則每個(gè)元素所占用存儲(chǔ)空間大小 (即字節(jié)數(shù) )為sizeof(ElemType),整個(gè)線性表所占用存儲(chǔ)空間的大小為 : n*sizeof(ElemType) 其中 ,n表示線性表的長(zhǎng)度。 a 1 LO C (A ) 0 a 2 LO C (A )+s iz e o f(E le m T y p e ) 1 線性表存儲(chǔ)空間 存儲(chǔ)地址 下標(biāo)位置 ┇ ┇ a i LO C (A )+(i 1 )* s iz e o f(E le m T y p e ) i 1 ┇ ┇ a n LO C (A )+(n 1 )* s iz e o f(E le m T y p e ) n 1 ┇ ┇ ┇ LO C (A )+(M a x Size 1 )* s iz e o f(E le m T y p e ) M a x Size 1 順序表示意圖 在定義一個(gè)線性表的順序存儲(chǔ)類型時(shí) ,需要定義一個(gè)數(shù)組來存儲(chǔ)線線表中的所有元素和定義一個(gè)整型變量來存儲(chǔ)線性表的長(zhǎng)度 。 假定數(shù)組用 data[MaxSize]表示 ,長(zhǎng)度整型變量用length表示 ,并采用結(jié)構(gòu)體類型表示 ,則元素類型為通用類型標(biāo)識(shí)符 ElemType的線性表的順序存儲(chǔ)類型可描述如下 : typedef struct { ElemType data[MaxSize]。 int length。 } SqList。 /*順序表類型 */ 其中 ,data成員存放元素 ,length成員存放線性表的實(shí)際長(zhǎng)度。 說明：由于 C/C++中數(shù)組的下標(biāo)從 0開始，線性表的第 i個(gè)元素 ai存放順序表的第 i1位置上。為了清楚，將 ai在邏輯序列中的位置稱為 邏輯位序 ，在順序表中的位置稱為 物理位序 。 順序表基本運(yùn)算的實(shí)現(xiàn) 一旦采用順序表存儲(chǔ)結(jié)構(gòu) ,我們就可以用 C/C++語言實(shí)現(xiàn)線性表的各種基本運(yùn)算。為了方便 ,假設(shè)ElemType為 char類型 ,使用如下自定義類型語句 : typedef char ElemType。 1. 建立順序表 其方法是將給定的含有 n個(gè)元素的數(shù)組的每個(gè)元素依次放入到順序表中，并將 n賦給順序表的長(zhǎng)度成員。算法如下： void CreateList(SqList *amp。L,ElemType a[],int n) /*建立順序表 */ { int i。 L=(SqList *)malloc(sizeof(SqList))。 for (i=0。in。i++) Ldata[i]=a[i]。 Llength=n。 } 2. 順序表基本運(yùn)算算法 (1) 初始化線性表 InitList(L) 該運(yùn)算的結(jié)果是構(gòu)造一個(gè)空的線性表 L。 實(shí)際上只需將 length成員設(shè)置為 0即可 。 void InitList(SqList *amp。L) //引用型指針 { L=(SqList *)malloc(sizeof(SqList))。 /*分配存放線性表的空間 */ Llength=0。 } 本算法的時(shí)間復(fù)雜度為 O(1)。 順序表 L (2) 銷毀線性表 DestroyList(L) 該運(yùn)算的結(jié)果是釋放線性表 L占用的內(nèi)存空間 。 void DestroyList(SqList *amp。L) { free(L)。 } 本算法的時(shí)間復(fù)雜度為 O(1)。 (3) 判定是否為空表 ListEmpty(L) 該運(yùn)算返回一個(gè)值表示 L是否為空表 。 若 L為空表 ,則返回 1,否則返回 0。 int ListEmpty(SqList *L) { return(Llength==0)。 } 本算法的時(shí)間復(fù)雜度為 O(1)。 (4) 求線性表的長(zhǎng)度 ListLength(L) 該運(yùn)算返回順序表 L的長(zhǎng)度 。 實(shí)際上只需返回length成員的值即可 。 int ListLength(SqList *L) { return(Llength)。 } 本算法的時(shí)間復(fù)雜度為 O(1)。 (5) 輸出線性表 DispList(L) 該運(yùn)算當(dāng)線性表 L不為空時(shí)