博客

数据结构——线性结构（线性表）

  • Post author:
  • Post category:其他


文章目录



一. 线性结构概述



1. 线性结构（线性表的逻辑结构)的定义

  • 定义：把所有的结点用一根直线穿起来
  • 详细定义：线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，n=0是一个空表。
  • 用L表示线性表：L=(a1,a2,…,ai,ai+1,…,an)。a1是唯一的第一个数据元素，又称表头元素；an是唯一的最后一个元素，又叫表尾元素。
  • 除了第一个元素之外，每个元素有且仅有一个直接前驱。除了最后一个元素外，每个元素有且仅有一个直接后继。

    在这里插入图片描述



2. 线性表的特点

  • 线性结构的特点：在数据元素的非空有限集中 

      1. 存在惟一的一个被称做“第一个”的数据元素
  2. 存在惟一的一个被称做“最后一个”的数据元素
  3. 除第一个之外，集合中的每个数据元素均只有一个前驱
  4. 除最后一个之外，集合中每个数据元素均只有一个后继

  • 线性表(linear_list)

    定义：是n个数据元素的有限序列

    特点： 

    线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特性，即属于同一数据对象（占有相同的大小）
相邻数据元素之间存在着序偶关系，元素有其先后次序
线性表的长度可以根据需要增长或缩短

  • 抽象数据类型线性表的定义




线性结构/线性表是一种逻辑结构，而顺序存储/顺序表以及链式存储/链表则是一种存储结构



二. 线性结构分类



1. 连续存储[顺序表]


线性表的顺序存储结构是一种随机存取的存储结构。

通常我们用高级设计语言中的数组来描述线性表的顺序结构

所以下面我都是用C语言中的数组来表示线性结构中的顺序表



(1). 什么叫数组

元素类型相同，大小相同



(2). 顺序表算法的基本操作


顺序表算法代码https://github.com/zhiqiang99/DataStructure/blob/master/Arr.cpp

注意以下几点：

  • 初始化动态分配数组

    在这里插入图片描述

  • 在合适位置插入元素

    在这里插入图片描述

  • 在合适位置删除元素

    在这里插入图片描述

  • 倒置元素的时候

    注意while循环里面的 i<j，适用与个数为奇数和偶数的情况

    要熟记交换变量内容的三个语句：t = a; a = b; b = t;

  • 排序元素

    没有固定方法，排序的十几种方法都可以使用



(3). 顺序表(物理结构)

  • 定义：

    用一组地址连续的存储单元依次存储线性表的数据元素

  • 特点：

    在这里插入图片描述

  • 顺序表表中元素的逻辑顺序与物理顺序相同

  • 只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构

  • 线性表的顺序存储结构示意图

    在这里插入图片描述

  • 数组类型也有随机存取的特性，

    通常用数组来描述数据结构中的顺序存储结构
     

      线性表的长度可变，则在C语言中可用动态分配的一维数组

  • 顺序表的优缺点


    优点

    ：

    顺序表存储结构容易实现随机存取线性表的第i个数据元素的操作

    无需为表示表中元素之间的逻辑关系而增加额外的存储空间


    缺点

    ：

    实现插入或删除操作时要移动大量数据元素

    当线性表长度变化较大时，难以确定存储空间的容量

    容易造成存储空间的碎片

  • 顺序表的时间复杂度

    若表长为n，算法ListInsert_Sq和ListDelete_Sq的时间复杂度为O（n）

    求表长和取第i个数据元素的时间复杂度O（1）

    算法LocalElem_Sq的时间复杂度为O（L.length）

  • 线性表的动态分配顺序存储结构

    静态分配数组大小和空间事前固定了，空间满了之后再添加就会溢出，一般我们都是采用动态分配 

    //------线性表的动态分配顺序存储结构---------
 
