当前位置:   article > 正文

数据结构之线性表,栈和队列_线性表栈和队

线性表栈和队

1.线性表

  1.1顺序表

  1.2链表

2.栈

  2.1数组栈

3.队列

  3.1链式队列

数据结构可以说是人必须学习的一门重要的课程了,它的难度可谓不小,今天这篇博客详细介绍了线性表,栈和队列的介绍以及实现,希望能给大家带来帮助。

1.线性表

概念:用一组地址连续的存储单元依次存储线性表的数据元素,这种存储结构的线性表称为顺序表。

特点:逻辑上相邻的数据元素,物理次序也是相邻的。只要确定好了存储线性表的起始位置,线性表中任一数据元素都可以随机存取,所以线性表的顺序存储结构是一种随机存取的储存结构,我们通常用动态内存开辟的方法来开辟顺序表内存。

1.1顺序表

因此基于线性表的特点,我们要实现的顺序表接口有以下几种:

1.顺序表的初始化

2.顺序表的尾部插入数据

3.顺序表的头部插入数据

4.顺序表的数据查找

5.顺序表的尾部删除数据

6.顺序表的头部删除数据

7.顺序表的打印

8.顺序表的销毁

顺序表的初始

顺序表的头部插入数据

顺序表的头部插入数据

顺序表的数据查找(找到了返回下标,没找到返回-1)

顺序表的尾部删除数据

顺序表的头部删除数据

顺序表的打印

顺序表的销毁

以上就是简单实现的顺序表了,接口还不算太多。
 

顺序表的优缺点

优点:无须为表中元素之间的逻辑关系而增加额外的存储空间;可以快速的存取表中任一位置的元素。
缺点:插入和删除操作需要移动大量元素;当线性表长度较大时,难以确定存储空间的容量;造成存储空间的“碎片”。

1.2链表

单链表的基本概念
在链式结构中,除了要存储数据元素的信息外,还要存储它的后继元素的存储地址。因此,为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系,对数据ai来说,除了存储其本身的信息之外,还需要存储一个指示其直接后继的信息(即直接后继的存储位置)。我们吧把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像,称为结点(Node)。
n个结点(ai的存储映像)链结成一个链表,即为线性表(a1, a2, …, an)的链式存储结构,因为此链表的每个结点中只包含一个指针域,所以叫做单链表。

实现链表的接口:

1.链表的数据头插

2.链表的数据尾插

3.链表的数据头删

4.链表的数据尾删

5.链表的数据查找

6.链表的数据插入

7.链表的数据打印

8.链表的销毁

链表的数据存储方式

这个图表是增添新的节点的函数,其原理和顺序表的类似。


1.链表的数据头插

链表的数据尾插

链表的数据头删

链表的数据尾删

链表的数据查找

链表的数据插入

链表的数据打印

链表的销毁

以上是单项链表的实现,结构算简单,后边还有双向链表,循环链表,双向循环链表等等复杂链表,感兴趣的小伙伴可以去了解一下

2.1数组栈

栈(Stack):是只允许在一端进行插入或删除的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。

栈顶(Top):线性表允许进行插入删除的那一端。
栈底(Bottom):固定的,不允许进行插入和删除的另一端。
空栈:不含任何元素的空表。

栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构

栈这类数据结构可以既可以用顺序表来实现(也称数组实现)也可以用链表来实现

但由于栈数据的先进后出的特性,我们一般采用后者方法来实现。

实现数组栈的接口:

1.数组栈的初始化

2.栈顶数据入栈

3.栈顶数据出栈

4.数组栈数据打印

5.数组栈销毁

6.查找栈顶数据

7.判断数组栈是否为空

8.求数组栈数据个数

数组栈的初始化

栈顶数据入栈

栈顶数据出栈

数组栈数据打印

数组栈销毁

查找栈顶数据

判断数组栈是否为空

求数组栈数据个数

以上是数组栈的接口实现,需要注意的是定义结构体变量的时候要定义地址变量

3.1链式队列

队列的定义
队列(queue)是只允许在一端进行插入操作,在另一端进行删除操作的线性表,简称“队”。

队列是一种先进先出(First In First Out)的线性表,简称FIFO。

允许插入的一端称为队尾(rear),允许删除的一端称为队头(front)。

向队列中插入新的数据元素称为入队,新入队的元素就成为了队列的队尾元素。

从队列中删除队头元素称为出队,其后继元素成为新的队头元素。

同栈这个数据结构一样,队列的实现也可以用顺序表和链表,在本篇博客,我们用链表队列来实现一个简单的栈结构

实现链式队列的接口:

1.队列的初始化

2.队列的销毁

3.队尾的数据插入

4.队头的数据出队列

5.判断队列是否为空

6.取队头的数据

7.取队尾的数据

8.求队列数据的个数

队列的初始化

队列的销毁

队尾的数据插入

队头的数据出队列

判断队列是否为空

取队头的数据

取队尾的数据

求队列数据的个数

以上就是对简单队列函数接口的实现了,后面还有更为复杂的循环队列

小伙伴们可以去leetcode上面找相关的题目来做

总结:看似我们今天实现了四个不同结构的结构,其实本质上就是顺序表和链表的区别,二者相关与不同的地方颇多。

顺序表和链表的比较
1、存取(读写)方式
顺序表可以顺序存取,也可以随机存取,链表只能从表头顺序存取元素。例如在第i个位置上执行存或取的操作,顺序表仅需一次访问,而链表则需从表头开始依次访问i次。

2、逻辑结构与物理结构
采用顺序存储时,逻辑上相邻的元素,对应的物理存储位置也相邻。而采用链式存储时,逻辑上相邻的元素,物理存储位置则不一定相邻,对应的逻辑关系是通过指针链接来表示的。

3、查找、插入和删除操作
对于按值查找,顺序表无序时,两者的时间复杂度均为O(n);顺序表有序时,可采用折半查找,此时的时间复杂度为O(log2n)。
对于按序号查找,顺序表支持随机访问,时间复杂度仅为O(1),而链表的平均时间复杂度为O(n)。顺序表的插入、删除操作,平均需要移动半个表长的元素。链表的插入、删除操作,只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域,故而存储密度不够大。

4、空间分配
顺序存储在静态存储分配情形下,一旦存储空间装满就不能扩充,若再加入新元素,则会出现内存溢出,因此需要预先分配足够大的存储空间。预先分配过大,可能会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。动态存储分配虽然存储空间可以扩充,但需要移动大量元素,导致操作效率降低,而且若内存中没有更大块的连续存储空间,则会导致分配失败。链式存储的结点空间只在需要时申请分配,只要内存有空间就可以分配,操作灵活、高效。

对于今天的博客分享就到这里,希望能帮助到大家!
 


 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/801602
推荐阅读
相关标签
  

闽ICP备14008679号