数据结构学习之——线性表

news/2024/12/29 23:23:21/

1、线性表的定义和基本操作

1.1、线性表的定义

线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若以L命名，则表示为
L = ( a 1 , a 2 , , ⋯ , a i , a i + 1 , ⋯ , a n ) L=\left(a_{1}, a_{2,},\cdots, a_{i}, a_{i+1}, \cdots, a_{n}\right) L=(a1​,a2,​,⋯,ai​,ai+1​,⋯,an​)
a 1 a_{1} a1​是唯一的“第一个”元素，又称表头元素； a n a_{n} an​是唯一的“最后一个”元素，又称表尾元素除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。

线性表的特性：

  • 表中元素的个数有限。
  • 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
  • 表中元素都是数据元素，每个元素都是单个元素。
  • 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
  • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。根据存储结构的不同可分为顺序表和链表。

1.2、线性表的基本操作

  • InitList(&L):初始化表。构造一个空的线性表。
  • Length (L)：求表长。返回线性表L的长度，即L中数据元素的个数。
  • LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
  • GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
  • Listinsert (&L, i, e)：插入操作。在表L中的第i个位置上插入指定元素e。
  • ListDelete (&L, i, &e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
  • PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
  • Empty (L):判空操作。若L为空表，则返回true,否则返回false。
  • DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

2、线性表的顺序表示

2.1、顺序表的定义

定义：线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

位序：第1个元素存储在线性表的起始位置,第i个元素的存储位置后面紧接着存储的是第i+1个元素，称i为元素 a i a_{i} ai​在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

线性表的顺序存储如下所示：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5yu7FLsk-1685022761721)(./2_1.png)]

随机存储：每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数，因此，顺序表中的任意一个数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。

内存分配方式：一维数组的内存分配方式有静态分配和动态分配。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。 而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。

特点：

  • 顺序表最主要的特点是随机访问,即通过首地址和元素序号可在时间0(1)内找到指定的元素。
  • 顺序表的存储密度高，每个结点只存储数据元素。
  • 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

2.2、顺序表基本操作实现

#define InitSize 50                             //定义线性表的最大长度
typedef struct {int *data;                                  //指示动态分配数组的指针int length;                                 //数组的当前个数
}List;void InitList(List &list) {                     //初始化表。构造一个空的线性表。list.data = new int[InitSize];              //初始动态内存分配list.length = 0;                            //初始当前长度
}int Length(List list) {                         //求表长。返回线性表L的长度，即L中数据元素的个数。return list.length;                         //获取当前长度
}int LocateElem(List list, int e) {              //按值查找操作。在表L中查找具有给定关键字值的元素。for (int i = 0; i < list.length; i++) { if (list.data[i] == e) return i + 1;    //查找成功，返回位序}return 0;                                   //查找失败，返回0
}int GetElem(List list, int i) {                 //按位查找操作。获取表L中第i个位置的元素的值。return list.data[i - 1];
}bool ListInsert(List& list, int i, int e) {     //插入操作。在表L中的第i个位置上插入指定元素e。if (i<1 || i>list.length + 1) return false; //判断i的范围是否有效if (list.length >= InitSize) return false;  //当前存储空间己满，不能插入for (int j = list.length; j >= i; j--)      //将第i个元素及之后的元素后移list.data[j] = list.data[j - 1];list.data[i - 1] = e;                       //在位置i处放入elist.length++;                              //线性表长度加1return true;
}bool ListDelete(List& list, int i, int& e) {    //删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。if (i<1 || i>list.length) return false;     //判断i的范围是否有效e = list.data[i - 1];                       //将被删除的元素赋值给efor (int j = i; j < list.length; j++)       //将第i个位置后的元素前移list.data[j - 1] = list.data[j];list.length--;                              //线性表长度减1return true;
}void PrintList(List list) {                     //输出操作。按前后顺序输出线性表L的所有元素值。for (int i = 0; i < list.length; i++) {     //循环输出线性表元素值cout << list.data[i] << " ";}cout << endl;
}bool Empty(List list) {                         //判空操作。若L为空表，则返回true,否则返回false。return list.length == 0;
}void DestroyList(List& list) {                  //销毁操作。销毁线性表，并释放线性表L所占用的内存空间。free(list.data);list.length = 0;
}

时间复杂度：

  • 按值查找（顺序查找）： O ( n ) O(n) O(n)
  • 按位查找： O ( 1 ) O(1) O(1)
  • 插入操作： O ( n ) O(n) O(n)
  • 删除操作： O ( n ) O(n) O(n)

3、线性表的链式表示

3.1、单链表的定义

定义：线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。

优缺点：利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

表示方式：通常用头指针来标识一个单链表，如单链表Z，头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。

