線性結(jié)構(gòu)及其應(yīng)用

1、線性結(jié)構(gòu)及其應(yīng)用1線性表的概念線性表（linear_list）是最常用、最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)線性表是n（n0）個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。它具有以下特性：存在唯一的被稱作“第一個(gè)”的數(shù)據(jù)元素；存在唯一的被稱作“最后一個(gè)”的數(shù)據(jù)元素；除第一個(gè)元素外，線性表中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；除最后一個(gè)元素外，每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼；線性表中的數(shù)據(jù)元素可以使多種類型，但同一線性表中的元素必定具有相同特性。即基類型相同。2線性表的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)：用一維數(shù)組來描述const lmaxlen=線性表可能達(dá)到的最大長度；type lelement=線性表數(shù)據(jù)元素的數(shù)據(jù)類型 list=r

2、ecord data:array1.lmaxlen of lelement; last:0.lmaxlen end;3線性表的存儲(chǔ)結(jié)構(gòu)鏈接存儲(chǔ)結(jié)構(gòu)：用指針類型來描述單鏈表：Type datatype=單鏈表中結(jié)點(diǎn)的數(shù)據(jù)類型 link=node; node=record data:dataty; next:link end;4線性表基本操作的實(shí)現(xiàn)順序存儲(chǔ)線性表基本操作的實(shí)現(xiàn)（1）初始化Procedure initial(a:list);Begin a.last:=0;End;(2)求長度Function length(a:list):integer;Begin length:=a.last;En

3、d;5線性表基本操作的實(shí)現(xiàn)（3）獲取元素Procedure getlist(a:list；i:integer；var x:lelement);Begin if (ia.last) then writeln(取數(shù)位置不對(duì)) else if a.last=0 then writeln(表為空) else x:=a.dataiEnd;(4)定位Function loclist(a:list; x:lelement):integer;Begin i:=1; while (i=a.last)and(a.dataix) do i:=i+1; if ilmaxlen then writeln(超出最大長度)

4、； if (ia.last) or (i0) then writeln(插入位置不對(duì))； if (i0)and(a.last+1=lmaxlen) then begin for j:=a.last downto i do a.dataj+1:=a.dataj; a.datai:=x; a.last:=a.last+1 end;End;7線性表基本操作的實(shí)現(xiàn)（6）刪除Procedure dellist(var a:list；i:integer);Var j：integer；Begin if a.last=0 then writeln(表為空)； if (ia.last ) then writel

5、n(刪除位置有錯(cuò))； if (a.last0) and (i0)and(i=a.last) then begin for j:=i+1 to a.last do a.dataj-1:=a.dataj; a.last:=a.last-1; end;End;8線性表基本操作的實(shí)現(xiàn)順序存儲(chǔ)線性表基本操作的實(shí)現(xiàn)（7）判斷線性表是否滿function fulllist(a:list):boolean;Begin if a.last=lmaxlen then fulllist:=true else fulllist:=false;End;(8)判斷線性表是否空Function emplist(a:list

6、):boolean;Begin if a.last=0 then emplist:=true else emplist:=false;End;9線性表基本操作的實(shí)現(xiàn)單鏈表基本操作的實(shí)現(xiàn)（1）初始化New(head); head:=nil;(2)建表 （頭插法建表和尾插法建表） read(ch)； while ch#do begin new(p)；P.data：=ch；Pnext：=head： head：=p；read(ch)； end； P：=head10線性表基本操作的實(shí)現(xiàn)單鏈表基本操作的實(shí)現(xiàn)(2)建表 （頭插法建表和尾插法建表） read(ch)；q：=nil； while ch#do b

7、egin new(p)；Pdata：=ch；Pnext：=nil： if head=nil then begin head：=p；q：=p；end else begin qnext：=p；q：=p；end； read(ch)； end；11線性表基本操作的實(shí)現(xiàn)單鏈表基本操作的實(shí)現(xiàn)(3)單鏈表的遍歷與輸出 P：=head； while pnil do begin write(pdata)；P：=pnext； end；(4)求單鏈表的長度lenlkst(head)function lenlkst(head：link)：integer； Var P：link；i：integer； begin P：=

