首页 > 其他分享 >顺序表的实现

顺序表的实现

时间:2024-07-30 22:56:31浏览次数:12  
标签:ps 顺序 实现 void sl int SL size

一、顺序表的定义

        顺序表是一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数据存储。在数组上完成数据的增删改查。

二、顺序表的分类

1、静态顺序表

#define N 1000
typedef int SLDataType; 

//静态顺序表 
typedef struct SeqList{
	SLDataType a[N];//表示数组的大小 
	int size;//表示数组中存储了多少数据 
}SL;

//接口函数 
void SeqListTnit(SL* ps,SLDataType x);//初始化 
void SeqListPushBack(SL* ps,SLDataType x);//尾插 
void SeqListPopBack(SL* ps);//尾删 
void SeqListPushFront(SL* ps,SLDataType x);//头插 
void SeqListPopFront(SL* ps);//头删 

2、动态顺序表

typedef int SLDataType; 

//动态顺序表 
typedef struct SeqList{
	SLDataType* a;//表示数组的大小 
	int size;//表示数组中存储了多少数据
	int capacity;//数组实际能存数据的空间容量多大 
}SL;

//接口函数 
void SeqListTnit(SL* ps,SLDataType x);//初始化 
void SeqListPushBack(SL* ps,SLDataType x);//尾插 
void SeqListPopBack(SL* ps);//尾删 
void SeqListPushFront(SL* ps,SLDataType x);//头插 
void SeqListPopFront(SL* ps);//头删 

三、顺序表的实现(动态顺序表)

mian.c

#include <stdio.h>
#include "SeqList.h"

void TestSeqList1()
{
	SL sl;
	//初始化测试 
	SeqListInit(&sl);
	
	//尾插测试打印 
	SeqListPushBack(&sl,1);
	SeqListPushBack(&sl,2);
	SeqListPushBack(&sl,3);
	SeqListPushBack(&sl,4);
	SeqListPushBack(&sl,5);
	SeqListPrint(&sl);
	
	//尾删测试打印 
	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPrint(&sl);
	
	
	//销毁内存 
	SeqListDestory(&sl);
}


void TestSeqList2()
{
	SL sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl,1);
	SeqListPushBack(&sl,2);
	SeqListPushBack(&sl,3);
	SeqListPushBack(&sl,4);
	SeqListPushBack(&sl,5);
	SeqListPrint(&sl);
	
	//头插测试打印 
	SeqListPushFront(&sl,10);
	SeqListPushFront(&sl,20);
	SeqListPushFront(&sl,30);
	SeqListPushFront(&sl,40);
	SeqListPrint(&sl);
	
	//头删测试打印 
	SeqListPopFront(&sl);
	SeqListPopFront(&sl); 
	SeqListPrint(&sl);
	
	//销毁内存 
	SeqListDestory(&sl);
}


void TestSeqList3()
{
	SL sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl,1);
	SeqListPushBack(&sl,2);
	SeqListPushBack(&sl,3);
	SeqListPushBack(&sl,4);
	SeqListPushBack(&sl,5);
	SeqListPrint(&sl);
	
	//指定位置插入 
	SeqListInsert(&sl,0,0);//头插 
	SeqListInsert(&sl,6,6);//尾插 
	SeqListPrint(&sl);
	
	//查找不存在插入 
	int pos = SeqListFind(&sl,4);
	if(pos == -1)
	{
		SeqListInsert(&sl,pos,4);	
	}
	SeqListPrint(&sl);
	
	//查找找到删除 
	int pos1 = SeqListFind(&sl,4);
	if(pos1 != -1)
	{
		SeqListErase(&sl,pos1);	
	}
	SeqListPrint(&sl);
	
	
	
	//指定位置删除 
	SeqListErase(&sl,0);//头删 
	SeqListErase(&sl,4);//尾删 
	
	SeqListPrint(&sl);
	
	//销毁内存 
	SeqListDestory(&sl);
}

int main(int argc, char *argv[]) 
{
	//TestSeqList1();
	//TestSeqList2();
	TestSeqList3();
	return 0;
}

SeqList.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "SeqList.h"


///*************测试打印************/ 
void SeqListPrint(SL* ps)
{
	int i;
	for(i = 0;i < ps->size;i++)
	{
		printf("%d ",ps->a[i]);
	}
	printf("\n");
}


/*************初始化**************/
void SeqListInit(SL* ps) 
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}


/*************内存销毁************/ 
void SeqListDestory(SL*ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
} 


/*************检查扩容************/ 
void SeqListCheckCapacity(SL* ps)
{
	if(ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity  == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a,newcapacity*sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("relloc fail\n");
			exit(-1);
		}
		
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}


