线性表顺序存储

我们来谈一下线性表的顺序储存结构

图示：
photo_ex

定义：
- 由 n (n>=0)个数据特性相同的元素构成的有限序列称为线性表
- 线性表中元素的个数 n (n>=0)定义为线性表的长度，n = 0 时称为空表

特点：
- 而对于一个非空的线性表来说，通常具有以下特征
1、存在唯一的开始结点
2、存在唯一的终端结点
3、除了终端结点和开始结点，其间的每一个结点都有 一个直接前驱 和 一个直接后继
- 逻辑结构：线性结构
- 特点：类型相同、有限性、有序性
- 也是应用最广泛的数据结构之一

顺序储存：

线性表的顺序表示指的是用一组 地址连续的存储单元 依次存储线性表的数据元素，这种表示也称作线性表的 顺序存储 或 顺序映像

图例：

C++实现代码

main.cpp

#include"LinkListHead.h"
void menu();
int main()
{
	char choise;
	LinkList ElemList;
	menu();
	std::cout << "请输入你的选择" << std::endl;
	std::cin >> choise;
	switch (choise)
	{
	case '1':
		if (ElemList.Create())
		{
			if (!ElemList.Insert(100, 5))
			{
				std::cout << "不能插入100到5的位置是因为该表已满" << std::endl;
				ElemList.DisplayList();
			}
		}
		break;
	case '2':
		if (ElemList.Create())
		{
			if (!ElemList.Delete(3))
			{
				std::cout << "不能删除的原因是因为表为空或者没有该下标" << std::endl;
				ElemList.DisplayList();
			}
		}
		break;
	case '3':
		if (ElemList.Create())
		{
			if (ElemList.Insert(100, 6))
			{
				std::cout << "能插入是因为其中元素个数为5个" << std::endl;
				ElemList.DisplayList();
			}
		}
		break;
	case '4':
		if (ElemList.Create())
		{
			if (!ElemList.Insert(100, 7))
			{
				std::cout << "不能插入是因为该元素个数只有5个，无法在第七个位置插入一个数"
					<< std::endl;
				ElemList.DisplayList();
			}
		}
		break;
	case '5':
		if (ElemList.Create())
		{
			if (ElemList.Delete(4))
			{
				std::cout << "能删除是因为列表中有大于4个元素的个数" << std::endl;
				ElemList.DisplayList();
			}
		}
		break;
	case '6':
		if (ElemList.Create())
		{
			if (!ElemList.Delete(8))
			{
				std::cout << "不能在第8个位置删除的原因是列表中没有大于或等于8的个数"
					<< std::endl;
				ElemList.DisplayList();
			}
		}
		break;
	case '7':
		if (ElemList.Create())
		{
			if (ElemList.Insert(100, 1))
			{
				std::cout << "能在该位置插入的原因是改下标合法" << std::endl;
				ElemList.DisplayList();
			}
		}
		break;
	case '8':
		if (ElemList.Create())
		{
			if (ElemList.Delete(1))
			{
				std::cout << "该位置能够删除是因为该下标处于线性表长度中" << std::endl;
				ElemList.DisplayList();
			}
		}
		break;
	default:
		std::cout << "非法输入，结束" << std::endl;
		break;
	}
	return 0;
}

void menu()
{
	std::cout
		<<"1、申请10个空间，往空间中放进10个元素，然后随意增加一个元素
" 
		<<"2、申请10个空间，往空间中放进0个元素，然后随意删除一个元素
"
		<<"3、申请10个空间，往空间中放进5个元素，然后在第6个位置增加一个元素
"
		<<"4、申请10个空间，往空间中放进5个元素，然后在第7个位置增加一个元素
"
		<<"5、申请10个空间，往空间中放进5个元素，然后删除第4个位置的元素
"
		<<"6、申请10个空间，往空间中放进5个元素，然后删除第8个位置的元素
"
		<<"7、申请10个空间，往空间中放进0个元素，然后增加第1个位置的元素
"
		<<"8、申请10个空间，往空间中放进5个元素，然后删除第1个位置的元素
"
		<<std::endl;
}

LinkListHead.h

