c++线性表的基本运算是什么

今天小编给大家分享一下c++线性表的基本运算是什么的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。线性表是一种简单的线性结构，特点是在非空的有限集合中，且第一个元素没有直接前驱元素，最后一个元素没有直接后继元素，其他元素都有唯一的前驱和后继元素。线性表有顺序存储结构和链式存储结构。是指将线性表中的各个元素依次存放在一组地址连续的存储单元中，通常将这种方法存储的线性表称为顺序表。假设，线性表的每个元素需占用m个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个元素的存储位置location(ai+1)和第i个元素的存储位置location(ai)之间满足关系location(ai+1)=location(ai) + m。线性表中第i个元素的存储位置与第一个元素的a1的存储位置满足以下关系，location(ai) =location(a1)+(i-1)*m。其中，第一个元素的位置location(a1)称为起始地址或基地址。顺序表逻辑上相邻的元素在物理上也是相邻的。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。只要确定了第一个元素的起始位置，线性表中的任一个元素都可以随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构。由于C语言的数组具有随机存储特别，因此采用数组来描述顺序表。如下所示：其中，DateType表示数据元素类型，list用于存储线性表中的数据元素，length用来表示线性表中数据元素的个数，SeqList是结构体类型名。定义一个顺序表代码：SeqList L; 指向顺序表的指针：SeqList *L;顺序表的基本运算如下：（1）初始化线性表：(2）线性表非空判断:（3）按序号查找：(4) 按内容查找：（5）插入操作：(6）删除操作：小结：顺序表的优缺点。（1）优点：无须关心表中元素之间的关系，所以不用增加额外的存储空间；可以快速地取表中任意位置的元素。（2）缺点：插入和删除操作需要移动大量元素。使用前需事先分配好内存空间，当线性表长度变化较大时，难以确定存储空间的容量。分配空间过大会造成存储空间的巨大浪费，分配的空间过小，难以适应问题的需求。在解决实际问题时，有时并不适合采用线性表的顺序存储结构，例如两个一元多项式的相加、相乘，这就需要另一种存储结构——链式存储。它是采用一组任意的连续或非连续存储单元存储线性表的元素。为了表示每个元素ai与其直接后继ai+1的逻辑关系，链式存储不仅需要存储元素本身，还要存储一个指向其直接后继元素的地址。这种存储结构被称之为结点（node）。存储元素的叫数据域，存储地址的叫指针域。结点元素的逻辑顺序称之为线性链表或单链表。因为第一个结点没有直接前驱结点，因此需要一个头指 香港云主机针指向它。为了方便操作放在第一个元素结点之前一个结点称之为头结点，头指针变成指向头结点，其数据域可以存放如线表长度等信息，而指针域则存放第一个元素结点的地址信息。若该链表为空，则头结点指针域为空。因为，最后一个元素没有直接后继元素，所以将其指针域设置为“Null”空。单链表的存储结构用C语言描述：其中，ListNode是链表的结点类型，LinkList是指向链表结点的指针类型。定义为：LinkList L = ListNode *L。单链表的基本运算如下：（1）初始化单链表：（2）单链表非空判断：（3）按序号查询操作：（4）按内容查找操作：（5）定位操作：(6)插入新数据元素e：(7) 删除第i个结点：（1）存储方式：顺序表用一组连续的存储单元依次存储线性表的数据元素；而单链表用一组任意的存储单元存放线性表的数据元素。（2）时间性能：采用循序存储结构时查找的时间复杂度为O(1)，插入和删除需要移动平均一半的数据元素，时间复杂度为O(n)。采用单链表存储结构的查找时间复杂度为O(n)，插入和删除不需要移动元素，时间复杂度仅为O(1）。（3）空间性能：采用顺序存储结构时需要预先分配存储空间，分配空间过大会造成浪费，过小会造成问题。采用单链表存储结构时，可根据需要进行临时分配，不需要估计问题的规模大小，只要内存够就可以分配，还可以用于一些特殊情况，如一元多项的表示。循环单链表（circular linkedlist）是首尾相连的一种单链表，即将最后一个结点的空指针改为指向头结点或第一个结点的形成一个环型，最后一个结点称为尾指针:rear。判断单链表为空的条件是head->next==NULL，而判断循环单链表为空的条件是head->next==head。访问第一个结点即rear->next->next。如果将两个循环单链表（LA，LB）合成一个链表，只需将一个表的表尾和另一个表的表头连接即可。具体步骤为：1，将LA->next = LB->next->next; 第一个结点。2，释放LB的头结点，free(LB->next);3, 将LB的表尾与LA的表头相连，LB->next = LA->next。说明：也可以把循环单链表中的头结点成为哨兵结点。双向链表(double linked list)就是链表中的每个结点有两个指针域，一个指向直接前驱结点，另一个指向直接后继结点。双向链表的每个结点有data域、prior域、next域，共三个域。其中，data域为数据域，存放数据元素；prior域为前驱结点指针域；next域为后继结点指针域。双向链表为了方便操作也可以增加一个头结点，同时也像单链表一样也具有循环结构，称为双向循环链表。判断带头结点的双向循环链表为空的条件是：head->prior ==head || head->next == head。C语言描述：p=p->prior->next = p->next->prior。双向链表的结点存储结构描述如下：（1）在第i个位置插入元素值为e的结点：分析：首先找到第i个结点；再申请一个新结点，由s指向该结点，将e放入数据域。然后修改p和s指向的结点的指针域，修改s的prior域，使其指向p的直接前驱结点；修改p的直接前驱结点的next域，使其指向s指向的结点；修改s的next域，使其指向p指向的结点；修改p的prior域，使其指向s指向的结点。（2）删除第i个结点上面各种链表结点的分配与释放都是由函数malloc、free动态实现，因此称为动态链表。但是有的高级程序没有指针类型，就不能利用上述办法动态创建链表，需要利用静态链表实现动态链表的功能。利用一维数组实现静态链表，类型说明如下：静态循环链表：数组的一个分量表示一个结点，同时用游标（指示器cur）代替指针指示结点在数组中的相对位置。头结点是数组的第0分量，其指针域指示链表的第一个结点。表中的最后一个结点的指针域为0，指向头结点。例：线性表如下：
设s为SlinkList类型的变量，则s[0].cur指示头结点，如果令i=s[0].cur，则s[i].data表示表中的第1个元素“Yang”是 s[i].cur指示第2个元素在数组的位置。静态链表基本元素：（1）初始化静态链表：(2）分配结点：(3）回收结点：(4）插入操作：（5）删除操作：以上就是“c++线性表的基本运算是什么”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注开发云行业资讯频道。

相关推荐: Docker Swarm服务发现和负载均衡的原理是什么

今天小编给大家分享一下Docker Swarm服务发现和负载均衡的原理是什么的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。使用的技术docker…