/*************尾插****************/
/*
情况一:整个顺序表为空,没有空间
情况二:空间不够,扩容(扩大二倍) 
情况三:空间足够,直接插入数据即可
*/ 
void SeqListPushBack(SL* ps,SLDataType x)
{
	//如果没有空间或空间不足,那么我们就扩容 
	SeqListCheckCapacity(ps); 
	
	ps->a[ps->size] = x;
	ps->size++;
	
	//SeqListInsert(ps,ps->size, x)		
}


/*************尾删****************/
void SeqListPopBack(SL* ps)
{
	/*防止越界访问方法一: 
	if(ps->size > 0)
	{
		//ps->a[ps->size - 1] = 0;无意义,有可能那个地方本身存0 
		ps->size--; //逻辑性删除,直接访问不到那个数据,后续如果再尾插的话,原数上重新赋值修改即可
	} 
	*/
	
	//方法二: 
	assert(ps->size > 0);//断言,条件为真没事,条件为假,终止程序 
	ps->size--;
	
	//方法三:SeqListErase(ps,ps->size-1) 
}


/*************头插****************/
void SeqListPushFront(SL* ps,SLDataType x)
{
	//扩容 
	SeqListCheckCapacity(ps);
	
	//挪动数据 
	int end = ps->size - 1;
	while(end >= 0)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
	
	//SeqListInsert(ps,0,x);
} 


/*************头删****************/
void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);
	
	//挪动数据 
	int begin = 1;
	while(begin < ps->size)
	{
		ps->a[begin-1] = ps->a[begin];
		begin++;
	}
	ps->size--;
	
	//SeqListErase(ps,0);
}


/*************查找****************/
int SeqListFind(SL* ps,SLDataType x)
{
	int i;
	for(i = 0;i < ps->size;i ++)
	{
		if(ps->a[i] == x)
		{
			return i; 
		}	
	}
	
	return -1;
}


/*************在指定pos(下标)位置插入x****************/
void SeqListInsert(SL* ps,int pos,SLDataType x)
{
	if(pos > ps->size || pos < 0)
	{
		printf("pos invaild\n");
		return; 	
	}
	
	/*
	assert(pos >= 0 && pos <= ps->size);
	*/
	
	SeqListCheckCapacity(ps);
	
	//挪动数据 
	int end = ps->size - 1;
	while(end >= pos)
	{
		ps->a[end+1] = ps->a[end];
		end--;	
	}
	ps->a[pos] = x;
	ps->size++; 
}


/*************删除指定pos(下标)位置的数据****************/
void SeqListErase(SL* ps,int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while(begin < ps->size)
	{
		ps->a[begin-1] = ps->a[begin];
		begin++;
	}
	ps->size--;
			
}

SeqList.h

typedef int SLDataType; 

//动态顺序表 
typedef struct SeqList{
	SLDataType* a;//表示数组的大小(指向动态开辟的数组) 
	int size;//表示数组中存储了多少数据(有效数据个数) 
	int capacity;//数组实际能存数据的空间容量多大(容量空间大小) 
}SL;

//打印调试 
void SeqListPrint(SL* ps);

//接口函数 
void SeqListInit(SL* ps);//初始化 
void SeqListDestory(SL* ps);//内存销毁 

void SeqListCheckCapacity(SL* ps);//检查扩容 
void SeqListPushBack(SL* ps,SLDataType x);//尾插 
void SeqListPopBack(SL* ps);//尾删 
void SeqListPushFront(SL* ps,SLDataType x);//头插 
void SeqListPopFront(SL* ps);//头删 

int SeqListFind(SL* ps,SLDataType x);//查找位置,找到返回x位置下标,没有找到返回-1 

void SeqListInsert(SL* ps,int pos,SLDataType x);//在指定pos位置插入x 
void SeqListErase(SL* ps,int pos);//删除指定pos位置的数据 

 四、运行结果

五、示例(菜单)

main.c

#include <stdio.h>
#include "SeqList.h"

void menu()
{
	printf("**********************\n");
	printf("请选择你的操作:>\n");
	printf("1、头插  2、尾插\n"); 
	printf("3、头删  4、尾删\n"); 
	printf("5、打印  -1、退出\n"); 
	printf("**********************\n"); 
}

void MenuTest()
{
	
	SL sl;
	SeqListInit(&sl);
	int input = 0;
	int x;
	
	while(input != -1)
	{
		menu();
		scanf("%d",&input);
		switch(input)
		{
			case 1:
				printf("请输入你要头插的数据,以-1结束:\n");
				scanf("%d",&x);
				while(x != -1)
				{
					SeqListPushFront(&sl,x);
					scanf("%d",&x);
				}
				break;
			case 2: 
				SeqListPopFront(&sl);
				break;
			case 3:
				printf("请输入你要尾插的数据,以-1结束:\n");
				scanf("%d",&x);
				while(x != -1)
				{
					SeqListPushBack(&sl,x);
					scanf("%d",&x);
				}
				break;
			case 4:
				SeqListPopBack(&sl);
				break;
			case 5: 
				SeqListPrint(&sl);
				break;
			default:
				printf("输入错误\n");
				break; 
		}	
	}
	 
	SeqListDestory(&sl);	
}

