判断顺序表为空的条件

顺序表判断表满的条件
2016-05-27 09:22:26
课本上判断表满是if(last==maxsize-1) //last 是最后一个元素的下标，maxsize是表最大可容纳元素的个数是否可以替换为if(isFull()==true)？//isFull是判断表是否满的共有成员函数，如果满的话返回true
收起
c++

java数据结构与算法之顺序表与链表深入分析

万次阅读 多人点赞 2016-11-05 16:24:30

开篇直接奔主题，无论是顺序表还是链表，它们都是线性表的一种，用比较官方的话来讲，线性表是其组成元素间具有线性关系的一种线性结构，而我们恰好可以采用顺序存储和链式存储结构来表示线性表。接下来将从以下几点...


  转载请注明出处（万分感谢！）：  
http://blog.csdn.net/javazejian/article/details/52953190 

  出自【zejian的博客】


关联文章:

java数据结构与算法之顺序表与链表设计与实现分析 
java数据结构与算法之双链表设计与实现 
java数据结构与算法之改良顺序表与双链表类似ArrayList和LinkedList（带Iterator迭代器与fast-fail机制） 
java数据结构与算法之栈（Stack）设计与实现 
java数据结构与算法之队列(Queue)设计与实现 
java数据结构与算法之递归思维(让我们更通俗地理解递归) 
java数据结构与算法之树基本概念及二叉树（BinaryTree）的设计与实现 
java数据结构与算法之平衡二叉查找树(AVL树)的设计与实现

  数据结构与算法这门学科虽然在大学期间就已学习过了，但是到现在确实也忘了不少，因此最近又重新看了本书-《数据结构与算法分析》加上之前看的《java数据结构》也算是对数据结构的进一步深入学习了，于是也就打算写一系列的数据结构的博文以便加深理解，这些博文涵盖了自己对数据结构与算法的理解也包含了这类书籍的基础内容，所以博文中会包含书中的一些概念的引用段落，看到时也不必惊讶，本篇是开篇，主要涵盖顺序表与链表的知识点，关于顺序表与链表将会分两篇博文记录，而本篇将从以下几点出发分析线性表的设计与实现。


线性表抽象数据类型概述
线性表的顺序存储设计与实现顺序表1 顺序存储结构的设计原理概要
2 顺序存储结构的实现分析
3 顺序存储结构的效率分析

线性表的链式存储设计与实现链表1 链表的链式存储结构设计原理概要
2 单链表的储结构实现分析
3 带头结点的单链表以及循环单链表的实现带头结点的单链表
循环单链表

4 单链表的效率分析







1.线性表抽象数据类型概述

  首先来说明一下什么是抽象数据类型，我们都知道java在默认情况下，所有的基本数据类型(int,float,boolean等)都支持基本运算，如加减法，这是因为系统已帮我们实现了这些基本数据类型的的基本运算。而对于自定义的数据类型(如类)也需要定义相应的运算，但在实际使用这些自定义的数据类型的运算时需要自己实现相关的运算，也就是说用户自定义的数据类型的运算需要我们自己利用系统提供的基本运算来定义和实现。这些自定义了数据结构(如自定义类)和包含相关运算组合实现的数据类型就称其为抽象数据类型(ADT,Abstract Data Type),因此一个ADT会包含数据声明和运算声明。常用的ADT包含链表、栈、队列、优先队列、二叉树、散列表、图等，所以接下来我们要分析的顺序表和链表也属于ADT范畴。下面引用自java数据结构一书对线性表的定义：


    线性表是由n(n>=0)个类型相同的数据元素a₀,a₁,…,a_n-1组成的有限的序列，在数学中记作(a₀,a₁,…,a_n-1)，其中a_i的数据类型可以是基本数据类型(int,float等)、字符或类。n代表线性表的元素个数，也称其为长度(Length)。若n=0，则为空表；若n > 0，则a_i(0 < i < n-1)有且仅有一个前驱(Predecessor)元素a_i-1和一个后继(Successor)元素a_i+1，a₀没有前驱元素，a_i没有后继元素。


以上便是对线性表抽象数据类型概述，下面我们开始分别针对顺序表和链表进行深入分析。



2.线性表的顺序存储设计与实现（顺序表）



2.1 顺序存储结构的设计原理概要

  顺序存储结构底层是利用数组来实现的，而数组可以存储具有相同数据类型的元素集合，如int，float或者自定义类型等，当我们创建一个数组时，计算机操作系统会为该数组分配一块连续的内存块，这也就意味着数组中的每个存储单元的地址都是连续的，因此只要知道了数组的起始内存地址就可以通过简单的乘法和加法计算出数组中第n-1个存储单元的内存地址，就如下图所示： 


  通过上图可以发现为了访问一个数组元素，该元素的内存地址需要计算其距离数组基地址的偏移量，即用一个乘法计算偏移量然后加上基地址，就可以获得数组中某个元素的内存地址。其中c代表的是元素数据类型的存储空间大小，而序号则为数组的下标索引。整个过程需要一次乘法和一次加法运算，因为这两个操作的执行时间是常数时间，所以我们可以认为数组访问操作能再常数时间内完成，即时间复杂度为O(1)，这种存取任何一个元素的时间复杂度为O(1)的数据结构称之为随机存取结构。而顺序表的存储原理正如上图所示，因此顺序表的定义如下（引用）：


    线性表的顺序存储结构称之为顺序表(Sequential List),它使用一维数组依次存放从a₀到a_n-1的数据元素(a₀,a₁,…,a_n-1)，将a_i(0< i <> n-1)存放在数组的第i个元素，使得a_i与其前驱a_i-1及后继a_i+1的存储位置相邻，因此数据元素在内存的物理存储次序反映了线性表数据元素之间的逻辑次序。




2.2 顺序存储结构的实现分析

  接着我们来分析一下顺序表的实现，先声明一个顺序表接口类ISeqList<T>，然后实现该接口并实现接口方法的代码，ISeqList接口代码如下：



package com.zejian.structures.LinkedList;

/**
 * Created by zejian on 2016/10/30.
 * 顺序表顶级接口
 */
public interface ISeqList<T> {

    /**
     * 判断链表是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 链表长度
     * @return
     */
    int length();

    /**
     * 获取元素
     * @param index
     * @return
     */
    T get(int index);

    /**
     * 设置某个元素的值
     * @param index
     * @param data
     * @return
     */
    T set(int index, T data);

    /**
     * 根据index添加元素
     * @param index
     * @param data
     * @return
     */
    boolean add(int index, T data);

    /**
     * 添加元素
     * @param data
     * @return
     */
    boolean add(T data);

    /**
     * 根据index移除元素
     * @param index
     * @return
     */
    T remove(int index);

    /**
     * 根据data移除元素
     * @param data
     * @return
     */
    boolean remove(T data);

    /**
     * 根据data移除元素
     * @param data
     * @return
     */
    boolean removeAll(T data);

    /**
     * 清空链表
     */
    void clear();

    /**
     * 是否包含data元素
     * @param data
     * @return
     */
    boolean contains(T data);

    /**
     * 根据值查询下标
     * @param data
     * @return
     */
    int indexOf(T data);

    /**
     * 根据data值查询最后一个出现在顺序表中的下标
     * @param data
     * @return
     */
    int lastIndexOf(T data);

    /**
     * 输出格式
     * @return
     */
    String toString();
    }
}

  代码中声明了一个Object数组，初始化数组大小默认为64，存储的元素类型为泛型T，length则为顺序表的长度，部分方法实现比较简单，这里不过多分析，我们主要分析get(int index)、set(int index, T data)、add(int index, T data)、remove(int index)、removeAll(T data)、indexof(T data)等方法的实现。

get(int index) 实现分析 

从顺序表中获取值是一种相当简单的操作并且效率很高，这是由于顺序表内部采用了数组作为存储数据的容器。因此只要根据传递的索引值，然后直接获取数组中相对应下标的值即可，代码实现如下：

public T get(int index){
   if (index>=0 && index<this.length)
       return (T) this.table[index];         
   return null;
}
set(int index, T data) 实现分析 

在顺序表中替换值也是非常高效和简单的，只要根据传递的索引值index找到需要替换的元素，然后把对应元素值替换成传递的data值即可，代码如下：

public T set(int index, T data){
   if (index>=0 && index<this.length&& data!=null)
     {
         T old = (T)this.table[index];
         this.table[index] = data;
         return old;
     }
     return null;
 }
add(int index, T data)实现分析 

在顺序表中执行插入操作时，如果其内部数组的容量尚未达到最大值时，可以归结为两种情况，一种是在头部插入或者中间插入，这种情况下需要移动数组中的数据元素，效率较低，另一种是在尾部插入，无需移动数组中的元素，效率高。但是当顺序表内部数组的容量已达到最大值无法插入时，则需要申请另一个更大容量的数组并复制全部数组元素到新的数组，这样的时间和空间开销是比较大的，也就导致了效率更为糟糕了。因此在插入频繁的场景下，顺序表的插入操作并不是理想的选择。下面是顺序表在数组容量充足下头部或中间插入操作示意图（尾部插入比较简单就不演示了）： 


顺序表在数组容量不充足的情况下头部或中间插入操作示意图： 


理解了以上几种顺序表的插入操作后，我们通过代码来实现这个插入操作如下，注释很清晰就过多分析了：

/**
   * 根据index插入元素
   * @param index 插入位置的下标,0作为起始值
   * @param data 插入的数据
   * @return
   */
  public boolean add(int index, T data){                                        
     if (data==null)
         return false;

     //插入下标的容错判断,插入在最前面
     if (index<0)                             
         index=0;

     //插入下标的容错判断,插入在最后面
     if (index>this.length)
         index = this.length;

     //判断内部数组是否已满
     if (this.length==table.length)              
     {
         //把原数组赋值给临时数组
         Object[] temp = this.table;

         //对原来的数组进行成倍拓容,并把原数组的元素复制到新数组
         this.table = new Object[temp.length*2];   

         //先把原数组下标从0到index-1(即插入位置的前一个位置)复制到新数组
         for (int i=0; i<index; i++) {
             this.table[i] = temp[i];
         }
     }

     //从原数组的最后一个元素开始直到index位置,都往后一个位置
     // 最终腾出来的位置就是新插入元素的位置了
     for (int j=this.length-1; j>=index; j--) {
         this.table[j + 1] = this.table[j];
     }
     //插入新值
     this.table[index] = data;
     //长度加一
     this.length++;
     //插入成功
     return true;
  }
remove(int index) 实现分析 

顺序表的删除操作和前的插入操作情况是类似的，如果是在中间或者头部删除顺序表中的元素，那么在删除位置之后的元素都必须依次往前移动，效率较低，如果是在顺序表的尾部直接删除的话，则无需移动元素，此情况下删除效率高。如下图所示在顺序表中删除元素a_i时，a_i之后的元素都依次往前移动： 


删除操作的代码实现如下：

/**
  * 根据index删除元素
  * @param index 需要删除元素的下标
  * @return
  */
 public T remove(int index)
 {
     if (this.length!=0 && index>=0 && index<this.length)
     {
         //记录删除元素的值并返回
         T old = (T)this.table[index];

         //从被删除的元素位置开,其后的元素都依次往前移动
         for (int j=index; j<this.length-1; j++) {
             this.table[j] = this.table[j + 1];
         }
         //设置数组元素对象为空
         this.table[this.length-1]=null;
         //顺序表长度减1
         this.length--;
         return old;                         
     }
     return null;
 }
removeAll(T data) 实现分析 

在顺序表中根据数据data找到需要删除的数据元素和前面分析的根据index删除顺序表中的数据元素是一样的道理，因此我们只要通过比较找到与data相等的数据元素并获取其下标，然后调用前面实现的remove(int index)方法来移除即可。代码实现如下：

@Override
public boolean removeAll(T data) {
    boolean done=false;
    if (this.length!=0 && data!=null)
    {
        int i=0;
        while (i<this.length)
            //找出数据相同的选项
            if (data.equals(this.table[i]))
            {
                this.remove(i);//根据下标删除
                done = true;
            }
            else
                i++;//继续查找
    }
    return done;
}
indexOf(T data) 实现分析 

要根据data在顺序表中查找第一个出现的数据元素的下标，只需要通过对比数据项是否相等，相等则返回下标，不相等则返回-1，indexOf和lastIndexOf方法实现如下：

/**
 * 根据数据查询下标
 * @param data
 * @return
 */
@Override
public int indexOf(T data)
{
    if (data!=null)
        for (int i=0; i<this.length; i++) {
            //相当则返回下标
            if (this.table[i].equals(data))
                return i;
        }
    return -1;
}

/**
 * 根据data查询最后一个出现在顺序表中的下标
 * @param data
 * @return
 */
@Override
public int lastIndexOf(T data)
{
    if (data!=null)
        for (int i=this.length-1; i>=0; i--)
            if (data.equals(this.table[i]))
                return i;
    return -1;
}
  以上便是顺序表的主要的操作方法，当然顺序表中还可以实现其他操作，如在初始化构造函数时传入数组来整体初始化顺序表，比较两个信息表是否相等、是否包含某个数据等。这里贴一下传入数据构建顺序表构造方法实现，其他实现代码我们这里就不贴了，稍后实现源码都会上传gitHub提供给大家：



/**
* 传入一个数组初始化顺序表
* @param array
*/
public SeqList(T[] array){
  if (array==null){
      throw new NullPointerException("array can\'t be empty!");
  }
  //创建对应容量的数组
  this.table = new Object[array.length];
//复制元素
  for (int i=0;i<array.length;i++){
      this.table[i]=array[i];
  }

  this.length=array.length;
}



2.3 顺序存储结构的效率分析

  通过上述的分析，我们对顺序表的实现已有了比较清晰的认识，接下来看一下顺序表的执行效率问题，主要针对获取、插入、修改、删除等主要操作。前面分析过，由于顺序表内部采用了数组作为存储容器，而数组又是随机存取结构的容器，也就是说在创建数组时操作系统给数组分配的是一块连续的内存空间，数组中每个存储单元的地址都是连续的，所以在知道数组基地址后可以通过一个简单的乘法和加法运算即可计算出其他存储单元的内存地址(实际上计算机内部也就是这么做的)，这两个运算的执行时间是常数时间，因此可以认为数组的访问操作能在常数时间内完成，即顺序表的访问操作(获取和修改元素值)的时间复杂为O(1)。 

  对于在顺序表中插入或者删除元素，从效率上则显得不太理想了，由于插入或者删除操作是基于位置的，需要移动数组中的其他元素，所以顺序表的插入或删除操作，算法所花费的时间主要是用于移动元素，如在顺序表头部插入或删除时，效率就显得相当糟糕了。若在最前插入或删除，则需要移动n（这里假设长度为n）个元素；若在最后插入或删除，则需要移动的元素为0。这里我们假设插入或删除值为第i(0<i<=n)个元素，其概率为pi，则插入或删除一个元素的平均移动次数求和为：


  
 $p 1 * (n - 1) + p 2 * (n - 2) + . . . + p i * (n - i) + . . . + p n - 1 * 1 + p n * 0 = \sum i = 1 n (p i * (n - i))$ 

