顺序表的实现

在顺序表中，每个数组储存的地址是连续的。如下图

我们在写顺序表是要定义一个指针来储存我们的数据，在定义这个指针的时候，需要对指针赋予一定是储存空间。运用malloc进行操作：List.Elem = (int *)malloc(List_size * sizeof(int));

为了方便以后对表进行操作，我们需要定义一个int类型的参数来存放当前表的长度，我的代码用了：Length来表示。

还有我们需要给定表的容量，这样才能合理分配电脑里的储存空间，避免滥用，导致程序运行时内存不够。

下面是我的代码：

#include<iostream>#include<malloc.h>#define List_size 10#define List_recrement 10using namespace std;class SqList {                                       //定义一个顺序表的类public:	int *Elem;                                     //用于储存数据	int Length;                                   //表的当前长度	int Size;                                     //表的容量	bool initList(SqList &List);	bool Create_List(SqList &List);	bool Insert_List(SqList &List, int Position, int element);	bool Delet_List(SqList &List, int Position);	void Output_List(SqList &List);};bool SqList::initList(SqList &List) {                                    //  初始化顺序表	List.Elem = (int *)malloc(List_size * sizeof(int));	if (!Elem) {		cout << "OVERFLOW" << endl;		return false;	}	List.Size = List_size;	List.Length = 0;	return true;}bool SqList::Create_List(SqList &List) {                               //创建一个顺序表	int element = 1;	int *p;	p = List.Elem;	while (element) {		if (List.Length >= List.Size) {			List.Elem = (int *)realloc(List.Elem,(List.Size+ List_recrement) * sizeof(int));			List.Size += List_recrement;		}		while (Elem && (List.Length <= List.Size)) {			cout << "Please enter the NO." << List.Length + 1 << " element(0 for end):";			cin >> element;			if (element) {				*p = element;				p++;				List.Length++;			}			else break;		}	}	return true;}bool SqList::Insert_List(SqList &List, int Position, int element) {                     //在表中指定位置插入数据	int *p,*q;	if (Position < 1 && Position >= List.Length) {		cout << "The position you gave is not exist,please enter again:";		cin >> Position;	}	p = List.Elem+Position-1;                            //point to the head element	q = p + List.Size - 1;                               //point to the tail element	while (q >= p) {		*(q+1) = *q;		q--;	}	*p = element;	++List.Length;	return true;}bool SqList::Delet_List(SqList &List, int Position) {                 //删除表中指定位置的元素	int *p, i;	p = List.Elem + Position - 1;                      //point to the exact position	for (i = 0; i < List.Length - Position; ++i) {		*p = *(p + 1);		p++;	}	--List.Length;	*p = NULL;	return true;}void SqList::Output_List(SqList &List) {                             //输出表	int i = 0;	int *p;	p = List.Elem;	while (i < List.Length) {		cout << *p << " ";		p++;		i++;	}	cout << endl;}void main() {	SqList List1;	List1.initList(List1);	List1.Create_List(List1);	List1.Output_List(List1);	List1.Insert_List(List1, 2, 10);	List1.Output_List(List1);	List1.Delet_List(List1, 4);	List1.Output_List(List1);	system("pause");}