数据结构-第2章-线性表

1、第第2 2章章 线性表线性表第第2 2章章 线性表线性表2.1 2.1 线性表的逻辑结构线性表的逻辑结构 2.2 2.2 线性表的顺序存储结构表示线性表的顺序存储结构表示2.3 2.3 线性表元素的操作线性表元素的操作2.4 2.4 线性表应用举例线性表应用举例2.5 2.5 小结小结 习题习题2 2 第第2 2章章 线性表线性表2.1 2.1 线性表的逻辑结构线性表的逻辑结构2.1.1 线性表的定义线性表是由n个数据元素的有限序列(a1，a2，an)组成的，其中每一个数据元素ai的具体含义可以按不同的情况和要求定义具体的内容，它可以是一个数、一个符号、一串文字，甚至是其他更复杂的信息。例如，

2、英文字母表(A, B, C, , X, Y, Z)是一个线性表，其中的数据元素是单个字母。又如，某企业职工的姓名可构造成一个线性表，表中元素是姓名。以上的线性表类型主要表示单一的数据元素。较复杂的线性表中，一个数据元素可以由若干个数据项组成。我们常把由多个数据项组成的数据元素称作记录(Record)。 第第2 2章章 线性表线性表例如，一个班级某门学科的成绩单可构成一个线性表，如表2-1所示，表中每一个记录包含三个数据项：学号、姓名、数据结构。其中用以区别各个记录或数据元素的数据项的值称为关键字(KEY)。在表2-1中，关键字可选用学号，因为学号可以惟一地标识每一个学生，从而排除了选姓名时同名

3、同姓的非惟一性。综合上述例子，我们可以用如下形式来描述线性表：一个线性表是n(n0)个数据元素a1，a2，an的有限序列。若n=0，则表示一个空表，表示无数据元素；若n0，则每个ai代表一个结点，除a1和an外，有且仅有一个直接前趋和一个直接后继数据元素，第第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个位置已经给出。 第第2 2章章 线性表线性表图2-5 有序线性表的删除开始被删除内容送out将第i1个元素到第n个元素逐个向前移动一个位置(循环) 修正表长1nn结束第第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)所示的是无序线性表，其数据元素在线性表中的存放是任意的；图2-6(b)所示的是有序线性表，其数据元素的排列按英文字母的字母顺序从小到大存放。有序线性表有如下特点，设V为有序线性表，数据元素ai值的相邻关系为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?查找成功查找失败结束1 iiNYYN第第2 2章章 线性表线性表无序线性表的查找算法如下：/* 无序线性表的查找算法 */ ESEARCH(v,n,t)/* v是无序线性表，n是线性表的长度，t是被查找的记录 */ int i; vn+1=t; /* 建立无序查找的结束标志 */ 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？相等否？查找失败查找成功结束1iiNYYN第第2 2章章 线性表线性表有序线性表的查找算法如下： /* 有序线性表的查找算法 */EGSEARCH(v, n,t )/* v是有序线性表，n是线性表的长度，t是被查找的记录 */char search6; int i; vn+1=;/* 设置查找的结束标志 */ i=1; 第第2 2章章 线性表线性表while(vit) i+; if(vi=t) printf(search,true); else printf(search,

8、 false);第第2 2章章 线性表线性表2.4 2.4 线性表应用举例线性表应用举例图2-9给出了在有序线性表中查找并删除数据元素t的程序流程框图。第第2 2章章 线性表线性表图2-9 在线性表中查找并删除元素t开始读入数据t调用查找算法t是否在表中？调用删除算法结束表中无此元素NY第第2 2章章 线性表线性表下面给出相应的算法。A1(v, n, t)/* v是有序线性表，n是表长，t是需删除的数据元素 */ 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( 查无此元素)；假设一个有30名职工的小型企业和表2-2所示的工资管理项目。第第2 2章章 线性表线性表表2-2 工资管理项目表工 号 基本工资 附加工资 病 假 车 贴 物价补贴 应得工资 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章章 线性表线性表企业对职工工资管理的要求如下：(1) 能输出全部职工的工资清单；(2) 能查询和输出指定工号职工有关工资的全部信息；(3) 能修改指定工号职工有关工资项的内容；