如果在各个位置插入元素的概率相同即 pi=1n+1 (n+1个插入位置任意选择一个的概率)则有：


  
 $\sum i = 1 n (p i * (n - i)) = 1 n + 1 \sum i = 1 n (n - i) = 1 n + 1 * n ( n + 1 ) 2 = n 2 = O (n)$ 

  也就是说，在等概率的情况下，插入或者删除一个顺序表的元素平均需要移动顺序表元素总量的一半，其时间复杂度是O(n)。当然如果在插入时，内部数组容量不足时，也会造成其他开销，如复制元素的时间开销和新建数组的空间开销。 

  因此总得来说顺序表有以下优缺点：

优点

使用数组作为内部容器简单且易用
在访问元素方面效率高
数组具有内存空间局部性的特点，由于本身定义为连续的内存块，所以任何元素与其相邻的元素在物理地址上也是相邻的。
缺点

内部数组大小是静态的，在使用前必须指定大小，如果遇到容量不足时，需动态拓展内部数组的大小，会造成额外的时间和空间开销
在内部创建数组时提供的是一块连续的空间块，当规模较大时可能会无法分配数组所需要的内存空间
顺序表的插入和删除是基于位置的操作，如果需要在数组中的指定位置插入或者删除元素，可能需要移动内部数组中的其他元素，这样会造成较大的时间开销，时间复杂度为O(n)
3.线性表的链式存储设计与实现（链表）



3.1 链表的链式存储结构设计原理概要

  通过前面对线性顺序表的分析，我们知道当创建顺序表时必须分配一块连续的内存存储空间，而当顺序表内部数组的容量不足时，则必须创建一个新的数组，然后把原数组的的元素复制到新的数组中，这将浪费大量的时间。而在插入或删除元素时，可能需要移动数组中的元素，这也将消耗一定的时间。鉴于这种种原因，于是链表就出场了，链表在初始化时仅需要分配一个元素的存储空间，并且插入和删除新的元素也相当便捷，同时链表在内存分配上可以是不连续的内存，也不需要做任何内存复制和重新分配的操作，由此看来顺序表的缺点在链表中都变成了优势，实际上也是如此，当然链表也有缺点，主要是在访问单个元素的时间开销上，这个问题留着后面分析，我们先通过一张图来初步认识一下链表的存储结构，如下： 


  从图可以看出线性链表的存储结构是用若干个地址分散的存储单元存放数据元素的，逻辑上相邻的数据元素在物理位置上不一定相邻，因此每个存储单元中都会有一个地址指向域，这个地址指向域指明其后继元素的位置。在链表中存储数据的单元称为结点(Node)，从图中可以看出一个结点至少包含了数据域和地址域，其中数据域用于存储数据，而地址域用于存储前驱或后继元素的地址。前面我们说过链表的插入和删除都相当便捷，这是由于链表中的结点的存储空间是在插入或者删除过程中动态申请和释放的，不需要预先给单链表分配存储空间的，从而避免了顺序表因存储空间不足需要扩充空间和复制元素的过程，提高了运行效率和存储空间的利用率。



3.2 单链表的储结构实现分析

到此我们已初步了解了链表的概念和存储结构，接下来，开始分析链表的实现，这里先从单链表入手。同样地，先来定义一个顶级的链表接口:ILinkedList和存储数据的结点类Node，该类是代表一个最基本的存储单元，Node代码如下：



/**
 * Created by zejian on 2016/10/21.
 * 单向链表节点
 */
public class Node<T> {
    public T data;//数据域
    public Node<T> next;//地址域

    public Node(T data){
        this.data=data;
    }

    public Node(T data,Node<T> next){
        this.data=data;
        this.next=next;
    }
}

接着顶级的链表接口ILinkedList，该接口声明了我们所有需要实现的方法。



/**
 * Created by zejian on 2016/10/21.
 * 链表顶级接口
 */
public interface ILinkedList<T> {
    /**
     * 判断链表是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 链表长度
     * @return
     */
    int length();

    /**
     * 获取元素
     * @param index
     * @return
     */
    T get(int index);

    /**
     * 设置某个结点的的值
     * @param index
     * @param data
     * @return
     */
    T set(int index, T data);

    /**
     * 根据index添加结点
     * @param index
     * @param data
     * @return
     */
    boolean add(int index, T data);

    /**
     * 添加结点
     * @param data
     * @return
     */
    boolean add(T data);

    /**
     * 根据index移除结点
     * @param index
     * @return
     */
    T remove(int index);

    /**
     * 根据data移除结点
     * @param data
     * @return
     */
    boolean removeAll(T data);

    /**
     * 清空链表
     */
    void clear();

    /**
     * 是否包含data结点
     * @param data
     * @return
     */
    boolean contains(T data);

      /**
     * 输出格式
     * @return
     */
    String toString();
}

创建一个单链表SingleILinkedList并实现ILinkedList接口，覆盖其所有方法，声明一个单链表的头结点head，代表链表的开始位置，如下：



public class SingleILinkedList<T> implements ILinkedList<T> {
   protected Node<T> headNode; //带数据头结点

   public SingleILinkedList(Node<T> head) {
       this.headNode = head;
   }
   //其他代码先省略
   .....
}

boolean isEmpty()实现分析 

需要判断链表是否为空的依据是头结点head是否为null，当head=null时链表即为空链表，因此我们只需判断头结点是否为空即可，isEmpty方法实现如下：

/**
 * 判断链表是否为空
 * @return
 */
@Override
public boolean isEmpty() {
    return this.head==null;
}
int length()实现分析 

由于单链表的结点数就是其长度，因此我们只要遍历整个链表并获取结点的数量即可获取到链表的长度。遍历链表需要从头结点HeadNode开始，为了不改变头结点的存储单元，声明变量p指向当前头结点和局部变量length，然后p从头结点开始访问，沿着next地址链到达后继结点，逐个访问，直到最后一个结点，每经过一个结点length就加一，最后length的大小就是链表的大小。实现代码如下：

@Override
public int length() {
   int length=0;//标记长度的变量
   Node<T> p=head;//变量p指向头结点
   while (p!=null){
       length++;
       p=p.next;//后继结点赋值给p，继续访问
   }
   return length;
}
 T get(int index)实现分析 

在单链表中获取某个元素的值是一种比较费时间的操作，需要从头结点开始遍历直至传入值index指向的位置，其中需要注意的是index是从0开始计算，也就是说传递的index=3时，查找的是链表中第4个位置的值。其查询获取值的过程如下图所示： 


代码实现如下：

/**
 * 根据index索引获取值
 * @param index 下标值起始值为0
 * @return
 */
@Override
public T get(int index) {

    if(this.head!=null&&index>=0){
        int count=0;
        Node<T> p=this.head;
        //找到对应索引的结点
        while (p!=null&&count<index){
            p=p.next;
            count++;
        }

        if(p!=null){
            return p.data;
        }
    }
    return null;
}

通过上图和代码，我们就可以很容易理解链表中取值操作的整个过程了。
 T set(int index, T data)实现分析 

根据传递的index查找某个值并替换其值为data，其实现过程的原理跟get(int index)是基本一样的，先找到对应值所在的位置然后删除即可，不清晰可以看看前面的get方法的图解，这里直接给出代码实现：

/**
 * 根据索引替换对应结点的data
 * @param index 下标从0开始
 * @param data
 * @return 返回旧值
 */
@Override
public T set(int index, T data) {

    if(this.head!=null&&index>=0&&data!=null){
        Node<T> pre=this.head;
        int count=0;
        //查找需要替换的结点
        while (pre!=null&&count<index){
            pre=pre.next;
            count++;
        }
        //不为空直接替换
        if (pre!=null){
            T oldData=pre.data;
            pre.data=data;//设置新值
            return oldData;
        }

    }
    return null;
}
 add(int index, T data)实现分析 

单链表的插入操作分四种情况: 
a.空表插入一个新结点，插语句如下：

head=new Node<T>(x,null);



b.在链表的表头插入一个新结点(即链表的开始处)，此时表头head!=null，因此head后继指针next应该指向新插入结点p，而p的后继指针应该指向head原来的结点，代码如下：

//创建新结点
Node<T> p =new Node<T>(x,null);
//p的后继指针指向head原来的结点
p.next=head;
//更新head
head=p;

以上代码可以合并为如下代码：

//创建新结点，其后继为head原来的结点，head的新指向为新结点
head=new Node<T>(x,head);

执行过程如下图：



c.在链表的中间插入一个新结点p，需要先找到给定插入位置的前一个结点，假设该结点为front，然后改变front的后继指向为新结点p，同时更新新结点p的后继指向为front原来的后继结点，即front.next，其执行过程如下图所示： 


代码实现如下：

//新结点p
Node<T> p =new Node<T>(x,null);
//更新p的后继指向
p.next=front.next;
//更新front的后继指向
front.next=p;

以上三句代码合并为一句简洁代码：

front.next=new Node<T>(x,front.next);

d.在链表的表尾插入一个新结点(链表的结尾)在尾部插入时，同样需要查找到插入结点P的前一个位置的结点front（假设为front），该结点front为尾部结点，更改尾部结点的next指针指向新结点P，新结点P的后继指针设置为null，执行过程如下： 


其代码语句如下：

//front的next指针指向新结点，新结点的next指针设置为null
front.next=new Node<T>(x,null);

  到此我们也就可以发现单向链表中的中间插入和尾部插入其实可以合并为一种情况。最后这里给出该方法整体代码实现，从代码实现上来看中间插入和尾部插入确实也视为同种情况处理了。

  /**
     * 根据下标添加结点
     * 1.头部插入
     * 2.中间插入
     * 3.末尾插入
     * @param index 下标值从0开始
     * @param data
     * @return
     */
    @Override
    public boolean add(int index, T data) {

        if (data==null){
            return false;
        }
        //在头部插入
        if (this.head==null||index<=1){
            this.head = new Node<T>(data, this.head);
        }else {
            //在尾部或中间插入
            int count=0;
            Node<T> front=this.head;
            //找到要插入结点位置的前一个结点
            while (front.next!=null&&count<index-1){
                front=front.next;
                count++;
            }
            //尾部添加和中间插入属于同种情况,毕竟当front为尾部结点时front.next=null
            front.next=new Node<T>(data,front.next);
        }
        return true;
    }
 T remove(int index) 删除结点实现分析 

在单向链表中，根据传递index位置删除结点的操作分3种情况，并且删除后返回被删除结点的数据： 
a.删除链表头部（第一个）结点，此时需要删除头部head指向的结点，并更新head的结点指向，执行图示如下： 


代码实现如下：

//头部删除，更新head指向
head=head.next;

b.删除链表的中间结点，与添加是同样的道理，需要先找到要删除结点r（假设要删除的结点为r）位置的前一个结点front(假设为front)，然后把front.next指向r.next即要删除结点的下一个结点，执行过程如下： 


代码语句如下：

Node<T> r =front.next;
//更新结点指针指向
front.next=r.next;
r=null;

c.删除链表的最后一个结点，通过遍历操作找到最后一个结点r的前一个结点front，并把front.next设置为null，即可。执行过程如下： 


代码如下：

front.next=null;
r=null;

我们把中间删除和尾部删除合并为如下代码：

Node<T> r =front.next;
//如果不是尾部结点，更新结点front指针指向
if(r=!null){
    front.next=r.next;
    r=null;
}

该方法整体代码实现如下：

/**
     * 根据索引删除结点
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {

        T old=null;

        if (this.head!=null&&index>=0){

            //直接删除的是头结点
            if(index==0){
                old=this.head.data;
                this.head=this.head.next;
            }else {

                Node<T> front = this.head;
                int count = 0;
                //查找需要删除结点的前一个结点
                while (front.next != null && count < index - 1) {
                    front = front.next;
                    count++;
                }

                //获取到要删除的结点
                Node<T> r = front.next;

                if ( r!= null) {
                    //获取旧值
                    old =r.data;
                    //更改指针指向
                    front.next=r.next;
                    //释放
                    r=null;
                }
            }
        }
        return old;
    }

当然还有如下更简洁的代码写法：

@Override
  public T remove(int index) {

      T old=null;

      if (this.head!=null&&index>=0){

          //直接删除的是头结点
          if(index==0){
              old=this.head.data;
              this.head=this.head.next;
          }else {

              Node<T> front = this.head;
              int count = 0;
              //查找需要删除结点的前一个结点
              while (front.next != null && count < index - 1) {
                  front = front.next;
                  count++;
              }

              if ( front.next!= null) {
                  //获取旧值
                  old =front.next.data;
                  //更改指针指向
                  front.next=front.next.next;
              }
          }
      }
      return old;
  }
void clear() 实现分析 

清空链表是一件非常简单的事，只需让head=null即可；代码如下：

/**
 * 清空链表
 */
@Override
public void clear() {
    this.head=null;
}
  ok~,到此单链表主要的添加、删除、获取值、设置替换值、获取长度等方法已分析完毕，其他未分析的方法都比较简单这里就不一一分析了，单链表的整体代码最后会分享到github给大家。



3.3 带头结点的单链表以及循环单链表的实现



带头结点的单链表

前面分析的单链表是不带特殊头结点的，所谓的特殊头结点就是一个没有值的结点即：



//没有带值的头结点
Node<T> head= new Node<T>(null,null);

此时空链表的情况如下： 


那么多了头结点的单向链表有什么好处呢？通过对没有带头结点的单链表的分析，我们可以知道，在链表插入和删除时都需要区分操作位，比如插入操作就分头部插入和中间或尾部插入两种情况（中间或尾部插入视为一种情况对待即可），如果现在有不带数据的头结点，那么对于单链表的插入和删除不再区分操作的位置，也就是说头部、中间、尾部插入都可以视为一种情况处理了，这是因为此时头部插入和头部删除无需改变head的指向了，头部插入如下所示： 


