数据结构：线性链表的顺序存储结构

首先先了解什么是线性表的顺序储存结构，线性表的顺序存储结构就是用一段连续的存储空间单元一次存储线性表的数据元素。

这里我们可以用C/C++语言来表示顺序存储结构。

于是我们来定义一个顺序存储的代码如下：

typedef int ElemType;   /*存储类型，视情况而定，这里假设是int*/

const int MAXSIZE = 100;  /*存储空间初始分配量*/

struct array
{
	ElemType data[MAXSIZE];  /*线性表的数组，最大值为MAXSIZE*/
	int length;  /*线性表的长度*/
};

从这里我们来讲解，顺序结构的三个属性：

存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置
线性表的最大存储容量：数组长度MAXSIZE
线性表当前长度:length

好了基础的说完了，我来贴代码了。

array.h

#ifndef ARRAY_H_
#define ARRAY_H_

#include <iostream>
using namespace std;

typedef int ElemType;

const int MAXSIZE = 100;

struct array
{
	ElemType data[MAXSIZE];
	int length;
};

class arraylist
{
public:
	arraylist();  /*构造函数，初始化线性表*/
	bool ListEmpty();/*判断线性表是否为空*/
	bool GetElem(int i, ElemType &e); /*根据i的值来获取线性表中对应的第i个元素，将元素的值赋给e*/
	int Locate(ElemType& e);/*返回线性表中e出现的首个位置*/
	bool ListInsert(int i,ElemType e); /*将e插入到i元素之前*/
	bool ListDelete(int i,ElemType &e); /*将线性表中的i位置元素删除，并将删除的值存放在e中*/
	int ListLength(); /*返回线性表的长度*/
	bool ListTravel(); /*遍历线性表*/
	void UnionList(array& arr1); /*将arr1中有，线性表中没有的元素插入到线性表的后面*/
	~arraylist();
private:
	array arr;
};

#endif

array.cpp

#include "array.h"

arraylist::arraylist()
{
	arr.length = 0;
	for(int i = 0; i< MAXSIZE; i++)
	{
		arr.data[i] = 0;
	}
}

bool arraylist::ListEmpty()
{
	if(arr.length == 0)
		return true;
	else
		return false;
}

bool arraylist::GetElem(int pos, ElemType& ptr)
{
	if(arr.data == 0 || pos < 1|| pos>arr.length)
		return false;
	else
		ptr = arr.data[pos - 1];
	return true;
}

int arraylist::Locate(ElemType& Elem)
{
	for(int i = 0; i<arr.length; i++)
	{
		if(Elem == arr.data[i])
			return i+1;
	}
	return 0;
}

bool arraylist::ListInsert(int pos,ElemType Elem)
{
	if(arr.length == MAXSIZE)
	{
		return false;
	}
	if(pos > arr.length + 1 || pos < 1)
	{
		return false;
	}
	if(pos < arr.length + 1)
	{
		for(int i= pos; i <= arr.length; i++)
		{
			arr.data[i+1] = arr.data[i];
		}
	}
	arr.data[pos]=Elem;
	arr.length++;
	return true;
}
bool arraylist::ListDelete(int pos,ElemType &Elem)
{
	if(ListEmpty())
	{
		return false;
	}
	if(pos<1 || pos > arr.length)
	{
		return false;
	}
	Elem = arr.data[pos -1];
	for(int i= pos;i<arr.length;i++)
	{
		arr.data[i -1] = arr.data[i];
	}
	arr.length--;
	return true;
}

int arraylist::ListLength()
{
	return arr.length;
}

void arraylist::UnionList(array &arr2)
{
	int lena = arr.length;
	int lenb = arr2.length;
	int item;
	int flag = 1;

	for(int i = 0;i < lenb; i++)
	{
		if(arr2.length == 0 || i + 1 < 1||i+1 > arr2.length)
			flag = 0;
		item = arr2.data[i];
		if(flag)
		{
			if(Locate(item) == 0)
				ListInsert(++lena,item);
		}
	}
}

bool arraylist::ListTravel()
{
	if(ListEmpty())
	{
		return false;
	}
	for(int i = 0; i<arr.length; i++)
	{
		cout<<arr.data[i]<<" ";
	}
	cout<<endl;
	return true;
}

arraylist::~arraylist()
{
	arr.length = 0;
	for(int i = 0; i< MAXSIZE; i++)
	{
		arr.data[i] = 0;
	}
}

main.cpp

#include "array.h"

int main()
{
    arraylist list;
    for(int i = 0; i<5; i++)
    {
        list.ListInsert(i,i);
    }
    list.ListTravel();
    int var = 2;
    int pos = list.Locate(var);
    if(pos != 0)
    {
        int result;
        list.ListDelete(pos,result);
        cout<<"delete: "<<result<<endl;
    }
    list.ListTravel();

    array arr2 = {0};
    for(int i = 0; i<4; i++)
        arr2.data[i] = 6;
    arr2.length = 4;
    for(int i= 0 ; i<4; i++)
        cout<<arr2.data[i]<<" ";
    cout<<endl;

    list.UnionList(arr2);
    list.ListTravel();

    system("pause");
    return 0;
}

最终运行结果：

这种顺序存储的线性表的优点的话：

无需为表示表中的元素之间的逻辑关系而增加额外的存储空间
可以快速的存取表中的任意位置的元素

不过缺点也很明显：

插入删除操作需要移动大量的元素
当线性表变化较大的时候，难以确定存储空间的容量
造成存储空间的“碎片”

而且，这些数据保存在内存中，如果数据很多的话，就会造成很大的内存浪费，所以一般数据较大的时候，最好不要考虑这种。而是另外一种线性表的链式存储结构，这个在下篇博客中我再来写。

同时也欢迎大家有疑问在评论区问我，大家一起进步。