当前位置:   article > 正文

5.线性表:顺序表与链表_线性表顺序和链式

线性表顺序和链式

目     录

一、线性表的定义

二、线性表的顺序存储和链式存储

三、前驱和后继

四、顺序表(顺序存储结构)

1、什么是顺序表

2、顺序表与数组的关系和区别

3、顺序表的建立

4、顺序表的基本操作

五、链表(单链表)

1、什么是链表

2、结点(节点)

3、头结点、头指针和首元结点

4、链表的创建

5、链表的基本操作代码示例


一、线性表的定义

       具有“一对一”逻辑关系的数据,最佳的存储方式是使用线性表。线性表,全名为线性存储结构。使用线性表存储数据的方式可以这样理解,即“把所有数据用一根线儿串起来,再存储到物理空间中”。

图 1 "一对一"逻辑关系的数据

         如图 1 所示,这是一组具有“一对一”关系的数据,我们接下来采用线性表将其储存到物理空间中。首先,用“一根线儿”把它们按照顺序“串”起来,如图 2 所示:

图 2 数据的"线性"结构

       图 2 中,左侧是“串”起来的数据,右侧是空闲的物理空间。把这“一串儿”数据放置到物理空间,我们可以选择以下两种方式,如图 3 所示。

图 3 两种线性存储结构

       两种存储方式都可以将数据之间的关系存储起来,从线的一头开始捋,可以依次找到每个数据,且数据的前后位置没有发生改变。像图 3 这样,用一根线将具有“一对一”逻辑关系的数据存储起来,这样的存储方式就称为线性表或者线性存储结构。

二、线性表的顺序存储和链式存储

        从图 3 不难看出,线性表存储数据的实现方案有两种,分别是:

       1、像图 3a) 那样,不破坏数据的前后次序,将它们连续存储在内存空间中,这样的存储方案称为顺序存储结构(简称顺序表)。

       2、像图 3b) 那样,将所有数据分散存储在内存中,数据之间的逻辑关系全靠“一根线”维系,这样的存储方案称为链式存储结构(简称链表)。

       也就是说,使用线性表存储数据,有两种真正可以落地的存储方案,分别是顺序表和链表。

三、前驱和后继

       在具有“一对一“逻辑关系的数据集中,每个个体习惯称为数据元素(简称元素)。例如,图 1 显示的这组数据集中,一共有 5 个元素,分别是 1、2、3、4 和 5。

        1、某一元素的左侧相邻元素称为该元素的“直接前驱”,此元素左侧的所有元素统称为该元素的“前驱元素”;

        2、某一元素的右侧相邻元素称为该元素的“直接后继”,此元素右侧的所有元素统称为该元素的“后继元素”;

        以图 1 数据中的元素 3 来说,它的直接前驱是 2 ,此元素的前驱元素有 2 个,分别是 1 和 2;同理,此元素的直接后继是 4 ,后继元素也有 2 个,分别是 4 和 5。

图 4 前驱和后继

四、顺序表(顺序存储结构)

1、什么是顺序表

       顺序表又称顺序存储结构,是线性表的一种,专门存储逻辑关系为“一对一”的数据。顺序表存储数据的具体实现方案是:将数据全部存储到一整块内存空间中,数据元素之间按照次序挨个存放。举个简单的例子,将 {1,2,3,4,5} 这些数据使用顺序表存储,数据最终的存储状态如下图所示:

图 5 顺序存储结构示意图

2、顺序表与数组的关系和区别

        1)顺序表,全名顺序存储结构,是线性表的一种。顺序表不仅要求数据在逻辑上是连续的一条直线,还要求用一段物理地址连续的存储单元以次存储表中数据元素,一般情况下采用数组存储。

        2)数组是相同数据类型的元素按一定顺序排列的的集合。数组中的元素存储在一个连续性的内存块中,并通过索引来访问。

       简单的说,数组是在物理空间中连续存储的相同数据类型的元素的集合。

       3)可见:

        a. 数组是一种顺序表,但不能说顺序表是数组。就像小学生是学生,那所有的学生都是小学生吗?我们可以用数组实现顺序表,但我们同样可以用数组实现二叉树、队列等结构,因此不能直接认为顺序表就是数组。

        b. 数组理解为物理结构,顺序表理解为逻辑结构比较合理。因此,顺序表是在计算机内存中以数组的形式保存的线性表。

       c. 在顺序表中我们可以定义表中元素个数、表空间大小等变量,在数组中是没有的。