接着再看看在头部删除的情况： 


带头结点遍历从head.next开始： 


因此无论是插入还是删除，在有了不带数据的头结点后，在插入或者删除时都无需区分操作位了，好~，到此我们来小结一下带头结点的单链表特点：

a.空单链表只有一个结点，head.next=null。
b.遍历的起点为p=head.next。
c.头部插入和头部删除无需改变head的指向。
  同时为了使链表在尾部插入时达到更加高效，我们可在链表内增加一个尾部指向的结点rear，如果我们是在尾部添加结点，那么此时只要通过尾部结点rear进行直接操作即可，无需从表头遍历到表尾，带尾部结点的单链表如下所示： 


从尾部直接插入的代码实现如下：



/**
 * 尾部插入
 * @param data
 * @return
 */
@Override
public boolean add(T data) {
    if (data==null)
        throw new NullPointerException("data can\'t be empty!");

    this.rear.next = new Node<T>(data);
    //更新末尾指针的指向
    this.rear = this.rear.next;
    return true;
}



  从代码和图示看来确实只要获取当前的尾部指向的结点rear并把新结点赋值给rear.next，最后更新rear结点的值即可，完全不用遍历操作，但是如果是根据index来插入的还，遍历部分结点还是少不了的，下面看看根据index插入的代码实现，由于有了头结点，头部、中间、尾部插入无需区分操作位都视为一种情况处理。



/**
 * 根据下标添加结点
 * 1.头部插入
 * 2.中间插入
 * 3.末尾插入
 * @param index 该值从0开始,如传4就代表插入在第5个位置
 * @param data
 * @return
 */
@Override
public boolean add(int index, T data) {

    if (data==null){
        throw new NullPointerException("data can\'t be empty!");
    }

    if(index<0)
        throw new NullPointerException("index can\'t less than 0");

    //无需区分位置操作,中间/头部/尾部插入
    int j=0;
    Node<T> pre=this.headNode;
    //查找到插入位置即index的前一个结点
    while (pre.next!=null&&j<index){
        pre=pre.next;
        j++;
    }

    //将新插入的结点的后继指针指向pre.next
    Node<T> q=new Node<T>(data,pre.next);
    //更改指针指向
    pre.next=q;

    //如果是尾部指针
    if (pre==this.rear)
        this.rear=q;

    return true;
}

  最后在看看删除的代码实现，由于删除和插入的逻辑和之前不带头结点的单链表分析过的原理的是一样的，因此我们这里不重复了，主要注意遍历的起始结点变化就行。



 /**
     * 根据索引删除结点
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        T old=null;

        //无需区分头删除或中间删除或尾部删除的情况
        if (index>=0){
            Node<T> pre = this.headNode;
            int j = 0;
            //查找需要删除位置的前一个结点
            while (pre.next != null && j < index) {
                pre = pre.next;
                j++;
            }

            //获取到要删除的结点
            Node<T> r = pre.next;

            if (r != null) {
                //获取旧值
                old =r.data;
                //如果恰好是尾部结点,则更新rear的指向
                if (r==this.rear){
                    this.rear=pre;
                }
                //更改指针指向
                pre.next=r.next;
            }

        }
        return old;
    }

ok~，关于带头结点的单向链表就分析到这，这里贴出实现源码，同样地，稍后在github上也会提供：



package com.zejian.structures.LinkedList.singleLinked;

import com.zejian.structures.LinkedList.ILinkedList;

/**
* Created by zejian on 2016/10/22.
* 带头结点并含有尾指针的链表
*/
public class HeadSingleILinkedList<T> implements ILinkedList<T> {

   protected Node<T> headNode; //不带数据头结点
   protected Node<T> rear;//指向尾部的指针

   public HeadSingleILinkedList() {
       //初始化头结点与尾指针
       this.headNode =rear= new Node<>(null);
   }

   public HeadSingleILinkedList(Node<T> head) {
       this();
       this.headNode.next =rear.next= head;
       rear=rear.next;//更新末尾指针指向
   }

   /**
    * 传入一个数组,转换成链表
    * @param array
    */
   public HeadSingleILinkedList(T[] array)
   {
       this();
       if (array!=null && array.length>0)
       {
           this.headNode.next = new Node<T>(array[0]);
           rear=this.headNode.next;
           int i=1;
           while (i<array.length)
           {
               rear.next=new Node<T>(array[i++]);
               rear = rear.next;
           }
       }
   }

   /**
    * 通过传入的链表构造新的链表
    * @param list
    */
   public HeadSingleILinkedList(HeadSingleILinkedList<T> list) {
       this();
       if (list!=null && list.headNode.next!=null)
       {
           this.headNode.next = new Node(list.headNode.data);
           Node<T> p = list.headNode.next;
           rear = this.headNode.next;
           while (p!=null)
           {
               rear.next = new Node<T>(p.data);
               rear = rear.next;
               p = p.next;
           }
       }
   }


   /**
    * 判断链表是否为空
    * @return
    */
   @Override
   public boolean isEmpty() {
       return this.headNode.next==null;
   }

   @Override
   public int length() {
       int length=0;
       Node<T> currentNode=headNode.next;
       while (currentNode!=null){
           length++;
           currentNode=currentNode.next;
       }
       return length;
   }

   /**
    * 根据index索引获取值
    * @param index 下标值起始值为0
    * @return
    */
   @Override
   public T get(int index) {

       if(index>=0){
           int j=0;
           Node<T> pre=this.headNode.next;
           //找到对应索引的结点
           while (pre!=null&&j<index){
               pre=pre.next;
               j++;
           }

           if(pre!=null){
               return pre.data;
           }

       }
       return null;
   }

   /**
    * 根据索引替换对应结点的data
    * @param index 下标从0开始
    * @param data
    * @return 返回旧值
    */
   @Override
   public T set(int index, T data) {

       if(index>=0&&data!=null){
           Node<T> pre=this.headNode.next;
           int j=0;
           while (pre!=null&&j<index){
               pre=pre.next;
               j++;
           }

           if (pre!=null){
               T oldData=pre.data;
               pre.data=data;//设置新值
               return oldData;
           }

       }
       return null;
   }

   /**
    * 根据下标添加结点
    * 1.头部插入
    * 2.中间插入
    * 3.末尾插入
    * @param index 该值从0开始,如传4就代表插入在第5个位置
    * @param data
    * @return
    */
   @Override
   public boolean add(int index, T data) {

       if (data==null){
           throw new NullPointerException("data can\'t be empty!");
       }

       if(index<0)
           throw new NullPointerException("index can\'t less than 0");

       //无需区分位置操作,中间/头部/尾部插入
       int j=0;
       Node<T> pre=this.headNode;
       while (pre.next!=null&&j<index){
           pre=pre.next;
           j++;
       }

       //将新插入的结点的后继指针指向pre.next
       Node<T> q=new Node<T>(data,pre.next);
       //更改指针指向
       pre.next=q;

       //如果是未指针
       if (pre==this.rear)
           this.rear=q;

       return true;
   }

   /**
    * 尾部插入
    * @param data
    * @return
    */
   @Override
   public boolean add(T data) {
       if (data==null)
           throw new NullPointerException("data can\'t be empty!");

       this.rear.next = new Node<T>(data);
       //更新末尾指针的指向
       this.rear = this.rear.next;
       return true;
   }

   /**
    * 根据索引删除结点
    * @param index
    * @return
    */
   @Override
   public T remove(int index) {
       T old=null;

       //包含了头删除或中间删除或尾部删除的情况
       if (index>=0){

           Node<T> pre = this.headNode;
           int j = 0;
           //查找需要删除位置的前一个结点
           while (pre.next != null && j < index) {
               pre = pre.next;
               j++;
           }

           //获取到要删除的结点
           Node<T> r = pre.next;

           if (r != null) {
               //获取旧值
               old =r.data;
               //如果恰好是尾部结点,则更新rear的指向
               if (r==this.rear){
                   this.rear=pre;
               }
               //更改指针指向
               pre.next=r.next;
           }

       }
       return old;
   }

   /**
    * 根据data移除所有数据相同的结点
    * @param data
    * @return
    */
   @Override
   public boolean removeAll(T data) {

       boolean isRemove=false;

       if(data!=null){
           //用于记录要删除结点的前一个结点
           Node<T> front=this.headNode;
           //当前遍历的结点
           Node<T> pre=front.next;
           //查找所有数据相同的结点并删除
           while (pre!=null){
               if(data.equals(pre.data)){
                   //如果恰好是尾部结点,则更新rear的指向
                   if(data.equals(rear.data)){
                       this.rear=front;
                   }
                   //相等则删除pre并更改指针指向
                   front.next=pre.next;
                   pre =front.next;
                   isRemove=true;
               }else {
                   front=pre;
                   pre=pre.next;
               }
           }
       }
       return isRemove;
   }

   /**
    * 清空链表
    */
   @Override
   public void clear() {
       this.headNode.next=null;
       this.rear=this.headNode;
   }

   /**
    * 判断是否包含某个值
    * @param data
    * @return
    */
   @Override
   public boolean contains(T data) {

       if(data!=null){
           Node<T> pre=this.headNode.next;
           while (pre!=null){
               if(data.equals(pre.data)){
                   return true;
               }
               pre=pre.next;
           }
       }
       return false;
   }

   /**
    * 从末尾连接两个链表
    * @param list
    */
   public void concat(HeadSingleILinkedList<T> list)
   {
       if (this.headNode.next==null) {
           this.headNode.next = list.headNode.next;
       } else {
           Node<T> pre=this.headNode.next;
           while (pre.next!=null)
               pre = pre.next;
          pre.next=list.headNode.next;
           //更新尾部指针指向
           this.rear=list.rear;
       }
   }

   @Override
   public String toString() {
       String str="(";
       Node<T> pre = this.headNode.next;
       while (pre!=null)
       {
           str += pre.data;
           pre = pre.next;
           if (pre!=null)
               str += ", ";
       }
       return str+")";
   }

   public static void main(String[] args){

       String[] letters={"A","B","C","D","E","F"};
       HeadSingleILinkedList<String> list=new HeadSingleILinkedList<>(letters);

       System.out.println("list.get(3)->"+list.get(3));
       System.out.println("list:"+list.toString());

       System.out.println("list.add(4,Y)—>"+list.add(4,"Y"));
       System.out.println("list:"+list.toString());
       System.out.println("list.add(Z)—>"+list.add("Z"));
       System.out.println("list:"+list.toString());


       System.out.println("list.contains(Z)->"+list.contains("Z"));
       System.out.println("list.set(4,P)-->"+list.set(4,"P"));
       System.out.println("list:"+list.toString());

       System.out.println("list.remove(Z)->"+list.removeAll("Z"));
       System.out.println("list.remove(4)-->"+list.remove(4));
       System.out.println("list:"+list.toString());
   }
}



循环单链表

  有上述的分析基础，循环单链表(Circular Single Linked List)相对来说就比较简单了，所谓的循环单链表是指链表中的最后一个结点的next域指向了头结点head，形成环形的结构，我们通过图示来理解： 


此时的循环单链表有如下特点： 

a.当循环链表为空链表时，head指向头结点，head.next=head。 

b.尾部指向rear代表最后一个结点，则有rear.next=head。 

在处理循环单链表时，我们只需要注意在遍历循环链表时，避免进入死循环即可，也就是在判断循环链表是否到达结尾时，由之前的如下判断



Node<T> p=this.head;
while(p!=null){
     p=p.next;
}

在循环单链表中改为如下判断：



Node<T> p=this.head;
while(p!=this.head){
     p=p.next;
}

因此除了判断条件不同，其他操作算法与单链表基本是一样的，下面我们给出循环单链表的代码实现：



package com.zejian.structures.LinkedList.singleLinked;

import com.zejian.structures.LinkedList.ILinkedList;


/**
 * Created by zejian on 2016/10/25.
 * 循环单链表
 */
public class CircularHeadSILinkedList<T> implements ILinkedList<T> {

    protected Node<T> head; //不带数据头结点
    protected Node<T> tail;//指向尾部的指针


    public CircularHeadSILinkedList() {
        //初始化头结点与尾指针
        this.head= new Node<T>(null);
        this.head.next=head;
        this.tail=head;
    }


    public CircularHeadSILinkedList(T[] array)
    {
        this();
        if (array!=null && array.length>0)
        {
            this.head.next = new Node<>(array[0],head);
            tail=this.head.next;
            int i=1;
            while (i<array.length)
            {
                tail.next=new Node<>(array[i++]);
                tail.next.next=head;
                tail = tail.next;
            }
        }
    }


    @Override
    public boolean isEmpty() {
        return this.head.next==head;
    }

    @Override
    public int length() {

        int length=0;
        Node<T> p=this.head.next;
        while (p!=head){
            p=p.next;
            length++;
        }

        return length;
    }

    @Override
    public T get(int index) {

        if (index>=0)
        {
            int j=0;
            Node<T> pre=this.head.next;
            while (pre!=null && j<index)
            {
                j++;
                pre=pre.next;
            }
            if (pre!=null)
                return pre.data;
        }
        return null;
    }

    @Override
    public T set(int index, T data) {

        if (data==null){
            return null;
        }

        if(index>=0){
            int j=0;
            Node<T> p=this.head.next;

            while (p!=head&&j<index){
                j++;
                p=p.next;
            }

            //如果不是头结点
            if(p!=head){
                T old = p.data;
                p.data=data;

                return old;
            }
        }
        return null;
    }

    @Override
    public boolean add(int index, T data) {
        int size=length();
        if(data==null||index<0||index>=size)
            return false;

        int j=0;
        Node<T> p=this.head;
        //寻找插入点的位置的前一个结点
        while (p.next!=head&&j<index){
            p=p.next;
            j++;
        }

        //创建新结点,如果index=3,那么插入的位置就是第4个位置
        Node<T> q=new Node<>(data,p.next);
        p.next=q;
        //更新尾部指向
        if(p==tail){
            this.tail=q;
        }
        return true;
    }

    @Override
    public boolean add(T data) {
        if(data==null){
            return false;
        }

        Node<T> q=new Node<>(data,this.tail.next);
        this.tail.next=q;
        //更新尾部指向
        this.tail=q;

        return true;
    }

