博客

顺序表的定义及基本操作

一、数据结构：顺序表的定义，创建，基本运算，实现

二、全部代码

1. 定义顺序表

#include<stdio.h>
#include<malloc.h>
#define max 100 //顺序表最大可能达到的长度 
typedef int Elem;
typedef struct SqList{ //定义顺序表 
	Elem data[max];//存储空间的基地址 
	int length; //当前长度 
}Sql; //顺序表的结构类型为SqList 

2. 初始化顺序表

//初始化顺序表（时间复杂度为O(1)） 
void InitList(Sql *&L){
	L=(Sql *)malloc(sizeof(Sql));  
	L->length=0; //空表长度为0 
} 

3. 创建顺序表

//创建顺序表 （时间复杂度为O(n)->循环体while） 
void CreateList(Sql *&L,Elem a[],int n) {
	L=(Sql *)malloc(sizeof(Sql));
	InitList(L);//先初始化，再创表
	for(int i=0; i<n; i++) {
		L->data[i]=a[i];
		L->length++;//表长自增，插入一个表长加1
	}
}

4. 销毁顺序表

//销毁顺序表 （时间复杂度为O(1)）
void DespList(Sql *&L){
	free(L);	
}

5. 判空

bool isEmpy(Sql *L){
	return (L->length == 0);//表长为0，则返回true
}

6. 查找(按位查找、按值查找)

//按位查找
bool GetElem(Sql *L,int n,Elem &e) {
	if(n<1||n>L->length ||isEmpy(L)) return 0;
	 e=L->data[n-1];//用e来接收查找的值
	 return 1; 
}
//按值查找，返回位置
int LocalElem(Sql *L,Elem e){
	if(isEmpy(L)) return 0;
	for(int i=0;i<L->length;i++){
		if(L->data[i]==e){
			return i+1;
		}
	}
}

7. 插入

//插入元素(按位插入)
bool GetInserter(Sql *&L,int n,Elem e) {//在第n个位置插入e
	if(n<1||n>L->length+1 || L->length>max) return 0;
	for(int i=L->length; i>n-1; i--) {
		L->data[i]=L->data[i-1];//元素后移(从最后一个元素开始往后移)
	}
	L->data[n-1]=e;
	L->length++;
	return 1;
}

8. 删除(按位删除、按值删除)

//按位删除
bool GetDelete(Sql *&L,int n,Elem &e){
	if(n<1||n>L->length||isEmpy(L)) return 0;
	e=L->data[n-1];
	for(int i=n-1;i<L->length;i++){
		L->data[i]=L->data[i+1];
	}
	L->length--;
	return 1;
} 
//按值删除
int LocalDelete(Sql *&L,Elem e){
	if(isEmpy(L)) return 0;
	for(int i=0;i<L->length;i++){
		if(L->data[i]==e){//先找到所要删除的那个值的位置
			for(int j=0;j<L->length;j++){
				L->data[i]=L->data[i+1];//前移
			}
			L->length--;
			return i+1;
		}
	}
}

9. 顺序表的长度

int ListLength(Sql *L){
	return (L->length);
}

10.输出所有元素

//输出顺序表中的全部元素
void DispList(Sql *L) {
	for(int i=0; i<L->length; i++) {
		printf("%d ",L->data[i]);
	}
}

11. 实现主函数main()

int main() {
	Sql *L;
	int a[]= {1,2,3,4,5};
	CreateList(L,a,5);
	DispList(L);
	if(isEmpy(L)) printf("空");
	else printf("\n不空\n");
	int e=8;
	GetInserter(L,2,e);
	DispList(L);
	GetElem(L,4,e);
	printf("\n按位查找---第4位的值位：%d\n",e);
	e=2; 
	printf("\n按值查找---顺序表中值%d的位置为第%d个\n",e,LocalElem(L,e));
	int n=1;
	GetDelete(L,n,e);
	printf("\n按位删除---所删除第%d位的值是：%d\n",n,e);
	e=4;
	printf("\n按值删除---所删除值%d的位置为第%d个\n",e,LocalDelete(L,e));
	
	DispList(L);
	printf("\n顺序表长度=%d\n",L->length);
	DespList(L);
	DispList(L);
	return 0;
}

