Chinaunix首页 | 论坛 | 博客
  • 博客访问: 465214
  • 博文数量: 68
  • 博客积分: 2606
  • 博客等级: 上尉
  • 技术积分: 1308
  • 用 户 组: 普通用户
  • 注册时间: 2010-12-13 23:01
文章分类
文章存档

2012年(6)

2011年(62)

分类: C/C++

2011-06-09 15:28:29

/*定义数据结构类型,单向链表结构体包括数据部分和指针部分*/
struct node 
{
        unsigned int item;
        struct node * next;
};
/*不带头结点的反转函数,该函数采用三个结构体指针分别保存 前一节点 当前节点 后一节点 的值,将当前节点的指针域值直接指向前一节点,后一节点作为链表后面的引线,再将这三个指针往后移一位,递归进行前面的动作*/
struct node * reverse(struct node *head)
{
     if((head == NULL) || (head->next==NULL))  //链表为空,或只有一个结点(无需反转),直接返回
          return head;
     struct node *pre, *cur, *ne;
     pre = head;         //将前面几个节点的地址依次保存在新定义的结构体指针
     cur = head ->next;
     while(cur)
     {
          ne = cur->next;  //如果当前节点不为空,则将其指针域赋给ne指针
          cur->next = pre; //直接将两个指针的指向反转
          pre = cur;           //将当前节点赋给pre,将三个指针在链表中的位子都往后移一位
          cur = ne;     
      }
     head->next = NULL;//将原来的第一个节点的指针域赋为空,作为尾节点
     head = pre;            //将原来的尾节点变成新链表的第一个节点
     return head;
}
******************************************************************
/*带头结点的反转函数,该函数采用三个结构体指针分别保存 前一节点 当前节点 后一节点 的值,将当前节点的指针域值直接指向前一节点,后一节点作为链表后面的引线,再将这三个指针往后移一位,递归进行前面的动作;因为此链表为带头结点的链表,头结点的数据域并没有存放有效的数据,此函数与上一函数的区别是,需要保持头结点不动,只需要反转后面存有效数据的结点部分*/
struct node * reverse(struct node *head)
{
     if(!head || !head->next )  //判断链表是否为空或是否只有一个头节点
          return head;
     struct node *pre, *cur, *ne;
     pre = head->next;         //将前面几个节点的地址依次保存在新定义的结构体指针
     cur = pre ->next;
     while(cur)
     {
          ne = cur->next;  //如果当前节点不为空,则将其指针域赋给ne指针
          cur->next = pre; //直接将两个指针的指向反转
          pre = cur;           //将当前节点赋给pre,将三个指针在链表中的位子都往后移一位
          cur = ne;     
      }
     head->next ->next= NULL;//将原来的第一个节点的指针域赋为空,作为尾节点
     head->next = pre;            //将原来的尾节点变成新链表的第一个节点(头结点所指向的节点
     return head;
}

 
阅读(3451) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~