    @Override
    public T remove(int index) {
        int size=length();
        if(index<0||index>=size||isEmpty()){
            return null;
        }

        int j=0;
        Node<T> p=this.head.next;

        while (p!=head&&j<index){
            j++;
            p=p.next;
        }

        if(p!=head){
            T old =p.next.data;

            if(tail==p.next){
                tail=p;
            }
            p.next=p.next.next;

            return old;
        }

        return null;
    }

    @Override
    public boolean removeAll(T data) {
        boolean isRemove=false;
        if(data==null){
            return isRemove;
        }

        //用于记录要删除结点的前一个结点
        Node<T> front=this.head;
        //当前遍历的结点
        Node<T> pre=front.next;
        //查找所有数据相同的结点并删除
        while (pre!=head){
            if(data.equals(pre.data)){
                //如果恰好是尾部结点,则更新rear的指向
                if(data.equals(tail.data)){
                    this.tail=front;
                }
                //相等则删除pre并更改指针指向
                front.next=pre.next;
                pre =front.next;
                isRemove=true;
            }else {
                front=pre;
                pre=pre.next;
            }
        }


        return isRemove;
    }

    @Override
    public void clear() {
        this.head.next=head;
        this.tail=head;
    }

    @Override
    public boolean contains(T data) {
        if (data==null){
            return false;
        }

        Node<T> p=this.head.next;

        while (p!=head){
            if(data.equals(p.data)){
                return true;
            }

            p=p.next;
        }

        return false;
    }

    @Override
    public String toString()
    {
        String str="(";
        Node<T> p = this.head.next;
        while (p!=head)
        {
            str += p.data.toString();
            p = p.next;
            if (p!=head)
                str += ", ";
        }
        return str+")";
    }

    public static void main(String[] args){

        String[] letters={"A","B","C","D","E","F"};
        CircularHeadSILinkedList<String> list=new CircularHeadSILinkedList<>(letters);

        System.out.println("list.get(3)->"+list.get(3));
        System.out.println("list:"+list.toString());

        System.out.println("list.add(4,Y)—>"+list.add(4,"Y"));
        System.out.println("list:"+list.toString());
        System.out.println("list.add(Z)—>"+list.add("Z"));
        System.out.println("list:"+list.toString());


        System.out.println("list.contains(Z)->"+list.contains("Z"));
        System.out.println("list.set(4,P)-->"+list.set(4,"P"));
        System.out.println("list:"+list.toString());

        System.out.println("list.removeAll(Z)->"+list.removeAll("Z"));
        System.out.println("list.remove(4)-->"+list.remove(4));
        System.out.println("list:"+list.toString());
    }
}



3.4 单链表的效率分析

  由于单链表并不是随机存取结构，即使单链表在访问第一个结点时花费的时间为常数时间，但是如果需要访问第i(0<i<n)个结点，需要从头结点head开始遍历部分链表，进行i次的p=p.next操作，这点从上述的图文分析我们也可以看出，这种情况类似于前面计算顺序表需要平均移动元素的总数，因此链表也需要平均进行n2次的p=p.next操作，也就是说get(i)和set(i,x)的时间复杂度都为O(n)。 

  由于链表在插入和删除结点方面十分高效的，因此链表比较适合那些插入删除频繁的场景使用，单纯从插入操作来看，我们假设front指向的是单链表中的一个结点，此时插入front的后继结点所消耗的时间为常数时间O(1),但如果此时需要在front的前面插入一个结点或者删除结点自己时，由于front并没有前驱指针，单凭front根本无法知道前驱结点，所以必须从链表的表头遍历至front的前一个结点再执行插入或者删除操作，而这个查询操作所消耗的时间为O(n),因此在已知front结点需要插入前驱结点或者删除结点自己时，消耗的时间为O(n)。当然这种情况并不是无法解决的，后面我们要分析到的双链表就可以很好解决这个问题，双链表是每个结点都同时拥有前后继结点的链表，这样的话上面的问题就迎刃而解了。上述是从已知单链表中front结点的情况下讨论的单链表的插入删除效率。 

  我们可能会有个疑问，从前面单链表的插入删除的代码实现上来说，我们并不知道front结点的，每次插入和删除结点，都需要从表头开始遍历至要插入或者删除结点的前一个结点，而这个过程所花费的时间和访问结点所花费的时间是一样的，即O(n)， 

也就是说从实现上来说确实单链表的插入删除操作花费时间也是O(n)，而顺序表插入和删除的时间也是O(n)，那为什么说单链表的插入和删除的效率高呢？这里我们要明白的是链表的插入和删除之所以是O(N)，是因为查询插入点所消耗的，找到插入点后插入操作消耗时间只为O(1)，而顺序表查找插入点的时间为O(1)，但要把后面的元素全部后移一位，消耗时间为O(n)。问题是大部分情况下查找所需时间比移动短多了，还有就是链表不需要连续空间也不需要扩容操作，因此即使时间复杂度都是O(n)，所以相对来说链表更适合插入删除操作。

  以上便是本篇对象顺序表与单链表的分析，如有误处，欢迎留言，我们一起探讨学习。下篇会是双链表的知识点，欢迎持续关注，下面丢出github的地址： 
GITHUB博文源码下载地址

关联文章:

java数据结构与算法之顺序表与链表设计与实现分析 
java数据结构与算法之双链表设计与实现 
java数据结构与算法之改良顺序表与双链表类似ArrayList和LinkedList（带Iterator迭代器与fast-fail机制） 

如果您喜欢我写的博文，读后觉得收获很大，不妨小额赞助我一下，让我有动力继续写出高质量的博文，感谢您的赞赏！支付宝、微信

收起

展开全文

java 数据结构算法链表

数据结构顺序表基本操作（C/C++实现）

千次阅读 多人点赞 2019-10-22 23:23:01

判断顺序表L是否为空输出顺序表L的第3个元素输出元素a的位置在第4个元素位置上插入f元素输出顺序表L 删除顺序表L的第3个元素输出顺序表L 释放顺序表L GitHub地址（包含.cpp文件和可执行程序exe）我的数据结构...

数据结构顺序表基本操作（C/C++实现）
注意：本代码为了测试运行默认含有操作所需数据，如有需要可自己增删改相关数据
涉及基本运算

初始化顺序表
依次插入元素
输出顺序表
输出顺序表的长度
判断顺序表是否为空
输出顺序表的第n个元素
输出元素x的位置
在第n个元素位置上插入x元素
输出顺序表
删除顺序表的第n个元素
输出顺序表
释放顺序表

GitHub地址（包含.cpp文件和可执行程序exe）
我的数据结构GitHub地址
源代码（经VS2015、devC++编译器运行通过）
#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;          /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char ElemType;        /* ElemType类型根据实际情况而定，这里假设为int */


Status visit(ElemType c)
{
	printf("%c ", c);
	return OK;
}

typedef struct
{
	ElemType data[MAXSIZE];        /* 数组，存储数据元素 */
	int length;                                /* 线性表当前长度 */
}SqList;

/* 1.初始化顺序线性表 */
Status InitList(SqList *L)
{
	L->length = 0;
	return OK;
}

/* 2.初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L, int i, ElemType e)
{
	int k;
	if (L->length == MAXSIZE)  /* 顺序线性表已经满 */
		return ERROR;
	if (i<1 || i>L->length + 1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
		return ERROR;

	if (i <= L->length)        /* 若插入数据位置不在表尾 */
	{
		for (k = L->length - 1; k >= i - 1; k--)  /* 将要插入位置之后的数据元素向后移动一位 */
			L->data[k + 1] = L->data[k];
	}
	L->data[i - 1] = e;          /* 将新元素插入 */
	L->length++;

	return OK;
}


/* 3.初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
	int i;
	for (i = 0; i<L.length; i++)
		visit(L.data[i]);
	printf("\n");
	return OK;
}

/* 4.初始条件：顺序线性表L已存在。
操作结果：返回L中数据元素个数 */
int ListLength(SqList L)
{
	return L.length;
}

/* 5.初始条件：顺序线性表L已存在。
操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(SqList L)
{
	if (L.length == 0)
		return TRUE;
	else
		return FALSE;
}

/* 6.初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L, int i, ElemType *e)
{
	if (L.length == 0 || i<1 || i>L.length)
		return ERROR;
	*e = L.data[i - 1];

	return OK;
}

/* 7.初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(SqList L, ElemType e)
{
	int i;
	if (L.length == 0)
		return 0;
	for (i = 0; i<L.length; i++)
	{
		if (L.data[i] == e)
			break;
	}
	if (i >= L.length)
		return 0;

	return i + 1;
}



/* 初始条件：顺序线性表L已存在。
操作结果：将L重置为空表 */
Status ClearList(SqList *L)
{
	L->length = 0;
	return OK;
}







/* 10.初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L, int i, ElemType *e)
{
	int k;
	if (L->length == 0)               /* 线性表为空 */
		return ERROR;
	if (i<1 || i>L->length)         /* 删除位置不正确 */
		return ERROR;
	*e = L->data[i - 1];
	if (i<L->length)                /* 如果删除不是最后位置 */
	{
		for (k = i; k<L->length; k++)/* 将删除位置后继元素前移 */
			L->data[k - 1] = L->data[k];
	}
	L->length--;
	return OK;
}

void unionL(SqList *La, SqList Lb)
{
	int La_len, Lb_len, i;
	ElemType e;
	La_len = ListLength(*La);
	Lb_len = ListLength(Lb);
	for (i = 1; i <= Lb_len; i++)
	{
		GetElem(Lb, i, &e);
		if (!LocateElem(*La, e))
			ListInsert(La, ++La_len, e);
	}
}

int main()
{

	SqList L;
	SqList Lb;

	ElemType e;
	Status i;
	int j, k;
	/*1.初始化*/
	i = InitList(&L);
	printf("1.初始化L后：L.length=%d\n", L.length);

	/*2.依次插入abcde*/
	i = ListInsert(&L, 1, 'e');
	i = ListInsert(&L, 1, 'd');
	i = ListInsert(&L, 1, 'c');
	i = ListInsert(&L, 1, 'b');
	i = ListInsert(&L, 1, 'a');
	printf("2.abcde插入执行完毕\n");

	/*3.输出顺序表*/
	printf("3.在L的表头依次插入a～e后：L.data=\n");
	ListTraverse(L);

	/*4.顺序表长度*/
	printf("4.L.length=%d \n", L.length);

	/*5.判空*/
	i = ListEmpty(L);
	printf("5.L是否空：i=%d(1:是 0:否)\n", i);

	/*6.输出顺序表L的第三个元素*/
	GetElem(L, 3, &e);
	printf("6.第3个元素的值为：%c\n", e);

	/*7.输出顺序表a的位置*/
	int l = LocateElem(L, 'a');
	printf("7.返回元素a的位序：%d\n", l);

	/*8.在第4个元素位置上插入f元素*/
	i = ListInsert(&L, 5, 'f');
	printf("8.在第4个元素位置上插入f元素执行完毕\n", L.length);

	/*9.输出顺序表*/
	printf("9.在L的第4个元素位置上插入f元素后：L.data=\n");
	ListTraverse(L);

	/*10.删除顺序表L的第三个元素*/

	i = ListDelete(&L, 3, &e); /* 删除第j个数据 */
	if (i == ERROR)
		printf("删除第%d个数据失败\n", 3);
	else
		printf("10.删除第个的元素成功\n");

	/*11.输出顺序表L*/
	printf("11.输出顺序表\n");
	ListTraverse(L);

	/*12.释放顺序表*/
	i = ClearList(&L);
	printf("释放顺序表执行完毕\n"); 
	system("pause");
		return 0;
}

收起

展开全文

数据结构基本操作

顺序表的实现

千次阅读 2016-06-04 01:34:46

一直对顺序表的概念不是很清楚，终于在一次的学习中，明白了以下（红色标注）： ...如果是直线，我们称这个线性表为顺序表；如果是曲线，我们称其为链表。本篇文章，我来主要整理出关于顺序表的内

一直对顺序表的概念不是很清楚，终于在一次的学习中，明白了以下（红色标注）：
        线性表是一种最简单、最基础的数据结构，线性表中的元素都是一对一的，除了第
一个元素和最后一个元素之外，其他元素都是首尾相接。通俗地讲，线性表中的元素都
是连在一条线中的，不管是直线还是曲线。如果是直线，我们称这个线性表为顺序表；
如果是曲线，我们称其为链表。
本篇文章，我来主要整理出关于顺序表的内容。在通讯录的多版本实现这篇博客中，我们
 知道，根据顺序表的容量大小是否固定可将顺序表分为静态顺序表和动态顺序表。
对于有好的变成习惯的程序员来说，使用assert是比较多的，可是，并不是所有的指针都
可以用assert来断言，下边我来具体说一下，希望对那些不太会用断言的人有一点帮助~~
assert的正确使用：
assert是一个宏，原型定义在头文件assert.h中，在vs2015编译器下给出的定义如下图：


在执行assert宏时，它会先计算出表达式expression的值，如果值为假，那么它想stderr
打印出一条出错信息，通过调用abort来终止程序执行。
细心的你有可能会发现expression的前边怎么会有两个‘！’呢。是不是多余的呢？？其实
并不是。如果expression不是0，!!expression = =1,否则，!!expression = =0，这下你就
知道了吧。为什么要这样做呢？？这里用到了逻辑运算符'||'的短路功能。如果expression是真，后边的不执行，如果是假，打印出出错信息~~这个简直是妙~
看着assert好像是使用越多越好，其实并非这样。频繁的调用assert会极大地影响程序的
性能，增加额外开销。并且它只能用在debug版本，release版本并不可。
在程序结束后，可以通过在包含#include<assert.h>的语句之前插入#define NDEBUG来
禁用assert调用，比如（只给出头文件）：
#include<stdio.h>
#define NDEBUG

#include<assert.h>

