數(shù)據(jù)結(jié)構(gòu)ppt課件完整版

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

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

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

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

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

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

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

8、個輸入，也可以沒有輸入（隱含輸入） 5、輸出：一個算法可以有一個或多個輸出1.3 算法及算法分析1、正確性，首先要滿足算法需求，其次對算法的“正確性”的理解有以下四個層次：2、易讀性，一個好的算法主要是與他人交流共享，晦澀難懂的算法不利于交流、調(diào)試、維護。3、健壯性，對于非法數(shù)據(jù)能夠給出合理反應(yīng)4、高效性，主要有兩方面，運行時間和占用空間，即時間復(fù)雜度和空間復(fù)雜度此外，還要考慮算法的可維護性。二、算法的設(shè)計要求程序不含語法錯誤對于隨意的幾組合法數(shù)據(jù)輸入能夠得出符合要求的結(jié)構(gòu)對于精心設(shè)計的典型、有刁難性的合法數(shù)據(jù)能夠得出符合要求的結(jié)果程序?qū)λ械暮戏ǖ妮斎霐?shù)據(jù)都能得出符合要求的結(jié)果1.3 算法及

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

10、行時間之和。每條語句執(zhí)行時間 = 該語句的執(zhí)行次數(shù)（頻度）* 語句執(zhí)行一次所需時間。語句執(zhí)行一次所需時間取決于機器的指令性能和速度和編譯所產(chǎn)生的代碼質(zhì)量，很難確定。設(shè)每條語句執(zhí)行一次所需時間為單位時間，則一個算法的運行時間就是該算法中所有語句的頻度之和。例: for (i = 0; i n; i+ ) n+1 for ( j = 0; j y) x=5; else x=10; T(n)=O(1)算法的時間復(fù)雜度(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語言實現(xiàn)#define maxlen 1000typedef int elemtype; elemtype elemmaxlen; int len; typedef struct SqList; SqList *L,*p;順序表的運算1.順序表的查找 對于給定的數(shù)據(jù)元素，找出其在線性表中的位置int SqSearch(SqList * L, elemtype x)/在順序表L中查找數(shù)據(jù)元素x在表中第一次

12、出現(xiàn)的位置 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第二章 線性表時間復(fù)雜度：O（n）如按序號查找： O（1）順序表的運算2.順序表的插入 在線性表（n個元素）的第i個位置前插入一個元素 int SqInsert(SqList * L, elemtype x,int i ) 初始條件：線性表L已存在， 1in+1 操作結(jié)果：在L的第i個元素之前插入新的元素x，L的長度增1。實現(xiàn)步驟：將第n至第i

13、位的元素向后移動一個位置；將要插入的元素寫到第i個位置；表長加1。注意：事先應(yīng)判斷: 插入位置i 是否合法?表是否已滿?第二章 線性表第二章 線性表順序表的運算int SqInsert(SqList * L, elemtype x, int i)/在順序表L的第i個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素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)第二章 線性表順序表的運算線性表的插入算法的時間復(fù)雜度 插入算法中，其時間主要消耗在移動數(shù)據(jù)元素上，數(shù)據(jù)的移動次數(shù)與插入元素的位置有關(guān)(討論等概率)。所有可能的元素移動次數(shù)合計： 0+1+n = n(n+1)/2共有多少種插入形式? 連頭帶尾有n+1種!故插入時的平均移動次數(shù)為： n(n+1)/2（n+1） n/2 O(n)第二章 線性表順序表的運算3.順序表的刪除： 將線性表（n個元素）的第i個數(shù)據(jù)元素刪除 int SqDelete(S

15、qList * L,int i, elemtype * p) 初始條件：線性表L已存在且非空，1iListLength(L) 操作結(jié)果：刪除L的第i個元素，并用*p返回其值，L的長度減1。實現(xiàn)步驟：將第i+1 至第n 位的元素向前移動一個位置；表長減1。 注意：事先需要判斷，刪除位置i 是否合法?第二章 線性表順序表的運算int SqDelete(SqList * L, int i, elemtype *p)/在順序表L中刪除第i個數(shù)據(jù)元素，*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)第二章 線性表順序表的運算線性表的刪除算法的時間復(fù)雜度 刪除算法中，其時間主要消耗在移動數(shù)據(jù)元素上，數(shù)據(jù)的移動次數(shù)與刪除元素的位置有關(guān)所有可能的元素移動次數(shù)合計 0+1+n-1 = n(n-1)/2共有多少種刪除形式? 有n種!刪除時的平均移動次數(shù)為： n(n-1)/2n （n-1）/2 O(n)第二章 線性表順序存儲結(jié)構(gòu)的優(yōu)缺點優(yōu)點邏輯相鄰，物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點

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