10、(4) 能在工资总表中增加某一职工的工资内容并计算其应得工资；(5) 能从工资总表中删除指定职工的全部工资项内容。 第第2 2章章 线性表线性表在完成工资管理的应用程序时，首先必须选择一个合适的数据结构，这将有助于工资管理应用程序的实现。我们以线性表中的二维数组来体现这张工资表。考虑到职工人数的增加，设企业的最多职工数为30人，工资项目为7项，分别为工号、基本工资、附加工资、病假、车贴、物价补贴、应得工资，每一维相当于一个线性表。设数组a(30,7)为工资表，其中第1列到第7列分别对应工号、基本工资、附加工资、病假、车贴、物价补贴、应得工资。每一行表示某一职工的工资情况，例如工号为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，表示病假应扣除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号的职工的应得工资为219.50元。也就是数组中每一行表示某个工号职工的工资情况。第第2 2章章 线性表线性表为了

12、使程序结构清晰、明了，本例采用结构化的程序设计方式，用过程调用的方法实现设计要求，同时还采用菜单方式实现功能的调用。在程序设计中，有以下几个过程函数：(1)查找过程find：查询某工号职工的工资状况。(2) 修改过程change：修改某工号职工的工资项内容。(3) 增加工资项过程add：在工资单上增加某职工的工资项。(4) 删除工资项过程del：在工资单中删除某职工的工资项。(5) 列清单过程list：列出全部职工工资单。图2-10所示为工资管理程序的总框图。 第第2 2章章 线性表线性表图2-10 工资管理程序总框图开始结束查询修改增加工资项删除职工列清单结束NY第第2 2章章 线性表线性表

13、图2-11所示是查询某一职工工资项的程序框图。该框图中设置了一个查询是否成功的状态标志位，以便表示所查询的职工工号是否在本工资表内。图2-12所示是某职工工资表项目中工资项发生变化并进行修改的框图。在该过程中，若被修改工资项的职工工号在工资表中，则可以通过选择工号来修改某工资项的内容。第第2 2章章 线性表线性表图2-11 查询某职工工资的算法框图 开始清屏输入查询职工工号设置查询是否成功标志循环查询该职工工号是否在工资表中该职工工号是否在表中？输出该职工工资单结束该职工不在表中NY第第2 2章章 线性表线性表 图2-12 修改某职工工资的算法框图 开始清屏输入修改职工工号设置修改职工工号是否

14、在工资表中的状态标志位循环查找修改工资职工工号是否在工资表中修改职工工号是否在工资表中？修改该职工的工资项目结束该职工不在表中NY第第2 2章章 线性表线性表在工资表中增加和删除职工的算法框图和输出全部职工工资清单的算法框图请读者自行分析。下面给出模拟企业的工资管理程序。#include#includeint a318,i,j,m,n,inx,tt,x,endx; /* 职工工资表 */char aa;FILE*f1,*fopen( );/* 以数据文件形式建立工资表的各数据项 */第第2 2章章 线性表线性表find( )/* 查询某职工工号的工资情况 */ int t;clrscr( );

15、/* 清屏 */t=0;/* 设置被查询职工是否在工资表中的状态标志位 */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;/* 表示查询工号在工资表内 */ for(j=1;j=7;j+) printf(%5d, aij);/* 输出该工号的全部工资项内容 */ i+;if(t!=1) printf(have not this man)

16、; return;change( )第第2 2章章 线性表线性表/* 修改指定工号的工资项内容过程 */ 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);/* 显示被修改职工的原数据项内容 */ printf(input which kind change); scanf(%d, &

17、m);/* 输入需修改的某工资数据项 */ printf(input change data); scanf(%d, &n);/* 输入修改后的新数据 */ 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;/* 查询输入的工号是否与工资表中的工号重复 */第第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;/* 计算所增加工号的应得工资

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);/* 输出(显示)工资表的全部数据 */ printf(*); return;第第2 2章

21、章 线性表线性表main( ) int r; clrscr( ); printf(do you want to write file again y/n); /* 是否需要把数据重新写入文件 */ scanf(%c, &aa); if(aa=y)(aa=Y)第第2 2章章 线性表线性表 f1=fopen(gidata.dat, w); printf(how many man in this file); /* 工资表的职工人数是多少 */ 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