文档介绍：线性表的定义及其运算
线性表的顺序存储结构(向量)
线性表的链表存储结构
循环链表和双向链表
多项式相加问题
线性表的算法实现举例
第2章线性表
返回主目录
各种运算简介
对线性表要经常进行的基本运算主要有以下几种:
(1) 求线性表的表长Length(L);
(2) 取线性表中的第i个元素Get(L, i);
(3) 修改线性表中的第i个元素Modify(L, i);
(4) 删除线性表中的第i个元素Delete(L, i);
(5) 在线性表中第i个元素之后(或之前)插入一个新元素Insert(L, i, x);
第2章线性表
线性表的定义及其运用
线性表的顺序存储结构(向量)
顺序存储结构(向量)
在计算机内, 可以用不同的方法来存储数据信息, 最常用的方法是顺序存储。顺序存储结构也称为向量存储。向量是内存中一批地址连续的存储单元。由于线性表的所有数据元素属于同一类型, 所以每个元素在存储器中占用的空间大小相同。假设向量的第一个元素存放的地址为LOC(a1), 每个元素占用的空间大小为L个字节, 则元素ai的存放地址为
LOC(ai)=LOC(a1)+L*(i-1)
线性表的这种机内表示称做线性表的顺序存储结构或顺序映象(sequential mapping), 只要确定了存储线性表的起始位置, 线性表中任一数据元素都可随机存取, 所以线性表的顺序存储结构是一种随机存取结构。
在高级语言环境中常用一维数组来表示向量。为更好体现信息隐蔽原则以及数据抽象原则, 在这里把数组和线性表的长度封装在一个结构体中:
Struct sequnce
{ELEMTP elem ; /* 数组域*/
int len ; /* 表长域*/
}
向量中基本运算的实现
1. 插入
向量的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素x, 使长度为n的线性表(a1, …, ai-1, ai, …, an)变成长度为n+1的线性表(a1, …, ai-1,x, ai, …, an)。插入操作应先把元素ai, …, an向后各自移动一个位置, 然后将x插在第i个位置上。C语言的数组下标从零开始, 为了与前文概念的描述相一致, [0]闲置不用, [1]之中。
插入过程可用如下算法来实现:
算法
”SS]void insert(struct sequnce *p, int i, ELEMTP x)
{ struct sequnce v;
v=*p;
if ((i<1)||(i>+1)) printf("Error!"); /* 插入位置出错*/
else {for (j=;j>=i;j--) [j+1]=[j];
[j]=x;
=+1;
}
*p=v;
}
, -1, 则不允许进行任何插入操作。由于C语言函数的一般参数仅能向被调函数传值, 这个值在返回时也不会改变, 因此在上面的算法中, 采用指针变量p做参数, 虽然从被调函数返回时p值不变, 但是p中地址所代表的结构体的内容发生了变化。 struct sequnce v; v=*p;这两个语句是为了使程序书写简明易懂, 用v来表示结构体。这样, 操作是在局部变量v结构体上进行, 因此最后还要用*p=v; 将改变后的内容赋值给*p, 由指针变量p将结构带回主调函数。
在下面的删除算法中也是同样处理, 目的是使算法主体部分简明扼要。处理此类函数的参数传递问题, 上述方法多用了一个局部变量, 并不理想。在本节最后的源程序例题中, 使用的是另一种方法, 也不理想。在此, 问题显得如此麻烦, 主要因为C语言参数传递的限制。如果换为C++语言, 通过让&v做参数就可以解决问题。
2. 删除
要删除线性表中的第i个元素ai, 操作和插入操作类似。把元素a i+1, …, an分别向前移动一个位置, 使长度为n的线性表(a1, …, ai-1, ai, …, an),变成长度为n-1的线性表(a1, …, ai-1, ai+1, …, an)。在下面的算法中, [1]之中。。
  void delete(struct seq