Tim的资源站

一、顺序表的初始化

顺序表的初始化，就是构造一个数据元素为0的空表，算法如下：

void SequenList::Initiate()
{
	len = 0;
}

设调用函数为主函数，主函数对初始化函数的调用如下：

void main()
{
	SequenList L;
	L.Initiate();
	......
}

二、插入运算

顺序表的插入运算是指在顺序表中的第i个位置插入一个值为x的新元素，插入后，使原表为n的顺序表：

(a₁， a₂，···，a_i-1，a_i，a_i+1，···，a_n)

变为表长为n+1的顺序表：

(a₁， a₂，···，a_i-1，x，a_i，a_i+1，···，a_n)

其中，i的合理取值范围为1≤i≤n+1

顺序表插入运算的图形表示

在顺序表上完成插入运算，主要步骤如下：

1. 将数据元素a_i ~ a_n依次向后移动一个位置，为新元素让出位置；
2. 将x置入空出的新位置；
3. 增加len的值

（一）代码实现

int SequenList::Insert(DataType x, int i) {
	//在线性表的第 i 个数据元素之前插入一个新的数据元素 x
	int j;
	
	if (len >= MAXSIZE) {
		cout << "overflow!" << endl；　　　//数据溢出
		return 0;
	} else if ((i<1) || (i>len+1)) {　　//如果插入位置不合法
		cout << "position is not correct!" << endl;
		return 0;
	} else {
		for(j=len; j>=i; j--)
			data[j]=data[j-1]；　　　　//元素后移
			
		data[i-1]=x；　　　　 //插入元素
		len++；　　　　　　　　//表长度增加 1

		return 1;
	}
}

要注意的问题：

1. 顺序表中数据区域有 MAXSIZE 个存储单元，所以在向顺序表中做插入操作时，首先检查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。

2. 要检验插入位置的有效性，这里 i 的有效范围是 1≤i≤n+1，其中 n 为原表长。

3. 注意数据的移动方向。

顺序表插入运算的时间复杂度为 O（n）。

三、删除运算

线性表的删除运算是指将表中第 i 个元素从线性表中删除，使原表长为 n 的线性表：

(a₁， a₂，···，a_i-1，a_i，a_i+1，···，a_n)

变成表长为 n-1 的线性表：

(a₁， a₂，···，a_i-1，a_i+1，···，a_n)

i 的取值范围为 1≤i≤n。

顺序表删除运算图形表示

在顺序表上完成删除运算，主要步骤如下：

1. 将数据元素a_i+1 ~ a_n依次向前移动一个位置，为新元素让出位置；
2. 将len的值减1

（一）代码实现

int SequenList::Deleted(int i) { //删除顺序表的第i个数据元素
	int j;
	if((i<1) || (i>len)) {　　　//若删除位置不合法
		cout << "position is not correct!" << endl;
		return 0;
	} else {
		for(j=i; j<len; j++)
		data[j-1]=data[j]；　　//元素前移
		len--；　　　　　　//表长度减 1
		return 1;
	}
}

本算法应注意以下问题。

（1）删除第 i 个数据元素，i 的取值为 1≤i≤n，否则第 i 个元素不存在。因此，要检查删除位置的有效性。

（2）删除a_i之后，该数据不再存在；如果需要，可先取出a_i，再做删除。

顺序表的删除算法的时间复杂度为O（n）。

四、按值查找

顺序表中的按值查找是指在线性表中查找与给定值 x 相等的数据元素。

在顺序表中完成该运算最简单的方法是：

从第一个元素a₁起依次和 x 比较，直到找到一个与 x 相等的数据元素，则返回它在顺序表中的位置值（下标 +1）；或者查遍整个表都没有找到与 x 相等的数据元素，则返回 0。

（一）代码实现如下

int SequenList::Locate(DataType x) {
	//返回值为 x 的数据元素的位序值
	int j=0;
	while ((j<len) && (data[j]!=x)) j++;
	if (j<len) return j+1;
	else return 0;
}

该算法的时间复杂度为O（n）。

五、读取第 i 个数据元素的值

DataType SequenList::Get(int i) {
	if ((i<1) || (i>len)) {
		cout<<"position is not correct!"<<endl;
		return NULL;
	} else return data[i-1];
}

六、取得数据元素个数

int SequenList::Length() {
	return len;
}