当前位置：主页 > 查看内容

手把手带你入门--线性表的顺序存储（大话数据结构）

发布时间：2021-08-06 00:00| 有位朋友查看

简介：C语言简单实现线性表的顺序存储线性表的顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构实际上就是在内存中找一块连续的存储空间然后将相同数据类型的数据元素存储在这块存储空间中。所以用C语言中的一维数……

C语言简单实现线性表的顺序存储

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表的顺序存储结构，实际上就是在内存中找一块连续的存储空间，然后将相同数据类型的数据元素存储在这块存储空间中。所以用C语言中的一维数组就可以实现顺序存储结构。

线性表的顺序存储结构优点在于可以快速随机访问表中任意位置的元素，并且~~因为其占用的一段连续的存储空间，所以不需要为表示元素之间的逻辑关系来增加额外的存储空间~~节省空间（相对）。

而线性表的顺序存储结构的缺点就在于插入和删除操作需要移动大量元素，执行效率低，并且数组的容量需要提前确定，因此可能造成空间浪费。

线性表的基本结构：

要存储的数据
线性表长度
数组的最大值

typedef struct{
	ElemType data[MAX];
	int length;
}SqList;

准备工作：

#include<stdio.h>

#define MAX 20
//数组的最大长度
#define OK 1
#define error 0
//OK和error代表函数状态，分别为1（函数成功运行），0（函数出错）
typedef int Status;
//Status是函数类型，其值是函数结果状态代码，如OK代表成功，error代表出错。
typedef int ElemType;
//ElemType代表数组类型，根据实际情况确定，这里假设为int型

线性表的顺序存储结构的8种基本操作：

初始化
判断线性表是否为空
清空线性表
返回线性表的给定位置元素值
插入元素
删除元素
查找元素
合并线性表

下面给出具体分析：

线性表的初始化：

即将线性表的长度赋值为0

Status initList(SqList *L){
	L->length = 0;
	return OK;
}

判断线性表是否为空:

这里我稍微做了一点改进，直接用bool返回线性表为空的真假：

长度为真，返回 true。

长度为假，返回 false。

//判断线性表是否为空
bool ListEmpty(SqList L){
	if(L.length == 0)
		return true;
	else
		return false;
}

清空线性表：

与初始化一样，将线性表的长度置为0。

Status ClearList(SqList *L){
	L->length = 0;
	return OK;
}

返回线性表的给定位置元素值：

1.首先判断该元素是否合理

最小位置不能小于1
最大位置不能大于线性表的长度
线性表的长度不能为0

2.然后将该位置元素的值赋值给e。

（因为要保留e的值，不能使e所占内存空间在函数调用完成后自动释放，所以这里采用指针）

Status GetElem(SqList L,int i,ElemType *e){
	if(i < 1 || i > L.length || L.length == 0)
		return error;
	*e = L.data[i-1];
	return OK;
}

插入元素：

1.判断限制条件，如果线性表已满，插入位置不合理，则插入失败。

2.如果是在最后一个位置，直接赋值即可

3.如果不在最后一个位置，从最后一个位置开始，全部后移一位。

4.长度加一，给即将插入的元素赋值

PS：因为数组是从0开始计数的，所以对应线性表的位置，永远减一
线性表改变，所以需要传指针。

//插入操作：在 L中的第 i 个位置插入新元素 e
Status ListInsert(SqList *L,int i,ElemType e){
	if(L.length == MAX)
		return error;
		//判断线性表长度是否大于数组长度 
	if(i < 1 || i > L.length + 1)
		return error;
		//判断插入位置是否合理 
	if(i <= L.length){
		for(int k = L.length - 1;k >= i - 1;k--)
			L->data[k+1] = L->data[k];	
		//如果插入位置不在表的末尾，则从线性表的最后一个位置开始，所有元素向后移动一位
		//一直到插入位置的前一个元素		 
	}	
	L.length++;
	L->data[i-1] = e;
	//长度加一，为新插入的元素赋值 
}

删除元素：

1.先判断删除位置是否合理，具体如上。

2.将要删除的元素的值赋值给e。

3.如果是在最后一个位置，直接删除即可

4.如果不在最后一个位置，从该位置的后一位开始，全部前移一位。

4.长度减一，给即将插入的元素赋值

PS：因为数组是从0开始计数的，所以对应线性表的位置，永远减一。线性表改变，所以需要传指针。需要获得e的值，e也要传指针。

