数据结构初阶 链表的讲解

数据结构初阶 链表的讲解

一. 线性表

1.1 定义

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

看这个定义 我们再联想前面的知识

是不是发现数组的使用和这个定义十分相似

没错 其实顺序表本质上就是数组

但是它再数组上增加了一点内容

1.2 特点

它分为静态的和动态的

这个特点是不是又发现和我们上面做的项目通讯录十分相似

它是连续存储的 不能跳过元素

二. 顺序表

2.1 定义

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

2.2 代码

structSeqList{int a[100];//数组int size;//数组中存储了多少个数字 };

我们说类似这个结构的 就是一个顺序表

但是呢 为了我们以后改变数字方便 我们可以把这里的100 定义成一个宏 这样我们以后如果想修改顺序

表的大小 只要改变宏就可以了

代码表示如下

// 静态顺序表#defineN100structSeqList{int a[N];//数组int size;//数组中存储了多少个数字 };

上面就是一个标准的静态数据表 假如说 我们想使用顺序表来管理一个字符串

#defineN100structSeqList{char a[N];//数组int size;//数组中存储了多少个数字 };

我们可以改变int类型 变为char类型的数据 但是这样每次改也太麻烦了 所以我们依旧可以再上面定义

一个宏变量

#defineN100typedefchar SLDateType
structSeqList{int SLDateType[N];//数组int size;//数组中存储了多少个数字 };

我们说 就可以使用这样的格式 方便以后一次性改变所有的变量类型

但是呢 这样子我们看整个结构体还是有点麻烦 我们再将这个结构体简化一下

typedefstructSeqList{int SLDateType[N];//数组int size;//数组中存储了多少个数字 }SL;

这样子就能得到一个相对完美的静态顺序表啦

2.3 功能需求

在创建好这个静态表之后 我们要开始大概创建它的一些功能啦

比如说以下的一些功能

vovoid SeqListInit(SL* ps);voidSeqListPushBack(SL* ps, SLDateType x);voidSeqListPopBack(SL* ps);voidSeqListPushFront(SL* ps, SLDateType x);voidSeqListPopFront(SL* ps);

初始化 尾插 头插等等

2.4 静态顺序表的特点以及缺点

特点： 如果满了就不让插入

缺点： 不知道给多少合适

2.5 动态的顺序表

typedefstructSeqList{
    SLDateType* a;//数组int size;//数组中存储了多少个数字 int capacity;}SL;

是不是跟我们的通讯录特别相似

其实原理本质上都是一样的 这里只是命名更加规范了

2.6 动态顺序表接口的实现

初始化

voidSeqListInit(SL* ps){
    ps->a =NULL;
    ps->size = ps->capacity =0;}

尾插

我们先写空间足够的情况

voidSeqListPushBack(SL* ps, SLDateType x){
    ps->a[ps->size]= x;
    ps->size++;}

代码表示如上

那么我们接下来我们写上面的两种情况

这里我们要注意的是 一开始我们将指针置空 占用的空间为0

所以说我们一开始至少要开始4个数据的空间 这里可以使用一个三目操作符解决

int newcapacity = ps->capacity ==0?4: ps->capacity *2;

养成良好的习惯 代码加注释

voidSeqListPushBack(SL* ps, SLDateType x){// 如果没有空间或者空间不足 我们就扩容 // 扩容失败就报错if((ps->size)==(ps->capacity)){int newcapacity = ps->capacity ==0?4: ps->capacity *2;
        SLDateType* tmp =(SLDateType*)realloc(ps->a, newcapacity *sizeof(SLDateType));if(tmp==NULL){perror("pushback realloc");}}
    ps->a[ps->size]= x;
    ps->size++;}

这里我们使用一个打印函数看看整个数据的内容

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

打印出结果如下

在使用完成之后我们还需要一个借口函数来释放我们的动态开辟的内存 从而避免内存泄漏的问题

voidSeqListDestory(SL* ps){free(ps->a);
    ps->a ==NULL;
    ps->capacity = ps->size =0;}

接下来我们看尾删函数

voidSeqListPopBack(SL* ps){
    ps->size--;}

尾删的话其实我们只要将size-- 就可以

但是这里我们要注意一点 当size为0的时候 这里就不可以再删除了 所以我们还需要完善以下上面的代码

voidSeqListPopBack(SL* ps){if(ps->size==0){perror("SeqListPopBack");}
    ps->size--;}

接下来我们看前插

voidSeqListPushFront(SL* ps, SLDateType x){// 考虑扩容问题if((ps->size)==(ps->capacity)){int newcapacity = ps->capacity ==0?4: ps->capacity *2;
        ps->capacity = newcapacity;
        SLDateType* tmp =(SLDateType*)realloc(ps->a, newcapacity *sizeof(SLDateType));if(tmp ==NULL){perror("pushback realloc");}
        ps->a = tmp;}// 头插int end = ps->size -1;while(end>=0){
        ps->a[end +1]= ps->a[end];}
    ps->a[0]= x;
    ps->size++;}

接下来我们来看头删

这就要求我们定义一个bejin 然后从前往后依次挪数据

代码表示如下

voidSeqListPopFront(SL* ps){int bejin =0;while(bejin<ps->size-1){
        ps->a[bejin]= ps->a[bejin +1];
        bejin++;}
    ps->size--;}

这里我们基本实现了顺序表的所有接口函数啦

三. 代码

头文件

#pragmaonce#defineN100#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint SLDateType;typedefstructSeqList{
    SLDateType* a;//数组int size;//数组中存储了多少个数字 int capacity;}SL;voidSeqListInit(SL* ps);voidSeqListDestory(SL* ps);voidSeqListPushBack(SL* ps, SLDateType x);voidSeqListPopBack(SL* ps);voidSeqListPushFront(SL* ps, SLDateType x);voidSeqListPopFront(SL* ps);voidSeqListPrint(SL* ps);// . //...

主文件

#define_CRT_SECURE_NO_WARNINGS1#include"seqlist.h"voidSeqListInit(SL* ps){
    ps->a =NULL;
    ps->size = ps->capacity =0;}voidSeqListPrint(SL* ps){int i =0;for( i =0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");}voidSeqListPushBack(SL* ps, SLDateType x){// 如果没有空间或者空间不足 我们就扩容 // 扩容失败就报错if((ps->size)==(ps->capacity)){int newcapacity = ps->capacity ==0?4: ps->capacity *2;
        ps->capacity = newcapacity;
        SLDateType* tmp =(SLDateType*)realloc(ps->a, newcapacity *sizeof(SLDateType));if(tmp==NULL){perror("pushback realloc");}
        ps->a = tmp;}
    ps->a[ps->size]= x;
    ps->size++;}voidSeqListDestory(SL* ps){free(ps->a);
    ps->a =NULL;
    ps->capacity = ps->size =0;}voidSeqListPopBack(SL* ps){if(ps->size==0){perror("SeqListPopBack");}
    ps->size--;}voidSeqListPushFront(SL* ps, SLDateType x){// 考虑扩容问题if((ps->size)==(ps->capacity)){int newcapacity = ps->capacity ==0?4: ps->capacity *2;
        ps->capacity = newcapacity;
        SLDateType* tmp =(SLDateType*)realloc(ps->a, newcapacity *sizeof(SLDateType));if(tmp ==NULL){perror("pushback realloc");}
        ps->a = tmp;}// 头插int end = ps->size -1;while(end >=0){
        ps->a[end +1]= ps->a[end];
        end--;}
    ps->a[0]= x;
    ps->size++;}voidSeqListPopFront(SL* ps){int bejin =0;while(bejin<ps->size-1){
        ps->a[bejin]= ps->a[bejin +1];
        bejin++;}
    ps->size--;}

测试文件

#define_CRT_SECURE_NO_WARNINGS1#include"seqlist.h"intmain(){
    SL a1;SeqListInit(&a1);SeqListPushBack(&a1,1);SeqListPushBack(&a1,2);SeqListPushBack(&a1,3);SeqListPushBack(&a1,4);SeqListPushBack(&a1,5);SeqListPrint(&a1);SeqListPopBack(&a1);SeqListPrint(&a1);SeqListPopFront(&a1);SeqListPrint(&a1);SeqListDestory(&a1);return0;}

以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够

不吝赐教 在评论区或者私信指正 博主一定及时修正

那么大家下期再见咯