數據結構ppt課件完整版_第1頁
數據結構ppt課件完整版_第2頁
數據結構ppt課件完整版_第3頁
數據結構ppt課件完整版_第4頁
數據結構ppt課件完整版_第5頁
已閱讀5頁,還剩299頁未讀, 繼續免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、數據結構 什么是數據結構 重要性及學習意義 課程特點及學習方法 參考資料序:課程介紹1、數據結構是程序設計的重要組成部分 用計算機解決問題的步驟: 從具體問題中抽象出一個適當的數學模型。 設計一個適合該數學模型的算法。 編寫程序。 進行測試、調整、修改,直至解決問題。 瑞士計算機科學家N.writh提出: 程序設計=算法+數據結構 什么是數據結構2、數據結構的主要內容 計算機科學發展的早期主要用來做科學計算,處理一些數值計算問題,這類問題的數學模型為數學方程,但是隨其發展,已經不局限于此。例1 電話號碼簿的查詢問題李王 什么是數據結構例2 學生信息檢索河南商專計算機系軟件2010級2009級計

2、算機應用會計系 什么是數據結構例3 交通圖的查找3、數據結構的定義 數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及他們之間的關系和操作的學科。是數據的組織、存儲和運算的總和。邏輯結構:指數據元素之間的邏輯關系,是從具體問題中抽象出來的數學模型,獨立于計算機。存儲結構:指數據元素之間的邏輯關系在計算機中的表示,又稱物理結構。運算操作:查詢,插入,刪除 什么是數據結構計算機專業的核心課程之一是程序設計及軟件開發的重要基礎各類計算機考試、專升本的主要內容學習它,有助于形成計算機處理問題的意識:存儲、輸入、處理、輸出具有復雜問題的解決能力 重要性及學習意義課程特點:理論性強,難度較大

3、學習方法:理解課堂內容:認真聽、做筆記勤于習題演練:強調代碼要獨立寫加強上機實踐:階段性調試算法養成獨立思考問題、解決問題的習慣 課程特點及學習方法嚴尉敏、吳偉民:數據結構,清華大學出版社嚴尉敏、吳偉民:數據結構習題集,清華大學出版社徐士良:實用數據,清華大學出版社李春葆:數據結構習題與解析,清華大學出版社 參考資料主要內容 1.數據結構課程的性質和地位 2.基本概念和術語 3.算法及算法分析 重點、難點 基本概念及術語,算法評價的方法第1章 數據結構概述數據(Data):是對信息的一種符號表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數據元素(Data Elem

4、ent):是數據的基本單位,在計算機程序中通常作為一個整體進行考慮和處理。 一個數據元素可由若干個數據項組成。數據項是數據的不可分割的最小單位。數據對象(Data Object):是性質相同的數據元素的集合。是數據的一個子集。 如:自然數集N0,1,2,3, 字母集CA,B,C1.1 基本概念和術語數據結構(Data Structure):是相互之間存在一種或多種特定關系的數據元素的集合。1.1 基本概念和術語形式化定義:Data_Structures = (D, S)其中: D是數據元素的有限集, S是D上關系的有限集。包括三個方面: 邏輯結構、存儲結構、存儲及實現邏輯結構:描述其邏輯關系。

5、可歸結為以下四類: 集合結構1.1 基本概念和術語線性結構(一對一)樹形結構(一對多)圖狀結構(多對多)線性結構的形式化描述:Line=(D, R) D= a, b, c, d R=, , 存儲結構:邏輯結構在計算機中的表示。分為兩類:順序存儲結構:邏輯關系由存儲單元的鄰接關系體現 即:邏輯上相鄰的物理上也相鄰。 通常用一維數組來描述。 可延伸為:索引和散列鏈式存儲結構:元素可以任意存儲,不要求邏輯上相鄰的物理上也相鄰,其邏輯關系一般用指針來實現。 注意:任一算法,設計在邏輯結構,但實現在存儲結構上。1.1 基本概念和術語數據類型:具有相同性質的操作對象及其運算方法的集合。即:一個值的集合和定

6、義在這個值集上的一組操作的總稱。 如:int:3276832767;+、*、抽象數據類型(Abstract Data Type 簡稱ADT) 是指一個數學模型以及定義在此數學模型上的一組操作 它與數據類型實質上是一個概念,但其特征是使用與實現分離,實行封裝和信息隱蔽(獨立于計算機)1.1 基本概念和術語 討論每一種數據結構時,均要介紹其上的運算。 一般的,運算可分為下列兩種基本類型:(1)加工型運算:運算后改變了原結構中數據元素的個數或數據元素的內容。(2)引用型運算:運算不改變結構中數據元素的個數和元素的內容,只從結構中提取某些信息作為運算的結果。1.2 運算 常用的基本運算主要包括:插入(

7、加工型):在原結構的指定位置上增添新的數據元素。刪除(加工型):將原結構中的某個指定的數據元素刪除。查找(引用型):從結構中找出滿足條件的數據元素的位置。讀取(引用型):使用結構中滿足條件的數據元素的內容。更新(加工型):更換結構中某個數據元素的內容。 使用這些基本運算,可以構成其他的復雜運算1.2 運算一、算法的概念 是為了解決某類問題而定義的一個有限長的操作序列。 一個算法必須滿足五個重要特性: 1、有窮性:有限的指令,每個指令在有限的時間內完成 2、確定性:每一條指令都有明確的含義,相同的條件下執行線路是確定的 3、可行性:每個步驟都是切實可行,足夠基本 4、輸入:一個算法可以有一個或多

