前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
腾讯云架构师技术同盟
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP腾讯云架构师技术同盟
返回腾讯云官网
社区首页 >专栏 >数据结构与算法（顺序表）

数据结构与算法（顺序表）

作者头像
风中的云彩
发布于 2024-11-07 21:51:37
发布于 2024-11-07 21:51:37
910
举报
文章被收录于专栏：C/C++的自学之路

无论你期望或者不期望，清晨依旧来临。

前言

这是我学习数据结构的第二份笔记，有关顺序表的知识。后期我会继续将数据结构知识的笔记补全。 上一期笔记有关复杂度，没看过的同学可以去看看：有关复杂度的笔记

线性表

1. 线性表是n个具有相同特性的数据元素的有限序列。 2. 线性表在逻辑上是线性结构，但是在物理结构上并不⼀定是连续的。 3. 线性表在物理上存储时，通常以顺序结构和链式结构的形式存储。 4. 线性表包括了顺序表、链表、栈、队列等这几种数据结构。

顺序表

顺序表的概念

1. 顺序表是用一段物理地址连续的存储单元，依次存储数据元素的线性结构。 2. 一般情况下采用数组存储，即顺序表是对数组的封装,实现了常用的增删改查等接口。 3. 顺序表的底层是数组，但是在数组基础上，添加了很多其他的功能。 4. 形象的理解，把数组比作成一辆黄包车，那么顺序表就是一辆专车，除了把你运输到目的地之外，还能提供其他黄包车没有的服务，比如端茶倒水，让你更加舒服。

顺序表的分类

静态顺序表

1. 使用定长数组存储元素。 2. 缺点：空间给少了不够用，给多了造成空间浪费。 3. 一般不用静态顺序表。 4. 结构体成员变量声明时不能初始化。（但可以宏定义）

代码语言：javascript
复制
#define N 7 //方便后期修改成其他数字大小,一键替换
typedef int SLDataType; //方便后期修改成其他类型,一键替换
typedef struct SeqList//定义一个顺序表结构体
{
	SLDataType a[N];//定长数组
	int size;//有效的数据个数
}SeqList;//把struct SeqList结构体重命名为SeqList
动态顺序表
代码语言：javascript
复制
typedef int SLDataType;//方便后期修改成其他类型,一键替换
typedef struct SeqList//定义一个顺序表结构体
{
	SLDataType* arr;//一个指针，也可以视为一个动态的数组
    int capacity;//顺序表的容量
	int size;//有效数据的个数
}SeqList;//把struct SeqList结构体重命名为SeqList
动态顺序表的初始化
传数值初始化
代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SeqList;
void InitSeqList(SeqList s)
{
	s.arr = NULL;
	s.size = s.capacity = 0;
}
int main()
{
	SeqList s;//创建一个顺序表s
	InitSeqList(s);//由于传值调用，所以函数调用完后，形参空间释放，实参无影响，故还是没有初始化
	return 0;
}
传地址初始化
代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SeqList;
void InitSeqList(SeqList* ps)//ps=&s
{
    assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
int main()
{
	SeqList s;//创建一个顺序表s
	InitSeqList(&s);//传址调用
	return 0;
}
//ps->相当于*(p.s)

1. 如果直接传值调用，那么顺序表变量s将无法初始化，因为形参初始化完后，就直接释放了内存空间，所以实参s并没有改变。 2. 如果传址调用的话，那么形参和实参共用一块地址，所以顺序表变量s就能实现初始化。 3. 我们在主函数里面创建顺序表变量s，然后需要先初始化，在进行其他操作。

动态顺序表的销毁
代码语言：javascript
复制
void DestroySeqList(SeqList* ps)
{
    assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	if (ps->arr != NULL)//如果arr不是空指针，则进入去释放arr的空间
	{
		free(ps->arr);//释放动态数组arr空间
	}
	ps->arr = NULL;//释放完空间后，指针仍然存在，但是指向任意值，要避免形成野指针，就用NULL赋值。
	ps->size = ps->capacity = 0;
}

1. 顺序表的销毁与初始化很像，多了一个操作：如果结构体变量s占用了内存，那么先释放内存，再将结构体变量s赋值为0。

动态顺序表尾插数据
代码语言：javascript
复制
void PushBackSeqList(SeqList* ps, SLDataType x)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	if (ps->size== ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)realloc(ps->arr, NEWcapacity  * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;//更新指针
		ps->capacity = NEWcapacity;//更新成员内容
	}
	ps->arr[ps->size++] = x;//尾部插入
}
动态顺序表头插数据
代码语言：javascript
复制
void PushHeadSeqList(SeqList* ps, SLDataType x)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)realloc(ps->arr, NEWcapacity * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;
		ps->capacity = NEWcapacity;
	}
	for (int i = ps->size; i > 0; i--)//把后size个数据整体向后移动一位
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;//在最前面插入新成员
	ps->size++;//有效数据增加一个
}
动态顺序表尾删数据
代码语言：javascript
复制
void DeleteBackSeqList(SeqList* ps)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	if(ps->size ==0 )//防止没有有效数据
    {
        exit(1);
    }                   
	ps->size--;//有效成员个数减一
}
动态顺序表头删数据
代码语言：javascript
复制
void DeleteHeadSeqList(SeqList* ps)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	if(ps->size == 0)//防止没有有效数据
    {
        exit(1);
    }    
	for (int i = 1; i < ps->size-1; i++)//除了第一个数组成员，其余的都往前移一位
	{
		ps->arr[i - 1] = ps->arr[i];//从第二个数据开始移动
	}
	ps->size--;//有效成员个数减一
}
动态顺序表任意位置增加数据
代码语言：javascript
复制
void FreePushSeqList(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	assert(pos > 0 && pos < ps->size);//任意位置要求有效
	if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)realloc(ps->arr, NEWcapacity * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;
		ps->capacity = NEWcapacity;
	}
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//在pos位置之后增加了一个数据
	}
	ps->arr[pos] = x;
	ps->size++;
}
动态顺序表任意位置删除数据
代码语言：javascript
复制
void FreeDelete(SeqList* ps, int pos)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	assert(pos > 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//删除了pos位置的数据
	}
	ps->size--;
}
动态顺序表的成员查找
代码语言：javascript
复制
int FindSeqList(SeqList* ps, SLDataType x)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			printf("找到了,下标是%d\n",i);
			return i;
		}
	}
	printf("抱歉,没有找到\n");
	return -1;//如果没有找到则返回一个无效的下标
}
动态顺序表的打印
代码语言：javascript
复制
void PrintSeqList(SeqList* ps)
{
    assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
}

