Carson带你学数据结构:这是一份全面& 详细的 线性表 学习指南

雨点打透心脏的1/2处 2022-03-17 15:08 316阅读 0赞

e42c52b9af8d79486a0f3cd0e50df7b7.png

前言

  • 本文主要讲解 数据结构中最基础的线性表
  • 内容包括其特点、结构(顺序存储结构 & 链式结构)等,希望你们会喜欢。

目录

示意图


1. 简介

示意图

  • 其中,线性表的存储结构最为重要
    下面,我将主要讲解其 顺序存储结构 & 链式存储结构

2. 顺序存储结构

  • 实现方式:数组
  • 下面,我将主要讲解其结构特点 & 相关操作

2.1 结构特点

  1. 存储线性表的数据元素的方式 = 一段地址连续的存储单元
  2. 具备:起始位置、数组长度(最大存储容量) & 线性表长度(当前长度)

    • 示意图

示意图

  • 概念说明

























概念 说明
数组长度 存放线性表的空间长度(固定不变)
线性表长度 存放线性表数据元素的长度(动态变化)
地址 存储单元的编号
数组下标 第 i 个元素 = 数组下标第 i-1 的位置

2.2 对应操作

顺序存储结构的操作包括:插入 & 删除

  • 操作1:插入

示意图

  • 操作2: 删除

示意图

注:线性表的存取数据时间性能 = O(1)

2.3 结构优、缺点

示意图

2.4 应用场景

已知长度、数据元素个数变化不大、存、取数据频率高的场景

2.5 总结

示意图


3. 链式存储结构

  • 实现方式:链表
  • 下面,我将主要讲解其结构特点 & 相关操作

3.1 结构特点

示意图

  • 链表示意图(以单链表为例)
    示意图
  • 存储元素说明示意图

示意图

下面将主要重点讲解各种链表:(重点讲解)单链表、双向链表、循环链表、静态链表

3.2 单链表

3.2.1 定义

每个结点只有1个指针域

3.2.2 示意图

示意图

3.2.3 操作(读取、插入、删除、整表创建、整表删除)
  • 读取
    算法思路:工作指针向后移

    int j ;

    // 1. 声明1动态指针
    LinkList p ;

    // 2. 让p指向链表L的第一个结点
    // L = 头结点
    p = L ->next

    // 3. 设置计数器
    j = 1;
    while ( p && j<i ){

    p = p->next;// 指向下一个结点
    ++j;

    }

    // 直到到了i结点,直接取出
    e = p->data

  • 插入

通过遍历找到i结点,生成一个空结点,然后插入

示意图

  • 删除

示意图

  • 整表创建
    示意图
  • 整表删除

示意图

  • 单链表实现

