1、第第2 2章章 線性表線性表第第2 2章章 線性表線性表2.1 2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 2.2 2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)表示線性表的順序存儲(chǔ)結(jié)構(gòu)表示2.3 2.3 線性表元素的操作線性表元素的操作2.4 2.4 線性表應(yīng)用舉例線性表應(yīng)用舉例2.5 2.5 小結(jié)小結(jié) 習(xí)題習(xí)題2 2 第第2 2章章 線性表線性表2.1 2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)2.1.1 線性表的定義線性表是由n個(gè)數(shù)據(jù)元素的有限序列(a1，a2，an)組成的，其中每一個(gè)數(shù)據(jù)元素ai的具體含義可以按不同的情況和要求定義具體的內(nèi)容，它可以是一個(gè)數(shù)、一個(gè)符號(hào)、一串文字，甚至是其他更復(fù)雜的信息。例如，

2、英文字母表(A, B, C, , X, Y, Z)是一個(gè)線性表，其中的數(shù)據(jù)元素是單個(gè)字母。又如，某企業(yè)職工的姓名可構(gòu)造成一個(gè)線性表，表中元素是姓名。以上的線性表類(lèi)型主要表示單一的數(shù)據(jù)元素。較復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。我們常把由多個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素稱(chēng)作記錄(Record)。 第第2 2章章 線性表線性表例如，一個(gè)班級(jí)某門(mén)學(xué)科的成績(jī)單可構(gòu)成一個(gè)線性表，如表2-1所示，表中每一個(gè)記錄包含三個(gè)數(shù)據(jù)項(xiàng)：學(xué)號(hào)、姓名、數(shù)據(jù)結(jié)構(gòu)。其中用以區(qū)別各個(gè)記錄或數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)的值稱(chēng)為關(guān)鍵字(KEY)。在表2-1中，關(guān)鍵字可選用學(xué)號(hào)，因?yàn)閷W(xué)號(hào)可以惟一地標(biāo)識(shí)每一個(gè)學(xué)生，從而排除了選姓名時(shí)同名

3、同姓的非惟一性。綜合上述例子，我們可以用如下形式來(lái)描述線性表：一個(gè)線性表是n(n0)個(gè)數(shù)據(jù)元素a1，a2，an的有限序列。若n=0，則表示一個(gè)空表，表示無(wú)數(shù)據(jù)元素；若n0，則每個(gè)ai代表一個(gè)結(jié)點(diǎn)，除a1和an外，有且僅有一個(gè)直接前趨和一個(gè)直接后繼數(shù)據(jù)元素，第第2 2章章 線性表線性表即ai(其中1 i=i; j-) vj+1=vj;/* 從表末元素到序號(hào)為i的元素逐個(gè)下移 */ vi=t; /* 新元素插入 */ n+;/* 修正表長(zhǎng) */ else vl=t; n=1; /* 表空，插入元素為線性表的第一個(gè)元素 */ 第第2 2章章 線性表線性表2.3.2 線性表元素刪除操作 圖2-5給出了

4、在有序線性表中刪除一個(gè)元素的框圖，其中被刪除元素所在的第i個(gè)位置已經(jīng)給出。 第第2 2章章 線性表線性表圖2-5 有序線性表的刪除開(kāi)始被刪除內(nèi)容送out將第i1個(gè)元素到第n個(gè)元素逐個(gè)向前移動(dòng)一個(gè)位置(循環(huán)) 修正表長(zhǎng)1nn結(jié)束第第2 2章章 線性表線性表下面給出有序線性表刪除一個(gè)元素的算法，被刪除的元素被保留在out中以防丟失。/* 有序線性表元素的刪除 */DELEGLIST(v, i, n)/* v是有序線性表，i是被刪除元素的位置，n是線性表的長(zhǎng)度 */ int j; out=vi; for(j=i;j=n-1; j+) vj=vj+1;/* 從i+1到n位置上的元素逐個(gè)上移 */ n-

5、;第第2 2章章 線性表線性表2.3.3 線性表元素定位操作圖2-6(a)所示的是無(wú)序線性表，其數(shù)據(jù)元素在線性表中的存放是任意的；圖2-6(b)所示的是有序線性表，其數(shù)據(jù)元素的排列按英文字母的字母順序從小到大存放。有序線性表有如下特點(diǎn)，設(shè)V為有序線性表，數(shù)據(jù)元素ai值的相鄰關(guān)系為ai-1aiai+1。圖2-7所示是在無(wú)序線性表上進(jìn)行查找的流程圖。第第2 2章章 線性表線性表 圖2-6 無(wú)序和有序線性表(a) 無(wú)序線性表；(b) 有序線性表1c2a3f4m5n6e7h(a)(b)1a2c3e4f5h6m7n第第2 2章章 線性表線性表圖2-7 無(wú)序線性表的查找算法框圖開(kāi)始讀入一個(gè)查找的記錄t末尾

