【正文】 最小單位 (2) 數(shù)據(jù) (data) 是對客觀事物的 表示，指所有能輸入到計算機并被計算機程序處理的符號的總稱。這些信息之間大多數(shù)情況下往往具有重要的結(jié)構(gòu)關系。信息量的增加，信息范圍的拓寬，使系統(tǒng)程序和應用程序的規(guī)模的日趨增大，結(jié)構(gòu)也日趨增大。 ?主要涉及兩方面的問題： 信息的表示 和 信息的處理 信息的表示和組織直接關系到處理信息的程序 的效率，隨著計算機的應用領域的擴大。 4 第 一 章 緒 論 計算機程序 是 對信息進行加工處理。 10 12 基本概念和術語 (1) 數(shù)據(jù)元素 (data element) 數(shù)據(jù)基本單位，也稱節(jié)或孩子，可由若干個數(shù)據(jù)項組成。 （ 6）物理結(jié)構(gòu) (存儲結(jié)構(gòu) )： DE及關于在計算機中的表示。 T(o)=O(f(n)) 時間復雜度分為平均時間復雜度和最壞時間復雜度 復雜度的值取規(guī)模函數(shù)最高階 22 ?分析標準 a 、時間復雜度 ： 算法中基本操作重復執(zhí)行的次數(shù)。k++) n+1 for(j=0。 3. 設計下面問題算法，并分析最壞情況時間復雜性 : 在數(shù)組 A[1..n]中查找值為 K的元素，若找到輸出其位置 i ( 0 i n+1),否則輸出 0。 for(j=0。In。) { count +=m+j。 while(s=n1){ k=k+s*6。 線性表的類型定義32 167。 線性表的類型定義 基本運算 ( 1 ) 初始化 initList(sq)。 ( 3 ) 讀表 元 素 G e t E l e m ( s q ， i)。 線性表的類型定義 基本運算 (4)定位 (按值查找 )LocateElem(sq， x)。 參數(shù) i的合法取值范圍是： 1≤i≤n+ 1 167。參數(shù) i的合法取值范圍是：1≤i≤n。 (8)求后繼 NextElem(sq,e) 若線性表中存在元素 e且不是最后一個 ,其作用是返回 e的后繼元素 。 線性表的類型定義 [解 ]本題的算法思路是：依次檢查線性表 B中的每個元素，看它是否在線性表 A中。 線性表的類型定義 void delete(sqlist amp。 i=ListLen(B)。 //若在線性表 A //中找到則將其刪除 } } 43 167。 //依次獲取線性表 A中的元素 ， //存放在 x中 k=LocateElem(B， x)。 線性表的順序存儲和實現(xiàn) 一、 線性表的順序存儲 （ 順序表 ） ?定義：把線性表中所有元素按其邏輯順序依次存儲到指定位置開始的連續(xù)空間中。 線性表的順序存儲和實現(xiàn) 49 167。 char publisher[30]。 或動態(tài)申請和釋放內(nèi)存 DATATYPE *pData； pDat=(DATATYPE*)malloc(sizeof(DATATYPE))。 線性表的順序存儲和實現(xiàn) ?插入一個元素算法 int sxbcr(int i,int x,int v[],int *p){ int j,n。j=i。 return (1)。 線性表的順序存儲和實現(xiàn) ?插入算法時間復雜度 T(n) Pi是在第 i個元素之前插入一個元素的概率，則在長度為 n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為 ： 56 167。 return。 [0] = item。 L,const ElemTypeamp。 i。 j) [j+1] = [j]。 線性表的順序存儲和實現(xiàn) ?向線性表中的末尾添加一個元素 void InsertRear(Listamp。 } [] = item。 線性表的順序存儲和實現(xiàn) ?刪 除 一 個 元 素算法 int sxbsc(int i, int v[], int *p) { int j,n。jn。 } 61 內(nèi)存 a1 a2 ai ai+1 an 0 1 i1 V數(shù)組下標 n1 i n 1 2 i 元素序號 i+1 n n+1 167。 線性表的順序存儲和實現(xiàn) ?從線性表中刪除等于給定值的元素 1 int Delete(Listamp。 i 。 return 0。 。 167。 while (i=j) { while ([i]%2==0) i++。 A. data[j]=temp。 線性表的鏈式存儲結(jié)構(gòu) ?結(jié)點 數(shù)據(jù)域： 元素本身信息 指針域： 指示直接后繼的存儲位置 71 頭指針 31 H 167。 }LNode,*LinkList。 線性表的鏈式存儲結(jié)構(gòu) 75 h a1 a2 an ^ …... h 空表 ^ 167。j = 1。 j++。 線性表的鏈式存儲結(jié)構(gòu) ?在帶頭節(jié)點的單鏈表中第 i 個結(jié)點處插入新元素 x 78 167。amp。return ERROR。 pnext = s。 線性表的鏈式存儲結(jié)構(gòu) Status ListDelete_L (LinkList L,int I,ElemType *e){ P = L。ji1){//尋找第 i個結(jié)點 ,并令 p指向其前趨 P = pnext。 pnext = qnext。 }//ListDelete_L ?刪除元素 ： 81 167。 While (pa amp。 pa = panext。} } pcnext = pa?pa:pb。 線性表的鏈式存儲結(jié)構(gòu) h 空表 h ?循環(huán)鏈表 :表中最后一個結(jié)點的指針指向頭表 p或 pnext=H結(jié)點，使鏈表構(gòu)成環(huán)狀 – 特點： 從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點 ， 提高查找效率 84 167。 }DLNode,*DLinkLIst 86 L ?空雙向循環(huán)鏈表 ： ?非空雙向循環(huán)鏈表 ： L A B 167。 線性表的鏈式存儲結(jié)構(gòu) ?在給定結(jié)點 p前插入一個新結(jié)點 89 ?在給定結(jié)點 p前插入一個新結(jié)點 S=(DLinklist)malloc(sizeof(DLNode))。② ppriornext = s。 pnextprior=pprior。 ?刪除給定結(jié)點 p動畫演示 167。 ?刪除給定結(jié)點 p 算法 就這么簡單！ 167。 （分別以順序、鏈式實現(xiàn)） 95 習題與練習 二 A[MAXSIZE]的前elenum個分量中，且遞增有序。 第三章 棧與隊列 98 第 三 章 棧 與 隊列 167。 ?進棧 top+1。s) （ 3） 進棧 Push(amp。e) 101 進棧： top+1。 棧 （ stack） 一、棧的順序存儲 104 棧 （ stack） ?棧的順序存儲 ?棧頂指針 top 指示棧頂元素在順序棧中的 – top=1,?？眨藭r出棧，則下溢（ underflow） – top= MAXSIZE1,棧滿，此時入棧，則上溢（ overflow） 105 棧 （ stack） ?順序棧進、出棧圖示 top=1 1 2 3 4 5 0 棧空 棧頂指針 top,指向?qū)嶋H棧頂 后的空位置，初值為 1 top 1 2 3 4 5 0 進棧 A top 出棧 棧滿 B C D E F 設數(shù)組維數(shù)為 M top=1,棧空，此時出棧，則 下溢 （ underflow) top=M1,棧滿，此時入棧，則 上溢 （ overflow) top top top top top 1 2 3 4 5 0 A B C D E F top top top top top top ?？? 106 Status Push(SqStack *S,datatype e){ If(Stop = MAXSIZE1) /*上溢 */ return ERROR。 } 棧 （ stack） ? 進棧算法 107 棧 （ stack） ? 出棧算法 Status Pops (SqStack *S,datatype *e){ If (Stop == 1) /*下溢 */ return ERROR。 } 108 二、鏈棧 （單鏈表） 棧 （ stack） typedef struct node { int data。 初始時為NULL ? 鏈式棧無棧滿問題，空間可擴充 ? 插入與刪除僅在棧頂處執(zhí)行 ? 鏈式棧的棧頂在鏈頭 ? 適合于多棧操作 110 棧 （ stack） ?鏈棧的進棧算法 進棧等同于不帶頭結(jié)點單鏈表的頭插法 Status Push(LinkList * S,datatype e ){ p = (LinkList )malloc(sizeof(Linklist))。 return OK。 *e = pdata。一個對象部分地包含它自己 ， 或是用它自己給自己定義 169。 } 118 例 ：遞歸的執(zhí)行情況分析 棧 （ stack） 119 void print(Int w) { int i。++i) printf(“ %3d,” ,w)。 （ 1） w=3 top (2) 輸出： 3, 3, 3 w 2 print(1)。 122 隊列（ QUEUE） 一、隊列定義 ?隊列是限定只能在表的一端進插入，在表的另一端進行刪除的線性表 ?隊尾 (rear)——允許插入的一端 ?隊頭 (front)——允許刪除的一端 ?隊列特點： 先進先出 (FIFO) 123 隊列（ QUEUE） ?隊列定義 假設隊列 S=(a1， a2， a3， … an)， 則 a1稱為 隊首元素 ， an為 隊尾元素 。Q,e) （ 3） 出隊 DeQueue(amp。 struct node *next。 pnext = NULL。 else{ s = Qfrontnext。 *e = sdata。 出隊列： x=sq[++front]。入隊： rear=(rear+1)%M。 x=sq[front]。 隊空： rear = front。 ?隊頭、隊尾指針 加 1時從 MaxSize 1直接進到 0，可用語言的取模 (余數(shù) )運算實現(xiàn)。 elements[rear]=item； ?出隊 front=(front+1)%MaxSize。 } } 隊列（ QUEUE） ?循環(huán)隊列入隊算法 139 ?循環(huán)隊列出入隊圖示 隊列（ QUEUE） int del_cycque(int sq[],int front,int rear,int *q){ if(front==rear) return(0)。 } } 140 1. 鐵路進行列車調(diào)度時 , 常把站臺設計成棧式結(jié)構(gòu)的站臺 ， 如右圖所示 。試給出該循環(huán)隊列的隊空條件和隊滿條件 , 并寫出相應的插入 (enqueue)和刪除(delqueue)元素的操作。I = max(i,j),J=min(i,j) 4． 3 矩陣的壓縮存儲 好東西??！ 158 二 . 稀疏矩陣 ?Am*n 中非零元素個數(shù)遠小于零元素個數(shù) 4． 3 矩陣的壓縮存儲 1．三元組表 組成 ：所有非零元素（行，列，值） + （行數(shù)，列數(shù)，非零元素個數(shù)） 159 ?三元組表類型說明： define SMAX 16 typedef int datatype； typedef struct{ int i,j。 /*行、列數(shù)，非零元素個數(shù) */ node data[SMAX]。row++) for(c