数据结构初阶:顺序表和链表

发布于:2024-04-07 ⋅ 阅读:(150) ⋅ 点赞:(0)

线性表

线性表 linear list n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串 ...
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,
线性表在物理上存储时,通常以数组和链式结构的形式存储。

顺序表

概念及结构

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构,一般情况下采用数组存
储。在数组上完成数据的增删查改。
与数组的区别:
特点:只能从头开始连续存储

顺序表一般可以分为:
1. 静态顺序表:使用定长数组存储元素
缺点:不知道需要多少,N给小了不够用,N给大了浪费。

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

 接口实现

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

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;  // 空间容量
}SL;

void SLInit(SL* psl);
void SLDestroy(SL* psl);

void SLPrint(SL* psl);
void SLCheckCapacity(SL* psl);

// 头尾插入删除
void SLPushBack(SL* psl, SLDataType x);
void SLPushFront(SL* psl, SLDataType x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);

// pos下标位置前的插入
void SLInsert(SL* psl, int pos, SLDataType x);
// pos下标位置的删除
void SLErase(SL* psl, int pos);

SeqList.c

#include"SeqList.h"

void SLInit(SL* psl)
{
	assert(psl);

	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

void SLDestroy(SL* psl)
{
	assert(psl);

	if (psl->a != NULL)
	{
		free(psl->a);
		psl->a = NULL;
		psl->size = 0;
		psl->capacity = 0;
	}
}

void SLPrint(SL* psl)
{
	assert(psl);

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

void SLCheckCapacity(SL* psl)
{
	assert(psl);

	if (psl->size == psl->capacity)
	{
		int newCapacity = psl->capacity 

网站公告

今日签到

点亮在社区的每一天
去签到