头结点和头指针的区分:不管带不带头结点，头指针都始终指向链表的第一个结点，而头结
点是带头结点的链表中的第一个结点，结点内通常不存储信息。

3.2、单链表基本操作的实现（带头节点）

typedef struct LNode {                      //定义单链表节点类型int data;                               //数据域struct LNode* next;                     //指针域
}*LinkList;LinkList List_HeadInsert(LinkList& L) {     //头插法LNode* s;int x;L = (LinkList)malloc(sizeof(LNode));    //创建头节点L->next = NULL;                         //初始为空链表cin >> x;                               //输入结点的值while (x != 9999) {s = (LinkList)malloc(sizeof(LNode));//创建新结点s->data = x;s->next = L->next;L->next = s;                        //将新节点插入表中，L为头指针cin >> x;}return L;
}LinkList List_TailInsert(LinkList& L) {    //尾插法int x;L = (LinkList)malloc(sizeof(LNode));LNode* s, * r = L;                     //r为表尾指针cin >> x;while (x != 9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;r->next = s;                       //r指向新的表尾结点r = s;cin >> x;}r->next = NULL;                        //尾结点指针置空return L;
}LNode* GetElem(LinkList L, int i) {        //单链表按序号查找节点if (i < 1) return NULL;                //若i无效，则返回NULLint j = 1;                             //计数，初始为1LNode* p = L->next;                    //第1个结点指针赋给pwhile (p != NULL && j < i) {           //从第一个结点开始找，查找第i个结点p = p->next;j++;}return p;                              //返回第i个结点的指针，若i大于表长，则返回NULL
}LNode* LocateElem(LinkList L, int e) {     //按值查找表结点LNode* p = L->next;while (p != NULL && p->data != e)      //从第1个结点开始查找data为e的结点p = p->next;return p;                              //找到返回结点指针，否则返回NULL
}bool ListInsert(LinkList L, int i, int e) {//插入操作，在第i个位置插入data为e的结点LNode* p = GetElem(L, i);              //查找到第i个结点LNode* s;if (p == NULL) {p = GetElem(L, i - 1);             //不存在第i-1和i个结点if (p == NULL) return false;s->data = e;                       //最后一个结点是第i-1个结点，插入到尾端s->next = NULL;p->next = s;return true;}s = (LinkList)malloc(sizeof(LNode));   s->data = p->data;                     //使用前插法将元素插入到第i个结点s->next = p->next;p->data = e;p->next = s;return true;
}bool ListDelete(LinkList L, int i) {       //删除操作，删除第i个位置的结点LNode* p = GetElem(L, i);              //查找到第i个结点if (p == NULL) return false;LNode* s = p->next;p->data = s->data;                     //将p结点的后续结点的data复制到p结点的datap->next = s->next;                     //令p结点指向后续结点的后续结点free(s);                               //释放
}int Length(LinkList L) {                   //求表长。返回单链表表L的长度，即L中数据元素的个数。int l = 0;                             //初始化为0LNode* p = L->next;while (p != NULL) {                    //循环遍历单链表,计算表长l++;                               //长度加一p = p->next;}return l;                              //返回表长
}

时间复杂度：

  • 头插法： O ( n ) O(n) O(n)
  • 尾插法： O ( n ) O(n) O(n)
  • 按序号查找结点： O ( n ) O(n) O(n)
  • 按值查找结点： O ( n ) O(n) O(n)
  • 插入操作： O ( n ) O(n) O(n)
  • 删除操作： O ( n ) O(n) O(n)
  • 求表长操作： O ( n ) O(n) O(n)

3.3、双链表

双链表在单链表的结点中增加了一个指向其前驱的prior指针，因此双链表中的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。 这是因为"链”变化时也需要对prior指针做出修改，其关键是保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除操作的时间复杂度仅为0(1)。

注意：双链表的插入和删除要同时注意前驱和后驱指针的修改。

3.4、循环链表

循环单链表：循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL,而改为指向头结点，从而整个链表形成一个环，在循环单链表中，表尾结点r的next域指向L,故表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。

循环双链表：由循环单链表的定义不难推出循环双链表。不同的是在循环双链表中，头结点的prior指针还要指向表尾结点，在循环双链表L中，某结点p为尾结点时，p->next==L；当循环双链表为空表时，其头结点的prior域和next域都等于L。

注意：循环链表需要注意的是其表空时头节点的指针指向。

3.5、静态链表

定义：静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next,
与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址(数组下标)，又称游标。 和顺序表一样，静态链表也要预先分配一块连续的内存空间。静态链表以next==-l作为其结束的标志。静态链表的插入、删除操作与动态链表的相同,只需要修改指针，而不需要移动元素。

