数据结构入门-顺序表链表

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种实际中广泛使用多个数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

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

顺序表

概念及结构

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

顺序表一般可分为：

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

//顺序表的静态存储
#define N 7
typedef int SLDataType;   //整形数据typedef struct SeqList
{SLDataType array[N];  //定长数组，N=7事先定义。size_t size;          //有效数据的个数
}SeqList;

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

//顺序表的动态存储
typedef struct SeqList
{SLDataType* array; //指向动态开辟的数组size_t size;       //有效数据个数size_ capicity;    //容量空间的大小
}SeqList;

接口实现

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

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{SLDataType* array; // 指向动态开辟的数组size_t size ; // 有效数据个数size_t capicity ; // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl, size_t capacity);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x); 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);

函数补全请关注我的博客更新~

链表

链表的概念及结构

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

• 从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续；
• 现实中的节点一般都是从堆上申请出来的；
• 从堆上申请的空间，是按照一定的策略分出来的，两次申请的空间可能连续也可能不连续。

链表的分类

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

• 单向或双向

• 带头或者不带头

 

• 循环或者非循环

 虽然有这么多种结构，但是最常用的只有两种

• 无头单向非循环链表
• 带头双向循环链表

1.无头单向非循环链表： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结 构 ，如哈希桶、图的邻接表等等。另外这种结构在 笔试面试 中出现很多。

2. 带头双向循环链表： 结构最复杂 ，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

链表的实现

// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);

// 2、带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* next;struct ListNode* prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

顺序表和链表的区别和联系

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，物理上不一定
随机访问	支持O（1）	不支持O（n）
任意位置任意插入或者删除	可能需要搬移元素，效率低O（n）	只需要修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入删除频繁
缓存利用率	高	低