数据结构算法大应用部分线性表.pdfVIP

自我介绍

•本科东学，大学，计算机专业，研究方向大数

据和分布式。

•主要擅长Java技术栈，Python开发，大数据，web开发相关技术。

•参与多个项目，包括国家重点项目和大型互联网公司项目开发。

•在美团点评实实习和秋招面试拿到包括、腾讯、

阿里、美团、、网易游戏、、蘑菇街在内的10余个

国内大中型互联网公司offer。

课程介绍

•线性表

•栈和队列

•树

•图

•散列表

线性表

•基本概念：数组和链表的区别，单链表，双向链表和循环链表

•单链表基本操作

•实战之单链表反转，单链表取中间值

•实战之合并两个有序链表

•面试：奇数位升序，偶数位降序链表排序

•面试：单链表实现归并排序

基本概念

线性表是一种逻辑结构，相同数据类型的n个数据元素的有限序列，除第一个元素外，每个元素有且仅有一

个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继。

线性表具有以下特点：

•元素个数有限

•逻辑上元素有先后次序

•数据类型相同

•仅讨论元素间的逻辑关系

数组和链表

数组的优点链表的优点

•随机性强•删除速度快

•查找速度快•内存利用率高，不会浪费内存

数组的缺点•大小没有固定，拓展很灵活。

•和删除效率低链表的缺点

•可能浪费内存•不能随机查找，必须从第一个开始遍历，查找效率低

•内存空间要求高，必须有足够的连续内存空间。

•数组大小固定，不能动态拓展

单链表，双向链表和循环链表

单链表，双向链表和循环链表

1.循环单链表

与单链表的区别在于，表中最后一个节点的指针不为null，而改为指向头结点（第一个节点），从而整个链表

形成一个环。判断循环单链表是否为空，判断是否等于头指针。只有一个尾指针的循环单链表，可以很方便

的操作表头和表尾，因为尾指针的后继就是头指针O(1)。

2.循环双链表

与双链表的区别在于，头结点的prior指针指向尾节点，尾节点的next指针指向头结点。

基本操作

头结点尾结点

基本操作

删除

实战

•单链表反转，单链表取中间值

•合并两个有序链表

•面试：奇数位升序，偶数位降序链表排序

•面试：单链表归并排序

归并排序

归并排序（MERGE-SORT）是利用归并的思想

实现的排序方法，该算法采用经典的分治策略

（分治法将问题分成一些小的问题然后递归求解，

而治的阶段则将分的阶段得到的各答案修补在

一起，即分而治之)。

可以看到这种结构很像一棵完全二叉树，本题的

归并排序我们采用递归去实现（也可采用迭代的

方式去实现）。分阶段可以理解为就是递归拆分

子序列的过程，递归深度为logn。

2

归并排序

归并排序应该算是链表排序最佳的选择了，保证了最好和时间复杂度都是nlogn，而且它在数组排序中广

受诟病的空间复杂度在链表排序中也从O(n)降到了O(1)。

归并排序的一般步骤为：

•将待排序数组（链表）取中点并一分为二；

•递归地对左半部分进行归并排序；

•递归地对右半部分进行归并排序；

•将两个半部分进行合并（merge），得到结果。

首先用快慢指针(快慢指针思路，快指针一次走两步，慢指针一次走一步，快指针在链表末尾时，慢指针恰好

在链表