數據結構教案C語言版

. 課程教案課程名稱： 數據結構 授課教師：學習對象：任課時間：一、學生情況分析數據結構是計算機專業(yè)的一門核心專業(yè)課程。學生在前期的學習中已經學習了C語言程序設計課程。通過本課程學習使學生對提高編寫程序的能力以及解決實際問題的能力。二、課程教學目標數據結構是計算機學科中一門核心專業(yè)基礎課。主要介紹如何合理地組織數據、有效地存儲和處理數據，正確地設計算法以及對算法的分析和評價。通過本課程的學習，使學生深透地理解數據結構的邏輯結構和物理結構的基本概念以及有關算法，培養(yǎng)基本的、良好的程序設計技能，編制高效可靠的程序，為學習操作系統(tǒng)、編譯原理和數據庫等課程奠定基礎。三、課程教學內容第一章 緒論教學內容：1） 什么是數據結構2） 抽象數據類型概念；數據類型；數據抽象與抽象數據類型；用于描述數據結構的語言3） 數據結構的抽象層次4） 算法定義5）性能分析與度量；算法的性能標準；算法的后期測試；算法的事前估計；空間復雜度度量；時間復雜度度量；時間復雜度的漸進表示法；教學要求： 了解：數據結構基本概念及數據結構的抽象層次 了解：抽象數據類型概念 了解：算法的定義及算法特性 掌握：算法的性能分析與度量方法第二章 線性表教學內容：1） 線性表的定義和特點2） 線性表的順序存儲及查找、插入和刪除操作3） 線性表的鏈式存儲及查找、插入和刪除操作4） 使用線性表的實例教學要求：了解：線性表的定義和特點熟練掌握：線性表的順序存儲結構的查找、插入和刪除等基本操作熟練掌握：單鏈表、循環(huán)鏈表及雙向鏈表的定義及實現掌握：熟練掌握單鏈表的應用方法第三章 棧和隊列教學內容：1） 棧：棧的抽象數據類型；棧的順序存儲表示；棧的鏈式存儲表示2） 隊列：隊列的抽象數據類型；隊列的順序存儲表示；隊列的鏈式存儲表示3） 隊列的應用舉例教學要求：熟練掌握：棧的定義及實現熟練掌握：隊列的定義及實現掌握：能運用棧和隊列解決簡單實際問題第四章 串教學:內容：1) 字符串的抽象數據類型2) 字符串操作的實現3) 字符串的模式匹配教學要求：熟練掌握：字符串的定義方式熟練掌握：字符串的各種操作的實現了解：字符串的模式匹配算法第五章 數組和廣義表教學:內容：1) 數組的定義和初始化2) 作為抽象數據類型的數組的順序存儲方式教學要求：了解：作為抽象數據類型的數組的定義熟練掌握：順序表的數組定義方式及實現第六章 樹和二叉樹教學內容：1) 樹和森林的概念：樹的定義；樹的術語；樹的抽象數據類型；森林的概念2) 二叉樹：二叉樹的定義；二叉樹的性質；二叉樹的抽象數據類型3) 二叉樹的表示：數組表示；鏈表存儲表示4) 二叉樹的遍歷：中序遍歷；前序遍歷；后序遍歷；應用二叉樹遍歷的實例；二叉樹的中序非遞歸算法5) 線索化二叉樹：線索；中序線索化二叉樹；前序與后序的線索化6) 樹與森林：樹的存儲表示；森林與二叉樹的轉換；樹的遍歷；森林的遍歷7) 二叉樹的計數8) 霍夫曼樹：路徑長度；霍夫曼樹；霍夫曼樹編碼教學要求：了解：樹和森林的概念掌握：二叉樹的概念、性質及二叉樹的表示熟練掌握：二叉樹的遍歷方法掌握：線索化二叉樹的特性及尋找某結點的前驅和后繼的方法掌握：樹和森林的實現及遍歷方法掌握：二叉樹的計數方法及從二叉樹遍歷結果得到二叉樹的方法掌握：霍夫曼樹的實現方法及霍夫曼編碼的概念第七章 圖教學內容：1）圖的基本概念：圖的基本概念；圖的抽象數據類型2）圖的存儲表示：鄰接矩陣；鄰接表；鄰接多重表3）圖的遍歷與連通性；深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量4）最小生成樹：克魯斯卡爾算法；普里姆算法教學要求：掌握：圖的基本概念和圖的存儲表示熟練掌握：圖的兩種遍歷方法與求解連通性問題的方法掌握：構造最小生成樹的Prim和Kruskal方法第九章 查找教學內容：1) 靜態(tài)查找表：順序表的查找；有序表的查找；索引順序表的查找2) 二叉排序樹：二叉排序樹上的搜索、插入和刪除教學要求：熟練掌握：靜態(tài)搜索表的順序搜索和折半搜索方法熟練掌握：二叉搜索樹的表示、搜索、插入、刪除算法及其性能分析方法第十章 內部排序 教學內容：1) 概述2) 插入排序：直接插入排序；對分插入排序；鏈表插入排序；希爾排序3) 選擇排序：直接選擇排序；堆排序教學要求：掌握：排序的基本概念和性能分析方法掌握：插入排序、選擇排序、等內排序的方法及性能分析方法單元名稱：第 一 講：緒論 一、教學目標 1.了解數據結構課程的體系結構2.掌握本章介紹的各種基本概念和術語3.了解數據結構的二元組表示4.掌握邏輯結構與物理結構之間的映像關系。二、重點與難點重點：數據結構的基本概念；邏輯結構與物理結構之間的映像關系。難點：邏輯結構與物理結構之間的映像關系。三、教學內容與教學過程介紹本學期課程的內容及安排本課程是計算機專業(yè)的重要專業(yè)課之一，主要介紹常用的數據結構以及相關算法。本課程主要講授線性表、棧和隊列、串、數組、樹和二叉樹、圖、查找、排序等內容。成績考核方式為：期末成績+平時成績，其中期末成績占70%，平時成績占30%，平時成績?yōu)椋鹤鳂I(yè)成績+出勤率+上機成績。講授新課1.1 什么是數據結構 講解：（數據結構課程的研究背景）從計算機最初以數值計算為主到大量非數值計算出現引出數據結構。講解：（數據結構課程的研究對象）例1-1圖書館的書目檢索系統(tǒng)自動化問題。1-2計算機和人機對奕問題1-3多叉路口交通燈的管理問題總結：從以上三個例子可以看出，描述這類非數值計算問題的數學模型不再是數學方程，而是諸如線性表、樹和圖等之類的數據結構，這些都是數據結構課程的研究對象。因此，簡單地說，數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科。介紹數據結構課程的發(fā)展以及與其他課程之間的關系。1.2基本概念和術語基本概念：數據、數據元素、數據項、數據對象、數據結構、結構（1）常見基本結構（邏輯結構）：集合、線性結構、樹形結構、圖狀結構或網狀結構數據結構的形式定義： 數據結構一般用一個二元組來表示：Data_Structure=(D,S)其中：D是數據元素的有限集，S是D上的關系的有限集表示一種數據結構，它由數據元素集合K和在K上定義的一種二元關系的集合R所組成。其中：是數據元素的有限集合，n為中數據元素的個數。是K上關系的有限集合，m為K上關系的個數，通常情況下m的取值為1。K上任何一個二元關系Rj是序偶的集合。對于Rj中的任一序偶（x，yK），稱x為第一個元素（或y的前驅），y為第二個元素（或x的后繼）。數據結構中的數據元素和數據元素之間的關系還可以用圖形直觀地表示出來。圖形中的每個結點對應一個數據元素，兩結點之間帶箭頭的連線對應二元關系中的一個序偶，其中序偶的第一個元素稱為弧尾，第二個元素稱為弧頭。舉例講解：例 數據結構line=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=，,，。例數據結構tree=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=，。例 數據結構graph=K，R，其中K=01，02，03，04，05，R=r，r=，。介紹常見數據結構（集合、線性結構、樹型結構、圖型結構）具體表示方式(2) 邏輯結構上述數據結構的定義是對操作對象的一種數學描述，是從操作對象抽象出來的數學模型。結構定義中的“關系”描述的是數據元素之間的邏輯關系，因此又稱為數據的邏輯結構。根據這種邏輯關系通常將數據結構劃分為線性結構和非線性結構，其中非線性結構又分為樹型結構和圖型結構。(3) 物理結構數據結構在計算機中的表示（存儲映象）稱為數據的物理結構或存儲結構，它涉及到數據元素及其相互關系在計算機內部的表示形式。數據元素之間的關系在計算機中有兩種不同的表示方法：順序映像和非順序映像。根據數據元素相互之間的關系在計算機中的表示形式將數據的物理結構劃分為順序結構和鏈式結構。順序映像的特點是借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系。非順序映像的特點是借助指示元素存儲地址的指針表示數據元素之間的邏輯關系。注意：數據的邏輯結構和物理結構是密切相關的兩個方面，任何一個算法的設計取決于選定的數據的邏輯結構，而算法的實現依賴于采用的存儲結構。（4）數據結構一般包括三方面內容： 數據的邏輯結構、數據的存儲結構、數據的運算 （舉例講解）小結：總結本講的主要內容四、作業(yè)布置見習題集 單元名稱：第 二 講：線性表的類型定義，線性表的順序存儲一、教學目標 掌握線性表的順序表示和實現二、重點與難點線性表的順序表示和實現。三、教學過程的具體安排講授新課2.1線性表的類型定義 線性表的定義：一個線性表是n 個數據元素的有限序列。其中每個數據元素的具體含義，在不同的情況下各不相同，但是同一線性表中的元素必定具有相同特性，即屬于同一數據對象。例如：26個英文字母表；學生健康情況登記表（圖2.1）等。 例如線性表（a1,ai-1,ai,ai+1,an），稱ai-1是ai的直接前驅元素， ai+1是 ai的直接后繼。引導學生自己總結線性結構的特點。線性表的長度：線性表中元素的個數（n0），n=0為空表。 線性表中數據元素的位序（如數據元素ai在線性表中的位序為i）。抽象數據類型線性表的定義：講解定義中的數據對象，數據關系以及基本操作（教材P19），重點講解常用的基本操作含義。通過示例2-1，2-2講解更復雜的基本操作，并分析時間復雜度。2.2 線性表的順序表示和實現（1）線性表的順序表示：用一組地址連續(xù)的存儲單元依次存儲線性表的數據元素。（2）順序儲存的地址關系：假設線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數據元素的存儲位置。則線性表中第i+1個數據元素的存儲位置LOC( a i+1)和第i個數據元素的存儲位置LOC(a i)之間滿足下列關系：LOC(a i+1)=LOC(a i)+l 線性表的第i個數據元素ai的存儲位置為：LOC(ai)=LOC(a1)+(i-1)*l，其中LOC(a1)為線性表的基地址。（3）順序表及其特點, 順序儲存結構是一種隨機存取的存儲結構。（4）線性表的動態(tài)分配順序存儲結構。 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 Typedef struct ElemType *elem;int length;int listsize;SqList;(1) 基于順序存儲結構的基本操作的實現主要介紹下面的基本操作并且分析時間復雜度。InitList_Sq(SqList &L);ListInsert_Sq(SqList &L, int i, ElemType e); ListDelete_Sq(SqList &L, int i, ElemType &e);LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType);MergeList_Sq(SqList La,SqList Lb, SqList &Lc);重點講解：順序存儲結構上實現線性表的插入操作設線性表，為了保證線性表的有序性，當在位置i之前插入一個新的數據元素x時，需要將第i個到第n個數據元素均向后移動一個位置，然后將數據元素x存儲到第i個位置上并改變線性表的長度。Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在順序線性表L的第i個元素之前插入新的元素e，/ i的合法值為1iListlength_Sq(L)+1if (i L.length+1) return ERROR; / 插入位置不合法if (L.length = L.listsize) / 當前存儲空間已滿，增加分配 newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(OVERFLOW); / 存儲分配失敗L.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存儲容量q = &(L.elemi-1); / q指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;/ 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表長增1return OK; / ListInsert_Sq平均時間復雜度分析： 順序存儲結構上實現線性表的刪除操作設線性表 ，為了保證線性表的有序性,當刪除第個位置上的元素后，需要將第i+1個到第n個數據元素均向前移動一個位置并改變線性表的長度。Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在順序線性表L中刪除第i個元素，并用e返回其值。/ i的合法值為1iListLength_Sq(L)if (i L.length) return ERROR; / 刪除位置不合法p = &(L.elemi-1); / p為被刪除元素的位置e = *p; / 被刪除元素的值賦給eq = L.elem+L.length-1; / 表尾元素的位置for (+p; p next = NULL; / 先建立一個帶頭結點的單鏈表for (i = n; i 0; -i ) p = (LinkList) malloc (sizeof (LNode); / 生成新結點scanf(&p-data); / 輸入元素值p-next = L-next; L-next = p; / 插入到表頭 / CreateList_L注：從頭部插入元素建立單向鏈表得到的線性序列為輸入序列的逆序列。(2) 建立單鏈表（要求從尾部插入）void CreateList_L(LinkList &L, int n) /正位序輸入n個元素的值，建立帶表頭結點的單鏈線性表L。L = (LinkList) malloc (sizeof (LNode); r = L;L-next = NULL; / 先建立一個帶頭結點的單鏈表for (i = n; i 0; -i ) p = (LinkList) malloc (sizeof (LNode); / 生成新結點scanf(&p-data); / 輸入元素值p-next=r-next; r-next=p; r = p; / 插入到表尾 / CreateList_L (3) 在帶頭結點的單鏈表中插入結點分析：設在結點a和結點b之間插入數據為x的結點，通過圖來分析則插入前和插入后的情況。Status ListInsert_L(LinkList L, int i, ElemType e) / 在帶頭結頭的單鏈表L中第i位置之前插入元素ep = L; j = 0;while (p & j next; +j; / 尋找第i-1個結點if (!p | j i-1) return ERROR; / i小于1或者大于表長s = (LinkList) malloc ( sizeof (LNode); / 生成新結點s-data = e; s-next = p-next; / 插入L中p-next = s;return OK; / LinstInsert_L(4) 在帶頭結點的單鏈表中刪除結點Status ListDelete_L(LinkList L, int i, ElemType &e) p = L; j = 0;while (p-next & j next; +j; /尋找第i個結點并令p指向其前趨if (!(p-next) | j i-1) return ERROR; / 刪除位置不合理q = p-next; p-next = q-next; / 刪除并釋放結點e = q-data; free(q);return OK; / ListDelete_L注：上述兩個算法的時間復雜度均為O(n)。單鏈表的優(yōu)點：它是一種動態(tài)結構，整個存儲空間為多個鏈表共用不需預先分配空間插入、刪除操作方便單鏈表的缺點：指針占用額外存儲空間不能隨機存取，查找速度慢小結：本講主要介紹了單鏈表的存儲結構，以及的基本操作（建立、插入和刪除）的實現。四、作業(yè)布置見習題集實驗作業(yè)見實驗指導。 第四講 循環(huán)鏈表，雙向鏈表，鏈表應用一、教學目標 1了解循環(huán)鏈表和的基本概念；2掌握雙向鏈表的插入和刪除操作；3掌握一元多項式的表示及加法在鏈式存儲結構上的實現。二、重點與難點雙向鏈表的存儲結構和基本操作實現。三、教學內容與教學過程講授新課單向循環(huán)鏈表設指針p指向單向鏈表中最后一個結點，則p-next的值是0，表示該結點是單向鏈表的最后一個結點。如果將單向鏈表中的最后一個結點的指針域改為存放單向鏈表中第一個結點的地址值，使得整個線性鏈表構成一個環(huán)，則稱這種線性鏈表為單向循環(huán)鏈表。設p指向單向循環(huán)鏈表中的最后一個結點，則p-next的值不是0而是等于指向循環(huán)鏈表中的第一個結點head的值。雙向鏈表如果鏈表中的每個結點都有兩個指針域，分別指向其前驅結點和后繼結點，則稱這種鏈表為雙向鏈表。雙向鏈表中的結點類型描述如下：typedef struct DuLNode ElemType data; / 數據域struct DuLNode *prior; / 指向前驅的指針域struct DuLNode *next; / 指向后繼的指針域 DuLNode, *DuLinkList;設指針p指向雙向鏈表中的某個結點，則顯然有以下的結論：p-prior-next=p=p-next-prior(1) 雙向鏈表的插入操作設指針變量p指向雙向鏈表中的結點A，指針變量q指向被插入的新結點B，則在結點A的后面插入結點B的操作序列為：(1) q-next=p-next； (2) p-next-prior=q；(3) p-next=q；(4) q-prior=p；(2) 雙向鏈表的刪除操作設指針變量p指向雙向鏈表中被刪除的結點X，則刪除結點X的操作序列為：(1) p-prior-next=p-next； (2) p-next-prior=p-prior； (3) free(p)；注：在雙向鏈表或雙向循環(huán)鏈表中進行插入和刪除操作時，尤其要注意修改有關結點指針域的操作次序，以免丟失鏈域信息而造成鏈表中斷的錯誤。鏈式存儲結構的應用：一元多項式的表示及相加一元多項式可按升冪寫成：它由n+1個系數唯一確定。在計算機中，可用一個線性表P來表示：每項系數i隱含在系數的序號里。若為一個一元多項式，同樣用線性表Q表示：這兩個多項式可以相加，結果為，其中設，則用線性表表示R為：我們可以采用順序存儲結構存放P、Q和R，使得多項式相加算法定義十分簡介。然而，在通常的應用中，多項式的次數很高且變化很大，使得順序存儲結構的最大長度很難確定，特別是在處理形如S(x)=1+3x10001+2x20000的多項式時，要用長度為20001的線性表來表示。如果對每個元素使用兩個數據項，一個為系數項，另一個為指數項，則這樣構成的線性表可表示成：因此上式S(x)可表示成(1, 0 ),(3, 1001), (2, 20000 )。顯然這樣的線性表應采用鏈式存儲結構。課本 P41 圖2.17中兩個線性鏈表分別表示一元多項式A(x)=7+3x+9x8+5x11和一元多項式B(x)=8x+22x7-9x8，由這兩個多項式得到的和多項式如圖課本 P412.18所示。用鏈表表示多項式時，鏈表中的數據類型描述成：typedef struct polynomialfloat coef;int expn ; struct polynomial *next;ElemType;根據一元多項式相加的運算規(guī)則：對于兩個一元多項式中所有指數相同的項，對應系數相加，若其和不為零，則構成和多項式中的一項；對于兩個一元多項式中所有指數不相同的項則分別抄到和多項式中去。第一步：分別從A表和B表的表頭開始，根據比較pa-expn和pb-expn的比較結果分三種情況討論，直到A表或B表全部處理完。(1) pa-expn=pb-expn：則相加此兩項的系數，如果相加后該項系數不等于0，則在C表中生成一個新結點存放該項，修改pa和pb使其指向各自的下一個結點。(2) pa-expn pb-expn：則復制A表中pa所指向的結點到C表中，修改pa使其指向下一個結點。(3) pa-expn expn：則復制B表中pb所指向的結點到C表中，修改pb使其指向下一個結點。第二步：若B表沒有處理完，將B表中剩余結點復制到C表中；反之則將A表中剩余結點復制到C表中。void create_item(LinkList &pc,float coef,int expn)p=(LinkList)malloc(sizeof(LNode);p-coef=coef; p-expn=expn; pc-next=p; pc=p;void ploy_add(LinkList pah,LinkList pbh,LinkList &pch)pa = pah; pb = pbh;pc = pch=(LinkList *)malloc(sizeof(LNode); / 為c鏈表添加一個頭結點while(pa!=0 & pb!=0)if(pa-expn=pb-expn)x=pa-coef+pb-coef;if(x!=0) create_item(pc,x,pa-expn);pa=pa-next; pb=pb-next;else if(pa-expnpb-expn)create_item(pc,pa-coef,pa-expn); pa=pa-next;else create_item(pc,pb-coef,pb-expn); pb=pb-next;while (pa!=0) create_item(pc,pa-coef,pa-expn); pa=pa-next;while (pb!=0) create_item(pc,pb-coef,pb-expn); pb=pb-next;pc-next=0; pc=pch; pch=pch-next; free(pc); /* 釋放c鏈中的頭結點 */小結：本講主要介紹了循環(huán)鏈表和雙向鏈表的基本概念，雙向鏈表的插入和刪除操作，一元多項式的表示及相加在鏈式存儲結構上的實現。四、作業(yè)布置見習題集實驗作業(yè)見實驗指導。單元名稱：第 五 講：棧一、教學目標 1了解棧的基本概念和基本操作；2掌握棧的基本操作在兩種存儲結構上的實現。二、重點與難點棧的基本操作在兩種存儲結構上實現。三、教學內容與教學過程首先復習線性表的知識，引入限定性的數據結構棧和隊列。講授新課3.1 棧3.1.1 抽象數據類型棧的定義棧：限定僅在表尾進行插入或刪除操作的線性表，表尾棧頂，表頭棧底，不含元素的空表稱空棧。通過教材P44的圖3.1講解棧頂，棧底以及棧后進先出的特點。棧的抽象數據類型定義：ADT Stack 數據對象：D ai | ai ElemSet, i=1,2,.,n, n0 數據關系：R1 | ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 基本操作：InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S, &e) Push(&S, e)Pop(&S, &e) ADT Stack3.1.2 棧的表示和實現順序棧類似于線性表的順序映象實現，指向表尾的指針可以作為棧頂指針。 棧的順序存儲表示： #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;順序棧的基本操作的算法描述：初始化，返回棧頂元素，入棧，出棧。(a) ?？諚M條件?？諚l件：top=base棧滿條件：base-top=stacksize(b) 入棧操作Status Push (SqStack &S, SElemType e) if(S.top-S.base=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base ) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+ = e;return OK; (c) 出棧操作Status Pop (SqStack &S, SElemType &e) if (S.top=S.base) return ERROR;e=*-S.top;return OK;鏈棧：棧的鏈式存儲結構。棧頂指針就是鏈表的頭指針棧的鏈式存儲結構類似單鏈表的存儲結構，鏈表中第一個結點表示棧頂，最后一個結點表示棧底。由于鏈表的長度可以動態(tài)增長，因此進行入棧操作時無需考慮棧的上溢，但進行出棧操作時，必需考慮棧的下溢，下溢的條件是top的值為0。鏈式棧的入棧操作Status Push(LinkList &top, ElemType x)p=(LinkList *)malloc(sizeof(LNode); p-data=x; p-next=top; top=p; return OK;(2) 鏈式棧的出棧操作Status Pop(LinkStack &top, ElemTye &y)if (top=0) return ERROR;p=top; y=p-data; top=p-next; free(p);return OK;小結；本講主要介紹了棧的基本概念，棧的基本運算，棧在順序存儲結構和鏈式存儲結構上實現基本操作。四、作業(yè)布置 見習題集實驗作業(yè)見實驗指導。單元名稱：第 六 講：隊列一、教學目標 1了解棧的基本概念和基本操作；2掌握棧的基本操作在兩種存儲結構上的實現。二、重點與難點棧的基本操作在兩種存儲結構上實現。三、教學內容與教學過程講授新課隊列的基本概念隊列是一種限制所有插入操作在線性表的一端進行，而所有的刪除操作在線性表的另一端進行的特殊線性表。允許插入（入隊）操作的一端稱為隊尾，允許刪除（出隊）操作的一端稱為隊頭。設隊列為，則是隊頭元素，是隊尾元素。隊列中的元素按照的順序進入隊列的，退出隊列也只能按照這個次序依次退出，即只有在都退出隊列后，才能退出隊列。因此隊列也稱為先進先出（FIFO）的線性表。2、隊列的基本操作InitQueue(&Q)DestroyQueue(&Q)ClearQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)EnQueue(&Q, e)DeQueue(&Q, &e)3、隊列的順序存儲結構和循環(huán)隊列在隊列的順序存儲結構中，除了用一組地址連續(xù)的存儲單元依次存放從隊頭到隊尾的元素之外，還需要附設兩個指針front和rear。為了在C語言中描述方便起見，在此我們約定：初始化建立空隊列時，令front=rear=0，每當插入新的隊尾元素時，尾指針rear增1；每當刪除隊頭元素時，頭指針front增1。因此，在非空隊列中，頭指針始終指向隊列頭元素，尾指針始終指向隊列尾元素的下一個位置。討論：將數據10，20，30，40，50，60按照入隊列、入隊列、入隊列、出隊列、出隊列、入隊列、入隊列、入隊列、出隊列和出隊列的順序，觀察隊列中隊頭和隊尾指針的變化狀態(tài)。假設當前為隊列分配的最大空間為6，則不可再繼續(xù)插入新的隊尾元素，否則會因數組越界而導致程序代碼被破環(huán)，然而，此時又不宜如順序棧那樣進行存儲再分配擴大數組空間，因為隊列的實際可用空間并末占滿。解決這個問題的巧妙方法是將順序隊列的存儲空間想象成一個邏輯上首尾相連的環(huán)狀空間，這種存儲結構稱為循環(huán)隊列。分析課本P64圖3.14可知，Q.front=Q.rear無法判斷隊列空間是“滿”還是“空”。解決這個問題有兩種方法：其一是另設一個標志位以區(qū)別隊列是“空”還是“滿”；其二是少用一個元素空間，約定以隊頭指針在隊尾指針的下一個位置上作為隊列“滿”的標志。因此，判斷隊列空的條件為Q.front=Q.rear；判斷隊列滿的條件為Q.front = (Q.rear+1) % MAXQSIZE。(a) 順序循環(huán)隊列的類型描述typedef struct QElemType *base; int front; int rear; SqQueue; (b) 順序循環(huán)隊列的入隊列操作status EnQueue(SqQueue&Q, QelemType e)if (Q.rear+1)%MAXSIZE=Q.front) return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXSIZE;return OK;(c) 順序循環(huán)隊列的出隊列操作status DeQueue(SqQueue &Q, QelemType &e) if (Q.rear=Q.front) return ERROR;e = Q.baseQ.front;Q.front = (Q.front+1)%MAXSIZE;return OK;4、隊列的鏈式存儲結構隊列的鏈式存儲結構實際上是一個同時帶有頭指針和尾指針的單向鏈表，頭指針指向隊頭元素，尾指針指向隊尾元素。為了操作方便起見，給鏈式隊列添加一個頭結點?？盏逆準疥犃械呐袛鄺l件為頭指針和尾指針都指向頭結點。(a) 鏈式循環(huán)隊列的類型描述typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; / 隊頭指針QueuePtr rear; / 隊尾指針 LinkQueue;(b) 鏈式隊列的入隊列操作stutus EnQueue(LinkQueue &Q, QelemType e)p=(QueuePtr)malloc(sizeof(Qnode);if(!p)exit(OVERFLOW);p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;(c) 鏈式隊列的出隊列操作。status DeQueue (LinkQueue &Q, QelemType &e) if(Q.front=Q.rear returnERROR;p=Q.front-next; e=p-data; Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front; free(p);return OK;注意：當隊列中最后一個元素被刪除后，隊列尾指針也丟失了，因此需要對隊尾指針重新賦值。小結：主講主要介紹了隊列的基本概念和基本操作，以及隊列的基本操作在順序存儲結構和鏈式存儲結構上的實現。四、作業(yè)布置 見習題集實驗作業(yè)見實驗指導。單元名稱：第 七 講：串一、教學目標 1.熟悉串的定義以及基本操作的定義，并能利用這些基本操作來實現串的其它各種操作的方法。2.熟練掌握在串的定長順序存儲結構上實現串的各種操作的方法。3.掌握串的堆分配存儲結構以及在其上實現串操作的基本方法。4.了解串的塊鏈存儲結構二、重點與難點串的存儲結構以及基本操作的實現。三、教學內容與教學過程講授新課4.1 串類型的定義（1）基本概念：串（string）：由零個或多個字符組成的有限序列，也稱字符串。記為：S = a1a2a3an (n0) 如：A= BEIJING， B= JING串的長度：串中字符的數目n ?？沾翰缓魏巫址拇?，串長度為0，空格串：僅由一個或多個空格組成的串，長度為串中空格字符的個數。如： ， C= BEI JING 子串：由串中任意個連續(xù)的字符組成的子序列。主串：包含子串的串。如：A= BEIJING B= JING 字符在串中的位置：字符在序列中的序號。子串在主串中的位置：以子串的第一個字符在主串中的位置來表示。如：A= BEIJING ，B= JING ，B在A中的位置為4。串相等：當且僅當兩個串的值相等。也就是說，只有兩個串的長度相等且各個對應位置的字符都相等時才相等。（2）串的抽象數據類型定義：ADT String 數據對象：D ai |aiCharacterSet, i=1,2,.,n, n0 數據關系：R1 | ai-1, ai D, i=2,.,n 基本操作：（見教材P71） ADT String 通過基本操作可以實現更復雜的操作。如通過判等、求串長和求子串等操作可以實現定位函數Index。 4.2 串的表示和實現4.2.1 定長順序存儲表示用一組地址連續(xù)的存儲單元存儲串值的字符序列，類似于線性表的順序存儲結構。所謂定長順序存儲結構，是直接使用定長的字符數組來定義，數組的上界預先給出： #define MAXSTRLEN 255 / 用戶可在255以內定義最大串長 typedef unsigned char SStringMAXSTRLEN + 1; / 0號單元存放串的長度特點：串的實際長度可在這個予定義長度的范圍內隨意設定，超過予定義長度的串值則被舍去，稱之為“截斷” 。按這種串的表示方法實現的串的運算時，其基本操作為 “字符序列的復制”（通過串聯接和求子串來講解）。4.2.2 堆分配存儲表示以一組地址連續(xù)的存儲單元存儲串值的字符序列，存儲空間在程序執(zhí)行過程中動態(tài)分配。 C語言中提供的串類型就是以這種存儲方式實現的。系統(tǒng)利用函數malloc()和free( )進行串值空間的動態(tài)管理，為每一個新產生的串分配一個存儲區(qū)，稱串值共享的存儲空間為“堆”。C語言中的串以一個空字符為結束符，串長是一個隱含值。串堆分配存儲表示：typedef struct char *ch; / 若是非空串，則按串長分配存儲區(qū),否則ch為NULLint length; / 串長度 HString;這類串操作實現的算法為：先為新生成的串分配一個存儲空間，然后進行串值的復制（以串的復制操作為例）。講解串堆分配的表示與實現 （P76，77）4.2.3 塊鏈存儲表示 以鏈表存儲串值，除頭指針外還可以附設一個尾指針指示鏈表中的最后一個結點，并給出當前串的長度。稱如此定義的傳存儲結構為塊鏈結構。#define CHU