//删除操作：删除 L 的第一个数据元素，并用 e返回其值
Status ListDelete(SqList *L,int i,ElemType *e){
	if(L->length == 0)
		return error;
	if(i < 1 || i > length)
		return error;
	*e = L->data[i-1];
	if(i < L->length){
		for(int k = i; k < L->length ;k++){
			L->data[k-1] = L->data[k]; 
		}
	}
	L->length--;
	return OK;
}

查找元素：

1.线性表长度为0，查找失败

2.遍历数组，成功则返回其在线性表中的位置

Status LocateElem(SqList L,ElemType e){
	if(L.length == 0)
		return 0;
	for(int i = 0;i < L.length;i++){
		if(e == L.data[i])
		return i + 1;
	}
	return 0;
}

合并两个线性表（将Lb中的元素插入La）：

1.遍历Lb中数组，得到第i个位置对应元素的值，赋与e。

2.如果La中没有对应的元素，将e的值插入到La的最后一个位置。

3.La长度加一。

//合并两个数组
Status ListUnion(SqList *La,SqList Lb){
	ElemType e;
	int La_len = La->length;
	int Lb_len = Lb.length;
	for(int i = 1 ; i <= Lb_len ; i++){
		GetElem(Lb,i,&e);
		if(!LocateElem(*La,e))
			ListInsert(La,++La_len,e);
	}
}

完整代码实现（加入测试）：

#include<stdio.h>

#define MAX 20
//数组的最大长度
#define OK 1
#define error 0

typedef int Status;
//Status是函数类型，其值是函数结果状态代码，如OK代表成功，error代表出错。
typedef int ElemType;
//ElemType代表数组类型，根据实际情况确定，这里假设为int型

typedef struct{
	ElemType data[MAX];
	int length;
}SqList; 

//初始化线性表 
Status initList(SqList *L){
	L->length = 0;
	return OK;
}

//判断线性表是否为空
bool ListEmpty(SqList L){
	if(L.length == 0)
		return true;
	else
		return false;
} 

//输出数组数据 
void ListTraverse(SqList L){
	for(int i = 0; i < L.length; i++)
		printf("%d ",L.data[i]);
	printf("\n");	
}

//清空线性表
Status ClearList(SqList *L){
	L->length = 0;
	return OK;
} 

//用e返回L中第 i个数据元素的值
Status GetElem(SqList L,int i,ElemType *e){
	if(i < 1 || i > L.length || L.length == 0)
		return error;
	*e = L.data[i-1];
	return OK;
} 

//查找元素 e 
Status LocateElem(SqList L,ElemType e){
	if(L.length == 0)
		return 0;
	for(int i = 0;i < L.length;i++){
		if(e == L.data[i])
		return i + 1;
	}
	return 0;
}

//插入操作：在 L中的第 i 个位置插入新元素 e
Status ListInsert(SqList *L,int i,ElemType e){
	if(L->length == MAX)
		return error;
		//判断线性表长度是否大于数组长度 
	if(i < 1 || i > L->length + 1)
		return error;
		//判断插入位置是否合理 
	if(i <= L->length){
		for(int k = L->length - 1;k >= i - 1;k--)
			L->data[k+1] = L->data[k];	
		//如果插入位置不在表的末尾，则从线性表的最后一个位置开始，所有元素向后移动一位
		//一直到插入位置的前一个元素		 
	}	
	L->length++;
	L->data[i-1] = e;
	//长度加一，为新插入的元素赋值 
}

//删除操作：删除 L 的第一个数据元素，并用 e返回其值
Status ListDelete(SqList *L,int i,ElemType *e){
	if(L->length == 0)
		return error;
	if(i < 1 || i > L->length)
		return error;
	*e = L->data[i-1];
	if(i < L->length){
		for(int k = i; k < L->length ;k++){
			L->data[k-1] = L->data[k]; 
		}
	}
	L->length--;
	return OK;
} 

//合并两个数组
Status ListUnion(SqList *La,SqList Lb){
	ElemType e;
	int La_len = La->length;
	int Lb_len = Lb.length;
	for(int i = 1 ; i <= Lb_len ; i++){
		GetElem(Lb,i,&e);
		if(!LocateElem(*La,e))
			ListInsert(La,La_len++,e);
	}
}

