数据结构（二）-线性表

发表于 | 分类于 ，

1. 概述

  • 线性结构的特点
    • 存在惟一的一个被称作“第一个”的数据元素
    • 存在惟一的一个被称作“最后一个”的数据元素
    • 除第一个之外，集合中每个数据元素均只有一个前驱
    • 除最后一个之外，集合中每个数据元素均只有一个后继

2. 线性表的类型定义

  • 线性表
    • 是$n$个数据元素的有限序列
  • 复杂的线性表
    • 一个元素可以由若干个数据项(item)组成，数据元素称为记录(record)，含有大量记录的线性表又称文件(file)
    • 同一线性表中的元素必定具有相同属性，即属同一数据对象
  • 数组
    • 线性表的顺序存储结构，即一段连续的内存空间存储的数据元素
  • 线性链表
    • 用一组任意的存储单元存储线性表的数据元素，由结点构成
    • 一个结点不仅存储数据元素，也需要存储后继结点指针
    • 只包含一个指针域的线性链表称为单链表
    • 包含前后指针域的线性链表称为双向线性链表
  • 循环链表
    • 表中最后一个结点的指针域指向头结点，整个链表形成一个环

3. 单向链表实现

  • 创建链表
  • 插入数据
  • 在指定数据点后插入数据
  • 更新指定数据点的数据
  • 删除指定数据的结点
  • 链表反转
  • 打印
  • 清空链表

代码：

  • List.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#ifndef DATA_STRUCTURE_LIST_H
#define DATA_STRUCTURE_LIST_H

#include <iostream>

class List {

public:
    List();
    ~List();

    int Insert(const int data);
    int InsertPos(const int data, const int dataInsert);
    void Update(const int data, const int dataUpdate);
    void Erase(const int data);
    void Reverse();
    
    void Clear();
    void Print();

private:
    struct Node{
        int data;
        Node * next;
        Node(const int& d):data(d),next(NULL) {}
    };

    Node *head;

    Node* Find(const int data);
};

#endif //DATA_STRUCTURE_LIST_H
  • List.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

#include "List.h"

List::List() {
    head = new Node(0);
}

List::~List() {
    if (NULL != head) {
        head = NULL;
    }
}

int List::Insert(const int data) {
    Node * p = new Node(data);
    p->next = head->next;
    head->next = p;
    return 0;
}

int List::InsertPos(const int data, const int dataInsert) {
    Node* p = Find(data);
    Node* q = new Node(dataInsert);
    q->next = p->next;
    p->next = q;
    return 0;
}

void List::Update(const int data, const int dataUpdate) {
    Node* p = Find(data);
    p->next->data = dataUpdate;
}

void List::Erase(const int data) {
    Node *p = Find(data);
    if (NULL == p->next->next) {
        delete p;
    } else {
        Node* q = p->next;
        p->next = p->next->next;
        delete q;
    }
}

void List::Reverse() {
    if (NULL == head->next) {
        return;
    }
    Node* p = head->next;
    Node* q = head->next->next;
    Node* m = head->next->next->next;
    p->next = NULL;
    while (m) {
        q->next = p;
        p = q;
        q = m;
        m = m->next;
    }
    q->next = p;
    head->next = q;
}

void List::Clear() {
    Node *p = head;
    while (p) {
        Node *q = p->next;
        delete p;
        p = q;
    }
}

void List::Print() {
    if (NULL == head) {
        printf("List is clear\n");
        return;
    }
    Node *p = head->next;
    while (p) {
        printf("%d\n", p->data);
        p = p->next;
    }
}

List::Node* List::Find(const int data) {
    for (Node *p = head; p; p = p->next) {
        if (p->next->data == data) {
            return p;
        }
    }
    return head;
}

4. 双向链表实现

  • 创建链表
  • 插入数据
  • 在指定数据点后插入数据
  • 更新指定数据点的数据
  • 删除指定数据的结点
  • 打印
  • 清空链表

代码：

  • DoubleLinkedList.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#ifndef DoubleLinkedList_hpp
#define DoubleLinkedList_hpp

#include <stdio.h>

class DoubleLinkedList {
public:
    DoubleLinkedList();
    ~DoubleLinkedList();
    
    void CreateLinedList(int n);
    void Insert(int position, int data);
    void Remove(int position);
    
    int GetLength();
    void Print();
    
private:
    struct Node {
        int data;
        Node *pNext, *pPre;
        Node(const int& data):data(data), pNext(NULL), pPre(NULL) {}
    };
    
    Node* head;
    
};

#endif /* DoubleLinkedList_hpp */
  • DoubleLinkedList.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include "DoubleLinkedList.hpp"

DoubleLinkedList::DoubleLinkedList() {
    head = new Node(0);
}

DoubleLinkedList::~DoubleLinkedList() {
    if (NULL != head) {
        delete head;
    }
}

