< ! doctype html>
< html>
< head>
< meta charset= "utf-8" >
< title> 双链表 - 插入排序< / title>
< meta http- equiv= "Content-Type" content= "text/html; charset=gb2312" / >
< / head>
< script type= "text/javascript" >
var Node = function ( pData ) {
this . next = null ;
this . prev = null ;
this . data = pData;
}
var DbLinkList = function ( ) {
this . head = new Node ( null ) ;
this . insert = function ( pNodeValue ) {
var newNode = new Node ( pNodeValue) ;
if ( this . head. next == null ) {
this . head. next = newNode;
newNode. prev = this . head;
return ;
}
var p = this . head;
while ( p. next != null ) {
p = p. next;
}
p. next = newNode;
newNode. prev = p;
}
this . getData = function ( index ) {
if ( index < 1 || index > this . size) {
return null ;
}
var p = this . head;
var i = 1 ;
while ( p. next != null && i <= index) {
p = p. next;
i += 1 ;
}
return p. data;
}
this . getTail = function ( ) {
if ( this . head. next == null ) {
return null ;
}
var p = this . head. next;
while ( p. next != null ) {
p = p. next;
}
return p;
}
this . removeAt = function ( index ) {
if ( index < 1 || index > this . size) {
return null ;
}
var p = this . head;
var i = 1 ;
while ( p. next != null && i < index) {
p = p. next;
i += 1 ;
}
p. next = p. next. next;
p. next. prev = p;
return p. data;
}
this . print = function ( ) {
document. write ( "<br/>" ) ;
if ( this . head. next == null ) {
return ;
}
var p = this . head. next;
while ( p. next != null ) {
document. write ( p. data + " " ) ;
p = p. next;
}
document. write ( p. data + " " ) ;
document. write ( "<br/>" ) ;
}
this . printFromBack = function ( ) {
document. write ( "该链表 共有" + this . size + "个元素,从后向前分别为:<br/>" ) ;
var tail = this . getTail ( ) ;
var p = tail;
if ( p == null ) {
return ;
}
while ( p. prev != null ) {
document. write ( p. data + " " ) ;
p = p. prev;
}
document. write ( "<br/>" ) ;
}
this . insertSort = function ( ) {
if ( this . head. next == null || this . head. next. next == null ) {
return ;
}
var p = this . head. next;
while ( true ) {
if ( p == null ) {
return ;
}
var t = p. prev;
while ( t. prev != null && t. data > p. data) {
t = t. prev;
}
if ( t. next == p) {
p = p. next;
continue ;
}
var x = p. next;
if ( p. next != null ) {
p. next. prev = p. prev;
}
p. prev. next = p. next;
t. next. prev = p;
p. next = t. next;
t. next = p;
p. prev = t;
this . print ( ) ;
p = x;
}
}
}
var linkTest = new DbLinkList ( ) ;
linkTest. insert ( 10 ) ;
linkTest. insert ( 9 ) ;
linkTest. insert ( 8 ) ;
linkTest. insert ( 7 ) ;
linkTest. insert ( 6 ) ;
linkTest. insert ( 5 ) ;
linkTest. insert ( 4 ) ;
linkTest. insert ( 3 ) ;
linkTest. insert ( 2 ) ;
linkTest. insert ( 1 ) ;
document. write ( "--排序前---<br/>" )
linkTest. print ( ) ;
linkTest. insertSort ( ) ;
document. write ( "<br/>--排序后---<br/>" )
linkTest. print ( ) ;
< / script>
< / html>