6、增加一個(gè)查找的記錄t 從表首開(kāi)始1i 第i個(gè)記錄的值是否等于t？in?查找成功查找失敗結(jié)束1 iiNYYN第第2 2章章 線性表線性表無(wú)序線性表的查找算法如下：/* 無(wú)序線性表的查找算法 */ ESEARCH(v,n,t)/* v是無(wú)序線性表，n是線性表的長(zhǎng)度，t是被查找的記錄 */ int i; vn+1=t; /* 建立無(wú)序查找的結(jié)束標(biāo)志 */ i=1; while(vi!=t) i+; 第第2 2章章 線性表線性表if(i=n) return(search, true); else return(search, false);圖2-8給出了有序線性表的查找算法框圖。第第2 2章章 線性表

7、線性表圖2-8 有序線性表的查找算法框圖開(kāi)始讀入一個(gè)查找的記錄t末尾增加一個(gè)最大值 從表首開(kāi)始1i 第i個(gè)記錄的值小于t？相等否？查找失敗查找成功結(jié)束1iiNYYN第第2 2章章 線性表線性表有序線性表的查找算法如下： /* 有序線性表的查找算法 */EGSEARCH(v, n,t )/* v是有序線性表，n是線性表的長(zhǎng)度，t是被查找的記錄 */char search6; int i; vn+1=;/* 設(shè)置查找的結(jié)束標(biāo)志 */ i=1; 第第2 2章章 線性表線性表while(vit) i+; if(vi=t) printf(search,true); else printf(search,

8、 false);第第2 2章章 線性表線性表2.4 2.4 線性表應(yīng)用舉例線性表應(yīng)用舉例圖2-9給出了在有序線性表中查找并刪除數(shù)據(jù)元素t的程序流程框圖。第第2 2章章 線性表線性表圖2-9 在線性表中查找并刪除元素t開(kāi)始讀入數(shù)據(jù)t調(diào)用查找算法t是否在表中？調(diào)用刪除算法結(jié)束表中無(wú)此元素NY第第2 2章章 線性表線性表下面給出相應(yīng)的算法。A1(v, n, t)/* v是有序線性表，n是表長(zhǎng)，t是需刪除的數(shù)據(jù)元素 */ int i; vn+1=; i=1; while(vit) i+; /* 在有序線性表v中，查找t在表中的位置 */第第2 2章章 線性表線性表if(vi=t) for(j=i; j

9、=n-1; j+) vj=vj+1; n-; else printf( 查無(wú)此元素)；假設(shè)一個(gè)有30名職工的小型企業(yè)和表2-2所示的工資管理項(xiàng)目。第第2 2章章 線性表線性表表2-2 工資管理項(xiàng)目表工 號(hào) 基本工資 附加工資 病 假 車(chē) 貼 物價(jià)補(bǔ)貼 應(yīng)得工資 1 150.00 40.00 ?4.00 4.50 30.00 219.50 10 136.00 30.00 0 5.00 30.00 201.00 第第2 2章章 線性表線性表企業(yè)對(duì)職工工資管理的要求如下：(1) 能輸出全部職工的工資清單；(2) 能查詢(xún)和輸出指定工號(hào)職工有關(guān)工資的全部信息；(3) 能修改指定工號(hào)職工有關(guān)工資項(xiàng)的內(nèi)容；

10、(4) 能在工資總表中增加某一職工的工資內(nèi)容并計(jì)算其應(yīng)得工資；(5) 能從工資總表中刪除指定職工的全部工資項(xiàng)內(nèi)容。 第第2 2章章 線性表線性表在完成工資管理的應(yīng)用程序時(shí)，首先必須選擇一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)，這將有助于工資管理應(yīng)用程序的實(shí)現(xiàn)。我們以線性表中的二維數(shù)組來(lái)體現(xiàn)這張工資表。考慮到職工人數(shù)的增加，設(shè)企業(yè)的最多職工數(shù)為30人，工資項(xiàng)目為7項(xiàng)，分別為工號(hào)、基本工資、附加工資、病假、車(chē)貼、物價(jià)補(bǔ)貼、應(yīng)得工資，每一維相當(dāng)于一個(gè)線性表。設(shè)數(shù)組a(30,7)為工資表，其中第1列到第7列分別對(duì)應(yīng)工號(hào)、基本工資、附加工資、病假、車(chē)貼、物價(jià)補(bǔ)貼、應(yīng)得工資。每一行表示某一職工的工資情況，例如工號(hào)為1號(hào)的職工的