8、head；i：=0； while Pnextnil do begin i：=i+1；P：=Pnext end； lenlkst：=i； end；12線性表基本操作的實(shí)現(xiàn)單鏈表基本操作的實(shí)現(xiàn)(5)判斷鏈表是否為空(emplkst(head) function emplkst(head：link)：boolean； begin if headNext=nil then emplkst：=true else emplkst：=false end； (6)查找 按序號(hào)查找。 按值查找。read(ch)； P：=head； while(pnil)and(pdatach)do P：=Pnext； if p

9、nil then write(ok) else write(sorry)；13線性表基本操作的實(shí)現(xiàn)單鏈表基本操作的實(shí)現(xiàn) (7)插入元素(inslkst(head，i，x) 將S結(jié)點(diǎn)插在P結(jié)點(diǎn)之后表頭插入。Snext：=headnext；headnext：=s表中插入。Snext：=pnext；Pnext：=S表尾插入。Snext：=nil；Pnext：=s14線性表基本操作的實(shí)現(xiàn)單鏈表基本操作的實(shí)現(xiàn)(8)刪除值為z的結(jié)點(diǎn)表頭刪除。Headnext：=Pnext；dispose(p)；表中刪除。qnext：=pnext；dispose(p)；表尾刪除。qnext：=nil；dispose(p)；

10、procedure delete(var head：pointer；x：integer)；var P，q：pointer； begin if head=nil then writeln(no element)else begin q：=head；p：=headnext； while(pnil)and(pdatax)do begin q：=P；P：=Pnext end； if pnil then begin qnext：=pnext；dispose(p)；end else writeln(not found x) end end；15雙向鏈表基本操作的實(shí)現(xiàn) 單鏈表的特點(diǎn)是任何操作都必須從表頭開始

11、。假如要把一個(gè)鏈表從尾到頭輸出，那效率就太低了，建立雙向鏈表可以解決這一問題。16循環(huán)鏈表基本操作的實(shí)現(xiàn) 利用指針實(shí)現(xiàn)表時(shí)，表中最后一個(gè)元素所在單元的指針域(next)為空指針nil。如果將這個(gè)空指針改為指向表頭單元的指針就使整個(gè)鏈表形成一個(gè)環(huán)。這種首尾相接的鏈表稱為循環(huán)鏈表。在循環(huán)鏈表中，從任意一個(gè)單元出發(fā)可以找到表中其他單元。 (1)單向循環(huán)鏈表 在單鏈表中，將最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn) (2)雙向循環(huán)鏈表 在單向循環(huán)鏈表中，雖然從任一單元出發(fā)，可以找到其前驅(qū)單元，但需要O(n)時(shí)間。如果將雙鏈表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，且頭結(jié)點(diǎn)的前趨指向最后一個(gè)結(jié)點(diǎn)，這樣就構(gòu)成了雙向循環(huán)鏈表17

12、線性表的應(yīng)用1、 【問題描述】 線性表a和b分別表示兩個(gè)線性表，它們的數(shù)據(jù)元素類型相同，現(xiàn)要將b中存在而a中不存在的數(shù)據(jù)元素插入到線性表a中。設(shè)線性表a的長度與線性表b的長度之和不超過線性表a允許的最大長度。 【參考程序】 proceduIre union(var a：list；b：list)； begin n：=length(a)； for i：=1 to length(b)do begin getlist(b，i，x)；取線性表b中第i位上的數(shù)給T k：=loclist(a，x)；返回z在線性表a中的位置 if k=0 then begin inslist(a，n+1，x)；將z插入線性表

13、a的末尾 n：=n+1； end； end； end；18線性表的應(yīng)用2、 【問題描述】 已知線性表。和b中的數(shù)據(jù)元素按遞增的順序排列，現(xiàn)要求將a和b歸并為一個(gè)新的線性表c，c中的數(shù)據(jù)元素仍按遞增排列。用數(shù)組實(shí)現(xiàn)用鏈表實(shí)現(xiàn)19線性表的應(yīng)用3、 Joseph(約瑟夫)問題 【問題描述】 m只猴子要選大王，選舉辦法如下：所有猴子按1m編號(hào)圍坐一圈，從第1號(hào)開始按順序1，2，n報(bào)數(shù)，凡報(bào)到竹的猴子退出到圈外，如此循環(huán)，直到圈內(nèi)只剩下一只猴子時(shí)，這只猴子就是大王。 m和咒由鍵盤輸入，打印出最后剩下的那只猴子的編號(hào)。 運(yùn)行示例： Input m，n：8 3 The monkey king is no7

14、用數(shù)組實(shí)現(xiàn) 【算法分析】 在確定程序設(shè)計(jì)方法之前首先來考慮如何組織數(shù)據(jù)，由于要記錄m只猴子的狀態(tài)，可利用含m個(gè)元素的數(shù)組monkey來實(shí)現(xiàn)。利用元素下標(biāo)代表猴子的編號(hào)，元素的值表示猴子的狀態(tài)，用monkeyEk=l表示第k只猴子仍在圈中，monkeyEk-=0則表示第k只猴子已經(jīng)出圈。程序采用模擬選舉過程的方法，開始時(shí)將報(bào)數(shù)變量count置為1；用變量current表示當(dāng)前報(bào)數(shù)的猴子的編號(hào)，初始時(shí)也置為1；變量。out記錄出圈猴子數(shù)。當(dāng)count=n時(shí)，對(duì)當(dāng)前報(bào)數(shù)的猴子做出圈處理，即monkeycurrent：=O，count：=0,out：=out+1。然后繼續(xù)往下報(bào)數(shù)，直到圈中只剩一只猴子

15、為止(即out=m-1)。20 用數(shù)組實(shí)現(xiàn) 【算法分析】 在組織數(shù)據(jù)時(shí)，也可以考慮只記錄仍在圈中的猴子的情況。用一個(gè)線性表按編號(hào)由小到大依次記錄圈中所有猴子的編號(hào)，每當(dāng)有猴子出圈時(shí)，即從線性表中刪除對(duì)應(yīng)元素，表中元素減少一個(gè)。程序中用變量rest表示圈中剩余的猴子數(shù)，即線性表中元素的總數(shù)。用單向循環(huán)鏈表實(shí)現(xiàn) 【算法分析】結(jié)點(diǎn)的數(shù)據(jù)域?yàn)楹镒拥木幪?hào)，指針域指向下一個(gè)猴子。報(bào)數(shù)實(shí)際上是計(jì)數(shù)，只要設(shè)一個(gè)計(jì)數(shù)器就可以了。當(dāng)計(jì)數(shù)器由0變化到n時(shí)，刪除該結(jié)點(diǎn)，計(jì)數(shù)器回0繼續(xù)計(jì)數(shù)(或者用求余運(yùn)算)。直到鏈表中剩下一個(gè)結(jié)點(diǎn)。21線性表的應(yīng)用4、 一元多項(xiàng)式加減運(yùn)算 【問題描述】 給定一個(gè)一元n次多項(xiàng)式p和一個(gè)一元m次多項(xiàng)式Q，求它們的和與差?！舅惴ǚ治觥?選方法。遍歷兩個(gè)單鏈表根據(jù)指數(shù)和系數(shù)進(jìn)行相應(yīng)的加減，生成一個(gè)新鏈表系數(shù)為0的結(jié)點(diǎn)刪除掉(或不生成這種結(jié)點(diǎn))，輸出該鏈表。22特殊線性結(jié)構(gòu)棧 棧(stack)是一種特殊的線性表，這種線性表限定其只能在表尾進(jìn)行插入或刪除數(shù)據(jù)元素。23括號(hào)匹配【問題描述】 假設(shè)一個(gè)表達(dá)式由英文字母(小寫)、運(yùn)算符(+，一，*，)和左右小(圓)括號(hào)構(gòu)成，以“”作為表達(dá)式的結(jié)束符。請(qǐng)編寫一個(gè)程序檢查表達(dá)式中的左右圓括號(hào)是否匹配，若匹配，則返回“圣”，否則返回“NO。假設(shè)表達(dá)式長度小于255，左圓括號(hào)少于20個(gè)。 【算法分析】 將輸人的字符串存儲(chǔ)