int main(int argc, char *argv[])
{
	MenuTest();
	return 0;
}

 

标签:ps,顺序,实现,void,sl,int,SL,size
From: https://blog.csdn.net/qq_63057731/article/details/140747338

相关文章

  • 基于springboot学生毕业离校系统lw(毕设+实现+源码+数据库)
    摘 要一年一度的毕业季的到来,方方面面都普及使得学生毕业离校系统的开发成为必需。学生毕业离校系统主要是借助计算机,通过对学生、教师、离校信息、费用结算、LW审核等信息进行管理。为减少管理员的工作,同时也方便广大学生对个人所需毕业离校的及时查询以及管理。学生毕......
  • 基于springboot音乐网站与分享平台(毕设+实现+源码+数据库)
                           摘要本LW主要论述了如何使用JAVA语言开发一个音乐网站与分享平台,本系统将严格按照软件开发流程进行各个阶段的工作,采用B/S架构,面向对象编程思想进行项目开发。在引言中,作者将论述音乐网站与分享平台......
  • 基于Matlab的车牌识别系统设计与实现
    基于Matlab的车牌识别系统设计与实现摘要随着智能交通系统的不断演进,车牌识别技术已成为提升交通管理效率与准确性的关键。本文深入探讨了基于Matlab平台的车牌识别系统设计与实现,该系统通过精细的图像预处理、高效的车牌定位算法、精准的字符分割与识别技术,显著提升了车牌识......
  • 基于Matlab的疲劳检测系统设计与实现
    基于Matlab的疲劳检测系统设计与实现一、引言1.阐述疲劳驾驶的危害性及对交通安全的影响。2.强调疲劳检测系统的重要性和现实意义。3.介绍本文的主题:基于Matlab的疲劳检测系统设计与实现。二、系统设计1.系统总体架构设计t- 输入模块:负责捕捉驾驶员的面部图像。t......
  • SQL执行顺序和逻辑
    SQL执行顺序和逻辑MySQL的执行顺序:  (9)SELECT  (6)SUM(聚合函数)  (10)DISTINCT<select_list>  (1)FROM<left_table>  (3)<join_type>JOIN<right_table>  (2)ON<join_condition>  (4)WHERE<where_condition>  (5)GROUP......
  • 如何自动实现本地AD中禁用的用户从地址列表中隐藏掉?
    我的博客园:https://www.cnblogs.com/CQman/如何自动实现本地AD中禁用的用户从地址列表中隐藏掉? 需求信息: 用户本地AD用户通过ADConnect同步到O365,用户想实现在本地已做同步的OU中禁用某一用户后,其可以自动实现把该用户从地址列表中隐藏掉。 用户的ADConnect同步工具装在......
  • 用idea实现第一个springBoot
    hello@Controller@RequestMapping("/hello")publicclassHelloController{@GetMapping("/hello")@ResponseBodypublicStringhello(){return"hello";}} 更改端口号#更改端口号server.port=8081banner.tx......
  • 静态顺序表
    顺序表顺序表和链表都是线性表的一种,此处介绍顺序表数据的存储结构有分为逻辑存储结构和物理存储结构。顺序表和链表(之后的文章会详解)实际上都是线性表,是因为他们的逻辑存储关系都是线性的,只是因为在计算机内存中存储的方式(物理存储结构)不同。两种物理存储结构各有......
  • 门控循环单元(GRU)预测模型及其Python和MATLAB实现
    ##一、背景循环神经网络(RNN)是处理序列数据的一类神经网络,尤其适用于时间序列预测、自然语言处理等领域。然而,传统的RNN在长序列数据的训练中面临梯度消失和爆炸的问题,导致模型对长期依赖的学习能力不足。为了解决这一问题,研究人员提出了多种改进的RNN结构,其中包括长短期记忆......
  • 长短期记忆网络(LSTM)预测模型及其Python和MATLAB实现
    ##LSTM预测模型背景长短期记忆网络(LongShort-TermMemory,LSTM)是一种特殊的递归神经网络(RNN),于1997年首次由SeppHochreiter和JürgenSchmidhuber提出。LSTM主要用于处理和预测序列数据中的时间依赖关系,能够有效地解决传统RNN在处理长序列时遇到的梯度消失和梯度爆炸问题。因......