数据结构“入门”—手撕顺序表

目录

一:顺序表基本概念

二:顺序表的实现

1 创建顺序表

 2 初始化顺序表

3 检查是否需要扩容

4 打印顺序表

5 销毁顺序表

 三:顺序表重要功能—“增 删 查 改”

1:增加数据

1-1：尾插

1-2：头插

 1-3：指定下标插入

2:删除数据

2-1：尾删

2-2：头删

2-3：指定下标删除

 3:查找数据

 4:修改数据

4:源码

5:下篇预告

一:顺序表基本概念

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

类别: 

1.静态顺序表：使用定长数组存储元素。

 2. 动态顺序表：使用动态开辟的数组存储。

❗：顺序表要求存储的数据是从下标0开始，依次连续存储，中间不能用空位。

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

二:顺序表的实现

⭐：顺序表代码的实现将放在三个文件中，分别是SeqList.h、SeqList.c、Test.c。分别用于声明，定义，测试。

1 创建顺序表

  • SeqList.h文件：
  • //创建顺序表

typedef int SLDateType; //确保以后想存其它数据类型的时候方便改动，本文以存放整型数据为例

typedef struct SeqList
{
	SLDateType* a; //动态开辟数组
	int size;      //存储顺序表中有效数据个数
	int capacity;  //记录开辟空间的容量
}SeqList;

 2 初始化顺序表

  • SeqList.h文件：
  • //初始化顺序表
void SeqListInit(SeqList* psl);

  • SeqList.c文件：

  • //初始化顺序表
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

3 检查是否需要扩容

  • SeqList.h文件：
  • //检测是否需要扩容
void SeqListCheckCapacity(SeqList* psl);
  • SeqList.c文件：
  • //检测是否需要扩容
void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);
	//如果满了，就要扩容
	if (psl->size == psl->capacity)
	{
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; //防止原始capacity的容量本身为0，导致后续扩容仍为0
		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
        //如果psl->a为空指针，此时realloc相当于malloc
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = (int)newCapacity;
		}
	}
}

4 打印顺序表

  • SeqList.h文件：
  • //打印顺序表
void SeqListPrint(SeqList* psl);
  • SeqList.c文件：
  • //打印顺序表
void SeqListPrint(SeqList* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ",psl->a[i]);
	}
	printf("\n");
}

5 销毁顺序表

  • SeqList.h文件：
  • //销毁顺序表
void SeqListDestroy(SeqList* psl);
  • SeqList.c文件：
  • //销毁顺序表
void SeqListDestroy(SeqList* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->capacity = psl->size = 0;
}

 三:顺序表重要功能—“增 删 查 改”

1:增加数据

1-1：尾插

思路：在我们进行插入数据之前我们首先要判断一下自己realloc的空间是否已满，如果满我们需要扩容，未满我们就可以在数组下标为psl->size处插入数据。

  • SeqList.h文件：
  • //尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
  • SeqList.c文件：
  • //尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl); //检测容量
	psl->a[psl->size] = x;
	psl->size++;
}
  • Test.c文件：
  • void SeqListTest1()
{
		SeqList s;
		SeqListInit(&s); //注意加上&，因为形参的改变不影响实参
		//尾插5个数字
		SeqListPushBack(&s, 1);
		SeqListPushBack(&s, 2);
		SeqListPushBack(&s, 3);
		SeqListPushBack(&s, 4);
		SeqListPushBack(&s, 5);
		SeqListprint(&s); //打印
}

1-2：头插

思路：头插就是在下标为0的位置插入一个元素，同时把原来的元素往后挪，把第一个位置空出来，同时也要确保空间足够，不够进行扩容。

  • SeqList.h文件：
  • //头插
void SeqListPushFront(SeqList* psl, SLDataType x);
  • SeqList.c文件：
  • //头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl); //检测容量
	int end = psl->size;
	while (end > 0)
	{
		psl->a[end] = psl->a[end-1];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}
  • Test.c文件：
  • void SeqListTest2()
{
	SeqList s;
	SeqListInit(&s); //注意加上&，因为形参的改变不影响实参
	//先尾插4个数字
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListprint(&s); //尾插4次后打印
	//头插2个数字
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, -1);
	SeqListprint(&s); //头插2次后打印
}

 1-3：指定下标插入