12.全部代码

#include<stdio.h>
#include<malloc.h>
#define max 100 //顺序表最大可能达到的长度 
typedef int Elem;
typedef struct SqList{ //定义顺序表 
	Elem data[max];//存储空间的基地址 
	int length; //当前长度 
}Sql; //顺序表的结构类型为SqList 
void InitList(Sql *&L){
	L=(Sql *)malloc(sizeof(Sql));  
	L->length=0; //空表长度为0 
} 
//创建顺序表 （时间复杂度为O(n)->循环体while） 
void CreateList(Sql *&L,Elem a[],int n) {
	L=(Sql *)malloc(sizeof(Sql));
	InitList(L);//先初始化，再创表
	for(int i=0; i<n; i++) {
		L->data[i]=a[i];
		L->length++;//表长自增，插入一个表长加1
	}
}
//销毁顺序表 （时间复杂度为O(1)）
void DespList(Sql *&L){
	free(L);	
}
bool isEmpy(Sql *L){
	return (L->length == 0);//表长为0，则返回true
}
//按位查找
bool GetElem(Sql *L,int n,Elem &e) {
	if(n<1||n>L->length ||isEmpy(L)) return 0;
	 e=L->data[n-1];//用e来接收查找的值
	 return 1; 
}
//按值查找，返回位置
int LocalElem(Sql *L,Elem e){
	if(isEmpy(L)) return 0;
	for(int i=0;i<L->length;i++){
		if(L->data[i]==e){
			return i+1;
		}
	}
}
//插入元素(按位插入)
bool GetInserter(Sql *&L,int n,Elem e) {//在第n个位置插入e
	if(n<1||n>L->length+1 || L->length>max) return 0;
	for(int i=L->length; i>n-1; i--) {
		L->data[i]=L->data[i-1];//元素后移(从最后一个元素开始往后移)
	}
	L->data[n-1]=e;
	L->length++;
	return 1;
}
//按位删除
bool GetDelete(Sql *&L,int n,Elem &e){
	if(n<1||n>L->length||isEmpy(L)) return 0;
	e=L->data[n-1];
	for(int i=n-1;i<L->length;i++){
		L->data[i]=L->data[i+1];
	}
	L->length--;
	return 1;
} 
//按值删除
int LocalDelete(Sql *&L,Elem e){
	if(isEmpy(L)) return 0;
	for(int i=0;i<L->length;i++){
		if(L->data[i]==e){//先找到所要删除的那个值的位置
			for(int j=0;j<L->length;j++){
				L->data[i]=L->data[i+1];//前移
			}
			L->length--;
			return i+1;
		}
	}
}
int ListLength(Sql *L){
	return (L->length);
}

//输出顺序表中的全部元素
void DispList(Sql *L) {
	for(int i=0; i<L->length; i++) {
		printf("%d ",L->data[i]);
	}
}
int main() {
	Sql *L;
	int a[]= {1,2,3,4,5};
	CreateList(L,a,5);
	DispList(L);
	if(isEmpy(L)) printf("空");
	else printf("\n不空\n");
	int e=8;
	GetInserter(L,2,e);
	DispList(L);
	GetElem(L,4,e);
	printf("\n按位查找---第4位的值位：%d\n",e);
	e=2; 
	printf("\n按值查找---顺序表中值%d的位置为第%d个\n",e,LocalElem(L,e));
	
	int n=1;
	GetDelete(L,n,e);
	printf("\n按位删除---所删除第%d位的值是：%d\n",n,e);
	DispList(L);
	
	e=4;
	printf("\n按值删除---所删除值%d的位置为第%d个\n",e,LocalDelete(L,e));
	DispList(L);
	
	printf("\n顺序表长度=%d\n",L->length);
	DespList(L);
	DispList(L);
	return 0;
}