首页 > 代码库 > 数据结构学习系列之线性表(二)

数据结构学习系列之线性表(二)

2024-11-16 01:22:39   204人阅读

前言

线性表链式存储结构的实现，通过这种方式实现的线性表，简称为链表，这是这篇文章的主题。与顺序存储相对应的是链式存储。链式存储逻辑结构相邻，物理结构可能相邻也有可能不相邻。链式结构的优点有：1.存储空间不限制(操作系统可支持的存储空间范围内)；2.插入删除操作不需要移动元素等等。当然链式结构也有缺点，比如每个节点需要维护指向下一个节点的指针；比如需要查找某个节点时，需要从头节点开始查找，时间复杂度O(n)等等。总之，顺序存储以及链式存储各有优缺点，需要根据需求具体情况，选择合适的存储方式。没有事物是万能的，不同的问题尽可能用不同的擅长解决这类问题的事物解决。有一句很流行的话，存在即是合理的。

链式结构

什么是链式结构呢？线性表各个节点逻辑结构相邻，物理结构可以不相邻，这样的存储方式是链式存储，每个节点的关联关系就是链式结构。

链表的抽象数据结构模型

它包含：节点的定义，链表初始化，插入，删除，清空，销毁，链表长度，是否为空的判断，查找，定位等操作。使用JS模拟实现链表抽象数据结构模型。不同的语言实现方式不一样。

初始化

头插法