#define LIST_INIT_SIZE 100	//线性表存储空间的初始分配了 
#define LISTINCREMENT 10 	//线性表存储空间的分配增量
struct Sqlist
{
	ElemType *elem;		//存储空间基址	 
	int length;			//当前长度（数组有效元素个数） 
	int listsize;		//当前分配的存储容量 （以sizeof(ElemType)为单位） 
	int incrementsize	//增补空间
};

    在这里插入图片描述

  • 检验顺序表中各个基本操作函数是否正确


    顺序表的操作，C语言详细代码：https://github.com/zhiqiang99/DataStructure/blob/master

  1. 图示：定义两个数据元素（2,6）、12个存储空间的顺序表

    在这里插入图片描述
  2. 图示：初始化构造一个空的顺序线性表L

    在这里插入图片描述
  3. 图示：销毁顺序线性表L

    在这里插入图片描述
  4. 图示：在顺序表中插入元素

    在这里插入图片描述
  5. 图示：在顺序表中删除元素

    在这里插入图片描述
  6. 图示：归并顺序表La和顺序表Lb得到一个新的顺序表Lc

    在这里插入图片描述



2. 离散存储[链表]



(1). 定义

  • n个节点离散分配
  • 彼此通过指针相连
  • 每个节点只有一个前驱节点，每个节点只有一个后续节点
  • 首节点没有前驱节点，尾节点没有后续节点



1. 专业术语

  • 首节点：第一个有效节点

  • 尾节点：最后一个有效节点


  • 头结点：第一个有效节点之前的那个节点
     

    头节点并不存放有效节点
加一个没有实际含义的头结点的目的主要为了方便对链表的操作
头结点的数据类型和首节点类型一样

  • 头指针：指向头结点的指针变量，指示链表中第一个节点的存储位置

  • 尾指针：指向尾结点的指针变量

在这里插入图片描述



2. 确定一个链表需要几个参数

如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的哪些参数：


  • 只需要一个参数：头指针
  • 因为我们通过头指针可以推出链表的其他所有信息



3. 每一个链表节点的数据类型如何表示

在这里插入图片描述 

每个节点数据类型：

typedef struct Node
{
	int data;  //数据域
	struct Node * pNext; //指针域
}NODE, *PNODE

---------------------------
NODE等价于struct Node类型
PNODE等价于struct Node * 类型



(2). 分类

在这里插入图片描述



1. 单链表

定义

  • 通过一组任意的存储单元来存储线性表中的数据元素

单链表单个节点结构

在这里插入图片描述 

typedef struct Node
{
	int data;  //数据域
	struct Node * pNext; //指针域
}NODE, *PNODE

NODE等价于struct Node类型
PNODE等价于struct Node * 类型

优点：

  • 不需要大量连续存储单元

缺点：

  • 附加指针域，浪费空间
  • 非随机存取的存储结构

带头结点的单链表

在这里插入图片描述

  • 带头结点的好处 

    1. 第一个数据节点的操作和其他位置上操作相同，无需进行特殊处理
2. 无论链表是否为空，其头指针都指向头结点的非空指针



单链表上基本算法操作的实现：



https://gitee.com/zhiqiang99/data-structure/blob/master/List/LinkList/list.cpp

  1. 采用头插法建立单链表

    在这里插入图片描述 

    核心代码:

s->next = L->next; //s指向结构体变量中的next这个成员（这个next成员为结构体型指针变量，它指向了头指针L所指向结构体变量中的next成员所指的结构体）
//可以这么理解：s的next指向L的next所指的节点
L->next = s; //将新结点插入表中，L为头指针

  2. 采用尾插法建立单链表

    在这里插入图片描述 

    核心代码：

r->next=s;
r=s; //r指向新的表尾结点

  3. 按序号查找结点值

  4. 按值查找表结点

  5. 插入结点操作

    在这里插入图片描述 

    核心代码：

p=GetElem (L, i-1) ; //査找插入位置的前驱结点
s->next=p->next; 	//图 2.7中操作步骤 1
p->next=s; 			//图 2.7中操作步骤2

  6. 删除结点操作

    在这里插入图片描述 

    核心代码：