3、顺序表的建立

       1)顺序表的组成:

            使用顺序表存储数据,除了存储数据本身的值以外,通常还会记录以下两样数据:

         (1)顺序表的最大存储容量:顺序表最多可以存储的数据个数。

         (2)顺序表的长度:当前顺序表中存储的数据个数。

      2)顺序表插入数据原理:往指定位置放元素时,执行如下步骤:

         (1)将要插入位置元素以及后续的元素整体向后移动一个位置;

         (2)将元素放到腾出来的位置上;

            例如,在 {1,2,3,4,5} 的第 3 个位置上插入元素 6,实现过程如下:

            a. 遍历至顺序表存储第 3 个数据元素的位置,如图6所示:

图 6 找到目标元素位置

            b. 将元素 3、4 和 5 整体向后移动一个位置,如图7所示:

图 7 将插入位置腾出

             c.将新元素 6 放入腾出的位置,如图 3 所示:

图 8 插入目标元素

4、顺序表的基本操作

             在Java语言中,顺序表的建立需要使用数组。

             包括操作:

             1) 显示顺序表内容

             2) 获取 pos 位置的元素

             3) 判断空间是否满

             4) 插入数据

             5) 删除指定位置数据

  1. public class sequenceTableArraysList {
  2. // 定义的数组,用于存储元素
  3. public int[] sequenceTable;
  4. // 当前顺序表的存储容量
  5. public int size ;
  6. // 当前顺序表中元素个数,也是有效数据长度
  7. public int usedSize ;
  8. // 构造函数
  9. public myArraysList(){
  10. this.sequenceTable = new int[10];//初始化数组
  11. this.size = 10; // 容量是10
  12. this.usedSize = 0; // 初始化是0
  13. }
  14. // 1. 显示顺序表内容
  15. public void display(){
  16. // 是否为空
  17. if(this.usedSize <= 0){
  18. System.out.println("顺序表为空");
  19. return -1;
  20. }
  21. for (int i = 0; i < this.usedSize; i++){
  22. System.out.print(this.sequenceTable[i]+" ");
  23. }
  24. System.out.println();
  25. }
  26. // 2. 获取 pos 位置的元素
  27. //判断是否越界
  28. //判断是否顺序表为空
  29. //直接返回下标元素
  30. public int getPos(int pos){
  31. if(pos < 0||pos > this.usedSize){
  32. System.out.println("pos下标越界");
  33. return -1;
  34. }
  35. if(this.usedSize <= 0){
  36. System.out.println("顺序表为空");
  37. return -1;
  38. }
  39. return this.arrary[pos];
  40. }
  41. // 3.判断空间是否满
  42. public boolean isFull() {
  43. return this.size == this.usedSize;
  44. }
  45. // 4.中间插入数据还是在尾部添加新数据
  46. public void add(int pos,int data){
  47. if(pos < 0 || pos > this.usedSize)){//判断是否在顺序表范围内
  48. System.out.println("pos不合法");
  49. return;
  50. }
  51. if(isFull()){
  52. //判断是否满了,满了的话扩容
  53. this.sequenceTable = Arrays.copyOf(this.sequenceTable,this.size*2);
  54. this.size = this.size*2;
  55. }
  56. //判断pos是插入数据还是在尾部添加新数据,注意这是顺序表,中间不存在空元素的情况
  57. //从前往后存储
  58. if(pos == this.usedSize){ // 尾部添加新数据
  59. this.sequenceTable[pos] = data;
  60. this.usedSize++;
  61. }else{ // 插入数据
  62. for(int i = this.usedSize - 1; i > pos; i--){
  63. this.arrary[i+1] = this.arrary[i];//从后往前落动
  64. }
  65. this.sequenceTable[pos] = data;
  66. this.usedSize++;
  67. }
  68. }
  69. // 5.删除指定位置数据
  70. public void del(int pos){
  71. if(pos < 0 || pos >= this.usedSize)){//判断是否在顺序表范围内
  72. System.out.println("pos不合法");
  73. return;
  74. }
  75. //默认数组从前往后存储
  76. if(pos == (this.usedSize-1)){ // 尾部删除
  77. this.sequenceTable[pos] = 0;
  78. this.usedSize--;
  79. }else{ // 中间删除
  80. for(int i = pos; i < (this.usedSize -1); i++){
  81. this.sequenceTable[i] = this.sequenceTable[i+1];//从后往前移动
  82. }
  83. this.sequenceTable[this.usedSize - 1] = 0;
  84. this.usedSize--;
  85. }
  86. }
  87. }

