數(shù)據(jù)結(jié)構(gòu)教案c語(yǔ)言版(編輯修改稿)
2025-05-14 01:46 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 生成新結(jié)點(diǎn)scanf(amp。pdata)。 // 輸入元素值pnext = Lnext。 Lnext = p。 // 插入到表頭}} // CreateList_L注：從頭部插入元素建立單向鏈表得到的線性序列為輸入序列的逆序列。(2) 建立單鏈表（要求從尾部插入）void CreateList_L(LinkList amp。L, int n) { //正位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。L = (LinkList) malloc (sizeof (LNode))。 r = L。Lnext = NULL。 // 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for (i = n。 i 0。 i ) { p = (LinkList) malloc (sizeof (LNode))。 // 生成新結(jié)點(diǎn)scanf(amp。pdata)。 // 輸入元素值pnext=rnext。 rnext=p。 r = p。 // 插入到表尾}} // CreateList_L (3) 在帶頭結(jié)點(diǎn)的單鏈表中插入結(jié)點(diǎn)分析：設(shè)在結(jié)點(diǎn)a和結(jié)點(diǎn)b之間插入數(shù)據(jù)為x的結(jié)點(diǎn)，通過圖來分析則插入前和插入后的情況。Status ListInsert_L(LinkList L, int i, ElemType e) {// 在帶頭結(jié)頭的單鏈表L中第i位置之前插入元素ep = L。 j = 0。while (p amp。amp。 j i1) { p = pnext。 ++j。 } // 尋找第i1個(gè)結(jié)點(diǎn)if (!p || j i1) return ERROR。 // i小于1或者大于表長(zhǎng)s = (LinkList) malloc ( sizeof (LNode))。 // 生成新結(jié)點(diǎn)sdata = e。 snext = pnext。 // 插入L中pnext = s。return OK。} // LinstInsert_L(4) 在帶頭結(jié)點(diǎn)的單鏈表中刪除結(jié)點(diǎn)Status ListDelete_L(LinkList L, int i, ElemType amp。e) {p = L。 j = 0。while (pnext amp。amp。 j i1) { p = pnext。 ++j。 } //尋找第i個(gè)結(jié)點(diǎn)并令p指向其前趨if (!(pnext) || j i1) return ERROR。 // 刪除位置不合理q = pnext。 pnext = qnext。 // 刪除并釋放結(jié)點(diǎn)e = qdata。 free(q)。return OK。} // ListDelete_L注：上述兩個(gè)算法的時(shí)間復(fù)雜度均為O(n)。單鏈表的優(yōu)點(diǎn)： 它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用 不需預(yù)先分配空間 插入、刪除操作方便單鏈表的缺點(diǎn)： 指針占用額外存儲(chǔ)空間 不能隨機(jī)存取，查找速度慢小結(jié)：本講主要介紹了單鏈表的存儲(chǔ)結(jié)構(gòu)，以及的基本操作（建立、插入和刪除）的實(shí)現(xiàn)。四、作業(yè)布置 見習(xí)題集實(shí)驗(yàn)作業(yè)見實(shí)驗(yàn)指導(dǎo)。 第四講 循環(huán)鏈表，雙向鏈表，鏈表應(yīng)用一、教學(xué)目標(biāo) 1．了解循環(huán)鏈表和的基本概念；2．掌握雙向鏈表的插入和刪除操作；3．掌握一元多項(xiàng)式的表示及加法在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。二、重點(diǎn)與難點(diǎn)雙向鏈表的存儲(chǔ)結(jié)構(gòu)和基本操作實(shí)現(xiàn)。三、教學(xué)內(nèi)容與教學(xué)過程講授新課單向循環(huán)鏈表設(shè)指針p指向單向鏈表中最后一個(gè)結(jié)點(diǎn)，則pnext的值是0，表示該結(jié)點(diǎn)是單向鏈表的最后一個(gè)結(jié)點(diǎn)。如果將單向鏈表中的最后一個(gè)結(jié)點(diǎn)的指針域改為存放單向鏈表中第一個(gè)結(jié)點(diǎn)的地址值，使得整個(gè)線性鏈表構(gòu)成一個(gè)環(huán)，則稱這種線性鏈表為單向循環(huán)鏈表。設(shè)p指向單向循環(huán)鏈表中的最后一個(gè)結(jié)點(diǎn)，則pnext的值不是0而是等于指向循環(huán)鏈表中的第一個(gè)結(jié)點(diǎn)head的值。雙向鏈表如果鏈表中的每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，分別指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，則稱這種鏈表為雙向鏈表。雙向鏈表中的結(jié)點(diǎn)類型描述如下：typedef struct DuLNode { ElemType data。 // 數(shù)據(jù)域struct DuLNode *prior。 // 指向前驅(qū)的指針域struct DuLNode *next。 // 指向后繼的指針域} DuLNode, *DuLinkList。設(shè)指針p指向雙向鏈表中的某個(gè)結(jié)點(diǎn)，則顯然有以下的結(jié)論：ppriornext==p==pnextprior(1) 雙向鏈表的插入操作設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量q指向被插入的新結(jié)點(diǎn)B，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列為：(1) qnext=pnext； (2) pnextprior=q；(3) pnext=q； (4) qprior=p；(2) 雙向鏈表的刪除操作設(shè)指針變量p指向雙向鏈表中被刪除的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X的操作序列為：(1) ppriornext=pnext； (2) pnextprior=pprior； (3) free(p)；注：在雙向鏈表或雙向循環(huán)鏈表中進(jìn)行插入和刪除操作時(shí)，尤其要注意修改有關(guān)結(jié)點(diǎn)指針域的操作次序，以免丟失鏈域信息而造成鏈表中斷的錯(cuò)誤。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的應(yīng)用：一元多項(xiàng)式的表示及相加一元多項(xiàng)式可按升冪寫成：它由n+1個(gè)系數(shù)唯一確定。在計(jì)算機(jī)中，可用一個(gè)線性表P來表示：每項(xiàng)系數(shù)i隱含在系數(shù)的序號(hào)里。若為一個(gè)一元多項(xiàng)式，同樣用線性表Q表示：這兩個(gè)多項(xiàng)式可以相加，結(jié)果為，其中設(shè)，則用線性表表示R為：我們可以采用順序存儲(chǔ)結(jié)構(gòu)存放P、Q和R，使得多項(xiàng)式相加算法定義十分簡(jiǎn)介。然而，在通常的應(yīng)用中，多項(xiàng)式的次數(shù)很高且變化很大，使得順序存儲(chǔ)結(jié)構(gòu)的最大長(zhǎng)度很難確定，特別是在處理形如S(x)=1+3x10001+2x20000的多項(xiàng)式時(shí)，要用長(zhǎng)度為20001的線性表來表示。如果對(duì)每個(gè)元素使用兩個(gè)數(shù)據(jù)項(xiàng)，一個(gè)為系數(shù)項(xiàng)，另一個(gè)為指數(shù)項(xiàng)，則這樣構(gòu)成的線性表可表示成：因此上式S(x)可表示成((1, 0 ),(3, 1001), (2, 20000 ))。顯然這樣的線性表應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。課本 P41 (x)=7+3x+9x8+5x11和一元多項(xiàng)式B(x)=8x+22x79x8，由這兩個(gè)多項(xiàng)式得到的和多項(xiàng)式如圖課本 。用鏈表表示多項(xiàng)式時(shí)，鏈表中的數(shù)據(jù)類型描述成：typedef struct polynomial{float coef。int expn 。 struct polynomial *next。}ElemType。根據(jù)一元多項(xiàng)式相加的運(yùn)算規(guī)則：對(duì)于兩個(gè)一元多項(xiàng)式中所有指數(shù)相同的項(xiàng)，對(duì)應(yīng)系數(shù)相加，若其和不為零，則構(gòu)成和多項(xiàng)式中的一項(xiàng)；對(duì)于兩個(gè)一元多項(xiàng)式中所有指數(shù)不相同的項(xiàng)則分別抄到和多項(xiàng)式中去。第一步：分別從A表和B表的表頭開始，根據(jù)比較paexpn和pbexpn的比較結(jié)果分三種情況討論，直到A表或B表全部處理完。(1) paexpn==pbexpn：則相加此兩項(xiàng)的系數(shù)，如果相加后該項(xiàng)系數(shù)不等于0，則在C表中生成一個(gè)新結(jié)點(diǎn)存放該項(xiàng)，修改pa和pb使其指向各自的下一個(gè)結(jié)點(diǎn)。(2) paexpn pbexpn：則復(fù)制A表中pa所指向的結(jié)點(diǎn)到C表中，修改pa使其指向下一個(gè)結(jié)點(diǎn)。(3) paexpn pbexpn：則復(fù)制B表中pb所指向的結(jié)點(diǎn)到C表中，修改pb使其指向下一個(gè)結(jié)點(diǎn)。第二步：若B表沒有處理完，將B表中剩余結(jié)點(diǎn)復(fù)制到C表中；反之則將A表中剩余結(jié)點(diǎn)復(fù)制到C表中。void create_item(LinkList amp。pc,float coef,int expn){p=(LinkList)malloc(sizeof(LNode))。pcoef=coef。 pexpn=expn。 pcnext=p。 pc=p。}void ploy_add(LinkList pah,LinkList pbh,LinkList amp。pch){pa = pah。 pb = pbh。pc = pch=(LinkList *)malloc(sizeof(LNode))。 // 為c鏈表添加一個(gè)頭結(jié)點(diǎn)while(pa!=0 amp。amp。 pb!=0){if(paexpn==pbexpn){x=pacoef+pbcoef。if(x!=0) create_item(pc,x,paexpn)。pa=panext。 pb=pbnext。}else
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1