思路：在有效数据size范围内在指定下标插入想要插入的数据，同时检测是否需要扩容。

  • SeqList.h文件：
  • //在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
  • SeqList.c文件：
  • //在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	//暴力检查
	/*assert(pos <= psl);*/
	//温和检查
	if (pos > psl->size)
	{
		printf("pos 越界：%d\n", pos);
		return;
	}
	SeqListCheckCapacity(psl); //检测容量
	int end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
}

    Test.c文件：

  • void SeqListTest3()
{
	SeqList s;
	SeqListInit(&s);
	//先尾插4个数字
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListprint(&s); //尾插4次后打印
	//指定下标插入2个数字
	SeqListInsert(&s, 10, 100);
	SeqListInsert(&s, 1, 10);
	SeqListInsert(&s, 3, 20);
	SeqListprint(&s); //插入成功后打印
}

  • ⭐：当pos=size时，程序实现的就是尾插，所以尾插只是在指定下标插入的一种特殊情况。

  • //尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
//法一：
	/*SeqListCheckCapacity(psl); //检测容量
	psl->a[psl->size] = x;
	psl->size++;*/
//法二：
	SeqListInsert(psl, psl->size, x);
}

    同理：当pos=0时，实现的就是头插。

  • //头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
//法一：
	/*SeqListCheckCapacity(psl); //检测容量
	int end = psl->size;
	while (end > 0)
	{
		psl->a[end] = psl->a[end-1];
		end--;
	}
	psl->a[0] = x;
	psl->size++;*/
//法二：
	SeqListInsert(psl, 0, x);
}

2:删除数据

2-1：尾删

思路：我们创建的结构体成员size指的是顺序表中有效数据的个数，因为顺序表的下标是从0开始的，而下标size所对应的元素就是最后一位有效数据的下一位，所以我们想要实现尾删只需要把有效数据的个数-1，打印的时候自然会把最后一个数据删掉，如果删除次数过多，有效数据size可能会变成负数，所以我们需要确保在size>0的情况下再减减。

  • SeqList.h文件：
  • //尾删
void SeqListPopBack(SeqList* psl);
  • SeqList.c文件：
  • //尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	if (psl->size > 0)
	{
		psl->size--;
	}
  • Test.c文件：
  • void SeqListTest4()
{
	SeqList s;
	SeqListInit(&s); //注意加上&，因为形参的改变不影响实参
	//尾插5个数字
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListprint(&s); //尾插5次后打印

	//尾删4个数字
	//SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListprint(&s); //尾删4次后打印

	//再尾插2个数字
	SeqListPushBack(&s, 6);
	SeqListPushBack(&s, 7);
	SeqListprint(&s); //再尾插2次打印

}

2-2：头删

思路：头删就是去除下标为0的元素，我们只需要把下标1~size-1的元素都向前挪一位即可。同时也要确保size>=0。

  • SeqList.h文件：
  • //头删
void SeqListPopFront(SeqList* psl);
  • SeqList.c文件：
  • //头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	if (psl->size > 0)
	{
		int begin = 1;
		while (begin < psl->size)
		{
			psl->a[begin - 1] = psl->a[begin];
			begin++;
		}
		psl->size--;
	}
}
  • Test.c文件：
  • void SeqListTest5()
{
	SeqList s;
	SeqListInit(&s);
	//尾插10个数字
	for (int i = 1; i <= 10; i++)
	{
		SeqListPushBack(&s, i);
	}
	SeqListprint(&s); //尾插9个数字后打印
	//头删12次数据
	for (int i = 1; i <= 9; i++)
	{
		SeqListPopFront(&s);
	}
	SeqListprint(&s); //头删12次后打印
	//头插5个数字
	for (int i = -5; i <= -1; i++)
	{
		SeqListPushFront(&s, i);
	}
	SeqListprint(&s); //头插5次后打印
}

2-3：指定下标删除

思路：和头删的思路大致相同，同时确保指定下标pos<size,如果pos=size则是删除了一个无意义的数。

  • SeqList.h文件：
  • //删除pos位置的数据
void SeqListErase(SeqList* psl, size_t pos);

    SeqList.c文件：

  • //删除pos位置的数据
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);
	size_t begin = pos + 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}
	psl->size--;
}

    Test.c文件：

  • void SeqListTest6()
{
	SeqList s;
	SeqListInit(&s);
	//先尾插4个数字
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListprint(&s); //尾插4次后打印
	//删除2个指定下标的数字
	SeqListErase(&s, 1);//下标1
	SeqListErase(&s, 2);//下标2
	SeqListprint(&s); //删除后打印
}

  • ⭐：当pos=0时，删除的就是下标为0的元素，此时实现的就是头删。

  • //头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
