[PHP] 数据结构-链表成立-插入-删除-查找的PHP落成

发布时间:2019-02-13  栏目:Python  评论:0 Comments

链表获取成分
1.表明结点p指向链表第四个结点,j起首化1开端
2.j<i,p指向下一结点,因为此时p是指向的p的next,由此不要求格外
3.只要到结尾了,p还为null,就是没有检索到

  使用了NIL来作为链表的头和尾,创设的时候也用插入函数插入,在遍历的时候若是判断当前的指针指向的情节是不是NIL即可。

安插成分
1.插入元素和寻找类似,找到地点后
2.生成新的结点s, s->next=p->next p->next=s;

至于NIL节点的应用:

除去成分
1.去除成分,找到地方后
2.绕过一下,q=p->next p->next=q->next;

Node NIL;
Node *nil = &NIL;

 

关于内存池的采用:

<?php
class Node{
        public $data;
        public $next;
}
//创建一个链表
$linkList=new Node();
$linkList->next=null;
$temp=$linkList;
for($i=1;$i<=10;$i++){
        $node=new Node();
        $node->data="aaa{$i}";
        $node->next=null;
        $temp->next=$node;
        $temp=$node;
}


//获取元素
function getEle($linkList,$i,&$e){
        $p=$linkList->next;
        //寻找结点标准语句
        $j=1;
        while($p && $j<$i){
                $p=$p->next;
                ++$j;
        }   
        if(!$p || $j>$i){
                return false;
        }   
        $e=$p->data;
        return true;
}

//插入元素
function listInsert(&$linkList,$i,$e){
        $p=$linkList;
        $j=1;
        while($p && $j<$i){
                $p=$p->next;
                ++$j;
        }   
        if(!$p || $j>$i){
                return false;
        }   
        $s=new Node();
        $s->data=$e;
        //插入元素标准语句
        $s->next=$p->next;
        $p->next=$s;
        return true;
}
//删除元素
function listDelete(&$linkList,$i,&$e){
        $p=$linkList;
        $j=1;
        //注意这里的判断$p->next为真,主要是后面要把$p->next指向$p->next->next
        while($p->next && $j<$i){
                $p=$p->next;
                ++$j;
        }
        if(!$p->next || $j>$i){
                return false;
        }
        $q=$p->next;//这个才是当前元素
        $e=$q->data;
        $p->next=$q->next;
        return true;
}
$e="";
//获取元素
getEle($linkList,5,$e);
var_dump($e);
//插入元素
listInsert($linkList,5,"taoshihan");
//删除元素
listDelete($linkList,1,$e);
var_dump($e);
var_dump($linkList);
Node pool[MAX];
int poolIndex;
Node* getnew(){

    return &pool[poolIndex++];

}

  

部署的时候对于七个指针进行操作:

    NewNode->pre = dstNode;
    NewNode->next = dstNode->next;

    dstNode->next->pre = NewNode;
    dstNode->next = NewNode;

2017年9月30日10:58:50更新:—————————————————————————————————————————————————————————————

至于插入的时候多个指针操作的次第大概导致的BUG

  七个指针操作,对于Newnode的操作一般不会有毛病,不过对于dst的操作要达到的效果在眼下以此例子里面是要兑现一个每插入一个要素它的pre指向前一个要素,next指向链表头(即NIL)的数据链式结构。

不过当先把地点的操作中的后两项颠倒一下的时候汇合世如下的场景:

图片 1 
对应代码: dstNode->next =
NewNode;

                                    dstNode->next->pre

NewNode;                                    
可以看见。我们没插入一个节点并不曾对准NIL,而是指向了她协调。原因就在于大家先操作dst->next
=newnode的时候改变了dst->next的值,可是大家后面还要用到dst->next的值,所以必要先操作dst->next->pre,然后再操作dst->next.那样才能保障收获如下图的结果:

图片 2对应代码:dstNode->next->pre =
NewNode;  

                                  dstNode->next
= NewNode;

 

!!!所以得出的下结论就是插入的时候为了幸免那种BUG,就先对于pre进行操作(蕴涵dst和newnode),然后再对此next举行操作。

—————————————————2017年9月30日11:11:54———————————————————————————————————————————————

除去的时候对于要刨除的节点的前一个节点和后一个节点的多少个指针的操作:

    node->pre->next = node->next;
    node->next->pre = node->pre;

总体测试代码:

#include <stdio.h>
#include <malloc.h>
#define MAX 100000
typedef struct node{
    int data;
    struct node *next;
    struct node *pre;
}Node;
Node NIL;
Node *nil = &NIL;
Node pool[MAX];
int poolIndex;
Node* getnew(){

    return &pool[poolIndex++];

}
void listInit(){

    nil->next = nil;
    nil->pre = nil;
    nil->data = 0;

}

void listInsertAfter(Node*dstNode,Node*NewNode){

    NewNode->pre = dstNode;
    NewNode->next = dstNode->next;

    dstNode->next->pre = NewNode;
    dstNode->next = NewNode;

}

void listDelete(Node*node){

    node->pre->next = node->next;
    node->next->pre = node->pre;

}

Node* search(int key){
    Node *x = nil->next;//从表头的下一个元素开始找
    while (x != nil&&x->data !=key){
        x = x->next;
    }
    return x;//可能返回NIL或者找到的数据的地址
}

void showList(){
    Node * x = nil->next;//从第一个元素开始显示
    while (x != nil){
        printf("%d\n", x->data);
        x = x->next;
    }

}
//主函数实现的功能:在链表中添加1到20的数字,然后找到2的位置在它后面添加一个22,然后再利用删除函数删除。
int main(){
    listInit();
    Node *dstnode = getnew();
    dstnode = nil;
    for (int i = 1; i <= 20; i++){
        Node * newnode = getnew();
        newnode->data = i;
        listInsertAfter(dstnode,newnode);
        dstnode = newnode;

    }
    dstnode = search(2);
    Node * newnode = getnew();
    newnode->data = 22;
    listInsertAfter(dstnode, newnode);
    showList();
    dstnode = search(22);

    listDelete(dstnode);
    showList();

}

 

留下评论

网站地图xml地图