【数据结构初阶】顺序表

  • 开发
  • 23

hi，我们又见面啦！happy~~~

目录

前言：

一、线性表

二、顺序表

1、概念

2、与数组的区别

3、分类

4、动态顺序表的实现

SeqList.h 见下

SeqList.c 见下

test.c 见下

【注意】

—————————————   致回不去的童年   —————————————

正文开始——

前言：

顺序表是线性表的一种，所以在学习顺序表之前先了解下线性表。

一、线性表

线性表，是一类具有相同特性的数据结构的集合。常见的线性表：顺序表、链表、栈、队列、字符串... 

相同特性又表现在逻辑结构和物理结构上；逻辑结构：人为想象出来的数据的组织形式，一定是线性的。物理结构：数据在内存上的存储形式，不一定是线性的。

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

二、顺序表

1、概念

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

2、与数组的区别

顺序表的底层逻辑是数组，对数组的封装，实现了常用的增删查改等接口。

3、分类

分为 静态顺序表和 动态顺序表。
静态顺序表：使用定长数组存储元素。 
#define N 7 
typedef int SLDataType;  //方便后续修改数据类型
typedef struct SeqList{
    SLDataType a[N];     //定长数组
    int size;            //数组内有效数据的个数
}SL;  //为方便对结构体重新命名

缺陷：由于数组空间提前定好长度，空间给小不够用，给大了浪费。

动态顺序表：使用动态开辟的数组存储。所以相比之下，动态顺序表更有优势。

typedef int SLDataType;
typedef struct SeqList{
    SLDataType* arr;    //指向数组空间的指针 
    int size;           //有效数据个数
    int capacity;       //数组空间容量
}SL;

4、动态顺序表的实现

先创建3个文件

 SeqList.h 见下

#pragma once
#include<stdio.h>

//定义动态顺序表结构

typedef int SLDatatype;
typedef struct SeqList {
	SLDatatype* arr;
	int size;            //数组内有效数据的个数
	int capacity;        //数组空间容量
}SL; 
//typedef struct SeqList SL;

//初始化
void SLInit(SL* ps);

//销毁
void SLDestroy(SL* ps);

//判断空间是否充足
void SLCheck(SL* ps);

//尾插
void SLPushBack(SL* ps, SLDatatype x);

//头插
void SLPushFront(SL* ps, SLDatatype x);

//尾删
void SLPopBack(SL* ps);

//头删
void SLPopFront(SL* ps);

//在指定位置之前插入数据
void SLInsert(SL* ps,SLDatatype x,int pos);

//删除指定位置的数据
void SLErase(SL* ps, int pos);

//查找
int SLFind(SL* ps, SLDatatype x);

//打印
void SLPrint(SL* ps);

SeqList.c 见下

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include "SeqList.h"
#include<stdlib.h>
#include<assert.h>

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

