r******n
发帖数: 170 | 1 假如我写了个linklist的类，如下：
template
struct Node
{
T data;
Node* next;
};
template
class List
{
public:
List():head(NULL){};
List(const Node *inNode):head(inNode){};
~List(){destroy();};
void addToHead( const T &item );
void print( ostream &out ) const;
void reverse();
void destroy();
private:
Node *head;
};
//iterative reverse
template
void List::reverse()
{
if (!head) //empty list
return;
Node *prev=NULL;
Node *curr = head;
while (curr)
{
Node *next = curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
head=prev;
}
有可能把这个成员函数改成递归的写法吗？
（http://www.ihas1337code.com/category/linked-list/page/2）
很久没写C++了，语法都忘记了........... |
m********l
发帖数: 4394 | 2 first of all, why?
why can't you just add a PREV field?
secondly,
if you make it recursive, you can't pass argument.
So, you probably will wind up violating encapsulation.
【在 r******n 的大作中提到】
: 假如我写了个linklist的类，如下：
: template
: struct Node
: {
: T data;
: Node* next;
: };
: template
: class List
: {
|
r******n
发帖数: 170 | 3 啥叫加个prev?你说node里加？还不是double linklist了，又何必做reverse了呢？
我只是讨论下在single linklist时的情况，我想把reverse作为类的成员函数写，不知
道有没有可
能写成递归的形式？
【在 m********l 的大作中提到】
: first of all, why?
: why can't you just add a PREV field?
: secondly,
: if you make it recursive, you can't pass argument.
: So, you probably will wind up violating encapsulation.
|
r**d
发帖数: 316 | 4 可以
基本思想
1：显然,空链表和单节点链表直接返回
2：取下第一个节点
3：递归处理余下的链表，需要将逆转后的链表的尾传出来
4：把第一个节点连到队尾。
【在 r******n 的大作中提到】
: 啥叫加个prev?你说node里加？还不是double linklist了，又何必做reverse了呢？
: 我只是讨论下在single linklist时的情况，我想把reverse作为类的成员函数写，不知
: 道有没有可
: 能写成递归的形式？
|
d*******l
发帖数: 338 | 5 应该可以，但当前的定义不能直接递归，内部得定义另外的辅助函数 |
p*****a
发帖数: 147 | 6 Following the idea:
void List::reverse()
{
reverselist(head);
}
Node* List::reverselist(Node* link)
{
if (!link || ! link->next) {head=link; return link;}
Node* tail=reverselist(link->next);
tail->next=link;
link->next=NULL;
return link;
}
【在 r**d 的大作中提到】
: 可以
: 基本思想
: 1：显然,空链表和单节点链表直接返回
: 2：取下第一个节点
: 3：递归处理余下的链表，需要将逆转后的链表的尾传出来
: 4：把第一个节点连到队尾。
|
m*****k
发帖数: 731 | 7 //Node class
class MyObj
{
int m_value;
MyObj m_next = null;
static MyObj head = null;
static MyObj tail = null;
MyObj(int x)
{
m_value = x;
}
public String toString()
{
return m_value + "";
}
//recurrsive func
static MyObj reverse(MyObj head)
{
MyObj next = head.m_next;
head.m_next = null;
if (next != null)
{
MyObj llast = reverse(next);
llast.m_next = head;
}
else
{
MyObj.head = head;
}
MyObj.tail = head;
return head;
}
String display()
{
//print out the list
String disp = "";
MyObj head = this;
while (head != null)
{
disp += (head.m_value + "->");
head = head.m_next;
}
disp += ".";
JOptionPane.showMessageDialog(null, disp);
return disp;
}
}
private static void testReverse_A_SingleLinkedList2()
{
MyObj[] arr = new MyObj[4];
for (int i = 0; i < arr.length; i++)
{
arr[i] = new MyObj(i);
if (i > 0)
{
arr[i - 1].m_next = arr[i];
}
}
MyObj.head = arr[0];
if(MyObj.head ==null)
{
return;
}
MyObj.head.display();
//reverse the link list
MyObj.reverse(MyObj.head);
MyObj.head.display();
} |
