資料結構學習-順序表

資料結構是一門研究非數值計算的程式設計中計算機的操作對象以及他們之間的關系和操作的學科。

資料類型：資料類型是一組性質相同的值的集合以及定義于這個值集合上的一組操作的總稱。

資料類型=值的集合+值集合上的一組操作

抽像資料類型：是将資料對象、資料對象之間關系和資料對象的基本操作封裝在一起的一種表達方式

線性表是由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);

}