数据结构线性表之吐血攻略

缺乏、安全感 2022-05-09 17:10 202阅读 0赞

这是一篇闲狗写给闲狗看的线性表攻略。

![70][]

# 1 线性表 #

## 1.1 线性表的概述 ##

**线性表**简称表，是零个或多个元素的有穷序列

![70 1][]

# ![70 2][] #

## 1.2 线性表类模板 ##

### C++版 ###

template <class T> class List {
      void clear(); // 置空线性表
    
      bool isEmpty(); // 线性表为空时，返回 true
    
      //在表尾添加一个元素 value，表的长度增 1
      bool append(const T value); 
     
      //在位置 p 上插入一个元素 value，表的长度增 1
      bool insert(const int p, const T value);
      
      //删除位置 p 上的元素，表的长度减 1
      bool delete(const int p);
      
      //查找值为 value 的元素并返回其位置
      bool getPos(int& p, const T value);
      
      //把位置 p 元素值返回到变量 value
      bool getValue(const int p, T& value);
    
      //用 value 修改位置 p 的元素值
      bool setValue(const int p, const T value);
    }

### Java版 ###

public interface Collection<E> extends Iterable<E> {
    
        int size();
    
        boolean isEmpty();
       
        boolean contains(Object o);
      
        Iterator<E> iterator();
       
        Object[] toArray();
       
        boolean add(E e);
       
        boolean remove(Object o);
     
        boolean containsAll(Collection<?> c);
       
        void clear();
    
        boolean equals(Object o);
       
        int hashCode();
        ...
    }

# 2 链表（Linked List） #

**链表：**一种物理存储单元上非连续、非顺序的存储结构。通过指针把一串存储结点链接成一个链。

**存储结点**一般由两部分组成：数据域+指针域（后继地址）

![70 3][]

## 2.1 单链表（Singly Linked List） ##

### 2.1.1 不带头结点的单链表 ###

### ![70 4][] ###

### 2.1.2 带头结点的单链表 ###

![70 5][]

### 2.1.3 单链表的结点类型 ###

template <class T> class Link {
         public:
         T data; // 用于保存结点元素的内容
         Link<T> * next; // 指向后继结点的指针
    
         Link(const T info, const Link<T>* nextValue =NULL) {
             data = info;
             next = nextValue;
         }
    
         //创建头结点
         Link(const Link<T>* nextValue) {
             next = nextValue;
         }
    };

类似于Java定义一个对象类，Java集合为线性结构，存放着对象

### 2.1.4 单链表类定义 ###

template <class T> class lnkList : public List<T> {
        private:
        Link<T> * head,
        *tail; // 单链表的头、尾指针
        Link<T> *setPos(const int p); // 第p个元素指针
    
        public:
        lnkList(int s); // 构造函数
        ~lnkList(); // 析构函数
        bool isEmpty(); // 判断链表是否为空
        void clear(); // 将链表存储的内容清除，成为空表
        int length(); // 返回此顺序表的当前实际长度
        bool append(cosnt T value); // 表尾添加一个元素 value，表长度增 1
        bool insert(cosnt int p, cosnt T value); // 位置 p 上插入一个元素
        bool delete(cosnt int p); // 删除位置 p 上的元素，表的长度减 1
        bool getValue(cosnt int p, T& value); // 返回位置 p 的元素值
        bool getPos(int &p, const T value); // 查找值为 value 的元素
    }

类似于Java的LinkedList，相应的增删改查方法可以模仿LinkedList封装好的方法。

--------------------

### 2.1.5 插入结点 ###

### ![70 6][] ###

### 2.1.6 删除结点 ###

![70 7][]

### 2.1.7 单链表上运算的分析 ###

![70 8][]

## 2.2 双链表 ##

## ![70 9][] ##

### 2.2.1 双链表结点类型 ###

