[数据结构] PHP实现数据结构链表的时候出现的问题

hackfan

我根据Pascal的链表代码改编成PHP代码，使用了引用类型来代替指针类型。
此段代码主要是是一个链表插入函数insert()
根据数据的大小，来判断插入的位置，小的放在前面，大的放在后面。
目前有问题的代码，我已经表明出来了——不能插入在表首。数据将被忽略。

1. 
   
2. <?
   
3. error_reporting(E_ALL);
   
4. DEFINE('NIL' , NULL);
   
5. DEFINE('n' , 4);
   
6. 
   
7. $x = stdin();
   
8. 
   
9. new_link($head);
   
10. $head['value'] = $x;
    
11. 
    
12. for($i = 1 ; $i <=n ; $i ++)
    
13. {
    
14.         $x = stdin();
    
15.         insert($head,$x);
    
16. }
    
17. 
    
18. print_r($head);
    
19. 
    
20. $next = &$head;
    
21. 
    
22. echo $next['value']."\n";
    
23. do
    
24. {
    
25.         $next = & $next['link'];
    
26.         echo $next['value']."\n";
    
27. }while(($next['link'] != NIL));
    
28. 
    
29. //初始化链表
    
30. function new_link(&$var)
    
31. {
    
32.         $var = array(
    
33.                 'value' =>; NULL ,
    
34.                 'link' =>; NIL
    
35.         );
    
36. }
    
37. 
    
38. function insert(&$head,$value)
    
39. {
    
40.         new_link($q);
    
41.         $q['value'] = $value;
    
42.         if($value <= $head['value'])
    
43.         {
    
44. /*有问题的代码*/
    
45.                                                                                                 //插入表前
    
46.                                                                                                 $q['link'] = &$head;
    
47.                                                                                                 unset($head);
    
48.                                                                                                 $head = &$q;
    
49. /*有问题的代码*/
    
50.         }
    
51.         else
    
52.         {
    
53.                 //找出表中合适的位置
    
54.                 $next = &$head;
    
55.                 while($value >; $next['value'] && $next['link'] != NIL)
    
56.                 {
    
57.                         $last = &$next;
    
58.                         $next = &$next['link'];
    
59.                 }
    
60.                 if($value <= $next['value'])
    
61.                 {
    
62.                         //插入表中间
    
63.                         $last['link'] = &$q;
    
64.                         $q['link'] = &$next;
    
65.                 }
    
66.                 else
    
67.                 {
    
68.                         //插入表尾
    
69.                         $next['link'] = &$q;
    
70.                         $q['link'] = NIL;
    
71.                 }
    
72. 
    
73.         }
    
74.         unset($q);
    
75. 
    
76. }
    
77. 
    
78. //以下是输入输出处理
    
79. 
    
80. //获得输入流
    
81. function stdin($length='255')
    
82. {
    
83.         if (!isset($GLOBALS['StdinPointer'])){
    
84.                 $GLOBALS['StdinPointer']=fopen("php://stdin","r");
    
85.         }
    
86.         $line=fgets($GLOBALS['StdinPointer'],$length);
    
87.         return trim($line);
    
88. }
    
89. 
    
90. //输出流
    
91. function stdout($msg)
    
92. {
    
93.         if (!isset($GLOBALS['StdoutPointer'])){
    
94.                 $GLOBALS['StdoutPointer']=fopen("php://stdout","w");
    
95.         }
    
96.         fputs($GLOBALS['StdoutPointer'],$msg);
    
97. }
    
98. 
    
99. //输出错误信息
    
100. function stderr($msg)
     
101. {
     
102.         if (!isset($GLOBALS['StderrPointer'])){
     
103.                 $GLOBALS['StderrPointer']=fopen("php://stderr","w");
     
104.         }
     
105.         fputs($GLOBALS['StderrPointer'],$msg);
     
106. }
     
107. ?>;
     

复制代码

运行方式在PHPCLI下，不能在Webserver上运行。

1. 
   
2. //插入表前
   
3. $q['link'] = &$head;
   
4. //此时$head的数据被两个变量指向，一个是$head，一个是$q['link']
   
