數(shù)據(jù)結(jié)構(gòu)-第2章-線性表

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

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

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

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

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

6、增加一個查找的記錄t 從表首開始1i 第i個記錄的值是否等于t？in?查找成功查找失敗結(jié)束1 iiNYYN第第2 2章章 線性表線性表無序線性表的查找算法如下：/* 無序線性表的查找算法 */ ESEARCH(v,n,t)/* v是無序線性表，n是線性表的長度，t是被查找的記錄 */ int i; vn+1=t; /* 建立無序查找的結(jié)束標志 */ 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 有序線性表的查找算法框圖開始讀入一個查找的記錄t末尾增加一個最大值 從表首開始1i 第i個記錄的值小于t？相等否？查找失敗查找成功結(jié)束1iiNYYN第第2 2章章 線性表線性表有序線性表的查找算法如下： /* 有序線性表的查找算法 */EGSEARCH(v, n,t )/* v是有序線性表，n是線性表的長度，t是被查找的記錄 */char search6; int i; vn+1=;/* 設(shè)置查找的結(jié)束標志 */ 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開始讀入數(shù)據(jù)t調(diào)用查找算法t是否在表中？調(diào)用刪除算法結(jié)束表中無此元素NY第第2 2章章 線性表線性表下面給出相應(yīng)的算法。A1(v, n, t)/* v是有序線性表，n是表長，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( 查無此元素)；假設(shè)一個有30名職工的小型企業(yè)和表2-2所示的工資管理項目。第第2 2章章 線性表線性表表2-2 工資管理項目表工 號 基本工資 附加工資 病 假 車 貼 物價補貼 應(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è)對職工工資管理的要求如下：(1) 能輸出全部職工的工資清單；(2) 能查詢和輸出指定工號職工有關(guān)工資的全部信息；(3) 能修改指定工號職工有關(guān)工資項的內(nèi)容；

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

11、工資單如表2-2第一行所示，其中：第第2 2章章 線性表線性表a(1,1)=1，表示工號為1號；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，表示本月車貼為4.50元；a(1,6)=30.00，表示物價補貼為30.00元；a(1,7)=219.50，表示a(1,2)+a(1,3)+a(1,4)+a(1,5)+a(1,6)的總計，即本月工號為1號的職工的應(yīng)得工資為219.50元。也就是數(shù)組中每一行表示某個工號職工的工資情況。第第2 2章章 線性表線性表為了

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

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

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

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

16、; return;change( )第第2 2章章 線性表線性表/* 修改指定工號的工資項內(nèi)容過程 */ 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ù)項內(nèi)容 */ printf(input which kind change); scanf(%d, &

17、m);/* 輸入需修改的某工資數(shù)據(jù)項 */ 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 ( )/* 在工資表中增加一名職工工號的過程 */ int t; clrscr( ); t=0; printf(input you want add man#); scanf(%d, &a

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

19、 */ else printf(have this man); return;第第2 2章章 線性表線性表del( )/* 刪除某一工號職工的工資表 */ int t,i,k; clrscr( ); printf(input delete man#); scanf(%d, &inx);/* 輸入刪除職工的工號 */ i=1;t=0;/* t為刪除指定職工是否成功的標志位 */ 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、; /* 整個工資表從endx開始向上移位 */ 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ù)重新寫入文件 */ 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