数据结构简单话(一)线性表

前言

本菜鸟笔者打算入门一下数据结构,在学习过程中通过自己简单话术总结相关基础知识要点,希望能帮助同样在入门的小伙伴们快速了解相关基础知识的轮廓,然后根据知识点再进一步的学习和理解。整个系列采用c语言来实现,代码会提供注释,方便理解实现思路。

逻辑结构

线性表是0个或多个的有穷序列,(k_0) 是(k_1)的前驱,(k_1)是(k_0)的后继,除了首尾结点以外每个结点元素都有且只有一个前驱和一个后继(类似于现实生活中排队)。

物理存储结构

一、顺序表

  1. 概念:采用一组相邻且连续的存储空间存储元素。即:存储一个元素需要2个单位地址空间,从1号开始存储,则第二个元素存储首地址为3号,以此类推。代码实现中常用 数组作为顺序表元素的存储。
  2. 优缺点
  3. 优点:方便查找,确定首地址就可以查找任意下标的元素。由此可以随机存取。
  4. 缺点:不易于插入删除,由于顺序表中元素地址是相邻的,当插入或者删除一个元素后,修改位置之后的所有元素都需要移动,空间开销大(类比排队中一个人出或者插入到队伍中,后面的所有人都需要向前或向后移动)
  5. 代码实现(初始化增删改查)
#include
#include

#define MAXMIUM 100 //定义数组容量最大值
/*结构体*/
typedef struct SeqList
{
    int element[MAXMIUM];//存放整型数据的数组
    int n;//数组元素个数
}SeqList;
/*初始化,创建一个顺序表*/
SeqList *createNullSeq()
{
    SeqList *list = (SeqList *)malloc(sizeof(SeqList));
    if (list == NULL)
    {
        printf("wrong");
    }
    else
    {
        list->n = 0;//初始化的数组内没有元素,所以n=0
    }
    return list;
}

/*在指定下标位置插入元素*/
int insert(SeqList* list , int data,int index){
    if(list->n < MAXMIUM && indexn){//插入前数组个数不能达到上限,下标需要在有效范围内
        int i;
        for(i=list->n-1;i>=index;i--){//当前插入元素的位置和位置后的元素都需要往后移动一位
            list->element[i+1] = list->element[i];
        }
        i++;
        list->element[i] = data;
        list->n++;
        return 1;
    }
    return 0;

}
/*删除指定位置的元素*/
int delete(SeqList* list,int index){
    if(indexn-1&&index>=0){//跟插入类似,判断有效条件
        for(int i=index;in-1;i++){//删除的位置以及后面的元素都需要往前移动一格
            list->element[i] = list->element[i+1];
        }
        list->n--;
        return 1;
    }
    return 0;
}
/*简单线性表判空*/
int isNull(SeqList* list){
    return list->n==0?1:0;
}
/*查找元素*/
int locate_seq(SeqList* list,int data){
    if(list->n==0){
        return -1;
    }
    for(int i=0;in;i++){
        if(list->element[i]==data){
            return i;
        }
    }
    return -1;
}
/*获得指定下标的元素*/
int find(SeqList* list,int x){
    if(x>=0||xn){
        return list->element[x];
    }

    return -1;
}

二、链表

  1. 原理 顺序表插入删除需要大量空间损耗(因为需要移动),所以可以采用链表的方式减少损耗。每个结点元素在存储元素信息时(数据域),还需要额外存储一个指针域,用于存储指向下一个结点的地址。这样相邻结点之间的地址无需相邻。插入删除时只需要修改相关指针域即可。
  2. 优缺点
  3. 优点:插入删除空间代价小,只需要直接修改指针域。
  4. 缺点:查找麻烦,每次查找都需要从头结点遍历。
  5. 代码实现(初始化增删改查)
#include <stdio.h>
#include <stdlib.h>

typedef struct PNode
{
    struct PNode *next;
    int data;
} PNode;

PNode *createNullNode()
{
    PNode *node = (PNode *)malloc(sizeof(PNode));
    if (node == NULL)
    {
        printf("wrong");
        return NULL;
    }
    node->next = NULL;
    node->data = 0;
    return node;
}

/*&#x5E26;&#x5934;&#x7ED3;&#x70B9;&#x63D2;&#x5165;*/
int insertNode(PNode *list, int i, int data)
{
    if (list == NULL)
    {
        printf("null");
        return 0;
    }
    int p = 0;
    while (list->next != NULL)
    {
        if (p != i)
        {
            list = list->next;
            p++;
        }else{
          break;
        }
    }
    if (p == i)
    {
        PNode *temp = list->next;
        PNode *node = createNullNode();
        node->next = temp;
        node->data = data;
        list->next = node;
        return 1;
    }
    printf("out of range");
    return 0;
}
/*&#x5E26;&#x5934;&#x7ED3;&#x70B9;&#x5220;&#x9664;&#x7B2C;&#x4E00;&#x4E2A;&#x503C;&#x4E3A;x&#x7684;&#x7ED3;&#x70B9;*/
int delete(PNode *list,int x){
    if(list==NULL){
        printf("list is null");
        return 0;
    }
    while(list->next!=NULL&&list->next->data!=x){
        list = list->next;
    }
    if(list->next!=NULL&&list->next->data==x){
        PNode* temp = list->next;
        list->next = temp->next;
        temp->next = NULL;
        free(temp);
        return 1;
    }
    printf("no found %d",x);
    return 0;
}