11、工資單如表2-2第一行所示，其中：第第2 2章章 線性表線性表a(1,1)=1，表示工號(hào)為1號(hào)；a(1,2)=150.00，表示基本工資為150.00元；a(1,3)=40.00，表示附加工資為40.00元；a(1,4)=-4.00，表示病假應(yīng)扣除4.00元；a(1,5)=4.50，表示本月車(chē)貼為4.50元；a(1,6)=30.00，表示物價(jià)補(bǔ)貼為30.00元；a(1,7)=219.50，表示a(1,2)+a(1,3)+a(1,4)+a(1,5)+a(1,6)的總計(jì)，即本月工號(hào)為1號(hào)的職工的應(yīng)得工資為219.50元。也就是數(shù)組中每一行表示某個(gè)工號(hào)職工的工資情況。第第2 2章章 線性表線性表為了

12、使程序結(jié)構(gòu)清晰、明了，本例采用結(jié)構(gòu)化的程序設(shè)計(jì)方式，用過(guò)程調(diào)用的方法實(shí)現(xiàn)設(shè)計(jì)要求，同時(shí)還采用菜單方式實(shí)現(xiàn)功能的調(diào)用。在程序設(shè)計(jì)中，有以下幾個(gè)過(guò)程函數(shù)：(1)查找過(guò)程find：查詢(xún)某工號(hào)職工的工資狀況。(2) 修改過(guò)程change：修改某工號(hào)職工的工資項(xiàng)內(nèi)容。(3) 增加工資項(xiàng)過(guò)程add：在工資單上增加某職工的工資項(xiàng)。(4) 刪除工資項(xiàng)過(guò)程del：在工資單中刪除某職工的工資項(xiàng)。(5) 列清單過(guò)程list：列出全部職工工資單。圖2-10所示為工資管理程序的總框圖。 第第2 2章章 線性表線性表圖2-10 工資管理程序總框圖開(kāi)始結(jié)束查詢(xún)修改增加工資項(xiàng)刪除職工列清單結(jié)束NY第第2 2章章 線性表線性表

13、圖2-11所示是查詢(xún)某一職工工資項(xiàng)的程序框圖。該框圖中設(shè)置了一個(gè)查詢(xún)是否成功的狀態(tài)標(biāo)志位，以便表示所查詢(xún)的職工工號(hào)是否在本工資表內(nèi)。圖2-12所示是某職工工資表項(xiàng)目中工資項(xiàng)發(fā)生變化并進(jìn)行修改的框圖。在該過(guò)程中，若被修改工資項(xiàng)的職工工號(hào)在工資表中，則可以通過(guò)選擇工號(hào)來(lái)修改某工資項(xiàng)的內(nèi)容。第第2 2章章 線性表線性表圖2-11 查詢(xún)某職工工資的算法框圖 開(kāi)始清屏輸入查詢(xún)職工工號(hào)設(shè)置查詢(xún)是否成功標(biāo)志循環(huán)查詢(xún)?cè)撀毠すぬ?hào)是否在工資表中該職工工號(hào)是否在表中？輸出該職工工資單結(jié)束該職工不在表中NY第第2 2章章 線性表線性表 圖2-12 修改某職工工資的算法框圖 開(kāi)始清屏輸入修改職工工號(hào)設(shè)置修改職工工號(hào)是否

14、在工資表中的狀態(tài)標(biāo)志位循環(huán)查找修改工資職工工號(hào)是否在工資表中修改職工工號(hào)是否在工資表中？修改該職工的工資項(xiàng)目結(jié)束該職工不在表中NY第第2 2章章 線性表線性表在工資表中增加和刪除職工的算法框圖和輸出全部職工工資清單的算法框圖請(qǐng)讀者自行分析。下面給出模擬企業(yè)的工資管理程序。#include#includeint a318,i,j,m,n,inx,tt,x,endx; /* 職工工資表 */char aa;FILE*f1,*fopen( );/* 以數(shù)據(jù)文件形式建立工資表的各數(shù)據(jù)項(xiàng) */第第2 2章章 線性表線性表find( )/* 查詢(xún)某職工工號(hào)的工資情況 */ int t;clrscr( );