8、個輸入,也可以沒有輸入(隱含輸入) 5、輸出:一個算法可以有一個或多個輸出1.3 算法及算法分析1、正確性,首先要滿足算法需求,其次對算法的“正確性”的理解有以下四個層次:2、易讀性,一個好的算法主要是與他人交流共享,晦澀難懂的算法不利于交流、調試、維護。3、健壯性,對于非法數據能夠給出合理反應4、高效性,主要有兩方面,運行時間和占用空間,即時間復雜度和空間復雜度此外,還要考慮算法的可維護性。二、算法的設計要求程序不含語法錯誤對于隨意的幾組合法數據輸入能夠得出符合要求的結構對于精心設計的典型、有刁難性的合法數據能夠得出符合要求的結果程序對所有的合法的輸入數據都能得出符合要求的結果1.3 算法及

9、算法分析1、算法的時間復雜度 算法在整個運行過程中消耗的時間。 影響運行時間的因素: 算法選用的策略問題的規模編程語言編譯程序產生的目標代碼的質量機器運行指令的速度衡量算法運行時間的方法 事后統計 缺點:必須執行程序;容易受其他硬件、軟件因素影響 事前估計1.3 算法及算法分析二、算法分析(時間、空間) 討論算法主要討論隨著問題規模的增長,算法執行時間的增長率,通常用一個函數來表示: 它表示隨著問題規模n的增大,算法的執行時間的增長率和f(n)的增長率相同,稱為算法的漸進時間復雜度,簡稱時間復雜度。1.3 算法及算法分析算法的時間復雜度怎么分析算法的時間復雜度呢?運行時間 = 算法中每條語句執

