精华内容
下载资源
问答
  • 线性表的定义:线性表中数据元素之间的关系是一对一的关系,即除了第一元素没有前驱,最后一元素没有后继之外,其余元素既有唯一前驱和唯一后继,如下图所示 搞懂什么是线性表之后,我们再考虑一问题,...

    1.何为线性表

    首先说什么是线性表

    线性表的定义:线性表中数据元素之间的关系是一对一的关系,即除了第一个元素没有前驱,最后一个元素没有后继之外,其余元素既有唯一前驱和唯一后继,如下图所示

    搞懂什么是线性表之后,我们再考虑一个问题,线性表能干啥?

    手机上的通讯录是不是符合一个线性表的定义?

    刺激战场中背包内容是不是符合一个线性表的定义?

    学校中的成绩单是不是符合一个线性表的定义?

    是的,对于上述三个场景都符合线性表的定义,只不过主要的区别在于所存储的数据元素不同罢了

    这里大家注意,所谓的数据元素不只是整数int,小数double,布尔boolean和字符串String等等简单的数据类型

    数据元素,是由多个数据项组成的集合体,大家可以定义一个类对这些数据项进行封装,那么线性表中只需要存储由这个类所创建出来的若干个对象即可

    比如手机通讯录里的联系人数据元素,由头像、姓名、电话三个数据项组成

    刺激战场中背包的物品数据元素,由图片、名称、说明、属性四个数据项组成

    成绩单中学生分数的数据元素,由姓名、语文分数、数学分数、英语分数、总分、平均分六个数据项组成

    到这里大家就能够明白,线性表的主要作用就是存储类似上述场景中的数据

    除了存储之外,还应该具有增加数据,删除数据,查寻数据,修改数据这四个基本的操作,对吧~

     

    2.逻辑结构和物理结构

    到目前为止,我们一直在讨论线性表能够做什么,但是如何让计算机能够认识且存储线性表就是我们现在要考虑的问题

    上述讨论的线性表其实是我们臆想出来的,还没有真实的存储在于计算机内存中,我们把它称之为线性表的逻辑结构

    什么是逻辑结构,就是只知道他的定义,但不知如何将其进行实际的实现

    在计算机领域中,对于线性表的实现方式主要有两种,称之为线性表的物理结构

    • 动态数组:用编程语言中自带的数组去实现线性表,如图所示

    • 动态链表:定义节点数据类型,将元素存入节点,然后将节点进行串联实现线性表,如图所示

    我们会发现,如果用动态数组实现线性表,那么元素在数组中存储的话是地址连续的,因为数组中的存储空间是连续的

    如果用动态链表实现线性表的话,那么元素的地址是随机的,因为节点对象创建时的地址是由系统底层决定的且随机的,所以为了保持线性表的性质,每一个节点除了存储数据信息外,还需要存储其下一个节点的地址

    无论是动态数组实现线性表也好,还是动态链表实现也罢,它们对线性表的操作无非还是增删改查,所以我们可以先对两者的具体实现定义统一的操作规范,即定义线性表的接口,如下代码所示

    创建List.java写入代码

    
     
    1. //让List线性表支持泛型,E表示任意的数据类型
    2. public interface List<E> {
    3. public int getSize(); //获取线性表中元素的个数
    4. public boolean isEmpty(); //判断线性表是否为空表
    5. public void add(int index,E e); //在线性表中指定角标index处插入元素e
    6. public void addFirst(E e); //在线性表中第一个位置插入元素e
    7. public void addLast(E e); //在线性表中最后一个位置插入元素e
    8. public E get(int index); //获取线性表中指定角标index处的元素
    9. public E getFirst(); //获取线性表中第一个元素
    10. public E getLast(); //获取线性表中最后一个元素
    11. public void set(int index,E e); //修改线性表中指定角标index处的元素为新元素e
    12. public boolean contains(E e); //判断线性表中是否包含指定元素e
    13. public int find(E e); //获取线性表中元素e从头到尾第一次出现的位置
    14. public E remove(int index); //删除并返回线性表中指定角标index处的元素
    15. public E removeFirst(); //删除并返回线性表中第一个元素
    16. public E removeLast(); //删除并返回线性表中最后一个元素
    17. public void removeElement(E e); //删除线性表中指定元素e
    18. public void clear(); //清空线性表
    19. }

     

    3.Java中数组的特点

    创建好List接口之后,我们接下来就来讨论如何用动态数组实现线性表

    首先我们来回顾一下Java中数组的特点,下面代码是Java中创建一维数组的三种常用方式:

    
     
    1. int[] arr1= new int[ 100];
    2. int[] arr2= new int[]{ 1, 2, 3, 4, 5};
    3. int[] arr3={ 1, 2, 3, 4, 5};
    • 第一种,创建名为arr1的一维整型数组,指定长度为100,且元素默认为0
    • 第二种,创建名为arr2的一维整型数组,指定元素为[1,2,3,4,5],且长度为5
    • 第三种,和第二种同理

    除了创建方式之外,数组还有以下几个特点:

    • 数组提供角标访问元素
    • 数组长度一旦确定则不可更改
    • 数组只有唯一的属性length表示数组的长度

    那么数组的本质是什么的?数组本质就是一组空间大小相同连续的存储结构,如图所示

    已知第1个空间的地址为0x100,且每个空间大小都是4byte,那么第n个空间的大小是多少呢?

    A_n=A_1+(n-1)\ast d

    大家会发现,这是一个等差公式,对的!此时A1=0x100,d=4,所以一个公式直接算出第n个位置元素的地址

    所以基于这一特点,我们可以用O(1)的时间去查找一个元素

    注意此处 n 为元素在数组中的位置,而 n-1 表示元素在数组中的角标

    
     
    1. int[] arr={ 1, 2, 3, 4, 5};
    2. arr[ 3]; //表示角标3的元素,即就是位置4的元素 A4=A1+(4-1)*4
    3. arr[ 4]; //表示角标4的元素,即就是位置5的元素 A5=A1+(5-1)*4
    4. arr[ 5]; //表示角标5的元素,即就是位置6的元素,但是该元素不存在,所以报错

    OK,数组的本质说完了,再来看看数组的操作

    我们之前学过和数组相关的操作,基本上都是将数组当做参数传入到一个函数当中

    
     
    1. //查找数组中的最大值
    2. public int findMax(int[] arr){...}
    3. //对数组进行排序
    4. public void sort(int[] arr){...}
    5. //交换角标i,j元素的位置
    6. public void swap(int[] arr,int i,int j){...}

    这样子的话,我们是将数组这个数据和函数这个操作进行分离的,并没有很好的体现面向对象的思想

    如果能够将数据和操作进行封装成一个类MyArray,形成如下的操作方式,岂不是更好?

    
     
    1. class MyArray{
    2. private int[] arr;
    3. public MyArray(){
    4. arr= new int[ 10];
    5. }
    6. public void add(int e){...}
    7. public int findMax(){...}
    8. public void sort(){...}
    9. public void swap(int i,int j){...}
    10. }
    11. MyArray arr= new MyArray();
    12. arr.add( 1);
    13. arr.add( 2);
    14. arr.add( 3);
    15. arr.sort();
    16. arr.swap( 0, 1);
    17. arr.findMax();

    那么,我们就可以把对数组的所有操作都定义在这个MyArray类中,将来调用起来会很方便的

    所以,将数组和其相关操作进行类封装的过程称之为动态数组

     

    4.线性表的动态数组实现

    哈哈,结合线性表的定义和动态数组的概念,我们就可以真正开始写线性表的动态数组实现方式了

    4.1 创建ArrayList类并实现List接口

    
     
    1. public class ArrayList<E> implements List<E>{
    2. }

    至于List中的方法,稍后我们在一个个实现,别急

    4.2 成员变量

    对于线性表的动态数组实现而言,如果只封装一个数组数据够用吗?

    如上图所示,虽然数组data长度为10,但是只有5个元素存入到数组当中

    10很好表示,data.length即可

    5怎么表示呢?所以我们还需要维护一个记录线性表中有效元素个数的变量 size

    如下图所示

    小技巧提示,size不仅可以表示有效元素的个数,也可以表示在末尾添加元素时新元素的位置

    
     
    1. public class ArrayList<E> implements List<E>{
    2. private E[] data; //作为容器存储元素 data.length为最大容量
    3. private int size; //当前线性表中元素的个数-有效长度
    4. }

    4.3 构造函数

    可以让调用者创建一个指定容量大小的线性表,也可以创建一个默认容量大小的线性表

    
     
    1. public class ArrayList<E> implements List<E>{
    2. private E[] data; //作为容器存储元素 data.length为最大容量
    3. private int size; //当前线性表中元素的个数-有效长度
    4. private static final int DEFAULT_CAPACITY= 10; //默认容量为10
    5. //默认构造函数中创建一个默认容量的线性表
    6. public ArrayList(){
    7. this(DEFAULT_CAPACITY);
    8. }
    9. //构造函数中创建一个容量为capacity的线性表
    10. public ArrayList(int capacity){
    11. if(capacity< 0){
    12. capacity=DEFAULT_CAPACITY;
    13. }
    14. this.data=(E[]) new Object[capacity];
    15. this.size= 0;
    16. }
    17. }

    增删功能在后头,一会再说哈,先把几个简单的问题解决了~困难的放后头

    4.4 getSize()函数

    获取线性表中元素的个数

    直接返回size即可

    
     
    1. public int getSize() {
    2. return this.size;
    3. }

    4.5 isEmpty()函数

    判断线性表是否为空表

    直接判断size==0的结果即可

    
     
    1. public boolean isEmpty() {
    2. return this.size== 0;
    3. }

    4.6 get()函数

    获取线性表中指定角标index处的元素

    直接返回数组[index],注意角标越界问题

    
     
    1. public E get(int index) {
    2. if(index< 0||index>=data.length){
    3. throw new IllegalArgumentException( "角标不存在!");
    4. }
    5. return data[index];
    6. }

    4.7 getFirst()函数

    获取线性表中第一个元素

    复用get()函数

    
     
    1. public E getFirst() {
    2. return get( 0);
    3. }

    4.8 getLast()函数

    获取线性表中最后一个元素

    复用get()函数

    
     
    1. public E getLast(){
    2. return get(size- 1);
    3. }

    4.9 set函数

    修改线性表中指定角标index处的元素为新元素e

    
     
    1. public void set(int index, E e) {
    2. if(index< 0||index>=size){
    3. throw new IllegalArgumentException( "角标不存在!");
    4. }
    5. data[index]=e;
    6. }

    4.10 find()函数

    获取线性表中元素e从头到尾第一次出现的位置

    
     
    1. public int find(E e) {
    2. for( int i= 0;i<size;i++){
    3. if(data[i].equals(e)){
    4. return i;
    5. }
    6. }
    7. return - 1;
    8. }

    4.11 contains()函数

    判断线性表中是否包含指定元素e

    
     
    1. public boolean contains(E e) {
    2. return find(e)!=- 1;
    3. }

    4.12 clear()函数

    清空线性表

    简单粗暴

    
     
    1. public void clear() {
    2. this.data=(E[]) new Object[DEFAULT_CAPACITY];
    3. this.size= 0;
    4. }

    4.13 getCapacity()函数

    获取线性表的最大容量

    
     
    1. public int getCapacity(){
    2. return data.length;
    3. }

    4.14 swap()函数

    交换顺序表中指定角标i,j的两个元素

    
     
    1. public void swap(int i,int j){
    2. if(i< 0||i>=size||j< 0||j>=size){
    3. throw new IllegalArgumentException( "角标非法!");
    4. }
    5. E temp=data[i];
    6. data[i]=data[j];
    7. data[j]=temp;
    8. }

    好了,现在开始复杂的部分了,增删!其实也不难哈

    4.15 add()函数

    在线性表中指定角标index处插入元素e

    先别急着写代码,分析一下,添加元素主要分为三种情况

    • 在表头插入:index=0
    • 在表中插入:index∈(0,size)任意
    • 在表尾插入:index=size

    如果在表头插入元素,原先已存在的元素就得挨个后移,别忘了size++

    思路:另 i 从 size 开始,i 到角标 0 结束,每次将 i-1 的元素赋予 i ,完毕后将新元素加入角标0 如下图所示

    如果在表中插入元素,基本思路和上述一直,插入位置 index 之后的元素就得挨个后移,别忘了size++

    思路:另 i 从 size 开始,i 到角标 index 结束,每次将 i-1 的元素赋予 i ,完毕后将新元素加入角标 index 如下图所示

    如果在表尾插入元素,直接把元素放入size位置,size++即可,此处无图,自己想

    其实三者插入方式都是一个意思的,完全可以按照一个思路写,只不过表尾插入不需要循环,可以直接插入即可,代码如下

    
     
    1. public void add(int index, E e) {
    2. if(index< 0||index>size){
    3. throw new IllegalArgumentException( "角标非法!");
    4. }
    5. if(size==data.length){
    6. resize(data.length* 2);
    7. }
    8. for( int i=size;i>index;i--){
    9. data[i]=data[i- 1];
    10. }
    11. data[index]=e;
    12. size++;
    13. }
    14. private void resize(int newLen) {
    15. E[] newData=(E[]) new Object[newLen];
    16. for( int i= 0;i<Math.min(data.length,newData.length);i++){
    17. newData[i]=data[i];
    18. }
    19. data=newData;
    20. }

    有同学会发现,这里怎么还多了个resize函数呢?

    其实这个函数是为了实现数组的自动扩容和缩容功能的

    如果元素填满了数组( size==data.length),此时就要需要考虑数组该扩容了,一般扩容为原先的2倍,如图所示

    思路:创建一个比原先数组大2倍的新数组,然后将老数组中的值挨个放入到新数组中,最后新数组替代老数组即可

    恩,在任意位置添加元素讲完了

    4.16 addFirst()函数

    在线性表中第一个位置插入元素e

    复用add()即可

    
     
    1. public void addFirst(E e) {
    2. add( 0,e);
    3. }

    4.17 addLast()函数

    在线性表中最后一个位置插入元素e

    复用add()即可

    
     
    1. public void addLast(E e) {
    2. add(size,e);
    3. }

    4.18 remove()函数

    删除并返回线性表中指定角标index处的元素

    哈哈,此处的删除也分为删除表头,删除表中,和删除表尾

    此处我就不给出演示图了,希望大家自己可以动手画一画

    删除表头思路:先取出要删除的元素,然后另 i 从 0 开始,到size-2结束,将 i+1 的元素赋予 i  即可,最后 size--

    删除表中思路:先取出要删除的元素,然后另 i 从 index 开始,到size-2结束,将 i+1 的元素赋予 i  即可,最后 size--

    删除表尾思路:直接size--即可

    此处的重点在于,删除元素之后,可能有缩容的情况,什么时候缩容呢,当 size==data.length/4 时缩容

    为什么是除以4,而不是除以2呢?

    如果是 size==data.length/2 时缩容,大家可以考虑一个问题,如果新加元素之后满了,扩容;接着删除元素之后,size到达length的一半,缩容;这样子的话我们的线性表是不是太“勤快”了些呢?是的,这样子的话会影响效率,所以删除元素之后,就算size到达length的一半,别急着缩,让它再删几个,删到足够少的时候再缩容,为时也不晚,一般设置在1/4处即可;这样子就避免了缩的太勤的问题。

    还有就是,如果已达到默认容量的话,则不需要再缩了

    
     
    1. public E remove(int index) {
    2. if(index< 0||index>=size){
    3. throw new IllegalArgumentException( "角标非法!");
    4. }
    5. E res=data[index];
    6. for( int i=index;i<size- 1;i++){
    7. data[i]=data[i+ 1];
    8. }
    9. size--;
    10. if(size==data.length/ 4&&data.length>DEFAULT_CAPACITY){
    11. resize(data.length/ 2);
    12. }
    13. return res;
    14. }

    4.19 removeFirst()函数

    删除并返回线性表中第一个元素

    复用remove()即可

    
     
    1. public E removeFirst() {
    2. return remove( 0);
    3. }

    4.20 removeLast()函数

    删除并返回线性表中最后一个元素

    复用remove()即可

    
     
    1. public E removeLast() {
    2. return remove(size- 1);
    3. }

    4.21 removeElement()函数

    删除线性表中指定元素e

    先找,再删

    
     
    1. public void removeElement(E e) {
    2. int index=find(e);
    3. if(index!=- 1){
    4. remove(index);
    5. }
    6. }

     

    欧克,好啦,到这里线性表的动态数组实现方式讲完了,大家再接再厉,附上完整代码

    ArrayList.java

    
     
    1. /**
    2. @Author Teacher_HENG
    3. */
    4. //动态数组实现的线性表->顺序表
    5. public class ArrayList<E> implements List<E>{
    6. private E[] data; //作为容器存储元素 data.length为最大容量
    7. private int size; //当前线性表中元素的个数-有效长度
    8. private static final int DEFAULT_CAPACITY= 10; //默认容量为10
    9. //默认构造函数中创建一个默认容量的线性表
    10. public ArrayList(){
    11. this(DEFAULT_CAPACITY);
    12. }
    13. //构造函数中创建一个容量为capacity的线性表
    14. public ArrayList(int capacity){
    15. if(capacity< 0){
    16. capacity=DEFAULT_CAPACITY;
    17. }
    18. this.data=(E[]) new Object[capacity];
    19. this.size= 0;
    20. }
    21. //将传入数组封装成动态数组
    22. public ArrayList(E[] arr){
    23. data=(E[]) new Object[arr.length];
    24. for( int i= 0;i<data.length;i++){
    25. data[i]=arr[i];
    26. }
    27. size=arr.length;
    28. }
    29. public void add(int index, E e) {
    30. if(index< 0||index>size){
    31. throw new IllegalArgumentException( "角标非法!");
    32. }
    33. if(size==data.length){
    34. resize(data.length* 2);
    35. }
    36. for( int i=size;i>index;i--){
    37. data[i]=data[i- 1];
    38. }
    39. data[index]=e;
    40. size++;
    41. }
    42. public void addFirst(E e) {
    43. add( 0,e);
    44. }
    45. public void addLast(E e) {
    46. add(size,e);
    47. }
    48. public E remove(int index) {
    49. if(index< 0||index>=size){
    50. throw new IllegalArgumentException( "角标非法!");
    51. }
    52. E res=data[index];
    53. for( int i=index;i<size- 1;i++){
    54. data[i]=data[i+ 1];
    55. }
    56. size--;
    57. if(size==data.length/ 4&&data.length>DEFAULT_CAPACITY){
    58. resize(data.length/ 2);
    59. }
    60. return res;
    61. }
    62. public E removeFirst() {
    63. return remove( 0);
    64. }
    65. public E removeLast() {
    66. return remove(size- 1);
    67. }
    68. @Override
    69. public void removeElement(E e) {
    70. int index=find(e);
    71. if(index!=- 1){
    72. remove(index);
    73. }
    74. }
    75. private void resize(int newLen) {
    76. E[] newData=(E[]) new Object[newLen];
    77. for( int i= 0;i<Math.min(data.length,newData.length);i++){
    78. newData[i]=data[i];
    79. }
    80. data=newData;
    81. }
    82. public int getSize() {
    83. return this.size;
    84. }
    85. public boolean isEmpty() {
    86. return this.size== 0;
    87. }
    88. public E get(int index) {
    89. if(index< 0||index>=data.length){
    90. throw new IllegalArgumentException( "角标不存在!");
    91. }
    92. return data[index];
    93. }
    94. public E getFirst() {
    95. return get( 0);
    96. }
    97. public E getLast(){
    98. return get(size- 1);
    99. }
    100. public void set(int index, E e) {
    101. if(index< 0||index>=size){
    102. throw new IllegalArgumentException( "角标不存在!");
    103. }
    104. data[index]=e;
    105. }
    106. public int find(E e) {
    107. for( int i= 0;i<size;i++){
    108. if(data[i].equals(e)){
    109. return i;
    110. }
    111. }
    112. return - 1;
    113. }
    114. public boolean contains(E e) {
    115. return find(e)!=- 1;
    116. }
    117. public int getCapacity(){
    118. return data.length;
    119. }
    120. public void clear() {
    121. this.data=(E[]) new Object[DEFAULT_CAPACITY];
    122. this.size= 0;
    123. }
    124. public void swap(int i,int j){
    125. if(i< 0||i>=size||j< 0||j>=size){
    126. throw new IllegalArgumentException( "角标非法!");
    127. }
    128. E temp=data[i];
    129. data[i]=data[j];
    130. data[j]=temp;
    131. }
    132. }

     

    展开全文
  • 本文主要总结常用的数据结构——线性表数组实现实现基本运算功能,不涉及完整功能,目的是为了熟悉常用数据结构特性和代码实现底层原理。 一、线性表——数组Array 1.1线性表定义 从逻辑上来看,线性表就是有n(n...

    本文主要总结常用的数据结构——线性表之顺序数组,实现其基本的增删查改功能,不涉及完整功能,目的是为了熟悉常用数据结构属性和代码实现底层原理。

    一、线性表——顺序数组seqList

    1.1线性表定义

    从逻辑上来看,线性表就是有n(n>=0)个数据元素a1,a2,…,an组成的有限序列。
    对于一个非空的线性表,其逻辑结构特征如下:

    • 有且仅有一个开始结点a1和一个直接后继节点a2,没有直接前驱节点,;
    • 有且仅有一个终止节点an和一个直接前驱节点a*(n-1)*,没有直接后继节点;
    • 其余的内部节点ai (2 <= i <= n-1)都有且仅有一个直接前驱节点a*(i-1)和一个直接后继节点a(i+1)*;
    • 对于同一个线性表,各数据元素ai必须具有相同的数据类型,即同一线性表中各数据元素具有相同的类型,每个数据元素长度相同。

    1.2线性表的基本运算

    1.2.1基本运算

    (1) 初始化(构造一个空的线性表,也就是new或者用堆栈创建一个元素的数组)
    (2) 计算表长(线性表节点个数)
    (3) 插入节点(插入当前位置,其它元素依次外后移动一位)
    (4) 删除节点(删除当前节点元素,其它元素依次往前移动一位)
    (5) 查找节点(返回查找到的第一个节点地址)
    (6) 修改节点(先查找,然后再替换该位置元素)
    简单来说,就是实现顺序表的初始化、元素的增删查改。

    1.3线性表结构(顺序表)

    图1-1  顺序表结构图
    图1-1 顺序表结构图

    1.4代码实现

    common.h

    #pragma once
    
    typedef short int BYTE;
    typedef unsigned int WORD32;
    

    Element.h

    #pragma once
    
    #include "common.h"
    
    class Element
    {
    public:
    	Element();
    	Element(BYTE key, WORD32 value);
    	~Element();
    
    	BYTE getKey() const;
    	WORD32 getValue() const;
    
    private:
    	BYTE key;
    	WORD32 value;
    };
    

    SeqList.h

    #pragma once
    #include <string>
    #include "Element.h"
    
    using namespace std;
    
    class SeqList
    {
    public:
    	SeqList(WORD32 capability);
    	~SeqList();
    	const WORD32 getSize() const; // 返回当前实际元素个数
    	const WORD32 getCapability() const; // 返回当前最大容量
    	bool add(Element& element); // 加入元素
    	bool insert(WORD32 index, Element& element); // 插入元素
    	bool remove(WORD32 index); //删除元素
     	Element* find(const WORD32 index) const; // 查找元素,按索引位置
    	Element* find(const BYTE key) const; // 按元素关键字查找
    	bool repalce(WORD32 index, Element& element); // 修改指引索引位置元素
    	void showAllElements() const;
    
    private:
    	Element *element; // 指向元素数组指针
    	WORD32 size; // 实际元素个数
    	WORD32 capability; // 最大容量
    };
    

    Element.cpp

    #include "Element.h"
    #include <iostream>
    
    Element::Element(BYTE key, WORD32 value)
    	: key(key), value(value)
    {
    }
    
    Element::Element() : key(0), value(0)
    {
    }
    
    Element::~Element()
    {
    	static int count = 0;
    	//std::cout << "Element::~Element() count:" << count++ << std::endl;
    }
    
    BYTE Element::getKey() const
    {
    	return key;
    }
    
    WORD32 Element::getValue() const
    {
    	return value;
    }
    
    

    SeqList.cpp

    #include "SeqList.h"
    #include <iostream>
    
    using namespace std;
    
    SeqList::SeqList(WORD32 capability)
    	: element(nullptr)
    	,size(0)
    	, capability(capability)
    {	
    	if (capability == 0)
    	{
    		return;
    	}
    	element = new(std::nothrow) Element[capability]; // 初始化,构建一个空的顺序表
    	if (element == nullptr)
    	{
    		cout << "new err!" << endl;
    		throw;
    	}
    }
    
    SeqList::~SeqList()
    {
    	if (element != nullptr)
    	{
    		delete[] element;
    	}
    }
    
    const WORD32 SeqList::getSize() const
    {
    	return size;
    }
    
    const WORD32 SeqList::getCapability() const
    {
    	return capability;
    }
    
    bool SeqList::add(Element& element)
    {
    	if (size == capability)
    	{
    		cout << "add failed for size equal capability, bad add element! size == capability == " 
    			<< size << endl;
    		return false;
    	}
    	this->element[size++] = element;
    	return true;
    }
    
    bool SeqList::insert(WORD32 index, Element& element)
    {	
    	if (size == capability)
    	{
    		cout << "insert failed for size equal capability, ban insert element! size == capability == " 
    			<< size << "  index:" << index << endl;
    		return false;
    	}
    	if (index > size) // 大于最大元素个数加一后的值,插入失败
    	{
    		cout << "insert failed for invalid index == " << index << endl;
    		return false;
    	}
    	for (auto i = size; i >= index; --i)
    	{
    		if (i == index)
    		{
    			this->element[i] = element;
    			break;
    		}
    		this->element[i] = this->element[i-1]; // 从插入位置开始,数组后面元素依次往右移动一位
    	}
    	++size;
    	return true;
    }
    
    bool SeqList::remove(WORD32 index)
    {
    	if (index >= size) // 大于最大元素个数,删除失败
    	{
    		cout << "remove failed for invalid index:" << index << endl;
    		return false;
    	}
    	for (auto i = index; i < size; ++i)
    	{
    		element[i] = element[i+1]; // 删除位置开始,数组后面元素依次往左移动一位
    	}
    	--size;
    
    	return true;
    }
    
    Element* SeqList::find(const WORD32 index) const
    {
    	if (index >= size) // 大于最大元素个数,查找失败
    	{
    		cout << "find failed for invalid index:" << index << endl;
    		return nullptr;
    	}
    	return &element[index];
    }
    
    Element* SeqList::find(const BYTE key) const
    {
    	for (auto i = 0; i < size; ++i)
    	{
    		if (key == this->element[i].getKey())
    		{
    			return &this->element[i];
    		}
    	}
    
    	cout << "find failed for invalid elementKey:" << key << endl;
    	return nullptr;
    }
    
    bool SeqList::repalce(WORD32 index, Element& element)
    {
    	if (index >= size) // 大于最大元素个数,修改失败
    	{
    		cout << "replace failed for invalid index:" << index << endl;
    		return false;
    	}
    	this->element[index] = element;
    	return true;
    }
    
    void SeqList::showAllElements() const
    {
    	for (auto i = 0; i < size; ++i)
    	{		
    		cout << "key == " << element[i].getKey()
    			<< "  value == " << element[i].getValue()
    			<< "  size == " << size
    			<< "  capability == " << capability << endl;
    	}
    }
    
    

    main.cpp

    #include <iostream>
    #include "Element.h"
    #include "SeqList.h"
    
    using namespace std;
    
    int main(int argc, char* argv[])
    {
    	Element* element0 = new Element(0, 0);
    	Element* element1 = new Element(1, 1);
    	Element* element2 = new Element(2, 2);
    	Element* element3 = new Element(3, 3);
    	Element* element4 = new Element(4, 4);
    	Element* element5 = new Element(5, 5);
    	SeqList* seqList = new SeqList(5);
    	cout << "size==" << seqList->getSize() << endl; // size == 0
    	cout << "capability == " << seqList->getCapability() << endl; // getCapability == 1024
    	
    	cout << "\n---------------测试add函数------------------" << endl;
    	cout << "after add Elements num == 4" << endl; // after add Elements num == 4
    	seqList->add(*element0);
    	seqList->add(*element1);
    	seqList->add(*element2);
    	seqList->add(*element3);	
    	cout << "size==" << seqList->getSize() << endl; // size == 4
    	cout << "getCapability==" << seqList->getCapability() << endl; // getCapability == 1024
    	seqList->showAllElements();
    
    	cout << "\n---------------测试insert函数------------------" << endl;
    	cout << "after insert Elements num == 2" << endl;
    	seqList->insert(0, *element4); // 插入成功,插入到第0个元素位置
    	seqList->insert(2, *element5); // 插入失败,达到最大容量5后禁止插入
    	cout << "size==" << seqList->getSize() << endl; // size == 6
    	cout << "getCapability==" << seqList->getCapability() << endl; // getCapability == 1024
    	seqList->showAllElements();
    
    	cout << "\n---------------测试find(index)函数------------------" << endl;
    	const WORD32 index = 1;
    	const auto* sl = seqList->find(index);
    	cout << "key == " << sl->getKey() << "  value == " << sl->getValue() << endl;
    
    	cout << "\n---------------测试find(key)函数------------------" << endl;
    	const BYTE key = 3;
    	sl = seqList->find(key);
    	cout << "key == " << sl->getKey() << "  value == " << sl->getValue() << endl;
    
    	cout << "\n---------------测试repalce(key)函数------------------" << endl;
    	seqList->repalce(index, *element0);
    	sl = seqList->find(index);
    	cout << "key == " << sl->getKey() << "  value == " << sl->getValue() << endl;
    
    	cout << "\n---------------测试remove函数------------------" << endl;
    	seqList->remove(index);
    	seqList->showAllElements();
    
    	delete element0;
    	delete element1;
    	delete element2;
    	delete element3;
    	delete element4;
    	delete element5;
    	delete seqList;
    
    	getchar();
    	return 1;
    }
    

    1.5输出结果

    图1-2  不开析构函数打印图
    图1-2 不开析构函数打印图
    在这里插入图片描述
    在这里插入图片描述
    图1-2 打开析构函数打印图

    参考内容

    C++ 数据结构线性表-数组实现

    数据结构之线性表—数组实现(C++)

    哔哩哔哩 P2 2.顺序表结构

    《数据结构、算法与应用 C++语言描述》 [美] 萨特吉-萨尼(Sartaj Sahni)著. 王立柱 刘志红译 page:92-112

    展开全文
  • 线性表的就地逆置(数组实现+链表实现

    头插法且头节点为空的链表的就地逆置方法

    void Reverse_l(LinkList &L){
        LinkList p=L->next;
        L->next = NULL;
        while (p!=NULL) {
            LinkList r=p->next;
            p->next=L->next;
            L->next=p;
            p=r;
        }
    }
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    
    using namespace std;
    
    typedef struct Node{
        int data;
        struct Node *next;
    }Node, *LinkList;
    
    void insert1(int *a, LinkList &head, int elenum)
    {
        LinkList p1 = head;
        LinkList p2;
        for (int i = 1; i <= elenum; i++) {
            scanf ("%d", &a[i]);
            p2 = (LinkList)malloc(sizeof(Node));
            p2->data = a[i];
            p1->next = p2;
            p1 = p2;
        }
        p2->next = NULL;
    }
    
    void transform1(int *a, int elenum)
    {
        for (int i = 1; i <= elenum / 2; i++) {
            int t = a[i];
            a[i] = a[elenum - i + 1];
            a[elenum - i + 1] = t;
        }
    }
    
    void Reverse_l(LinkList &L){
        LinkList p=L->next;
        L->next = NULL;
        while (p!=NULL) {
            LinkList r=p->next;
            p->next=L->next;
            L->next=p;
            p=r;
        }
    }
    
    void print1(int *a, LinkList head, int elenum)
    {
        for (int i = 1; i <= elenum; i++) {
            printf ("%d ", a[i]);
        }
        printf ("\n");
        LinkList p = head->next;
        while (p != NULL) {
            printf ("%d ", p->data);
            p = p->next;
        }
        printf ("\n");
    }
    
    void CreatList_head(LinkList &head, int elenum)
    {
        head = (LinkList)malloc(sizeof(LinkList));
        head->next = NULL;
    }
    
    int main()
    {
        int elenum;
        scanf ("%d", &elenum);
        int a[elenum + 1];
        LinkList head;
        CreatList_head (head, elenum);
        insert1 (a, head, elenum);
        transform1 (a, elenum);
        Reverse_l (head);
        print1 (a, head, elenum);
        return 0;
    }
    
    展开全文
  • 数据结构 线性表 数组(顺序) 链表(链式)

    talking:这里会先介绍线性表,一种最简单的储存方式 。


    一、线性表

    1. 定义:零个或多个元素的有限序列;

    一对一的关系构成线性表;

    即有头有尾,前后相接,只有一条链;

    在较复杂的线性表中,一个数据元素通常由多个数据项组成,这里的线性表一般建立在结构体的基础上

    2. 重要属性:
    • 直接前继元素
    • 直接后继元素
    • 线性表的长度n:线性表元素的个数
    • 空表(n=0)
    3.储存方式:
    • 顺序储存结构:数组

    • 链式储存结构:链表

    这两种都只的是在内存中的物理存储方式;

    4.抽象数据类型
    • 数据类型:性质相同的值的集合以及定义在这个集合上的操作的总称;

    二、数组(线性表的顺序储存结构)

    此处强调数据结构的线性表,故只介绍一维数组。

    1.概述:
    • 定义:用一段地址连续的存储单元依次存储线性表的数据元素;

    • 特点:在内存中占据连续的储存空间;在插入等算法中需移动大量数据,效率较低

    • 三个必要属性:

      • 储存空间的起始位置
      • 线性表的最大存储容量
      • 线性表的当前长度
    • 线性表长度<=数组长度

    • 存取时间性能为O(1),为随机存储结构

    2.算法:创建、读取、插入、删除

    记得对数组是否为空/满进行检验(要不检验空要不检验满,依该函数实际而定,例如:读取,删除时检验其是否为空,插入时检验其是否为满)

    可以注意算法对数据元素的位置处在表尾的处理
    以插入函数为例:

    //初始化线性表
    typedef struct{
    	int data[maxsize];      //假装最多能放下maxsize个元素(数组长度)
    	int length;    			//线性表长度,表示当前已经使用的长度
    }list;
    //然后假装线性表里面存放了数据
    //插入函数:现将e插入到第i个元素的位置
    int listInsert(list *l,int i,int e){  //l为数组首地址
    	int j;
    	if(l->length==maxsize){    //注意,这个地方不能直接写length,此时表示线性表已满时
    		return 0;
    	}
    	if(i>l->length-1 || i<1){   //i不在范围内时
    		return 0;
    	}
    	if(i<l->length-1){     //i不在末尾时
    		for(j=l->length-1;j>=i;j--){
    			l->data[j+1]=l->data[j];
    		}
    	}
    	l->data[i]=e;    //把这个值赋值给第i个元素
    	l->length++;
    	return 1;
    }
    

    可以看到该算法重复度很少,效率较高。


    三、链表(线性表的链式储存结构)

    1.概述:
    • 定义:在内存中的储存位置并不连续,靠指针的作用将其一个一个串起来,形成一个链式结构;

    • 特点:在内存中不占据连续的储存空间;整体效率较高,插入等算法中只需要简单的修改指针域的值;

    • 属性:

      • 指针域:存放指针的区域,可以有一个两个或者多个
      • 数据域:存放数据的区域
      • 结点:指针域和数据域共同构成一个结点,很多结点相连构成一个链表
      • 头结点:在第一个结点之前,其指针域里的指针指向第一个结点,对于链表来说它不是必须存在的。
      • 头指针:头指针不是头结点里面的指针!如果头结点存在,则指向头结点;如果没有头结点,则指向第一个结点,对于链表来说它必须存在。
    2.单链表
    • 简单来说,其特点为:尾结点指向NULL或^,指针域中只有指向下一个结点的指针;

    • 算法:读取、插入、删除、整表创建、整表删除;

      需要注意的地方:

      • 单链表的插入时,在所有检验语句之后,即判断确定可以插入时再为新结点申请内存空间(使用malloc()函数);
      • 单链表的删除中效率更高的方法是以要删除的前一个结点为主,用p->next->next指向要删除的后一个结点(假设p是要删除的结点);
      • 删除时注意删除语句的顺序,记得用free()让系统收回一个结点,释放内存;
      • 整表创建包括头插法、尾插法,使用malloc()函数;
      • 整表删除时记得对已释放的结点的指针域的替代与保存,以便下一个结点的删除
    //单链表的整表删除,初始条件:线性表l已存在且有头节点;
    int Clearlist (linklist *l){   //l为头指针;
    	linklist p,q;
    	p=(*l)->next;   //p指向第一个结点
    	while(p!=NULL){
    		q=p->next;     //用q暂时存储下一个结点,防止在释放p的空间后找不到下一个结点
    		free(p);
    		p=q;
    	}
    	(*l)->next=NULL;
    	return 1;
    }
    
    • 在实际编程时,每个块都要记得对链表是否为空/满进行检验(要不检验空要不检验满,依该函数实际而定,例如:读取,删除时检验其是否为空,插入时检验其是否为满)
    • 注意检验语句的先后顺序,尽量使其效率最高,时间复杂度最低。
    • 要经常检查头指针是否为NULL,避免其初始化失败或者传值失败。

    这里有自己做的一个 家庭财务管理系统 的实例,当时没有学数据结构,代码的层次等也不是很清晰,没有使用free()语句,但是对于链表的实际应用也有参考意义。
    地址如下:https://blog.csdn.net/qq_44263261/article/details/95222343

    3.静态链表(数组和链表的转化)
    • 静态链表实际是用数组来描述链表,也被称为游标实现法

    • 也有其类似于单链表的插入、删除等算法,实际应用中基本不用,但可以以之拓展链表的应用,更好的理解链表的算法。

    • 其算法最关键的部分在于

      • 将数组每个元素像结点那样分成两个部分,储存数据和下一个元素的地址;
      • 将已用的部分和未用的部分分别当作两个链表;
    4.循环链表
    • 最后一个结点的指针域存放的是第一个结点的地址,相当于将其首尾相连
    • 小技巧:如果第一个结点和尾结点的地址都需要知道,可以将头指针指向尾结点,可以大大增加效率;
    5.双向链表
    • 指针域有两个指针,分别指向前一个结点和后一个结点
    • 用空间来换取时间
    展开全文
  • 线性表的定义:线性表中数据元素之间的关系是一对一的关系,即除了第一元素没有前驱,最后一元素没有后继之外,其余元素既有唯一前驱和唯一后继,如下图所示 搞懂什么是线性表之后,我们再考虑一问题,...
  • 线性表中数据元素之间的关系是一对一的关系,即除了第一和最后一数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑结构简单,便于实现和操作。因此,线性表这种数据结构实际应用是广泛采用的一种数据...
  • 答:数组是一种线性表结构。用一组连续的内存空间来保存类型一致的数据。 例如 Java 定义 int[] arr = new int[5]; 问:如何实现随机访问? 答:两概念 1. 线性表数组、链表、栈、队列 2. 连续的内存空间...
  • 链表会需要更多一点的空间,因为不仅要存储数据,而且要存储下一个节点的地址,所以需要消耗一些额外存储下一个节点的空间 数组是元素是多少那么整个需要开辟的空间就是多少,不需要开辟额外的空间 ② 新增元素...
  • 目录 一、线性表 二、数组 2.1、动态数组 简单动态数组实现: 三、链表 简单单向链表实现: 双向链表 循环链表 一、线性表 package ... //返回线性表的大小 ... //判断线性表中是...
  • //栈内存分配一指针变量,该变量占用空间大小为4字节 //他的值并没有被初始化。 new = malloc(sizeof(*new)); //如果分配地址空间成功的话。那么将有如下: //堆分配一DARR结构大小的...
  • 线性表是一种线性结构,他是具有相同类型的n个数据元素组成的有限序列(n&gt;=0)。 线性表包括:数组、单链表、双链表。 1.数组数组有上界和下界,数组的数据上下界内是连续的。  特点:数据是连续的,...
  • 线性表是一种十分基础且重要的数据结构,它主要包括以下内容: 数组 链表 队列 栈 接下来,我将对这四种数据结构做一详细的总结,...但与此同时却使得在数组中删除,插入数据需要大量的数据搬移工作。 低效的“插
  • 今天又是学习数据结构的一天。(mooc浙大数据结构的重点笔记) ...List MakeEmpty():初始化一线性表L。 ElementType FindKth(int k, List L):根据位序k,返回相应的元素; int Find(Elemen...
  • 文章目录线性表数组实现线性表Java实现 数据结构是以某种形式将数据组织一起的集合,它不仅存储数据,还支持访问和处理数据的操作。 线性表 逻辑结构: 线性表是最常用且最简单的一种数据结构,它是n个数据元素...
  • /** ADT线性表接口 * 线性表的元素位置从1开始 */ public interface ListInterface{ /** Task:往线性表的末尾插入新元素 * @param newEntry 做为新元素插入的对象 * @return 如果插入成功则返回true,否则...
  • 线性结构[把所有的结点用一线穿起来]...连续存储[线性表(数组)] 什么叫数组? 元素类型相同,大小相等 确定一个数组需要几参数? 数组的大小 数组有效存储量 数组首地址 数组的优缺点(相对于链表)? ...
  • 摘自:... 前言:  引用和指针来实现链表的各种操作 代码: #include #include typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *n
  • 顺序表是计算机内存数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是...
  • 线性表及其实现

    2019-08-27 20:31:55
    数据对象集:n个元素的构成的有序序列(n=>0) 操作集:L ∈ List,X ∈ ElementType,整线性表的基本操作主要有:(如下) /* 线性表的基本操作*/ List MakeEmpty();//初始化一空的线性表 ElementType ...
  • 2、熟练运用掌握的线性表的操作,实现一元n次多项式的加法运算并明确规定: 输入的形式:用户输入多项式(eg:3x2 +1x1+5和1x1 +6) 输入范围:任意正整数系数、降幂排列的多项式 输出的形式:多项式相加和(eg:3...
  • 数组线性表数据结构 顺序存储 的具体实现。用一组 连续 的内存空间,存储 相同类型 的数据 链表 是线性表数据结构 链式存储的具体实现。用 节点 的 指针 把各个节点串联一起 数组的基本操作 指定位置...
  • 数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。 连续的内存空间和相同类型的数据(随机访问的前提) 优点:两限制使得具有随机访问的特性缺点:删除,插入数据效率低 ...
  • 线性表实现

    2013-12-19 16:59:44
    顺序线性表实现 import java.util.Arrays; public class SequenceList { private int DEFAULT_SIZE = 16;... // 定义一个数组用于保存顺序线性表的元素 private Object[] elementData; // 保存顺序表元素的当
  • 线性表的定义 线性表(List):零或多数据元素的有限序列。...最后线性表中的数据元素必须是相同类型。 如果用数据语言来定义,可如下(配合下图理解): 数学语言定义: 若将线性表记为(a1...
  • 用链表实现链表的每结点存储多项式的一非零项,包括系数指数两数据域以及一指针域。 线性表的抽象数据类型描述 类型名称:线性表(List) 数据对象集:线性表元素构成的有序序列 操作集:...
  • 线性表 C语言实现

    千次阅读 2013-11-27 15:28:18
    // 线性表的顺序存储结构的操作实现 #include #include typedef int ElemType; //定义元素类型 struct List //定义单链表结点类型 { ElemType *list;//存储空间基址 int size; //当前长度 int MaxSize; //当前...
  • 线性表一、定义二、引用传参"&"(重点) 一、定义 二、引用传参"&...ListInsert(L,i,e)表示执行表L的第i元素增加e这操作,然后回滚。 ListInsert(&L,i,e)表示执行增加操作后然后提交。 ...
  • 在线性表的使用,我们需要实际估计表的大小以动态申请空间足够的的数组容量,由于稳妥起见,一般都需要将空间估算得大一些,所以就导致了空间浪费,这也是它的一比较严重的缺点。但是,一些比较小的地方并且...
  • 问题的解决肯定是要先排序的,然后再定位;
  • 1.一元多项式的表示 ...用指数,系数构成的结构存储在数组 struct Num{ int a;//系数 int b;//指数 }num[n];//n为非0项aix^x的个数 //按指数大小有序存储 c.链表结构存储非零项 typedef struct PolyNode *Pol

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,680
精华内容 6,672
关键字:

在n个节点的线性表的数组实现中