線性表之《順序表的表示及基本操作的實作》

一、順序表的表示

1、靜態順序存盤結構

/*線性表靜態順序存盤結構*/
#define MAXSIZE 100 //定義線性表的最大長度
typedef int ElemType; //定義抽象型別ElemType為int型別
typedef struct
{
	ElemType elem[MAXSIZE]; //宣告一個ElemType型別的陣列elem
	int length; //順序表的當前長度
}SqList; //此結構為SqList型別

2、動態順序存盤結構

/*線性表動態順序存盤結構*/
#define MAXSIZE 100 //定義線性表的最大長度
typedef int ElemType; //定義抽象型別ElemType為int型別
typedef struct
{
	ElemType* elem;//存盤空間的基地址
	int length;//當前長度
}SqList;

二、順序表基本操作的實作

補充：操作演算法中用到的預定義常量和型別

//函式結果狀態代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//Status是函式回傳值型別，其值是函式結果狀態代碼
typedef int Status;

線性表的定義：

#define MAXSIZE 100 //定義線性表的最大長度
typedef int ElemType; //定義抽象型別ElemType為int型別
typedef struct
{
	ElemType* elem;//存盤空間的基地址
	int length;//當前長度
}SqList;

1、初始化

演算法思想
(1)為順序表動態分配一個預定義大小的陣列空間，使elem指向這段空間的基地址
(2)使該順序表的當前長度為0

/*順序表的初始化*/
typedef int Status;
Status InitList(SqList& L)//修改線性表，按參考傳遞
{
	L.elem = new ElemType[MAXSIZE]; //為順序表分配空間
	if (!L.elem)  //開辟存盤空間失敗
		exit(OVERFLOW); 
	L.length = 0; //線性表的長度為0
	return OK;
}

2、查找

演算法思想：
(1)從第一個元素起，依次和e相比較
(2)若第i個元素的值等于e,則查找成功，回傳該元素的位序 i + 1
(3)若查遍整個順序表都沒有找到，則查找失敗，回傳0

/*順序表的查找*/
int LocateElem(SqList L, ElemType e)
{
	for (i = 0;i < L.length;i++) //i 為下標序號
		if (L.elem[i] == e)
			return i + 1; //查找成功，回傳i+1
	return 0; //查找失敗，回傳0
}

3、插入

演算法思想：
(1)檢查插入的位置i是否合法(合法范圍 1 <= i <= n + 1), 若不合法回傳ERROR
(2)檢查陣列空間是否存滿，若存滿回傳ERROR
(3)從第n個元素到第i個元素依次往后移動一位
(4)將要插入的元素存到第i個位置
(5)表長 + 1
(6)插入成功，回傳OK

/*順序表的插入*/
typedef int ElemType;
typedef int Status;
Status ListInsert(SqList& L, int i, ElemType e)
{
	if (i < 1 || i > L.length + 1) return ERROR;//插入位置不合法
	if (L.length == MAXSIZE) return ERROR;//陣列空間已滿
	for (j = L.length - 1;j >= i - 1;j--)
		L.elem[j + 1] = L.elem[j];//插入位置及之后元素后移
	L.elem[i - 1] = e;//新插入的元素e存到i-1
	++L.length;//表長+1
	return OK;
}

4、洗掉

演算法思想
(1)判斷洗掉元素位置是否合法
(2)將洗掉元素存入到e中
(3)將第i - 1到第i個元素依次往前移動一位
(4)表長 - 1，洗掉成功回傳OK

/*順序表的洗掉*/
typedef int Status;
typedef int ElemType;
Status ListDelete(SqList& L, int i, ElemType& e)
{
	if (i < 1 || i > L.length + 1) return ERROR;//判斷位置是否合法
	e = L.elem[i - 1];//洗掉元素存入e
	for (j = i, j <= L.length -1, j++)
		L.elem[j - 1] = L.length[j];
	--L.length;
	return OK;
}

5、順序表的操作

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 100
#define OK 1
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define ERROE 0

