[数据结构与算法]数据结构学习-顺序表

数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及他们之间的关系和操作的学科。

数据类型：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。

数据类型=值的集合+值集合上的一组操作

抽像数据类型：是将数据对象、数据对象之间关系和数据对象的基本操作封装在一起的一种表达方式

线性表是由n个相同类型的数据元素组成的有限序列，线性表有两种存储方式，顺序存储和链式存储，采用顺序存储的线性表称为顺序表，采用链式存储的线性表称为链表，链表又分为：单链表、双向链表和循环链表。

顺序表中在逻辑上相邻的数据在计算机中存储的位置也是相邻的。顺序表可分为静态分配和动态分配两种方法。

静态分配：顺序表最简单的方法是使用定长数组data[]存储数据，设一个最大空间Maxsize，用length记录实际长度。

#define Maxsize 100
typedef struct{
    ElemType data[Maxsize];
    int length;
}SqList;

动态分配：在程序运行过程中，根据需要动态分配一段连续的空间（大小为Maxsize),用elem记录该空间的首地址，用length记录实际个数，在运算过程中，如果溢出，可以另外开辟一块更大的存储空间。

#define Maxsize 100
typedef struct{
    ElemType *elem;
    int length;
}SqList；

顺序表的基本操作

#include<iostream>
typedef int ElemType;
#define Maxsize 100
typedef struct {
	ElemType *elem;//列表首地址
	int length;//列表长度
}SqList;
//列表初始化
//初始化是指为顺序表分配一段预定大小的连续空间
bool InitList(SqList& L) {
	L.elem = new int[Maxsize];//用new分配大小为Maxsize的空间，分配成功后会返回空间的首地址
	if (!L.elem)				//分配失败会返回空指针
		return false;
	L.length = 0;
	return true;
}
//创建列表
//创建是向顺序表中输入数据，输入数据类型必须与类型定义中的类型一致
bool CreateList(SqList& L) {
	int x=0, i = 0;
	while (x!=-1) {
		if (L.length == Maxsize) {
			std::cout << "顺序表已满" << std::endl;
			return false;
		}
		std::cin >> x;
		L.elem[i++] = x;
		L.length++;
	}
	return true;
}
//取值
//顺序表中的任何一个元素都可以立即找到，称为随机存取方法
bool GetElem(SqList L,int i,int& e) {
	if (i<1 || i>L.length)
		return false;
	e = L.elem[i - 1];
	return true;
}
//查找
//查找元素返回所在位置
int LocateElem(SqList L,int e) {
	for (int i = 0; i < L.length; i++) {
		if (L.elem[i] == e)
			return i + 1;
	}
	return -1;
}
//插入
//在第i位插入e（i位表示意思是从1开始）
bool ListInsert_Sq(SqList &L,int i,int e) {
	if (i<1 || i>L.length+1||L.length==Maxsize)
		return false;
	for (int j = L.length - 1; j > i - 1;j--) {
		L.elem[j + 1] = L.elem[i];
	}
	L.elem[i - 1] = e;
	L.length++;
	return true;
}
//删除
//将要删除的元素存放到e中
bool ListDelete_Sq(SqList& L,int i,int e) {
	if (i<1 || i>L.length)
		return false;
	e = L.elem[i - 1];
	for (int j = i; j < L.length - 1;j++) {
		L.elem[j - 1] = L.elem[i];
	}
	L.length--;
	return true;
}
int main() {
	SqList L;
	if (!InitList(L)) {
		InitList(L);
	}
	CreateList(L);

}