综合示例的代码

代码语言：javascript
复制
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SeqList;

void InitSeqList(SeqList* ps)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

void PushBackSeqList(SeqList* ps, SLDataType x)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)realloc(ps->arr, NEWcapacity * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;//更新指针
		ps->capacity = NEWcapacity;//更新成员内容
	}
	ps->arr[ps->size++] = x;//尾部插入
}

void PrintSeqList(SeqList* ps)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
}

void PushHeadSeqList(SeqList* ps, SLDataType x)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)realloc(ps->arr, NEWcapacity * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;
		ps->capacity = NEWcapacity;
	}
	for (int i = ps->size; i > 0; i--)//把后size个数据整体向后移动一位
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;//在最前面插入新成员
	ps->size++;//有效数据增加一个
}

void DeleteBackSeqList(SeqList* ps)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	if (ps->size == 0)//防止没有有效数据
	{
		exit(1);
	}
	ps->size--;//有效成员个数减一
}

void DeleteHeadSeqList(SeqList* ps)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	if (ps->size == 0)//防止没有有效数据
	{
		exit(1);
	}
	for (int i = 1; i < ps->size - 1; i++)//除了第一个数组成员，其余的都往前移一位
	{
		ps->arr[i - 1] = ps->arr[i];//从第二个数据开始移动
	}
	ps->size--;//有效成员个数减一
}

void FreePushSeqList(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	assert(pos > 0 && pos < ps->size);//任意位置要求有效
	if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容
	{
		int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tem = (SLDataType*)realloc(ps->arr, NEWcapacity * sizeof(SLDataType));
		if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序
		{
			perror("relloc fail");//显示增容错误
			exit(1);//退出程序
		}
		ps->arr = tem;
		ps->capacity = NEWcapacity;
	}
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//在pos位置之后增加了一个数据
	}
	ps->arr[pos] = x;
	ps->size++;
}

void FreeDelete(SeqList* ps, int pos)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	assert(pos > 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//删除了pos位置的数据
	}
	ps->size--;
}

int FindSeqList(SeqList* ps, SLDataType x)
{
	assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			printf("找到了,下标是%d\n", i);
			return i;
		}
	}
	printf("抱歉,没有找到\n");
	return -1;//如果没有找到则返回一个无效的下标
}

void DestroySeqList(SeqList* ps)
{
    assert(ps);//要求ps!=NULL,否则直接断言报错。因为后面需要对ps进行解引用操作。
	if (ps->arr != NULL)//如果arr不是空指针，则进入去释放arr的空间
	{
		free(ps->arr);//释放空间
	}
	ps->arr = NULL;//释放完空间后，指针任然存在，但是指向任意值，要避免形成野指针，就用NULL赋值。
	ps->size = ps->capacity = 0;
}

int main()
{
	SeqList s;
	//添加操作
	return 0;
}

1. 这是一个包含了顺序表的各种功能函数的综合示例。 2. 当我们需要看看是否符合我们预期时候，可以直接用打印方式进行查看。

致谢

感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-11-07，如有侵权请联系 cloudcommunity@tencent.com 删除
ps
程序
数据
数据结构与算法
数组

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

ps
程序
数据
数据结构与算法
数组
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 前言
  • 线性表
  • 顺序表
    • 顺序表的概念
      • 顺序表的分类
        • 静态顺序表
        • 动态顺序表
    • 综合示例的代码
    • 致谢
    领券

    腾讯云开发者

    扫码关注腾讯云开发者

    扫码关注腾讯云开发者

    领取腾讯云代金券

    热门产品

    热门推荐

    更多推荐

    Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

    深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

    腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

    Copyright © 2013 - 2025 Tencent Cloud.

    All Rights Reserved. 腾讯云 版权所有

    登录 后参与评论