int main(){
    SqList L,Lb;
    ElemType e;
    Status r;
    r = initList(&L);
    int k;
    
	printf("初始化L后,L.length = %d\n",L.length);
	
	for(int i = 1; i <= 5 ; i++){
		r = ListInsert(&L,1,i);
	} 
	printf("在L的表头依次插入1-5后：L.data = "); 
	ListTraverse(L);
	
	printf("L.length = %d\n",L.length);
	if(ListEmpty(L))
	printf("L为空\n");
	else
	printf("L不为空\n");
	
	r = ClearList(&L); 
	printf("清空L后,L.length = %d\n",L.length);
	if(ListEmpty(L))
	printf("L为空\n");
	else
	printf("L不为空\n");
	
	for(int i = 1; i <= 10 ; i++){
		ListInsert(&L,i,i);
	}
	printf("在L的表头插入1-10后，L.data = ");
	ListTraverse(L);
	printf("L.length = %d\n",L.length);
	
    ListInsert(&L,1,0);
    printf("在L的表头插入0后：L.data= ");
    ListTraverse(L); 
    printf("L.length=%d\n",L.length);
	
	GetElem(L,5,&e);
	printf("第5个元素的值为:%d\n",e);
	
	for(int i = 3;i <= 4; i++){
		r = LocateElem(L,i);
		if(r == 0)
			printf("没有值为%d的元素\n",r);
		else
			printf("第%d个元素的值为:%d\n",r,i);
	}
	
	k = L.length;
	for(int i = k + 1 ; i >= k ;i--){
		r = ListDelete(&L,i,&e);
		if(r == error)
			printf("删除第%d个元素失败！\n",i);
		else
			printf("删除第%d个元素的值为%d\n",i,e); 
	}
	printf("依次输出L的元素: ");
	ListTraverse(L);
	
	r = 5;
	ListDelete(&L,r,&e);
	printf("删除第%d个元素的值为%d\n",r,e);
	
	printf("依次输出L的元素: ");
	ListTraverse(L);
	
	r = initList(&Lb);
	for(int i = 6;i <= 15; i++){
		r = ListInsert(&Lb,1,i);
	}
	ListUnion(&L,Lb);
	
	printf("依次输出合并了Lb的L的元素：");
	ListTraverse(L);
	
    return 0;
}

第一次发布博客，有问题还望大家指出。
（水平菜的一批，哈哈）

；原文链接：https://blog.csdn.net/m0_52532896/article/details/115791314
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！

上一篇：2021年第十二届蓝桥杯省赛B组第一场4.18（真题+部分题解） 下一篇：BUAA数据结构（2020级）简要声明和注意事项

随机推荐

【排序算法】之lowb三人组（冒泡、插入、

【排序算法】之lowb三人组冒泡、插入、选择什么是lowb三人组冒泡排序bubble so...
Vue中computed和watch有哪些区别

计算属性computed：支持缓存，只有依赖数据发生改变，才会重新进行计算不支持...
利用Typings为Visual Studio Code实现智

前言相信大家都知道在IDE中代码的智能提示几乎都是标配，虽然一些文本编辑器也...
ASP 常见对象总结(熟悉一下利用以后的开

ADO对象： Connection Command Recordset Record Stream ASP支持的对象很多，可...
成也数据库败也数据库 Oracle 如何云渡

一石激起千层浪，继中国区浩浩荡荡的大裁员告一段落之后，甲骨文并未因此收起手...
vbs:把一段文字中指定字符颜色变成红色的

vbs:把一段文字中指定字符颜色变成红色的正则 functionc(Tstr,Word) Dimre Setre...
正则表达式的应用

一、正则表达式概述二、正则表达式在VBScript中的应用三、正则表达式在VavaScr...
Android 微信文件传输助手文件夹

微信文件传输助手是微信电脑版与手机微信之间相互传输图片等文件的好工具，但很...
ES6的循环与可迭代对象示例详解

本文将研究 ES6 的 for ... of 循环。旧方法在过去，有两种方法可以遍历 javas...
歌词编辑器和选择歌曲可播放的网页

歌词编辑器歌词编辑器第一步：选择要播放的歌曲并播放第二步：填写全部的歌词...

手把手带你入门--线性表的顺序存储（大话数据结构）

C语言简单实现线性表的顺序存储

推荐图文

湖南大学计科专业分流个人建议

关于爬虫和反爬虫的简略方案分享

JSP实现计算器功能（网页版）

AIOps工具，要开源还是闭源？

ESP32学习笔记（2）——GPIO接口使用

java面试2021年高级（中、初）程序员算法、数据结构

随机推荐

【排序算法】之lowb三人组（冒泡、插入、

Vue中computed和watch有哪些区别

利用Typings为Visual Studio Code实现智

ASP 常见对象总结(熟悉一下利用以后的开

成也数据库败也数据库 Oracle 如何云渡

vbs:把一段文字中指定字符颜色变成红色的

正则表达式的应用

Android 微信文件传输助手文件夹

ES6的循环与可迭代对象示例详解

歌词编辑器和选择歌曲可播放的网页

关于我们