C++順序表的基本操作實(shí)現(xiàn)

更新時間：2022年02月11日 09:11:20 作者：通過計(jì)算機(jī)改變世界

大家好，本篇文章主要講的是C++順序表的基本操作實(shí)現(xiàn)，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下

1.順序表的定義

線性表的順序存儲又稱順序表。它是用一組地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素，從而使得邏輯上相鄰的兩個元素在物理位置上也相鄰。第1個元素存儲在線性表的起始位置，第i個元素的存儲位置后面緊鄰這存儲的是第i+1個元素，稱 i 為元素ai在線性表中的位序。因此，順序表的特點(diǎn)是表中元素的邏輯順序和物理順序相同。

假定線性表中的元素類型為ElemType,則線性表的順序存儲為

#define ElemType int
#define MaxSize 50  //定義線性表的最大長度
typedef struct{
    ElemType data[MaxSize] //順序表的元素
    int length; //順序表的當(dāng)前長度
}SqList;   //順序表的類型定義

此時，一維數(shù)組是靜態(tài)分配，由于數(shù)組的大小和空間事先已經(jīng)固定，一單空間占滿，再加入新的數(shù)據(jù)就會產(chǎn)生溢出，進(jìn)而導(dǎo)致程序崩潰。

2.順序表上基本操作的實(shí)現(xiàn)

（1）初始化操作
初始化順序表。構(gòu)造一個空的線性表。

void IniteList(SqList &L){
	memset(L.data,0,sizeof(L)); //將順序表L中的數(shù)據(jù)初始化為0 
	L.length = 0;
}

注意： “&”表示C++中的應(yīng)用調(diào)用，后面就不一一贅述了！
（2）創(chuàng)建順序表

bool CreateList(SqList &L,int n){
	if(n<0||n>MaxSize){  //創(chuàng)建順序表的個數(shù)不合理
		return false;
	}
	L.length = n;
	cout << "請依次輸出" << n <<"個數(shù)并用空格隔開："; 
	for(int i=0;i<L.length;i++){
		cin >> L.data[i];
	}
	return true;
}

（3）插入操作
在順序表L的第i（1 <= i <= L.length+1)個位置插入新元素e。若 i 的輸入不合法，則返回false,表示插入失??；否則，將第 i 個元素及其后的所有元素依次往后移動一個位置，騰出一個空位置插入新元素e,順序表的長度加1，插入成功，返回true.

bool InserteList(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1){
		return false;
		cout << "插入位置不合法！"; 
	}
	if(L.length == MaxSize){
		return false;
		cout << "當(dāng)前順序表空間已滿！";
	}
	for(int j=L.length;j>=i;j--){  //先移動最后一個元素，在移動其他的
		L.data[j]=L.data[j-1];//將i以及i之后的所有元素都往后移 
	}
	L.data[i-1]=e; //注意：先后移完之后在插入 
	L.length++;
	return true;
}

注意： 區(qū)別順序表的位序和數(shù)組下標(biāo)。前者是從1開始，后者是從0開始。
（4）刪除操作
刪除順序表L中的第 i （1 <= i <= L.length) 個位置的元素，用應(yīng)用變量e返回。若 i 的輸入不合法，則返回 false;否則，將被刪除元素賦給引用變量e,并將第 i + 1 個元素及其后的所有元素依次往前移動一個位置，返回true。

bool DeleteList(SqList &L,int i,ElemType e){
	if(i<1||i>L.length){
		return false;
	}
	e=L.data[i-1]; //將所刪除的元素賦值給 e
	for(int j=i;j<L.length;j++){  //j = i,在數(shù)組中下標(biāo)表示就是所刪除元素后面第一個元素
		L.data[j-1]=L.data[j]; //將i之后的元素都往前移 
	}
	L.length--;
	return true;
}

（5）查找（按值查找）
在順序表L中查找第一個元素值等于 e 的元素，并將其返回。

int Search1_List(SqList &L,ElemType e){
	int j=0;
	for(int i=0;i<L.length;i++){
		if(L.data[i] == e){
			j=i+1;   //下標(biāo)為 i 的元素值等于 e ,將其返回其位序 i+1
		}
	}
	return j;
}

（6）查找（按序查找）
在順序表中返回指定位置的元素。

int Search2_List(SqList &L,int i){
	if(i<1||i>L.length){
		cout << "查找位置不合理！";
	}
	return L.data[i-1];
}

（7）打印操作
按前后順序打印線性表L中的所有值。

