当前位置： 首页 > news >正文

【数据结构】万字深入浅出讲解顺序表（附原码 | 超详解）

news 来源：原创 2024/4/27 1:54:02

在这里插入图片描述

🚀write in front🚀
📝个人主页：认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏：C语言实现数据结构
💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🖊
✉️如果无聊的话，就来逛逛我的博客栈吧stack-frame.cn

文章目录

  • 前言
  • 一、线性表概念
    • 1.1线性表
  • 二、顺序表实现
    • 2.1概念及结构
    • 2.2 接口的布局
    • 2.3接口的实现
      • SeqList.h的代码
      • SeqList.c 的代码
  • 三、完整代码
  • 总结

前言

在这里插入图片描述
这几天看了数据结构的顺序表这一节，真的收获很大，第一次看没有动手敲代码就是感觉学了和没学一样，今天也是从新又看了一遍，并且边学边敲代码，终于算是非常理解顺序表这个东西了，今天就把我所学到的知识给大家分享一下。

提示：以下是本篇文章正文内容，下面案例可供参考

一、线性表概念

1.1线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。

在这里插入图片描述

二、顺序表实现

2.1概念及结构

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

顺序表一般可以分为：

  • 静态顺序表：使用定长数组存储。
  • 动态顺序表：使用动态开辟的数组存储.

以下是静态顺序表：

#pragma once//防止被重复的包含 

#define N 100
typedef int SQDataType;

typedef struct SeqList
{
	SQDataType a[N];
	SQDataType size; //有效数据 
}SL;
//增删查改等接口函数 

//对于结构体的定义typedef struct SeqList SL;

//静态顺序表
//问题：给少了不够用，给多了用不完浪费，不能灵活控制

由于静态顺序表无法伸缩变换数组，所以今天着重讲解动态的顺序表

动态顺序表的实现：

//#pragma once 
//#define N 10 对于动态线性表这个就没有用了 
typedef int SQDataType;

typedef struct SeqList
{
	SQDataType* a;
	int size;	  //有效数据的个数 
	int capacity; //容量 
}SL;

2.2 接口的布局

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大
了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态
的分配空间大小，所以下面我们实现动态顺序表。

我们需要的工程文件：

  • SeqList.h：用于存放函数声明、包含头文件、定义宏等等。
  • test.c：用于写程序整体执行逻辑等。
  • SeqList.c：用于写函数定义，写函数实现等。

2.3接口的实现

SeqList.h的代码

#include<string.h>
#include<stdio.h>//printf
#include<stdlib.h>//realloc 
#include<assert.h>//断言 

typedef int SQDataType; //方便修改数据 

typedef struct SeqList //重命名方便书写 
{
	SQDataType* a;
	int size;	  //有效数据的个数 
	int capacity; //容量 
}SL;


//初始化与销毁：
void SeqListInit(SL* ps);//初始化顺序表 
void SeqListCheckCapcity(SL* ps)//创建新空间---扩容
void SeqListDestory(SL* ps)//销毁空间 

//顺序表的插入操作---头插，尾插，任意插
void SeqListPushBack(SL* ps,SQDataType x);//顺序表尾插 o(1) 
void SeqListPushFront(SL* ps,SQDataType x);//顺序表头插  o(n)
void SeqListInsert(SL* ps,int pos,SQDataType x) //在顺序表指定下标位置插入数据 

//顺序表的删除操作---头删，尾删，任意删
void SeqListPopBack(SL* ps);//顺序表尾删 o(1)
void SeqListPopfront(SL* ps);//顺序表头删 o(n)
void SeqListErase(SL* ps,int pos) //顺序表任意下标删除 

//顺序表的查找、打印、寻找
int SeqListFind(SL* ps,SQDataType x) //顺序表查找下标 
int  SeqListModity(SL* ps,int pos,SQDataType x)//修改指定下标位置的数据 
void SeqListPrint(SL* ps)//打印顺序表元素

SeqList.c 的代码

这里就是实现上述的函数的代码啦~

  • 初始化顺序表
void SeqListInit(SL* ps)
{
	aseert(ps)//断言 
	//初始化
	ps->a=NULL;//设置为空 
	ps->size=0;//设置为0 
	ps->capacity=0;//设置为0 
}
  • 检查顺序表容量和扩容
    如果顺序表空间足够，那么不需要扩容，通过相关操作插入数据，如果空间不足或者根本没有空间，那么就得扩容。

当顺序表没有空间时，我们开辟四个空间(至少为1个空间)；当顺序表空间不足，我们将当前空间扩大为两倍

