注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

潘凌云的博客

简单的我 快乐的教学 快乐的生活

 
 
 

日志

 
 

线性表  

2010-10-01 22:03:36|  分类: 奥赛资料 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

    一、概述

    在处理实际问题时,大量的是表格处理.例如,一个班级50名学生的某门考试的成绩表.

    这类表通常称为“线性表”.每个表是一个整体,同时,它们又都是由多个互相独立的成分(或元素)有序(线性)地组成的,各个成分的类型均相同,这种表在PASCAL语言中通常用数组来实现其组织和加工.

    线性表是最常用且最简单的一种数据结构.简而言之,一个线性表是N个数据元素的有限序列.至于每个数据元素的具体含义,在不同的情况下各不相同,它可以是一个数,或一个符号,也可以是一页书,甚至其它更复杂的信息.例如由每个英文字母组成的字母表:(A,B,C,……,Z)是一个线性表,表中的数据元素是单个字符.又如某校从1993年至1998年各种型号计算机的拥有量的变化情况,可以用线性表的形式给出(16,27,38,60,102,198,表中的数据元素是自然数,线性表的特点是:

    ① 存在唯一的一个被称作“第一个”的数据元素;

    ② 存在唯一的一个被称为“最后一个”的数据元素;

    ③ 除第一个元素外,线性表中的每个数据元素均只有一个前驱;

    ④ 除最后一个元素之外,每个数据元素均只有一个后继.

综上所述,线性表中的数据元素可以是各种各样的,但同一线性表中的元素必定具有相同特性,因此属于同一类数据对象.

    对线性表可进行的运算种类繁多,其中包括:

    确定表的长度n,即求表中数据元素的个数;

    从左到右(或从右到左)读表,即按a1, a2…,an(或anan-1 …,a1 )读取数据元素的值;

    存、取表中第i个数据元素(1in),即改变或检查第i个数据元素的值;

    在第i-1个和第i个数据元素之间(1in)插入一个新的数据元素,使原来的第ii+1,…,n个数据元素变成为第i+1i+2,…,nn+1个数据元素;

    删除第i个数据元素(1in),使原来的第i+1i+2,…,n个数据元素变成为第ii+1,…,n-1个数据元素;

    检索线性表,即在表中查找具有某个特征值的数据元素;

    对表排序,即按某个特征值递增(或递减)的顺序对表中的数据元素重新排列。

    对一个线性表,同时要求进行上述的所有运算,这在计算机的应用中是很少有的。实际上,在很多情况下,只需要完成其中的一部分运算就够了。

    二、 线性表的存储结构

       在计算机内,线性表可以用不同的方式表示,即有多种存储结构可供选择。对于完成某种运算来说,不同的存储方式,其执行效果是不一样的,为了使所要进行的运算得以有效地执行,在选择存储结构时,必须考虑要施行的是哪些运算,对选定的存储结构,应估计这些运算执行时间的量级,以及它对存储容量的要求。本讲只介绍数组形式存储的线性表。

       在计算机内,存储线性表的最简单和最自然的方式,是把表中的数据元素一个接一个地放进一组连续的存储单元之中,也就是说,把表中相邻的数据元素存放在内存中邻接的存储单元里,这种存储方法叫做顺序分配(Sequential Allocation),又称顺序映象(Sequential Mapping),其特点是:逻辑上相邻的数据元素,它们的物理次序也是邻接的。

       假设每个数据元素占用L个存储单元,则相邻的两个数据元素aiai+1在机器内的存储地址LOCai)与LOC(ai+1)将满足下面的关系:

LOC(ai+1) = LOCai+L

而的存储地址LOCai)为:

LOCai= LOCa1+(i - 1) *L

线性表是一个相当灵活的数据结构,它的长度可根据需要增长或缩短。

    三、线性表的插入和删除

若插入是在表的末尾进行,即在长度为n的线性表(a1, a2a3,…,an)的第n个元素之后,添加一个新元素,使长度变为n+1的表(a1, a2a3,…,anan+1),这很简单,只要在表的第n+1 个位置上写入新元素即可。

若插入是在表的中间进行,即在长度为n的线性表(a1, a2a3,…,an)的第i1in)个元素之前插入一个新元素,使长度变为n+1的表(a1, a2a3,…,anan+1),此时的情况要稍复杂一点,因为顺序分配是把表中的元素依次放在一组连续的存储单元中,也就是说,表中的元素在机器内是一个紧接着一个,没有“空隙”。为了能在第i个元素之前插入一个新元素,就必须把从第i个到第n个之间的元素依次向后挪动一个位置,腾出一个空位给插入的元素。

所以,在一般情况下,顺序分配的线性表的插入算法为:

① 把aian的元素后移一个位置,腾出空位。

② 往第i个位置上写入新值。

现用一个过程描述如下:

procedure insert(var v:arraytype;var n:integer;i:integer;x:elementtype);

var j:integer;

