【正文】 if(ij){ temp=[i]。 } 66 [例 ] 已知線性表 (ao， a1， … ， an1)按順序存 儲，且每個元素都是均不相等的 整數(shù)。 65 167。 線性表的順序存儲和實現(xiàn) ?刪 除 一 個 元 素圖示 1 62 內(nèi)存 a1 a2 ai+1 V數(shù)組下標(biāo) 0 1 i1 n2 i n1 1 2 i 元素序號 i+1 n1 n an ai+2 167。 n=*p。} 58 167。} for(i=0。 } for(i = Lsize – 1。 return (1)。 線性表的順序存儲和實現(xiàn) ?插入一個元素算法 int sxbcr(int i,int x,int v[],int *p){ int j,n。 char publisher[30]。 線性表的順序存儲和實現(xiàn) 一、 線性表的順序存儲 （ 順序表 ） ?定義：把線性表中所有元素按其邏輯順序依次存儲到指定位置開始的連續(xù)空間中。 //若在線性表 A //中找到則將其刪除 } } 43 167。 線性表的類型定義 void delete(sqlist amp。 (8)求后繼 NextElem(sq,e) 若線性表中存在元素 e且不是最后一個 ,其作用是返回 e的后繼元素 。 參數(shù) i的合法取值范圍是： 1≤i≤n+ 1 167。 (3) 讀 表 元 素 GetElem(sq ， i) 。 線性表的類型定義32 167。) { count +=m+j。 for(j=0。k++) n+1 for(j=0。 （ 6）物理結(jié)構(gòu) (存儲結(jié)構(gòu) )： DE及關(guān)系在計算機中的表示。 4 第 一 章 緒 論 計算機程序 是 對信息進行加工處理。信息量的增加，信息范圍的拓寬，使系統(tǒng)程序和應(yīng)用程序的規(guī)模的日趨增大，結(jié)構(gòu)也日趨增大。數(shù)據(jù)項 是數(shù)據(jù)最小單位 (2) 數(shù)據(jù) (data) 是對客觀事物的 表示，指所有能輸入到計算機并被計算機程序處理的符號的總稱。 T(o)=O(f(n)) 時間復(fù)雜度分為平均時間復(fù)雜度和最壞時間復(fù)雜度 復(fù)雜度的值取規(guī)模函數(shù)最高階 13 算法和算法分析 b 、空間復(fù)雜度： 算法所需存貯空間 S(n)=O(f(n)) 23 13 算法和算法分析 例：分析下列語句段的時間復(fù)雜度 m = 0。 26 習(xí)題與練習(xí) 一 4. 設(shè) n 為正整數(shù)，寫出下列程序段的時間復(fù)雜度： （ 1） for(I=1。I++){ m=m+I。 s++。其作用是建立一個空表 sq(即建立線性表的構(gòu)架，但不含任何數(shù)據(jù)元素 )。 若 sq中存在一個或多個值與 x相等的元素 ， 則其作用是返回這些元素的序號的最小值；否則 ， 返回 0。 39 167。若在表A中，則將其從 A中刪除 。i++){ x=GetElem(B,i)。 //在線性表 B中查 x if (k0) {Insert(C,x,j)。 線性表的順序存儲和實現(xiàn) ?線性表的順序存儲示例 （圖書資料） typedef struct card{ int num。 free(pData )； 167。j) v[j]=v[j1]。 線性表的順序存儲和實現(xiàn) ?向線性表中表頭插入一個元素 InsertFront(List* L,const ElemTypeamp。 } 57 167。 j) Llist[j+1] = Llist[j]。 } 59 ? ?nii aaaaa ???? , 1,21 ?變成長度為 n1的線性表 ? ?nii aaaaa ???? , 11,21 ??需將第 i+1至第 n共（ ni）個元素前移 167。 *p=n。 } for(i = 0。 j++) Llist[j1] = 。 ElemType temp。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?單鏈表 (線性鏈表 ) 特點 : 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素 每個數(shù)據(jù)元素 ai，除存儲本身信息外，還需存儲其直接后繼的信息 70 ?單鏈表 (線性鏈表 ) 特點 : 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素 每個數(shù)據(jù)元素 ai，除存儲本身信息外，還需存儲其直接后繼的信息 指針 數(shù)據(jù)域 結(jié)點 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 74 data next p 結(jié)點（ *p） ?(*p)表示 p所指向的結(jié)點 ?(*p).data/pdata表示 p指向結(jié)點的數(shù)據(jù)域 ?(*p).next/pnext表示 p指向結(jié)點的指針域 ?生成一個 LNode型新結(jié)點： p=(LNode *)malloc(sizeof(LNode))。amp。j=0。 s data = x。 While(pnextamp。free(q)。 pb){ If(padata = pbdata){ pcnext = pa。 } 82 ?它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用 ?不需預(yù)先分配空間 ?指針占用額外存儲空間 ?不能隨機存取，查找速度慢 167。 167。 ④ 167。 pnextprior = pprior。 。棧中元素按 a1， a2， a3， … an的次序進棧，退棧按后進先出的原則進行的 ,因此按 an …… a3 a2 a1的次序出棧 棧 （ stack） 100 棧 （ stack） ?棧的主要操作： （ 1）建立一個空棧 IniStack(amp。 int top。 *e = Selements[Stop+1]。 pnext = Stop。 return OK。 for(i=1。 （ 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 括號的匹配檢驗 棧 （ stack） ?假設(shè)表達式中有多種擴號，可以用棧來進行擴號匹配檢驗，具體做法為： 非括號字符跳過不理；碰上左擴號，入棧；碰上右擴號，出棧，并且檢查出棧元素是否與當(dāng)前右擴號相匹配，若匹配繼續(xù)檢查，否則匹配失敗。e) （ 4） 判斷一個隊列是否為空 QueueEmpty(Q) （ 5）獲得隊頭元素值 GetHead(Q,amp。 Qrear = p。 return OK。 187。 0 1 2 …… front 0 1 2 rear 隊列初始化： front = rear = 0。 else { rear=(rear+1)%MAXSIZE。 如果能 , 說明如何得到 (即寫出 進棧 或 出棧 的序列 )。1||。 /*元素值 */ }node。col++) b[col][row] = a[row][col]。 /*行、列數(shù)，非零元素個數(shù) */ node data[SMAX]。試給出該循環(huán)隊列的隊空條件和隊滿條件 , 并寫出相應(yīng)的插入 (enqueue)和刪除(delqueue)元素的操作。 } } 隊列（ QUEUE） ?循環(huán)隊列入隊算法 139 ?循環(huán)隊列出隊 隊列（ QUEUE） int del_cycque(int sq[],int front,int rear,int *q){ if(front==rear) return(0)。 ?隊頭、隊尾指針 加 1時從 MaxSize 1直接進到 0，可用語言的取模 (余數(shù) )運算實現(xiàn)。 x=sq[front]。 出隊列： x=sq[++front]。 else{ s = Qfrontnext。 struct node *next。 122 隊列（ QUEUE） 一、隊列定義 ?隊列是限定只能在表的一端進插入，在表的另一端進行刪除的線性表 ?隊尾 (rear)——允許插入的一端 ?隊頭 (front)——允許刪除的一端 ?隊列特點： 先進先出 (FIFO) 123 隊列（ QUEUE） ?隊列定義 假設(shè)隊列 S=(a1， a2， a3， … an)， 則 a1稱為 隊首元素 ， an為 隊尾元素 。++i) printf(―%3d,‖,w)。一個對象部分地包含它自己 ， 或是用它自己給自己定義 169。 return OK。 } 108 二、鏈棧 （單鏈表） 棧 （ stack） typedef struct node { int data。 棧 （ stack） 一、棧的順序存儲 104 棧 （ stack） ?棧的順序存儲 ?棧頂指針 top 指示棧頂元素在順序棧中的位置 – top=1,?？?，此時出棧，則下溢（ 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ù)組維數(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。s) （ 3） 進棧 Push(amp。 第三章 棧與隊列 98 第 三 章 棧 與 隊列 167。 ?刪除給定結(jié)點 p 算法 就這么簡單！ 167。 pnextprior=pprior。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?在給定結(jié)點 p前插入一個新結(jié)點 89 ?在給定結(jié)點 p前插入一個新結(jié)點 S=(DLinklist)malloc(sizeof(DLNode))。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) h 空表 h ?循環(huán)鏈表 :表中最后一個結(jié)點的指針指向表頭結(jié)點，使鏈表構(gòu)成環(huán)狀 – 特點： 從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點 ， 提高查找效率 84 167。 pa = panext。 }//ListDelete_L ?刪除元素 ： 81 167。ji1){//尋找第 i個結(jié)點 ,并令 p指向其前趨 P = pnext。 pnext = s。amp。 j++。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 75 h a1 a2 an ^ …... h 空表 ^ 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)