"); } //节点类 var Node = function (v) { this.data = v; //节点值 this.next = null; //后继节点 } //单链表 var SingleLink = function () { this.head = new Node(null); //约定头节点仅占位，不存值 //插入节点 this.insert = function (v) { var p = this.head; while (p.next != null) { p = p.next; } p.next = new Node(v); } //删除指定位置的节点 this.removeAt = function (n) { if (n <= 0) { return; } var preNode = this.getNodeByIndex(n - 1); preNode.next = preNode.next.next; } //取第N个位置的节点(约定头节点为第0个位置) //N大于链表元素个数时，返回最后一个元素 this.getNodeByIndex = function (n) { var p = this.head; var i = 0; while (p.next != null && i < n) { p = p.next; i++; } return p; } //查询值为V的节点， //如果链表中有多个相同值的节点， //返回第一个找到的 this.getNodeByValue = function (v) { var p = this.head; while (p.next != null) { p = p.next; if (p.data == v) { return p; } } return null; } //打印输出所有节点 this.print = function () { var p = this.head; while (p.next != null) { p = p.next; print(p.data + " "); } println(""); } } //测试单链表L中是否有重复元素 function hasSameValueNode(singleLink) { var i = singleLink.head; while (i.next != null) { i = i.next; var j = i; while (j.next != null) { j = j.next; if (i.data == j.data) { return true; } } } return false; } //单链表元素反转 function reverseSingleLink(singleLink) { var arr = new Array(); var p = singleLink.head; //先跑一遍，把所有节点放入数组 while (p.next != null) { p = p.next; arr.push(p.data); } var newLink = new SingleLink(); //再从后向前遍历数组,加入新链表 for (var i = arr.length - 1; i >= 0; i--) { newLink.insert(arr[i]); } return newLink; } var linkTest = new SingleLink(); linkTest.insert('A'); linkTest.insert('B'); linkTest.insert('C'); linkTest.insert('D'); linkTest.print();//A B C D var newLink = reverseSingleLink(linkTest); newLink.print();//D C B A @H_403_7@

关于

邻接矩阵、邻接表

的选择：

邻接矩阵、邻接表都是图的基本存储方式，

稀松图

情况下（即边远小于顶点情况下），用邻接表存储比较适合（相对矩阵N*N而言，邻接表只存储有值的边、顶点，不存储空值，存储效率更高）

稠密图

情况下（即边远大地顶点情况下），用邻接矩阵存储比较适合（数据较多的情况下，要对较做遍历，如果用链表存储，要经常跳来跳去，效率较低）

堆：

几乎完全的二叉树

：除了最右边位置上的一个或几个叶子可能缺少的二叉树。在物理存储上，可以用数组来存储，如果A[j]的顶点有左、右子节点，则左节点为A[2j]、右节点为A[2j+1]，A[j]的父顶点存储在A[j/2]中

堆：

本身是一颗几乎完全的二叉树，而且父节点的值不小于子节点的值。应用场景：优先队列，寻找最大或次最大值；以及把一个新元素插入优先队列。

注：以下所有讨论的堆，约定索引0处的元素仅占位，有效元素从下标1开始

根据堆的定义，可以用以下代码测试一个数组是否为堆：