单链表的逆转-C语言

/*
 * LinkList.c
 *
 * Created on: 2010-12-16
 * Author: qiang
 */

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

typedef int ElemType;
typedef int Status;
typedef struct LNode{    //定义单链表数据结构

    ElemType data;
    struct LNode* next;
}LNode,*LinkList;

//初始化一个空链表

LinkList LinkListInit()
{
    LNode* L;
    L = (LNode*)malloc(sizeof(LNode));
    if(L==NULL)
        printf("申请内存空间失败");
    L->next = NULL;

    return L;
}

//创建一个单链表

LinkList LinkListCreat()
{
    //创建头节点

    LNode* L;
    L = (LNode*)malloc(sizeof(LNode));
    if(L==NULL)
        printf("分配空间失败！\n");
    L->next=NULL;    //初始化空链表


    //定义节点r，r始终指向尾节点

    LNode* r;
    r = L;    //其实r指向头指针


    //添加新节点

    int i;
    printf("请输入链表数据，CTRL+D结束！ \n");
    while(scanf("%d",&i)!=EOF)
    {
        LNode* p;
        p = (LNode*)malloc(sizeof(LNode));
        p->data = i;

        r->next = p;    //和前节点建立关系

        r = p;            //r节点后移

    }

    printf("创建的链表的数据为： \n");
    LNode* q;
    for(q=L->next;q!=NULL;q=q->next)
        printf("List data:%d \n",q->data);

    //添加尾节点

    r->next = NULL;

    return L;
}

//测出单链表的长度

int LinkListLen(LNode* L)
{
    int i=0;    //链表长度

    LNode* r;
    for(r=L->next;r!=NULL;r=r->next)
        i++;

    return i;
}

//实现单链表的逆转

LinkList LinkListReverse(LNode* L)
{
    if(L==NULL || L->next==NULL)    //空链表

        return L;

    LNode *p1,*p2,*p3;    // |p1| -> |p2| -> |p3|

    p1 = L->next;
    p2 = p1->next;
    while(p2!=NULL)
    {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }
    L->next = NULL;    //头指针变成尾节点

    L = p1;
    return L;
}

//删除头节点

LinkList LinkListRmHead(LNode *L)
{
    LNode *p,*q;
    p = L->next;    //指向头节点

    L->next = p->next;
    free(p);
    for(q=L->next;q!=NULL;q=q->next)
            printf("List Del after data:%d \n",q->data);
    return L;
}


int main()
{
    //创建单链表

    LNode* L;
    L = LinkListCreat();

    //求长度

    int i=0;
    i = LinkListLen(L);
    printf("The length is %d \n",i);

    /*
    //单链表逆转
    L = LinkListReverse(L);
    LNode *r;    //指向头指针
    for(r=L;r!=NULL;r=r->next)
        printf("List reverse data:%d \n",r->data);
    */
    L = LinkListRmHead(L);

    return 0;
}


文件:	cLinkList.tar.gz
大小:	17KB
下载:	下载