template <class T> class Link {
        public:
        T data; // 用于保存结点元素的内容
        Link<T> * next; // 指向后继结点的指针
        Link<T> *prev; // 指向前驱结点的指针
       
        // 给定值和前后指针的构造函数
        Link(const T info, Link<T>* preValue = NULL, Link<T>* nextValue = NULL) {
            data = info;
            next = nextValue;
            prev = preValue;
        }
    
        //给定前后指针的构造函数
        Link(Link<T>* preValue = NULL, Link<T>* nextValue = NULL) {
            next = nextValue;
            prev = preValue;
        }
    }

### 2.2.1 插入结点 ###

### ![70 10][] ###

经理p将一些设备分配给新来的员工q，

q再将自己的一些信息告诉经理p

--------------------

**1（华文课后题）**完成在双循环链表结点p之后插入s的操作为**AD**

A、p->next->prev=s; s->prev=p; s->next=p->next; p->next=s;  (4,2,1,3)

B、p->next->prev=s; **p->next**=s; s->prev=p; s->next=**p->next**;(4,3,2,1)

> 解析：造成原来的p结点后来的next信息丢失

C、s->prev=p; s->next=p->next; **p->next**=s; **p->next**\->prev=s;(2,1,3,4)

> 解析：先更改p->next成s再更改p->next->prev，会造成原来的p结点后来的next信息丢失

D、s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;(1,4,2,3)

--------------------

### 2.2.2 删除结点 ###

![70 11][]

--------------------

**1 （2016计算机联考真题）**

![70 12][]

--------------------

## 2.3 循环链表 ##

### 2.3.1 循环单链表 ###

**（1）带头结点的空链表**

![70 13][]

**（2）带头结点，头指针的非空链表**

![70 14][]

**（3）带头结点，尾指针的非空链表**

![70 15][]

![70 16][]

### 2.3.2 循环双链表 ###

![70 17][]

## 2.4 静态链表 ##

借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next。不同的是，这里的指针是结点的相对地址（数组下标），又称为游标。

![70 18][]

与顺序表一样，静态链表也要预先分配一块连续的内存空间。

--------------------

![70 19][]

本文参考自：

张铭《数据结构与算法》

程杰《大话数据结构》

陈越，何钦铭《数据结构》

[70]: /images/20220506/6d00f8844256463fa14987f7b3c86b6b.png
[70 1]: /images/20220506/654d60619a2c4abdba728de1b6b98956.png
[70 2]: /images/20220506/e1d27e75087146608d774c564fa9481f.png
[70 3]: /images/20220506/9efc4fe1b7a24fed8b1556f795dd323a.png
[70 4]: /images/20220506/446bdd37f99a4510bdc673a026c9477d.png
[70 5]: /images/20220506/692a789f400b429e83f4892ce46cdbc7.png
[70 6]: /images/20220506/4e955c473a7b4111a4f22d000ff9cd36.png
[70 7]: /images/20220506/868a098123064fc39e8f439dbe09bd95.png
[70 8]: /images/20220506/e820f3756c504ff2bd9da6dae65fead4.png
[70 9]: /images/20220506/3d2946e1dac24d0a8d05467162331ab7.png
[70 10]: /images/20220506/6a3083df307642f2a9f672ecde3df69c.png
[70 11]: /images/20220506/02db32438ee944d5bacd7e6394eff1f9.png
[70 12]: /images/20220506/e039db4b9dae4d84a58df2b4e5cce349.png
[70 13]: /images/20220506/fd44aa946611437dbef467dfd21e8be8.png
[70 14]: /images/20220506/6fc8490e0b00434f9b8503a08188ce72.png
[70 15]: /images/20220506/c73f755fc4ef4d9eaf798b1c24d616bf.png
[70 16]: /images/20220506/c80e7a4c738b4b2dbcc7020ae5ad552e.png
[70 17]: /images/20220506/41f09ff22d25445a83a074b77b42e90a.png
[70 18]: /images/20220506/68040f6918a44b97b3396e5f01f2165d.png
[70 19]: /images/20220506/bdacbdd9086d47caa163e71b1ccb9c2c.png