美文网首页数据结构与算法
数算---线性表（一）

数算---线性表（一）

作者: Lcr111 | 来源:发表于2023-04-22 09:44 被阅读0次

前言

线性表包括顺序表和链表两种结构，顺序表类似于数组，链表是除了类似数组之外的还包括指针的概念，利用指针的指向来确定表的走向。本片文章我们将从顺序表和单向链表的实现及相关功能着手，学习线性表的特性，下篇文章我们会介绍剩余几种链表。(代码用的是C语言编写)

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

#include <stdio.h>
#include "stdlib.h"

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

//元素类型假设为int
typedef int ElemType;
//函数返回类型 如上的状态码，OK 等
typedef int Status;

//顺序表结构数据元素
typedef struct {
    ElemType *data;
    int length;
}Sqlist;

//1.1 初始化
Status InitList(Sqlist *L){//如果内部需要修改L，带*，不修改可直接带L
    //分配一个大小为 MAXSIZE 的数组空间
    L->data = malloc(sizeof(ElemType)*MAXSIZE);
    if(!L->data) exit(ERROR);//存储分配失败就退出
    L->length = 0;
    return OK;
}

//1.2 插入数据
//i 第i个位置插入数据元素e,L长度加1
Status ListInsert(Sqlist *L, int i,ElemType e){
    //i 不合法
    if((i < 1) || (i > L->length + 1)) return ERROR;
    //存储已满
    if(L->length == MAXSIZE) return ERROR;
    
    //插入位置不在表尾，则先移动出空余位置,就是将第i位置及后面的都往后移动一个位置
    if(i <= L->length) {
        for (int j = L->length - 1; j >= i - 1; j --) {
            L->data[j + 1] = L->data[j];
        }
    }
    //第i个位置插入
    L->data[i - 1] = e;
    ++L->length;
    return OK;
}

//1.3 取值
//*e 为装载取到的值,供外界使用
Status GetElem(Sqlist L,int i,ElemType *e){
    //i 不合法
    if((i < 1) || (i > L.length)) return ERROR;
    *e = L.data[i - 1];
    return OK;
}

//1.4 删除元素
Status listDelete(Sqlist *L, int i){
    if(L->length == 0) return ERROR;
    
    if(i < 1 || i > L->length) return  ERROR;
    
    for (int j = i; j < L->length; j ++) {
        L->data[j - 1] = L->data[j];
    }
    L->length--;
    return OK;
}

//1.5 清空
Status CLearList(Sqlist *L){
    L->length = 0;
    return OK;
}

//1.6 是否为空
Status ListEmpty(Sqlist L){
    if(L.length == 0){
        return TRUE;
    }else{
        return FALSE;
    }
}

//1.7 长度
int ListLength(Sqlist L){
    return  L.length;
}

//1.8 遍历
Status PrintList(Sqlist L){
    int i;
    for (i = 0; i < L.length; i ++) {
        printf("%d\n",L.data[i]);
    }
    printf("\n");
    return OK;
}

//1.9 寻找下标
int LocateElem(Sqlist L, ElemType e){
    int i;
    if(L.length == 0) return 0;
    
    for (i = 0; i < L.length; i ++) {
        if(L.data[i] == e)
            break;
    } 
    if(i >= L.length) return 0;
    return i + 1;
}

int main(int argc, const char * argv[]) {
    Sqlist L;
    Status iStatus;
    
    iStatus = InitList(&L);
    printf("初始化L后: L.Length = %d\n", L.length);
    
    for(int j=1; j <= 5;j++){
        iStatus = ListInsert(&L, 1, j);
    }
    printf("插入数据L长度: %d\n",L.length);
    PrintList(L);
    return 0;
}

需要注意的是插入和删除时length长度需要做相应的加1减1操作。其余数据需要移动位置。

单向链表

单向链表是由若干个结点组成的链表结构，每个结点分数据域和指针域，数据域存放实际数据，指针域存放下个结点的地址。

结点

链表第一个实际装有数据的结点称为首元结点，首指针指向此结点，如果需要使用到头结点，我们会给它加上一个头结点，头指针指向头结点，头结点数据域可以写有实际意思的数据，也可以置空，指针域存放首元结点的地址。日常开发中我们更倾向于加上头结点，原因如下：
1.便于首元结点的操作处理。
2.便于空表和非空表的统一处理。

单向链表（无头结点） 空链表 非空链表
准备工作
#include <stdio.h>
#include "stdlib.h"

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int ElemType;

//定义结点
typedef struct Node{
    ElemType data;//数据域
    struct Node *next;//指针域
}Node;

typedef struct Node *LinkList;
初始化

此处我们添加了头结点，初始化时候为空表，只有一个头结点，所以next->NULL。

//1.1 初始化
Status InitList(LinkList *L) {
    //头结点
    *L = (LinkList)malloc(sizeof(Node));
    if(*L == NULL) return ERROR;
    //将头节点的指针域置空
    (*L)->next = NULL;
    
    return OK;
}
插入数据

假设需要在两个数据元素a和b之间插入一个数据元素x，即打破a和b之间的关系，需求a->next = x,x->next = b，需要注意的是要先将x->next指向b,然后再a->next指向x,如果顺序反了的话，b会被释放掉。

单链表插入 
Status ListInsert(LinkList *L, int i, ElemType e){
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    
    //寻找第i - 1个结点
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    
    if(!p || j > i) return ERROR;
    
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    
    return OK;
}
获取数据（取值）

