【正文】 是數(shù)據(jù)最小單位 (2) 數(shù)據(jù) (data) 是對(duì)客觀事物的 表示，指所有能輸入到計(jì)算機(jī)并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。 ? DE存儲(chǔ)稱(chēng)為 節(jié)點(diǎn) ?關(guān)系存儲(chǔ)： a. 順序存儲(chǔ) b. 鏈?zhǔn)酱鎯?chǔ) 17 12 基本概念和術(shù)語(yǔ) （ 7） DS廣義定義： ? DE 的邏 輯 結(jié) 構(gòu) ? DE 的物 理 結(jié) 構(gòu) ? DE 的 抽 象 運(yùn) 算 （ 8）基本操作 ? 加工型：插入 刪除 更新 排序 ? 引用型：查找 18 1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。 T(o)=O(f(n)) 時(shí)間復(fù)雜度分為平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度 復(fù)雜度的值取規(guī)模函數(shù)最高階 13 算法和算法分析 b 、空間復(fù)雜度： 算法所需存貯空間 S(n)=O(f(n)) 23 13 算法和算法分析 例：分析下列語(yǔ)句段的時(shí)間復(fù)雜度 m = 0。jk。 26 習(xí)題與練習(xí) 一 4. 設(shè) n 為正整數(shù)，寫(xiě)出下列程序段的時(shí)間復(fù)雜度： （ 1） for(I=1。jn。I++){ m=m+I。 j++。 s++。 線性表的類(lèi)型定義 一、線性表的定義 ?一個(gè)線性表可以用一個(gè)標(biāo)識(shí)符來(lái)命名： A=(a1 , a2 , … , ai , ai+1 , … , an) ai可以是基本數(shù)據(jù)類(lèi)型也可以是 struct 類(lèi)型 33 167。其作用是建立一個(gè)空表 sq(即建立線性表的構(gòu)架，但不含任何數(shù)據(jù)元素 )。 若1≤i≤ListLen(sq)， 則其作用是返回線性表 sq的第 i個(gè)數(shù)據(jù)元素 。 若 sq中存在一個(gè)或多個(gè)值與 x相等的元素 ， 則其作用是返回這些元素的序號(hào)的最小值；否則 ， 返回 0。 線性表的類(lèi)型定義 38 167。 39 167。否則，返回 NULL 40 167。若在表A中，則將其從 A中刪除 。A， sqlist B) { //A為引用型參數(shù) int i, k。i++){ x=GetElem(B,i)。 線性表的類(lèi)型定義 [解 ] 先始化線性表 C，然后依次檢查線性表 A中的每個(gè)元素，看它是否在線性表 B中；若在線性表 B中，則將其插入到線性表 C中 . 基本運(yùn)算 [例 ] 利用線性表的基本運(yùn)算，編寫(xiě)將線性表 A和 B中公共元素生成線性表 C的算法 44 167。 //在線性表 B中查 x if (k0) {Insert(C,x,j)。即用一組地址連續(xù)的存儲(chǔ)單元存放一個(gè)線性表 ?特點(diǎn)： ? 實(shí)現(xiàn)邏輯上相鄰 —物理地址相鄰 ? 實(shí)現(xiàn)隨機(jī)存取 ?實(shí)現(xiàn)： （ 一維 ） 數(shù)組 46 下標(biāo)位置 0 1 … i1 i … n1 … MaxSize1 數(shù)組存貯空間 a1 a2 … ai ai+1 … an … 167。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?線性表的順序存儲(chǔ)示例 （圖書(shū)資料） typedef struct card{ int num。 float price。 free(pData )； 167。 n=*p。j) v[j]=v[j1]。 } } 53 167。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?向線性表中表頭插入一個(gè)元素 InsertFront(List* L,const ElemTypeamp。 i = 0。 } 57 167。 iLsize。 j) Llist[j+1] = Llist[j]。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?向線性表中的末尾添加一個(gè)元素 void InsertRear(List* L, ElemType item){ if(Lsize = = MaxSize){ printf( ―List overflow!‖ )。 } 59 ? ?nii aaaaa ???? , 1,21 ?變成長(zhǎng)度為 n1的線性表 ? ?nii aaaaa ???? , 11,21 ??需將第 i+1至第 n共（ ni）個(gè)元素前移 167。 if((i1) || (in)) return (0)。 *p=n。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?刪 除 一 個(gè) 元 素圖示 2 63 ? ? ? ?nOnTninnEnQnidei????????? 1 21)(11則若認(rèn)為 故在順序表中插入或刪除一個(gè)元平均移動(dòng)表的一半元素，當(dāng) n很大時(shí)，效率很低 167。 } for(i = 0。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?從線性表中刪除等于給定值的元素 2 if(i = = Lsize){ printf( ―Deleted element is not exist!‖ )。 j++) Llist[j1] = 。設(shè)計(jì) 把所有奇數(shù)移到所有的偶數(shù)前邊的算法 (要求 時(shí)間最少，輔助空間最少 )。 ElemType temp。[i]=[j]。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?單鏈表 (線性鏈表 ) 特點(diǎn) : 用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素 每個(gè)數(shù)據(jù)元素 ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息 70 ?單鏈表 (線性鏈表 ) 特點(diǎn) : 用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素 每個(gè)數(shù)據(jù)元素 ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息 指針 數(shù)據(jù)域 結(jié)點(diǎn) 167。 struct node *next。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 74 data next p 結(jié)點(diǎn)（ *p） ?(*p)表示 p所指向的結(jié)點(diǎn) ?(*p).data/pdata表示 p指向結(jié)點(diǎn)的數(shù)據(jù)域 ?(*p).next/pnext表示 p指向結(jié)點(diǎn)的指針域 ?生成一個(gè) LNode型新結(jié)點(diǎn)： p=(LNode *)malloc(sizeof(LNode))。 頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空 76 167。amp。 *e = pdata。j=0。j++。 s data = x。} 79 167。 While(pnextamp。 } if(!(pnext)||j i1) return ERROR。free(q)。 pb = Lbnext。 pb){ If(padata = pbdata){ pcnext = pa。pc = pb。 } 82 ?它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用 ?不需預(yù)先分配空間 ?指針占用額外存儲(chǔ)空間 ?不能隨機(jī)存取，查找速度慢 167。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) （ double linked list ) prior element next 指向前驅(qū)結(jié)點(diǎn) 數(shù)據(jù) 指向后繼結(jié)點(diǎn) ?結(jié)點(diǎn)定義 typedef struct node{ datatype data。 167。 sprior = pprior。 ④ 167。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?刪除給定結(jié)點(diǎn) p 91 ppriornext=pnext。 pnextprior = pprior。 3 存儲(chǔ)結(jié)構(gòu)的選用 順序與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的選用應(yīng)考慮因素： （ 1）存儲(chǔ)空間 （ 2）運(yùn)算時(shí)間 （ 3）程序設(shè)計(jì)語(yǔ)言 結(jié)點(diǎn)數(shù)據(jù)占用存儲(chǔ)量量結(jié)點(diǎn)數(shù)據(jù)本身占用存儲(chǔ)存儲(chǔ)密度 ?94 習(xí)題與練習(xí) 二 ： 頭結(jié)點(diǎn)、頭指針和開(kāi)始結(jié)點(diǎn) 鏈表有 。 。 定義 ?通常稱(chēng)插入、刪除的這一端（如 表尾 ）為棧頂 (Top)，另一端（表頭）為 棧底(Bottom)。棧中元素按 a1， a2， a3， … an的次序進(jìn)棧，退棧按后進(jìn)先出的原則進(jìn)行的 ,因此按 an …… a3 a2 a1的次序出棧 棧 （ stack） 100 棧 （ stack） ?棧的主要操作： （ 1）建立一個(gè)空棧 IniStack(amp。s,amp。 int top。 Selements[Stop] = e。 *e = Selements[Stop+1]。 }LinkList。 pnext = Stop。/*下溢 */ p = Stop。 return OK。利用前面運(yùn)算來(lái)求得答案的過(guò)程 ?實(shí)現(xiàn)： 建立遞歸工作棧 ?優(yōu)點(diǎn)： 遞歸函數(shù)結(jié)構(gòu)清晰 ， 程序易讀 ， 正確性易證明 ?缺點(diǎn)： 速度慢 ， 空間大效率低 棧 （ stack） 2．遞歸調(diào)用 116 棧 （ stack） void p (參數(shù)表 ) { if （遞歸結(jié)束條件） 可直接求解步驟； 基本項(xiàng) else p（較小的參數(shù)）； 歸納項(xiàng) } ?遞歸算法的一般形式 117 棧 （ stack） 例：求 n! = 1， n=0 n*(n1)！ n0 int Factorial(int n){ if (n==0) return 1。 for(i=1。 } } 棧 （ stack） 運(yùn)行結(jié)果： 1， 2， 2， 3， 3， 3， ? 例 遞歸的執(zhí)行情況分析 120 棧 （ stack） 主程序 (1) print(w) w=3。 （ 3） w=1 （ 2） w=2 （ 1） w=3 top (4)輸出： 1 w 0 （ 4） w=0 （ 3） w=1 （ 2） w=2 （ 1） w=3 top w (2) 2 (1) 3 輸出：(3) 1 (2) 2 (1) 3 3 (1 ) 3 返回 (3) 1 (2) 2 (1) 3 top (4) 0 結(jié)束 ?上例圖示分析 121 括號(hào)的匹配檢驗(yàn) 棧 （ stack） ?假設(shè)表達(dá)式中有多種擴(kuò)號(hào)，可以用棧來(lái)進(jìn)行擴(kuò)號(hào)匹配檢驗(yàn)，具體做法為： 非括號(hào)字符跳過(guò)不理；碰上左擴(kuò)號(hào)，入棧；碰上右擴(kuò)號(hào)，出棧，并且檢查出棧元素是否與當(dāng)前右擴(kuò)號(hào)相匹配，若匹配繼續(xù)檢查，否則匹配失敗。 124 入隊(duì) 時(shí)將 rear+1, 新元素插入 elements[rear]位置 . 出隊(duì) 時(shí)，將加 front+1, 刪去元素 隊(duì)列（ QUEUE） a1 a2 a3…………………… .an 入隊(duì) 出隊(duì) front rear 隊(duì)列 Q=(a1,a2,……,an) ?隊(duì)列定義 125 a1 a2 a3…………………… .an 端 1 端 2 入隊(duì) 出隊(duì) 入隊(duì) 出隊(duì) 隊(duì)列（ QUEUE） ?雙端隊(duì)列 126 隊(duì)列（ QUEUE） ?隊(duì)列的主要操作 （ 1）建立一個(gè)空隊(duì)列 InitQueue(amp。e) （ 4） 判斷一個(gè)隊(duì)列是否為空 QueueEmpty(Q) （ 5）獲得隊(duì)頭元素值 GetHead(Q,amp。 128 front rear x入隊(duì) ^ x front rear y入隊(duì) x ^ y front rear 空隊(duì) ^ 隊(duì)列（ QUEUE） ?鏈隊(duì)列圖示 129 入隊(duì)不用考慮隊(duì)滿 ,但出隊(duì)要考慮隊(duì)空 隊(duì)空條件為