計(jì)算機(jī)軟件技術(shù)基礎(chǔ)徐士良第2章1

第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.1數(shù)據(jù)結(jié)構(gòu)的基本概念2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)2.3線性鏈表及其運(yùn)算2.4數(shù)組2.5樹與二叉樹2.6圖1第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.1數(shù)據(jù)結(jié)構(gòu)的基本概念2.1.1兩個(gè)例子2.1.2什么是數(shù)據(jù)結(jié)構(gòu)2.1.3數(shù)據(jù)結(jié)構(gòu)的圖形表示2.1.4線性數(shù)據(jù)結(jié)構(gòu)與非線性數(shù)據(jù)結(jié)構(gòu)2第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算數(shù)據(jù)結(jié)構(gòu)三個(gè)方面的問題：(1)數(shù)據(jù)的邏輯結(jié)構(gòu)(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算目的：提高數(shù)據(jù)處理的效率提高數(shù)據(jù)處理的速度盡量節(jié)省計(jì)算機(jī)存儲(chǔ)空間

3第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.1.1兩個(gè)例子例無序表的順序查找35167885432933215446有序表的對(duì)分查找16212933354346547885數(shù)據(jù)元素在表中的排列順序?qū)Σ檎倚适怯泻艽笥绊憽?第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算例學(xué)生情況登記表以學(xué)號(hào)為順序排列5第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算6第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算7第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算8第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算結(jié)論：在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，可以根據(jù)所做的運(yùn)算不同，將數(shù)據(jù)組織成不同的形式，以便于做該種運(yùn)算，從而提高數(shù)據(jù)處理的效率。9第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.1.2什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素集合。

現(xiàn)實(shí)世界中客觀存在的一切個(gè)體都可以是數(shù)據(jù)元素。10第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算描述一年四季的季節(jié)名春，夏，秋，冬可以作為季節(jié)的數(shù)據(jù)元素；表示數(shù)值的各個(gè)數(shù)

18，11，35，23，16，…

可以作為數(shù)值的數(shù)據(jù)元素；表示家庭成員的各成員名父親，兒子，女兒可以作為家庭成員的數(shù)據(jù)元素。11第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

前后件關(guān)系是數(shù)據(jù)元素之間的一個(gè)基本關(guān)系，但前后件關(guān)系所表示的實(shí)際意義是隨具體對(duì)象的不同而不同。一般來說，數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來描述。12第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1.數(shù)據(jù)的邏輯結(jié)構(gòu)

是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。13第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：數(shù)據(jù)元素的集合D；反映D中各數(shù)據(jù)元素之間的前后件關(guān)系R。

數(shù)據(jù)結(jié)構(gòu)可以表示成

B＝（D，R）其中B表示數(shù)據(jù)結(jié)構(gòu)。14第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。設(shè)a與b是D中的兩個(gè)數(shù)據(jù)，則二元組（a，b）表示a是b的前件，b是a的后件。例如

B＝（D，R）

D＝{春，夏，秋，冬}

R＝{(春，夏)，(夏，秋)，(秋，冬)}15第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算家庭成員數(shù)據(jù)結(jié)構(gòu)

B＝（D，R）

D＝{父親，兒子，女兒}R＝{(父親，兒子），(父親，女兒）}n維向量

X＝（x1，x2，…，xn）也是一種數(shù)據(jù)結(jié)構(gòu)。即

X＝（D，R）

D＝{x1，x2，…，xn}R＝{(x1，x2)，(x2，x3)，…，(xn－1，xn)}16第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算m×n的矩陣是一個(gè)數(shù)據(jù)結(jié)構(gòu)。即

A＝（D，R）

D＝{A1，A2，…，Am}R＝{(A1，A2)，(A2，A3)，…，(Ai，Ai＋1)，…，(Am－1，Am)}其中Ai=（ai1，ai2，…，ain），i＝1，2，…，m

Ai＝（Di，Ri）

Di＝{ai1，ai2，…，ain}

Ri＝{(ai1，ai2)，(ai2，ai3)，…，(aij，ai，j＋1)，…，(ai，n－1，ain)}17第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（數(shù)據(jù)的物理結(jié)構(gòu)）

數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。常用的存儲(chǔ)結(jié)構(gòu)有：順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。18第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.1.3數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示（數(shù)據(jù)結(jié)點(diǎn)，結(jié)點(diǎn)）用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。19第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示20第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

家庭成員間輩份關(guān)系數(shù)據(jù)結(jié)的圖形表示21第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

用圖形表示數(shù)據(jù)結(jié)構(gòu)B＝（D，R）D＝{di|1≤i≤7}＝{d1，d2，d3，d4，d5，d6，d7}R＝{(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)}22第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.1.4線性數(shù)據(jù)結(jié)構(gòu)與非線性數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。線性結(jié)構(gòu)又稱線性表。23第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算不是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)特例

24第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)25第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)2.2.1線性表及其運(yùn)算2.2.2棧及其應(yīng)用2.2.3隊(duì)列及其應(yīng)用26第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.2.1線性表及其運(yùn)算1.什么是線性表(LinearList)n維向量(x1，x2，…，xn)是一個(gè)長(zhǎng)度為n的線性表英文小寫字母表(a，b，c，…，z)是一個(gè)長(zhǎng)度為26的線性表一年中的四個(gè)季節(jié)(春，夏，秋，冬)是一個(gè)長(zhǎng)度為4的線性表矩陣是一個(gè)比較復(fù)雜的線性表27第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算學(xué)生情況登記表是一個(gè)復(fù)雜的線性表由若干數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素稱為記錄(record)

由多個(gè)記錄構(gòu)成的線性表又稱為文件(file)28第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

線性表是由n(n≥0)個(gè)數(shù)據(jù)元素a1，a2，…，an組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。即線性表或是一個(gè)空表，或可以表示為

(a1，a2，…，ai，…，an)

其中ai(i＝1，2，…，n)是屬于數(shù)據(jù)對(duì)象的元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。29第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

非空線性表結(jié)構(gòu)特征：

(1)有且只有一個(gè)根結(jié)點(diǎn)a1，它無前件；

(2)有且只有一個(gè)終端結(jié)點(diǎn)an，它無后件；

(3)除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其它所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n＝0時(shí)，稱為空表。30第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)基本特點(diǎn)：(1)線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；(2)線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。線性表中第i個(gè)元素ai在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址為

ADR(ai)＝ADR(a1)＋(i－1)k31第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算長(zhǎng)度為n的線性表(a1，a2，…，ai，…，an)順序存儲(chǔ)結(jié)構(gòu)32第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算整型一維數(shù)組存放長(zhǎng)度為8的線性表(29,18,56,63,35,24,31,47)33第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算建立空線性表的順序存儲(chǔ)空間（即初始化線性表的順序存儲(chǔ)空間）

#include"stdlib.h"voidinitsl(v，m，n)ET*v；

intm，*n；

{v＝malloc(m*sizeof(ET))；*n＝0；

return；

}釋放線性表的順序存儲(chǔ)空間

free(v)；34第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

線性表順序存儲(chǔ)結(jié)構(gòu)下的主要運(yùn)算：(1)在線性表的指定位置處加入一個(gè)新的元素（即線性表的插入）；(2)在線性表中刪除指定的元素（即線性表的刪除）；(3)在線性表中查找某個(gè)（或某些）特定的元素（即線性表的查找）；(4)對(duì)線性表中的元素進(jìn)行整序（即線性表的排序）；(5)按要求將一個(gè)線性表分解成多個(gè)線性表（即線性表的分解）；(6)按要求將多個(gè)線性表合并成一個(gè)線性表（即線性表的合并）；(7)復(fù)制一個(gè)線性表（即線性表的復(fù)制）；(8)逆轉(zhuǎn)一個(gè)線性表（即線性表的逆轉(zhuǎn)）等。35第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算3.線性表在順序存儲(chǔ)下的插入運(yùn)算36第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算37第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算線性表在順序存儲(chǔ)下的插入算法輸入：線性表的存儲(chǔ)空間V(1：m)；線性表的長(zhǎng)度n（n≤m）；插入的位置i（i表示在第i個(gè)元素之前插入）；插入的新元素b。輸出：插入后的線性表存儲(chǔ)空間V(1：m)及線性表的長(zhǎng)度n。

PROCEDUREINSL(V，m，n，i，b)1.IF(n＝m)THEN{OVERFLOW；RETURN}2.IF(i＞n)THENi＝n＋13.IF(i＜1)THENi＝14.FORj＝nTOiBY－1DOV(j＋1)＝V(j)5.V(i)＝b6.n＝n＋17.RETURN38第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

voidinsl(v，m，n，i，b)ETv[]，b；

intm，*n，i；

{if(*n＝＝m){printf("overflow\n")；return；}if(i＞*n－1)i＝*n＋1；

if(i＜1)i＝1；

for(j＝*n；j＜＝i；j――)v[j]＝v[j－1]；

v[i－1]＝b；*n＝*n＋1；

return；

}39第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算4.線性表在順序存儲(chǔ)下的刪除運(yùn)算40第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算41第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算線性表在順序存儲(chǔ)下的刪除算法輸入：線性表的存儲(chǔ)空間V(1：m)；線性表的長(zhǎng)度n（n≤m）；刪除的位置i（表示刪除第i個(gè)元素）。輸出：刪除后的線性表存儲(chǔ)空間V(1：m)及線性表的長(zhǎng)度n。

PROCEDUREDESL(V，m，n，i)1.IF(n＝0)THEN{UNDERFLOW；RETURN}2.IF(i＜1)or(i＞n)THEN{“Notthiselementinthelist”；RETURN}3.FORj＝iTOn－1DOV(j)＝V(j＋1)4.n＝n－15.RETURN42第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

voiddesl(v，m，n，i)ETv[]；

intm，*n，i；

{if(*n＝＝0){printf("underflow\n")；return；}if((i＜1)||(i＞*n))

{printf("Notthiselementinthelist\n")；

return；

}for(j＝i；j＜＝*n－1；j＋＋)v[j－1]＝v[j]；*n＝*n－1；

return；

}43第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.2.2棧及其應(yīng)用1.什么是棧主程序與子程序之間的調(diào)用關(guān)系

MAIN

SUB1

SUB2

SUB3SUB4……

……

……

…………CALLSUB1

CALLSUB2

CALLSUB3

CALLSUB4……A：……

B：……

C：……

D：……

……

……

……

……

…………END

RETURN

RETURN

RETURNRETURN44第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算棧(stack)是限定在一端進(jìn)行插入與刪除的線性表。允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧是按照“先進(jìn)后出”(FILO—FirstInLastOut)或“后進(jìn)先出”(LIFO—LastInFirstOut)的原則組織數(shù)據(jù)的，因此，棧也被稱為“先進(jìn)后出”表或“后進(jìn)先出”表。棧具有記憶作用。用指針top來指示棧頂?shù)奈恢?，用指針bottom指向棧底。往棧中插入一個(gè)元素稱為入棧運(yùn)算，從棧中刪除一個(gè)元素(即刪除棧頂元素)稱為退棧運(yùn)算。45第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算46第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.棧的順序存儲(chǔ)及其運(yùn)算47第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算top＝0表示?？?；top＝m表示棧滿。建立空棧的順序存儲(chǔ)空間（即初始化棧的順序存儲(chǔ)空間）

#include"stdlib.h"voidinit_stack(s，m，top)ET*s；

intm，*top；

{s＝malloc(m*sizeof(ET))；*top＝0；

return；

}釋放棧的順序存儲(chǔ)空間時(shí)

free(s)；48第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

(1)入棧運(yùn)算

PROCEDUREPUSH(S，m，top，x)1.IF(top＝m)THEN{Stack－OVERFLOW；RETURN}2.top＝top＋13.S(top)＝x4.RETURNvoidpush(s，m，top，x)ETs[]，x；

intm，*top；

{if(*top＝＝m){printf("Stack－overflow\n")；return；}*top＝*top＋1；s[*top－1]＝x；

return；

}49第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(2)退棧運(yùn)算PROCEDUREPOP(S，m，top，y)1.IF(top＝0)THEN{Stack－UNDERFLOW；RETURN}2.y＝S(top)3.top＝top－14.RETURNvoidpop(s，m，top，y)ETs[]，*y；

intm，*top；{if(*top＝＝0){printf("Stack－underflow\n")；return；}*y＝s[*top－1]；*top＝*top－1；

return；}50第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(3)讀棧頂元素PROCEDURETOP(S，m，top，y)1.IF(top＝0)THEN{“Stackempty”；RETURN}2.y＝S(top)3.RETURNvoidtop(s，m，top，y)ETs[]，*y；

intm，*top；{if(*top＝＝0){printf("Stackempty\n")；return；}*y＝s[*top－1]；

return；}51第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算3.表達(dá)式的計(jì)算運(yùn)算符棧，用于在表達(dá)式處理過程中存放運(yùn)算符。在開始時(shí)，運(yùn)算符棧中先壓入一個(gè)表達(dá)式結(jié)束符“；”。操作數(shù)棧，用于在表達(dá)式處理過程中存放操作數(shù)。52第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算從左到右依次讀出表達(dá)式中的各個(gè)符號(hào)：若是操作數(shù)，則壓入操作數(shù)棧，依次讀下一個(gè)符號(hào)。若是運(yùn)算符，則作進(jìn)一步判斷：

①若讀出運(yùn)算符的優(yōu)先級(jí)大于運(yùn)算符棧棧頂運(yùn)算符的優(yōu)先級(jí)，則將讀出的運(yùn)算符壓入運(yùn)算符棧，并依次讀下一個(gè)符號(hào)。②若讀出的是表達(dá)式結(jié)束符“；”，且運(yùn)算符棧棧頂?shù)倪\(yùn)算符也是表達(dá)式結(jié)束符“；”，則表達(dá)式處理結(jié)束，最后的計(jì)算結(jié)果在操作數(shù)棧的棧頂位置。③若讀出運(yùn)算符的優(yōu)先級(jí)不大于運(yùn)算符棧棧頂運(yùn)算符的優(yōu)先級(jí)，則從操作數(shù)棧連續(xù)退出兩個(gè)操作數(shù)，并從運(yùn)算符棧退出一個(gè)運(yùn)算符，然后作相應(yīng)的運(yùn)算（運(yùn)算符為剛從運(yùn)算符棧退出的運(yùn)算符，運(yùn)算對(duì)象為剛從操作數(shù)棧退出的兩個(gè)操作數(shù)），并將運(yùn)算結(jié)果壓入操作數(shù)棧。53第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算A＋B*C－D/E；54第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算A＋B*C－D/E；55第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算A＋B*C－D/E；56第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算A＋B*C－D/E；57第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算4.遞歸依次打印輸出自然數(shù)1到n的非遞歸算法

PROCEDUREWRT(n)FORk＝1TOnDOOUTPUTkRETURN依次打印輸出自然數(shù)1到n的遞歸算法

PROCEDUREWRT(n)IF(n≠0)THEN{WRT(n)；OUTPUTn}RETURN58第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

#include"stdio.h"wrt(intn){if(n!＝0)

{wrt(n－1)；

printf("%d\n"，n)；}return；

}59第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.2.3隊(duì)列及其應(yīng)用1.什么是隊(duì)列隊(duì)列(equeue)是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，用尾指針(rear)指向隊(duì)尾元素。允許刪除的一端稱為排頭(也稱隊(duì)頭)，用排頭指針(front)指向排頭元素的前一個(gè)位置。隊(duì)列又稱為“先進(jìn)先出”(FIFO—FirstInFirstOut)或“后進(jìn)后出”(LILO—LastInLastOut)的線性表，體現(xiàn)了“先來先服務(wù)”的原則。往隊(duì)列的隊(duì)尾插入一個(gè)元素稱為入隊(duì)運(yùn)算，從隊(duì)列的排頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算。60第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算61第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.循環(huán)隊(duì)列及其運(yùn)算62第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算63第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算隊(duì)列空的條件為s＝0隊(duì)列滿的條件為(s＝1)且front＝rear64第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算建立循環(huán)隊(duì)列順序存儲(chǔ)空間（即初始化循環(huán)隊(duì)列順序存儲(chǔ)空間）#include"stdlib.h"voidinit_queue(q，m，front，rear，s)ET*q；

intm，*front，*rear，*s；{q＝malloc(m*sizeof(ET))；*front＝m；*rear＝m；*s＝0；

return；}釋放循環(huán)隊(duì)列的順序存儲(chǔ)空間free(q)；65第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(1)入隊(duì)運(yùn)算PROCEDUREADDCQ(Q，m，rear，front，s，x)1.IF(s＝1)and(rear＝front)THEN{Queue－OVERFLOW；RETURN}2.rear＝rear＋13.IF(rear＝m＋1)THENrear＝14.Q(rear)＝x5.s＝16.RETURN66第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算voidaddcq(q，m，rear，front，s，x)ETq[]，x；

intm，*rear，*front，*s；{if((*s＝＝1)&&(*rear＝＝*front)){printf("Queue－OVERFLOW\n")；

return；

}*rear＝*rear＋1；

if(*rear＝＝m＋1)*rear＝1；

q[*rear－1]＝x；*s＝1；return；}67第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(2)退隊(duì)運(yùn)算PROCEDUREDELCQ(Q，m，rear，front，s，y)1.IF(s＝0)THEN{Queue－UNDERFLOW；RETURN}2.front＝front＋13.IF(front＝m＋1)THENfront＝14.y＝Q(front)5.IF(front＝rear)THENs＝06.RETURN68第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算voiddelcq(q，m，rear，front，s，y)ETq[]，*y；

intm，*rear，*front，*s；{if(*s＝＝0){printf("Queue－UNDERFLOW\n")；return；}*front＝*front＋1；

if(*front＝＝m＋1)*front＝1；*y＝q[*front－1]；

if(*front＝＝*rear)*s＝0；

return；}69第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算3.隊(duì)列的應(yīng)用

(1)給工人分配工作的模擬開辟一個(gè)隊(duì)列結(jié)構(gòu)的線性表。設(shè)置一個(gè)排頭指針和一個(gè)隊(duì)尾指針。初始時(shí)隊(duì)列為空。每當(dāng)有一個(gè)工人到調(diào)度員處報(bào)到時(shí)（包括新來的與完成任務(wù)后返回的），都將他加入到隊(duì)尾；當(dāng)需要一名工人去做某項(xiàng)工作時(shí)，就派排頭的工人去做該項(xiàng)工作。70第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(2)輸入輸出緩沖區(qū)的結(jié)構(gòu)71第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(3)汽車加油站的工作模擬

汽車加油站有兩臺(tái)油泵，每臺(tái)油泵為一輛汽車加油的時(shí)間為d分鐘。該加油站的到車率為1輛/g分鐘。用一個(gè)容量為m的循環(huán)隊(duì)列來組織等待加油的汽車，并對(duì)到達(dá)加油站的汽車按先后順序用自然數(shù)給予編號(hào)。假設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間用一維數(shù)組cq(1：m)模擬，初始狀態(tài)為rear＝front＝m，并假定該循環(huán)隊(duì)列不會(huì)發(fā)生隊(duì)列滿的情況。其次，假設(shè)模擬的時(shí)間長(zhǎng)度為time分鐘，并用時(shí)間步長(zhǎng)法進(jìn)行模擬，取采樣時(shí)間間隔為dt，即每隔dt分鐘對(duì)汽車加油站的工作情況測(cè)試一次，同時(shí)輸出汽車排隊(duì)的情況及每臺(tái)油泵的工作情況。72第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算模擬汽車排隊(duì)（SIMUAUTO）一分鐘來一輛車的概率為1/g。在采樣時(shí)間間隔dt分鐘內(nèi)來一輛車的概率為dt/g。要求采樣的時(shí)間間隔dt＜g。在實(shí)際模擬時(shí)，每隔dt分鐘（即每次采樣測(cè)試時(shí)）產(chǎn)生一個(gè)0到1之間均勻分布的隨機(jī)數(shù)rnd。若rnd≤dt/g，則認(rèn)為有一輛車到達(dá)，并將它編號(hào)，加入到循環(huán)隊(duì)列中。PROCEDURESIMUAUTO(CQ，m，rear，num，dt，g，rnd)IF(rnd＜＝dt/g)THEN{num＝num＋1rear＝rear＋1IF(rear＝m＋1)THENrear＝1CQ(rear)＝num}RETURN73第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算模擬油泵工作用標(biāo)志flag(i)表示第i(i＝1，2)臺(tái)油泵的工作進(jìn)程，aut(i)表示第i臺(tái)油泵服務(wù)的對(duì)象（即汽車的編號(hào)）。當(dāng)?shù)趇臺(tái)油泵開始為一輛車加油服務(wù)時(shí)，置工作進(jìn)程標(biāo)志為flag(i)＝d－dt；以后每經(jīng)過dt分鐘，令flag(i)＝flah(i)－dt。當(dāng)flag(i)＜0時(shí)，說明第i臺(tái)油泵剛完成對(duì)一輛汽車的加油服務(wù)，有可以從循環(huán)隊(duì)列的排頭取出一輛汽車進(jìn)行服務(wù)。若此時(shí)隊(duì)列為空，則置油泵為空閑狀態(tài)，即置flag(i)＝074第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算PROCEDURESIMUPUMP(CQ，m，front，rear，dt，d，flag，aut，i)IF(flag(i)＜＝0)THEN{IF(front＝rear)THENflag(i)＝0ELSE{front＝front＋1IF(front＝m＋1)THENfront＝1aut(i)＝cq(front)flag(i)＝d－dt

}}ELSEflag(i)＝flag(i)－dtRETURN75第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算采樣測(cè)試結(jié)果輸出每隔dt分鐘將汽車隊(duì)列的情況以及每臺(tái)油泵的工作情況的模擬結(jié)果打印輸出。PROCEDUREOUT(CQ，m，front，rear，flag，aut)k＝frontWHILE(k≠rear)DO{k＝k＋1IF(k＝m＋1)THENk＝1OUTPUTCQ(k)}OUTPUTflag(1)，aut(1)OUTPUTflag(2)，aut(2)RETURN76第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算在輸出結(jié)果中，分以下兩種情況：當(dāng)aut(i)＞0時(shí)：若flag(i)＞0，

則aut(i)值為油泵i正在服務(wù)的對(duì)象；

若flag(i)＜0，

則aut(i)值為油泵i剛服務(wù)完的對(duì)象；若flag(i)＝0，

則aut(i)值為油泵i已服務(wù)完的對(duì)象。當(dāng)aut(i)＝－1時(shí)，表示油泵i還未服務(wù)過。77第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算主模塊①分配循環(huán)隊(duì)列空間CQ(1：m)，并置循環(huán)隊(duì)列為空。即置front＝rear＝m。②置每臺(tái)油泵為空閑。即置flag(1)＝flag(2)＝0。③置每臺(tái)油泵還無服務(wù)對(duì)象。即置aut(1)＝aut(2)＝－1。78第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算/*主模塊*/#include"stdlib.h"#include"math.h"#include"stdio.h"main(){int*cq，m，front，rear，aut[2]，flag[2]，num；

doubletime，dt，t，g，d，rnd，r＝1.0，s；

m＝10；/*循環(huán)隊(duì)列空間的容量*/

cq＝malloc(m*sizeof(int))；/*分配循環(huán)隊(duì)列的順序存儲(chǔ)空間*/

rear＝m；front＝m；/*初始化循環(huán)隊(duì)列*/

aut[0]＝－1；

aut[1]＝－1；/*置每臺(tái)油泵還未服務(wù)過*/

flag[0]＝0；flag[1]＝0；/*置每臺(tái)油泵為空閑*/num＝0；t＝0；79第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

printf("inputg：")；

scanf("%lf"，&g)；/*輸入來一輛車的平均時(shí)間*/

printf("inputd：")；

scanf("%lf"，&d)；/*輸入油泵為一輛車加油所需要的時(shí)間*/

printf("inputtime：")；

scanf("%lf"，&time)；/*輸入總的模擬時(shí)間長(zhǎng)度*/

printf("inputdt：")；

scanf("%lf"，&dt)；/*輸入采樣時(shí)間間隔*/

printf("－－－－－－－－－－－－－－－－－－－－－－－－－－－\n")；80第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

while(t＜time)/*模擬時(shí)間未結(jié)束*/

{r＝2053.0*r＋13849.0；

s＝(int)(r/65536.0)；

r＝r－s*65536.0；

rnd＝r/65536.0；/*產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)*/

simuauto(cq,m,&rear,&num,dt,g,rnd)；/*模擬汽車排隊(duì)*/

simupump(cq，m，&front，rear，dt，d，flag，aut，1)；

/*模擬油泵1工作*/

simupump(cq，m，&front，rear，dt，d，flag，aut，2)；

/*模擬油泵2工作*/

out(cq，m，front，rear，flag，aut)；/*模擬結(jié)果輸出*/

t＝t＋dt；

}free(cq)；/*釋放循環(huán)隊(duì)列空間*/}81第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算/*模擬汽車排隊(duì)*/simuauto(cq，m，rear，num，dt，g，rnd)intcq[]，m，*rear，*num；doubledt，g，rnd；{if(rnd＜＝dt/g){*num＝*num＋1；*rear＝*rear＋1；

if(*rear＝＝m＋1)*rear＝1；

cq[*rear－1]＝*num；

}}82第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算/*模擬油泵工作*/simupump(cq，m，front，rear，dt，d，flag，aut，i)intcq[]，m，*rear，*front，flag[]，aut[]，i；doubledt，d；{if(flag[i－1]＜＝0){if(*front＝＝rear)flag[i－1]＝0；

else{*front＝*front＋1；

if(*front＝＝m＋1)*front＝1；

aut[i－1]＝cq[*front－1]；

flag[i－1]＝d－dt；

}}elseflag[i－1]＝flag[i－1]－dt；}83第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算/*模擬結(jié)果輸出*/out(cq，m，front，rear，flag，aut)intcq[]，m，front，rear，flag[]，aut[]；{intk；

k＝front；

while(k!＝rear){k＝k＋1；

if(k＝＝m＋1)k＝1；

printf("cq(%d)＝%d\n"，k，cq[k－1])；

}

printf("flag(1)＝%d，aut(1)＝%d\n"，flag[0]，aut[0])；

printf("flag(2)＝%d，aut(2)＝%d\n"，flag[1]，aut[1])；

printf("－－－－－－－－－－－－－－－－－－－－－－－－－－－\n")；}84第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.3線性鏈表及其運(yùn)算2.3.1線性鏈表的基本概念2.3.2線性鏈表的基本運(yùn)算2.3.3循環(huán)鏈表85第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.3.1線性鏈表的基本概念1.線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。86第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算87第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算88第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算89第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算90第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算依次輸出線性鏈表中的各結(jié)點(diǎn)值輸入：線性鏈表的存儲(chǔ)空間V(1：m)、NEXT(1：m)；

線性鏈表的頭指針HEAD。輸出：依次輸出線性鏈表中各結(jié)點(diǎn)的值。

PROCEDUREPRTLL(HEAD)j＝HEADWHILE(j≠0)DO{OUTPUTV(j)；j＝NEXT(j)}RETURN91第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

struct結(jié)構(gòu)體名

{數(shù)據(jù)成員表；

struct結(jié)構(gòu)體名*指針變量名；

}例如

structnode{charname[10]；/*數(shù)據(jù)域*/

charsex；/*數(shù)據(jù)域*/

structnode*next；/*指針域*/}92第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算#include"stdlib.h"/*malloc函數(shù)需要包含頭文件stdlib.h*/structnode/*定義結(jié)點(diǎn)類型*/{intd；/*數(shù)據(jù)域*/

structnode*next；/*指針域*/}main(){structnode*p；/*定義該類型的指針變量p*/…p=(structnode*)malloc(sizeof(structnode))；

/*申請(qǐng)分配結(jié)點(diǎn)存儲(chǔ)空間*/…

free(p)；/*釋放結(jié)點(diǎn)存儲(chǔ)空間*/}93第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算#include"stdlib.h"#include"stdio.h"structnode/*定義結(jié)點(diǎn)類型*/{intd；

structnode*next；

}main(){intx；

structnode*head，*p，*q；

head＝NULL；/*置鏈表空*/

q＝NULL；

scanf(“%d”，&x)；/*輸入一個(gè)正整數(shù)*/94第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

while(x＞0)/*若輸入值大于0*/

{p＝(structnode*)malloc(sizeof(structnode))；/*申請(qǐng)一個(gè)結(jié)點(diǎn)*/

p－>d＝x；p－>next＝NULL；/*置當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域和指針域*/

if(head＝＝NULL)head＝p；/*若鏈表空，則將頭指針指向當(dāng)前結(jié)點(diǎn)p*/elseq－>next＝p；/*將當(dāng)前結(jié)點(diǎn)鏈接在最后*/

q＝p；/*置當(dāng)前結(jié)點(diǎn)為鏈表最后一個(gè)結(jié)點(diǎn)*/

scanf("%d"，&x)；

}p＝head；

while(p!＝NULL)/*從鏈表第一個(gè)結(jié)點(diǎn)開始打印各結(jié)點(diǎn)元素值，并刪除*/{printf("%5d"，p－>d)；/*打印當(dāng)前結(jié)點(diǎn)中的數(shù)據(jù)*/

q＝p；p＝p－>next；free(q)；/*刪除當(dāng)前結(jié)點(diǎn)并釋放該結(jié)點(diǎn)空間*/}

printf("\n")；}95第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算雙向鏈表96第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.帶鏈的棧97第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算可利用棧及其運(yùn)算98第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算將結(jié)點(diǎn)送回可利用棧輸入：可利用棧棧頂指針TOP（默認(rèn)）；送回可利用棧的結(jié)點(diǎn)序號(hào)p。輸出：結(jié)點(diǎn)p入棧后的可利用棧棧頂指針TOP（默認(rèn)）。

PROCEDUREDISPOSE(p)NEXT(p)＝TOP；TOP＝pRETURN從可利用棧取得一個(gè)結(jié)點(diǎn)輸入：可利用棧的棧頂指針TOP（默認(rèn)）。輸出：退棧后的可利用棧棧頂指針TOP（默認(rèn)）；存放取得結(jié)點(diǎn)序號(hào)的變量p。

PROCEDURENEW(p)p＝TOP；TOP＝NEXT(TOP)RETURN99第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算帶鏈棧的入棧運(yùn)算輸入：帶鏈棧的棧頂指針top；入棧的元素值x。輸出：元素x入棧后的帶鏈棧棧頂指針top。

PROCEDUREPUSHLL(top，x)NEW(p)[從可利用棧取得一個(gè)新結(jié)點(diǎn)]

V(p)＝x[置新結(jié)點(diǎn)數(shù)據(jù)域]

NEXT(p)＝top[置新結(jié)點(diǎn)指針域]

top＝p[改變棧頂指針]

RETURN100第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；/*數(shù)據(jù)元素類型*/

structnode*next；

}；pushll(top，x)ETx；

structnode**top；{structnode*p；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝x；p－>next＝*top；/*置新結(jié)點(diǎn)的數(shù)據(jù)域與指針域*/*top＝p；/*改變棧頂指針*/

return；}101第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算帶鏈棧的退棧運(yùn)算輸入：帶鏈棧的棧頂指針top。輸出：退棧后的帶鏈棧棧頂指針top；存放退出結(jié)點(diǎn)元素值的變量y。

PROCEDUREPOPLL(top，y)y＝V(top)[取出棧頂元素值]

p＝toptop=NEXT(p)[改變棧頂指針]

DISPOSE(p)[被刪除結(jié)點(diǎn)送回可利用棧]

RETURN102第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；/*數(shù)據(jù)元素類型*/

structnode*next；

}；popll(top，y)ETy；