assert的用法总结：
（1）在函数开始处检验传入参入的合法性。这个我们平时使用的比较多。可是，如果
某个条件在为假时，对于程序 而言仍为合法值，此时就不要assert断言了。（关于这
个，在链表的博客中再述）
（2）每个assert最好只检验一个条件。否则，如果断言失败，我们无法直观的判断哪个
条件失败。
（3）assert里的参数不能使用改变环境的语句。比如：
assert(i++<100);这条语句是不正确的，这是因为如果在这条语句执行之前i=100，i++
<100这个条件为假，程序直接报错，i++就不会执行。
（4）有的地方，assert不能代替条件过滤。这里我举不出例子，有见解的朋友，可以在
博客下边的评论栏指出。
由于通讯录版本已经对静态顺序表做了解释，这里只给出代码和编码过程中的注意事项
//SeqList.c
#include"SeqList.h"
void menu()
{
	printf("*******1.初始化顺序表*******\n");
	printf("*******2.显示出顺序表*******\n");
	printf("*******3.顺序表尾插*********\n");
	printf("*******4.顺序表尾删*********\n");
	printf("*******5.顺序表头插*********\n");
	printf("*******6.顺序表头删*********\n");
	printf("*******7.插入元素***********\n");
	printf("*******8.删除给定元素*******\n");
	printf("*******9.删除给定元素的全部**\n");
	printf("*******10.顺序表排序*********\n");
	printf("*******11.折半查找元素*******\n");
	printf("*******0.退出****************\n");
}
//初始化
void InitSeq(pSeqList  pSeq)
{
	assert(pSeq);
	pSeq->sz = 0;
	memset(pSeq,0,sizeof(TypeName) * MAX);
	printf("初始化成功！\n");
}
//打印
void PrintSeq(pSeqList  pSeq)
{
	assert(pSeq);
	int i = 0;
	printf("顺序表中的元素有：\n");
	for (i = 0;i < pSeq->sz;i++)
	{
		printf("%d ",pSeq->Data[i]);
	}
	printf("\n");
}
//尾插
void PushBack(pSeqList  pSeq, TypeName x)
{
	assert(pSeq);
	if (pSeq->sz == MAX)
	{
		printf("顺序表已满，不可插入");
		exit(EXIT_FAILURE);
	}
	pSeq->Data[pSeq->sz] = x;
	pSeq->sz++;
	printf("尾插成功！\n");
}
//尾删
void PopBack(pSeqList  pSeq)
{
	assert(pSeq);
	if (pSeq->sz == 0)
	{
		printf("顺序表已空，不可删除");
		exit(EXIT_FAILURE);
	}
	pSeq->sz--;
	printf("尾删成功！\n");
}
//插入
void Insert(pSeqList  pSeq, int pos, TypeName x)
{
	assert(pSeq);
	int i = 0;
	if (pSeq->sz == MAX || pos == MAX)
	{
		printf("顺序表已满或者插入位置不合理\n");
		exit(EXIT_FAILURE);
	}
	for (i = pSeq->sz - 1;i >= pos; i--)
	{
		pSeq->Data[i + 1] = pSeq->Data[i];
	}
	pSeq->Data[pos] = x;
	pSeq->sz++;
	printf("插入成功!\n");
}
//删除给定元素
void Remove(pSeqList  pSeq, TypeName x)
{
	assert(pSeq);
	if (pSeq->sz == 0)
	{
		printf("顺序表已空，不可删除");
		exit(EXIT_FAILURE);
	}
	int i = 0;
	int j = 0;
	for (i = 0;i < pSeq->sz;i++)
	{
		if (pSeq->Data[i] == x)
			break;
	}
	if (i == pSeq->sz)
	{
		printf("要删除的元素不存在\n");
		exit(EXIT_FAILURE);
	}
	for (j = i + 1;j < pSeq->sz;j++)
	{
		pSeq->Data[j-1] = pSeq->Data[j];
	}
	pSeq->sz--;
	printf("删除成功!\n");
}
//删除给定元素的所有
void RemoveAll(pSeqList  pSeq, TypeName x)
{
	assert(pSeq);
	int count = 0;
	if (pSeq->sz == 0)
	{
		printf("顺序表已空，不可删除");
		exit(EXIT_FAILURE);
	}
	int i = 0;
	int j = pSeq->sz-1;
	while(i < pSeq->sz)
	{
		if (pSeq->Data[i] == x )
		{
			while (pSeq->Data[j] == x)
			{
				j--;
			}
			pSeq->Data[i] = pSeq->Data[j];
			count++;
			
		}
		i++;
	}
	pSeq->sz -= count;
	printf("删除成功！\n");
}
//头插
void PushFront(pSeqList  pSeq, TypeName x)
{
	assert(pSeq);
	int i = 0;
	if (pSeq->sz == MAX)
	{
		printf("顺序表已满，不可插入");
		exit(EXIT_FAILURE);
	}
	for (i = pSeq->sz - 1;i >= 0;i--)
	{
		pSeq->Data[i + 1] = pSeq->Data[i];
	}
	pSeq->Data[0] = x;
	pSeq->sz++;
	printf("头插成功！\n");
}
//头删
void PopFront(pSeqList  pSeq)
{
	assert(pSeq);
	int i = 0;
	if (pSeq->sz == 0)
	{
		printf("顺序表已空，不可删除");
		exit(EXIT_FAILURE);
	}
	for (i = 1;i < pSeq->sz ;i++)
	{
		pSeq->Data[i - 1] = pSeq->Data[i];
	}
	pSeq->sz--;
	printf("头删成功！\n");
}
//排序
void Sort(pSeqList  pSeq)
{
	assert(pSeq);
	int i = 0;
	int j = 0;
	int flag = 0;
	TypeName tmp= 0;
	if (pSeq->sz == 0)
	{
		printf("顺序表已空，不可排序");
		exit(EXIT_FAILURE);
	}
	for (i = 0;i < pSeq->sz;i++)
	{
		flag = 1;
		for (j = 0;j < pSeq->sz - i - 1;j++)
		{
			if (pSeq->Data[j] > pSeq->Data[j + 1])
			{
				tmp = pSeq->Data[j];
				pSeq->Data[j] = pSeq->Data[j + 1];
				pSeq->Data[j + 1] = tmp;
				flag = 0;
			}
		}
		if (flag == 1)
			break;
	}
	//printf("排序成功！\n");
}
//折半查找
void BinarySearch(pSeqList  pSeq, TypeName x)
{
	assert(pSeq);
	int left = 0;
	int right = pSeq->sz - 1;;
	int middle = 0;
	if (pSeq->sz == 0)
	{
		printf("顺序表已空，不可查找");
		exit(EXIT_FAILURE);
	}
	Sort(pSeq);
	while (left <= right)
	{
		middle = (left + right)/2;
		if (pSeq->Data[middle] == x)
		{
			printf("查找成功！\n");
			return;
		}
		else if (pSeq->Data[middle] < x)
		{
			left = middle + 1;
		}
		else
		{
			right = middle - 1;
		}
	}
	printf("要查找的元素不存在！\n");
}
//SeqList.h
#ifndef __SEQLIST_H__
#define  __SEQLIST_H__
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<memory.h>
#include<windows.h>
#define MAX 100
typedef int TypeName;
typedef struct SeqList
{
	TypeName Data[MAX];
	int sz;
}SeqList,*pSeqList;
enum op
{
	EXIT,
	INIT,
	PRINT,
	PUSHBACK,
	POPBACK,
	PUSHFRONT,
	POPFRONT,
	INSERT,
	REMOVE,
	REMOVEALL,
	SORT,
	BINARYSEARCH
};

void InitSeq(pSeqList  pSeq);
void PrintSeq(pSeqList  pSeq);
void PushBack(pSeqList  pSeq, TypeName x);
void PopBack(pSeqList  pSeq);
void PushFront(pSeqList  pSeq, TypeName x);
void PopFront(pSeqList  pSeq);
void Insert(pSeqList  pSeq,TypeName pos,TypeName x);//在给定位置插入给定元素
void Remove(pSeqList  pSeq,TypeName x);//删除表中的特定元素
void RemoveAll(pSeqList  pSeq,TypeName x);//删除表中所有值为x的元素
void Sort(pSeqList  pSeq);
void BinarySearch(pSeqList  pSeq,TypeName x);


#endif //__SEQLIST_H__
//test.c
#include"SeqList.h"
void test()
{
	SeqList seq;
	//pSeqList pseq = &seq;
	int pos = 0;
	int input = 1;
	TypeName x = 0;
	while (input)
	{
		menu();
		printf("请选择：>");
		scanf("%d", &input);
		switch (input)
		{
		case EXIT:
			break;
		case INIT:
			InitSeq(&seq);
			break;
		case PRINT:
			PrintSeq(&seq);
			break;
		case INSERT:
			printf("请输入插入元素的位置：>");
			scanf("%d",&pos);
			printf("请输入插入元素的值：>");
			scanf("%d", &x);
			Insert(&seq, pos, x);
			break;
		case PUSHBACK:
			printf("请输入插入元素的值：>");
			scanf("%d", &x);
			PushBack(&seq,x);
			break;
		case POPBACK:
			PopBack(&seq);
			break;
		case PUSHFRONT:
			printf("请输入插入元素的值：>");
			scanf("%d", &x);
			PushFront(&seq,x);
			break;
		case POPFRONT:
			PopFront(&seq);
			break;
		case SORT:
			Sort(&seq);
			break;
		case BINARYSEARCH:
			printf("请输入查找元素的值：>");
			scanf("%d", &x);
			BinarySearch(&seq, x);
			break;
		case REMOVE:
			printf("请输入要删除的元素：>");
			scanf("%d", &x);
			Remove(&seq, x);
			break;
		case REMOVEALL:
			printf("请输入要删除的元素：>");
			scanf("%d", &x);
			RemoveAll(&seq, x);
			break;
		}
	}
}
int main()
{
	test();
	system("pause");
	return 0;
}


静态顺序表编码的注意：
（1）删除之前必须对顺序表是否为空进行检查，如果为空不可删除。
（2）插入之前必须对顺序表是否满进行检查，如果已满，不可插入。
（3）折半查找之前必须对元素排序。（这个属于两个版本共同需要注意的）
下边给出动态顺序表的实现代码：
//SeqList.h
#ifndef __SEQLIST_H__
#define __SEQLIST_H__
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
enum OP
{
	EXIT,
	PRINT,
	PUSHBACK,
	POPBACK,
	PUSHFRONT,
	POPFRONT,
	REMOVE,
	REMOVEALL,
	BOTTLESORT,
	INSERTSORT,
	SELECTSORT,
	BINARYSEARCH,
	ERASE
};
#define DEFAULT_SIZE 3
typedef int DataType;
typedef struct Seqlist
{
	DataType *data;
	int size;
	int capacity;
}SeqList,*pSeqList;
void InitSeqList(pSeqList pSeq);
void DestroySeqList(pSeqList pSeq);
void PushBack(pSeqList pSeq,DataType x);
void PopBack(pSeqList pSeq);
void PushFront(pSeqList pSeq,  DataType x);
void PopFront(pSeqList pSeq);
void Remove(pSeqList pSeq, DataType x);
void RemoveAll(pSeqList pSeq, DataType x);
void BubbleSort(pSeqList pSeq);
void InsertSort(pSeqList pSeq);
void SelectSort(pSeqList pSeq);
void BinarySearch(pSeqList pSeq);
void Erase(pSeqList pSeq,int pos);
void PrintSeqList(pSeqList pSeq);
#endif// __SEQLIST_H__
//SeqList.c
#include"SeqList.h"