LinkList.prototype.createHead = function(n){ //头插法    for (var i = 0 ; i < n; i++){        var node = new Node( Math.ceil(Math.random()*10000));            node.next = this.head.next;        this.head.next = node;    }    return true;};

尾插法

LinkList.prototype.createTail = function(n){ //尾插法    var lastNode = this.head;    for (var i = 0; i < n; i++){        node = new Node( Math.ceil(Math.random()*10000));        lastNode.next = node;        lastNode = node;    }    return true;};

插入

链表中元素插入第N个位置，找到链表中第N-1个位置的节点之后，让需要插入的节点后继节点指针指向第N-1个节点的后继节点，然后第N-1个节点的后继节点指针指向当前插入的节点

LinkList.prototype.insert = function(i,node){    i = parseInt(i);    if (isNaN(i)){        return false;    }    if (!(node instanceof Node)){        return false;    }    var j = 1;    var p = this.head;    while (p && (j < i)){        p = p.next;        j++;    }    if (!p || (j < i)){        return false;    }    node.next = p.next;    p.next = node;    return true;}

删除

删除链表中第N个元素，找到第N-1个位置的节点，让第N-1个节点的后继指针指向第N个节点后继节点指针指向的后继节点，然后释放第N个节点的内存

LinkList.prototype.remove = function(i){    i = parseInt(i);    if (isNaN(i) || (i < 1)){        return false;    }    var p = this.head;    var j = 1;    while (p && (j < i)){        p = p.next;        j++;    }    if (!p || (j < i)){        return false;    }    var q = p.next;    if (!q){        return false;    }    p.next = q.next;    q.next = null;    return q;};

查找

LinkList.prototype.get = function(i){    i = parseInt(i);    if (isNaN(i)){        return false;    }    var p = this.head;    var j = 1;    while(p && (j < i)){        p = p.next;        j++;    }    if (!p || (j < i)){        return false;    }    if (p.next){        return p.next.data;    }    return false;};

定位

LinkList.prototype.locate = function(node){    if (!(node instanceof Node)){        return -1;    }    var p = this.head.next;    var j = 1;    while(p){        if (p.data =http://www.mamicode.com/= node.data){>

清空

LinkList.prototype.clear = function(){    var p = this.head;    var q;    while(p){        q = p.next;        p = p.next;        delete q;    }    this.head.next = null;    return true;};

完整代码

技术分享
  1 /**  2  * @desc 单链表  3  *  4  * @author WadeYu  5  * @date 2015-01-02  6  * @copyright by WadeYu  7  */  8 var Node = function(data){  9     this.data =http://www.mamicode.com/ data; 10     this.next = null; 11 }; 12 var LinkList = function(){ 13     this.head = new Node(0); 14 }; 15 LinkList.prototype.createHead = function(n){ //头插法 16     for (var i = 0 ; i < n; i++){ 17         var node = new Node( Math.ceil(Math.random()*10000)); 18             node.next = this.head.next; 19         this.head.next = node; 20     } 21     return true; 22 }; 23 LinkList.prototype.createTail = function(n){ //尾插法 24     var lastNode = this.head; 25     for (var i = 0; i < n; i++){ 26         node = new Node( Math.ceil(Math.random()*10000)); 27         lastNode.next = node; 28         lastNode = node; 29     } 30     return true; 31 }; 32 LinkList.prototype.insert = function(i,node){ 33     i = parseInt(i); 34     if (isNaN(i)){ 35         return false; 36     } 37     if (!(node instanceof Node)){ 38         return false; 39     } 40     var j = 1; 41     var p = this.head; 42     while (p && (j < i)){ 43         p = p.next; 44         j++; 45     } 46     if (!p || (j < i)){ 47         return false; 48     } 49     node.next = p.next; 50     p.next = node; 51     return true; 52 } 53 LinkList.prototype.remove = function(i){ 54     i = parseInt(i); 55     if (isNaN(i) || (i < 1)){ 56         return false; 57     } 58     var p = this.head; 59     var j = 1; 60     while (p && (j < i)){ 61         p = p.next; 62         j++; 63     } 64     if (!p || (j < i)){ 65         return false; 66     } 67     var q = p.next; 68     if (!q){ 69         return false; 70     } 71     p.next = q.next; 72     q.next = null; 73     return q; 74 }; 75 LinkList.prototype.get = function(i){ 76     i = parseInt(i); 77     if (isNaN(i)){ 78         return false; 79     } 80     var p = this.head; 81     var j = 1; 82     while(p && (j < i)){ 83         p = p.next; 84         j++; 85     } 86     if (!p || (j < i)){ 87         return false; 88     } 89     if (p.next){ 90         return p.next.data; 91     } 92     return false; 93 }; 94 LinkList.prototype.locate = function(node){ 95     if (!(node instanceof Node)){ 96         return -1; 97     } 98     var p = this.head.next; 99     var j = 1;100     while(p){101         if (p.data =http://www.mamicode.com/= node.data){102             return j;103         }104         j++;105         p = p.next;106     }107     return -1;108 };109 LinkList.prototype.clear = function(){110     var p = this.head;111     var q;112     while(p){113         q = p.next;114         p = p.next;115         delete q;116     }117     this.head.next = null;118     return true;119 };120 LinkList.prototype.print = function(){121     var p = this.head;122     var i = 0;123     while(p){124         i++;125         p = p.next;126         if (p){127             console.log("No."+i+",value="http://www.mamicode.com/+p.data);128         }129     }130     return true;131 };
View Code

测试用例

技术分享
 1 var linkList = new LinkList(); 2     linkList.createTail(5); 3  4 console.log("The Link list is:"); 5 linkList.print(); 6  7 console.log("----------------------"); 8  9 console.log("Test Insert");10 for (var i = 0; i < 2; i++){11     var iTmpData = http://www.mamicode.com/Math.ceil(Math.random()*10000);12     var iPos = Math.ceil(Math.random()*10);13     console.log("Insert data %s at No.%s",iTmpData,iPos);14     linkList.insert(iPos,new Node(iTmpData));15 }16 linkList.print();17 18 console.log("--------------------------");19 20 console.log("Test Remove");21 22 for (var i = 0; i < 2; i++){23     var iPos = Math.ceil(Math.random()*10);24     console.log("Remove data at %s",iPos);25     linkList.remove(iPos);26 }27 linkList.print();28 29 console.log("-----------------------");30 31 console.log("Test Get");32 33 for (var i = 0; i < 5; i++){34     var iPos = Math.ceil(Math.random()*10);35     console.log("The Data At %s is %s",iPos,linkList.get(iPos));36 }37 38 console.log("-----------------------------");39 40 console.log("Test Locate");41 42 var aData =http://www.mamicode.com/ [];43 var p = linkList.head.next;44 while(p){45     aData.push(p.data);46     p = p.next;47 }48 for (var i = 0; i < 5; i++){49     iTmpData = http://www.mamicode.com/aData[ Math.ceil(Math.random()*10)  % aData.length];50     console.log("The Data %s At %s",iTmpData,linkList.locate(new Node(iTmpData)));51 }52 53 console.log("----------------------");54 55 console.log("Test Clear");56 57 linkList.clear();58 linkList.print();
View Code

后记

链表是最基本的数据结构，是其它数据结构的基础，需要好好掌握它。

数据结构学习系列之线性表(二)


联系
我们