structnode**top；{structnode*p；

y＝*top－>d；/*取出棧頂元素值*/

p＝*top；*top＝p－>next；/*改變棧頂指針*/

free(p)；return；/*釋放被刪除結(jié)點(diǎn)后返回*/}103第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算3.帶鏈的隊(duì)列104第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算帶鏈隊(duì)列的入隊(duì)運(yùn)算輸入：帶鏈隊(duì)列的隊(duì)尾指針rear；入隊(duì)的新元素x。輸出：元素x入隊(duì)后的帶鏈隊(duì)列隊(duì)尾指針rear。

PROCEDUREADDLL(rear，x)NEW(p)[從可利用棧取得一個(gè)新結(jié)點(diǎn)p]V(p)＝x[置新結(jié)點(diǎn)的數(shù)據(jù)域]

NEXT(p)＝0[置新結(jié)點(diǎn)的指針為空]

NEXT(rear)＝p[最后一個(gè)結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)]

rear＝p[改變隊(duì)尾指針]

RETURN105第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；/*數(shù)據(jù)元素類型*/

structnode*next；

}；addll(rear，x)ETx；

structnode**rear；{structnode*p；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝x；p－>next＝NULL；/*置新結(jié)點(diǎn)的數(shù)據(jù)域與指針域*/*rear－>next＝p；/*置最后一個(gè)結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)*/

*rear＝p；/*改變隊(duì)尾指針*/return；}106第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算帶鏈隊(duì)列的退隊(duì)運(yùn)算輸入：帶鏈隊(duì)列的排頭指針front。輸出：退隊(duì)后的帶鏈隊(duì)列排頭指針front；存放退出結(jié)點(diǎn)值的變量y。

PROCEDUREDELLL(front，y)y=V(front)[取出排頭元素值]

p＝frontfront＝NEXT(front)[改變排頭指針]

DISPOSE(p)[釋放刪除的結(jié)點(diǎn)]

RETURN107第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；/*數(shù)據(jù)元素類型*/

structnode*next；

}；delll(front，y)ETy；

structnode**front；{structnode*p；

y＝*front－>d；/*取出排頭元素值*/

p＝*front；*front＝p－>next；/*改變排頭指針*/

free(p)；/*釋放被刪除結(jié)點(diǎn)*/

return；}108第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.3.2線性鏈表的基本運(yùn)算(1)在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。(2)在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。(3)將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。(4)將一個(gè)線性鏈表按要求進(jìn)行分解。(5)逆轉(zhuǎn)線性鏈表。(6)復(fù)制線性鏈表。(7)線性鏈表的排序。(8)線性鏈表的查找。109第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1.在線性鏈表中查找指定元素在非空線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)p輸入：非空線性鏈表頭指針HEAD；被尋找元素x。輸出：非空線性鏈表中包含元素x的前一個(gè)結(jié)點(diǎn)p。PROCEDURELOOKST(HEAD，x，p)p＝HEADWHILE(NEXT(p)≠0)and(V(NEXT(p))≠x)DOp＝NEXT(p)RETURN110第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算structnode/*定義結(jié)點(diǎn)類型*/{ETd；/*數(shù)據(jù)元素類型*/

structnode*next；

}；structnode*lookst(head，x)ETx；

structnode*head；{structnode*p；

p＝head；

while((p－>next!＝NULL)&&(((p－>next)－>d)!＝x))

p＝p－>next；

return(p)；}111第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.線性鏈表的插入在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中插入一個(gè)新元素。112第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算可利用棧與線性鏈表113第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(1)從可利用棧取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號(hào)為p。

并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴迦氲脑刂礲，即V(p)＝b。(2)在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)q。114第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(3)將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后：①使結(jié)點(diǎn)p指向包含元素x的結(jié)點(diǎn)，即

NEXT(p)＝NEXT(q)②使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn)p，即

NEXT(q)＝p115第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算線性鏈表的插入輸入：線性鏈表的頭指針HEAD；插入位置處的前一個(gè)結(jié)點(diǎn)值x；插入的新元素b。輸出：插入后的線性鏈表。PROCEDUREINSLST(HEAD，x，b)1.NEW(p)2.V(p)＝b3.IF(HEAD＝0)THEN{HEAD＝p；NEXT(p)＝0；RETURN}4.IF(V(HEAD)＝x)THEN{NEXT(p)＝HEAD；HEAD＝p；RETURN}5.LOOKST(HEAD，x，q)6.NEXT(p)＝NEXT(q)；NEXT(q)＝p7.RETURN116第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；structnode*next；}；inslst(head，x，b)ETx，b；structnode**head；{structnode*p，*q；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝b；/*置結(jié)點(diǎn)的數(shù)據(jù)域*/

if(*head＝＝NULL)/*鏈表為空*/{*head＝p；p－>next＝NULL；return；}if((*head－>d)＝＝x)/*在第一個(gè)結(jié)點(diǎn)前插入*/{p－>next＝*head；*head＝p；return；}q＝lookst(*head，x)；/*尋找包含元素x的前一個(gè)結(jié)點(diǎn)q*/p－>next＝q－>next；q－>next＝p；/*結(jié)點(diǎn)p插到結(jié)點(diǎn)q之后*/

return；}117第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算3.線性鏈表的刪除在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點(diǎn)。118第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算可利用棧與線性鏈表119第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(1)尋找包含元素x的前一個(gè)結(jié)點(diǎn)q。則包含元素x的結(jié)點(diǎn)序號(hào)p＝NEXT(q)。(2)將結(jié)點(diǎn)q后的結(jié)點(diǎn)p刪除，即

