[PHP] 数据结构-循环链表的PHP完成

1.将单链表中终端结点的指针端由空指针改为指向头结点,单循环链表,循环链表和单链表的根本差别就在于循环的判断标准上
原本是判定p->next是不是为空,现在则是p->next不对等头结点,则循环未终止

————————————————————————————————————————————

2.指向终极结点的尾指针代表该循环链表

循环单链表

3.开立循环链表关键是头结点指向自身,最后一个极限结点指向头结点

– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –

<?php
class Node{
        public $data;
        public $next;
}
//创建一个链表
$linkList=new Node();
//头结点指向自身
$linkList->next=$linkList;
$temp=$linkList;
for($i=1;$i<=10;$i++){
        $node=new Node();
        $node->data="aaa{$i}";
        //最后一个结点指向头结点
        $node->next=$linkList;
        $temp->next=$node;
        $temp=$node;
}
//循环链表的遍历
function printLoopLink($linkList){
        $p=$linkList;
        //头结点
        $head=$linkList;
        //如果下一个结点是头结点代表结束
        while($p->next!=$head){
                $p=$p->next;
                print_r($p->data."  ");
        }   
}


//循环链表的优势
function printLoopLink3($linkList){
        //循环链表的优势,从第三个结点开始遍历,遍历全部链表
        $p=$linkList->next->next->next;
        $head=$linkList->next->next->next;
        while($p->next!=$head){
                $p=$p->next;
                print_r($p->data."  ");
        }   
}

printLoopLink($linkList);
printLoopLink3($linkList);

  

尾指针是指向终极结点的指针,用它来代表单循环链表可以使得搜索链表的开首结点和极端结点方便。

安装尾指针因为初叶结点和终端结点查询的年月复杂度都是O(1)。而设置头指针,查找终端结点的岁月复杂度为O(n)。

– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –


协会体定义://其余操作方法与单链表相似,不一一列举

代码落成

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 typedef int ElemType;
 5 typedef int Status;
 6 struct LNode
 7 {
 8     ElemType data;
 9     struct LNode *next;
10 };

– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –


结点最先化/插入结点:

代码达成:

 1 void InitList_CL(struct LNode **L)
 2 {
 3     *L = (struct LNode *)malloc(sizeof(struct LNode));
 4     if (!*L)
 5         exit(0);
 6     (*L)->next = (*L); //指针域指向头结点
 7 }
 8 int ListInsert_CL(struct LNode **L)
 9 {
10     int n, number, i = 0;
11     printf("The input position n:");
12     scanf("%d", &n);
13     printf("The input digital number:");
14     scanf("%d", &number);
15     if (number < 1)
16     {
17         return 0;
18     }
19     struct LNode *p, *s;
20     p = (*L)->next;
21     while(i < n - 1)
22     {
23         p = p->next;
24         i++;
25     }
26     s = (struct LNode *)malloc(sizeof(struct LNode));
27     s->data = number;
28     s->next = p->next;
29     p->next = s;
30     if(p == *L)
31     {
32         *L = s;
33     }
34     ListInsert_CL(L);
35 }

 

图解:当输入地点为1,值为1 2 3 4时进度如下:

图片 1

– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –


结点打印:

打印时指针指向头结点,循环打印,直到指向尾节点L

代码已毕:

 1 void ListPrint_CL(struct LNode *L)
 2 {
 3     struct LNode *p;
 4     p = L->next;
 5     while(p != L)
 6     {
 7         p = p->next;
 8         printf("%d ", p->data);
 9     }
10     printf("\n");
11 }

 

– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –


一体化代码

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 typedef int ElemType;
 5 typedef int Status;
 6 struct LNode
 7 {
 8     ElemType data;
 9     struct LNode *next;
10 };
11 void ListEmpty_CL(struct LNode *L)
12 {
13     if (L->next == L) //当指针域指向头结点时证明没有其他结点,链表为空
14     {
15         printf("The list is empty\n");
16     }
17 }
18 void InitList_CL(struct LNode **L)
19 {
20     *L = (struct LNode *)malloc(sizeof(struct LNode));
21     if (!*L)
22         exit(0);
23     (*L)->next = (*L); //指针域指向头结点
24 }
25 int ListInsert_CL(struct LNode **L)
26 {
27     int n, number, i = 0;
28     printf("The input position n:");
29     scanf("%d", &n);
30     printf("The input digital number:");
31     scanf("%d", &number);
32     if (number < 1)
33     {
34         return 0;
35     }
36     struct LNode *p, *s;
37     p = (*L)->next;
38     while(i < n - 1)
39     {
40         p = p->next;
41         i++;
42     }
43     s = (struct LNode *)malloc(sizeof(struct LNode));
44     s->data = number;
45     s->next = p->next;
46     p->next = s;
47     if(p == *L)
48     {
49         *L = s;
50     }
51     ListInsert_CL(L);
52 }
53 void ListPrint_CL(struct LNode *L)
54 {
55     struct LNode *p;
56     p = L->next;
57     while(p != L)
58     {
59         p = p->next;
60         printf("%d ", p->data);
61     }
62     printf("\n");
63 }
64 int main(int argc, char const *argv[])
65 {
66     struct LNode *L;
67     int j;
68     Status i;
69     InitList_CL(&L); //初始化链表
70     ListEmpty_CL(L); //判断链表是否为空
71     ListInsert_CL(&L); //在链表中第n个位置插入元素
72     ListPrint_CL(L); //打印链表
73     return 0;
74 }

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图