#pragma once
#ifndef _LINKLISTHEAD_H_
#define _LINKLISTHEAD_H_
#include<iostream>
#include<cstdlib>
typedef int DataType;
class LinkList
{
private:
	int length;//表元素的长度
	int maxsize;//表最大的长度
	bool empty;//判断表空
	DataType* list = nullptr;//表
public:
	LinkList();//初始化函数，初始化为空表 done
	LinkList(LinkList& L);//构造一个新的线性表 done
	bool Create();//创建顺序离散表 done
	bool Insert(DataType target, int index);//往第几个位置插入一个元素 done
	bool Delete(int index);//删除下标为index的元素 done
	int Find(DataType target);//找到是否有这些元素，然后返回该元素下标，如果没有，返回0
	void DisplayList();//显示线性表
	void DestoryList();//摧毁离散表
	virtual ~LinkList();//析构链表

};
#endif // !_LINKLISTHEAD_H_

LinkListHead.cpp

#include "LinkListHead.h"

LinkList::LinkList()
{
	length = 0;
	maxsize = 0;
	empty = true;
}

LinkList::LinkList(LinkList& L)
{
	length = L.length;
	maxsize = L.maxsize;
	empty = L.empty;
	//进行拷贝复制，申请新的顺序表
	list = new DataType[maxsize];//申请maxsize大小的空间
	for (int i = 0; i < length; i++)//进行每一个元素复制
		list[i] = L.list[i];

}

bool LinkList::Create()
{
	using std::cin;
	using std::cout;
	using std::endl;
	cout << "请输入申请顺序线性表的大小" << endl;
	cin >> maxsize;//输入线性表的大小
	list = new DataType[maxsize];//利用大小来创建线性表
	if (!list)//如果表为空
	{
		cout << "不能申请空间" << endl;
		exit(-1);//当申请空间失败的时候，退出
	}
	//当表空的时候，创建数据
	cout << "请输入有多少个数据" << endl;
	cin >> length;
	if (length<0 || length>maxsize)
	{
		cout << "非法输入创建失败" << endl;
		//失败后置空空间，恢复初始设置
		maxsize = 0;
		length = 0;
		delete[]list;
		list = nullptr;

		return false;//返回失败
	}
	else
	{
		cout << "请输入数据" << endl;
		for (int i = 0; i < length; i++)
			cin >> list[i];//进行数据输入
		cout << "输入成功，创建成功" << endl;
		empty = false;
		return true;//返回成功
	}
}

bool LinkList::Insert(DataType target, int index)
{
	using std::cout;
	using std::endl;
	//首先进行非法检查
	if (index<1 || index>length+1 || length == maxsize)//判断插入数的下表是否是合法
	{
		//非法的形式：
		//1、插入的下表上溢或者下溢
		//2、顺序表中的元素的长度已经等于最大值的长度
		cout << "非法插入" << endl;
		return false;
	}
	else
	{
		for (int i = length - 1; i >= index - 1; i--)
		{
			list[i + 1] = list[i];//整体元素往后移动一位
		}
		list[index - 1] = target;//把index位置插入元素
		length++;
		cout << "插入成功" << endl;
		return true;
	}
}

bool LinkList::Delete(int index)
{
	using std::endl;
	using std::cout;
	if (length == 0 || empty)
	{
		cout << "表空，无法删除" << endl;
		return false;
	}
	if (index<1 || index>length)
	{
		//大于有效长度，或者小于最小长度，非法
		cout << "非法下标" << endl;
		return false;
	}
	else
	{
		//如果不是以上的情况，那么正常删除其中的元素
		
		for (int i = index - 1; i < length; i++)
			list[i] = list[i + 1];//后一位赋值给前一位，覆盖掉前一位
		length--;//长度减少1
		cout << "删除完成" << endl;
		return true;//返回成功
	}
}

int LinkList::Find(DataType target)
{
	for (int i = 0; i < length; i++)
		if (list[i] == target)
			return i + 1;//找到了，返回其元素的下表
	return 0;//找不到，返回0
}

void LinkList::DisplayList()
{
	for (int i = 0; i < length; i++)
	{
		std::cout << list[i] << " ";
	}
	std::cout << "length = "<<length << std::endl;
	std::cout << std::endl;
}

void LinkList::DestoryList()
{
	delete[]list;
	length = 0;
	maxsize = 0;
	list = nullptr;
}

LinkList::~LinkList()
{
	delete[]list;
	length = 0;
	maxsize = 0;
	list = nullptr;
}