//判断空间是否充足
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		//增容
		//若ps->capacity==0,给其赋初值，若不为0，直接增大2倍
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));
		if (tmp == NULL)
		{
			perror("realloc file!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//尾插
void SLPushBack(SL* ps, SLDatatype x)
{
	assert(ps);

	//判断空间是否充足
	SLCheckCapacity(ps);

	ps->arr[ps->size++] = x;
}

//头插
void SLPushFront(SL* ps, SLDatatype x)
{
	assert(ps);

	//判断空间是否充足
	SLCheckCapacity(ps);

	//数据整体后移一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	//下标为0的位置空出来，插入数据
	ps->arr[0] = x; 
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	//若顺序表为空，不能尾删
	assert(ps->size);
  //ps->arr[ps->size - 1] = -1;  多余了，假设原来size为4，这里直接size--，有效数据直接变为3个，
	ps->size--;                 //最后一个数据失效了，并且对之后插入数据无影响，这样操作就可以直接
	                            //达到尾删的效果
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//将数据整体前移一位
	for (int i=1;i<ps->size;i++)
	{
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;
}

//在指定位置之前插入数据（空间足够才能直接插入）
void SLInsert(SL* ps, SLDatatype x, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);

	SLCheckCapacity(ps);

	//将pos之后的数据从后往前 整体后移一位
	for (int i = ps->size;i>=pos+1;i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);  //注意这里pos不能等于ps->size

	//限制顺序表不能为空
	assert(ps->size);

	//将pos之后的数据从前往后，整体前移一位
	for (int i = pos+1;i<=ps->size-1;i++)
	{
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;
}

//查找
int SLFind(SL* ps, SLDatatype x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	//到此说明没有找到,返回一个无用的下标
	return -1;
}

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

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

test.c 见下

#define _CRT_SECURE_NO_WARNINGS 
#include"SeqList.h"

void SLtest01()
{
	SL s;
	SLInit(&s); 
	
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	
	SLPushFront(&s, 1);
	SLPushFront(&s, 2);
	SLPushFront(&s, 3);
	SLPushFront(&s, 4);
	SLPrint(&s);

	SLPopFront(&s);
	SLPrint(&s);
	SLPopFront(&s);
	SLPrint(&s);
	SLPopFront(&s);
	SLPrint(&s);
	SLPopFront(&s);

	SLInsert(&s, 100,2 );  
	SLPrint(&s);

	SLPopBack(&s);
	SLPrint(&s);

	SLErase(&s, 3);
	SLPrint(&s);

	int n = SLFind(&s, 1);
	if (n < 0)
	{
		printf("没找到\n");
	}
	else
		printf("找到了,%d\n",n);

	SLDestroy(&s);
}

int main()
{
	SLtest01();
	return 0;
}

【注意】

1、初始化，这里传的是地址&s，而不是传s，形参是实参数据的一份临时拷贝，形参和实参是两个互相独立的空间，形参的改变不影响实参，所以这里是传址，从而改变实参。

2、增容，数组大小成2倍增长，2-->4-->8-->16......

3、为什么不一次增加一个，这样就避免了空间浪费？因为增容的操作本身就有一定程序性能的损耗，频繁地增容会导致程序效率低下。

4、限制，assert(ps)，限制顺序表结构不为空（NULL空指针不能解引用），但不能限制顺序表内数组不为空；assert(pos >= 0 && pos < ps->size)，限制pos指向的为合理位置；assert(ps->size)，限制顺序表内数组不为空。

5、实现顺序表内功能函数时，一定要写一个测试一个，不然直接写完到最后的时候都是错误，那时候就知道我为啥要这样说了（嘻嘻）。

完——

左手右手_杨沛宜_高音质在线试听_左手右手歌词|歌曲下载_酷狗音乐酷狗音乐为您提供由杨沛宜演唱的高清音质无损左手右手mp3在线听,听左手右手,只来酷狗音乐!icon-default.png?t=N7T8https://t4.kugou.com/song.html?id=7vRqr83CPV2

—————————————   致回不去的童年   —————————————

期待我们下次的相遇——

再见——

阅读全部

相关推荐

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-19 14:52:03       49 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-19 14:52:03       53 阅读

  9. 在Django里面运行非项目文件

    2024-07-19 14:52:03       42 阅读

  19. Python语言-面向对象

    2024-07-19 14:52:03       53 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-19 14:52:03       49 阅读

热门阅读

  1. vue 预览pdf

    2024-07-19 14:52:03       14 阅读

  9. LeetCode //C - 233. Number of Digit One

    2024-07-19 14:52:03       21 阅读

  10. Redis详解

    2024-07-19 14:52:03       17 阅读

  15. 电平的概念及应用（电路节点在某一时刻的电压状态）（高电平、低电平）（电压是推动电荷通过导体的力，而电平是这种力的表达形式）

    2024-07-19 14:52:03       18 阅读

  16. PyTorch深度学习入门汇总

    2024-07-19 14:52:03       18 阅读

  18. 非结构化网格跨结点并行渲染

    2024-07-19 14:52:03       14 阅读

  22. 快速删除node_modules

    2024-07-19 14:52:03       15 阅读

  25. 小抄 20240714 我即世界

    2024-07-19 14:52:03       14 阅读

  26. 二叉树---找树左下角的值

    2024-07-19 14:52:03       15 阅读

  28. Android 一体机等root后的机器指令截屏

    2024-07-19 14:52:03       17 阅读