五、链表(单链表)

1、什么是链表

       链表又称单链表、链式存储结构,用于存储逻辑关系为“一对一”的数据。和顺序表不同,使用链表存储数据,不强制要求数据在内存中集中存储,各个元素可以分散存储在内存中。例如,使用链表存储 {1,2,3},各个元素在内存中的存储状态可能是:

       可以看到,数据不仅没有集中存放,在内存中的存储次序也是混乱的。那么,链表是如何存储数据间逻辑关系的呢?链表存储数据间逻辑关系的实现方案是:为每一个元素配置一个指针,每个元素的指针都指向自己的直接后继元素,如下图所示:

       显然,我们只需要记住元素 1 的存储位置,通过它的指针就可以找到元素 2,通过元素 2 的指针就可以找到元素 3,以此类推,各个元素的先后次序一目了然。这样,数据元素随机存储在内存中,通过指针维系数据之间“一对一”的逻辑关系,这样的存储结构就是链表。

2、结点(节点)

       在链表中,每个数据元素都配有一个指针,这意味着,链表上的每个“元素”都长下图这个样子:

       数据域用来存储元素的值,指针域用来存放指针。数据结构中,通常将上图这样的整体称为结点。也就是说,链表中实际存放的是一个一个的结点,数据元素存放在各个结点的数据域中。举个简单的例子, {1,2,3} 的存储状态用链表表示,如下图所示:

3、头结点、头指针和首元结点

      一个完整的链表应该由以下几部分构成:

       1)头指针:一个和结点类型相同的指针,它的特点是:永远指向链表中的第一个结点。上文提到过,我们需要记录链表中第一个元素的存储位置,就是用头指针实现。

       2)结点:链表中的节点又细分为头结点、首元结点和其它结点:

       (1)头结点:某些场景中,为了方便解决问题,会故意在链表的开头放置一个空结点,这样的结点就称为头结点。也就是说,头结点是位于链表开头、数据域为空(不利用)的结点。

       (2)首元结点:指的是链表开头第一个存有数据的结点。

       (3)其他节点:链表中其他的节点。

       也就是说,一个完整的链表是由头指针和诸多个结点构成的。每个链表都必须有头指针,但头结点不是必须的。例如,创建一个包含头结点的链表存储 {1,2,3},如下图所示:

       再次强调,头指针永远指向链表中的第一个结点。换句话说,如果链表中包含头结点,那么头指针指向的是头结点,反之头指针指向首元结点。

4、链表的创建

       在Java语言中,链表的建立需要使用类。一个链表的构建离不开一个个结点的组成,所以构建链表的第一步当然是打基础,建立结点,我们可以创建一个类来实现一个结点的创建,然后通过构造方法赋值的方式来给结点赋值,当然这个引用必须得是这个结点类型的引用,因为我们的链表基本都是通过结点指向下一个结点实现的。

  1. //定义节点类
  2. class NodeList{
  3. public int data;
  4. public NodeList next;
  5. public NodeList(int num){
  6. this.data = num;
  7. }
  8. }

