大漠落日

while(!dead) study++;
posts - 46, comments - 126, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

单向链表逆序

Posted on 2011-06-23 17:01 乱78糟 阅读(1283) 评论(0)  编辑 收藏 引用 所属分类: 算法&数据结构
/***********************************
*    单向链表逆序
*    yanzh 2011-6-23
***********************************
*/
#include 
<iostream>

using namespace std;

class Node{
public:
    Node(
int v):value(v),next(NULL){}
    
int value;
    Node
* next;
};

Node
* init_list(int n)
{
    Node 
*head, *node, *tail;
    
    head 
= tail = NULL;
    
for (int i = 0; i < n; i++)
    {
        node 
= new Node(i);

        
if (i == 0)
        {
            head 
= node;
            tail 
= node;
        }
        
else
        {
            tail
->next = node;
            tail 
= node;
        }
    }
    
return head;
}

void uninit_list(Node *head)
{
    Node 
*node = head;
    
while (head != NULL)
    {
        node 
= node->next;
        delete head;
        head 
= node;
    }
    head 
= NULL;
}

void reverse_list(Node **list)
{
    Node 
*head, *tail, *mid;

    head 
= *list;

    
//一个节点,直接返回
    if (head->next == NULL)
        
return;

    
//两个节点或以上节点
    mid = head->next;
    head
->next = NULL;
    tail 
= mid->next;

    
while (tail != NULL)
    {
        mid
->next = head;
        head 
= mid;
        mid 
= tail;
        tail 
= tail->next;
    }

    mid
->next = head;
    
*list = mid;
}

void output(Node *list)
{
    
int i = 0;
    Node 
*node = list;

    
while (node != NULL)
    {
        cout
<<"node["<<i++<<"] = "<<node->value<<endl;
        node 
= node->next;
    }
}

int main(int argc, char *argv[])
{
    
int len = 5;
    Node 
*list = NULL;

    
if (argc > 1)
        len 
= atoi(argv[1]);
    
    list 
= init_list(len);
    output(list);

    reverse_list(
&list);

    
//输出
    cout<<"\n逆序后\n"<<endl;
    output(list);

    uninit_list(list);
    
    
return 0;    
}

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理