| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1181 人关注过本帖
标题:单链表逆置算法
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
收藏
 问题点数:0 回复次数:0 
单链表逆置算法
/*
    Name: 单链表逆置
    Copyright:
    Author: 巧若拙
    Date: 22-11-14 16:13
    Description:
    分别用递归和非递归两种方式实现单链表(不含头结点)的逆置
*/

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

typedef char ElemType;
typedef int Status; //函数类型,其值是函数结果状态代码,如OK等

typedef struct Node{
    ElemType data;//数据域
    struct Node *next;//指针域
} Node, *LinkList;

void CreatList(LinkList *head);//创建一个不带头结点的单链表
void DisplayList(LinkList head);//输出单链表的所有结点
void ReverseList(LinkList *head);//逆置单链表方法1
LinkList ReverseList_2(LinkList head);//逆置单链表方法2
LinkList ReverseList_3(LinkList head, Node *pre);//逆置单链表方法3(递归),确保head非空

int main(void)
{
    LinkList a = NULL;
   
    CreatList(&a);//创建一个不带头结点的单链表
    DisplayList(a);//输出单链表的所有结点
    ReverseList_1(&a);//逆置单链表方法1
    DisplayList(a);//输出单链表的所有结点
   
    a = ReverseList_2(a);//逆置单链表方法2  
    DisplayList(a);//输出单链表的所有结点

    a = ReverseList_3(a, NULL);//逆置单链表方法2  
    DisplayList(a);//输出单链表的所有结点
   
    return 0;
}

void CreatList(LinkList *head)//创建一个不带头结点的单链表
{
    int i;
    Node *p, *s;
   
    //创建第一个结点  
    *head = (LinkList)malloc(sizeof(Node));
    if (!*head)
    {
        printf("Out of space!");
        exit(0);
    }
    p = *head;
    p->data = 'A';
    p->next = NULL;
   
    for (i=1; i<10; i++)//创建其余的结点
    {
        s = (LinkList)malloc(sizeof(Node));
        if (!s)
        {
            printf("Out of space!");
            exit(0);
        }
        s->data = i + 'A';
        s->next = NULL;
        p->next = s;
        p = p->next;
    }
}

void DisplayList(LinkList head)//输出单链表的所有结点
{
    while (head)
    {
        printf("%c ", head->data);
        head = head->next;   
    }
    printf("\n");
}

void ReverseList_1(LinkList *head)//逆置单链表方法1
{
    Node *left, *mid, *right;
   
    left = *head;
    mid = left->next;
    left->next = NULL;
    while (mid)
    {
        right = mid->next;
        mid->next = left;
        left = mid;
        mid = right;
    }   
   
    *head = left;
}

LinkList ReverseList_2(LinkList head)//逆置单链表方法2
{
    Node *left, *mid, *right;
   
    left = head;
    mid = left->next;
    left->next = NULL;
    while (mid)
    {
        right = mid->next;
        mid->next = left;
        left = mid;
        mid = right;
    }   
   
    return left;
}

LinkList ReverseList_3(LinkList head, Node *pre)//逆置单链表方法3(递归),确保head非空
{
    Node *p = head->next;
   
    head->next = pre; //逆置尾指针

    return p ? ReverseList_3(p, head) : head;
}
搜索更多相关主题的帖子: Copyright include 
2014-11-22 16:57
快速回复:单链表逆置算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015789 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved