大话数据结构学习笔记(2)线性表的顺序存储结构

一、相关知识点 

1、线性表的定义：线性表的数据对象集合为{a1,a2,a3,....,an}，每个元素的类型相同。其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素。除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

2、线性表的顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。在C++里可以通过一维数组来实现。比如定义数组:

int *list=new int[n]；

注意线性表的下标是从1开始的，而数组的下标的是从0开始的。

意思就是:list[0]=a1;list[1]=a2；.......list[n-1]=an；

线性表的顺序存储结构代码：

#define MAXSIZE 20;        //存储空间初始分配量
typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];//数组存储数据元素，最大值为MAXSIZE
    int length;
}Sqlist

3、顺序存储结构需要三个属性：

（1）存储空间的起始位置：数组data,它的存储空间就是存储空间的存储位置；

（2）线性表的最大存储容量：数组长度MaxSize；

（3）线性表的当前长度：length；

注意数组长度和线性表长度的区别：前者是我们预先定义好的，是不变的；后者随着我们对线性表删除，插值等操作是可以改变的。

线性表的长度是小于等于数组长度的。

二、用C++实现顺序存储结构的创建、插入、删除等操作

#include <iostream>
using namespace std;
const int MAXSIZE = 20;
template < typename T > 	         //类模板定义
class SeqList
{
public:
	SeqList(T list[], int n);        //有参构造函数，建立长度为n的线性表
	~SeqList();
	void printList();	         //打印线性表
	void getListLength();	         //求当前线性表的长度
	T get(int i);		         //查找线性表第i个元素
	int getIndex(T x);               //查找元素x并返回索引
	void insertList(int i, T x);     //在第i个位置插入值为x的元素
	T deleteList(int i);		 //删除第i个元素
private:
	T data[MAXSIZE];		 //存储线性表
	int length;			 //线性表长度
	
};

template <typename T>
SeqList<T>::SeqList(T list[], int n)
{
	if (n > MAXSIZE){ cout << "超出范围"; }
	for (int i = 0; i < n; i++)
	{
		this->data[i] = list[i];
	}
	this->length = n;
}

template<typename T>
SeqList<T>::~SeqList()
{

}

template<typename T>
void SeqList<T>::printList()
{
	cout << "当前线性表元素: ";
	for (int i = 0; i < length; i++)
	{
		cout << data[i] << " ";
	}
	cout << endl;
}

template<typename T>
void SeqList<T>::getListLength()
{
	cout << "当前线性表长度: " << length << endl;
}

template<typename T>
T SeqList<T>::get(int i)
{
	if (i > MAXSIZE || i<1){ cout << "超出范围"; }
	else
	{
		cout << "第i个位置的元素：" << data[i - 1] << endl;
		return data[i - 1]; }
}

template<typename T>
int SeqList<T>::getIndex(T x)
{
	for (int i = 0; i < length; i++)
	{
		if (data[i] == x)
			return i + 1;
	}
	return 0;
}

template<typename T>
void SeqList<T>::insertList(int i, T x)
{
	if (i > MAXSIZE || i<1){ cout<<"超出范围"; }
	else
	{
		if (i < length)		//插入位置不在表尾
		{
			for (int j = length; j >= i; j--)
			{
				data[j] = data[j - 1];					//元素后移一个位置
			}
			data[i - 1] = x;
			length++;
		}
	}
}

template<typename T>
T SeqList<T>::deleteList(int i)
{
	if (i > MAXSIZE || i<1){ cout << "超出范围"; }
	else
	{
		T x = data[i - 1];	//取出第i个元素
		for (int j = i; j < length; j++)
		{
			data[j - 1] = data[j];
		}
		length--;
		return x;
	}
}

void main()
{
	int list[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	SeqList<int> seqlist(list, 7);
	seqlist.printList();
	seqlist.getListLength();
	seqlist.get(3);
	cout << seqlist.getIndex(2) << endl;
	seqlist.insertList(2, 10);
	seqlist.printList();
	seqlist.getListLength();
	seqlist.deleteList(2);
	seqlist.printList();
	seqlist.getListLength();
	system("pause");
}

 函数输出：