美文网首页C语言C语言必知必会
【数据结构轻松学 二】顺序表 和 链表

【数据结构轻松学 二】顺序表 和 链表

作者: 不会编程的程序圆 | 来源:发表于2020-05-11 23:44 被阅读0次

码字不易,对你有帮助 点赞/转发/关注 支持一下作者

微信搜公众号:不会编程的程序圆

看更多干货,获取第一时间更新

【数据结构轻松学】系列 Github :https://github.com/hairrrrr/Date-Structure

本文的代码已上传至 Github

看更好的排版,阅读原文:
https://mp.weixin.qq.com/s/QhRWUPCxZPm1ViojONscWg

目录


toc

正文


一 顺序表

1. 结构

静态顺序表

使用定长数组

#define N 100
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType array[N]; // 定长数组
    size_t size; // 有效数据的个数
}SeqList;
动态顺序表
typedef int DataType; // 可扩展性

typedef struct SeqList
{
    DataType* array; // 指向动态开辟的数组
    size_t size; // 有效数据个数
    size_t capicity; // 容量空间的大小
}SeqList;

2. 接口实现

void SeqListPushBack(plist sl, DataType data); // 尾插
void SeqListPushFront(plist sl, DataType data); // 头插

void SeqListPopBack(plist sl); // 尾删
void SeqListPopFront(plist sl); // 头删

void SeqListInsert(plist sl, size_t pos, DataType data); // pos 位插入 x
void SeqListRemove(plist sl, size_t pos); // pos 位删除

void SeqListInit(plist sl, size_t capacity); // 初始化
void SeqListDestory(plist sl); // 销毁

void SeqListPrint(plist sl); // 打印
void SeqListCheckCapacity(plist sl); // 检查空间是否已经满,如果满了,就扩容

3. 顺序表的优劣势

劣势:

  1. 中间/头部的插入删除,时间复杂度为O(N)
  2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
  3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间

优势:

空间连续,支持随机访问。

二 链表

image

1. 无头单向非循环链表

接口实现:
typedef int Type;

typedef struct Node
{
    struct Node* _next;
    Type _data;
}Node;

//实现不带头单向非循环链表
typedef struct SingleList
{
    Node* _head; // head: 表示链表真正的头结点,即第一个有效的数据的位置
}SingleList;


void singleListInit(SingleList* sl); 

Node* creatNode(Type data); 

void singleListPushBack(SingleList* sl, Type data);

void singleListPopBack(SingleList* sl);

void singleListPushFront(SingleList* sl, Type data);

void singleListPopFront(SingleList* sl);

void singleListInsertAfter(Node* pos, Type data);

void singleListEraseAfter(Node* pos);

Node* find(SingleList* sl, Type data);

void singleListPrint(SingleList* sl);

void singleListDestroy(SingleList* sl);

2. 带头双向循环链表

接口实现
typedef int DataType;

// 结点类型
typedef struct ListNode
{
    DataType data;
    struct ListNode* next;
    struct ListNode* prev;
}ListNode;

// 表头
typedef struct ListHead {
    ListNode* head;
}ListHead;


// 接口
void ListCreate(ListHead* plist);

void ListDestory(ListHead* plist);

void ListPrint(ListHead* plist);

void ListPushBack(ListHead* plist, DataType data);

void ListPopBack(ListHead* plist);

void ListPushFront(ListHead* plist, DataType data);

void ListPopFront(ListHead* plist);

ListNode* ListFind(ListHead* plist, DataType data);

void ListInsert(ListNode* pos, DataType data);

void ListErase(ListNode* pos);

3. 链表的优劣势

优势:

以节点为单位存储,不支持随机访问

劣势:

  1. 任意位置插入删除时间复杂度为O(1)
  2. 没有增容问题,插入一个开辟一个空间。

查看【数据结构轻松学】更详细的目录: https://github.com/hairrrrr/Date-Structure

不要忘记 star 呦~

欢迎大家在 评论区/私信 提出问题/指正错误,谢谢观看。

我是程序圆,我们下次再见。

相关文章

  • 【数据结构轻松学 二】顺序表 和 链表

    码字不易,对你有帮助 点赞/转发/关注 支持一下作者微信搜公众号:不会编程的程序圆看更多干货,获取第一时间更新【数...

  • 带头结点的链表

    1、链表和顺序表 链表是很常见的数据结构,链表总是会和线性顺序表来比较。 1.1、顺序表 具有随机存储的特性,给定...

  • python中的树数据结构

    线性数据中的典型顺序表和链表已经讲完: 《顺序表数据结构在python中的应用》 《python实现单向链表数据结...

  • 数据结构

    数据结构 数据结构概念 顺序表 链表 队列 栈 二叉树 常用排序算法

  • 数据结构笔记

    数据结构课程概览 ================== 1.顺序表 2.链表:单链表,单向循环链表,双链表...

  • 总结

    Android篇 数据结构与算法顺序表 - ArrayList源码链表 - 单向链表、双向链表 - LinkedL...

  • 数据结构-线性表

    [TOC] 线性表-List list是最简单的数据结构,可分为顺序表与链表,顺序表内部数据存储由数组实现,链表则...

  • 线性表之顺序表和链表(单/双链表,单/双循环链表)

    线性表按存储方式分为顺序表和链表两种,其中链表又分为单链表,循环链表,双链表,双向循环链表。 顺序表 顺序表采用顺...

  • 数据结构

    数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈和队列; 树结构,包括普通树,二叉树,线索二...

  • Java 数据结构 单向链表

    Java 数据结构 单向链表 基础介绍 链表与循序表都是同属于数据结构中顺序表中的一种,而它与循序表的不同就在于 ...

网友评论

    本文标题:【数据结构轻松学 二】顺序表 和 链表

    本文链接:https://www.haomeiwen.com/subject/gfvmnhtx.html