0%

php版链表的实现

1
<?php
2
class Node {
3
    private $data;
4
    private $next;
5
6
    public function getData() {
7
        return $this->data;
8
    }
9
10
    public function setData($data) {
11
        $this->data = $data;
12
        return true;
13
    }
14
15
    public function getNext() {
16
        return $this->next;
17
    }
18
19
    public function setNext($next) {
20
        $this->next = $next;
21
        return true;
22
    }
23
}
24
25
/**
26
 * 链表类
27
 */
28
class Link {
29
    private $size = 0;
30
    private $first;
31
    private $last;
32
33
    /**
34
     * 获取链表长度
35
     */
36
    public function getLength() {
37
        return $this->size;
38
    }
39
40
    /**
41
     * 链表中插入第一个元素的时候,头和尾部都是同一个元素
42
     */
43
    public function oneNode(string $element) {
44
        $this->first = new Node;
45
        $this->first->setData($element);
46
        $this->last = $this->first;
47
    }
48
49
    /**
50
     * 当只有一个元素的时候,删除$fist和$last
51
     */
52
    public function clear() {
53
        $this->first = $this->last = null;
54
    }
55
    
56
    /**
57
     * 头节点插入
58
     */
59
    public function addHead(string $element) {
60
        if ($this->size == 0) {
61
            $this->oneNode($element);
62
        } else {
63
            $node = new Node;
64
            $node->setData($element);
65
            $node->setNext($this->first);
66
            $this->first = $node;
67
        }
68
        $this->size++;
69
        return true;
70
    }
71
    
72
    /**
73
     * 尾节点插入
74
     */
75
    public function addTail(string $element) {
76
        if ($this->size == 0) {
77
            $this->oneNode($element);
78
        } else {
79
            $node = new Node();
80
            $node->setData($element);
81
            $this->last->setNext($node);
82
            $this->last = $node;
83
        }
84
85
        $this->size++;
86
    }
87
88
    /**
89
     * 中间节点插入
90
     */
91
    public function add(int $index, string $element) {
92
        if ($index <= $this->size) {
93
            if ($this->size == 0) {
94
                oneNode($element);
95
            } elseif ($index == 0) {
96
                $this->addHead($element);
97
            } elseif ($index == $this->size) {
98
                $this->addTail($element);
99
            } else {
100
                $tmp = $this->get($index - 1);
101
                $node = new Node;
102
                $node->setData($element);
103
                $node->setNext($tmp->getNext());
104
                $tmp->setNext($node);
105
            }
106
            $this->size++;
107
        } else {
108
            throw new \Exception("插入位置无效或超出链表长度");
109
        }
110
    }
111
    
112
    /**
113
     * 获取指定位置的元素
114
     */
115
    public function get(int $index) {
116
        $tmp = $this->first;
117
        for ($i = 0; $i < $index - 1; $i++) {
118
            $tmp = $tmp->getNext();
119
        }
120
        return $tmp;
121
    }
122
123
    /**
124
     * 删除头节点
125
     */
126
    public function deleteFirst() {
127
        if ($this->size == 0) {
128
            throw new \Exception("空链表,无元素可删除");
129
        } elseif ($this->size == 1) {
130
            $this->clear();
131
        } else {
132
            $tmp = $this->first;
133
            $this->first = $tmp->getNext();
134
            $this->size--;
135
        }
136
    }
137
138
    /**
139
     * 删除尾节点
140
     */
141
    public function deleteLast() {
142
        if ($this->size == 0) {
143
            throw new \Exception("空链表,无元素可删除");
144
        } elseif ($this->size == 1) {
145
            $this->clear();
146
        } else {
147
            $tmp = $this->get($this->size - 1);
148
            $tmp->setNext(null);
149
            $this->size--;
150
        }
151
    }
152
153
    /**
154
     * 删除指定节点
155
     */
156
    public function deleteIndex(int $index) {
157
        if ($this->size == 0) {
158
            throw new \Exception("空链表,无元素可删除");
159
        } elseif ($this->size == 1) {
160
            $this->clear();
161
        } else {
162
            $tmp = $this->get($index - 1);
163
            $tmp->setNext($tmp->getNext()->getNext());
164
            $this->size--;
165
        }
166
    }
167
    
168
    /**
169
     * 反转节点
170
     */
171
    public function receve() {
172
        if ($this->size < 2) {
173
            return true;
174
        } else {
175
            $tmp = $this->first;
176
            $last = $tmp;
177
            $next = $this->first->getNext();
178
            for($i = 0; $i < $this->size - 1; $i++) {
179
                $nextNext = $next->getNext();
180
                $next->setNext($tmp);
181
                $tmp = $next;
182
                $next = $nextNext;
183
            }
184
            $last->setNext(null);
185
            $this->first = $tmp;
186
            return true;
187
        }
188
    }
189
190
    /**
191
     * 打印现有的所有元素
192
     */
193
    public function printLink() {
194
        $tmp = $this->first;
195
        if(is_null($tmp)) {
196
            return false;
197
        } 
198
        echo $tmp->getData();
199
        while(!is_null($tmp->getNext())) {
200
            $tmp = $tmp->getNext();
201
            echo "->" . $tmp->getData();
202
        }
203
        echo "\n";
204
    }
205
}
206
207
$link = new Link();
208
$link->addHead("1");
209
$link->printLink(); // 1
210
211
$link->addHead("5");
212
$link->printLink(); // 5->1
213
214
$link->addTail("9");
215
$link->printLink(); // 5->1->9
216
217
$link->addTail("7");
218
$link->printLink(); // 5->1->9->7
219
220
$link->add(3, "8"); 
221
$link->printLink(); // 5->1->9->8->7
222
223
print_r("链表长度:" . $link->getLength() . "\n");
224
225
$link->deleteFirst();
226
$link->printLink();
227
228
$link->deleteLast();
229
$link->printLink();
230
231
$link->deleteIndex(1);
232
$link->printLink();
233
234
print_r("链表长度:" . $link->getLength() . "\n");