void check_capacity(pSeqList pSeq)
{
	assert(pSeq);
	if (pSeq->capacity == pSeq->size)
	{
		DataType *tmp = (DataType *)realloc(pSeq->data,(pSeq->capacity +DEFAULT_SIZE)*sizeof(DataType));
		if (NULL == tmp)
		{
			printf("out of memory.");
			exit(EXIT_FAILURE);
		}
		else
		{
			pSeq->data = tmp;
			pSeq->capacity += DEFAULT_SIZE;
		}
	}
}
void InitSeqList(pSeqList pSeq)
{
	assert(pSeq);
	pSeq->data = (DataType*)malloc(2*sizeof(DataType));
	if (NULL == pSeq->data)
	{
		printf("out of memory\n");
		exit(EXIT_FAILURE);
	}
	pSeq->size = 0;
	pSeq->capacity = 2;
}
void DestroySeqList(pSeqList pSeq)
{
	assert(pSeq);
	free(pSeq->data);
	pSeq->size = 0;
	pSeq->capacity = 0;
	pSeq->data = NULL;
}
void PushBack(pSeqList pSeq, DataType x)
{
	assert(pSeq);
	check_capacity(pSeq);
	pSeq->data[pSeq->size] = x;
	pSeq->size++;
	printf("尾插成功！\n");
}
void PopBack(pSeqList pSeq)
{
	assert(pSeq);
	if (0 == pSeq->size)
	{
		printf("seqlist is empty.\n");
		exit(EXIT_FAILURE);
	}
	pSeq->size--;
	printf("尾删成功！\n");
}
void PushFront(pSeqList pSeq, DataType x)
{
	assert(pSeq);
	check_capacity(pSeq);
	int i = 0;
	for (i = pSeq->size - 1;i >= 0;i--)
	{
		pSeq->data[i + 1] = pSeq->data[i];
	}
	pSeq->data[0] = x;
	pSeq->size++;
	printf("头插成功！\n");
}
void PopFront(pSeqList pSeq)
{
	assert(pSeq);
	if (0 == pSeq->size)
	{
		printf("seqlist is empty.\n");
		exit(EXIT_FAILURE);
	}
	int i = 0;
	for (i = 1;i < pSeq->size - 1;i++)
	{
		pSeq->data[i - 1] = pSeq->data[i];
	}
	pSeq->size--;
	printf("头删成功！\n");
}
void Remove(pSeqList pSeq, DataType x)
{
	assert(pSeq);
	int i = 0;
	int j = 0;
	if (0 == pSeq->size)
	{
		printf("seqlist is empty.\n");
		exit(EXIT_FAILURE);
	}
	for (i = 0;i < pSeq->size;i++)
	{
		if (x == pSeq->data[i])
			break;
	}
	for (j = i + 1;j < pSeq->size;j++)
	{
		pSeq->data[j - 1] = pSeq->data[j];
	}
	pSeq->size--;
	printf("删除指定元素成功！\n");
}
void RemoveAll(pSeqList pSeq, DataType x)
{
	assert(pSeq);
	int i = 0;
	int count = 0;
	int j = 0;
	if (0 == pSeq->size)
	{
		printf("seqlist is empty.\n");
		exit(EXIT_FAILURE);
	}
	/*for (i = 0;i < pSeq->size;i++)
	{
		if (pSeq->data[i] == x)
		{
			count++;
		}
	}*/
	i = 0;
	j = pSeq->size - 1;
	/*while (j >= pSeq->size - count && i < pSeq->size - count)
	{
		if (pSeq->data[j] != x && pSeq->data[i] == x)
		{
			pSeq->data[i] = pSeq->data[j];
		}
		j--;
		i++;
	}*/
	while (i < pSeq->size)
	{
		if (pSeq->data[i] == x)
		{
			while (pSeq->data[j] == x)
			{
				j--;
			}
			pSeq->data[i] = pSeq->data[j];
			count++;
		}
		i++;
	}
	pSeq->size -= count;
	printf("delete success！\n");
}
void BubbleSort(pSeqList pSeq)
{
	assert(pSeq);
	if (0 == pSeq->size)
	{
		printf("seqlist is empty.\n");
		exit(EXIT_FAILURE);
	}
	int i = 0;
	int j = 0;
	int k = pSeq->size - 1;
	int tmp = 0;
	int m = 0;
	int flag = 0;
	for (i = 0;i < pSeq->size - 1;i++)
	{
		flag = 1;
		for (j = 0;j < k;j++)
		{
			if (pSeq->data[j]>pSeq->data[j + 1])
			{
				tmp = pSeq->data[j];
				pSeq->data[j] = pSeq->data[j + 1];
				pSeq->data[j + 1] = tmp;
				m = j;//m is used for recording the position of last swap
				flag = 0;
			}
		}
		k = m;
		if (flag == 1)
		{
			break;
		}
	}
	printf("successful bottlesort\n");
}
void InsertSort(pSeqList pSeq)
{
	assert(pSeq);
	if (0 == pSeq->size)
	{
		printf("seqlist is empty.\n");
		exit(EXIT_FAILURE);
	}
	int i = 0;
	int j = 0;
	int tmp = 0;
	for (i = 1;i < pSeq->size;i++)
	{
		tmp = pSeq->data[i];
		for (j = i - 1;j >= 0 && pSeq->data[j] > tmp;j--)
		{
			pSeq->data[j + 1] = pSeq->data[j];
		}
		pSeq->data[j + 1] = tmp;
	}
	printf("successful insertsort\n");
}
void SelectSort(pSeqList pSeq)
{
	assert(pSeq);
	if (0 == pSeq->size)
	{
		printf("seqlist is empty.\n");
		exit(EXIT_FAILURE);
	}
	int i = 0;
	int j = 0;
	int min = 0;//the index of min number
	int tmp = 0;
	for (i = 0;i < pSeq->size;i++)
	{
		min = i;
		for (j = i;j < pSeq->size;j++)
		{
			if (pSeq->data[j] < pSeq->data[min])
			{
				min = j;
			}
		}
		if (min != i)
		{
			tmp = pSeq->data[i];
			pSeq->data[i] = pSeq->data[min];
			pSeq->data[min] = tmp;
		}
	}
	printf("successful selectsort\n");
}
void BinarySearch(pSeqList pSeq, DataType x)
{
	assert(pSeq);
	if (0 == pSeq->size)
	{
		printf("seqlist is empty.\n");
		exit(EXIT_FAILURE);
	}
	SelectSort(pSeq);//before searching,we must sort seqlist
	int left = 0;
	int right = pSeq->size - 1;
	int middle = 0;
	while (left < right)
	{
		middle = (left + right) / 2;
		if (x == pSeq->data[middle])
		{
			printf("have found\n");
			return;
		}
		else if (x < pSeq->data[middle])
		{
			right = middle - 1;
		}
		else
		{
			left = middle + 1;
		}
	}
	printf("not found\n");
}
void Erase(pSeqList pSeq, int pos)
{
	assert(pSeq);
	if (0 == pSeq->size)
	{
		printf("seqlist is empty.\n");
		exit(EXIT_FAILURE);
	}
	pSeq->data[pos] = pSeq->data[pSeq->size - 1];
	pSeq->size--;
	printf("successful delete designated position\n");
}
void PrintSeqList(pSeqList pSeq)
{
	assert(pSeq);
	int i = 0;
	printf("动态顺序表中的元素为：\n");
	for (i = 0;i < pSeq->size;i++)
	{
		printf("%d ",pSeq->data[i]);
	}
	printf("\n");
}
//test.c
#include"SeqList.h"
void menu()
{
	printf("-------动态顺序表管理系统-------\n");
	printf("-------0.退出-------------------\n");
	printf("-------1.显示-------------------\n");
	printf("-------2.尾插-------------------\n");
	printf("-------3.尾删-------------------\n");
	printf("-------4.头插-------------------\n");
	printf("-------5.头删-------------------\n");
	printf("-------6.删除指定---------------\n");
	printf("-------7.删除指定全部-----------\n");
	printf("-------8.冒泡排序---------------\n");
	printf("-------9.插入排序---------------\n");
	printf("-------10.选择排序--------------\n");
	printf("-------11.折半查找---------------\n");
	printf("-------12.删除指定位置-----------\n");
}
void test()
{
	SeqList seq;
	pSeqList pSeq = &seq;
	DataType x = 0;
	int input = 1;
	int pos = 0;
	InitSeqList(pSeq);
	while (input)
	{
		menu();
		printf("请选择：>");
		scanf("%d",&input);
		switch (input)
		{
		case EXIT:
			DestroySeqList(pSeq);
			break;
		case PRINT:
			PrintSeqList(pSeq);
			break;
		case PUSHBACK:
			printf("请输入要插入的元素：\n");
			scanf("%d",&x);
			PushBack(pSeq,x);
			break;
		case POPBACK:
			PopBack(pSeq);
			break;
		case PUSHFRONT:
			printf("请输入要插入的元素：\n");
			scanf("%d", &x);
			PushFront(pSeq,x);
			break;
		case POPFRONT:
			PopFront(pSeq);
			break;
		case BOTTLESORT:
			BubbleSort(pSeq);
			break;
		case SELECTSORT:
			SelectSort(pSeq);
			break;
		case INSERTSORT:
			InsertSort(pSeq);
			break;
		case ERASE:
			printf("请输入要删除元素的位置：\n");
			scanf("%d", &pos);
			Erase(pSeq, pos);
			break;
		case BINARYSEARCH:
			printf("请输入要查找的元素：\n");
			scanf("%d", &x);
			BinarySearch(pSeq, x);
			break;
		case REMOVE:
			printf("请输入要删除的元素：\n");
			scanf("%d", &x);
			Remove(pSeq, x);
			break;
		case REMOVEALL:
			printf("请输入要删除的元素：\n");
			scanf("%d", &x);
			RemoveAll(pSeq, x);
			break;
		}
	}
}
int main()
{
	test();
	system("pause");
	return 0;
}


动态顺序表的注意事项：
（1）插入之前对顺序表的大小与顺序表容量之间的关系进行判断，如果相等，扩容。
（2）删除、排序等操作之前需要对顺序表是否为空进行判断。
在最近经常碰到以下错误：（如图）


读取位置发生冲突，这是因为没有对某些数据进行初始化导致错误，以上错误就是未调
用初始化函数导致。
有时，程序运行着运行着，就会突然崩，弹出一个窗口，某处触发了一个断点，这是因
为这个地方的函数参数搞错导致吧。
如果是提示某处写入异常，可能是对常量赋值导致吧。
以上内容如有问题，请指出~~

收起

展开全文

顺序表和链表实现图书管理系统

千次阅读 多人点赞 2019-10-10 08:25:39

顺序表和链表实现图书管理系统本次记录的是数据结构课程的实验，实验内容如下：图书信息表包括如下常用的基本操作：图书信息表的创建和输出、排序（分别按图书名称、按图书价格排序）、修改、按名查找、最贵图书的...




数据结构文章推荐：




👉 多种方式实现英文单词词频统计和检索系统


👉 指针如何赋值？关于指针的理解


👉 深度优先搜索判断有向图路径是否存在


👉 待更新


顺序表和链表实现图书管理系统
      本次记录的是数据结构课程的实验，实验内容如下：

      图书信息表包括如下常用的基本操作：图书信息表的创建和输出、排序（分别按图书名称、按图书价格排序）、修改、按名查找、最贵图书的查找、新书入库、旧书出库等八项。

      其中，图书信息包括如下6部分：

      ISBN、作者姓名、图书名称、出版社、出版年份、图书价格

文章目录
       1. 代码实现

       2. 运行效果

       3. 实验总结

1、代码实现
顺序表代码实现
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define maxsize 50    //图书库存最大数量
//函数结果状态代码
#define OK 1          //正确标志
#define ERROR 0  //错误标志
//函数结果状态代码
typedef int Status;

typedef struct{
    int id; //管理系统中的id
    char isbn[20];    //ISBN
    char authorName[30];    //作者姓名
    char bookName[50];    //图书名称
    char publisher[40];   //出版社
    char publishYear[10];     //出版年份
    float price;   //图书价格
}Book;
//顺序表数据结构
typedef struct{
    Book *elem;   //储存空间的基地址
    int length;   //数据结构的长度
}SqList;
SqList BookSystem;

//初始化顺序表基本算法
Status InitList(SqList *BookSystem){
    //构造一个空的顺序表BookSystem
    BookSystem->elem =  (Book*)malloc(sizeof(Book)*maxsize);   //分配内存空间
    if(!BookSystem->elem)exit(-1);   //存储分配失败
    BookSystem->length = 0;  //当前长度为0
    return OK;
}

//用于测试数据,更易看出实验效果
void insertBook(SqList *BookSystem){
    Book book[] = {{1,"5447395","余小华","《这么玩才赚钱》","人民邮电出版社","2017-01",49.50},
        {2,"4375152","达芙妮","《高情商心理学》","现代出版社","2016-11",20.00},
        {3,"6644188","郝言言","《悦己》","新华出版社","2007-04",25.00},
        {4,"0211267","路瑶","《平凡的世界》","北京文艺出版社","1986-12",30.00},
        {5,"6075642","张汝","《小时候》","海燕出版社","2013-06",33.00},
        {6,"1553645","陈果","《好的爱情》","人民日报出版社","2010-09",28.00}};
    int i = 0;  //循环变量
    for(i;i<6;i++){
        BookSystem->elem[i] = book[i];   //初始化图书
        BookSystem->length++;
    }
}

//8项操作的实现：创建、输出、排序、修改、按名查找、最贵图书的查找、新书入库、旧书出库
int showFunctions(){//显示图书管理系统功能
    printf("%-30s***************欢迎来到图书管理系统***************\n","");
    printf("%-33s1、创建系统\t2、输出图书\t3、图书排序\n%-33s4、图书修改\t5、按名查找\t6、最贵图书\n%-33s7、新书入库\t8、旧书出库\t9、退出系统","","","");
    printf("\n%-33s请选择相关功能操作：","");
    int choice = -1;    //定义用户的选择并初始化
    scanf("%d",&choice);
    printf("%-30s**************************************************\n","");
    return choice;
}

void creatBookSystem(SqList *BookSystem){//第一项功能：创建
    int i = 0;
    /*for(i;i<30;i++){
        printf("*");
    }printf("\n");*/
    printf("%-30s系统：图书管理系统初始化中...\n","");
    //SqList BookSystem;     //定义SqList类型的图书库
    InitList(BookSystem);   //初始化图书管理系统
    insertBook(BookSystem);     //添加一些初始化图书
    printf("%-30s系统：图书管理系统初始化成功!\n","");
}

void showBook(SqList *BookSystem){//第二项功能：输出
    int j = 0;
    for(j;j<115;j++){
        printf("=");
    }
    printf("\n");
    printf("    -id-   ---ISBN---    --作者姓名--     ---图书名称---       -----出版社-----       -出版年份-     -图书价格-\n");
    if(BookSystem->length == 0){
        printf("%-30s系统：当前图书系统内无图书!","");
    }
    int i = 0;
    for(i;i<BookSystem->length;i++){
        Book book = BookSystem->elem[i];
        printf("%-5s%-8d","",book.id);
        printf("%-15s",book.isbn);
        printf("%-13s",book.authorName);
        printf("%-23s",book.bookName);
        printf("%-24s",book.publisher);
        printf("%-14s",book.publishYear);
        printf("%.3f\n",book.price);
    }
    for(j=0;j<115;j++){
        printf("=");
    }
    printf("\n");
}

void sortBook(SqList *BookSystem){//第三项功能：排序
    int i = 0;int j = 0;int max_Index = -1;int choice = -1;Book temp;
    printf("%-33s1、按名称排序\t2、按价格排序\t请选择：","");
    scanf("%d",&choice);
    if(choice==1){
        for(i;i<BookSystem->length-1;i++){
            max_Index = i;
            for(j=i+1;j<BookSystem->length;j++){
                if(strcmp(BookSystem->elem[max_Index].bookName,BookSystem->elem[j].bookName)>0){
                    max_Index=j;
                }
            }
            temp = BookSystem->elem[i];
            BookSystem->elem[i] = BookSystem->elem[max_Index];
            BookSystem->elem[max_Index] = temp;
        }
    }
    if(choice==2){
        for(i;i<BookSystem->length-1;i++){
            max_Index = i;
            for(j=i+1;j<BookSystem->length;j++){
                if(BookSystem->elem[max_Index].price<BookSystem->elem[j].price){
                    max_Index=j;
                }
            }
            temp = BookSystem->elem[i];
            BookSystem->elem[i] = BookSystem->elem[max_Index];
            BookSystem->elem[max_Index] = temp;
        }
    }
    printf("%-30s系统：排序完毕!\n","");
    i = 0;
    for(i=0;i<BookSystem->length;i++){
        BookSystem->elem[i].id = i+1;
    }
}

void updateBook(SqList *BookSystem){//第四项功能：修改
    printf("%-30s系统：请输入您要修改的书籍名称或id：","");
    char ch[50];
    scanf("%s",&ch);
    int id = atoi(ch);int i = 0;
    if(id==0){
        for(i;i<BookSystem->length;i++){
            if(strcmp(ch,BookSystem->elem[i].bookName)==0){
                printf("%-30s系统：","");
                Book book = BookSystem->elem[i];
                printf("(%s-%s-%s-%s-[%s]-%.3f)\n",book.isbn,book.authorName,
                       book.bookName,book.publisher,book.publishYear,book.price);
                printf("%-30s修改格式：(ISBN 作者姓名 图书名称 出版社 出版年份 图书价格)\n%-30s请输入：","","");
                scanf("%s %s %s %s %s %f",&BookSystem->elem[i].isbn,&BookSystem->elem[i].authorName,&BookSystem->elem[i].bookName,
                      &BookSystem->elem[i].publisher,&BookSystem->elem[i].publishYear,&BookSystem->elem[i].price);
                printf("%-30s系统：修改成功!\n","");
                break;
            }
        }
    }else{
        for(i;i<BookSystem->length;i++){
            if(BookSystem->elem[i].id == id){
                printf("%-30s系统：","");
                Book book = BookSystem->elem[i];
                printf("(%s-%s-%s-%s-[%s]-%.3f)\n",book.isbn,book.authorName,
                       book.bookName,book.publisher,book.publishYear,book.price);
                printf("%-30s修改格式：(ISBN 作者姓名 图书名称 出版社 出版年份 图书价格)\n%-30s请输入：","","");
                scanf("%s %s %s %s %s %f",&BookSystem->elem[i].isbn,&BookSystem->elem[i].authorName,&BookSystem->elem[i].bookName,
                      &BookSystem->elem[i].publisher,&BookSystem->elem[i].publishYear,&BookSystem->elem[i].price);
                printf("%-30s系统：修改成功!\n","");
                break;
            }
        }
    }
}