18、SUN 125 WU 3731 ZHAO 737 ZHENG 1943 ZHOU 25WUZHENGhZHAOQIANSUNLIZHOUWANG2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 第二章 線性表結(jié)點：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成；鏈表： n 個結(jié)點由指針鏈組成一個鏈表。它是線性表的鏈?zhǔn)酱鎯τ诚?，稱為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu),結(jié)點只有一個指針域的鏈表，稱為單鏈表或線性鏈表。頭指針：指向鏈表中第一個結(jié)點的指針。頭結(jié)點：有時候為了操作方便在單鏈表的第一個結(jié)點之前添加一個結(jié)點，該結(jié)點和表中的其他結(jié)點結(jié)構(gòu)相同，只是數(shù)據(jù)域不存放數(shù)據(jù)，或閑置不用，或存放其他信息。HZHAOQIANSUNLIZHOU

19、WUZHENGWANG2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 第二章 線性表類型定義typedef struct Node elemtype data;struct Node * next; LinkList;LinkList *h, *p;生成一個LinkList型新結(jié)點： p=(LinkList *)malloc(sizeof(LinkList);系統(tǒng)回收p結(jié)點：free(p)a1a2an h空單鏈表：hp2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 第二章 線性表單鏈表的算法(1)查找 查找單鏈表中是否存在結(jié)點x，若有則返回指向x結(jié)點的指針；否則返回NULLLinkList *LinkSearch(LinkLis

20、t *h,elemtype x)/ 在單鏈表中查找數(shù)據(jù)元素值為x的節(jié)點 LinkList *p; p=h-next; while( p!=NULL & p-data !=x) p=p-next; return (p);時間復(fù)雜度O（n）a1a2Xan hppp(2)取指定位置（第i個）的元素int GetElem(LinkList *h, int i, elemtype * e)/把鏈表h中第i個元素的值存入在指針e的目標(biāo)變量中 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的結(jié)點 LinkList *p,*

22、s; int j; p=h; j=0;while(p !=NULL & jnext; j+; if(p=NULL) return 0; / 參數(shù) i不合法，s=(LinkList *)malloc(sizeof(LinkList);s-data=x; / 創(chuàng)建新元素的結(jié)點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);/ 釋放結(jié)點空間 return 1; ai-1aipai+1q(4)刪除 將鏈表（n個元素）的第i（1in）個數(shù)據(jù)元素刪除單鏈表的算法第二章 線性表 void LinkCreate(LinkList *h, int n) /逆序建立帶頭結(jié)點的單鏈表。LinkList *p; int i; h-next = NULL;/ 先建立一個帶頭結(jié)點的空的單鏈表for (i=n; i

24、0; i -) p=(LinkList *)malloc(sizeof(LinkList); scanf(%d,&p-data) ; / 輸入元素值 p-next = h-next; h-next = p; / 插入在頭結(jié)點之后 (5)單鏈表的建立：建立一個含有n個元素的單鏈表單鏈表的算法第二章 線性表例 ：設(shè)計算法逆置線性表中的元素（單鏈表逆置）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) /無頭結(jié)點 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第二章 線性表有時候為了方便操作，將鏈表的最后一個結(jié)點的指針域改為指向鏈表的頭結(jié)點或第一個節(jié)點，使得鏈表構(gòu)成一個環(huán)，成為循環(huán)鏈表。ha1a2anh空循環(huán)單鏈表：2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 2.循環(huán)鏈表第二章 線性表循環(huán)單鏈表的查找運算（查找值為x的結(jié)點）Lin

26、kList *LLinkSearch(LinkList *h, elemtype x)/ 在循環(huán)單鏈表中查找數(shù)據(jù)元素值為x的結(jié)點 LinkList *p; p=h-next; while( p!=h & p-data !=x) p=p-next; if(p!=h) return p; else return NULL;2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 3.雙向鏈表:每個結(jié)點增加一個指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。前驅(qū)指針數(shù)據(jù)域后繼指針typedef struct DuNode elemtype data; struct DuNode * pr

27、ior,* next; DuLinkList;hh 和單鏈表類似，雙鏈表一般也帶頭結(jié)點，從而使某些運算變得方便，將頭結(jié)點和尾結(jié)點鏈接起來也能構(gòu)成雙向循環(huán)鏈表。第二章 線性表2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 雙向鏈表的對稱性：設(shè)指針p指向某一結(jié)點，則雙向鏈表結(jié)構(gòu)的對稱性可用下式描述： (p-prior)-next = p =(p-next)-prioraiai-1Pxs雙向鏈表運算（1）插入第二章 線性表s-prior=p-prior p-prior-next=ss-next=p p-prior=s注意次序2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) int DuLinkInsert ( DuLinkList *h

28、, int i, elemtype x )/在雙向循環(huán)鏈表h中第i個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素x DuLinkList *p,*s; int j;p=h-next; j=1;while(p !=h & jnext; j+; if(p=h) return 0; / 參數(shù)不合法s=(DuLinkList *)malloc(sizeof(DuLinkList);s-data=x; / 創(chuàng)建新元素的結(jié)點 s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; / 修改指針 return 1;第二章 線性表2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 雙向鏈表的刪除

29、aiai+1ai-1Pp-next-prior=p-prior;p-prior-next=p-next;第二章 線性表2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) int DuLinkDelete ( DuLinkList *h, int i, elemtype *s) /在雙向循環(huán)鏈表L中刪除第i個數(shù)據(jù)元素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);/ 釋放結(jié)點

30、空間 return 1;第二章 線性表2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 第二章 線性表4.靜態(tài)鏈表：利用一維數(shù)組實現(xiàn)的鏈表a1a2a3a4 h數(shù)據(jù)域指針域下標(biāo)10a121a232a343a4-145hav數(shù)據(jù)域指針域下標(biāo)10a121a252a343a4-14x356hav2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 順序表：相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點：存儲密度大，存儲空間利用率高,可以實現(xiàn)隨機存取。缺點：插入或刪除元素時不方便。鏈表：相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針優(yōu)點：插入或刪除元

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兩棧共享的數(shù)據(jù)結(jié)構(gòu)描述typedef struct Node elemtype data; struct Node * next;LinkStack;LinkStack * top;3.1 棧（Stack）3.棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)int LPush(LinkStack * top,elemtype x)/把數(shù)據(jù)元素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)/棧頂數(shù)據(jù)元素出棧，并用*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）數(shù)制轉(zhuǎn)換 十進制N和其它進制數(shù)的轉(zhuǎn)換是計算機實現(xià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.棧的應(yīng)用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）括號匹配的檢驗 假設(shè)表達式中允許包含兩種括號：圓括號和方括號，則（ （）或（ ）等為正確的匹配，（ ）或（ （ ）或 ( ( ) ) ）均為錯誤的匹配。每一個出現(xiàn)的左括號都要等待與之匹配的右括號的的出現(xiàn);如果有多個左括號在等待，則這些左括號要排成一隊，且為逆序的（最后的左括號期待急迫程度最高）。每一個出現(xiàn)的右括號，都要有以之匹配的左括號在等待，而且這個左括號排在第一位。什么樣的情況是“不匹配”的情況呢？來的右

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

38、右括號，則判斷棧是否為空，如果棧不空判斷是否匹配；最后，棧應(yīng)該為空。 3.1 棧（Stack）綜合比較可得下列結(jié)論： 三式中的操作數(shù)之間的相對次序相同,運算符的相對次序不同”； 中綴式丟失了括弧信息，致使運算的次序不確定； 前綴式的運算規(guī)則為：連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運算符構(gòu)成一個最小表達式； 后綴式的運算規(guī)則為：每個運算符和之前緊靠它的兩個操作數(shù)構(gòu)成一個最小表達式；表達式不需要使用括號運算符在式中出現(xiàn)的順序恰為表達式的運算順序若 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） 運算過程為：對后綴式從左向右掃描，遇見操作數(shù)則暫時保存，遇見運算符即可進行運算；此時參加運算的兩個操作數(shù)應(yīng)該是在它之前剛剛碰到的兩個操作數(shù)，并且先出現(xiàn)的是第一操作數(shù)，后出現(xiàn)的是第二操作數(shù)。由此可見，在運算過程中保存操作數(shù)的結(jié)構(gòu)應(yīng)該是個棧。 基本思想為：設(shè)置一個棧，從左到右掃描后綴表達式。每讀到一個操作數(shù)，就將其入棧；每讀到一個運算符，就從棧頂取出兩個操作數(shù)，完成此操作符的運算，并將計算結(jié)果作為一個新的操作數(shù)入棧。一直到整個表達式掃描完，最后位于棧頂位置的元素值就是該表達式的值。如何從后綴表達式求值？3.1 棧（Stack） 如何由原表達式轉(zhuǎn)換成后綴式

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

41、3) 若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式；4) 若當(dāng)前字符為運算符且優(yōu)先數(shù)大于棧頂運算符，則進棧，否則退出棧頂運算符發(fā)送給后綴式；5) 若當(dāng)前字符是結(jié)束符，則自棧頂至棧底依次將棧中所有運算符發(fā)送給后綴式；6) (對它之前后的運算符起隔離作用，則若當(dāng)前運算符為(時進棧；7) )可視為自相應(yīng)左括弧開始的表達式的結(jié)束符，則從棧頂起，依次退出棧頂運算符發(fā)送給后綴式直至棧頂字符為(止。 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的優(yōu)先數(shù)大于或等于ch,precede(c,ch)值為true3.1 棧（Stack）（4）函數(shù)的嵌套調(diào)用 當(dāng)一個函數(shù)在運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，需先完成三件事：1) 將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；2) 為被調(diào)用函數(shù)的局部變量分配存儲區(qū)；3) 將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成：1) 保存被調(diào)函數(shù)的計算結(jié)果；2) 釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)；3) 依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。當(dāng)多個函數(shù)嵌套調(diào)用時，由于函數(shù)的運行規(guī)則是：后調(diào)用先返回，因此各函數(shù)占有的存儲管理應(yīng)實行棧式管理

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

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