begin

         for j:=n downto i do v[j+1]:=v[j];

     v[i]:=x;

     n:=n+1

   end;

同样,若删除是在表的末尾进行,也很简单,只要把表的长度n1即可。

当删除是在表的中间进行,则也要引起表中元素移动。若要删除长度为n的线性表中第i1in)个元素,则必须把表中第i+1n之间的元素依次向前挪动一个位置,以覆盖掉第i个位置上的存储单元。

在一般情况的线性表的删除算法如下:

procedure delete(var v:arraytype;var n:integer;i:integer);

var j:integer;

begin

         for j:=i to n-1 do v[j]:=v[j+1];

     n:=n-1

   end;

    四、线性表应用举例

[4-1] 编码问题:设有一个数组AARRAY[0..N-1] OF INTEGER;数组中存储的元素为0-N-1之间的整数,且A[I]A[J]       (IJ)时。

    例如:N=6时,有:(430512

    此时,数组A的编码定义如下:

    A[0]的编码为0

    A[I]的编码为:在A[0]A[1],……A[I-1]中比A[I]的值小的元素的个数(I=12,……N-1

    所以上面数组A的编码为:B=(0,0,0,3,1,2)

    程序要求解决以下问题

    给出数组A后,求出其编码;

    给出数组A的编码后,求出A的原数据。

[算法设计] 问题①比较简单,只要统计一下即可。问题②是一个线性表的删除问题,将0 N-1之间的N个整数顺序放在一个线性表C中,取出编码数组B中的最后一个元素b[N-1],则C中的第b[N-1]个元素为数组A的最后一个元素,取出该元素后从C中删除之,再取编码数组B中的前一个元素,重复上述操作,直到数组A的所有元素都得到为止。

[程序清单]

program ex4_1(input,output);

const maxn=50;

type arraytype=array [0..maxn] of integer;

var n,select:integer;

    a,b:arraytype;

procedure init(var v:arraytype);

var i:integer;

begin

     write('Input n:');

     readln(n);

     write('Input ',n,' integer number:');

     for i:=0 to n-1 do read(v[i]);

     readln

end;

procedure print(v:arraytype);

var i:integer;

begin

     for i:=0 to n-1 do write(v[i],' ');

     writeln

end;

procedure task1;

var i,j:integer;

begin

     init(a);

     for i:=0 to n-1 do

     begin

          b[i]:=0;

          for j:=0 to i-1 do

              if a[i]>a[j] then b[i]:=b[i]+1;

     end;

     writeln('The code of array A is:');

     print(b)

end;

procedure delete(var v:arraytype;var n:integer;i:integer);

var j:integer;

begin

     for j:=i to n-2 do v[j]:=v[j+1];

     n:=n-1

end;

procedure task2;

var i,len:integer;

    c:arraytype;

begin

     init(b);

     for i:=0 to n-1 do c[i]:=i;

     len:=n;

     for i:=n-1 downto 0 do

     begin

          a[i]:=c[b[i]];

          delete(c,len,b[i])

     end;

     writeln('Array A is:');

     print(a)

end;

begin

     writeln(' ':20,'1--Task1');

     writeln(' ':20,'2--Task2');

     write(' ':20,'Input your select(1 or 2):');

     readln(select);

     if select=1 then task1 else task2

end.

 [4-2] M只猴子要选大王,选举办法如下:所有猴子按1M编号围坐一圈,从第1号开始按顺序1,2,,N报数,凡报到N的猴子退出到圈外,如此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.MN由键盘输入,打印出最后剩下的那只猴子的编号.

    这个例题是由古罗马著名史学家Josephus提出的问题演变而来的,所以通常称为Josephus(约瑟夫)问题.

    在确定程序设计方法之前首先来考虑如何组织数据,由于要记录m只猴子的状态,可利用含m个元素的数组monkey来实现.利用元素下标代表猴子的编号,元素的值表示猴子的状态,monkey[k]=1表示第k只猴子仍在圈中,monkey[k]=0则表示第k只猴子已经出圈.程序采用模拟选举过程的方法,开始时将报数变量count置为1,用变量current表示当前报数的猴子的编号,也置为1,变量out记录出圈猴子数.当报数达到n,对当前报数的猴子作出圈处理,monkey[current]0, count0,out增加1.然后继续往下报数,直到圈中只剩一只猴子为止.

[程序清单]

program ex4_2(input,output);

const maxm=100;

var i,m,n,count,current,out:integer;

    monkey:array [1..maxm] of integer;

begin

     write('Input m,n:'); readln(m,n);

     for i:=1 to m do monkey[i]:=1;

     out:=0; count:=1; current:=1;

     while out<m-1 do

     begin

          while count<n do

          begin

               repeat{寻找圈上的下一只猴子}

                     current:=current+1;

                     if current=m+1 then current:=1

               until monkey[current]=1;

               count:=count+1

          end;

          monkey[current]:=0; out:=out+1; count:=0

     end;

     for i:=1 to m do

         if monkey[i]=1 then writeln('The monkey king is no.',i)

end.

[运行程序]下划线表示输入

Input m,n:8 3

The monkey king is no.7

    在组织数据时,也可以考虑只记录仍在圈中的猴子的情况.用一个线性表按编号由小到大依次记录圈中所有猴子的编号,每当有猴子出圈时,即从线性表中删除对应元素,表中元素减少一个.程序中用变量rest表示圈中剩余的猴子数,即线性表中元素的总数.

program ex4_2_2(input,output);

const maxm=100;

var i,m,n,current,rest:integer;

    monkey:array [1..maxm] of integer;

begin

     write('Input m,n:'); readln(m,n);

     for i:=1 to m do monkey[i]:=i;

     rest:=m; current:=1;

     while rest>1 do

     begin

          current:=(current+n-1) mod rest;

          if current=0 then current:=rest;

          for i:=current to rest-1 do monkey[i]:=monkey[i+1];

          rest:=rest-1

     end;

     writeln('The monkey king is no.',monkey[1])

end.

[ 4-3] 对任意给定的一个自然数n(n<=100),将分母小于等于n的不可约的真分数按上升的次序排序,并且在第一个分数前加上0/1, 而在最后一个分数后加上1/1,这个序列称为n级法雷序列,Fn表示.例如,F8:

0/1,1/8,1/7,1/6,1/5,1/4,2/7,1/3,3/8,2/5,3/7,1/2,4/7,3/5,5/8,2/3,5/7,3/4,4/5,5/6,6/7,7/8,1/1.

    编程求出n级法雷序列,每行输出10个分数.

[算法设计]由于程序要求以分数的形式输出法雷序列,对每个真分数必需分别存放其分子分母,这就要用两个线性表来实现.开始时线性表中只有两个元素,分别是0/11/1,线性表用两个数组fpfq来表示,fp存放分子,fq存放分母.所有的真分数用一个两重循环来产生,每次将当前产生的真分数p/q插入到线性表中去.为了保证线性表中所有元素在插入新元素后仍然按从小到大的次序排列,首先要从表中找出第一个不小于p/q的元素,如果该元素等于p/q,则说明p/q不是不可约的真分数,p/q无需插入,否则p/q应插入在表中第一个大于它的元素的位置.当向线性表中插入新元素时,如果该线性表是用数组实现的,则插入新元素之前要将从插入位置直到最后的所有元素都后移一位,然后再插入新元素.删除线性表中元素时,只要将从删除位置之后的那个元素直到最后的所有元素都前移一位即可.由于对实数要避免等或不等的比较,程序中在对两个分数进行比较时,将它们化成了乘式进行.

[程序清单]

program ex4_3(input,output);

const maxn=100;

type arraytype=array [1..maxn*maxn] of integer;

var i,k,n,p,q,total:integer;

    fp,fq:arraytype;

begin

     write('Input n:'); readln(n);

     fp[1]:=0; fq[1]:=1; fp[2]:=1; fq[2]:=1; total:=2;

     for q:=2 to n do{列举分母}

         for p:=1 to q-1 do{列举分子}

         begin

              k:=1;

              while p*fq[k]>q*fp[k] do k:=k+1; {寻找插入位置}

              if p*fq[k]<>q*fp[k] then { p/q不在表中}

              begin

                   for i:=total downto k do fp[i+1]:=fp[i];

                   for i:=total downto k do fq[i+1]:=fq[i];

                   fp[k]:=p; fq[k]:=q; total:=total+1

              end

         end;

     for i:=1 to total do

     begin

          write(fp[i],'/',fq[i],'   ');

          if i mod 10=0 then writeln

     end;

     writeln

end.

[运行程序]下划线表示输入

Input n:15

0/1  1/15  1/14  1/13  1/12  1/11  1/10  1/9  1/8  2/15 

1/7  2/13  1/6  2/11  1/5  3/14  2/9  3/13  1/4  4/15 

3/11  2/7  3/10  4/13  1/3  5/14  4/11  3/8  5/13  2/5 

5/12  3/7  4/9  5/11  6/13  7/15  1/2  8/15  7/13  6/11 

5/9  4/7  7/12  3/5  8/13  5/8  7/11  9/14  2/3  9/13 

7/10  5/7  8/11  11/15  3/4  10/13  7/9  11/14  4/5  9/11 

5/6  11/13  6/7  13/15  7/8  8/9  9/10  10/11  11/12  12/13

13/14  14/15  1/1  


到目前为止,我们所知道的描述线性表的方法只有数组,利用数组描述线性表时,其优点是对线性表中任一元素都可随机存取,具体反映为通过改变下标的值可以对线性表中的任一元素进行访问和修改.其缺点是在向线性表中插入和删除元素时,必须移动表中的部分元素.插入元素时,要将从插入位置直至最后的所有元素后移一个位置,如上例所示.删除第i个元素时,需将第i+1至最后一个元素依次向前移动一个位置. 

  评论这张
 
阅读(68)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018