---

title: 06-数据结构及算法-线性表
date: 2019-11-17 20:34:00
tags: 数据结构及算法

---

记录线性表相关知识

线性表的类型及定义

什么是线性表

线性表：一个线性表是n个数据特性相同的数据元素的有序序列。

在稍微复杂的线性表中，一个数据元素可以由多个数据项构成。
线性表中元素的个数n(n大于等于0)定义为线性表的长度，n=0时成为空表。
线性表是一个相当灵活的数据结构，可以根据需要增长或缩短。

对于非空的线性表或者线性结构的特点：

1. 第一个数据元素没有前驱，这个数据元素被称为开始节点。
2. 最后一个元素没有后继，这个元素被称为终端节点。
3. 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。

线性表的顺序表示及实现

顺序表的定义

• 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

顺序表的特点

• 用元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的相邻。
• 存储密度高，但要预先分配“足够应用”的存储空间，这可能会造成存储空间的浪费。
• 便于随机存储
• 插入删除操作繁琐

线性表的顺序存储

线性表的顺序存储结构

// 线性表的顺序存储结构
#include <iostream>
#include<stdio.h>
#include<stdlib.h>

#define Max 80
#define Increment 10
typedef struct
{
    int* elem;
    int length;
    int size;
}SqList;

线性表的初始化

// 线性表的初始化
// 为顺序表分配一个预定大小的数组空间，并将顺序表的长度设为0
void InitList(SqList& L) 
{
    L.elem = (int*)malloc(Max * sizeof(int));
    if (!L.elem) {
        printf("存储空间分配失败！");
        return;
    }
    L.length = 0; //空表长度为0
    L.size = Max; //初始存储容量
    printf("初始化成功");
}

获取指定位置元素

// 获取元素
// 将线性表中的第i个位置元素值返回
int GetElem(SqList& L, int i, int *e)
{
    if (i<1 || i>L.length) {
        printf("位置信息错误");
        return 0;
    }
    *e = L.elem[i-1];
    printf("获取成功");
    return 1;
}

线性表的插入操作

// 插入元素
// 在指定位置插入元素
int ListInsert(SqList& L, int i,int e)
{
    int* _new;
    if (i<1 || i>L.length)
    {
        printf("插入位置不合法！\n");
        return -1;
    }
    if (L.length >= L.size)
    {
        _new = (int*)realloc(L.elem,(L.length + Increment) * sizeof(int));
        if (!_new)exit(0);
        L.elem = _new;
        L.size += Increment;
    }
    for (int k = L.length - 1; k >= i - 1; k--)
    {
        L.elem[k + 1] = L.elem[k];
    }
    L.elem[i - 1] = e;
    L.length++;
}

顺序存储结构的优缺点

优点：

• 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素

缺点：

• 插入和删除需要移动大量元素
• 线性表长度变化较大时，不容易确定存储空间的容量
• 造成存储空间的“碎片”

线性表的链式存储

顺序存储中，插入和删除时需要移动大量元素，这会耗费大量的时间，导致这些问题的原因是相邻两个元素的存储位置也相邻，中间没有空隙。
为解决上述问题，我们不再考虑相邻元素存储位置的相邻关系，只要做到让当前位置的元素知道下一个元素的位置即可。

线性表的链式存储：

链式存储示意.png

为了表示每个数据与其后继元素之间的逻辑关系，数据元素除了存储本身的信息外，还需要存储其直接后继的信息。
这两部分信息组成数据元素a的存储映像，称为结点；它包含两个域：其中存储数据元素信息的称为数据域；存储直接后继存储位置的域称为指针域，指针域中存储的信息称作指针或链。

注意：

1. 整个链表的存取必须从头指针开始进行。
2. 最后一个元素没有直接后继，则线性链表中最后一个结点的指针为“空”(NULL);

线性表的链式存储结构

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

#define OK 1
#define ERROR 0
typedef struct LNode {
    int data;
    struct LNode* next;
}LNode,*LinkList;

未完待续。。。。。