void findByName(SqList *BookSystem){//第五项功能：按名查找
    printf("%-30s系统：请输入您要查找的书籍名称：","");
    char ch[50];
    scanf("%s",&ch);
    int i = 0;
    for(i;i<BookSystem->length;i++){
        if(strcmp(ch,BookSystem->elem[i].bookName)==0){
            printf("%-30s系统：","");
            Book book = BookSystem->elem[i];
            printf("(%s-%s-%s-%s-[%s]-%.3f)\n",book.isbn,book.authorName,
                       book.bookName,book.publisher,book.publishYear,book.price);
            break;
        }else if(i==BookSystem->length-1&&strcmp(ch,BookSystem->elem[i].bookName)!=0){
            printf("%-30s系统：查无此书!\n","");
        }
    }
}

void findByExpensive(SqList *BookSystem){//第六项：最贵图书查找
    int j = 0;int max_Index = 0;
        for(j=max_Index+1;j<BookSystem->length;j++){
            if(BookSystem->elem[max_Index].price<BookSystem->elem[j].price){
                max_Index=j;
            }
        }
    printf("%-30s系统：","");
    Book book = BookSystem->elem[max_Index];
    printf("(%s-%s-%s-%s-[%s]-%.3f)\n",book.isbn,book.authorName,
                       book.bookName,book.publisher,book.publishYear,book.price);
}

void addBook(SqList *BookSystem){//第七项：新书入库
    if(BookSystem->length==maxsize){
        printf("%-30s系统：库存已满!","");
    }
    else{
        printf("%-30s添加格式：(ISBN 作者姓名 图书名称 出版社 出版年份 图书价格)\n%-30s请输入：","","");
        int index = ++BookSystem->length;
        Book newBook;
        scanf("%s %s %s %s %s %f",&newBook.isbn,&newBook.authorName,
                  &newBook.bookName,&newBook.publisher,
                  &newBook.publishYear,&newBook.price);
        newBook.id = index;
        BookSystem->elem[index-1] = newBook;
        //9787115447395 黄鹏飞 《代码是如何敲成的》 人民出版社 2019-10 33->00  用于测试
        printf("%-30s系统：入库成功!\n","");
    }
}

void outBook(SqList *BookSystem){//第八项：旧书出库
    printf("%-30s系统：请输入要出库的书籍名称或id：","");
    char ch[50];
    scanf("%s",&ch);
    int id = atoi(ch);int i = 0;
    if(id==0){
        for(i;i<BookSystem->length;i++){
            if(strcmp(ch,BookSystem->elem[i].bookName)==0){
                int j = i;
                for(j=i;j<BookSystem->length-1;j++){
                    BookSystem->elem[j] = BookSystem->elem[j+1];
                }
                BookSystem->length--;
                printf("%-30s系统：出库成功!\n","");
                break;
            }else if(i==BookSystem->length-1&&strcmp(ch,BookSystem->elem[i].bookName)!=0){
                printf("%-30s系统：查无此书!\n","");
            }
        }
    }else{
        for(i;i<BookSystem->length;i++){
            if(BookSystem->elem[i].id==id){
                int j = i;
                for(j=i;j<BookSystem->length-1;j++){
                    BookSystem->elem[j] = BookSystem->elem[j+1];
                }
                BookSystem->length--;
                printf("%-30s系统：出库成功!\n","");
                break;
            }else if(i==BookSystem->length-1&&strcmp(ch,BookSystem->elem[i].bookName)!=0){
                printf("%-30s系统：查无此书!\n","");
            }
        }
    }
    for(i=0;i<BookSystem->length;i++){
        BookSystem->elem[i].id = (i+1);
    }
}

int main()
{
    bool isCreated = false;
    while(true){
        int choice = showFunctions();   //调用函数取得用户选择的功能
        if(choice == 1){
            creatBookSystem(&BookSystem);
            isCreated = true;
            continue;
        }
        if(choice == 2&&isCreated){
            system("cls");
            showBook(&BookSystem);
            continue;
        }
        if(choice==3&&isCreated){
            sortBook(&BookSystem);
            continue;
        }
        if(choice==4&&isCreated){
            updateBook(&BookSystem);
            continue;
        }
        if(choice==5&&isCreated){
            findByName(&BookSystem);
            continue;
        }
        if(choice==6&&isCreated){
            findByExpensive(&BookSystem);
            continue;
        }
        if(choice==7&&isCreated){
            addBook(&BookSystem);
            continue;
        }
        if(choice==8&&isCreated){
            outBook(&BookSystem);
            continue;
        }
        if(choice==9){
            printf("%-30s系统：欢迎下次使用!\n\n\n","");
            break;
        }
        if(choice>9||choice<1){
            printf("%-30s系统：请输入正确选项!\n","");
            continue;
        }
        printf("%-30s系统：您还未创建图书管理系统!\n","");
    }
    return 0;
}

链表代码实现
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//函数结果状态代码
#define OK 1          //正确标志
#define ERROR 0  //错误标志
//函数结果状态代码
typedef int Status;

typedef struct{
    int id; //管理系统中的id
    char isbn[20];    //ISBN
    char authorName[30];    //作者姓名
    char bookName[50];    //图书名称
    char publisher[40];   //出版社
    char publishYear[10];     //出版年份
    float price;   //图书价格
}Book;
//顺序表数据结构
typedef struct LNode{
    Book book;   //当前节点中的Book结构体
    struct LNode *next;   //next指向下一个LNode
}LNode,*LinkList;
LinkList BookSystem;

//8项操作的实现：创建、输出、排序、修改、按名查找、最贵图书的查找、新书入库、旧书出库
int showFunctions(){//显示图书管理系统功能
    printf("%-30s***************欢迎来到图书管理系统***************\n","");
    printf("%-33s1、创建系统\t2、输出图书\t3、图书排序\n%-33s4、图书修改\t5、按名查找\t6、最贵图书\n%-33s7、新书入库\t8、旧书出库\t9、退出系统","","","");
    printf("\n%-33s请选择相关功能操作：","");
    int choice = -1;    //定义用户的选择并初始化
    scanf("%d",&choice);
    printf("%-30s**************************************************\n","");
    return choice;
}

void creatBookSystem(){//第一项功能：创建
    BookSystem = (LinkList)malloc(sizeof(LNode));
    BookSystem->next = NULL;
    int i = 0; //初始给6个节点
    Book book[] = {{1,"5447395","余小华","《这么玩才赚钱》","人民邮电出版社","2017-01",49.50},
        {2,"4375152","达芙妮","《高情商心理学》","现代出版社","2016-11",20.00},
        {3,"6644188","郝言言","《悦己》","新华出版社","2007-04",25.00},
        {4,"0211267","路瑶","《平凡的世界》","北京文艺出版社","1986-12",30.00},
        {5,"6075642","张汝","《小时候》","海燕出版社","2013-06",33.00},
        {6,"1553645","陈果","《好的爱情》","人民日报出版社","2010-09",28.00}};
    for(i;i<6;i++){
        LNode *node = (LinkList)malloc(sizeof(LNode));  //生成新节点
        node->book = book[5-i];
        node->next = BookSystem->next;
        BookSystem->next = node;
    }
    printf("%-30s系统：图书管理系统初始化成功!\n","");
}

void showBook(){//第二项功能：输出
    int j = 0;LNode *temp = BookSystem->next;
    for(j;j<115;j++){
        printf("=");
    }
    printf("\n");
    printf("    -id-   ---ISBN---    --作者姓名--     ---图书名称---       -----出版社-----       -出版年份-     -图书价格-\n");
    if(temp == 0){
        printf("%-30s系统：当前图书系统内无图书!","");
    }else{
        while(temp){
            Book book = temp->book;
            printf("%-5s%-8d","",book.id);
            printf("%-15s",book.isbn);
            printf("%-13s",book.authorName);
            printf("%-23s",book.bookName);
            printf("%-24s",book.publisher);
            printf("%-14s",book.publishYear);
            printf("%.3f\n",book.price);
            temp = temp->next;
        }
    }
    int i = 0;
    for(j=0;j<115;j++){
        printf("=");
    }
    printf("\n");
}

void sortBook(){//第三项功能：排序
    int choice = -1;bool isCompared = false;
    printf("%-33s1、按名称排序\t2、按价格排序\t请选择：","");
    scanf("%d",&choice);
    if(choice==1){
        LNode *node = BookSystem->next;     //循环体条件
        LNode *temp;     //临时变量
        Book maxBook;   //比较的书
        LNode *temp_book = node;   //临时变量
        while(node->next){
            maxBook = node->book;
            temp_book = node;
            while(temp_book){
                if(strcmp(maxBook.bookName,temp_book->book.bookName)>0){
                    maxBook = temp_book->book;
                    temp = temp_book;
                    isCompared = true;
                }
                temp_book = temp_book->next;
            }
            if(isCompared){
                temp->book = node->book;
                node->book = maxBook;
                isCompared = false;     //*突破点
            }
                node = node->next;
        }
    }
    if(choice==2){
        LNode *node = BookSystem->next;     //循环体条件
        LNode *temp = BookSystem->next;     //临时变量
        Book maxBook;   //比较的书
        LNode *temp_book;   //临时变量
        while(node->next){
            maxBook = node->book;
            temp_book = node;
            while(temp_book){
                if(maxBook.price<temp_book->book.price){
                    maxBook = temp_book->book;
                    temp = temp_book;
                    isCompared = true;
                }
                temp_book = temp_book->next;
            }
            if(isCompared){
                temp->book = node->book;
                node->book = maxBook;
                isCompared = false;
            }
                node = node->next;
        }
    }
    printf("%-30s系统：排序完毕!\n","");
    int i = 0;
    LNode *node = BookSystem->next;
    while(node){
        node->book.id = ++i;
        node = node->next;
    }
}

void updateBook(){//第四项功能：修改
    printf("%-30s系统：请输入您要修改的书籍名称或id：","");
    char ch[50];
    scanf("%s",&ch);
    int id = atoi(ch);int i = 0;
    LNode *p = BookSystem->next;
    if(id==0){
        while(p){
            if(strcmp(ch,p->book.bookName)==0){
                printf("%-30s系统：","");
                Book book = p->book;
                printf("(%s-%s-%s-%s-[%s]-%.3f)\n",book.isbn,book.authorName,
                       book.bookName,book.publisher,book.publishYear,book.price);
                printf("%-30s修改格式：(ISBN 作者姓名 图书名称 出版社 出版年份 图书价格)\n%-30s请输入：","","");
                scanf("%s %s %s %s %s %f",&p->book.isbn,&p->book.authorName,&p->book.bookName,
                      &p->book.publisher,&p->book.publishYear,&p->book.price);
                printf("%-30s系统：修改成功!\n","");
                break;
            }
            p=p->next;
        }
    }else{
        while(p){
            if(p->book.id == id){
                printf("%-30s系统：","");
                Book book = p->book;
                printf("(%s-%s-%s-%s-[%s]-%.3f)\n",book.isbn,book.authorName,
                       book.bookName,book.publisher,book.publishYear,book.price);
                printf("%-30s修改格式：(ISBN 作者姓名 图书名称 出版社 出版年份 图书价格)\n%-30s请输入：","","");
                scanf("%s %s %s %s %s %f",&p->book.isbn,&p->book.authorName,&p->book.bookName,
                      &p->book.publisher,&p->book.publishYear,&p->book.price);
                printf("%-30s系统：修改成功!\n","");
                break;
            }
            p=p->next;
        }
    }
}

void findByName(){//第五项功能：按名查找
    printf("%-30s系统：请输入您要查找的书籍名称：","");
    char ch[50];
    scanf("%s",&ch);
    int i = 0;
    LNode *p = BookSystem->next;
    while(p){
        if(strcmp(ch,p->book.bookName)==0){
            printf("%-30s系统：","");
            Book book = p->book;
            printf("(%s-%s-%s-%s-[%s]-%.3f)\n",book.isbn,book.authorName,
                       book.bookName,book.publisher,book.publishYear,book.price);
            break;
        }
        p=p->next;
    }
}

void findByExpensive(){//第六项：最贵图书查找
    LNode *node = BookSystem->next;     //循环体条件
    Book maxBook;   //比较的书
    LNode *temp_book;   //临时变量
    while(node->next){
        maxBook = node->book;
        temp_book = node->next;
        while(temp_book->next){
            if(maxBook.price<temp_book->book.price){
                maxBook = temp_book->book;
            }
            temp_book = temp_book->next;
        }
        break;
    }
    printf("%-30s系统：","");
    Book book = maxBook;
   printf("(%s-%s-%s-%s-[%s]-%.3f)\n",book.isbn,book.authorName,
                       book.bookName,book.publisher,book.publishYear,book.price);
}

void addBook(){//第七项：新书入库
    LNode *p = BookSystem->next;
    LNode *book = (LinkList)malloc(sizeof(LNode));
    int index = 0;
    while(p->next){
        index++;
        p = p->next;
    }
    printf("%-30s添加格式：(ISBN 作者姓名 图书名称 出版社 出版年份 图书价格)\n%-30s请输入：","","");
    Book newBook;
    scanf("%s %s %s %s %s %f",&newBook.isbn,&newBook.authorName,
              &newBook.bookName,&newBook.publisher,
              &newBook.publishYear,&newBook.price);
    newBook.id = index;
    book->book = newBook;
    p->next = book;
    book->next = 0;
    printf("%-30s系统：入库成功!\n","");
}