5. unset($head);
   
6. //把$head到$head的数据的引用关系取消，否则对$head操作同时也对$q['link']操作
   
7. $head = &$q;
   
8. //建立$head到$q内容的引用关系
   

复制代码

请教哪里出错了？

测试数据： 2 6 5 4 7没问题
但是：4 3 5 6 1就不行了，比4大的才能够出现

HonestQiao

请参看：
http://w.yi.org/ftp/FAPM/PHP/php_manual_zh/language.references.arent.html

原帖由 "引用不是什么" 发表：

如前所述，引用不是指针。这意味着下面的结构不会产生你预期的效果：

1. <?php
   
2. function foo (&$var)
   
3. {
   
4.     $var =& $GLOBALS["baz"];
   
5. }
   
6. foo($bar);
   
7. ?>;

复制代码

这将使 foo 函数中的 $var 变量在函数调用时和 $bar 绑定在一起，但接着又被重新绑定到了 $GLOBALS["baz"] 上面。不可能通过引用机制将 $bar 在函数调用范围内绑定到别的变量上面，因为在函数 foo 中并没有变量 $bar（它被表示为 $var，但是 $var 只有变量内容而没有调用符号表中的名字到值的绑定）。

HonestQiao

然后你的程序如下修改：

1. 
   
2. ......
   
3.         $head = insert($head,$x);
   
4. ......
   
5.        function insert($head,$value)
   
6. {
   
7. ......
   
8.    unset($q);
   
9.    return($head);
   
10. }
    
11. ......
    

复制代码

HonestQiao

我是如何发现问题所在的：
1、看过引用的一些说明，然后做了如下测试：

2、然后你的原来的程序如下修改进行测试：

1. 
   
2. ......
   
3.         insert($head,$x);
   
4.         print_r($head);
   
5. ......
   
6.        function insert($head,$value)
   
7. {
   
8. ......
   
9.         unset($q);
   
10.         print_r($head);
    
11. }
    
12. ......   
    

复制代码

3、测试结果表明，当function(insert)结束时，$head因为进行二次的引用操作，其结果恰恰如手册的说明。

HonestQiao

结论:
1、手册是对的
2、手册很重要
3、多看手册是很必要的

powerpolly

干嘛用PHP来做，流程不够清晰。引用的作用和C中的指针是类似但绝不是一回事！用C++写很简单的，如下：

1. 
   
2. #include "iostream.h"
   
3. 
   
4. struct nodeStruct {
   
5.         int data;
   
6.         struct nodeStruct *next;
   
7. }
   
8. 
   
9. typedef struct nodeStruct * NODE;
   
10. 
    
11. function insert( NODE *p, int num )
    
12. {
    
13.         NODE prev;
    
14.         nodeStruct newNode = malloc( sizeof( nodeStruct ));
    
15.         newNode->;data = num;
    
16.        
    
17.         while( num>;p->;data && p->;next )
    
18.         {
    
19.                 prev = p;
    
20.                 p = p->;next;
    
21.         }
    
22.        
    
23.         prev->;next = newNode;
    
24.         newNode->;next = p;
    
25.        
    
26.         return;
    
27. }
    
28. 
    
29. void main( void )
    
30. {
    
31.         int num;
    
32.         nodeStruct node;
    
33.         node->;data = node->;next = NULL;
    
34.        
    
35.         for( int i=0; i<5; i++ )
    
36.         {
    
37.                 cin<<num;
    
38.                 insert( node, num );
    
39.         }
    
40.         //        打印node
    
41.         NODE p = node;
    
42.         while( p->;next )
    
43.         {
    
44.                 cout<<"\n"<<node->;data;
    
45.                 p = p->;next;
    
46.         }
    
47. }
    
48. 
    

复制代码

是不是简洁多了？实际代码未来得及调试。

HonestQiao

原帖由 "powerpolly" 发表：

是不是简洁多了？实际代码未来得及调试。

你这个就是多此一举了。
既然使用PHP来实现，那么这个时候去考虑C++，有点牛头不对马嘴了。

可能Pascal来实现最合适了。