http://blog.csdn.net/chenleixing/article/details/42392283

  1. public class UnidirectionalLinkedList<T> {
  2. /**
  3. * 设置结点结构
  4. */
  5. // a. 结点结构
  6. private class Node<T>{
  7. private T data;
  8. private Node<T> next ;
  9. public Node(T data){
  10. this.data = data;
  11. }
  12. }
  13. // b. 头结点
  14. private Node<T> first;
  15. // c. 当前结点
  16. private Node<T> currentNode;
  17. // d. 链表长度
  18. private int size;
  19. /**
  20. * 构造函数
  21. * 作用:初始化结点
  22. */
  23. public UnidirectionalLinkedList(){
  24. currentNode = first = null;
  25. size = 0;
  26. }
  27. /**
  28. * 1. 添加结点
  29. * 内容:在头 / 尾 添加结点 & 在特定位置插入结点
  30. */
  31. // a. 在链表头部加入1个结点
  32. // 即,把新加入的结点设置为第一结点
  33. public void addFirstNode(T data){
  34. // 1. 将需添加的内容封装成结点
  35. Node<T> newNode = new Node<T>(data);
  36. // 2. 将新添加结点的指针域指向旧第1个结点
  37. newNode.next = first;
  38. // 3. 将新添加结点设置为第1个结点
  39. first = newNode;
  40. // 4. 链表长度+1
  41. size++;
  42. }
  43. // b. 在链表尾部加入1个结点
  44. // 即,把新加入的结点设置为最后结点
  45. public void addNode(T data){
  46. // 1. 检查当前链表是否为空
  47. if (isEmpty()){
  48. addFirstNode(data);
  49. return;
  50. }
  51. // 2. 把当前指针定位到最后一个结点
  52. locateNode(size-1);
  53. // 3. 将需添加的内容封装成结点
  54. currentNode.next = new Node<T>(data);
  55. // 4. 链表长度+1
  56. size++;
  57. }
  58. // c. 在链表中插入结点
  59. public T insertNode(int index, T data) {
  60. // 1. 检查当前链表是否为空
  61. if (isEmpty()){
  62. addFirstNode(data);
  63. return null;
  64. }
  65. // 2. 把当前指针定位到需插入的结点位置
  66. locateNode(index);
  67. // 3. 将需添加的内容封装成结点
  68. Node<T> insertNode = new Node<T>(data);
  69. // 4. 把需插入结点位置的下1个结点 赋给 插入的结点
  70. insertNode.next = currentNode.next;
  71. // 5. 把插入结点 赋给 需插入的结点的位置
  72. currentNode.next = insertNode;
  73. // 6. 链表长度+1
  74. size++;
  75. // 7. 返回插入结点的数据
  76. return insertNode.data;
  77. }
  78. /**
  79. * 2. 删除结点
  80. * 内容:删除第1个结点 & 删除特定位置的结点
  81. */
  82. // a. 删除第1个结点,并返回该结点数据
  83. public T removeFirstNode() {
  84. // 1. 检查当前链表第一个结点是否为空
  85. if (first == null){
  86. try {
  87. throw new Exception("链表为空!");
  88. } catch (Exception e) {
  89. e.printStackTrace();
  90. }
  91. }
  92. // 2. 获取被删除结点的数据
  93. T temp = first.data;
  94. // 3. 将第2个结点设置为第1个结点
  95. first = first.next;
  96. // 4. 链表长度减1
  97. size--;
  98. // 5. 返回被删除结点的数据
  99. return temp;
  100. }
  101. // b. 删除特定位置的结点,并将里面的数据返回
  102. public T removeNode(int index) {
  103. // 1. 检查当前链表是否为空
  104. if (isEmpty()){
  105. try {
  106. throw new Exception("链表为空!");
  107. } catch (Exception e) {
  108. e.printStackTrace();
  109. }
  110. }
  111. // 2. 把当前指针(currentNode)定位到 需删除结点(index)的前1个结点
  112. locateNode(index-1);
  113. // 3. 获取被删除结点的数据
  114. T temp = currentNode.next.data;
  115. // 4. 将需删除结点(index)的前1个结点 的下1个结点 设置为 需删除结点(index)的下1个结点
  116. currentNode.next = currentNode.next.next;
  117. // 5. 链表长度减1
  118. size--;
  119. // 6. 返回被删除结点的数据
  120. return temp;
  121. }
  122. /**
  123. * 3. 获取特定位置的结点
  124. * 内容:将当前指针(currentNode)定位到所需结点位置、根据索引位置获取结点数据
  125. */
  126. // a. 将当前指针(currentNode)定位到所需结点位置
  127. private void locateNode(int index){
  128. // 1. 判断指针是否越界
  129. if (index <0 && index >size){
  130. try {
  131. throw new IndexOutOfBoundsException("参数越界!");
  132. } catch (Exception e) {
  133. e.printStackTrace();
  134. }
  135. }
  136. int i = 0;
  137. // 2. 通过遍历链表,寻找索引index所指结点
  138. for(currentNode = first; currentNode.next != null && i < index; i++){
  139. currentNode = currentNode.next;
  140. }
  141. }
  142. // b. 根据索引位置获取结点数据
  143. public T getNode(int index) {
  144. // 1. 判断链表是否为空
  145. if (isEmpty()){
  146. try {
  147. throw new Exception("链表为空!");
  148. } catch (Exception e) {
  149. e.printStackTrace();
  150. }
  151. }
  152. // 2. 把当前指针(currentNode)定位到 所需索引位置(index)
  153. locateNode(index);
  154. // 3. 返回当前指针的数据,即所需索引位置的数据
  155. return currentNode.data;
  156. }
  157. /**
  158. * 检查当前链表是否为空
  159. */
  160. public boolean isEmpty(){
  161. if (size == 0){
  162. return true;
  163. }else {
  164. return false;
  165. }
  166. }
  167. public static void main(String[] args){
  168. // 1. 创建链表 & 加入结点数据
  169. UnidirectionalLinkedList<Integer> list = new UnidirectionalLinkedList<Integer>();
  170. list.addNode(1);
  171. list.addNode(2);
  172. list.addNode(3);
  173. list.addNode(4);
  174. list.addNode(5);
  175. // 2. 输出当前链表数据
  176. System.out.println("链表数据如下:");
  177. for (int i = 0; i < list.size;i++){
  178. try {
  179. System.out.print(list.getNode(i)+" ");
  180. } catch (Exception e) {
  181. e.printStackTrace();
  182. }
  183. }
  184. System.out.println("-----------------------");
  185. // 3. 获得某个位置结点的数据
  186. System.out.println("位置3的数据是:" + list.getNode(3));
  187. System.out.println("-----------------------");
  188. // 4. 插入结点:在位置4插入,数据 = 66
  189. System.out.println("在位置4插入的data:"+list.insertNode(3,66));
  190. System.out.println("插入后:");
  191. for (int i = 0; i < list.size;i++){
  192. try {
  193. System.out.print(list.getNode(i)+" ");
  194. } catch (Exception e) {
  195. e.printStackTrace();
  196. }
  197. }
  198. System.out.println("-----------------------");
  199. // 5. 删除结点
  200. System.out.println("删除index为3的data:"+list.removeNode(3));
  201. System.out.println("删除后:");
  202. for (int i = 0; i < list.size;i++){
  203. try {
  204. System.out.print(list.getNode(i)+" ");
  205. } catch (Exception e) {
  206. e.printStackTrace();
  207. }
  208. }
  209. }
  210. }
  • 测试结果

    链表数据如下:1 2 3 4 5

    位置3的数据是:4

    在位置4插入的data:66

    插入后:1 2 3 4 66 5

    删除index为3的data:4
    删除后:1 2 3 66 5


3.3 循环链表

  • 定义
    将单链表的终端结点的指针指向头结点、使得单链表头尾相接、形成1个环

也称单循环链表

  • 示意图

示意图

3.4 双向链表

3.4.1 定义

每个结点有2个指针域:1指向后驱结点元素、2指向前驱结点元素

即 在单链表的结点中,再设置一个指向前驱结点的指针域

3.4.2 示意图

示意图

3.4.3 链表操作(插入& 删除)

示意图

注:插入 & 删除都需要同时改变2个指针变量

3.4.4 特点

  • 缺点:占用空间多 = 记录2个指针
  • 优点:算法时间性能高 = 良好对称性(前、后指针)

即,用空间换时间

3.5 静态链表

示意图


4. 存储结构对比

示意图


5. 总结

  • 本文主要讲解了数据结构中最基础的线性表
  • 下面我将继续对 数据结构,感兴趣的同学可以继续关注carson_ho的微信公众号
    示意图

请帮顶 / 评论点赞!因为你的鼓励是我写作的最大动力!

发表评论

表情:
评论列表 (有 0 条评论,316人围观)

还没有评论,来说两句吧...

相关阅读