typedef int ElemType;
typedef int Status;

/*定義順序表*/
typedef struct
{
	ElemType* elem;//陣列空間基指標
	int length;
}SqList;

Status InitList_Sq(SqList& L);/*初始化順序表*/
void InputList_Sq(SqList& L);/*順序表的輸入*/
void Output_Sq(SqList& L);/*順序表的輸出*/
int LocateElem_Sq(SqList L, ElemType e);/*順序表的查找*/
Status InsertList_Sq(SqList& L, int i, ElemType e);/*順序表的插入*/
Status DeleteList_Sq(SqList& L, int i, ElemType e);/*順序表的洗掉*/

/*main函式*/
int main(void)
{
	SqList L;//順序表L
	int i, value;
	InitList_Sq(L);//初始化順序表
	InputList_Sq(L);//順序表的輸入
	Output_Sq(L);//順序表的輸出

	printf("\n請輸入要查找的元素：");
	int e;
	scanf_s("%d", &e);//輸入要查找的元素
	int locate = LocateElem_Sq(L, e);
	printf("要查找元素所在的位置為：第 %d 位",locate);

	printf("\n請輸入要插入的位置i:");
	scanf_s("%d", &i);
	printf("請輸入要插入的元素：");
	scanf_s("%d", &e);
	value =  InsertList_Sq(L, i, e);//插入元素
	if (value)
		Output_Sq(L);//輸出
	else
		printf("插入失敗！");

	printf("\n請輸入要洗掉元素的位置i:");
	scanf_s("%d", &i);
	value = DeleteList_Sq(L, i, e);//洗掉元素
	if (value)
		Output_Sq(L);//輸出
	else
		printf("洗掉失敗！");
	return 0;
}

/*初始化順序表*/
Status InitList_Sq(SqList& L)
{
	L.elem = new ElemType[MAXSIZE];//開辟空間
	if (!L.elem) exit(OVERFLOW);//分配空間失敗
	L.length = 0;//定義表長為0
	printf("順序表初始化成功！\n");//初始化提示
	return OK;
}

/*順序表的輸入*/
void InputList_Sq(SqList& L)
{
	int n;
	printf("請輸入順序表的長度：");
	scanf_s("%d", &n);
	L.length = n;
	if (n > MAXSIZE)//檢查輸入的長度是否合法
		printf("陣列長度不合法！");
	else
	{
		printf("請輸入%d個元素：\n", n);
		for (int i = 0;i < L.length;i++)
		{
			printf("第%d個元素為：", i);
			scanf_s("%d", &L.elem[i]);
		}
	}
}

/*順序表的輸出*/
void Output_Sq(SqList& L)
{
	printf("當前順序表的元素依次是：");
	for (int i = 0;i < L.length;i++)
		printf("%d ", L.elem[i]);
}

/*順序表的查找*/
int LocateElem_Sq(SqList L, ElemType e)
{
	for (int i = 0;i < L.length;i++)
		if (L.elem[i] == e) return i + 1;//查找成功回傳i+1
	return 0;
}

/*順序表的插入*/
Status InsertList_Sq(SqList& L, int i, ElemType e)
{
	if (i < 1 || i > L.length + 1) return ERROE;//i值不合法
	if (L.length == MAXSIZE) return ERROE;//存盤空間已滿
	for (int j = L.length - 1;j >= i - 1;j--)
		L.elem[j + 1] = L.elem[j];//插入位置后面的元素依次往后移動
	L.elem[i - 1] = e;//新插入的元素存在i - 1 中
	++L.length;//表長+1
	return OK;
}

/*順序表的洗掉*/
Status DeleteList_Sq(SqList& L, int i, ElemType e)
{
	if (i < 1 || i > L.length) return ERROE;// i值不合法
	e = L.elem[i - 1];//將洗掉的元素存入到e中
	for (int j = i;j <= L.length - 1;j++)
		L.elem[j - 1] = L.elem[j];//將i位置后面的元素往前移動一位
	--L.length;//表長-1
	return OK;
}

運行結果：