void SeqListCheckCapcity(SL* ps)
{
	assert(ps!= NULL);  //断言
	if(ps->size==ps->capacity)
	{
		int newcapacity=ps->capacity==0?4:ps->capacity*2;//如果是0就改为4，不是0就扩大二倍 
		SQDataType* tmp=(SQDataType*)realloc(ps->a,newcapacity*sizeof(SQDataType));
		if(tmp==NULL)
		{
			printf("realloc fail\n");//扩容失败 
			exit(-1);
		}
		else //扩容成功 
		{
			ps->a=tmp;//新的数组对吧 
			ps->capacity =newcapacity;//有效的容量 
		}
	}
}
  • 销毁顺序表
void SeqListDestory(SL* ps)//销毁 
{
	assert(ps != NULL);  //断言
	free(ps->a);//释放动态开辟的空间
	ps->a=NULL;//置空
	ps->capacity=0;//数据个数置0
	ps->size=0;//空间容量大小置0
}
  • 顺序表尾插
void SeqListPushBack(SL* ps,SQDataType x)//尾插
{
	//满了就要扩容 
//	if(ps->size==ps->capacity)
//	{
//		int newcapacity=ps->capacity==0?4:ps->capacity*2;
//		SQDataType* tmp=(SQDataType*)realloc(ps->a,newcapacity*2*sizeof(SQDataType));
//		if(tmp==NULL)
//		{
//			printf("realloc fail\n");
//			exit(-1);
//		}
//		else 
//		{
//			ps->a=tmp;//新的数组对吧 
//			ps->capacity = newcapacity;//有效的容量 
//		}
//	}	
	SeqListCheckCapcity(ps);//扩容函数 
	ps->a[ps->size]=x;//设置为要改的数x 
	ps->size++;//让数组长度增加 
}

测试：

void TestSeqList1()
{
	SL s1;
	SeqListInit(&s1); //初始化顺序表
	SeqListPushBack(&s1,1);
	SeqListPushBack(&s1,2);
	SeqListPushBack(&s1,3);
	SeqListPushBack(&s1,4);
	SeqListPushBack(&s1,5);
	SeqListPushBack(&s1,6);
	SeqListPushBack(&s1,7);
	SeqListPushBack(&s1,8);
	SeqListPushBack(&s1,9);
	SeqListPushBack(&s1,10);
	SeqListPushBack(&s1,11);
	SeqListPrint(&s1);//打印顺序表：下面实现
	//销毁顺序表：
	SeqListDestory(&s1);
}
int main()
{
	TestSeqList1();
	//TestSeqList2();
	return 0;
}

在这里插入图片描述

  • 顺序表尾删
    每次都在最后一个元素之后插入新的元素
void SeqListPopBack(SL* ps)//尾删 
{
	assert(ps->size>0);//断言 
	
	//ps->a[ps->size-1]=0;
	ps->size--;//数组减少 
}

void TestSeqList2()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushFront(&s1,1);
	SeqListPushFront(&s1,2);
	SeqListPushFront(&s1,3);
	SeqListPushFront(&s1,4);
	SeqListPushFront(&s1,5);
	SeqListPushFront(&s1,6);
	SeqListPopBack(&s1);
	SeqListPopBack(&s1);
	SeqListPopfront(&s1);
	SeqListPrint(&s1);
}

int main()
{
	//TestSeqList1();
	TestSeqList2();
	return 0;
}

在这里插入图片描述

  • 顺序表头插
    每次都在头结点之后插入新元素，头插法较为重要，当遇到链表的逆置操作时，可以使用头插法实现
void SeqListPushFront(SL* ps,SQDataType x)//头插 
{
	//1.初始条件
	//2.结束条件
	//3.迭代过程 
	
	//还是要考虑增容的情况
	SeqListCheckCapcity(ps);//扩容 
	int end=ps->size-1;//找到end指针 
	while(end>=0) //循环右移 
	{
		ps->a[end+1]=ps->a[end];
		--end;
	}
	ps->a[0]=x;//插入 
	ps->size++;//数组加大 
}

在这里插入图片描述
实现：

void TestSeqList2()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushFront(&s1,1);
	SeqListPushFront(&s1,2);
	SeqListPushFront(&s1,3);
	SeqListPushFront(&s1,4);
	SeqListPushFront(&s1,5);
	SeqListPushFront(&s1,6);
	SeqListPopBack(&s1);
	SeqListPopBack(&s1);
	SeqListPopfront(&s1);
	SeqListPrint(&s1);
}

int main()
{
	//TestSeqList1();
	TestSeqList2();
	return 0;
}

在这里插入图片描述

  • 顺序表头删
