首页 / 算法 / 数据结构与算法——基本数据结构
数据结构与算法——基本数据结构
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法——基本数据结构,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4916字,纯文字阅读大概需要8分钟。
内容图文
![数据结构与算法——基本数据结构](/upload/InfoBanner/zyjiaocheng/607/00ec2425fec741efb274891e8ccc4a9b.jpg)
数据结构与算法——基本数据结构00
线性表
-
n个具有相同特性的数据元素的有限序列。
-
数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储,但是把最后一个数据元素的尾指针指向了首位结点)。
-
“线性”和“非线性”,只在逻辑层次上讨论,而不考虑存储层次,所以双向链表和循环链表依旧是线性表。
-
在数据结构逻辑层次上细分,线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”,可以自由的删除或添加结点。受限线性表主要包括栈和队列,受限表示对结点的操作受限制。
-
特征
1.集合中必存在唯一的一个“第一元素”。
2.集合中必存在唯一的一个 “最后元素” 。
3.除最后一个元素之外,均有唯一的后继(后件)。
4.除第一个元素之外,均有唯一的前驱(前件)。
-
两种表示
- 顺序表示
- 指的是用一组地址连续的存储单元依次存储线性表的数据元素,称为线性表的顺序存储结构或顺序映像*(sequential mapping)*。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系,可随机存取表中任一元素。
- 链式表示
- 是用一组任意的存储单元存储线性表中的数据元素,称为线性表的链式存储结构。它的存储单元可以是连续的,也可以是不连续的。在表示数据元素之间的逻辑关系时,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息*(即直接后继的存储位置),这两部分信息组成数据元素的存储映像,称为结点(node)*。它包括两个域;存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链
- 顺序表示
队列
现象:
你们在用电脑时有没有经历,机器有时会处于疑似死机的状态,鼠标点什么似乎都没用,双击任何快捷方式都不动弹。就当你失去耐心,打算rest时。突然他像酒醒了一样,把你刚才点击的所有操作全部按顺序执行一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出,而按先后次序排队等待造成的。
再比如向移动、联通、电信等客服电话,客服人员与客户相比总是少数,在所有的客服人员都占线的情况下,客户会被要求等待,直到有某个客户人员空下来,才能让最先等待的客户接通电话。这里也是将所有当前打客服电话的客户进行排队处理。
操作系统和客服系统中,都是应用了一种数据结构来实现刚才提到的先进先出的排队功能,这就是队列。
-
队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。(头删尾插)
-
先进先出
-
顺序队列
建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间,并设置两个指针进行管理。一个是队头指针front,它指向队头元素;另一个是队尾指针rear,它指向下一个入队元素的存储位置,如图所示:
每次在队尾插入一个元素是,rear增1;每次在队头删除一个元素时,front增1。随着插入和删除操作的进行,队列元素的个数不断变化,队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时,队列中没有任何元素,称为空队列。当rear增加到指向分配的连续空间之外时,队列无法再插入新元素,但这时往往还有大量可用空间未被占用,这些空间是已经出队的队列元素曾经占用过得存储单元。
-
顺序队列中的溢出现象:
- 出队下溢:队列为空时,做出队运算产生的溢出现象。
- 队满上溢:当队列满时,做进栈运算产生空间溢出的现象。
- 假上溢:头尾指针只增加不减小,致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时,也可能由于尾指针已超越向量空间的上界而不能做入队操作。
-
循环队列:
-
-
实现
- 数组实现
- 链表实现
-
LinkedList类实现了Queue接口,因此我们可以把LinkedList当成Queue来用。
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
//add()和remove()方法在失败的时候会抛出异常(不推荐)
Queue<String> queue = new LinkedList<String>();
//添加元素
queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
queue.offer("e");
for(String q : queue){
System.out.println(q);
}
System.out.println("===");
System.out.println("poll="+queue.poll()); //返回第一个元素,并在队列中删除
for(String q : queue){
System.out.println(q);
}
System.out.println("===");
System.out.println("element="+queue.element()); //返回第一个元素
for(String q : queue){
System.out.println(q);
}
System.out.println("===");
System.out.println("peek="+queue.peek()); //返回第一个元素
for(String q : queue){
System.out.println(q);
}
}
}
offer,add 区别:
一些队列有大小限制,因此如果想在一个满的队列中加入一个新项,多出的项就会被拒绝。
这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常,而只是得到由 offer() 返回的 false。
poll,remove 区别:
remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似, 但是新的 poll() 方法在用空集合调用时不是抛出异常,只是返回 null。因此新的方法更适合容易出现异常条件的情况。
peek,element区别:
element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似,在队列为空时, element() 抛出一个异常,而 peek() 返回 null。
-
分类
-
单端队列
-
双端队列
-
-
- 访问Access O(n)
- 搜索Search O(n)
- 插入:O(1)
- 删除:O(1)
-
常用操作
-
创建队列
-
添加元素
-
获取即将要出队的(peek)
-
删除即将出队的 remove() pop() poll()
-
判断队列是否为空
-
队列长度
-
遍历队列
-
-
推荐Leecode 题目: 933 ,239
-
删除即将出队的 remove() pop() poll()
-
判断队列是否为空
-
队列长度
-
遍历队列
-
-
推荐Leecode 题目: 933 ,239
内容总结
以上是互联网集市为您收集整理的数据结构与算法——基本数据结构全部内容,希望文章能够帮你解决数据结构与算法——基本数据结构所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。