【正文】 業(yè)見實驗指導。S) DestroyStack(amp。 define STACKINCREMENT 10。if(! ) exit(OVERFLOW)。e=*。 pnext=top。 top=pnext。允許插入（入隊）操作的一端稱為隊尾，允許刪除（出隊）操作的一端稱為隊頭。e)EnQueue(amp。解決這個問題的巧妙方法是將順序隊列的存儲空間想象成一個邏輯上首尾相連的環(huán)狀空間，這種存儲結(jié)構(gòu)稱為循環(huán)隊列。 (b) 順序循環(huán)隊列的入隊列操作status EnQueue(SqQueueamp。e = []。 } QNode, *QueuePtr。 pnext=NULL。p=next。四、作業(yè)布置 見習題集實驗作業(yè)見實驗指導。 如： ‘ ’ ， C= ‘ BEI JING ’ 子串：由串中任意個連續(xù)的字符組成的子序列。如通過判等、求串長和求子串等操作可以實現(xiàn)定位函數(shù)Index。C語言中的串以一個空字符為結(jié)束符，串長是一個隱含值。 struct Chunk *next。 數(shù)組的順序存儲結(jié)構(gòu)有兩種：一種是按行序存儲，如高級語言BASIC、COBOL和PASCAL語言都是以行序為主。（1）稀疏矩陣的三元組表表示法對于稀疏矩陣的壓縮存儲要求在存儲非零元素的同時，還必須存儲該非零元素在矩陣中所處的行號和列號。通過程序結(jié)合矩陣進行講解。 typedef struct{Triple data[MAXSIZE+1]。 Loc[j1，j2，…jn]=Loc[0，0，…，0]+ 其中=L，ci1=bici， 1i≤n 特殊矩陣的壓縮存儲特殊矩陣壓縮存儲的壓縮原則是：對有規(guī)律的元素和值相同的元素只分配一個存儲單元，對于零元素不分配空間。從邏輯結(jié)構(gòu)上看，數(shù)組可以看成是一般線性表的擴充。 // 串的當前長度 } LString。這類串操作實現(xiàn)的算法為：先為新生成的串分配一個存儲空間，然后進行串值的復制（以串的復制操作為例）。按這種串的表示方法實現(xiàn)的串的運算時，其基本操作為 “字符序列的復制”（通過串聯(lián)接和求子串來講解）。 如：A= ‘ BEIJING ’，B= ‘JING ’，B在A中的位置為4。二、重點與難點串的存儲結(jié)構(gòu)以及基本操作的實現(xiàn)。 free(p)。}(c) 鏈式隊列的出隊列操作。(b) 鏈式隊列的入隊列操作stutus EnQueue(LinkQueue amp。為了操作方便起見，給鏈式隊列添加一個頭結(jié)點。return OK。(a) 順序循環(huán)隊列的類型描述typedef struct { QElemType *base。為了在C語言中描述方便起見，在此我們約定：初始化建立空隊列時，令front=rear=0，每當插入新的隊尾元素時，尾指針rear增1；每當刪除隊頭元素時，頭指針front增1。隊列的基本操作InitQueue(amp。四、作業(yè)布置 見習題集實驗作業(yè)見實驗指導。top, ElemTye amp。由于鏈表的長度可以動態(tài)增長，因此進行入棧操作時無需考慮棧的上溢，但進行出棧操作時，必需考慮棧的下溢，下溢的條件是top的值為0。return OK。 } SqStack。S, e) Pop(amp。講授新課 棧 抽象數(shù)據(jù)類型棧的定義棧：限定僅在表尾進行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧。 pc=pch。 pa=panext。pc = pch=(LinkList *)malloc(sizeof(LNode))。pc,float coef,int expn){p=(LinkList)malloc(sizeof(LNode))。}ElemType。若為一個一元多項式，同樣用線性表Q表示：這兩個多項式可以相加，結(jié)果為，其中設(shè)，則用線性表表示R為：我們可以采用順序存儲結(jié)構(gòu)存放P、Q和R，使得多項式相加算法定義十分簡介。雙向鏈表如果鏈表中的每個結(jié)點都有兩個指針域，分別指向其前驅(qū)結(jié)點和后繼結(jié)點，則稱這種鏈表為雙向鏈表。} // ListDelete_L注：上述兩個算法的時間復雜度均為O(n)。 j i1) { p = pnext。 snext = pnext。 j = 0。 i ) { p = (LinkList) malloc (sizeof (LNode))。 // 插入到表頭}} // CreateList_L注：從頭部插入元素建立單向鏈表得到的線性序列為輸入序列的逆序列。Lnext = NULL。L, i, e) // 插入數(shù)據(jù)元素ListDele CreateList(amp。三、教學內(nèi)容與教學過程 復習線性表的順序存儲結(jié)構(gòu)的特點引入另一種表示方法鏈式存儲結(jié)構(gòu)。 // 表尾元素的位置for (++p。Status ListDelete_Sq(SqList amp。 // q指示插入位置for (p = amp。Status ListInsert_Sq(SqList amp。L, int i, ElemType e)。 define LIST_INIT_SIZE 100 define LISTINCREMENT 10 Typedef struct { ElemType *elem。 線性表中數(shù)據(jù)元素的位序（如數(shù)據(jù)元素ai在線性表中的位序為i）。注意：數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個方面，任何一個算法的設(shè)計取決于選定的數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)。介紹常見數(shù)據(jù)結(jié)構(gòu)（集合、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖型結(jié)構(gòu)）具體表示方式(2) 邏輯結(jié)構(gòu)上述數(shù)據(jù)結(jié)構(gòu)的定義是對操作對象的一種數(shù)學描述，是從操作對象抽象出來的數(shù)學模型。是K上關(guān)系的有限集合，m為K上關(guān)系的個數(shù)，通常情況下m的取值為1。成績考核方式為：期末成績+平時成績，其中期末成績占70%，平時成績占30%，平時成績?yōu)椋鹤鳂I(yè)成績+出勤率+上機成績。二、課程教學目標《數(shù)據(jù)結(jié)構(gòu)》是計算機學科中一門核心專業(yè)基礎(chǔ)課。主要介紹如何合理地組織數(shù)據(jù)、有效地存儲和處理數(shù)據(jù)，正確地設(shè)計算法以及對算法的分析和評價。講授新課 什么是數(shù)據(jù)結(jié)構(gòu) 講解：（數(shù)據(jù)結(jié)構(gòu)課程的研究背景）從計算機最初以數(shù)值計算為主到大量非數(shù)值計算出現(xiàn)引出數(shù)據(jù)結(jié)構(gòu)。K上任何一個二元關(guān)系Rj是序偶的集合。結(jié)構(gòu)定義中的“關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此又稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。（4）數(shù)據(jù)結(jié)構(gòu)一般包括三方面內(nèi)容： 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的運算 （舉例講解）小結(jié)：　總結(jié)本講的主要內(nèi)容四、作業(yè)布置見習題集 單元名稱：第 二 講：線性表的類型定義，線性表的順序存儲一、教學目標 掌握線性表的順序表示和實現(xiàn)二、重點與難點線性表的順序表示和實現(xiàn)。抽象數(shù)據(jù)類型線性表的定義：講解定義中的數(shù)據(jù)對象，數(shù)據(jù)關(guān)系以及基本操作（教材P19），重點講解常用的基本操作含義。 int length。 ListDelete_Sq(SqList amp。L, int i, ElemType e) {// 在順序線性表L的第i個元素之前插入新的元素e，// i的合法值為1≤i≤Listlength_Sq(L)+1if (i 1 || i +1) return ERROR。([])。L, int i, ElemType amp。 p = q。講授新課 （1）線性鏈表線性鏈表：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的）。L, n) // 生成含 n 個數(shù)據(jù)元素的鏈表CreateList(amp。 // 先建立一個帶頭結(jié)點的單鏈表for (i = n。(2) 建立單鏈表（要求從尾部插入）void CreateList_L(LinkList amp。 // 生成新結(jié)點scanf(amp。while (p amp。 // 插入L中pnext = s。 ++j。單鏈表的優(yōu)點： 它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用 不需預先分配空間 插入、刪除操作方便單鏈表的缺點： 指針占用額外存儲空間 不能隨機存取，查找速度慢小結(jié)：本講主要介紹了單鏈表的存儲結(jié)構(gòu)，以及的基本操作（建立、插入和刪除）的實現(xiàn)。雙向鏈表中的結(jié)點類型描述如下：typedef struct DuLNode