void SeqListPopfront(SL* ps)//头删
{
	assert(ps->size>0);
	
	int start=1;
	while(start<ps->size)
	{
		ps->a[start-1]=ps->a[start];
		++start;
	}
	ps->size--;
}

在这里插入图片描述

  • 打印顺序表
void SeqListPrint(SL* ps)
{
	for(int i=0;i<ps->size;++i)
	{
		printf("%d ",ps->a[i]);
	}
	printf("\n");
}
  • 顺序表指定下标位置插入数据

插入操作，在表L中的第i个位置上插入指定元素

想要在第i个位置上插入元素，那么就要找到第i − 1 个结点，然后将新结点插入其后面

void SeqListInsert(SL* ps,int pos,SQDataType x) //任意插入 
{
	assert(pos<ps->size);
	SeqListCheckCapcity(ps);
	
	int end=ps->size-1;
	while(end>=pos)
	{
		ps->a[end+1]=ps->a[end];
		--end;
	}
	
	ps->a[pos]=x;
	ps->size++;
}
  • 顺序表任意下标删除

但是，使用这个算法有个问题，如果p是最后一个结点，那么当程序执行到p->data = p->next->data这一句时，会出现空指针的错误，所以只能从表头开始依次寻找p的前驱

void SeqListErase(SL* ps,int pos) //任意删除 
{
	assert(pos<ps->size); 
	
	int start=pos+1;
	while(start<ps->size)
	{
		ps->a[start-1]=ps->a[start];
		++start;
	}
	ps->size--;
}
  • 顺序表查找下标
    按位查找操作。获取表L中第i个位置的元素的值