5、链表的基本操作代码示例

        包括操作:

        1)得到单链表的长度

        2)查找是否在单链表当中存在内容为key的节点   

        3)插入一个节点

             (1) 在尾部插入一个节点

             (2)在头部插入一个节点

             (3)在任意位置插入一个节点

         4)  删除一个节点

         5) 显示一个链表的内容

         6) 清空链表

  1. public class MyLinkedList {
  2. // 头节点
  3. public NodeList head;
  4. // 初始化链表
  5. public MyLinkedList(int num){
  6. this.head = new NodeList(num);
  7. }
  8. //1、得到单链表的长度
  9. //还有更好的方法,就是在MyLinkedList中定义一个记录器,实时记录链表的长度。
  10. public int size(){
  11. int count = 0;
  12. NodeList cur = this.head;
  13. while(cur != null){
  14. count++;
  15. cur = cur.next;
  16. }
  17. return count;
  18. }
  19. //2. 查找是否在单链表当中存在内容为key的节点
  20. public boolean contains(int key){
  21. NodeList cur = this.head;
  22. while(cur != null){
  23. if(cur.data s == key){
  24. return true;
  25. }
  26. cur = cur.next;
  27. }
  28. return false;
  29. }
  30. //3 插入一个节点
  31. //3.1 在尾部插入一个节点
  32. public void addLast(int num){
  33. NodeList nodeList = new NodeList(num);
  34. if(this.head == null){
  35. this.head = nodeList;
  36. }else{
  37. NodeList cur = this.head;
  38. while(cur.next != null){
  39. cur = cur.next;
  40. }//cur == null
  41. cur.next = nodeList;
  42. }
  43. }
  44. //3.2 在头部插入一个节点
  45. public void addFirst(int num){
  46. NodeList nodeList = new NodeList(num);//先建立一个节点
  47. nodeList.next = this.head;
  48. this.head = nodeList;
  49. }
  50. //3.3 在任意位置插入一个节点
  51. /**
  52. * 找到index-1位置的节点的地址
  53. * @param index
  54. * @return
  55. */
  56. public NodeList findIndex(int index){
  57. NodeList cur = this.head;
  58. while(index - 1 != 0){
  59. cur = cur.next;
  60. index--;
  61. }
  62. return cur;
  63. }
  64. /**
  65. *
  66. * @param index 插入位置
  67. * @param num 插入元素
  68. * 我们可以先判断然后寻找然后插入
  69. */
  70. public void addIndex(int index,int num) {
  71. if (index < 0 || index > size()) {
  72. System.out.println("erro");
  73. return;
  74. }
  75. if(index == size()){
  76. addFirst(num);
  77. return;
  78. }
  79. if(index == size()){
  80. addLast(num);
  81. return;
  82. }
  83. NodeList nodeList = new NodeList(num);
  84. NodeList cur = findIndex(index);
  85. nodeList.next = cur.next;
  86. cur.next = nodeList;
  87. }
  88. //4、删除一个节点
  89. /**
  90. * 找到要删除的关键字的前驱
  91. * @param key
  92. * @return
  93. */
  94. public NodeList searchPerv(int key){
  95. NodeList cur = this.head;
  96. while(cur != null){
  97. if(cur.next.data == key){
  98. return cur;
  99. }//注意是cur.next
  100. cur = cur.next;
  101. }
  102. return null;
  103. }
  104. //删除第一次出现关键字为key的节点
  105. public void remove(int key){
  106. if(this.head == null){
  107. System.out.println("erro");
  108. return;
  109. }
  110. // 头节点的内容是否是key
  111. if(this.head.data == key){
  112. this.head = this.head.next;
  113. return;
  114. }
  115. NodeList cur = searchPerv(key);
  116. NodeList del = cur.next;
  117. cur.next = del.next;
  118. }
  119. //5、 显示一个链表的内容
  120. public void display(){
  121. NodeList cur = this.head;//cur来遍历链表
  122. while(cur != null){
  123. System.out.print(cur.date+" ");
  124. cur = cur.next;
  125. }
  126. System.out.println();
  127. }
  128. /**
  129. * 从指定头节点开始进行打印
  130. * @param newHead 给定的头节点
  131. */
  132. public void display2(NodeList newHead){
  133. NodeList cur = newHead;
  134. while(cur != null){
  135. System.out.print(cur.date+" ");
  136. cur = cur.next;
  137. }
  138. System.out.println();
  139. }
  140. //6、清空链表
  141. public void clear(){
  142. while (this.head != null) {
  143. NodeList curNext = head.next;
  144. this.head.next = null;
  145. this.head = curNext;
  146. }
  147. }
  148. }

上一篇:

4. 好算法的判断标准: 时间复杂度和空间复杂度_好的算法的标准_IT小悟的博客-CSDN博客程序=数据结构(解决存储数据和数据之间关系) + 算法(解决如何访问和处理数据问题),当数据之间的关系确定后,算法的选择将是影响程序执行效率的关键,通常运用“时间复杂度”和“空间复杂度”来衡量一个算法的运行效率_好的算法的标准https://blog.csdn.net/speedwalkman/article/details/130366560下一篇:

6.线性表:顺序表和链表的优缺点_IT小悟的博客-CSDN博客本章节主要介绍顺序表和链表的定义、特点、优点、缺点和适应环境https://blog.csdn.net/speedwalkman/article/details/131512304

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

闽ICP备14008679号