3.6、顺序表和链表的比较

  • 存取方式：顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。
  • 逻辑结构和物理结构：采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。
  • 查找、插入和删除：对于按值查找，顺序表无序时，两者的时间复杂度均为 O ( n ) O(n) O(n)；顺序表有序时，可采用折半查找，此时的时间复杂度为 O ( l o g 2 n ) O(log_{2}n) O(log2​n)。对于按序号查找，顺序表支持随机访问，时间复杂度仅为 O ( 1 ) O(1) O(1)，而链表的平均时间复杂度为 O ( n ) O(n) O(n)。顺序表的插入、删除操作，平均需要移动半个表长的元素，时间复杂度为 O ( n ) O(n) O(n)。链表的插入、删除操作，只需修改相关结点的指针域即可。
  • 空间分配：顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。

http://www.ppmy.cn/news/85767.html

相关文章

Java String split()方法详细教程

Java String split()方法详细教程

Java String split方法详细教程 1、内部实现2、语法3、参数4、返回值5、抛出异常6、Java String split()方法示例7、Java String split()方法与正则表达式和长度示例8、Java String split()方法与正则表达式和长度示例2 Java String类的split()方法根据给定的正则表达式拆分字符…
阅读更多...
SpringCloud Sleuth+Zipkin

SpringCloud Sleuth+Zipkin

SpringCloud SleuthZipkin 官网 https://github.com/spring-cloud/spring-cloud-sleuth Sleuth/Zipkin 是什么&#xff1f; 概述(两张图) 在微服务框架中&#xff0c;一个由客户端发起的请求在后端系统中会经过多个不同的的服务节点调用, 来协同产生最后的请求结果&#x…
阅读更多...
SelFlow: Self-Supervised Learning of Optical Flow

SelFlow: Self-Supervised Learning of Optical Flow

本文提出了一种用于光流的自监督学习方法。该方法从非遮挡像素中提取可靠的流估计&#xff0c;并使用这些预测作为真值来学习幻觉遮挡的光流。 本文设计了一个简单的 CNN&#xff0c;以利用 来自多个帧的时间信息 来更好地进行流估计。本方法可以在 MPI Sintel、KITTI 2012 和 …
阅读更多...
优维低代码实践：页面编排优化与数据联调

优维低代码实践：页面编排优化与数据联调

优维低代码技术专栏&#xff0c;是一个全新的、技术为主的专栏&#xff0c;由优维技术委员会成员执笔&#xff0c;基于优维7年低代码技术研发及运维成果&#xff0c;主要介绍低代码相关的技术原理及架构逻辑&#xff0c;目的是给广大运维人提供一个技术交流与学习的平台。 优维…
阅读更多...
LLMs开源模型们的分布式训练和量化

LLMs开源模型们的分布式训练和量化

前一篇博文整理了&#xff1a; LLMs开源模型们和数据集简介 这篇博文主要整理一下目前流行的训练方法和量化。 &#xff08;图自Towards a Unified View of Parameter-Efficient Transfer Learning&#xff09; Tuning Strategies 使通用LLMs适应下游任务的最常见方法是微调…
阅读更多...
机器学习算法入门与编程实践课后题及答案（唐四新等编著）

机器学习算法入门与编程实践课后题及答案（唐四新等编著）

目录 习题1 习题2 习题3 习题4 习题5 习题6 习题7 习题8 习题1 1.无监督学习的两个主要任务是(多选)(BD)。 A.回归 B.降维 C.分类 D.聚类 2.下列对无监督学习描述错误的是(C)。 A.无标签 B.核心是聚类 C.不需要降…
阅读更多...
汇编十四、51单片机汇编代码规范

汇编十四、51单片机汇编代码规范

1、代码规范的意义 (1)提高源程序的质量和可维护性&#xff0c;从而提高生产力。 2、51汇编开头字母的使用 (1)常量C&#xff1b; (2)变量R&#xff1b; (3)位变量B&#xff1b; (4)标号L&#xff1b; (5)子程序F&#xff1b; (6)表T&#xff1b; (7)中断T&#x…
阅读更多...
真别去阿里面试，6年测开经验的真实面试经历.....

真别去阿里面试，6年测开经验的真实面试经历.....

前几天我朋友跟我吐苦水&#xff0c;这波面试又把他打击到了&#xff0c;做了快6年软件测试员。。。为了进大厂&#xff0c;也花了很多时间和精力在面试准备上&#xff0c;也刷了很多题。但题刷多了之后有点怀疑人生&#xff0c;不知道刷的这些题在之后的工作中能不能用到&…
阅读更多...
最新文章

Copyright @ 2022~2023