线性表的顺序存储结构和基本操作
在计算机内存中如何存放线性表呢？其中最简单和常用的方式是用一组地址边续的的存储单元依次存储线性表的元素。假没线性表的每个元素占用Ｌ个存储单元，并以所占的第一个单元的存储地址作为数据元素位置，则线性表中第i+1个数据元素的存储位置loc(ai+1)和i个数据元素的存储位置loc(ai)之间应满足下列关系：
loc(ai+1)=loc(ai)+L
如果loc(ai)=b+(i-1)L
线性表的这种机内表示法称为线性表的顺序存储结构。也就是主元素在计算机内以“物理位相邻“来表示线性表中数据元素之间的关系。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数（如图2.6）。因此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。
在ＰＡＳＣＡＬ语言中可用一给数组描述线性表的顺序存储结构：
const
lmaxsize={线性表可能达的最大长度};
type
lelement={线性表元素的数据类型};
lposition=0..lmaxsize;
list=record
date:array[1..lmaxsize]of lelement;
last:lposition;
end;
kusterrir=(bierrmubdexerrmfubdfaukmiverfkiwmybderfkiw)l
在上述 述中，线性表的顺序存储结构是一个记录类型的结构，其中lelement描述线性表元素的数据类型，数据域data描述了线性表中的数据元素占用的数组空间，数组的第i个分量表示线性表中第i个数据元素的存储映像，数据域last指示最后一个数据元素在数组空间中的位置。此处数据元素的存储位置由数组的下标值（即相对于线性表的起始位置的值）来表示。listerror记录对指定的线性表操作后的情况，分别是“操作无误“，“检索出错“，“找不到“，“上溢出“，“下溢出“。
对于图2.1 学生成绩表，假设最多只有300个学生，用PASCAL语言描述的线性表的顺序存储结构如下：
const
lmaxize=300;
type
lelement=record
name:string[8];
chinese:real;
math:real;
sum:real;
average:real;
end;
lposition=0..lmaxize;
list=record
data:array[1..lmaxize]of lelement;
last:lposition;
end;
{定义线性表为list，它最多能容纳lmaxize个元素，首元素序号为1，尾元素序号为last。从宏观角度，如果只关心元素与元素关系时，我们常常把每个元素称为一个结点。}
listerror=(noerro，indexerro，findfail，overflow，underflow）；
var
L:list;
lerro:listerro;
线性表是一个相当灵活的数据结构，它的长度可根据需增加或缩短，即对线性表的数据元系不仅可以进行访问，还可进行插入和删除。为了完成线性表的基本操作，我们常常自定义下列函数或过程，参考算法描述如下：
1.初始化操作过程。
procedure lcreate(var L:list);
{没定一个空的线性表L}
begin
L.last:=0:
Lerro:=noerro;
end;
2.求和度函数。
function llength(var L:list):lposition;
{函数值为给定的线性表L中数据元素的个数，函数值为零表示线性表没有元素}
begin
llengtyh:=L.last:
end;
3.判空表函数。
function lempty(var L:list):boolean;
{若L为空表，则返回布尔值true，否则返回布尔值false}
begin
lempty:=(L.last=0);
end;
4.判满函数。
function lfull(var L:list):boolean;
{如果表中已装满元素，函数值为true，否则为false}
begin
lfull:=(L.last=lmaxsize);
end;
5.求首结点元素位置函数。
function lfirst(var L:list):lposition:
begin
if L.last=0
then lfirst:=0
else lfirst:=1;
end;
6.求尾结点元素位置函数。
function llast(var L:list):lposition:
begin
llast:=L.last;
end;
7.求前趋函数。
function lprior(p:lposition;var L:list):lposition;
{已知给定线性表L的一个元素的位序p，若1<p<=llength(L)，则函数值为p的前趋位序，否则指出错误}
begin
if(p<=1)or(p>llength(L))
then
begin
lerro:=indexerro;
lprior:=0;
end
else lprior:=p-1;
end;
8.求后继函数。
function lnext(p:lposition;var L:list):lposition;
{已知给定线性表L的一个元素位序p,若1<=p<llength(L),则函数值为p.的后继，否则为空元素}
begin
if(p<=0)or(p>=llength(L))
then
begin
lerro:=indexerro;
lnext:=0;
end
else lnext:=p+1;
end;
9.取元素函数。
procedure lretrieve(p:lposition;var e:lelement;var L:list);
{若1<=p<=llength(L)则函数值为给定的线性表L中第i个数据元素，否则指出错误。p称为该数据元素在线性表中的位序}
begin
if(p<=0)or(p>llength(L))
then lerro:=indexerro
else e:=L.data[p];
end;
10.修改元素数据过程。
procedure lupdate(e:lelement;p:lposition;var L:list);
begin
if(p<=0)or(p>llength(L))
then lerro:=indexerro
else L.data[p]:=e;
end;
11.删除操作过程。
procedure ldelete(p:lposition;var L:list);
{若1<=p<=llength(L),删除给定线性表中第p个数据元素，使操作之前和度为n的线性表(a1,a2,…,ap-1,ap,…an)变成长度为n-1的线性表(a'1,a'2,…,a'p-1,a'p…a'n-1），其中当1<=j<=p-1时a'j=aj，当p<=j<=n-1时a'j=aj+1。若p<1或p>llength(L)，则此操作无意义}
var i:lposition;
begin
if llength(L)=0
then lerro:=indexerro
else if(p<1)or(p>llength(L))
then lerro:=indexerro
else
begin
for i:=p to llength(L)-1 do
L.data[i]:=L.data[i+1]:{第i后元素逐个前移}
L.last:=L.last-1;{尾元素序号减1，即线性表长度减1}
end;
end;
12.后插操作过程。
procedure lisertafter(e:lelement;p:lposition;var L:list);
{在给定线性表中第p个元素之后插入一个新的数据元素e，使操作之前和度为n的线性表(a1,a2,…ap,ap+1,…an)变成长度为n+1的线性表(a'1,a'2,…a'p,e,a'p+2,…a'n)，其中e 为操作后的线性表L、中敏p+1个数据元素，且当1<=i<=p时a'i=ai，当p+2<=i<=n+1时a'i=ai-1。可见此操作仅在1<=p<=n时可行}
var
i:lposition;
begin
if llength(L)=0
then
begin
L.data[1]:=e;
L.last:=1;
end
else if(p<0)or(p>llength(L))
then lerro:=indexerro;
else if llength(L)=lmaxsize
then lerro:=overflow
else
begin
for i:=llength(L)downto p+1 do
L.data[i+1]:=L.data[i];{从最后元素开始到第i个元素逐个后移}
L.data[p+1]:=e;{插入}
L.last:=L.last+1;{尾元素序号加1，即线性表长度加1}
end;
end;
13.判断两元素是否相同函数。
function lequal(e,f:lelement):boolean:
{若e,f值相等，函数值为true，否则flse}
begin
{example}
lequal:=(e.name=f.name)and(e.chinese=f.chinese)and(e.math=f.math)
and(e.sum=f.sum)and(e.average=f.average);
end;
14.定位函数。
function lfind(e.lelement;var L:list):lposition;
{给定值e,若线性表L中存在值和e相同的数据元素不止一个，则函数值为这此元素在线性表L中的位序的最小值}
var
p:integer;
begin
p:=1;
Lerro:=findfail;
lfind:=0;
while(Lerro=findfail)and(p<=llength(L))do
begin
if lequal(e,L.data[p])
then
begin
lfind:=p;
lerro:=noerro;
end;
p:=p+1;
end;
end;
15.前插过程。
在上述函数或过程的基础上，我们还可以根所需要增加一些有用的自定义函数或过程，例如下面的在一个元素前插过程：
procedure linserbefore(e:lelement;p:lposition;var L:list);
var
temp:lelement;
begin
if(p<0)or(p>llength(L))
then lerro:=indexerro
else if lempty(L)
then linsertafter(e,p,L);{调用后插过程}
else
begin
p:=lprior(p,L);{求p的前一个位置并把新结点插入其后}
linsertafter(e,p,L);{调用后插过程}
end;
end;
例题：用线性表编一个学生成绩表，并对其进行插入、修改、删除、追加、显示、退出等操作。
解答：
{
By Unite Space 2001
http://www.cpascal.com
e-mail:webmaster@cpascal.com
}
program data_structure_application_chapter2_sample_2;
uses crt;
const
lmaxsize=300;
type
lelement=record
name:string[8];
chinese:real;
math:real;
sum:real;
average:real;
end;
lposition=0..lmaxsize;
list=record
data:array[1..lmaxsize]of lelement;
last:lposition;
end;
listerro=(noerror,indexerror,findfail,overflow,underflow);
var
l:list;
lerro:listerro;
menu,p:integer;
e:lelement;
procedure lcreate(var l:list);
begin
l.last:=0;
lerro:=noerror;
end;
function llength(var l:list):lposition;
begin
llength:=l.last;
end;
function lempty(var l:list):boolean;
begin
if l.last=0 then lempty:=true
else lempty:=false;
end;
procedure linsertafter(e:lelement;p:lposition;var l:list);
var
i:lposition;
begin
if llength(l)=0
then
begin
l.data[1]:=e;
l.last:=1;
end
else if(p<0)or(p>llength(l))
then lerro:=indexerror
else if llength(l)=lmaxsize
then lerro:=overflow
else
begin
for i:=llength(l) downto p+1 do
l.data[i+1]:=l.data[i];
l.data[p+1]:=e;
inc(l.last);
end;
end;
procedure lupdate(e:lelement;p:lposition;var l:list);
begin
if (p<=0)or(p>llength(l))
then lerro:=indexerror
else l.data[p]:=e;
end;
procedure ldelete(p:lposition;var l:list);
var i:lposition;
begin
if llength(l)=0
then lerro:=indexerror
else if (p<1)or(p>llength(l))
then lerro:=indexerror
else
begin
for i:=p to llength(l)-1 do
l.data[i]:=l.data[i+1];
dec(l.last);
end;
end;
procedure erromessage;
begin
case lerro of
noerror:writeln('ok!');
indexerror:writeln('index error!');
findfail:writeln('find fail!');
overflow:writeln('overflow error!');
underflow:writeln('underflow error!');
end;
readln;
end;
procedure readrecord(var e:lelement);
begin
with e do
begin
write('name:');
readln(name);
write('chinese:');
readln(chinese);
write('math:');
readln(math);
sum:=chinese+math;
average:=sum/2;
end;
end;
procedure readposition(var p:integer;message:string);
begin
write('please input ',message,' position');
readln(p);
end;
procedure printlist(var l:list);
var
i:integer;
begin
if lempty(l)
then writeln('It is empty now!')
else
writeln('no':10,'name':10,'chinese':10,'math':10,'average':10);
for i:=1 to llength(l) do
with l.data[i] do
begin
writeln(i:10,name:10,chinese:10:1,math:10:1,average:10:1);
end;
end;
begin
lcreate(l);
repeat
clrscr;
lerro:=noerror;
write('1--insert,2--edit,3--delete,4--append,5--list,0--quit:');
readln(menu);
case menu of
1:begin
readrecord(e);
readposition(p,'insert');
linsertafter(e,p,l);
end;
2:begin
readrecord(e);
readposition(p,'edit');
lupdate(e,p,l);
end;
3:begin
readposition(p,'delete');
ldelete(p,l);
end;
4:begin
readrecord(e);
linsertafter(e,llength(l),l);
end;
5:printlist(l);
0:halt;
else
writeln('please input number of 0--4! press any key to continue.');
readln;
end;
erromessage;
until false;
end.
{
By Unite Space 2001
http://www.cpascal.com
e-mail:webmaster@cpascal.com
}