问答题
【说明】
链表和栈对象的共同特征是：在数据上执行的操作与在每个对象中实体存储的基本类型无关。例如，一个栈存储实体后，只要保证最后存储的项最先用，最先存储的项最后用，则栈的操作可以从链表的操作中派生得到。程序6-1实现了链表的操作，程序6-2实现了栈操作。
import java.io.*;
class Node //定义结点
{ private String m_content;
private Node m_next;
Node(String str)
{ m_content=str;
m_next=null; }
Node(String str,Node next)
{ m_content=str;
m_next=next; }
String getData() //获取结点数据域
{ return m_content;}
void setNext(Node next] //设置下一个结点值
{ m_next=next; }
Node getNext() //返回下一个结点
{ return m_next; )
}
【程序6-1】
class List
{ Node Head;
List()
{ Head=null; }
void insert(String str) //将数据str的结点插入在整个链表前面
{ if(Head==null)
Head=new Node(str);
else
{{U}} (1) {{/U}}
}
void append(String str) //将数据str的结点插入在整个链表尾部
{ Node tempnode=Head;
it(tempnode==null)
Heed=new Node(str);
else
{ white(tempnode.getNext()!=null)
{{U}} (2) {{/U}}
{{U}}(3) {{/U}}}
}
String get() //移出链表第一个结点，并返回该结点的数据域
{ Srting temp=new String();
if(Head==null)
{ System.out.println("Errow! from empty list!")
System.exit(0); }
else
{ temp=Head.getData();
{{U}} (4) {{/U}} }
return temp;
}
}
【程序6-2】
class Stack extends List
{ void push(String str) //进栈
{ {{U}} (5) {{/U}} }
String pop() //出栈
{ return get();}
}
【正确答案】
【答案解析】Head=new Node(str，Head);
(2)tempnode=tempnode.getNext();
(3)tempnode.setNext(new Node(str,tempnode.getNext()));
(4)Head=Head.getNext()；
(5)insert(str);
[分析]
本题考查链表和栈的基本特征在Java中的实现。
在对链表进行表头插入时，首先要判断该链表是否为空，如果为空，直接插入结点；如果非空，在插入结点时把该结点的指针域改成能指向下一个结点的地址。在队尾插入时，同样要判断该链表是否为空，如果为空，直接插入结点；如果非空，在插入结点时把上一个结点的指针域改成能指向该结点的地址。
下面来具体分析代码，首先定义了一个结点类，类中有两个不同的构造函数和三个函数，分别用于获取结点数据域，设置下一个结点值和返回下一个结点值。第(1)空是函数insert()里面的代码，函数要实现的功能是将数据str的结点插入在整个链表前面。结合整个函数看，此空处要实现的功能是在非空链表的前面插入结点，需要指针域来存放下一个结点的地址，而下一个结点的地址就是Head，因此，此处应该填Head=new Node(str,Head)。
第(2)空和第(3)空一起考虑，它们都是函数append()里面的内容。函数要实现的功能是将数据str的结点插入在整个链表尾部。这两空要实现的功能是在非空链表的尾部插入结点。这需要调用返回下一个结点值函数和设置下一个结点值函数，因此，第 (2)空和第(3)空的答案分别为tempnode=tempnode.getNext()和tempnode.setNext(new Node(str,tempnode.getNext()))。
第(4)空是函数get()里面的内容，此函数的功能是移出链表第一个结点，并返回该结点的数据域，从整个函数来看，此空处的功能是让链表的地址Head指向下一个结点。因此，答案为Head=Head.getNext()。
第(5)空就比较简单了，要实现的功能就是让数据进栈，而进栈操作是在栈顶进行插入的，因此，只要调用函数insert()即可，其参数是str，此空答案为insert(str)。