当前位置： 首页 > article >正文

趣说数据结构 —— 2.线性表中的顺序表与单链表

article 2024/11/20 11:50:38

2.1 线性表的定义和特点

定义 由 n ( n ≥ 0 n (n \ge 0 n(n≥0) 个数据 特性相同 的元素构成的 有限序列 称为 线性表。

特点 对于 非空 的线性表或线性结构，其特点包括：

  • 存在唯一的一个被称作 “第一个” 的数据元素；
  • 存在唯一的一个被称作 “最后一个” 的数据元素；
  • 除第一个之外， 结构中的每个数据元素均只有一个前驱；
  • 除最后一个之外， 结构中的每个数据元素均只有一个后继。

2.2 线性表的例子

小伙伴们读书的时候（尤其是读大学的时候）有没有被 “花名册” 支配的恐惧呢 ？如果某堂课老师特意带了花名册了，那么极有可能会点名达到或者是点名叫人回答问题。

花名册就是很好的一个线性表的例子，我们一般会以学号进行排序，考试的时候也常常根据学号排座位进行考试。这种按照学号的顺序就是我们这里提到的线性表中的顺序，并且每个学号也满足前面提到的 4 个特点。

序号姓名
01光头强
02熊大
03熊二
04吉吉
05蹦蹦
……

2.3 线性表的顺序存储

线性表的顺序存储指的是用一组 地址连续 的存储单元 依次存储 线性表的数据元素。通常， 称这种存储结构的线性表为顺序表（Sequenitial List）。

主要特点：逻辑上相邻的数据元素， 其物理次序也是相邻的。

这里我们联想一下考试场景，学号相邻的一般考试座位也会相邻（如果按照学号排序并且未打乱的话）。这里的学号相邻可以理解为 “逻辑上的相邻”，而考试的时候座位的相邻可以理解为 “存储上的相邻”。当然为了排除例外，我们可以把考号替换成为考场中的座位号。

回到我们的计算机应用场景中，一般情况下我们用 “数组” 来存储这种顺序结构，比如我们定义一个数组：

int[] arr = {1, 2, 3, 4, 5, 6}

那么这个数组在真实的存储空间中也是相邻的。

接下来我们以 班级花名册 为例。

2.3.1 结构体

注意这个地方不同的语言可能表示方法不同，比如 c++ / java / python / c# 等都会使用 类 来表示，这里我们使用 C 的方法来定义。

#include <iostream>
#include <string>
#define MAXSIZE 100
using namespace std;

/**
 * 分别表示学生姓名，成绩
 */
typedef struct {
    string name;
    double score;
} ElemType;

/**
 * 表示班级所有人的名字和成绩
 */
typedef struct {
    ElemType* elem;
    int length;
} SqList;

2.3.2 初始化

/**
 * 初始化成绩单，空成绩单，还没有加入姓名和成绩
 */
void InitList(SqList& L) {
    L.elem = new ElemType[MAXSIZE];
    L.length = 0;
}

2.3.3 写数

/**
 * 插入元素到顺序表的尾巴
 */
void AddItem(SqList& L, string name, double score) {
    L.elem[L.length].name = name;
    L.elem[L.length].score = score;
    L.length += 1;
}

2.3.3 取数

/**
 * 根据索引找到对应的元素
 */
ElemType GetElemByIndex(SqList L, int index) {
    return L.elem[index];
}

2.3.4 查找

/**
 * 根据名称查找
 */
ElemType GetElemByName(SqList L, const string& name) {
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i].name == name) {
            return L.elem[i];
        }
    }
    // 如果没有找到，返回一个空
    ElemType noneType;
    noneType.name = "missing";
    noneType.score = -1.0;
    return noneType;
}

2.3.5 插入

/**
 * 插入某元素到某个位置
 */
void InsertElem(SqList& L, const string& name, const double score, int index) {
    for (int i = L.length - 1; i >= index ; i--) {
        L.elem[i + 1].name = L.elem[i].name;
        L.elem[i + 1].score = L.elem[i].score;
    }
    L.elem[index].name = name;
    L.elem[index].score = score;
    L.length += 1;
}

2.3.6 删除

/**
 * 删除索引为 index 的元素
 */