15、/* 清屏 */t=0;/* 設(shè)置被查詢(xún)職工是否在工資表中的狀態(tài)標(biāo)志位 */printf(input you want find man);scanf(%d, &inx);/* inx為輸入查詢(xún)職工的工號(hào) */i=1;while(t!=1)&(i=endx)/* endx為工資表中最末一個(gè)職工的工號(hào) */第第2 2章章 線性表線性表 if(ai1=inx) t=1;/* 表示查詢(xún)工號(hào)在工資表內(nèi) */ for(j=1;j=7;j+) printf(%5d, aij);/* 輸出該工號(hào)的全部工資項(xiàng)內(nèi)容 */ i+;if(t!=1) printf(have not this man)

16、; return;change( )第第2 2章章 線性表線性表/* 修改指定工號(hào)的工資項(xiàng)內(nèi)容過(guò)程 */ int t; clrscr( ); t=0; printf(input you want change man#); scanf(%d, &inx); i=1; while(t!=1)&(i=endx)第第2 2章章 線性表線性表 if(ail=inx) for(j=1; j=7;j+) printf(a%d=%5dn, j, aij);/* 顯示被修改職工的原數(shù)據(jù)項(xiàng)內(nèi)容 */ printf(input which kind change); scanf(%d, &

17、m);/* 輸入需修改的某工資數(shù)據(jù)項(xiàng) */ printf(input change data); scanf(%d, &n);/* 輸入修改后的新數(shù)據(jù) */ aim=n;ai7=0;第第2 2章章 線性表線性表 for(j=2;j=6;j+) ai7+=aij; t=1; i+; if(t!=1) printf(have not this man); return;第第2 2章章 線性表線性表add ( )/* 在工資表中增加一名職工工號(hào)的過(guò)程 */ int t; clrscr( ); t=0; printf(input you want add man#); scanf(%d, &a

18、mp;inx);/* 輸入需增加一個(gè)職工的工號(hào) */ for(i=1;i=endx;i+) if(ail=inx) t=1;/* 查詢(xún)輸入的工號(hào)是否與工資表中的工號(hào)重復(fù) */第第2 2章章 線性表線性表 if(t!=1) i=endx+1;endx=i; /* 修正工資表的長(zhǎng)度 */ printf(go on input data); for(j=1;j=6;j+) printf(a%d=, j); scanf(%d, &aij);/* 輸入所增加工號(hào)的各工資項(xiàng) */ai7=0;第第2 2章章 線性表線性表for(j=2;j=6;j+) ai7+=aij;/* 計(jì)算所增加工號(hào)的應(yīng)得工資

19、 */ else printf(have this man); return;第第2 2章章 線性表線性表del( )/* 刪除某一工號(hào)職工的工資表 */ int t,i,k; clrscr( ); printf(input delete man#); scanf(%d, &inx);/* 輸入刪除職工的工號(hào) */ i=1;t=0;/* t為刪除指定職工是否成功的標(biāo)志位 */ while(i=endx)&(t!=1)第第2 2章章 線性表線性表 if(ail=inx) t=1;endx-; for(j=1;j=endx;j+) for(k=1;k=7;k+) ajk=aj+1k

20、; /* 整個(gè)工資表從endx開(kāi)始向上移位 */ printf(delete finish); 第第2 2章章 線性表線性表i+; if(t!=1) printf(have not this man); return;list( )/* 顯示工資清單 */ clrscr( ); printf(#a1 a2 a3 a4 a5 a6);第第2 2章章 線性表線性表printf(*); for(i=1;i=endx;i+) for(j=1;j=7;j+) printf(%5d, aij); printf(n);/* 輸出(顯示)工資表的全部數(shù)據(jù) */ printf(*); return;第第2 2章

21、章 線性表線性表main( ) int r; clrscr( ); printf(do you want to write file again y/n); /* 是否需要把數(shù)據(jù)重新寫(xiě)入文件 */ scanf(%c, &aa); if(aa=y)(aa=Y)第第2 2章章 線性表線性表 f1=fopen(gidata.dat, w); printf(how many man in this file); /* 工資表的職工人數(shù)是多少 */ scanf(%d, &inx); endx=inx; for(i=1;i=endx,i+) for(j=1;j=7;j+) printf(a

22、%d%d=, i, j); scanf(%d, &aij); printf(f1, %d, aij); 第第2 2章章 線性表線性表 printf(n); else f1=fopen(gidata.dat, r); i=1; while(!feof(f1) for(j=1; j=7; j+) scanf(f1, %d, &aij); i+; 第第2 2章章 線性表線性表 endx=i-1;tt=0;fclose(f1);while(tt!=1) clrscr( ); puts(*); puts( 1.find one ); puts( 2.change ); puts( 3.add one ); puts( 4.del one ); puts( 5.list one );第第2 2章章 線性表線性表puts( 6.end ); puts