void DoubleLinkedList::CreateLinedList(int n) {
    if (n < 0) {
        return;
    }
    Node *p, *q;
    p = head;
    for (int i = 0; i < n; i ++) {
        q = new Node(0);
        q->pPre = p;
        p->pNext = q;
        p = q;
    }
}

void DoubleLinkedList::Insert(int position, int data) {
    if (position < 0 || position > GetLength() - 1) {
        return;
    }
    Node *p, *q;
    q = new Node(0);
    q->data = data;
    p = head->pNext;
    while (position -- > 1) {
        p = p->pNext;
    }
    if (NULL != p->pNext) {
        p->pNext->pPre = q;
    }
    q->pNext = p->pNext;
    q->pPre = p;
    p->pNext = q;
    p = q;
}

void DoubleLinkedList::Remove(int position) {
    if (position < 0 || position > GetLength() - 1) {
        return;
    }
    Node *p = head;
    Node *q;
    while (position -- > 1) {
        p = p->pNext;
    }
    q = p->pNext;
    if (NULL != q->pNext) {
        q->pNext->pPre = p;
    }
    p->pNext = q->pNext;
    delete q;
    q = NULL;
}

int DoubleLinkedList::GetLength() {
    int n = 0;
    Node *p = head->pNext;
    while (p) {
        n ++;
        p = p->pNext;
    }
    return n;
}

void DoubleLinkedList::Print() {
    Node *p = head->pNext;
    while (p) {
        printf("%d\n", p->data);
        p = p->pNext;
    }
}

5. 循环链表实现

  • 创建链表
  • 插入数据
  • 在指定数据点后插入数据
  • 更新指定数据点的数据
  • 删除指定数据的结点
  • 打印
  • 清空链表

代码：

  • CircularList.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#ifndef DATA_STRUCTURE_CIRCULARLIST_H
#define DATA_STRUCTURE_CIRCULARLIST_H

#include <iostream>

class Node {
public:
    int data;
    Node *pNext;
};

class CircularList {
public:
    CircularList();
    ~CircularList();

    void CreateList(int n);
    void TraverseLinkList();
    bool IsEmpty();
    int GetLength();
    void InsertNode(int position, int d);
    void DeleteNode(int position);
    void DeleteLinkList();

private:
    Node *head;

};

#endif //DATA_STRUCTURE_CIRCULARLIST_H
  • CircularList.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include "CircularList.h"

CircularList::CircularList() {
    head = new Node;
    head->data = 0;
    head->pNext = head;
}

CircularList::~CircularList() {
    delete head;
}

void CircularList::CreateList(int n) {
    if (n < 0) {
        return;
    }
    Node *pnew, *ptemp = head;
    int i = n;
    while (n-- > 0) {
        pnew = new Node;
        pnew->data = n;
        pnew->pNext = head;
        ptemp->pNext = pnew;
        ptemp = pnew;
    }
}

void CircularList::TraverseLinkList() {
    Node *ptemp = head->pNext;
    while (ptemp != head) {
        std::cout << ptemp->data << " ";
        ptemp = ptemp->pNext;
    }
    std::cout << std::endl;
}

bool CircularList::IsEmpty() {
    if (head->pNext == head) {
        return true;
    }
    return false;
}

int CircularList::GetLength() {
    int n = 0;
    Node *ptemp = head->pNext;
    while (ptemp != head) {
        n ++;
        ptemp = ptemp->pNext;
    }
    return n;
}

void CircularList::InsertNode(int position, int d) {
    if (position < 0 || position > GetLength() + 1) {
        return;
    }
    Node *pnew, *ptemp = head;
    pnew = new Node;
    pnew->data = d;
    while (position-- > 1) {
        ptemp = ptemp->pNext;
    }
    pnew->pNext = ptemp->pNext;
    ptemp->pNext = pnew;
}

void CircularList::DeleteNode(int position) {
    if (position < 0 || position > GetLength()) {
        return;
    }
    Node *ptemp = head, *pdelete;
    while (position-- > 1) {
        ptemp = ptemp->pNext;
    }
    pdelete = ptemp->pNext;
    ptemp->pNext = pdelete->pNext;
    delete pdelete;
    pdelete = NULL;
}

void CircularList::DeleteLinkList() {
    Node *pdelete = head->pNext, *ptemp;
    while (pdelete != head) {
        ptemp = pdelete->pNext;
        head->pNext = ptemp;
        delete pdelete;
        pdelete = ptemp;
    }
}

6. 编程题

6.1 查找单链表中的倒数第k个结点

  • 这里需要声明两个指针：即两个结点型的变量first和second，首先让first和second都指向第一个结点，然后让second结点前移k-1个位置，此时first和second就间隔了k-1个位置，然后整体向前移动这两个节点，直到second节点走到最后一个结点的时候，此时first节点所指向的位置就是倒数第k个节点的位置
  • 时间复杂度为O（n）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Node* FindNode(int k) {
    if (k < 0 || k > GetLength()) {
        return NULL;
    }
    Node *q = head;
    Node *p = head;
    for (int i = 0; i < k - 1; i ++) {
        p = p->next;
    }
    while (p != NULL) {
        p = p->next;
        q = q->next;
    }
    
    return q;
}

