算法导论 单链表_单链表计算机导论

单链表

1. 单链表是什么？

单链表是一种常见的简单数据结构，链表由很多个结点组成，每个结点有储存数据的数据域和指向下一个结点的地址。因为每个结点都有下一个结点的地址，因此通过当前结点可以找到下一个结点，将各种数据就像链子一样连接起来。相比于数组，链表的优点就是大小可以改变，删除和插入数据也不必作太大的改动，缺点是不可以随机访问（必须通过一个结点访问下一个结点来访问你想访问的结点）。

2. 单链表的实现（C++）

//SinglyLink.h
#pragma once

#include <assert.h>
#include <stdio.h>

template<typename ElemType>
class Node
{
public:
    Node(Node<ElemType>* pNext = NULL, ElemType* pData = NULL);
    ElemType const& GetData() const;
    void SetData(ElemType val) ;
    Node<ElemType>* const& GetNext() const;
    void SetNext(Node<ElemType>* val);
private:
    ElemType* m_pData;
    Node<ElemType>* m_pNext;
};

template<typename ElemType>
class SinglyLinkList
{
public:
    SinglyLinkList();
    unsigned int const& GetLength() const;
    bool Insert(ElemType elem, unsigned int pos);
    bool Delete(unsigned int pos, ElemType* elem);
    bool Search(unsigned int pos, ElemType* elem) const;
    bool Visit(ElemType* elem, const unsigned int& pos) const;
    bool Empty();
private:
    Node<ElemType>* m_pHeadNode;
    unsigned int m_length;
};

//————————————————————————————————//Node类的实现
template<typename ElemType>
Node<ElemType>::Node(Node<ElemType>* pNext /*= NULL*/, ElemType* pData /*= NULL*/)
    :m_pNext(pNext),m_pData(pData)
{

}


template<typename ElemType>
void Node<ElemType>::SetNext(Node<ElemType>* val)
{
    m_pNext = val;
}

template<typename ElemType>
Node<ElemType>* const& Node<ElemType>::GetNext() const
{
    return m_pNext;
}

template<typename ElemType>
void Node<ElemType>::SetData(ElemType val)
{
    m_pData = val;
}

template<typename ElemType>
ElemType const& Node<ElemType>::GetData() const
{
    return *m_pData;
}

//————————————————————————————————//SinglyLink类实现

template<typename ElemType>
SinglyLinkList<ElemType>::SinglyLinkList()
    :m_pHeadNode(new Node<ElemType>()),m_length(0)
{

}


template<typename ElemType>
bool SinglyLinkList<ElemType>::Insert(ElemType elem, unsigned int pos)
{
    if (pos > GetLength() || pos < 0)
    {
        assert(false && "Error: SinglyLink's insert pos is out of range!\n");
        return false;
    }

    for(Node<ElemType>* pCurrentNode = m_pHeadNode; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext())
    {
        if (pos-- == 0)
        {
            Node<ElemType>* insertNode = new Node<ElemType>(pCurrentNode->GetNext(),new ElemType(elem));
            pCurrentNode->SetNext(insertNode);
            ++m_length;
            return true;
        }
    }
    assert(false && "Error: SinglyLink Insert failed for unknow reason!");
    return false;
}

template<typename ElemType>
bool SinglyLinkList<ElemType>::Delete(unsigned int pos, ElemType* elem)
{
    if (pos >= GetLength() || pos < 0)
    {
        assert(false && "Error: SinglyLink's delete pos is out of range!\n");
    }

    for(Node<ElemType>* pCurrentNode = m_pHeadNode; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext())
    {
        if (pos-- == 0)
        {
            Node<ElemType>* deleteNode = pCurrentNode->GetNext();
            pCurrentNode->SetNext(deleteNode->GetNext());
            *elem = deleteNode->GetData();
            delete deleteNode;
            --m_length;
            return true;
        }
    }
    assert(false && "Error: SinglyLink pos delete failed for unknow reason!");
    return false;
}

template<typename ElemType>
unsigned int const& SinglyLinkList<ElemType>::GetLength() const
{
    return m_length;
}

template<typename ElemType>
bool SinglyLinkList<ElemType>::Search(unsigned int pos, ElemType* elem) const
{
    if (pos >= GetLength() || pos < 0)
    {
        assert(false && "Error: SinglyLink's search pos is out of range!\n");
    }

    for(Node<ElemType>* pCurrentNode = m_pHeadNode; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext())
    {
        if (pos-- == 0 && (pCurrentNode->GetNext() != NULL) )
        {
            *elem = pCurrentNode->GetNext()->GetData();
            return true;
        }
    }

    return false;
}

template<typename ElemType>
bool SinglyLinkList<ElemType>::Visit(ElemType* elem, const unsigned int& pos) const
{
    if (pos >= GetLength() || pos < 0)
    {
        return false;
    }
    return Search(pos,elem);
}

template<typename ElemType>
bool SinglyLinkList<ElemType>::Empty()
{
    return !m_length;
}
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

//Util.h
#pragma once

namespace Util
{
    template<typename T>
    void PrintMemory(const T& dateStruct, unsigned int size)
    {
        cout << "PrintMemory: ";
        for (int i = 0; i != size; i++)
        {
            ElemType tempElem;
            if (!dateStruct.Visit(&tempElem,i))
            {
                printf("\n");
                return;
            }
            printf("%d ",tempElem);
        }
        printf("\n");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//main.cpp
#include "Util.h"
#include "SinglyLinkList.h"
#include <iostream>

using namespace std;

typedef int ElemType;

int main()
{
    SinglyLinkList<int> testSinglyLinkList;

    cout << "testSinglyLinkList is " << (testSinglyLinkList.Empty() ? "Empty." : "Not Empty.") << endl;
    Util::PrintMemory(testSinglyLinkList,testSinglyLinkList.GetLength());

    for (int i = 0; i != 5; i++)
    {
        testSinglyLinkList.Insert(i+1,i);
        cout << "\nInsert:" << i+1 << endl;
        cout << "testSinglyLinkList is " << (testSinglyLinkList.Empty() ? "Empty." : "Not Empty.") << endl;
        Util::PrintMemory(testSinglyLinkList,testSinglyLinkList.GetLength());
    }

    for (int i = 0; i != 2; i++)
    {
        ElemType tempElem;
        testSinglyLinkList.Delete(i,&tempElem);
        cout << "\nDelete:" << tempElem << endl;
        cout << "testSinglyLinkList is " << (testSinglyLinkList.Empty() ? "Empty." : "Not Empty.") << endl;
        Util::PrintMemory(testSinglyLinkList,testSinglyLinkList.GetLength());
    }

    return 0;
}



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

3. 程序运行结果

testSinglyLinkList is Empty.
PrintMemory:

Insert:1
testSinglyLinkList is Not Empty.
PrintMemory: 1

Insert:2
testSinglyLinkList is Not Empty.
PrintMemory: 1 2

Insert:3
testSinglyLinkList is Not Empty.
PrintMemory: 1 2 3

Insert:4
testSinglyLinkList is Not Empty.
PrintMemory: 1 2 3 4

Insert:5
testSinglyLinkList is Not Empty.
PrintMemory: 1 2 3 4 5

Delete:1
testSinglyLinkList is Not Empty.
PrintMemory: 2 3 4 5

Delete:3
testSinglyLinkList is Not Empty.
PrintMemory: 2 4 5