//法一：
	/*if (psl->size > 0)
	{
		int begin = 1;
		while (begin < psl->size)
		{
			psl->a[begin - 1] = psl->a[begin];
			begin++;
		}
		psl->size--;
	}*/
//法二：指定下标删除法
	SeqListErase(psl, 0);
}

    而当pos=size-1时，实现的就是尾删。

 3:查找数据

思路：遍历数组即可。

  • SeqList.h文件：
  • //查找指定数字
int SeqListFind(SeqList* psl, SLDataType x);
  • SeqList.c文件：
  • //查找指定数字
int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
  • Test.c文件：
  • void SeqListTest7()
{
	SeqList s;
	SeqListInit(&s);
	//先尾插4个数字
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListprint(&s); //尾插4次后打印
	int pos = SeqListFind(&s, 2);
	if (pos != -1)
		printf("找到了，下标是：%d", pos);
	else
		printf("找不到\n");
}

 4:修改数据

思路：在有效数据范围内将指定下标元素进行修改即可。

  • SeqList.h文件：
  • //修改指定下标数字
void SeqListModify(SeqList* psl, size_t pos, SLDataType x);
  • SeqList.c文件：
  • //修改指定下标数字
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos < psl->size);
	psl->a[pos] = x;
}
  • Test.c文件：
  • void SeqListTest8()
{
	SeqList s;
	SeqListInit(&s);
	//先尾插4个数字
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListprint(&s); //尾插4次后打印
	SeqListModify(&s, 1, 5);
	SeqListprint(&s); //修改后打印
}

4:源码

SeqList.h

#pragma once

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

//创建顺序表

typedef int SLDataType; //确保以后想存其它数据类型的时候方便改动，本文以存放整型数据为例

typedef struct SeqList
{
	SLDataType* a; //动态开辟数组
	int size;      //存储顺序表中有效数据个数
	int capacity;  //记录开辟空间的容量
}SeqList;

//初始化顺序表
void SeqListInit(SeqList* psl);

//销毁顺序表
void SeqListDestory(SeqList* psl);

//打印顺序表
void SeqListprint(SeqList* psl);

//检查是否扩容
void SeqListCheckCapacity(SeqList* psl);
//尾插和尾删的时间复杂度为0(1)
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x);

//尾删
void SeqListPopBack(SeqList* psl);
//头插和头删的时间复杂度为0(N)
//头插
void SeqListPushFront(SeqList* psl, SLDataType x);

//头删
void SeqListPopFront(SeqList* psl);

//在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);

//删除pos位置的数据
void SeqListErase(SeqList* psl, size_t pos);

//查找顺序表中的元素
int SeqListFind(SeqList* psl, SLDataType x);

//修改指定下标数字
void SeqListModify(SeqList* psl, size_t pos, SLDataType x);

SeqList.c

#include "SeqList.h"

//初始化顺序表
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

//打印顺序表
void SeqListprint(SeqList* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

//销毁顺序表
void SeqListDestory(SeqList* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->capacity = psl->size = 0;
}

//检查是否扩容
void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);
	//如果满了，我们要扩容
	if (psl->size == psl->capacity)
	{
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;
		}
	}
}

//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	//法一
	//SeqListCheckCapacity(psl); //检测容量
	//psl->a[psl->size] = x;
	//psl->size++;
	//法二
	SeqListInsert(psl, psl->size, x);
}

//尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	//这里必须在size大于0的情况下完成尾删
	if (psl->size > 0)
	{
		(psl->size)--;
	}
}

//头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	//法一
	/*SeqListCheckCapacity(psl);

	int end = psl->size;
	while (end > 0)
	{
		psl->a[end] = psl->a[end-1];
		end--;
	}
	psl->a[0] = x;
	psl->size++;*/
	//法二
	SeqListInsert(psl, 0, x);
}

//头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	//法一
	/*if (psl->size > 0)
	{
		int begin = 1;
		while (begin < psl->size)
		{
			psl->a[begin - 1] = psl->a[begin];
			begin++;
		}
		psl->size--;
	}*/
	//法二
	SeqListErase(psl, 0);
}

