【数据结构】顺序表(Sequential List) && 单链表(Singly Linked List )

更多精彩尽在微信公众号【程序猿声】

微信公众号

本节纲要

  • 预备知识
  • 顺序表(Sequential List)
  • 单链表(Singly Linked List )
  • 静态链表(Static list )
  • 循环链表(circular linked list)
  • 双向链表(doubly linked list)

01 预备知识

1.0 什么是线性表?

线性表(List)是零个或者多个数据元素的有限序列.

  • 首先它是一个序列.里面的元素是有顺序的,如果有多个元素,除开头和结尾以外的元素都有一个前驱和一个后继.而开头元素只有后继,结尾元素只有前驱.
  • 其次线性表是有限的,也就是里面的元素个数是有限的。

1.1 线性表的基本操作(描述)

ADT 线性表(List)
Data
    线性表的数据对象集合为{a1, a2, a3, ......, an},每个元素类型为DataType。
Operation
    InitList(L);        //初始化线性表
    IsEmptyList(L);     //判断线性表是否为空
    ClearList(L);       //清空线性表
    GetElemList(L, i, *e); //获取第i个位置的数据
    SearchList(L, e); //查找与数据e相等的元素
    InsertNodeList(L, i, e);//在第i个位置插入元素
    DeleteNodeList(L, i, *e);//删除第i个位置的元素,e获取删除元素
    GetLengthList(L);  //获取线性表的长度
endADT

关于线性表的基本操作就上面几种,还有几个例如线性表的排序,合并,逆序等等操作。为了文章篇幅,就下次再介绍了。

1.2 什么是顺序存储结构?

线性表的顺序存储结构,就是指 用一段地址连续的存储单元一次存储线性表的数据元素。学过高级语言的朋友,相信对数组这玩意儿都不会陌生吧。数组就是一种顺序存储结构。

1.3 什么是链式存储结构?

链式存储结构就是可以用一组任意的内存单元存储线性表中的元素。与顺序存储不同的是,这组内存单元可以是连续的,也可以是不连续的。这就意味着,元素可以存储在内存的任意位置。正因为如此,在链式结构中,每个元素不仅要存它的信息,还需要存储它后继元素的存储地址。我们把存储元素信息的域称为数据域,而把存储后继元素地址的域称为指针域。由这两部分共同组成的数据元素ai,则可以称之为节点(Node)。

如下面这个图所示:

1.5 什么是链表?

链表就是链式存储的线性表。结点之间通过逻辑连接,形成链式存储结构。存储结点的内存单元,可以是连续的也可以是不连续的。逻辑连接与物理存储次序没有关系。

02 顺序表(Sequential List)

2.0 什么是顺序表?

采用顺序存储结构的线性表,就是顺序表。

2.1 顺序表的存储结构代码

这里我们统一采用C语言来描述。

#define MAXSIZE 20   //存储空间的初始大小
typedef int DataType //类型可根据实际情况而定
typedef struct 
{
    DataType data[MAXSIZE]; //数组来存储数据
    int length;              //实际长度
}SqlList;

可见,顺序表的几个重要特性:

  • 存储空间的位置:数组data
  • 顺序表的最大容量:数组长度MAXSIZE
  • 顺序表当前长度:length

2.2 顺序表的插入操作

相信大家在排队的时候都有过被插队的体验吧。当一个插队到你前面时,这个时候你内心os mmp外加素质三连的同时,也不得不往后挪一个位置。于是乎这个就不得了了,你后面的也要往后挪,你后面的后面也是……然后队伍里瞬间就狼烟起……

那么,这个顺序表的插入其实也差不多的。由于地址是连续存储的,那么在某个地方插入以后,其后的元素不得不往后挪一个位置。

插入算法描述:

  • 异常处理(插入位置不合理、顺序表已经满等等)。抛出异常。
  • 从最后一个元素往前遍历到第i个位置,依次将他们都往后挪一个位置。
  • 将要插入的元素放入位置i处。
  • 别忘记了表长度length++。