void DropItem(SqList& L, const int index) {
    for (int i = L.length; i > index; i--) {
        L.elem[i - 1].name = L.elem[i].name;
        L.elem[i - 1].score = L.elem[i].score;
    }
    L.length -= 1;
}

2.3.7 源码汇总

//
// Created by smileyan on 2023/4/28.
//
#include <iostream>
#include <string>
#define MAXSIZE 100
using namespace std;

/**
 * 分别表示学生姓名，成绩
 */
typedef struct {
    string name;
    double score;
} ElemType;

/**
 * 表示班级所有人的名字和成绩
 */
typedef struct {
    ElemType* elem;
    int length;
} SqList;


/**
 * 初始化成绩单，空成绩单，还没有加入姓名和成绩
 */
void InitList(SqList& L) {
    L.elem = new ElemType[MAXSIZE];
    L.length = 0;
}

/**
 * 插入元素到顺序表的尾巴
 */
void AddItem(SqList& L, string name, double score) {
    L.elem[L.length].name = name;
    L.elem[L.length].score = score;
    L.length += 1;
}

/**
 * 根据索引找到对应的元素
 */
ElemType GetElemByIndex(SqList L, int index) {
    return L.elem[index];
}

/**
 * 根据名称查找
 */
ElemType GetElemByName(SqList L, const string& name) {
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i].name == name) {
            return L.elem[i];
        }
    }
    // 如果没有找到，返回一个空
    ElemType noneType;
    noneType.name = "missing";
    noneType.score = -1.0;
    return noneType;
}

/**
 * 插入某元素到某个位置
 */
void InsertElem(SqList& L, const string& name, const double score, int index) {
    for (int i = L.length - 1; i >= index ; i--) {
        L.elem[i + 1].name = L.elem[i].name;
        L.elem[i + 1].score = L.elem[i].score;
    }
    L.elem[index].name = name;
    L.elem[index].score = score;
    L.length += 1;
}



/**
 * 删除索引为 index 的元素
 */
void DropItem(SqList& L, const int index) {
    for (int i = L.length; i > index; i--) {
        L.elem[i - 1].name = L.elem[i].name;
        L.elem[i - 1].score = L.elem[i].score;
    }
    L.length -= 1;
}



int main() {
    SqList L;
    InitList(L);
    cout<<L.length<<endl;
    AddItem(L, "小明", 89.0);
    cout<<L.length<<endl;
    InsertElem(L, "小朱", 93.0, 0);
    cout<<GetElemByIndex(L, 0).name<<endl;
    DropItem(L, 0);
    cout<<GetElemByName(L, "小明").name<<endl;
    return 0;
}

2.4 线性表的链式存储

链式存储同样包括以下几个过程，这里就不重复介绍了，总体而言代码如下：

//
// Created by smileyan on 2023/4/28.
//
#include <iostream>
#include <string>
#define MAXSIZE 100
using namespace std;

/**
 * 分别表示学生姓名，成绩
 */
typedef struct {
    string name;
    double score;
} ElemType;

typedef struct LNode {
    ElemType data;
    struct LNode* next;
}LNode, *LinkedList;

void InitLinkedList(LinkedList& L) {
    L = new LNode();
    L -> next = nullptr;
}

void AddItem(LinkedList& L, const string& name, double score) {
    LNode* next = new LNode();
    LNode* p = L;
    next->data.name = name;
    next->data.score = score;
    next->next = nullptr;

    while (p != nullptr && p -> next != nullptr) {
        p = p -> next;
    }

    p -> next = next;
}

/**
 * 根据索引找到对应的元素
 */
ElemType GetElemByIndex(LinkedList& L, int index) {
    LNode* p = L -> next;
    for (int i = 0; i < index; i++) {
        p = p -> next;
    }
    ElemType result;
    result.score = p -> data.score;
    result.name = p -> data.name;
    return result;
}

/**
 * 根据名称查找
 */
ElemType GetElemByName(LinkedList& L, const string& name) {
    LNode* p = L->next;
    ElemType result;
    while (p != nullptr) {
        if (p -> data.name == name) {
            result = p -> data;
            return result;
        }
        p = p->next;
    }
    // 如果没有找到，返回一个空
    result.name = "missing";
    result.score = -1.0;
    return result;
}

/**
 * 删除索引为 index 的元素
 */