//在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	//暴力检查
	/*assert(pos <= psl);*/
	//温和检查
	if (pos > psl->size)
	{
		printf("pos 越界：%d\n", pos);
		return;
	}
	SeqListCheckCapacity(psl); //检测容量
	int end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
}

//删除pos位置的数据
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);
	
	size_t begin = pos + 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		begin++;
	}
	psl->size--;
}

//查找顺序表中的元素
int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

//修改指定下标数字
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos < psl->size);
	psl->a[pos] = x;
}

test.c

#include "SeqList.h"

void SeqListTest1()
{
		SeqList s;
		SeqListInit(&s); //注意加上&，因为形参的改变不影响实参
		//尾插5个数字
		SeqListPushBack(&s, 1);
		SeqListPushBack(&s, 2);
		SeqListPushBack(&s, 3);
		SeqListPushBack(&s, 4);
		SeqListPushBack(&s, 5);
		SeqListprint(&s); //打印
}

void SeqListTest2()
{
	SeqList s;
	SeqListInit(&s); //注意加上&，因为形参的改变不影响实参
	//先尾插4个数字
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListprint(&s); //尾插4次后打印
	//头插2个数字
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, -1);
	SeqListprint(&s); //头插2次后打印
}

void SeqListTest3()
{
	SeqList s;
	SeqListInit(&s); //注意加上& ，因为形参的改变不影响实参
	//先尾插4个数字
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListprint(&s); //尾插4次后打印
	//指定下标插入2个数字
	SeqListInsert(&s, 10, 100);
	SeqListInsert(&s, 1, 10);
	SeqListInsert(&s, 3, 20);
	SeqListprint(&s); //插入成功后打印
}

void SeqListTest4()
{
	SeqList s;
	SeqListInit(&s); //注意加上&，因为形参的改变不影响实参
	//尾插5个数字
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListprint(&s); //尾插5次后打印

	//尾删4个数字
	//SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListprint(&s); //尾删4次后打印

	//再尾插2个数字
	SeqListPushBack(&s, 6);
	SeqListPushBack(&s, 7);
	SeqListprint(&s); //再尾插2次打印

}

void SeqListTest5()
{
	SeqList s;
	SeqListInit(&s);
	//尾插10个数字
	for (int i = 1; i <= 10; i++)
	{
		SeqListPushBack(&s, i);
	}
	SeqListprint(&s); //尾插10个数字后打印
	//头删12次数据
	for (int i = 1; i <= 9; i++)
	{
		SeqListPopFront(&s);
	}
	SeqListprint(&s); //头删12次后打印
	//头插5个数字
	for (int i = -5; i <= -1; i++)
	{
		SeqListPushFront(&s, i);
	}
	SeqListprint(&s); //头插5次后打印
}

void SeqListTest6()
{
	SeqList s;
	SeqListInit(&s);
	//先尾插4个数字
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListprint(&s); //尾插4次后打印
	//删除2个指定下标的数字
	SeqListErase(&s, 1);//下标1
	SeqListErase(&s, 2);//下标2
	SeqListprint(&s); //删除后打印
}

void SeqListTest7()
{
	SeqList s;
	SeqListInit(&s);
	//先尾插4个数字
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListprint(&s); //尾插4次后打印
	int pos = SeqListFind(&s, 2);
	if (pos != -1)
		printf("找到了，下标是：%d", pos);
	else
		printf("找不到\n");
}

void SeqListTest8()
{
	SeqList s;
	SeqListInit(&s);
	//先尾插4个数字
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListprint(&s); //尾插4次后打印
	SeqListModify(&s, 1, 5);
	SeqListprint(&s); //修改后打印
}

int main()
{
	/*SeqListTest1();
	SeqListTest2();
	SeqListTest3();
	SeqListTest4();
	SeqListTest5();*/
	/*SeqListTest6();*/
	/*SeqListTest7();*/
	SeqListTest8();
	return 0;
}

5:下篇预告

( o=^•ェ•)o 下篇我们将使用顺序表刷leetcode相关习题，我们不见不散???

如果看完这篇文章觉得有收获的请不要吝啬你的小手指噢~~（点个赞吧亲?）♥♥♥。

版权声明：本文为weixin_60718941原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。