void PrintList(SqList L){
	cout << "順序表中所有元素為：";
	for(int j=0;j<L.length;j++){
		cout << L.data[j] << " ";
	} 
	cout <<endl;
}

完整代碼如下：

/* 創(chuàng)建順序表 實(shí)現(xiàn)插入，刪除，按值查找，按序查找，打印順序表 */
#include<iostream>
#include<stdlib.h>
#include<cstring>
#include<string.h>
#define ElemType int
#define MaxSize 100
using namespace std;
typedef struct{
	ElemType data[MaxSize];
	int length; //數(shù)序標(biāo)的長度 
}SqList;
//初始化順序表
void IniteList(SqList &L){
	memset(L.data,0,sizeof(L)); //將順序表L中的數(shù)據(jù)初始化為0 
	L.length = 0;
} 
//創(chuàng)建順序表函數(shù) 
bool CreateList(SqList &L,int n){
	if(n<0||n>MaxSize){
		return false;
	}
	L.length = n;
	cout << "請依次輸出" << n <<"個數(shù)并用空格隔開："; 
	for(int i=0;i<L.length;i++){
		cin >> L.data[i];
	}
	return true;
} 
//順序表L中在第i個位插入元素
bool InserteList(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1){
		return false;
		cout << "插入位置不合法！"; 
	}
	if(L.length == MaxSize){
		return false;
		cout << "當(dāng)前順序表空間已滿！";
	}
	for(int j=L.length;j>=i;j--){
		L.data[j]=L.data[j-1];//將i以及i之后的所有元素都往后移 
	}
	L.data[i-1]=e; //注意：先后移完之后在插入 
	L.length++;
	return true;
}
//刪除順序表L中第i個元素的位置上 
bool DeleteList(SqList &L,int i,ElemType e){
	if(i<1||i>L.length){
		return false;
	}
	e=L.data[i-1]; //將所刪除的元素賦值給 e
	for(int j=i;j<L.length;j++){
		L.data[j-1]=L.data[j]; //將i之后的元素都往前移 
	}
	L.length--;
	return true;
}
//查找(按值查找）函數(shù)
int Search1_List(SqList &L,ElemType e){
	int j=0;
	for(int i=0;i<L.length;i++){
		if(L.data[i] == e){
			j=i+1;
		}
	}
	return j;
} 
//查找(按序查找）函數(shù)
int Search2_List(SqList &L,int i){
	if(i<1||i>L.length){
		cout << "查找位置不合理！";
	}
	return L.data[i-1];
} 
//打印輸出順序表函數(shù)
void PrintList(SqList L){
	cout << "順序表中所有元素為：";
	for(int j=0;j<L.length;j++){
		cout << L.data[j] << " ";
	} 
	cout <<endl;
} 
//創(chuàng)建
void Create(SqList &L){
	int n;bool flag;
	cout << "請輸入所創(chuàng)建順序表中元素的個數(shù)：";
	cin >> n;
	flag = CreateList(L,n);
	if(flag){
		cout << "創(chuàng)建成功！";
		PrintList(L);
	}
	else
	  cout << "創(chuàng)建失?。?; 
} 
//插入 
void Insert(SqList &L){
	int i; 
	int e;
	bool flag;
	cout << "請輸入插入位置和所插元素：";
	cin >> i >> e;
	flag = InserteList(L,i,e);
	if(flag){
		cout << "插入成功！\n" << "插入后" ;
		PrintList(L);
	}
	else 
	  cout << "插入失?。?;
}
//刪除 
void Delete(SqList &L){
	int i; int e; bool flag;
	cout << "請輸入刪除位置：";
	cin >> i;
	flag = DeleteList(L,i,e);
	if(flag){
		cout << "刪除成功！" << "刪除后";
		PrintList(L);
	}
	else 
	  cout << "刪除位置不合法！";
}
//按值查找
void Search_1(SqList &L){
	int e,a;
	cout << "請輸入要查找的值：";
	cin >> e;
	a = Search1_List(L,e);
	cout << e << "在順序表L中的位置為："<< a << endl;
} 
//按序查找
void Search_2(SqList &L){
	int i;
	cout << "請輸入要查找的位置：\n";
	cin >> i;
	int j = Search2_List(L,i);
	cout << "順序表L第" << i << "個位置上的元素為" << j; 
} 
int main(){
	SqList L;
	IniteList(L);
	Create(L);
	Insert(L);
	Delete(L);
	Search_1(L);
	Search_2(L);
	return 0;
}

編譯器DEVC++:
編譯結(jié)果：

在這里插入圖片描述