/*&#x901A;&#x8FC7;&#x4E0B;&#x6807;&#x67E5;&#x627E;&#x5143;&#x7D20;&#xFF0C;&#x5E26;&#x5934;&#x7ED3;&#x70B9;*/
PNode *find(PNode* list,int i){
    if(list==NULL){
        printf("null list ");
        return NULL;
    }
    int cursor = 0;
    while(list->next!=NULL&&cursor!=i){
        list = list->next;
        cursor++;
    }
    if(cursor==i){
        printf("find %d",list->next->data);
        return list->next;
    }
    printf("out of range");
    return NULL;
}

/*&#x5224;&#x7A7A;*/
int isNull(PNode* list){
    return list==NULL?1:list->next==NULL?1:0;
}
int main()
{
    PNode *head = createNullNode();
    int flag = isNull(head);
    printf("%d\n",isNull(head));
    insertNode(head,0,1);
    insertNode(head,1,2);
    insertNode(head,2,3);
    insertNode(head,3,4);
    insertNode(head,2,77);
    // find(head,2);
    printf("%d",isNull(head));
}
</stdlib.h></stdio.h>

总结

  1. 链表方便增删,顺序表方便查找
  2. 链表的增删主要通过修改指针,顺序表增删主要通过移动元素。

Original: https://www.cnblogs.com/allworldg/p/15339910.html
Author: allworldg
Title: 数据结构简单话(一)线性表

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/583402/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

  • WPF 调试依赖属性变更方法

    本文告诉大家如何调试 WPF 的某个依赖属性被变更的方法 在 WPF 里面,所有的依赖属性都有带通知的功能,通过带通知的功能,可以在通知里加上断点,通过调用堆栈了解是哪个模块调用的…

    Linux 2023年6月6日
    066
  • update-alternatives使用,更改Linux中软件默认版本

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月20日
    0261
  • Linux文本处理相关命令

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年9月10日
    0232
  • Linux c 开发-24 程序后台运行

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月24日
    0202
  • Ubuntu下为openwrt交叉编译cmake

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月26日
    0234
  • 【Docker搭建】0. 在CentOS下安装/卸载Docker

    警告:切勿在没有配置 Docker YUM 源的情况下直接使用 yum 命令安装 Docker. 系统要求Docker CE 支持 64 位版本 CentOS 7,并且要求内核版本…

    Linux 2023年6月13日
    049
  • Linux命令——jobs、bg、fg、nohup

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月24日
    0231
  • yum安装java时,没有jps的问题的解决

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月30日
    0226
  • ubuntu 查看cp2012和ch340串口转换器的驱动是否正确安装

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月26日
    0281
  • 五分钟通俗理解自动驾驶

    大家好,我是良许。 这几年,自动驾驶这个概念非常火热,无论是百度还是谷歌,都做出了还不错的原型机,但是你真的知道什么是自动驾驶吗? 本文就花 5 分钟左右的时间,向大家科普一下什么…

    Linux 2023年6月14日
    077
  • golang之context

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    2022年8月11日
    0258
  • oracle删除超过N天数据脚本

    公司内做的项目是工厂内的,一般工厂内数据要求的是实时性,很久之前的数据可以自行删除处理,我们数据库用的oracle,所以就想着写一个脚本来删除,这样的话,脚本不管放在那里使用都可以…

    Linux 2023年6月7日
    081
  • 【深度学习】ml_collections报错

    在一些源码中,看见了一个导入: import ml_collections 此时会报错,这个包并不是PyTorch的包,同时也非源码中模块 解决办法: pip install ml…

    Linux 2023年6月13日
    055
  • Docker安装及配置镜像加速

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年9月10日
    0179
  • Redis 配置文件

    http://blog.csdn.net/tonysz126/article/details/8280696/ 2.1 Redis配置文件 为了对Redis的系统实现有一个直接的认…

    Linux 2023年5月28日
    074
  • redis详解(三)– 面试题(转载)

    使用redis有哪些好处? (1) 速度快,因为数据存在内存中,类似于HashMap,HashMap的优势就是查找和操作的时间复杂度都是O(1) (2) 支持丰富数据类型,支持st…

    Linux 2023年5月28日
    066
亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球