由于数组下标是从0开始的,我们习惯要删除的位置第i处又是从1开始算起的。本文就全部统一成,都从0开始吧。比如要在第5个位置插入一个元素,那就是a5。不然真的会混乱的。

具体代码如下:

//功能:在顺序表L第i个位置之前插入元素e
int InsertSqlList(SqlList *L, int i, DataType data)
{
    int k;
    if(L->length==MAXSIZE || i<0 || i>L->length) //记住,都是从0开始的哦
        return 0;//异常处理
    if(i == L->length)
        L->data[length++] = data;//尾插一步到位
    if(i < L->length)  //中间插,要挪人啦
    {
        for(k = L->length-1; k >= i;k--) //再次强调哈,都是从0开始的。
            L->data[k+1]=L->data[k];//后移
        L->data[i] = data;//新元素插入
        L->length++;
    }
    return 1;
}

2.2 顺序表的删除操作

算法描述:

  • 异常处理(删除位置不合理、顺序表为空等等)//功能:在顺序表L中删除第i个数据元素,用e获取被删除值 int DeleteElemList(SqlList *L, int i, DataType *e) { int k; if(L->length==0 || i<0 || i>L->length-1) //记住,都是从0开始的哦 return 0;//异常处理 if(i == L->length-1) //尾删,easy { *e = L->data[i];//获取要删除元素 L->length--; //删除元素 } if(i < L->length) //中间删,要挪人啦 { *e = L->data[i];//获取要删除元素 for(k = i; k < L->length-1;k++) //再次强调哈,都是从0开始的。 L->data[k]=L->data[k+1];//前移 L->length--; return 1; }2.3 顺序表的完整代码#include <stdio.h> #include <stdlib.h> #define MAXSIZE 20 #define ERROR 0 #define OK 1 #define NO 0 #define YES 1 typedef int DataType; typedef int Status; typedef struct List { int data[MAXSIZE]; int length; }SqlList; void InitList(SqlList * L); //初始化顺序表 Status IsEmptyList(SqlList *L); //判断顺序表是否为空 void ClearList(SqlList *L); //清空线性表 Status GetElemList(SqlList *L,int i,DataType *e); //获取第i个位置的数据 int SearchList(SqlList *L, DataType e); //查找与数据e相等的元素 Status InsertNodeList(SqlList *L, int i,DataType e);//在第i个位置插入元素 Status DeleteNodeList(SqlList *L, int i, DataType *e);//删除第i个位置的元素,e获取删除元素 int GetLengthList(SqlList *L); //获取线性表的长度 void PrintList(SqlList *L); //遍历顺序表,此函数测试使用,根据实际类型编写 int main() { int e; SqlList *pL = (SqlList*)malloc(sizeof(SqlList)); InitList(pL); InsertNodeList(pL, 0, 1); InsertNodeList(pL, 1, 2); InsertNodeList(pL, 2, 3); InsertNodeList(pL, 3, 4); InsertNodeList(pL, 4, 5); InsertNodeList(pL, 5, 6); PrintList(pL); DeleteNodeList(pL, 2, &e); DeleteNodeList(pL, 4, &e); PrintList(pL); return 0; } void InitList(SqlList * L) { for(int i = 0; i < MAXSIZE; i++) L->data[i] = 0; L->length = 0; //将表设为空 } Status IsEmptyList(SqlList *L) { if(L->length == 0) return YES;//表为空 else return NO; } void ClearList(SqlList *L) { InitList(L);//此操作跟初始化一样。 } //这里的第i个位置,为了统一我们也是从0算起的 Status GetElemList(SqlList *L,int i,DataType *e) { if(i < 0 || i >= L->length || L->length == 0) return ERROR;//异常处理 *e = L->data[i]; return OK; } //找到与数据e相同的节点,返回下标。-1表示没找到,ERROR表示表为空 int SearchList(SqlList *L, DataType e) { if(L->length == 0) return ERROR; for(int i = 0; i < L->length; i++) { if(L->data[i] == e) return i; } return -1; } //获取顺序表的长度 int GetLengthList(SqlList *L) { return L->length; } //在位置i插入元素,再次强调,从0开始 Status InsertNodeList(SqlList *L, int i,DataType e) { if(i < 0 || i > L->length || L->length == MAXSIZE) return ERROR;//异常处理 for(int k = L->length; k > i; k--) { L->data[k] = L->data[k-1]; //往后挪 } L->data[i] = e;//插入数据, L->length++; //长度也要加1 return OK; } Status DeleteNodeList(SqlList *L, int i, DataType *e) { if(i < 0 || i > L->length || L->length == 0) return ERROR;//异常处理 *e = L->data[i];//获取数据 for(int k = i; k < L->length -1; k++) L->data[k] = L->data[k+1];//往前挪 L->length--; //长度减1 return OK; } void PrintList(SqlList *L) { if(L->length == 0) { printf("顺序表为空\n"); } printf("============遍历顺序表如下=============\n"); for(int i = 0; i < L->length; i++) { printf("\tdata[%d] = %d\n", i, L->data[i]); } printf("============共计%d个元素=============\n", L->length); }
  • 尾删,直接获取然后length--。
  • 中间删,从i开始往后遍历,依次将各元素往前挪。e获取要删元素,length--即可。