int SeqListFind(SL* ps,SQDataType x) //查找 
{
	for(int i=0;i<ps->size;++i)
	{
		if(ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
  • 改指定下标位置的数据
int  SeqListModity(SL* ps,int pos,SQDataType x)//修改位置的值 
{
	assert(pos<ps->size);
	ps->a[pos]=x;
}

三、完整代码

SeqList.h

#include<string.h>
#include<stdio.h>//printf
#include<stdlib.h>//realloc 
#include<assert.h>//断言 

typedef int SQDataType; //方便修改数据 

typedef struct SeqList //重命名方便书写 
{
	SQDataType* a;
	int size;	  //有效数据的个数 
	int capacity; //容量 
}SL;


void SeqListInit(SL* ps);//初始化顺序表 
void SeqListCheckCapcity(SL* ps)//创建新空间---扩容
void SeqListDestory(SL* ps)//销毁空间 


void SeqListPushBack(SL* ps,SQDataType x);//顺序表尾插 o(1) 
void SeqListPushFront(SL* ps,SQDataType x);//顺序表头插  o(n)
void SeqListInsert(SL* ps,int pos,SQDataType x) //在顺序表指定下标位置插入数据 

void SeqListPopBack(SL* ps);//顺序表尾删 o(1)
void SeqListPopfront(SL* ps);//顺序表头删 o(n)
void SeqListErase(SL* ps,int pos) //顺序表任意下标删除 

int SeqListFind(SL* ps,SQDataType x) //顺序表查找下标 
int  SeqListModity(SL* ps,int pos,SQDataType x)//修改指定下标位置的数据 
void SeqListPrint(SL* ps)//打印顺序表元素

SeqList.c：


//void SeqListInit(SL* ps);
//{
//	//初始化
//	memset(s1.a,0,sizeof(SQDataType)*N);
//	s1.size=0;
//}
//
//void SeqListPushBack(SL* ps,SQDataType x);//尾插
//{
//	if(ps->size>=N)
//	{
//		printf("SeqList is Full\n");
//		return;
//	}
//	
//	ps->a[ps->size]=x;
//	ps->size++;
//}
//以上就是静态 
//------------------------------------------------
//下面实现动态

 
void SeqListInit(SL* ps);
{
	//初始化
	ps->a=NULL;
	ps->size=0;
	ps->capacity=0;//开始如果是一个0的话，那么扩容就会失败 
}

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

void SeqListPushBack(SL* ps,SQDataType x);//尾插
{
	//满了就要扩容 
//	if(ps->size==ps->capacity)
//	{
//		int newcapacity=ps->capacity==0?4:ps->capacity*2;
		SQDataType* tmp=(SQDataType*)realloc(ps->a,ps->capacity*2*sizeof(SQDataType));
//		SQDataType* tmp=(SQDataType*)realloc(ps->a,ps->newcapacity*2*sizeof(SQDataType));
//		if(tmp==NULL)
//		{
//			printf("realloc fail\n");
//			exit(-1);
//		}
//		else 
//		{
//			ps->a=tmp;//新的数组对吧 
//			ps->capacity =newcapacity;//有效的容量 
//		}
//	}	
	SeqListCheckCapcity(&ps);
	ps->a[ps->size]=x;
	ps->size++;
}

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



void SeqListCheckCapcity(SL* ps)
{
	if(ps->size==ps->capacity)
	{
		int newcapacity=ps->capacity==0?4:ps->capacity*2;
		SQDataType* tmp=(SQDataType*)realloc(ps->a,newcapacity*sizeof(SQDataType));
		if(tmo==NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else 
		{
			ps->a=tmp;//新的数组对吧 
			ps->capacity =newcapacity;//有效的容量 
		}
	}
}

void SeqListPushFront(SL* ps,SQDataType x);//头插 
{
	//1.初始条件
	//2.结束条件
	//3.迭代过程 
	
	//还是要考虑增容的情况
	SeqListCheckCapcity(&ps);
	int end=ps->size-1;
	while(end>=0)
	{
		ps->a[end+1]=ps->a[end];
		--end;
	}
	ps->a[0]=x;
	ps->size++;
}

void SeqListPopBack(SL* ps)//尾删 
{
	assert(ps->size>0)
	
	//ps->a[ps->size-1]=0;
	ps->size--;
}

void SeqListPopfront(SL* ps)//头删
{
	assert(ps->size>0)
	
	int start=1;
	while(start<ps->size)
	{
		ps->a[start-1]=ps->a[start];
		++start;
	}
	ps->size--;
}

void SeqListInsert(SL* ps,int pos,SQDataType x) //任意插入 
{
	assert(pos<ps->size);
	SeqListCheckCapcity(&ps);
	
	int end=ps->size-1;
	while(end>=pos)
	{
		ps->a[end+1]=ps->a[end];
		--end;
	}
	
	ps->a[pos]=x;
	ps->size++;
}

void SeqListErase(SL* ps,int pos) //任意删除 
{
	assert(pos<ps->size)
	
	int start=pos+1;
	while(start<ps->size)
	{
		ps->a[start-1]=ps->a[start];
		++start;
	}
	ps->size--;
}

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

int  SeqListModity(SL* ps,int pos,SQDataType x)//修改位置的值 
{
	assert(pos<ps->size);
	ps->a[pos]=x;
}

test.c

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

//#pragma once 
//#define N 10 对于动态线性表这个就没有用了 
typedef int SQDataType;

typedef struct SeqList
{
	SQDataType* a;
	int size;	  //有效数据的个数 
	int capacity; //容量 
}SL;

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

void SeqListCheckCapcity(SL* ps)
{
	assert(ps!= NULL);  //断言
	if(ps->size==ps->capacity)
	{
		int newcapacity=ps->capacity==0?4:ps->capacity*2;//如果是0就改为4，不是0就扩大二倍 
		SQDataType* tmp=(SQDataType*)realloc(ps->a,newcapacity*sizeof(SQDataType));
		if(tmp==NULL)
		{
			printf("realloc fail\n");//扩容失败 
			exit(-1);
		}
		else //扩容成功 
		{
			ps->a=tmp;//新的数组对吧 
			ps->capacity =newcapacity;//有效的容量 
		}
	}
}

void SeqListPushBack(SL* ps,SQDataType x)//尾插
{
	//满了就要扩容 
//	if(ps->size==ps->capacity)
//	{
//		int newcapacity=ps->capacity==0?4:ps->capacity*2;
//		SQDataType* tmp=(SQDataType*)realloc(ps->a,newcapacity*2*sizeof(SQDataType));
//		if(tmp==NULL)
//		{
//			printf("realloc fail\n");
//			exit(-1);
//		}
//		else 
//		{
//			ps->a=tmp;//新的数组对吧 
//			ps->capacity = newcapacity;//有效的容量 
//		}
//	}	
	SeqListCheckCapcity(ps);//扩容函数 
	ps->a[ps->size]=x;//设置为要改的数x 
	ps->size++;//让数组长度增加 
}

void SeqListPushFront(SL* ps,SQDataType x)//头插 
{
	//1.初始条件
	//2.结束条件
	//3.迭代过程 
	
	//还是要考虑增容的情况
	SeqListCheckCapcity(ps);//扩容 
	int end=ps->size-1;//找到end指针 
	while(end>=0) //循环右移 
	{
		ps->a[end+1]=ps->a[end];
		--end;
	}
	ps->a[0]=x;//插入 
	ps->size++;//数组加大 
}

void SeqListPopBack(SL* ps)//尾删 
{
	assert(ps->size>0);//断言 
	
	//ps->a[ps->size-1]=0;
	ps->size--;//数组减少 
}

void SeqListPopfront(SL* ps)//头删
{
	assert(ps->size>0);
	
	int start=1;
	while(start<ps->size)
	{
		ps->a[start-1]=ps->a[start];
		++start;
	}
	ps->size--;
}

void SeqListInsert(SL* ps,int pos,SQDataType x) //任意插入 
{
	assert(pos<ps->size);
	SeqListCheckCapcity(ps);
	
	int end=ps->size-1;
	while(end>=pos)
	{
		ps->a[end+1]=ps->a[end];
		--end;
	}
	
	ps->a[pos]=x;
	ps->size++;
}

void SeqListErase(SL* ps,int pos) //任意删除 
{
	assert(pos<ps->size); 
	
	int start=pos+1;
	while(start<ps->size)
	{
		ps->a[start-1]=ps->a[start];
		++start;
	}
	ps->size--;
}

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

int  SeqListModity(SL* ps,int pos,SQDataType x)//修改位置的值 
{
	assert(pos<ps->size);
	ps->a[pos]=x;
}

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


void TestSeqList1()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1,1);
	SeqListPushBack(&s1,2);
	SeqListPushBack(&s1,3);
	SeqListPushBack(&s1,4);
	SeqListPushBack(&s1,5);
	SeqListPushBack(&s1,6);
	SeqListPushBack(&s1,7);
	SeqListPushBack(&s1,8);
	SeqListPushBack(&s1,9);
	SeqListPushBack(&s1,10);
	SeqListPushBack(&s1,11);
	SeqListPrint(&s1);
}

void TestSeqList2()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushFront(&s1,1);
	SeqListPushFront(&s1,2);
	SeqListPushFront(&s1,3);
	SeqListPushFront(&s1,4);
	SeqListPushFront(&s1,5);
	SeqListPushFront(&s1,6);
	SeqListPopBack(&s1);
	SeqListPopBack(&s1);
	SeqListPopfront(&s1);
	SeqListPrint(&s1);
}

int main()
{
	//TestSeqList1();
	TestSeqList2();
	return 0;
}

总结

  今天学习了线性表的知识，初次写数据结构的知识，给我的感觉就是，学三遍不如手敲代码一遍来的实在，所以数据结构的学习我将多画图，多敲代码来学习，希望大家吸取经验和我一起学习数据结构，为后面打比赛刷题打下坚实基础。

  我是夏目浅石，希望和你一起学习进步，刷题无数！！！希望各位大佬能一键三连支持一下博主，hhhh~我们下期见喽
在这里插入图片描述
如果无聊的话，就来逛逛我的博客栈吧stack-frame.cn

✨ 原创不易，还希望各位大佬支持一下 \textcolor{blue}{原创不易，还希望各位大佬支持一下} 原创不易，还希望各位大佬支持一下

👍 点赞，你的认可是我创作的动力！ \textcolor{9c81c1}{点赞，你的认可是我创作的动力！} 点赞，你的认可是我创作的动力！

⭐️ 收藏，你的青睐是我努力的方向！ \textcolor{ed7976}{收藏，你的青睐是我努力的方向！} 收藏，你的青睐是我努力的方向！

✏️ 评论，你的意见是我进步的财富！ \textcolor{98c091}{评论，你的意见是我进步的财富！} 评论，你的意见是我进步的财富！

相关文章：

  • Allegro如何设计线圈操作指导
  • c程序gcc编译常见报错及解决方法整理
  • SSH (Secure Shell)
  • 《蓝桥杯》30天拿下Python算法设计与分析【Day 11】
  • PyTorch初学者指南：数据预处理
  • Ribbon策略改变实现步骤（基于Eureka服务注册中心）
  • LeetCode和牛客网二叉树经典例题合集
  • C语言中的数组初始化常见方法
  • DT-6_TTL-WiFi透传模块介绍
  • 2023年网络安全比赛--JavaScript安全绕过中职组（超详细）
  • 最大油田（Python）
  • I.MX6ULL裸机开发笔记2：镜像文件
  • 基于EasyExcel实现百万级数据导入导出
  • C++初阶--模板
  • [Android]Bitmap Drawable
  • 【docker概念和实践 3】 注册阿里云账号、应用阿里云数据源
  • 手把手教你学51单片机-点亮你的LED
  • 华为数字化转型之道 平台篇 第十三章 变革治理体系
  • 23种设计模式（十）——原型模式【对象创建】
  • 数据挖掘之超参调优技巧