void DropItem(LinkedList & L, const int index) {
    LNode* p = L -> next;
    for (int i = 0; i < index - 1; i++) {
        p = p -> next;
    }
    LNode* q = p -> next;
    p -> next = p -> next -> next;
    delete q;
}

/**
 * 插入某元素到某个位置
 */
void InsertElem(LinkedList& L, const string& name, const double score, int index) {
    LNode* p = L -> next;
    LNode* q = new LNode();
    for (int i = 0; i < index - 1; i++) {
        p = p -> next;
    }
    q -> data.name = name;
    q -> data.score = score;
    q -> next = p -> next;
    p -> next = q;
}

void printLink(LinkedList L) {
    LNode* p = L -> next;
    while (p != nullptr) {
        cout << p -> data.name << " : " << p -> data.score << endl;
        p = p -> next;
    }
    cout << endl;
}


int main() {
    LinkedList L;
    InitLinkedList(L);
    AddItem(L, "小明", 89.0);
    AddItem(L, "小朱", 93.0);

    printLink(L);

    ElemType e = GetElemByIndex(L, 0);
    cout<<e.name << " : " << e.score <<endl<<endl;

    ElemType e2 = GetElemByName(L, "小朱");
    cout << e2.name << " : " << e2.score <<endl<<endl;

    ElemType e3 = GetElemByName(L, "小刘");
    cout << e3.name << " : " << e3.score <<endl<<endl;

    InsertElem(L, "小刘", 97.0, 1);
    printLink(L);

    DropItem(L, 1);
    printLink(L);

    DropItem(L, 1);
    printLink(L);

    return 0;
}

2.5 时间复杂度与空间复杂度分析总结

期末考、面试的时候常用

顺序表单链表
存储空间预先分配，会导致空间闲置或溢出现象动态分配，不会出现存储空间闲置或溢出现象
存储密度不用为表示结点间的逻辑关系而增加额外
的存储开销，存储密度等于1		需要借助指针来体现元素间的逻辑关系，
存储密度小于
存取数据随机存取，按位置访问元素的时间复杂度为O(1)顺序存取，按位置访问元素时间复杂度为O(n)
插入删除平均移动约表中一半元素，时间复杂度为O(n)不需移动元素，确定插入、删除位置后，时间复杂度为 O(1)
适用情况1. 表长变化不大，且能事先确定变化的范围
2. 很少进行插入或删除操作，经常按元素
位置序号访问数据元素		1. 长度变化较大
2. 频繁进行插入或删除操作

2.6 总结

本节主要回顾线性表中的顺序表与单链表，包括基本特点，代码实现，时间复杂度与空间复杂度分析等，这些都是非常基础的内容，计划在下个章节介绍循环链表与双链表，并将单链表、循环链表与单列表进行比较。

复制粘贴到在线编码环境（非广告，无需登录）
https://wandbox.org/
https://www.tutorialspoint.com/compile_cpp_online.php

Smileyan
2023.04.29 08:59


http://www.kler.cn/a/15184.html

相关文章：

  • 如何解决多系统数据重复与冲突问题？
  • 智慧安防丨以科技之力，筑起防范人贩的铜墙铁壁
  • 【含开题报告+文档+PPT+源码】基于springboot的教师评价系统的设计与实现
  • DNS with libevent
  • 2411rust,1.80
  • Kotlin return与return@forEachIndexed
  • 第3章：select
  • 山东大学2023操作系统实验2
  • 神经网络模型入门及蠓虫分类问题简单实战
  • 分类和扩展与继承
  • Python基于Pytorch Transformer实现对iris鸢尾花的分类预测，分别使用CPU和GPU训练
  • 无HMI和PLC设备时，模拟程序收发是否正常
  • MobileNetV3详细原理（含torch源码）
  • Hytrix原理
  • ​工程师如何对待开源
  • 【keil5开发ARM工程时使用STLink调试的技巧分享】
  • 数据结构之KMP算法：彻底搞懂kmp算法
  • Ajax XHR请求
  • c++元编程
  • Maven 如何下载依赖包的源码包
  • 2023年第二十届五一数学建模竞赛题目 C题详细思路
  • [最小距离的最大值] 跳石头
  • node(express框架)连接mysql 基础篇
  • 数据结构——求二叉树的属性
  • 制造策略 ETO、MTO、ATO、MTS
  • 09 【Sass语法介绍-函数指令】