p=GetElem(L,i-1); //查找删除位置的前驱结点
q=p->next;		//令q指向被删除结点    =:表示指向的意思，指向的是这个节点的整体
p->next=q->next	//将*q结点从链中“断开”
free(q);	//释放结点的存储空间①

  7. 求表长操作



2. 双链表

定义

  • 每个节点都有两个指针域，分别指向其前驱节点和后继节点

    在这里插入图片描述

  • 与单链表的算法区别 

      按值查找和按位查找与单链表相同
  插入和删除操作不同



双链表上基本算法操作的实现



加代码

  1. 双链表的插入操作

    在这里插入图片描述 

    核心代码：语句不唯一，1、2必须在4之前

s->next=p->next; //将结点*s插入到结点*p之后
p->next->prior=s;
s->prior=p;
p->next=s;

  2. 双链表的删徐操作

    在这里插入图片描述 

    核心代码：

p->next=q->next;
q->next->prior=p;
free(q);	//释放结点空间



3. 循环链表

能通过任何一个节点找到其他所有的节点

在这里插入图片描述

循环单链表的定义

  • 尾节点的指针域next指向头结点的单链表，形成一个环，即表中没有指针域为null的节点

在这里插入图片描述

循环单链表的算法操作

  • 判断是否为空 

      看头结点的指针是否指向它本身

  • 判断动态指针是否达到表尾节点 

      看p－>next是否指向其表头节点


加代码

循环双链表定义

  • 尾节点的指针域next指向头结点，且头结点的指针域prior指向尾节点的双链表

在这里插入图片描述

循环双链表的算法操作


加代码



4. 静态链表

定义

  • 借助数组来描述线性表的链式存储结构，节点也有数据域和指针域，但这里指针是节点的相对地址（数组下标），且也要预先分配一块连续的内存空间

在这里插入图片描述

静态链表数据结构的描述 

#define MaxSize 50
typedef struct{
	ElemType data;
	int next;
}SLinkList[MaxSize];

静态链表的优缺点：

  • 优点：线性表的插入和删除不需要移动元素，仅修改指针
  • 缺点：需预先分配一个较大的空间，进行空间扩充比较困难

静态链表的算法操作


加代码



3. 顺序表和链表的比较

在这里插入图片描述



(1). 顺序表



1. 优点

  • 可以随机存取，存取速度很快

  • 存储密度＝1 

      存储密度＝（节点数据本身所占的存储量）/（节点结构所占的存储总量）



2. 缺点

  • 插入删除需要移动大量元素很慢
  • 事先必须知道长度
  • 存储空间不便于扩充



(2). 链表



1. 优点

  • 空间没有限制
  • 插入删除元素很快



2. 缺点

  • 只能顺序存取，存取速度很慢
  • 需要额外空间（指针域）来表示数据元素之间的逻辑结构
  • 存储密度<1



三. 数据结构和算法



1. 算法种类

  • 遍历
  • 查找
  • 清空
  • 销毁
  • 求长度
  • 排序
  • 删除节点
  • 插入节点



2. 什么是数据结构



(1). 狭义


数据结构是专门研究数据存储的问题


数据结构包含两个方面：个体的存储+个体关系的存储

  • 从某种角度而言：数据的存储最核心的就是个体关系的存储，个体的存储可以忽略不计



(2). 广义


数据结构既包含数据的存储也包含数据的操作



3. 什么算法



(1). 狭义

  • 算法是对存储数据的操作
  • 算法和数据的存储方式密切相关



(2). 广义

算法和数据存储方式无关


这就是泛型


  • 泛型就是利用某种技术达到的效果就是i：不同的存储方式，执行的操作是一样的

  • 再次讨论到底什么是泛型：同一逻辑结构，无论该逻辑结构物理存储是什么样子的，我们可以对它执行相同的操作



4. 学习算法的方法

理解底层数学逻辑

怎么理解？

  • 抓住流程
  • 理解每个语句功能
  • 试数


版权声明：本文为qq_44853882原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。