2008秋-计算机软件基础-单链表练习（1）

/*--------------------------------------------------------

 设有一个单链表，头结点为head，为递增有序，

 写一个完整程序，将其改为递减有序。

----------------------------------------------------------*/

#include<stdio.h>

#include<stdlib.h>
//定义结点
struct nodetype

{

    int data;//数据域（可以是int,char,float,数组，结构体等类型)
    struct nodetype * next;

    //next指针域，指向下一个结点。
};

struct nodetype * InitialLinkList()

{

    //初始化链表，返回头指针
    struct nodetype * head;

    head=(struct nodetype *)malloc(sizeof(struct nodetype));//
    head->next=NULL;

    return head;

}

void CreateLinkListInRear(struct nodetype * head, int numbers[], 

                          int LengthOfNumbers)

{

    //尾接法创建单链表

    //从数组numbers[]中取出元素建立单链表

    //LengthOfNumbers为元素个数
    int i;

    struct nodetype * temp,* rear;

    rear=head;

    for(i=0;i<LengthOfNumbers;i++)

    {

        temp=(struct nodetype *)malloc(sizeof(struct nodetype));

        temp->data=numbers[i];

        temp->next=NULL;

        rear->next=temp;

        rear=temp;

    }

}

struct nodetype * ReverseLinkList(struct nodetype * head)

{

    //参照头插法建立单链表的思路，注意：为简单起见，没有释放结点空间

    //注意：如果想到排序算法，就把简单问题复杂化了。
    struct nodetype * newHead;

    struct nodetype * temp;

    struct nodetype *p;

    newHead=InitialLinkList();

    p=head->next;

    while(p!=NULL)

    {

        temp=(struct nodetype *)malloc(sizeof(struct nodetype));

        temp->data=p->data;

        temp->next=newHead->next;

        newHead->next=temp;

        p=p->next;

    }

    return newHead;

}

void PrintIntegerLinkList(struct nodetype * head)

{//显示链表结点数据
    struct nodetype *temp;

    temp=head->next;

    while(temp!=NULL)

    {

        printf("%d ",temp->data);

        temp=temp->next;

    }

    printf("\n");

}

void main()

{

    struct nodetype *head;

    int y[8]={1,2,3,4,5,6,7,8};

    head=InitialLinkList();//初始化
    CreateLinkListInRear(head,y,8);//以数组y中元素创建链表
    printf("显示原始链表中的元素，升序：\n");

    PrintIntegerLinkList(head);

    ReverseLinkList(head);

    printf("显示反转之后链表中的元素，降序：\n");

    PrintIntegerLinkList(ReverseLinkList(head));//显示删除6后链表
    getchar();

}

运行结果如下：

显示原始链表中的元素，升序：

1 2 3 4 5 6 7 8

显示反转之后链表中的元素，降序：

8 7 6 5 4 3 2 1