【数据结构】顺序表和链表

目录

前言

一、顺序表

1.概念及结构

2.函数接口

二、链表

1.概念及结构

2.单向无头非循环列表接口

3.双向带头循环列表接口

---

前言

顺序表与链表都属于线性表，二者均在逻辑上是线性结构，也就说是连续的一条直线，但是在物理内存上并不一定是连续的。其中，顺序表一般以数组来存储数据，链表则定义一种结构体形成链式结构来存储数据。

---

一、顺序表

1.概念及结构

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

顺序表一般可以分为：

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

2.函数接口

#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
    SLDataType* data;
    int size;     // 有效数据个数
    int capacity; // 空间容量
}SL;

//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLInitPrint(SL* ps);

//扩容
void SLCheckCapacity(SL* ps);

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

//指定位置之 前/后 插入/删除 数据
void SLInsert_B(SL* ps, int pos, SLDataType x);//前插
void SLInsert_A(SL* ps, int pos, SLDataType x);//后插
void SLErase_B(SL* ps, int pos);//前删
void SLErase_A(SL* ps, int pos);//后删

//指定位置开始查找指定数据
int SLFind(SL* ps, int* init_pos, SLDataType x);

源代码参考下面链接：

SL_DateStructure 动态顺序表https://gitee.com/yuhe-liang/c_learning/tree/master/SL_DateStructure

二、链表

1.概念及结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

• 单向或者双向
• 带头或者不带头
• 循环或者非循环

单向无头非循环列表如下图：

双向带头循环列表如下图：

2.单向无头非循环列表接口

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//打印链表
void SLTPrint(SLTNode* phead);
//打印节点
void NodePrint(SLTNode* node);

//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

源代码参考下面链接：

linked_list单向无头非循环列表https://gitee.com/yuhe-liang/date_structure/tree/master/linked_list

3.双向带头循环列表接口

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate(LTDataType x);
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

源代码参考下面链接：

D_Linked_List 双向带头循环列表https://gitee.com/yuhe-liang/date_structure/tree/master/D_Linked_List

?