数据结构与算法——顺序表

• 定义：一系列物理连续地址的存储单元，用来存储一系列的数据元素，一般是用数组的形式存储，（但和数组还是有一些区别），用来实现对数据的增删查改

（一）定义模板类

代码如下：

template  <class T>  			// 假定顺序表的元素类型为T
class arrList : public List<T>  {		// 顺序表，向量
private:    					// 线性表的取值类型和取值空间
	int  maxSize;            	// 私有变量，顺序表实例的最大长度
    int  curLen; 		    		// 私有变量，顺序表实例的当前长度
    int  position;				// 私有变量，当前处理位置
   	T  *aList ;            		// 私有变量，存储顺序表的实例
public: 						// 顺序表的运算集
	arrList(const int size) {  		// 创建一个新的顺序表，参数为表实例的最大长度
		maxSize = size;
		aList = new T[maxSize];
		curLen = position = 0;
	}
	~arrList() {					// 析构函数，用于消除该表实例
		delete [] aList;
	} 
	void clear() {      			// 将顺序表存储的内容清除，成为空表
		delete [] aList;
		curLen = position = 0;
		aList = new T[maxSize];
	}
	int length();            		// 返回此顺序表的当前实际长度
    bool append(T value);			// 在表尾添加一个元素value，表的长度增1
	bool insert(int p, T value);	 	// 在位置p上插入一个元素value，表的长度增1
	bool del(int p); 			// 删除位置p上的元素，表的长度减 1
	int getPos(const T value);		// 在线性表中查找值为value的元素，并返回第1次出现的位置
	void print();                     // 打印线性表 
}; 

（二）具体函数的实现：

构造函数：

arrlist(const int size){//创建一个新的顺序表，参数为表的最大长度
    maxsize=size;
    alist=new int[maxsize];
    curlen=position=0;
}

析构函数：

~arrlist(){
    delete[]alist;//析构函数，用于消除该表的实例
}

clear函数：

void clear(){//将顺序表储存的内容清除
    delete[]alist;
    curlen=position=0;
    alist=new int[maxsize];
}

length函数：

int length(){//返回此顺序表的当前实际长度
	return curlen;
}

getpos函数：

int getpos(const int value){//查找值为value的元素的下标
    for(int i=0;i<curlen;i++){
        if(value==alist[i])
            return i;
    }
    return -1;
}

insert函数：

bool insert(const int p,const int value){//在某位置插入元素
    if(curlen>=maxsize){
        cout<<"The List is overflow"<<endl;
        return false;
    }
    if(p<0||p>curlen){
        cout<<"Insertion point is illegal"<<endl;
        return false;
    }
    for (int i = curlen; i > p; i--) {
			alist[i] = alist[i - 1];
	}
	alist[p] = value;
	curlen++;
	return true;
}

del函数：

bool del(const int p){
    if(curlen==0){
        cout<<"No elements to delete"<<endl;
        return false;
    }
    if(p<0||p>curlen-1){
        cout<<"Deletion is illegal"<<endl;
        return false;
    }
    for(int i=p;i<=curlen-1;i++){
        alist[i]=alist[i+1];
    }
    curlen--;
    return true;
}

print函数：

void print(){
    for(int i=0;i<curlen;i++){
        cout<<alist[i];
    }
    cout<<endl;
}

（三）完整代码：

#include<iostream>
using namespace std;
class arrlist {
private:
	int* alist;//储存顺序表的实例
	int maxsize;//顺序表的最大长度
	int curlen;//顺序表的当前长度
	int position;//当前处理位置
public:
	arrlist(const int size) {//创建一个新的顺序表，参数为表的最大长度
		maxsize = size;
		alist = new int[maxsize];
		curlen = position = 0;
	}
	~arrlist() {
		delete[]alist;//析构函数，用于消除该表的实例
	}
	void clear() {//将顺序表储存的内容清除
		delete[]alist;
		curlen = position = 0;
		alist = new int[maxsize];
	}
	int length() {//返回此顺序表的当前实际长度
		return curlen;
	}
	int getpos(const int value) {//查找值为value的元素的下标
		for (int i = 0; i < maxsize; i++) {
			if (value == alist[i]) {
				return i;
			}
		}
		return -1;
	}
	bool insert(const int p, const int value) {//在某位置插入元素
		if (curlen >= maxsize) {
			cout << "The List is overflow" << endl;
			return false;
		}
		if (p<0 || p>curlen) {
			cout << "Insertion point is illegal" << endl;
			return false;
		}
		for (int i = curlen; i > p; i--) {
			alist[i] = alist[i - 1];
		}
		alist[p] = value;
		curlen++;
		return true;
	}
	bool del(const int p) {//删除顺序表上指定位置的元素
		if (curlen == 0) {
			cout << "No elements to delete" << endl;
			return false;
		}
		if (p<0 || p>curlen - 1) {
			cout << "deletion is illegal" << endl;
			return false;
		}
		for (int i = p; i <= curlen - 1; i++) {
			alist[i] = alist[i + 1];
			
		}
		curlen--;
			return true;
	}
	void print() {
		for (int i = 0; i < curlen; i++) {
			cout << alist[i];
		}
		cout << endl;
	}
};
int main() {
		arrlist a(10);
		a.insert(0, 1);
		a.print();
		a.insert(1, 3);
		a.insert(1, 2);
		a.print();
		a.insert(3, 4);
		cout<<a.length()<<endl;
		a.del(3);
		a.print();
		cout<<a.length()<<endl;
		cout << a.getpos(1);
		return 0;
}

（四）运行结果：

1
123
4
123
3
0

（五）关于时间复杂度：

• 按位置读取：$O(1)$

• 插入、删除、按内容查找：$O(n)$

• 查找：$$\sum^n_{i=1}p\times i=\frac{1}{n}(1+2+\cdots n)=\frac{n+1}{2}$$

• 插入：$$\sum^n_{i=0} p \times (n-i)= \frac{1}{n+1}\sum^n_{i=0}(n-i)=\frac{n}{2}$$