本文分享如何用 JavaScript 實作單向鏈結串列,列出所有單字及其出現次數。做法是可呼叫 LinkedList 類別的 orderInsert() 方法,依字母大小順序儲存英文字串,同時記錄每個單字出現的次數,供參考。
<html>
<head>
<title>Linked List</title>
<meta charset="utf-8">
</head>
<body>
<script type="text/javascript">
function Node(data) {
this.data = data;
this.frequency = 1;
this.next = null;
}
var SList = function SList() {
this.head = new Node("Dummy");
}
SList.prototype.insertLast = function (data) {
var p = this.head;
while (p.next != null) p = p.next;
p.next = new Node(data);
}
SList.prototype.insertFirst = function (data) {
var p = new Node(data);
p.next = this.head.next;
this.head.next = p;
}
SList.prototype.traversal = function () {
var p = this.head;
while (p.next != null) {
document.write(p.next.data + "(" + p.next.frequency + "), ");
p = p.next;
}
}
SList.prototype.orderInsert = function (data) {
var k = this.search(data);
if (k) k.frequency++;
else {
var p = new Node(data);
var q = this.head;
while (q.next != null && q.next.data < data) q = q.next;
p.next = q.next;
q.next = p;
}
}
SList.prototype.search = function (data) {
var p = this.head;
while (p.data != data && p.next != null) p = p.next;
if (p.data != data) return null;
else return p;
}
var Slist = new SList();
var s = new Array("earthquake","prediction","geology","physics",
"chemistry","biology","mathematics","computer","earth_science",
"chemistry","biology","mathematics","computer","paleomagnetism",
"topology","biology","mathematics","computer","earthquake");
for (var i = 0; i < s.length; i++) Slist.orderInsert(s[i]);
Slist.traversal();
</script>
</body>
</html>
這段程式的巧思在於 orderInsert():插入每個單字前先呼叫 search() 查找是否已存在,若存在就將頻率 frequency 加一,否則依字母順序插入適當位置。如此一來,遍歷串列時便能一次列出所有單字及其出現次數。
