【重学数据结构篇2 上】线性表之基础知识

今天药忘吃喽~ 2022-10-12 05:52 98阅读 0赞

## **一、本次学习内容** ##

***PPT学习部分***

1.  线性表
2.  顺序表
3.  单链表
4.  循环链表
5.  双向链表
6.  多项式

***课本补充部分***

***整体思维导图***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70]

## 二、PPT学习 ##

（1）线性表的基本概念

1.  线性表的定义

> 定义：n个数据元素的`有限序列`；原则上讲，线性表中表元素的数据类型可以不相同。但采用的存储表示可能会对其有限制；数组为广义的线性表。

1.  特点

> 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。  
> 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。  
> 直接前驱和直接后继描述了结点之间的`逻辑关系`（即邻接关系）  
> 注意：  
> 线性表、有序表、 ：表达的逻辑结构（线性结构）；  
> 顺序表、链表：表达的物理结构（存储结构）；

（2）线性表的基本实现

学习数据结构，首先需要明白该数据结构的作用（如何从实际问题抽象过来的（最为重要的能力）），然后明白怎么使用（基本的操作），最后 灵活应用解决实际问题。

面向对象编程，对于一个类主要分为两部分，即`成员变量`(属性)和`操作`（属性），而关于信息屏蔽和模块化这些属于类的管理协作，复杂项目去考虑，此处只需考虑单一的函数实现以及类实现。

1.  CPP版

template <class T, class E>
    class LinearList { 
    public:
        LinearList();				//构造函数
       ～LinearList();			//析构函数
        virtual int Size() const = 0;	//求表最大体积
        virtual int Length() const = 0;	//求表长度
        virtual int Search(T x) const = 0;         //搜索
        virtual int Locate(int i) const = 0;        //定位
        virtual E* getData(int i) const = 0;       //取值
        virtual void setData(int i, E x) = 0;       //赋值 
      virtual bool Insert(int i, E x) = 0;                //插入
        virtual bool Remove(int i, E& x) = 0;	  //删除
        virtual bool IsEmpty() const = 0;	            //判表空 
        virtual bool IsFull() const = 0;		  //判表满
        virtual void Sort() = 0；			  //排序
        virtual void input() = 0；			  //输入
        virtual void output() = 0；			  //输出
        virtual LinearList<T, E>operator= 
    			(LinearList<T, E>& L) = 0;	  //复制
    };

1.  Java版

public interface  LinearList { 
        // 线性表接口,类属性应有size、length
        //-----基本属性类方法---
        int size();// 线性的最大容量
        int length();// 线性表的长度,
        boolean isEmpty();
        boolean isFull();
        <E> E getData(int i);// 取值
        <E> void setData(int i,E e);//赋值
    
        
        //------查询类方法-----
        <E> int search(E e);// 搜索某个值的位置
        int locate(int i);// 定位i的取值？？
     
        
        //------增删改查更-----
        <E> void insert(int i,E e);//在i插入
        void delete(int i);//删除位子i的值
        <E> void update(int i,E e);//更新i位子的值,对应setData
        void sort();//排序
    
        <E> void add(E e);//末尾添加,线性表特性 首尾
        void outPut();
        
        void copy(LinearList list);//赋值
    }

Java List源码

public interface List<E> extends Collection<E> { 
               int size();
               boolean isEmpty();
               boolean contains(Object o);
               Iterator<E> iterator();
               Object[] toArray();
                boolean add(E e);
                boolean remove(Object o);
                   E set(int index, E element);
                 E get(int index);
               default void sort(Comparator<? super E> c) { 
            Object[] a = this.toArray();
            Arrays.sort(a, (Comparator) c);
            ListIterator<E> i = this.listIterator();
            for (Object e : a) { 
                i.next();
                i.set((E) e);
            }
        }
          int hashCode();
        
                ......
    }

（3）顺序表

1.  定义

> 定义： `顺序存储`的 n（  0）个表项的`有限序列`（a1, a2, …, an）  
> ai是表项，n是表长度

1.  特点

> 特点：所有元素的逻辑先后顺序与其物理存放顺序一致;  
> 优点：存储利用率高，存取速度快。

1.  实现

#define maxSize 100
    typedef int T;
    typedef struct { 
        T data[maxSize];     //顺序表的静态存储表示
        int n;
    } SeqList;
    
    typedef int T;
    typedef struct { 
        T *data;             //顺序表的动态存储表示
        int maxSize, n;
    } SeqList;

关于动态存储和静态存储（分配）、物理存储和顺序存储注意区分。

Java版

> 由于Java引入JVM，帮助程序员去管理内存分配，无需考虑内存回收等问题，因此Java一般来说无法自行进行动态内存分配，当new对象时，JVM将会帮你去管理内存分配。因此，只能在构造函数时，默认生成一个`指定大小的size`分配数组（实在想动态，那只能 引用（即链表方式），或者使用）。Java 的ArrayList实现如下；

首先，默认分配最大容量为10；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70 1]  
然后，当需要进行扩容时，使用grow进行扩容。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70 2]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70 3]  
最后，为其`分配新的对象`，但实质上还是JVM在为其管理内存释放等问题。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70 4]

顺序表的主要方法（操作）：

1.  size()，length()
2.  isEmpty()，isFull()
3.  getData(),setData()
4.  insert(),remove(),search(),sort(),isIn()
5.  next(),prior()

几个关键算法实现

