线性表
线性表是线性结构的抽象，线性结构的特点是结构中的数据元素之间存在一对一的线性关系。
数据元素之间的位置关系是一个接一个的排列：
.除第一个位置的数据元素外，其他数据元素位置的前面都只有一个数据元素。
.除最后一个位置的外，其他数据元素位置的后面都只有一个元素。
线性表通常表示为：l=(d,r)
d是数据元素的有限集合
r是数据元素之间关系的有限集合
线性表的基本操作：
代码如下:
public interface ilistds {
int getlength(); //求长度
void clear(); //清空
bool isempty(); //判空
void append(t item); //附加
void insert(t item, int i); //插入
t delete(int i); //删除
t getelement(int i); //取表元素
int locate(t value); //按值查找
}
顺序表
顺序表是线性表的顺序存储(sequence storage)，是指在内存中用一块地址连续的空间依次存放线性表的数据元素(sequence list)，具有随机存取的特点。
w: 每个数据元素占w个存储单元
a1:顺序表的基地址(base address)
loc(ai)=loc(a1)+(i-1)*w 1
为了理解顺序表，闪电学习了这样一个例题，有兴趣的朋友可以在自己的机器上写一下。
有数据类型为整型的顺序表la和lb，其数据元素均按从小到大的升序排列，编写一个算法将它们合并成一个表lc，要求lc中数据元素也按升序排列。
算法思路：
依次扫描la和lb的数据元素，比较la和lb当前数据元素的值，将较小值的数据元素赋给lc，如此直到一个顺序表被扫描完，然后将未完的那个顺序表中余下的数据元素赋给lc即可。lc的容量要能够容纳la和lb两个表相加的长度。
思路图示：
代码如下:
public class seqlist : ilistds {
private int maxsize; //顺序表的容量
private t[] data; //数组，用于存储顺序表中的数据元素
private int last; //指示顺序表最后一个元素的位置
//构造器
public seqlist(int size)
{
data = new t[size];
maxsize = size;
last = -1; //如果顺序表为空，last=-1
}
//索引器
public t this[int index]
{
get { return data[index]; }
set { data[index] = value; }
}
//最后一个元素的位置属性
public int last
{
get { return last; }
}
//容量属性
public int maxsize
{
get { return maxsize; }
set { maxsize = value; }
}
//判断顺序表是否为空
public bool isempty()
{
if (last == -1)
return true;
else
return false;
}
//判断顺序表是否为满
public bool isfull()
{
if (last == maxsize - 1)
return true;
else
return false;
}
//求顺序表的长度
public int getlength()
{
return last + 1;
}
//清空顺序表
public void clear()
{
last = -1;
}
//在顺序表末尾添加新元素
public void append(t item)
{
if (isfull())
{
console.writeline(list is full.);
return;
}
data[++last] = item;
}
//在顺序表第i个数据元素位置插入一个数据元素
public void insert(t item, int i)
{
if (isfull())
return;
if (i last + 2)
return;
if (i == last + 2)
data[last + 1] = item;
else
{
for (int j = last; j >= i - 1; --j)
{
data[j + 1] = data[j];
}
data[i - 1] = item;
}
++last;
}
//删除顺序表的第i个数据元素
public t delete(int i)
{
t tmp = default(t);
if (isempty())
return tmp;
if (i last + 1)
return tmp;
if (i == last + 1)
tmp = data[last--];
else
{
tmp = data[i - 1];
for (int j = i; j data[j] = data[j + 1];
}
--last;
return tmp;
}
//获得顺序表的第i个数据元素
public t getelement(int i)
{
if (isempty() || (i last + 1))
return default(t);
return data[i-1];
}
//在顺序表中查找值为value的数据元素
public int locate(t value)
{
if (isempty())
return -1;
int i = 0;
for (i = 0; i {
if (value.equals(data[i]))
break;
}
if (i > last)
return -1;
return i;
}
}
代码如下:
public class genericlist
{
public genericlist()
{ }
public seqlist merge(seqlist la, seqlist lb)
{
seqlist lc = new seqlist(la.maxsize+lb.maxsize);
int i = 0;
int j = 0;
int k = 0;
//两个表中元素都不为空
while ((i {
if (la[i] lc.append(la[i++]);
else
lc.append(lb[j++]);
}
//a表中还有数据元素
while (i lc.append(la[i++]);
//b表中还有数据元素
while (j lc.append(lb[j++]);
return lc;
}
}
客户端代码：
代码如下:
static void main(string[] args)
{
seqlist sl1 = new seqlist(4);
sl1.append(1);
sl1.append(3);
sl1.append(4);
sl1.append(7);
seqlist sl2 = new seqlist(6);
sl2.append(2);
sl2.append(5);
sl2.append(6);
sl2.append(8);
sl2.append(11);
sl2.append(14);
genericlist gl = new genericlist();
seqlist sl3 = gl.merge(sl1, sl2);
console.writeline(length: + sl3.getlength());
for (int i = 0; i {
console.writeline(i + : + sl3[i]);
}
}
好了，下一次学习链表。
作者：levinlee