6.2 查找单链表中的中间结点

  • 不允许你算出链表的长度
  • 设置两个指针first和second，只不过这里是，两个指针同时向前走，second指针每次走两步，first指针每次走一步，直到second指针走到最后一个结点时，此时first指针所指的结点就是中间结点

代码：

1
2
3
4
5
6
7
8
9
10
11
12
Node* FindNode() {
    if (NULL == head || NULL == head->next || NULL == head->next->next) {
        return NULL;
    }
    Node *p = head;
    Node *q = head;
    while (p->next != NULL && p->next->next != NULL) {
        p = p->next->next;
        q = q->next;
    }
    return q;
}

6.3 合并两个有序单向链表

  • 已知两个链表 head1 和 head2 各自有序，请把它们合并成一个链表依然有序。结果链表要包含 head1 和head2 的所有节点，即使节点值相同

  • 不能开辟新空间来存储合并后的链表。如果第一次做该题，很容易会想到使用新链表来存储合并后的有序链表。虽然可以如此实现，但是不符合常规解法和面试官的要求

  • 非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Node* MergeList(Node *head_1, Node *head_2) {
    Node *p = NULL;
    if (NULL == head_1) {
        return head_2;
    }
    if (NULL == head_2) {
        return head_1;
    }
    if (head_1->data < head_2->data) {
        p = head_1;
        head_1 = head_1->next;
    } else {
        p = head_2;
        head_2 = head_2->next;
    }
    while (head_1 && head_2) {
        if (head_1->data < head_2->data) {
            p->next = head_1;
            head_1 = head_1->next;
        } else {
            p->next = head_2;
            head_2 = head_2->next;
        }
        p = p->next;
    }
    if (head_1) {
        p->next = head_1;
    }
    if (head_2) {
        p->next = head_2;
    }
    return p;
}
  • 递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Node* MergeList(Node *head_1, Node *head_2) {
    Node *p = NULL;
    if (NULL == head_1) {
        return head_2;
    }
    if (NULL == head_2) {
        return head_1;
    }
    if (head_1->data < head_2->data) {
        p = head_1;
        p->next = MergeList(head_1->next, head_2);
    } else {
        p = head_2;
        p->next = MergeList(head_1, head_2->next);
    }
    return p;
}

6.4 单链表的反转

  • 不使用额外的空间
  • 思路：从头到尾遍历原链表，每遍历一个结点，将其摘下放在新链表的最前端。
    注意链表为空和只有一个结点的情况。时间复杂度为O（n）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node* ReverseList(Node *head) {
    if (NULL == head || NULL == head->next) {
        return head;
    }
    Node *p = NULL;
    Node *q = head;
    while (NULL != q) {
        Node *m = q->next;
        q->next = p;
        p = q;
        q = m;
    }
    return p;
}

6.5 从尾到头打印单链表

  • 递归实现：用递归实现，但有个问题：当链表很长的时候，就会导致方法调用的层级很深，有可能造成栈溢出。
1
2
3
4
5
6
7
8
Node* ReversePrint(Node *head) {
    if (NULL == head) {
        return NULL;
    }
    ReversePrint(head->next);
    printf("%d\n", head->data);
    return NULL;
}

6.6 判断单链表是否有环

  • 这里也是用到两个指针，如果一个链表有环，那么用一个指针去遍历，是永远走不到头的。因此，我们用两个指针去遍历：first指针每次走一步，second指针每次走两步，如果first指针和second指针相遇，说明有环。
    时间复杂度为O (n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool IsCycle(Node *head) {
    if (NULL == head) {
        return false;
    }
    Node *p = head;
    Node *q = head;
    while (q != NULL && q->next != NULL) {
        p = p->next;
        q = q->next->next;
        if (p == q) {
            return true;
        }
    }
    return false;
}

6.7 取出有环链表中环的长度

  • 思路：环的长度即为从开始到相遇处first走的步数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int GetCycleLength(Node *head) {
    if (NULL == head || NULL == head->next) {
        return 0;
    }
    int length = 0;
    Node *p = head;
    Node *q = head;
    while (q != NULL && q->next != NULL) {
        p = p->next;
        q = q->next->next;
        length ++;
        if (p == q) {
            return length;
        }
    }
    return 0;
}

6.8 有环单链表中，取出环的起始点

  • 思路：从相遇点开始，设置一个节点从头开始，然后最终相遇的节点就是环的起始点。由a=c可知。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Node* GetCycleLength(Node *head) {
    if (NULL == head || NULL == head->next) {
        return NULL;
    }
    Node *p = head;
    Node *q = head;
    while (q != NULL && q->next != NULL) {
        p = p->next;
        q = q->next->next;
        if (p == q) {
            Node* m = head;
            while (m != q) {
                m = m->next;
                q = q->next;
            }
            return q;
        }
    }
    return NULL;
}