/* 主要思想： （1）检查插入操作要求的有关参数的合理性； （2）将顺序表最后位置加1 （3）将第i至第n-1个表项依次往后移动一个位置； （4）把新的表项插入在顺序表的第i个位置 时间复杂度分析 最好： 0 最坏： n 平均： n/2 O(n) */
        @Override
        public <E> int insert(int i, E e) { 
              // 插入,-1非法插入，0 插入失败 1插入成功
            if(i<0||i>length){ 
                return -1;// 非法插入
                //exit(0);
            }
            length++;//插入之后,长度加一
            if(length>size){ 
                grow();//此处要么处理为动态扩容或者处理为不合法
            }
            for(int k=length-1;k>i;k--){ //注意数组与长度指标对应
                elements[k]=elements[k-1];
            }
            elements[i]=e;
            return 1;
        }
    
        public boolean grow(){ 
            System.out.println(System.currentTimeMillis()+"进行扩容...");
            size +=10;//扩容十个
            elements=Arrays.copyOf(elements,size);
            return true;
        }
    
    
     /* 主要思想： （1）从表的第一个数据元素起，依次和x进行比较， 若存在某个表项的值和x相等，则查找成功，并返回该表项的位置。 （2）如果查遍整个顺序表，都没有找到其值和x相等的表项，则查找不 成功，并返回-1。 时间复杂度分析 最好： 1 最坏： n 平均： (n+1)/2 O(n) */
        @Override
        public <E> int search(E e) { 
            int i=0;
            while(i<length&&elements[i++]!=e);//一直寻找直到匹配
    
            if(i>=length)
                return -1;
            else
                return i-1;
        }

（4）链表

> 链表是一种`物理存储单元上非连续、非顺序`的存储结构，数据元素的`逻辑顺序`是通过链表中的`指针`（Java中通过引用进行实现）链接次序实现的。

> 特点：特点  
> 每个元素(表项)由结点(Node)构成。  
> 线性结构  
> 结点可以不连续存储  
> 表可扩充

四种定义实现方式

class List;	                    //复合方式
     class ListNode { 	        //链表结点类 
     friend class List;	        //链表类为其友元类
     private:
         int data;		        //结点数据, 整型 
         ListNode * link;            //结点指针 
     };
     class List { 	                    //链表类 
     private:
         ListNode *first ;            //表头指针
     };
    
    
    class List {                         //嵌套方式
    private:
        class ListNode {            //嵌套链表结点类
        public:
            int data;			
            ListNode *link;		
        };
        ListNode *first;    	     //表头指针
    public:
        //链表操作………
    };
    
    
    //链表类和链表结点类定义(继承方式)
     class ListNode { 	    //链表结点类 
     protected:
         int data;		       
         ListNode * link;          	
     };
     class List : public class ListNode { 
     //链表类, 继承链表结点类的数据和操作 
     private:
         ListNode *first;         //表头指针
    };
    
    
    //链表类和链表结点类定义(结构方式)
     struct ListNode { 	       //链表结点类 
         int data;		       
         ListNode * link;          	
     };
     class List { 
     //链表类, 直接使用链表结点类的数据和操作
     private:
         ListNode *first;          //表头指针
     };    
    //链表中的结点属于链表私有，别人无法访问

1.  插入算法  
    a.第一个结点之前插入

newnode→link = first ;  first = newnode；

b.中间插入

newnode→link = current→link;// 先指向后结点
     current→link = newnode；

c.在链表末尾插入

newnode→link = current→link;(NULL)
    current→link = newnode；

1.  删除算法

a. 删除第一个元素

del = first；
    first = first→link; 
    delete del；

b.删除表中或表尾

del= current→link; current→link = del→link; delete del；

1.  其他算法  
    a.定位算法

template <class T, class E>
    LinkNode<T, E> *List<T, E>::Locate ( int i ) { 
    //函数返回表中第 i 个元素的地址。若i < 0或 i 超
    //出表中结点个数，则返回NULL。
    	 if (i < 0) return NULL;		//i不合理
    	 LinkNode<T, E> *current = first;  int k = 0;
    	 while ( current != NULL && k < i )
            {  current = current->link;	k++; }
         return current;	    //返回第 i 号结点地址或NULL
    };

b.创建链表（头插和尾插）

（5）循环链表

> 循环链表的特点：是单链表的变形。  
> 循环链表最后一个结点的 `link 指针不 为 0 (NULL)`，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。  
> 只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。（为方便设立了头指针和尾指针）

template <class T, class E>      //链表类定义
    class CircList : public LinearList<T, E> { 
    private: 
    	CircLinkNode<T, E> *first, *last;  //头指针, 尾指针
    public: 
    	CircList(const E x);		         //构造函数
    	CircList(CircList<T, E>& L);        //复制构造函数
    	～CircList();			         //析构函数
        int Length() const;		         //计算链表长度
    	bool IsEmpty() {  return first->link == first; }
                                                                //判表空否
    	CircLinkNode<T, E> *getHead() const;
    		                                           //返回表头结点地址

链表的应用：约瑟夫问题（循环链表）和多项式（静态数组、动态数组、结构体都可）

## 三、回顾总结 ##

1.  关于物理结构（存储结构）和逻辑结构、动态分配（存储）和静态分配（存储）、顺序存储和链式存储的总结？  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70 5]
2.  顺序存储和链式存储的各自特点？

顺序存储：随机访问，删减不方便；链式存储：删减方便，但不方便随机访问；（注意随机访问特性是指查找的特性，区别动态性）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70]: /images/20221005/95aaffb710f7401dad7050339cc93a2a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70 1]: /images/20221005/0a20f0da9e8f443984aea163c679a303.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210704145604947.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70 3]: /images/20221005/44c7107c13854aa7b5327138d7c0d1a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70 4]: /images/20221005/02202d9c23854729ac210cfa8ca132db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70 5]: /images/20221005/4fe9814cccf4492591b30ddc8943ddea.png