以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  请教几个《数据结构与算法》上的问题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=38069)

--  作者：yangling_1985
--  发布时间：9/19/2006 9:13:00 PM

--  请教几个《数据结构与算法》上的问题
1，教材P16 给出一示例程序：
    while(n>1)
       if (odd(n))
         n=3*n+1;
       else
        n=n/2;

说“不存在时间复杂度的平均估计，但存在上界和下界”。不知道上下界是为少？如何求？
2、教材P26 算法2.3
     描述中说“当单链表长度小于i时，返回值为NULL”。我怎么觉得i应该是i+1？
3、
     “教材P35页
     变量top为单链表的first指针，指向栈顶。”我记得单链表的first指针指向的是表头结点而非数据结点，谁能解释一下？
4、教材p51  算法2.12 中 assert(Elmlist!=NULL); 中的Elmlist 是否应该是Qlist?
5、《学习指导与习题解析》p9 课程表的抽象数据类型描述中：
virtual void Setsource(ELEM &pday)=0； 中 的“ virtual”  和“ =0”均不理解？

--  作者：Supremgoooo
--  发布时间：9/19/2006 11:24:00 PM

--  
（1）不知道，我对（H）没研究过。

（2）描述中说“当单链表长度小于i时，返回值为NULL”。我怎么觉得i应该是i+1？
注意p的初值是first-〉link。

（3） 变量top为单链表的first指针，指向栈顶。”我记得单链表的first指针指向的是表头结点而非数据结点，谁能解释一下？
栈不需要头指针，因为插入删除只在头上进行。

（4）教材p51  算法2.12 中 assert(Elmlist!=NULL); 中的Elmlist 是否应该是Qlist?
是

5、《学习指导与习题解析》p9 课程表的抽象数据类型描述中：
virtual void Setsource(ELEM &pday)=0； 中 的“ virtual”  和“ =0”均不理解？
不知道。

--  作者：kouyan
--  发布时间：9/20/2006 8:38:00 AM

--  
1。下界是1

5、《学习指导与习题解析》p9 课程表的抽象数据类型描述中：
virtual void Setsource(ELEM &pday)=0； 中 的“ virtual”  和“ =0”均不理解？

这是C++语法，虚函数的用法，找本C++教材看看吧

--  作者：yangling_1985
--  发布时间：9/23/2006 11:19:00 PM

--  
以下是引用Supremgoooo在2006-9-19 23:24:00的发言：
（1）不知道，我对（H）没研究过。

（2）描述中说“当单链表长度小于i时，返回值为NULL”。我怎么觉得i应该是i+1？
注意p的初值是first-〉link。

（3） 变量top为单链表的first指针，指向栈顶。”我记得单链表的first指针指向的是表头结点而非数据结点，谁能解释一下？
栈不需要头指针，因为插入删除只在头上进行。

（4）教材p51  算法2.12 中 assert(Elmlist!=NULL); 中的Elmlist 是否应该是Qlist?
是

5、《学习指导与习题解析》p9 课程表的抽象数据类型描述中：
virtual void Setsource(ELEM &pday)=0； 中 的“ virtual”  和“ =0”均不理解？
不知道。



考虑特殊情况： 单链表只有一个结点（头结点除外）
ListNode *p=first->link  //p初值为指向第一个结点的指针
设i=0，调用算法，return p;(p!=null).而此时单链表的实际长度为1（i+1)
从这个特殊情况可以推理到一般： 当单链表的长度为i+1时，此算法刚好可以返回正常值.若长度小于i+1(即在上例中长度小于1，表中无数据结点),则返回NULL.

请指教，谢谢！

--  作者：Smilingface
--  发布时间：9/26/2006 6:17:00 PM

--  
书中说的是实际长度,头结点也是单链表的一部分。

以下是引用yangling_1985在2006-9-23 23:19:00的发言：
[quote]以下是引用Supremgoooo在2006-9-19 23:24:00的发言：
（1）不知道，我对（H）没研究过。

  （2）描述中说“当单链表长度小于i时，返回值为NULL”。我怎么觉得i应该是i+1？
  注意p的初值是first-〉link。

  （3） 变量top为单链表的first指针，指向栈顶。”我记得单链表的first指针指向的是表头结点而非数据结点，谁能解释一下？
  栈不需要头指针，因为插入删除只在头上进行。

  （4）教材p51  算法2.12 中 assert(Elmlist!=NULL); 中的Elmlist 是否应该是Qlist?
  是

  5、《学习指导与习题解析》p9 课程表的抽象数据类型描述中：
  virtual void Setsource(ELEM &pday)=0； 中 的“ virtual”  和“ =0”均不理解？
  不知道。
[/quote]
考虑特殊情况： 单链表只有一个结点（头结点除外）
ListNode *p=first->link  //p初值为指向第一个结点的指针
设i=0，调用算法，return p;(p!=null).而此时单链表的实际长度为1（i+1)
从这个特殊情况可以推理到一般： 当单链表的长度为i+1时，此算法刚好可以返回正常值.若长度小于i+1(即在上例中长度小于1，表中无数据结点),则返回NULL.

请指教，谢谢！


W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 62.500ms