10、行時間之和。每條語句執行時間 = 該語句的執行次數(頻度)* 語句執行一次所需時間。語句執行一次所需時間取決于機器的指令性能和速度和編譯所產生的代碼質量,很難確定。設每條語句執行一次所需時間為單位時間,則一個算法的運行時間就是該算法中所有語句的頻度之和。例: for (i = 0; i n; i+ ) n+1 for ( j = 0; j y) x=5; else x=10; T(n)=O(1)算法的時間復雜度(3) for(i=1;i=n;i+) ai=i; T(n)=O(n)(4) n=100; for(i=1;i=n;i+) ai=i; T(n)=O(1)(5) x=0; for(i=1

11、;i=n;i+) for(j=1;j=i;j+) for(k=1;k=j;k+) x+;=O(n3)T(n)=(6) i=s=0; while(s 1 b, i = 1 第二章 線性表順序表的C語言實現#define maxlen 1000typedef int elemtype; elemtype elemmaxlen; int len; typedef struct SqList; SqList *L,*p;順序表的運算1.順序表的查找 對于給定的數據元素,找出其在線性表中的位置int SqSearch(SqList * L, elemtype x)/在順序表L中查找數據元素x在表中第一次

12、出現的位置 int j; for(j=0; jlen; j+) if (L-elemj=x) return (j+1); return (0);x=38x=39L-Len=7 23 0 75 1 41 2 38 3 54 4 62 5 17 6 7 8第二章 線性表時間復雜度:O(n)如按序號查找: O(1)順序表的運算2.順序表的插入 在線性表(n個元素)的第i個位置前插入一個元素 int SqInsert(SqList * L, elemtype x,int i ) 初始條件:線性表L已存在, 1in+1 操作結果:在L的第i個元素之前插入新的元素x,L的長度增1。實現步驟:將第n至第i

13、位的元素向后移動一個位置;將要插入的元素寫到第i個位置;表長加1。注意:事先應判斷: 插入位置i 是否合法?表是否已滿?第二章 線性表第二章 線性表順序表的運算int SqInsert(SqList * L, elemtype x, int i)/在順序表L的第i個數據元素之前插入一個數據元素x int j,n; n=L-len; if(in+1) printf(Error!); return (0); if(n=maxlen) printf(Overflow!); return (0); for(j=n; j=i; j-)L-elemj=L-elemj-1; L-elemi-1=x; L-l

14、en+; return (1); 23 0 75 1 41 2 38 3 54 4 62 5 17 6 7 8L-len=7SqInsert( L,66,5)第二章 線性表順序表的運算線性表的插入算法的時間復雜度 插入算法中,其時間主要消耗在移動數據元素上,數據的移動次數與插入元素的位置有關(討論等概率)。所有可能的元素移動次數合計: 0+1+n = n(n+1)/2共有多少種插入形式? 連頭帶尾有n+1種!故插入時的平均移動次數為: n(n+1)/2(n+1) n/2 O(n)第二章 線性表順序表的運算3.順序表的刪除: 將線性表(n個元素)的第i個數據元素刪除 int SqDelete(S

15、qList * L,int i, elemtype * p) 初始條件:線性表L已存在且非空,1iListLength(L) 操作結果:刪除L的第i個元素,并用*p返回其值,L的長度減1。實現步驟:將第i+1 至第n 位的元素向前移動一個位置;表長減1。 注意:事先需要判斷,刪除位置i 是否合法?第二章 線性表順序表的運算int SqDelete(SqList * L, int i, elemtype *p)/在順序表L中刪除第i個數據元素,*p返回其值 int j,n; n=L-len; if(in) printf(Error!); return (0); *p=L-elemi-1; for

16、(j=i-1;jelemj=L-elemj+1; L-len-; return (1); 23 0 75 1 41 2 38 3 54 4 62 5 17 6L-len=7SqDelete( L, 4, p)第二章 線性表順序表的運算線性表的刪除算法的時間復雜度 刪除算法中,其時間主要消耗在移動數據元素上,數據的移動次數與刪除元素的位置有關所有可能的元素移動次數合計 0+1+n-1 = n(n-1)/2共有多少種刪除形式? 有n種!刪除時的平均移動次數為: n(n-1)/2n (n-1)/2 O(n)第二章 線性表順序存儲結構的優缺點優點邏輯相鄰,物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點

17、插入、刪除操作需要移動大量的元素預先分配空間需按最大空間分配,利用不充分表容量難以擴充順序表第二章 線性表2.3 線性表的鏈式存儲結構 1.單鏈表線性表的鏈式存儲結構簡稱鏈表,其特點為:用一組任意的存儲單元存儲線性表的數據元素利用指針實現了用不相鄰的存儲單元存放邏輯上相鄰的元素數據域 指針域結點每個數據元素,除存儲本身信息外,還需存儲其直接后繼的信息結點數據域:元素本身信息指針域:指示直接后繼的存儲位置第二章 線性表例 線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)19 WANG NULL數據域指針域1 LI 43存儲地址31h頭指針7 QIAN 1313

18、SUN 125 WU 3731 ZHAO 737 ZHENG 1943 ZHOU 25WUZHENGhZHAOQIANSUNLIZHOUWANG2.3 線性表的鏈式存儲結構 第二章 線性表結點:數據元素的存儲映像。由數據域和指針域兩部分組成;鏈表: n 個結點由指針鏈組成一個鏈表。它是線性表的鏈式存儲映像,稱為線性表的鏈式存儲結構,結點只有一個指針域的鏈表,稱為單鏈表或線性鏈表。頭指針:指向鏈表中第一個結點的指針。頭結點:有時候為了操作方便在單鏈表的第一個結點之前添加一個結點,該結點和表中的其他結點結構相同,只是數據域不存放數據,或閑置不用,或存放其他信息。HZHAOQIANSUNLIZHOU

19、WUZHENGWANG2.3 線性表的鏈式存儲結構 第二章 線性表類型定義typedef struct Node elemtype data;struct Node * next; LinkList;LinkList *h, *p;生成一個LinkList型新結點: p=(LinkList *)malloc(sizeof(LinkList);系統回收p結點:free(p)a1a2an h空單鏈表:hp2.3 線性表的鏈式存儲結構 第二章 線性表單鏈表的算法(1)查找 查找單鏈表中是否存在結點x,若有則返回指向x結點的指針;否則返回NULLLinkList *LinkSearch(LinkLis

20、t *h,elemtype x)/ 在單鏈表中查找數據元素值為x的節點 LinkList *p; p=h-next; while( p!=NULL & p-data !=x) p=p-next; return (p);時間復雜度O(n)a1a2Xan hppp(2)取指定位置(第i個)的元素int GetElem(LinkList *h, int i, elemtype * e)/把鏈表h中第i個元素的值存入在指針e的目標變量中 LinkList p; int j; p=h-next; j=1; while( p!=NULL & jnext; j+; if(p=NULL) return 0;

21、*e = p-data; return 1; 單鏈表的算法第二章 線性表a1a2a3a4 hpj=1pj=2pj=3(3)插入 在鏈表(n個元素)的第i (1i n+1)個位置前插入一個元素,成功返回1,否則返回0。 ai-1aisxpai-1aisxp單鏈表的算法第二章 線性表 s=(LinkList *)malloc(sizeof(LinkList); s-data=x; s-next=p- next; p-next=s;int LinkInsert ( LinkList *h, int i, elemtype x ) /把鏈表h中第i個元素之前插入值為x的結點 LinkList *p,*

22、s; int j; p=h; j=0;while(p !=NULL & jnext; j+; if(p=NULL) return 0; / 參數 i不合法,s=(LinkList *)malloc(sizeof(LinkList);s-data=x; / 創建新元素的結點s-next=p- next; p-next=s; / 修改指針,完成插入return 1; 單鏈表的算法第二章 線性表完整算法: int LinkDelete ( LinkList *h, int i, elemtype *s) LinkList *p,*q; int j; p=h; j=0; while (p-next !

23、=NULL & j next; j+; if (p-next=NULL) return 0; / 刪除位置不合理 q = p-next; p-next = q-next;/ 修改指針*s = q-data; free(q);/ 釋放結點空間 return 1; ai-1aipai+1q(4)刪除 將鏈表(n個元素)的第i(1in)個數據元素刪除單鏈表的算法第二章 線性表 void LinkCreate(LinkList *h, int n) /逆序建立帶頭結點的單鏈表。LinkList *p; int i; h-next = NULL;/ 先建立一個帶頭結點的空的單鏈表for (i=n; i

24、0; i -) p=(LinkList *)malloc(sizeof(LinkList); scanf(%d,&p-data) ; / 輸入元素值 p-next = h-next; h-next = p; / 插入在頭結點之后 (5)單鏈表的建立:建立一個含有n個元素的單鏈表單鏈表的算法第二章 線性表例 :設計算法逆置線性表中的元素(單鏈表逆置)a1a2an hanan-1a1 hvoid reverse(LinkList *h) LinkList *p,*q; p=h-next; h-next=NULL; while(p!=NULL) q=p-next; p-next=h-next; h-

25、next=p; p=q; void reverse(LinkList *h) /無頭結點 LinkList *p,*q; if(h!=NULL&h-next!=NULL) p=h-next; h-next=NULL; while(p!=NULL) q=p-next; p-next=h; h=p; p=q; 單鏈表的算法第二章 線性表pq第二章 線性表有時候為了方便操作,將鏈表的最后一個結點的指針域改為指向鏈表的頭結點或第一個節點,使得鏈表構成一個環,成為循環鏈表。ha1a2anh空循環單鏈表:2.3 線性表的鏈式存儲結構 2.循環鏈表第二章 線性表循環單鏈表的查找運算(查找值為x的結點)Lin

26、kList *LLinkSearch(LinkList *h, elemtype x)/ 在循環單鏈表中查找數據元素值為x的結點 LinkList *p; p=h-next; while( p!=h & p-data !=x) p=p-next; if(p!=h) return p; else return NULL;2.3 線性表的鏈式存儲結構 3.雙向鏈表:每個結點增加一個指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個方向不同的鏈,故稱為雙向鏈表。前驅指針數據域后繼指針typedef struct DuNode elemtype data; struct DuNode * pr

27、ior,* next; DuLinkList;hh 和單鏈表類似,雙鏈表一般也帶頭結點,從而使某些運算變得方便,將頭結點和尾結點鏈接起來也能構成雙向循環鏈表。第二章 線性表2.3 線性表的鏈式存儲結構 雙向鏈表的對稱性:設指針p指向某一結點,則雙向鏈表結構的對稱性可用下式描述: (p-prior)-next = p =(p-next)-prioraiai-1Pxs雙向鏈表運算(1)插入第二章 線性表s-prior=p-prior p-prior-next=ss-next=p p-prior=s注意次序2.3 線性表的鏈式存儲結構 int DuLinkInsert ( DuLinkList *h

28、, int i, elemtype x )/在雙向循環鏈表h中第i個數據元素之前插入一個數據元素x DuLinkList *p,*s; int j;p=h-next; j=1;while(p !=h & jnext; j+; if(p=h) return 0; / 參數不合法s=(DuLinkList *)malloc(sizeof(DuLinkList);s-data=x; / 創建新元素的結點 s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; / 修改指針 return 1;第二章 線性表2.3 線性表的鏈式存儲結構 雙向鏈表的刪除

29、aiai+1ai-1Pp-next-prior=p-prior;p-prior-next=p-next;第二章 線性表2.3 線性表的鏈式存儲結構 int DuLinkDelete ( DuLinkList *h, int i, elemtype *s) /在雙向循環鏈表L中刪除第i個數據元素DuLinkList *p; int j;p=h-next; j=1;while(p !=h & jnext; j+; if(p=h)return 0; p-prior-next=p-next; p-next-prior=p-prior; / 修改指針*s = p-data; free(p);/ 釋放結點

30、空間 return 1;第二章 線性表2.3 線性表的鏈式存儲結構 第二章 線性表4.靜態鏈表:利用一維數組實現的鏈表a1a2a3a4 h數據域指針域下標10a121a232a343a4-145hav數據域指針域下標10a121a252a343a4-14x356hav2.3 線性表的鏈式存儲結構 順序表:相鄰數據元素的存放地址也相鄰(邏輯與物理統一;要求內存中可用存儲單元的地址必須是連續的。優點:存儲密度大,存儲空間利用率高,可以實現隨機存取。缺點:插入或刪除元素時不方便。鏈表:相鄰數據元素可隨意存放,但所占存儲空間分兩部分,一部分存放結點值,另一部分存放表示結點間關系的指針優點:插入或刪除元

31、素時很方便,使用靈活。缺點:存儲密度?。╰op = 0; 進棧 int push (SqStack * s, elemtype x)/ 若棧的存儲空間不滿,則插入 元素 x 為新的棧頂元素 if (s-top = maxnum) / 棧已滿,無法插入 return 0;s-stacks-top = x; / 插入新的元素s-top +; / 棧頂指針后移return 1;3.1 棧(Stack)(2)順序棧的操作 出棧int pop (SqStack * s, elemtype * p) / 若棧不空,則刪除s的棧頂元素,用 *p 返回其值 if (s-top = 0) return 0; s

32、-top -; / 棧頂指針前移 *p = s-stacks-top; / 返回棧頂元素 return 1; 取棧頂元素int GetTop (SqStack * s, elemtype * e) / 若棧不空,則用 *e 返回s的棧頂元素if (s-top = 0) return 0;*e = s-stacks-top-1; / 返回棧頂元素return 1; 3.1 棧(Stack) 判斷棧是否為空 int StackEmpty (SqStack * s) /判斷順序棧S是否為空棧 if (s-top = 0) return 1; else return 0; M-105 6 7 94 8

33、 45 56 23 11top0top13.1 棧(Stack)(3)共享棧#define M 500 typedef struct elemtype stackM;int top2;DuStack;(1)類型描述.topbottom兩棧共享的數據結構描述typedef struct Node elemtype data; struct Node * next;LinkStack;LinkStack * top;3.1 棧(Stack)3.棧的鏈式存儲結構int LPush(LinkStack * top,elemtype x)/把數據元素x插入到鏈棧的頂部 LinkStack * p; p=

34、(LinkStack *) malloc (sizeof(LinkStack); if(p=null) printf(overflow!); return(0); p-data = x; p-next = top-next; top-next = p; return 1;3.1 棧(Stack)(2)鏈棧操作int LPop(LinkStack * top,elemtype * p)/棧頂數據元素出棧,并用*p保存其值 LinkStack * q; q=top-next; if(q=null) printf(stack empty!); return(0); top-next = q-next

35、; *p = q-data; free(q); return 1;3.1 棧(Stack)(2)鏈棧操作(1)數制轉換 十進制N和其它進制數的轉換是計算機實現計算的基本問題,其解決方法很多,其中一個簡單算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div為整除運算,mod為求余運算) 例如 (1348)10=(2504)8,其運算過程如下: n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 24.棧的應用3.1 棧(Stack)算法描述: void conversion( int n ) initstack(s); w

36、hile(n!=0) push(s,n%8); n=n/8; while(! StackEmpty(s) pop(s,e); printf(“%d”,e); 3.1 棧(Stack)(2)括號匹配的檢驗 假設表達式中允許包含兩種括號:圓括號和方括號,則( ()或( )等為正確的匹配,( )或( ( )或 ( ( ) ) )均為錯誤的匹配。每一個出現的左括號都要等待與之匹配的右括號的的出現;如果有多個左括號在等待,則這些左括號要排成一隊,且為逆序的(最后的左括號期待急迫程度最高)。每一個出現的右括號,都要有以之匹配的左括號在等待,而且這個左括號排在第一位。什么樣的情況是“不匹配”的情況呢?來的右

37、括號非所“期待”的;來的是“不速之客”;直到結束,也沒有到來所期待的。 3.1 棧(Stack) 任何一個表達式都是由操作數(operand)、運算符(operator)和界限符(delimiter)組成。 (3)表達式的求值表達式 = 操作數 運算符 操作數 在計算機中,對這種二元表達式可以有三種不同的標識方法。假設 Exp = S1 + OP + S2則稱 OP + S1 + S2 為表達式的前綴表示法(簡稱前綴式)稱 S1 + OP + S2 為表達式的中綴表示法(簡稱中綴式)稱 S1 + S2 + OP 為表達式的后綴表示法(簡稱后綴式)基本思想為:如果來的是左括號,則入棧。如果來的是

38、右括號,則判斷棧是否為空,如果棧不空判斷是否匹配;最后,棧應該為空。 3.1 棧(Stack)綜合比較可得下列結論: 三式中的操作數之間的相對次序相同,運算符的相對次序不同”; 中綴式丟失了括弧信息,致使運算的次序不確定; 前綴式的運算規則為:連續出現的兩個操作數和在它們之前且緊靠它們的運算符構成一個最小表達式; 后綴式的運算規則為:每個運算符和之前緊靠它的兩個操作數構成一個最小表達式;表達式不需要使用括號運算符在式中出現的順序恰為表達式的運算順序若 Exp=ab +(c-d/e) f 則: 前綴式為:+a b- c/ d e f 中綴式為:ab + c d / e f 后綴式為:a bc d

39、 e /- f +3.1 棧(Stack) 運算過程為:對后綴式從左向右掃描,遇見操作數則暫時保存,遇見運算符即可進行運算;此時參加運算的兩個操作數應該是在它之前剛剛碰到的兩個操作數,并且先出現的是第一操作數,后出現的是第二操作數。由此可見,在運算過程中保存操作數的結構應該是個棧。 基本思想為:設置一個棧,從左到右掃描后綴表達式。每讀到一個操作數,就將其入棧;每讀到一個運算符,就從棧頂取出兩個操作數,完成此操作符的運算,并將計算結果作為一個新的操作數入棧。一直到整個表達式掃描完,最后位于棧頂位置的元素值就是該表達式的值。如何從后綴表達式求值?3.1 棧(Stack) 如何由原表達式轉換成后綴式

40、? 原表達式和后綴式兩者中運算符出現的次序有什么不同。 例1 原式:a*b/c*d-e+f 后綴式:ab*c/d*e-f+例2 原式:a+b*c-d/e*f 后綴式:abc*+de/f*-為此,引入運算符的“優先數”的概念 運算符: # ( + - * / * 優先數: -1 0 1 1 2 2 3 對原表達式中出現的每一個運算符是否即刻進行運算取決于在它后面出現的運算符,如果它的優先數“高或等于”后面的運算,則它的運算先進行,否則就得等待在它之后出現的所有優先數高于它的“運算”都完成之后再進行。 3.1 棧(Stack)1) 設立運算符棧;2) 設表達式的結束符為#,預設運算符棧的棧底為#;

41、3) 若當前字符是操作數,則直接發送給后綴式;4) 若當前字符為運算符且優先數大于棧頂運算符,則進棧,否則退出棧頂運算符發送給后綴式;5) 若當前字符是結束符,則自棧頂至棧底依次將棧中所有運算符發送給后綴式;6) (對它之前后的運算符起隔離作用,則若當前運算符為(時進棧;7) )可視為自相應左括弧開始的表達式的結束符,則從棧頂起,依次退出棧頂運算符發送給后綴式直至棧頂字符為(止。 3.1 棧(Stack) void transform(char exp ) / 從合法的表達式exp求后綴式InitStack(S); push(S, # ); p = exp; ch = *p;while (!S

42、tackEmpty(S) if (!IN(ch, OP) printf(%c,ch);else switch (ch) case ( : push(S, ch); break; case ) : pop(S, c); while (c!= ( ) printf(%c,c); Pop(S, c) break; defult :c=Gettop(s); while( precede(c,ch) ) printf(%c,c); Pop(S, c); if ( ch!= # ) Push( S, ch); break; / elseif ( ch!= # ) p+; ch = *p; / while

43、/ transform 若c的優先數大于或等于ch,precede(c,ch)值為true3.1 棧(Stack)(4)函數的嵌套調用 當一個函數在運行期間調用另一個函數時,在運行該被調用函數之前,需先完成三件事:1) 將所有的實在參數、返回地址等信息傳遞給被調用函數保存;2) 為被調用函數的局部變量分配存儲區;3) 將控制轉移到被調用函數的入口。而從被調用函數返回調用函數之前,應該完成:1) 保存被調函數的計算結果;2) 釋放被調函數的數據區;3) 依照被調函數保存的返回地址將控制轉移到調用函數。當多個函數嵌套調用時,由于函數的運行規則是:后調用先返回,因此各函數占有的存儲管理應實行棧式管理

44、。3.1 棧(Stack) 一個遞歸函數的運行過程類似于多個函數的嵌套調用,差別僅在于“調用函數和被調用函數是同一個函數”。 為了保證“每一層的遞歸調用”都是對“本層”的數據進行操作,在執行遞歸函數的過程中需要一個“遞歸工作?!?。作用:將遞歸調用時的實在參數和函數返回地址傳遞給下一層執行的遞歸函數;保存本層的參數和局部變量,以便從下一層返回時重新使用它們 遞歸過程執行過程中所占用的數據區,稱之為遞歸工作棧。 每一層的遞歸參數等數據合成一個記錄,稱之為遞歸工作記錄。 棧頂記錄指示當前層的執行情況,稱之為當前活動記錄。(5)遞歸的實現3.1 棧(Stack)1、隊列的定義及常用操作 定義:限定只能

45、在表的一端進行插入,在表的另一端進行刪除的線性表。 允許插入的一端稱為隊尾(rear),允許刪除的一端稱為隊頭(front)。在隊尾進行插入操作稱為入隊,在隊頭進行刪除操作稱為出隊。特點:先進先出(First In First Out,LIFO)。3.2 隊列(Queue) 3.2 隊列(Queue) 常用操作: (1)隊列的初始化:初始化一個空隊列。 (2)入隊:向隊列中插入一個新的隊尾元素。 (3)出隊:刪除隊列的隊頭元素。 (4)求隊長:計算隊列中元素的個數。 (5)判隊空:如果隊列為空返回真值,否則返回假值。 (6)判隊滿:如果隊列為滿返回真值,否則返回假值。2、隊列的順序存儲結構(1

46、)類型描述typedef struct elemtype queuemaxnum; int front,rear;SqQueue;3.2 隊列(Queue) 初始化建空隊列時,令 front=rear=0,每當插入一個新的隊尾元素后,尾指針rear增1;每當刪除一個隊頭元素之后,頭指針 front增1。因此,在非空隊列中,頭指針始終指向隊頭元素,而尾指針指向隊尾元素的下一個位置。 設想這個數組的存儲空間是個“環”,認定“7”的下一個位置是“0”,我們稱為循環隊列。 什么時候隊列為空?什么時候隊列為滿?front=rear(rear+1)%maxnum=front隊列的長度為多少?(rear-f

47、ront+maxnum)%maxnum3.2 隊列(Queue) typedef struct Node elemtype data; struct Node * next;QNode;typedef struct QNode * front; QNode * rear;LinkQueue;3.2 隊列(Queue) 3、隊列的鏈式存儲結構int InitQueue(LinkQueue * q)/構造一個空隊列q q-front=q-rear=(QNode * )malloc(sizeof(QNode); if(q-front=NULL) printf(Over flow!); return(

48、0); q-front-next=NULL; return 1;鏈隊列初始化3.2 隊列(Queue) 入隊int EnLQue(LinkQueue * q,elemtype x)/數據元素x插入鏈隊q中成為新的隊尾元素QNode * p;p=(QNode * )malloc(sizeof(QNode);if(p=NULL) printf(Over flow!); return(0);p-data=x;p-next=NULL;q-rear-next=p; / 修改尾結點的指針q-rear=p; / 移動隊尾指針return(1);3.2 隊列(Queue) 出隊int DeLQue(LinkQ

49、ueue * q, elemtype * p) / 若隊列不空,則刪除當前隊列q中的頭元素,用p返回其值Qnode *s; if (q-front = q-rear ) / 鏈隊列為空 return 0; s = q-front-next; * p = s-data;/ 返回被刪元素q-front-next = s-next; / 修改頭結點指針if(q-rear = s) q-rear = q-front; free(s);/ 釋放被刪結點return 1; 3.2 隊列(Queue) 3.2 隊列(Queue) 4、隊列的應用(1)輸入/輸出緩沖區問題 操作系統解決主機與外部設備之間速度的

50、不匹配問題,要借用緩沖區來實現。緩沖區一般采用先進先出的原則進行,可采用隊列實現。(2)計算機資源競爭問題 多終端計算機系統中,多個用戶向操作系統提出占用CPU的申請,操作系統按其請求時間先后排成隊列,每次把CPU分配給隊首的用戶。 第四章 串第四章 串本章內容 1. 串的定義及常用操作 2. 串的存儲結構 3. 串的模式匹配 4. 串的應用本章重點、難點 串類型的定義和存儲結構學習要點1、了解串的概念;2、熟悉串的基本運算的定義;3、熟練掌握串的基本算法。4.1 串的定義及常用操作一、定義及相關術語 1.串 零個或多個字符組成的有限序列。 一般記為:S=“a1a2.an” 其中,S是串名,引

51、號括起的字符序列是串值;串中所包含的字符個數稱為串的長度。 2.空串長度為零的串,它不包含任何字符。 3.空格串由一個或多個空格組成的串 4.子串串中任意個連續的字符組成的子序列。 5.主串包含子串的串 6.字符在串中的位置字符在序列中的序號 7.子串在主串中的位置子串在主串中第一次出現時,子串的第一個字符在主串中的位置。8.兩個串相等 兩個串的長度相等,并且各個對應位置的字符都相等時才相等。二、串的常用操作1.串變量賦值 :有一個串的常量或串變量為另一串變量賦值 2.判斷兩個串是否相等:若相等返回真值,否則返回假值3.連接兩個串:將第二個串接到第一個串的末尾4.求串長:統計字符串的字符的個數

52、5.求子串:在個主串中求從指定位置開始的指定長度的子串6.子串的定位:求指定子串在主串中第一次出現的位置7.子串的替換:在主串中用把一個子串替換為另一子串8.串的插入:在字符串的指定位置插入字符串9.串的刪除:從字符串的指定位置開始刪除連續基于個字符4.1 串的定義及常用操作一、串的順序存儲結構4.2 串的存儲結構#define maxlen 100 /定義字符串的最大長度typedef struct char datamaxlen+1; /多一個元素存儲結束標志0 int len;SeqString; 常用運算:(1)串連接 concat (s1, s2)把串 s2 連接在串s1的后面,形成

53、新串。兩種方法:定長一維數組實現和動態內存分配 1. 串的定長順序存儲結構SeqString * concat(SeqString * s1, SeqString *s2) int i,j; SeqString *t; t=(SeqString *)malloc(sizeof(SeqString); for(i=0; ilen; i+) t-datai = s1-datai; if(s1-len+s2-len= maxlen) for(j=0; jlen; j+) t-data i+=s2-dataj; t-len=s1-len+s2-len; else for( j=0; idatai=s2

54、-dataj; t-datamaxlen=0; t-len=maxlen; return(t);4.2 串的存儲結構(2)求子串 substring (s, pos, len)求串s的第 pos 個字符起長度為 len 的子串。SeqString * substring (SeqString *s, int pos, int len ) SeqString *t; int i;if (poss-len|lens-len-pos+1) return NULL;t=(SeqString *)malloc(sizeof(SeqString); for ( i = 0; i data i = s-da

55、ta pos + i - 1 ; t-data len =0; t-len=len; return t;4.2 串的存儲結構(3)子串的插入 StrInsert(s, pos, t ) 在串 s 的第 pos 個字符之前插入串 t。int StrInsert(SeqString * s, int pos, SeqString * t ) int i; if(t-len=0) printf(“空串!n”); return 0 ; if(poss-len+1) printf(“位置錯!”);return 0; if(s-len+t-lenmaxlen) printf(“溢出!”);return 0

56、; for(i=s-len; i=pos-1; i-) s-datai+ t-len=s-datai; for(i=0;ilen;i+) s-datapos-1+i=t-datai; s-len = s-len+ t-len return 1;4.2 串的存儲結構4.2 串的存儲結構typedef struct char *ch; /存儲字符串的首地址 int len;String; 常用運算:(1)串連接 concat (s1, s2)為新串t分配大小s1和s2長度之和的空間,然后依次復制s1和 s2的內容。2. 串的動態順序存儲結構 仍以一組地址連續的存儲單元存儲串值,只是在程序執行過程中

57、動態分配存儲空間。String concat(String s1, String s2) int i,j; String t; t.ch=(char *)malloc(s1.len+s2.len+1)*sizeof(char); /多定義一個空間存儲字符串結束標志 for(i=0; is1.len; i+) t.chi = s1.chi; for(j=0; j=pos-1; i-) s.chi+ t.len=s.chi; for(i=0; ilen=0 ) printf(“匹配串為空!”); return 0; if(poss-len) printf(“位置錯!”); return 0; i=

58、pos; j=1; while (ilen & jlen) if (s-datai=t-dataj) +i; +j; else i=i-j+2; j=1; /重新開始匹配 if (jt-len) return (i-t-len) ; else return 0; 算法實現:4.3 串的模式匹配4.4 串操作的應用 文本編輯 文本編輯程序是一個面向用戶的系統服務程序,廣泛應用于源程序的輸入和修改。其實質是修改字符數據的形式或格式,其基本操作包括串的查找,插入和刪除等基本功能。 可將文本劃分為若干頁,每頁又有若干行。具體操作中可將文本看作字符串,稱為文本串。頁是文本串的子串,行又是頁的子串。先為文

59、本串建立相應的頁表和行表,即建立各子串的存儲映象。 頁表給出頁號和該頁的起始行號. 行表則指示每一行的行號、起始地址和該行子串的長度。為查找方便,行表是按行號遞增順序存儲的。然后需在文本編輯程序中設立頁指針、行指針和字符指針,分別指示當前操作的頁、行和字符。從而實現基本操作。第五章 數組和廣義表第五章 數組和廣義表本章內容 1.數組 2.矩陣的壓縮存儲 3.廣義表本章重點、難點 數組的存儲、特殊矩陣的壓縮存儲、廣義表5.1 數組1.數組的定義及常用操作 數組是由n(n1)個相同類型的數據元素a0,a1,an-1構成的有限序列 。其數組元素可以是基本數據類型,可以是復雜數據類型。當數組元素也是數

60、組時,一維數組擴充為二維數組(矩陣)。 二維數組同樣滿足數組的定義。一個二維數組可以被看成是特殊的一維數組,其中,每個元素又是一個一維數組。多維數組可以按同樣的方法類推。常用操作:取值操作:給定一組下標,讀其對應的數據元素 ;賦值操作:給定一組下標,存儲或修改與其相對應的數據元素;2.數組的順序存儲結構及基本運算 5.1 數組 多維數組,通常有兩種映象方法:即“以行(序)為主(序)”的映象方法和“以列(序)為主(序)”的映象方法。a0,2a0,1a0,0a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2La0,1a1,0a0,0a1,1a0,2a1,2L對于mn二維數組(

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論