获取第i个数据元素的值。那就找到第i - 1个结点的next结点。

Status GetElem(LinkList L, int i, ElemType *e){
    int j;
    
    LinkList p;
    //将结点p 指向链表L的第一个结点;
    p = L->next;
    j = 1;
    
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    if(!p || j > i) return ERROR;
    *e = p->data;
    return OK;
}
数据删除

删除结点操作就是插入操作的逆序，假设a->b->c，需要将b删除，那么就需要将a->next = c就行了。注意要释放b的内存。

单链表删除 
//删除第i个位置，即找到前一个和后一个，将它们连上关系
Status ListDelete(LinkList *L,int i, ElemType *e){
    int j;
    LinkList p,q;
    p = (*L)->next;
    j = 1;
    
    while (p->next && j < (i - 1)) {
        p = p->next;
        ++j;//最终 j = i - 1
    }
    //此时找到第i-1个数据,即要删除的前一个结点，需要用到它的next
    
    //此时p->next就是需要删除的第i个数据元素
    //此时j = i - 1
    if (!(p->next) || (j > i - 1)) return  ERROR;
    
    //q指向要删除的结点
    q = p->next;
    //将q的后继赋值给p的后继
    p->next = q->next;
    //获取q中的数据给e
    *e = q->data;
    //释放内存
    free(q);
    
    return OK;
}
遍历链表

顺序表可根据下标遍历，链表可根据结点的指针域next遍历。

Status ListPrint(LinkList L){
    LinkList p = L->next;
    while (p) {
        printf("%d\n",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}
链表清空

注意清空时候需要释放开辟的内存。

Status ClearList(LinkList *L){
    LinkList p,q;
    p = (*L)->next;
    while (p) {
        q = p->next;
        free(p);//从首元结点开始释放
        p = q;
    }
    (*L)->next = NULL;//头结点指针域置空
    return OK;
}
建立链表（头插法/尾插法）

建立一个带头结点的链表可以使用头插法和尾插法两种实现方式。

//头插法
void CreateListHead(LinkList *L, int n){
    LinkList p;
    //先建立带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    for (int i = 0; i < n; i ++) {
        p = (LinkList)malloc(sizeof(Node));
        p->data = i;
        //将头结点next给到p的next，空表是即NULL，非空时为首元结点
        p->next = (*L)->next;
        //将p插入为首元结点
        (*L)->next = p;
    }
}
//尾插法
void CreateListTail(LinkList *L,int n){
    LinkList p,r;
    
    *L = (LinkList)malloc(sizeof(Node));
    r = *L;//此时为头结点
    
    for (int i = 0; i < n ; i ++) {
        p = (Node *)malloc(sizeof(Node));
        p->data = i;
        
        r->next = p;//表尾指针指向新结点
        r = p;//依次为新加入结点，即尾结点
    }
    r->next = NULL;//最后尾结点next指向NULL
}
顺序表/单向链表对比

存储分配方式：

  • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。
  • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。

时间性能：

  • 查找数据
    • 顺序存储 O(1)
    • 单链表 O(n)
  • 插入和删除
    • 顺序存储结构需要平均移动一个表长一半的元素，时间为O(n)
    • 单链表查找某位置后的指针后，插入和删除，时间为O(1)

空间性能：

  • 顺序存储结构需要预先分配存储结构，分太大，浪费空间，分太小，发生溢出。
  • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

在实际开发中，视情况而定，那种存储方式方便用哪个，实际问题实际分析。

相关文章

  • iOS设计模式--迭代器

    学习迭代器之前，先看一种数据结构--线性表 线性表：线性表是最基本，最简单，也是最常用的一种数据结构。 线性表中数...

  • 线性表

    1）线性表是什么？2）线性表的特点是怎么样的？ 一、线性表是什么？线性表是一种最基本、最简单的、也是最基本的一种数...

  • 2019-06-10

    数据结构线性表自己高数中值定理

  • 数算

    2018新年伊始，求神指教我们怎样数算自己的年日: 假如一个人能活100年的话，每年365天，活36500天x24...

  • 数算

    只有一时 没有之间 不用数算 自有天地，恩情浩存，数算不尽。 十一月末 秋实静默 祝福满满 数算果实，荣归爱主，奇...

  • 数算

    主恩的滋味 你 尝过多少？ 甜 酸 苦 辣 咸 一种滋味 一种恩典 一种环境 一种祝福 尝尽生活百味 经历主恩万千...

  • 数算

    这一周应该是整理的一周 除了数算自己的物品 也开始数算自己的得失 把缺失的东西补上去 把需要打磨的东西拿出来 还有...

  • javascript实现链表

    一：线性表的定义 线性表是一种数结构；线性表有两种存储方式连续存储以及链表存储；其基本组成称为数据节点； 1：连续...

  • 几个概念

    1.东数西算 “东数西算”是把东部密集的算力需求有序引导到西部，使数据要素跨域流动。打通“数”动脉，织就全国算力一...

  • 数算恩典

    现在回头看走过的路，依然感谢神的恩典。疾病疼痛都是恩典的记号。他已经回应了我很多很多的梦想和祷告。我祷告很久...

网友评论

    本文标题：数算---线性表（一）

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

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    数据结构与算法

    关于我们|服务条款|联系我们|数算---线性表（一）|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！