纯手打哈。。简单测试了一下。如果存在问题,欢迎指正,谢谢大家。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java学习录

浅谈数据库事务

原子性是指事务包含的所有操作要么全部成功,要么全部失败。 例小王要向小李转账200元。则账要么转账成功小王账户减200元,小李账户加200元,要么执行失败,两者...

11800
来自专栏运维经验分享

用monit监控mongodb,崩溃后自动重启mongdb

Monit是一个跨平台的用来监控Unix/linux系统(比如Linux、BSD、OSX、Solaris)的工具。Monit特别易于安装,而且非常轻量级(只有5...

18600
来自专栏Java学习录

使用Apollo做配置中心

由于Apollo支持的图形化界面相对于我们更加的友好,所以此次我们使用Apollo来做配置中心

30700
来自专栏程序员同行者

kubernetes系列之ConfigMap使用方式

如启用一个mysql容器,mysql容器重要的文件有两部分,一部分为存储数据文件,一部分为配置文件my.cnf,存储数据可以用持久存储实现和容器的分离解耦,配置...

54300
来自专栏Java架构师进阶

通用数据权限的思考与设计

如果想学习Java工程化、高性能及分布式、深入浅出。微服务、Spring,MyBatis,Netty源码分析的朋友可以加我的Java高级交流:787707172...

51400
来自专栏FREE SOLO

数据库锁的分类(粒度,级别)

数据库是一个多用户使用的共享资源。当多个用户并发地存取数据时,在数据库中就会产生多个事务同时存取同一数据的情况。若对并发操作不加控制就可能会读取和存储不正确的数...

24700
来自专栏阿dai_linux

面试没什么了不起! 原

针对找工作这件事情来讲,很多人都讲"金三银四",其实我对这个说法并不以为然,但是处于种种原因吧,今年3月份我还是加入求职大军。下面总结一下作为一名Linux系统...

10400
来自专栏magicodes

扒一扒.NET Core的环境配置提供程序

很久之前,在玩Docker的时候顺便扒了扒,最近,终于下定决心花了些时间整理并成文,希望能够给大家一些帮助。

9100
来自专栏FREE SOLO

2019面试题:谈谈对JDBC的理解(最简洁!)

JDBC(Java Data Base Connectivity,java数据库连接)是一种用于执行SQL语句的Java API(Application Pro...

18900
来自专栏mySoul

MyBatis 映射器

11510

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励