46、）類型描述typedef struct elemtype queuemaxnum; int front,rear;SqQueue;3.2 隊列（Queue） 初始化建空隊列時，令 front=rear=0，每當(dāng)插入一個新的隊尾元素后，尾指針rear增1；每當(dāng)刪除一個隊頭元素之后，頭指針 front增1。因此，在非空隊列中，頭指針始終指向隊頭元素，而尾指針指向隊尾元素的下一個位置。 設(shè)想這個數(shù)組的存儲空間是個“環(huán)”，認定“7”的下一個位置是“0”，我們稱為循環(huán)隊列。 什么時候隊列為空？什么時候隊列為滿？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、隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)int InitQueue(LinkQueue * q)/構(gòu)造一個空隊列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)/數(shù)據(jù)元素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; / 修改尾結(jié)點的指針q-rear=p; / 移動隊尾指針return(1);3.2 隊列（Queue） 出隊int DeLQue(LinkQ

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

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

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

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

53、新串。兩種方法：定長一維數(shù)組實現(xiàn)和動態(tài)內(nèi)存分配 1. 串的定長順序存儲結(jié)構(gòu)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 串的存儲結(jié)構(gòu)（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 串的存儲結(jié)構(gòu)（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 串的存儲結(jié)構(gòu)4.2 串的存儲結(jié)構(gòu)typedef struct char *ch; /存儲字符串的首地址 int len;String; 常用運算：（1）串連接 concat (s1, s2)為新串t分配大小s1和s2長度之和的空間，然后依次復(fù)制s1和 s2的內(nèi)容。2. 串的動態(tài)順序存儲結(jié)構(gòu) 仍以一組地址連續(xù)的存儲單元存儲串值，只是在程序執(zhí)行過程中

57、動態(tài)分配存儲空間。String concat(String s1, String s2) int i,j; String t; t.ch=(char *)malloc(s1.len+s2.len+1)*sizeof(char); /多定義一個空間存儲字符串結(jié)束標(biāo)志 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; 算法實現(xiàn)：4.3 串的模式匹配4.4 串操作的應(yīng)用 文本編輯 文本編輯程序是一個面向用戶的系統(tǒng)服務(wù)程序，廣泛應(yīng)用于源程序的輸入和修改。其實質(zhì)是修改字符數(shù)據(jù)的形式或格式，其基本操作包括串的查找，插入和刪除等基本功能。 可將文本劃分為若干頁，每頁又有若干行。具體操作中可將文本看作字符串，稱為文本串。頁是文本串的子串，行又是頁的子串。先為文

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

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