void outBook(){//第八项：旧书出库
    printf("%-30s系统：请输入您要修改的书籍名称或id：","");
    char ch[50];
    scanf("%s",&ch);
    int id = atoi(ch);
    LNode *p = BookSystem->next;
    LNode *book = BookSystem;
    if(id==0){
        while(p){
            if(strcmp(ch,p->book.bookName)==0){
                book->next = p->next;
                p->next = 0;
                printf("%-30s系统：出库成功!\n","");
                break;
            }else if(strcmp(ch,p->book.bookName)!=0&&!p->next){
                printf("%-30s系统：查无此书!\n","");
            }
            book=book->next;
            p=p->next;
        }
    }else{
        while(p){
            if(id==p->book.id){
                book->next = p->next;
                p->next = 0;
                printf("%-30s系统：出库成功!\n","");
                break;
            }else if(strcmp(ch,p->book.bookName)!=0&&!p->next){
                printf("%-30s系统：查无此书!\n","");
            }
            book=book->next;
            p=p->next;
        }
    }
    int i = 0;
    LNode *node = BookSystem->next;
    while(node){
        node->book.id = ++i;
        node = node->next;
    }
}

int main()
{
    bool isCreated = false;
    while(true){
        int choice = showFunctions();   //调用函数取得用户选择的功能
        if(choice == 1){
            creatBookSystem();
            isCreated = true;
            continue;
        }
        if(choice == 2&&isCreated){
            system("cls");
            showBook();
            continue;
        }
        if(choice==3&&isCreated){
            sortBook();
            continue;
        }
        if(choice==4&&isCreated){
            updateBook();
            continue;
        }
        if(choice==5&&isCreated){
            findByName();
            continue;
        }
        if(choice==6&&isCreated){
            findByExpensive();
            continue;
        }
        if(choice==7&&isCreated){
            addBook();
            continue;
        }
        if(choice==8&&isCreated){
            outBook();
            continue;
        }
        if(choice==9){
            printf("%-30s系统：欢迎下次使用!\n\n\n","");
            break;
        }
        if(choice>9||choice<1){
            printf("%-30s系统：请输入正确选项!\n","");
            continue;
        }
        printf("%-30s系统：您还未创建图书管理系统!\n","");
    }
    return 0;
}


2、运行效果
具体运行效果请看视频：项目演示视频

3、实验总结

因为C语言是大一上学期学的，我也没有去学顺序表和链表。到了下学期直到现在我都是学Java方面的知识，所以对顺序表和链表的不是很熟练，所以上面写的代码也许会有漏洞或者不好的地方请见谅！
做了这次实验，我感觉到链表确实比顺序表要麻烦，有的时候指针指向的问题搞了好久才解决，但是自己解决了之后加强了印象并且对链表的了解更深了。
该文章主要是记录一下这次实验，同时能给需要的人帮助是再好不过的事了，但我希望有需要的同学不是粘贴复制而是自己动手实践，我写的也只是一个参考。

            最后：如果有问题的话欢迎交流！有帮助的话别忘了支持一下哦！

数据结构文章推荐：
👉 多种方式实现英文单词词频统计和检索系统
👉 指针如何赋值？关于指针的理解
👉 深度优先搜索判断有向图路径是否存在
👉 待更新

收起

展开全文

管理系统 C语言链表图书管理系统

顺序表（笔记）
万次阅读 2021-04-20 07:53:05
顺序表可以随机访问，即通过表头和元素编号进行访问。 #include <stdio.h> #include <stdlib.h> //定义顺序表的结构体 typedef struct vector{ int size; //顺序表总容量 int length //顺序表当前个...
收起
顺序表插入数据
千次阅读 2019-07-21 13:28:33
1、创建顺序表 2、初始化顺序表 3、构建逻辑存储结构： typedef struct{ ElemType *elem; int Length; int ListSize; }SqList; 函数：ListInsertSq(SqList &L,int Location,ElemType Elem) ...
收起
数据结构
Java 实现顺序表的基本操作
千次阅读 2019-06-08 17:12:38
顺序表 静态顺序表：使用定长数组存储。动态顺序表：使用动态开辟的数组存储。接口 package com.github.sqlist; public interface ISequence { // 在 pos 位置插入 val boolean add(int pos, Object data); /...
收起
java 数据结构
顺序表的基本操作：初始化，创建新表，删除元素，插入元素，定位元素，打印顺序表，返回长度
千次阅读 2019-07-25 09:42:25
该程序实现了一个顺序表的基本操作： int InitList_Sq(); //初始化线性表 void CreateSqList(); //创建线性表 void ListInsert(); //向线性表中插入值 void ListDelete(); //删除顺序表中的数据元素 void Print...
收起
c语言数据结构
PTA 6-2顺序表操作集
千次阅读 2018-03-13 20:18:22
这道题题目很简单，但是我一直写错了一个...比较对照之后才能发现自己的问题吧，本来觉得也可以自己一步步调试的，但是实在是懒，不过这种错误还是很好发现的，希望自己以后在顺序表上不会犯这种低级错误。 6-2 ...
收起
数据结构c语言版严蔚敏 顺序表
千次阅读 2019-02-21 21:13:40
说来惭愧由于贪玩，数据结构挂科了，现在重新学一遍数据结构，...listsize代表这个顺序表的最大容量可以随时扩容 length代表表中元素个数应小于listsize 1.初始化 Status list_init(SqList &L) { L.elem...
收起
数据结构
顺序表的删除操作ListDelete
千次阅读 2020-03-22 14:25:08
顺序表的插入操作思路插入的两种情况代码思路 1.获取表长 ... /*初始条件： 顺序表L已存在，1<=i<=ListLength(L) */ /*操作结果：在L党的第i个位置之前插入新的数据元素e，L的长度+1 */ Status ...
收起
数据结构
C++中如何建立一个顺序表
万次阅读 多人点赞 2013-09-25 00:09:39
#define MAXLEN 100 //定义顺序表的最大长度 struct DATA { char key[10]; //结点的关键字 char name[20]; int age; }; struct SLType //定义顺序表结构 { DATA ListData[MAXLEN+1];//保存顺序表的结构数组 ...
收起
C++ 数据结构
数据结构>顺序表
千次阅读 2015-01-24 22:49:42
一，顺序表的基本概念： 1． 顺序表的定义 (1) 顺序存储方法　即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。...　用顺序存储方法存储的线性表简称为顺序表（Sequential List）。
收起
C++
C/C++常用算法【C语言顺序查找（顺序表）】【2】
千次阅读 2015-12-11 18:21:46
直接上代码，代码中有详细注释，请自己领悟#...#include <stdlib.h>#define MAXLEN 100 //定义顺序表的最大长度typedef struct { char key[10]; //结点的关键字 char name[20]; int age; } DATA; //定义结点类型ty
收起
c语言
对顺序表中元素从小到大排序的算法
千次阅读 2017-12-29 22:37:21
）编写一个对顺序表中元素从小到大排序的算法，函数接口如下： //初始条件：线性表L已经存在，且元素个数大于1 //操作结果：将L中的元素从小到大排序 Status ListSort_Sq(SqList &L); 然后，在main函数中调用...
收起
线性表结构一——顺序表初始化，插入，删除，查找。typedef 解释，链表知识点总结
千次阅读 多人点赞 2019-04-15 18:15:58
一、顺序表定义及特点 1.顺序表定义 2.顺序表特点二、顺序表定义三、顺序表插入运算四、顺序表删除运算五、顺序表元素查找六、顺序表取元素数据七、主函数定义注1. typedef 解释注2. 链表知识点...
收起
【数据结构严蔚敏版】 顺序表基本操作
千次阅读 2018-12-22 21:41:43
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素...
收起
C++ 数据结构
【数据结构】线性表（顺序表、单链表、双链表、循环链表）的JAVA代码实现
千次阅读 2018-03-14 19:53:32
它的实现方式有很多，下面用顺序表、单链表、双链表、循环链表来对它进行实现。线性表的抽象数据类型数据元素：可以为任意类型，只要同属于一种数据类型即可；数据关系：数据元素之间呈线性关系；数据...
收起
数据结构 Java 链表
顺序表中静态顺序表的创建、插入和删除一个元素(源码分析)
千次阅读 2014-07-10 08:27:03
在数据结构的开始，首要讲的是顺序表，顺序表分为静态
收起
c语言算法数据结构
【数据结构基础笔记】第二章线性表之顺序表
千次阅读 多人点赞 2018-08-03 18:47:57
第二章一共四小节，第二节讲的是顺序表的相关概念及实现，顺序表是线性表的顺序存储结构，是后续顺序存储的基础。在本节代码中，我会加上我大量的个人代码理解，包括我思考的一些问题和我自己得到的答案（问题加粗并...
收起
线性表顺序表相关习题及详解 ——数据结构
千次阅读 2017-10-11 15:57:07
重新系统的过一遍数据结构现在先回顾下它的定义#define MaxSize 50 //定义线性表的最大长度 typedef struct{ ElemType data[MaxSize]; //顺序表的元素 int length; //顺序表的当前长度 }SqList; //
收起
数据结构 C语言
Java实现顺序表及常见操作
千次阅读 2017-05-11 20:46:43
//顺序表类，实现ADT List声明的方法，T表示数据元素的数据类型 public class SeqList extends Object{ //对象数组存储顺序表的数据元素，protected声明 ... //构造容量为length的空表 public SeqL
收起
Java 数据结构
顺序表查找——顺序查找、折半查找（多种方法）
千次阅读 2020-06-26 00:03:13
查找8.2 顺序表8.2.1 顺序表的查找基本思想顺序存储结构下的顺序查找算法平均查找长度8.2.2 有序表的折半查找折半查找的算法思想折半查找算法一般代码二叉搜索树 8.2 顺序表 采用顺序存储结构的数据表称为顺序表。...
收起
数据结构
数据结构顺序表和链表的实现原理
千次阅读 2018-07-07 16:38:32
java数据结构与算法之顺序表与链表深入分析2016年11月05日 16:24:30阅读数：14829 转载请注明出处（万分感谢！）： http://blog.csdn.net/javazejian/article/details/52953190 出自【zejian的博客】关联文章:java...
收起
C语言数据结构顺序表的查找算法
千次阅读 2019-06-04 11:58:46
*顺序表的查找算法（重点是哨兵的设置） *创建一个数据结构体 *创建一个顺序表的结构体 *顺序表结构体里面包含数据数组和数组长度 *采用两种查找方法哨兵设置普通查找 *哨兵排序算法的设置的好处是可以降低时间...
收起
c语言数据结构
数据结构第二章线性表顺序表练习题及答案P19
千次阅读 2020-10-16 18:29:05
空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行算法思想：搜索整个顺序表，查找最小值元素并记住其位置，搜索结束后用最后一个元素填补空出的原最小值元素的位置 bool Del_Min(SeqList &...
收起
数据结构算法 c语言
MySql当查询条件为空时不作为条件查询
万次阅读 多人点赞 2018-08-16 11:55:38
这种情况下，需要去判断每个条件是不是为空，后来发现一个很有用的sql语句，能非常简单的解决这个问题。我们先上表： CREATE TABLE `clazz` ( `id` INT(11) NOT NULL AUTO_INCREMENT CO...
收起
多条件查询 Mysql
判断DATASET是否为空
千次阅读 2012-07-04 17:41:09
1，if(ds == null) 这是判断内存中的数据集是否为空，说明DATASET为空，行和列都不存在!! 　2，if(ds.Tables[0].Count == 0) 这应该是在内存中存在一个DATASET，但是，数据集中不存在表!! 　3，if(ds.Tables[0...
收起
dataset null table
数据结构与算法实验一：顺序表的建立及操作
千次阅读 2020-07-15 21:45:36
数据结构与算法实验一：顺序表的建立及操作 顺序表指用一组地址连续的存储单元依次存储线性表的数据元素，其特点是，逻辑上...判断插入位置i 是否合法、顺序表的存储空间是否已满；将第n至第i位的元素依次向后移一个位
收起
数据结构 c语言

顺序表判断表满的条件

java数据结构与算法之顺序表与链表深入分析

1.线性表抽象数据类型概述

2.线性表的顺序存储设计与实现（顺序表）

2.1 顺序存储结构的设计原理概要

2.2 顺序存储结构的实现分析

2.3 顺序存储结构的效率分析

3.线性表的链式存储设计与实现（链表）

3.1 链表的链式存储结构设计原理概要

3.2 单链表的储结构实现分析

3.3 带头结点的单链表以及循环单链表的实现

带头结点的单链表

循环单链表

3.4 单链表的效率分析

数据结构顺序表基本操作（C/C++实现）

数据结构顺序表基本操作（C/C++实现）

涉及基本运算

GitHub地址（包含.cpp文件和可执行程序exe）

源代码（经VS2015、devC++编译器运行通过）

顺序表的实现

顺序表和链表实现图书管理系统

顺序表和链表实现图书管理系统

文章目录

1、代码实现

顺序表代码实现

链表代码实现

2、运行效果

3、实验总结

顺序表（笔记）

顺序表插入数据

Java 实现顺序表的基本操作

顺序表的基本操作：初始化，创建新表，删除元素，插入元素，定位元素，打印顺序表，返回长度

PTA 6-2顺序表操作集

数据结构c语言版严蔚敏 顺序表

顺序表的删除操作ListDelete

C++中如何建立一个顺序表

数据结构>顺序表

C/C++常用算法【C语言顺序查找（顺序表）】【2】

对顺序表中元素从小到大排序的算法

线性表结构一——顺序表初始化，插入，删除，查找。typedef 解释，链表知识点总结

【数据结构 严蔚敏版】 顺序表基本操作

【数据结构】线性表（顺序表、单链表、双链表、循环链表）的JAVA代码实现

顺序表中静态顺序表的创建、插入和删除一个元素(源码分析)

【数据结构基础笔记】第二章线性表之顺序表

线性表顺序表相关习题及详解 ——数据结构

Java实现顺序表及常见操作

顺序表查找——顺序查找、折半查找（多种方法）

数据结构顺序表和链表的实现原理

C语言数据结构顺序表的查找算法

数据结构第二章线性表顺序表练习题及答案P19

MySql当查询条件为空时不作为条件查询

判断DATASET是否为空

数据结构与算法实验一：顺序表的建立及操作

判断顺序表为空的条件

数据结构c语言版严蔚敏顺序表

【数据结构严蔚敏版】顺序表基本操作