NEXT(q)＝NEXT(p)。120第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(3)將包含元素x的結(jié)點(diǎn)p送回可利用棧。121第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算線性鏈表的刪除輸入：線性鏈表的頭指針HEAD；需刪除的元素x。輸出：刪除后的線性鏈表。PROCEDUREDELST(HEAD，x)1.IF(HEAD＝0)THEN{“Thisisaemptylist!”；RETURN}2.IF(V(HEAD)＝x)THEN{p＝NEXT(HEAD)；DISPOSE(HEAD)；HEAD＝p；RETURN}3.LOOKST(HEAD，x，q)4.IF(NEXT(q)＝0)THEN{“Nothisnodeinthelist!”；RETURN}5.p＝NEXT(q)；NEXT(q)＝NEXT(p)6.DISPOSE(p)7.RETURN122第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；structnode*next；}；delst(head，x)ETx；structnode**head；{structnode*p，*q；

if(*head＝＝NULL)/*鏈表為空*/{printf("Thisisaemptylist!\n")；return；}if((*head－>d)＝＝x)/*刪除第一個(gè)結(jié)點(diǎn)*/{p＝*head－>next；free(*head)；*head＝p；return；}q＝lookst(*head，x)；/*尋找包含元素x的前一個(gè)結(jié)點(diǎn)q*/if(q－>next＝＝NULL)/*鏈表中沒有包含元素x的結(jié)點(diǎn)*/{printf("Nothisnodeinthelist!\n")；return；}p＝q－>next；q－>next＝p－>next；/*刪除結(jié)點(diǎn)p*/free(p)；/*釋放結(jié)點(diǎn)p*/return；}123第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.3.3循環(huán)鏈表(1)在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蚋鶕?jù)需要來設(shè)置，指針域指向線性表第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。(2)循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不空，而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。124第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(1)在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)。(2)空表與非空表的運(yùn)算統(tǒng)一。125第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算在頭指針為HEAD的循環(huán)鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)輸入：循環(huán)鏈表的頭指針HEAD；被尋找的元素x。輸出：循環(huán)鏈表中包含元素x的前一個(gè)結(jié)點(diǎn)p。PROCEDURELOOKCST(HEAD，x，p)p＝HEADWHILE(NEXT(p)≠HEAD)and(V(NEXT(p))≠x)DOp＝NEXT(p)RETURN126第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；structnode*next；}；structnode*lookcst(head，x)ETx；

structnode*head；{structnode*p；

p＝head；

while((p－>next!＝head)&&(((p－>next)－>d)!＝x))p＝p－>next；

return(p)；}127第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算在頭指針為HEAD的循環(huán)鏈表中包含元素x的結(jié)點(diǎn)前插入新元素b輸入：循環(huán)鏈表的頭指針HEAD；插入位置處的前一個(gè)結(jié)點(diǎn)值x；插入的新元素b。輸出：插入后的循環(huán)鏈表。PROCEDUREINSCST(HEAD，x，b)NEW(p)[從可利用棧取得一個(gè)新結(jié)點(diǎn)p]V(p)＝b[置新結(jié)點(diǎn)p的數(shù)據(jù)域（插入的元素值b）]LOOKCST(HEAD，x，q)[尋找循環(huán)鏈表中包含元素x的前一個(gè)結(jié)點(diǎn)q]NEXT(p)＝NEXT(q)；NEXT(q)＝p

[將新結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后]RETURN128第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；structnode*next；}；inscst(head，x，b)ETx，b；structnode*head；{structnode*p，*q；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝b；/*置結(jié)點(diǎn)的數(shù)據(jù)域*/

q＝lookcst(head，x)；/*尋找包含元素x的前一個(gè)結(jié)點(diǎn)q*/p－>next＝q－>next；q－>next＝p；/*結(jié)點(diǎn)p插入到結(jié)點(diǎn)q后*/

return；}129第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算在頭指針為HEAD的循環(huán)鏈表中刪除包含元素x的結(jié)點(diǎn)輸入：循環(huán)鏈表的頭指針HEAD；需刪除的元素x。輸出：刪除后的循環(huán)鏈表。PROCEDUREDELCST(HEAD，x)LOOKCST(HEAD，x，q)[尋找包含元素x的前一個(gè)結(jié)點(diǎn)q]IF(NEXT(q)＝HEAD)THEN[循環(huán)鏈表中沒有該結(jié)點(diǎn)]

{“Nothisnodeinthelist!”；RETURN}p＝NEXT(q)；NEXT(q)＝NEXT(p)[刪除結(jié)點(diǎn)q后的結(jié)點(diǎn)]DISPOSE(p)[將被刪除的結(jié)點(diǎn)p送回可利用棧]RETURN130第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；structnode*next；}；delcst(head，x)ETx；structnode*head；{structnode*p，*q；

q＝lookcst(head，x)；/*尋找包含元素x的前一個(gè)結(jié)點(diǎn)q*/if(q－>next＝＝NULL)/*鏈表中沒有包含元素x的結(jié)點(diǎn)*/{printf("Nothisnodeinthelist!\n")；return；}p＝q－>next；q－>next＝p－>next；/*刪除結(jié)點(diǎn)p*/free(p)；/*釋放結(jié)點(diǎn)p*/return；}131第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.4數(shù)組2.4.1數(shù)組的順序存儲(chǔ)結(jié)構(gòu)2.4.2規(guī)則矩陣的壓縮2.4.