学步园

/***************************************************************************************************
单项链表基本操作
环境：VS2005   WIN控制台程序
楼主：张永辉   20120907
***************************************************************************************************/

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>

/***************************************************************************************************
***************************************************************************************************/
struct  gLIST
{
    int nat;
    gLIST *mnext;
};

gLIST*  CreatList(int number);                  //创建链表
gLIST * InsertgList(gLIST *head ,int post);     //插入节点
gLIST * DelList(gLIST *head ,int post);         //删除一个节点
int     DelAllList(gLIST *head);                //删除整个链表
void    PrintList(gLIST *head);                 //打印节点
void    SetVlueList( gLIST *head);              //赋随机值
gLIST*  bobble(gLIST *head);                    //排序
gLIST * TurnList(gLIST * head);                 //反序

/***************************************************************************************************
main
***************************************************************************************************/

int _tmain(int argc, _TCHAR* argv[])
{
    gLIST *ghead = NULL;
    gLIST *tempNode = NULL;
    int count = 0;

    ghead = CreatList(5);           //创建5个节点的链表
    SetVlueList(ghead);             //给随机值
    PrintList(ghead);

    ghead = bobble(ghead);          //排序
    PrintList(ghead);

    ghead = InsertgList(ghead,1);   //在位置1 插入一个
    ghead = InsertgList(ghead,5);   //在位置5 插入一个
    PrintList(ghead);

    ghead = DelList(ghead,5);       //删除最后一个
    PrintList(ghead);

    ghead = TurnList(ghead);        //反序
    PrintList(ghead);

    DelAllList(ghead);              //删除整个链表

    system("pause");
    return 0;
}
//**************************************************************************************************
void PrintList(gLIST *head)
{
    int count = 0;
    printf("\n");
    for ( ; NULL != head ; )
    {
        printf("No.%d:  addr is %d, next is %d, data is %d\n", count, head, head->mnext, head->nat);
        head = head->mnext;
        count++;
    }
}
//**************************************************************************************************
gLIST* CreatList(int number)
{
    gLIST *head;
    gLIST *p1;
    gLIST *p2;

    if ( number <= 0)
    {
        return NULL;
    }

    head = (gLIST *)malloc(sizeof(gLIST));
    head->mnext = NULL;

    p1 = head;
    while ( --number )
    {
        p2 = (gLIST *)malloc(sizeof(gLIST));
        p1->mnext = p2;
        p2->mnext = NULL;

        p1 = p2;
    }

    return head;
}
//**************************************************************************************************
int DelAllList(gLIST *head)
{
    gLIST *p1;

    while(NULL != head)
    {
        p1 = head->mnext;
        free(head);
        head = p1;
    }

    return 0;
}
//**************************************************************************************************
gLIST * InsertgList(gLIST *head ,int post)
{
    gLIST *p1;
    gLIST *p2;
    if ( NULL == head || post < 0 )
    {
        return NULL;
    }

    p1 = (gLIST *)malloc(sizeof(gLIST));

    //在位置0插入
    if ( 0 == post)
    {
        p1->mnext = head;
        return p1;
    }

    p2 = head;
    while(1)
    {
        //在末尾插入
        if ( NULL == p2->mnext )
        {
            p2->mnext = p1;
            p1 ->mnext = NULL;
            return head;
        }

        //在中间插入
        if ( --post == 0)
        {
            p1->mnext = p2->mnext;
            p2->mnext = p1;

            return head;
        }
        p2 = p2->mnext;
    }

    return head;
}
//**************************************************************************************************
gLIST * DelList(gLIST *head ,int post)
{
    gLIST *p1;          //将被删除的节点
    gLIST *p2 = head;   //  被删除的节点的上一个节点
    if ( NULL == head || post < 0 )
    {
        return NULL;
    }

    p1 = head->mnext;

    //删除头结点。若只有一个节点
    if ( 0 == post)
    {
        free(head);
        return p1;
    }

    while(post--)
    {
        //删除中间或末尾节点
        if ( 0 == post)
        {
            p2->mnext = p1->mnext;
            free(p1);
            return head;
        }

        p1 = p1->mnext;
        p2 = p2->mnext;

        //没有第post个节点
        if ( NULL == p1)
        {
            return NULL;
        }
    }
    return NULL;
}
//**************************************************************************************************
void SetVlueList( gLIST *head)
{

    //srand(time(0));

    int count = 0;
    for ( ; NULL != head ; )
    {
        head->nat = rand()%100;
        head = head->mnext;
        count++;
    }
}
//**************************************************************************************************
gLIST* bobble(gLIST *head)
{
    gLIST head0;            //放在head的前面，增加一个节点
    gLIST *p0;              //
    gLIST *p1;              //比较的第一个数
    gLIST *p2;              //比较的第二个数

    int len = 0;            //链表长度
    int j;                  //循环变量

    if (NULL == head)
    {
        return NULL;
    }

    head0.mnext = head;

    //计算链表长度
    for ( ; NULL != head ; )
    {
        head = head->mnext;
        len++;
    }

    while(1)
    {
        if ( 1 == len--)
        {   //只有一个节点了
            break;
        }

        p0 = &head0;
        p1 = p0->mnext;
        p2 = p1->mnext;

        for( j = 0 ; j < len ; j++ )
        {
            //值大向下沉
            if(p1->nat > p2->nat)
            {
                //指针交换
                p1->mnext = p2->mnext;
                p2->mnext = p1;
                p0->mnext = p2;

                head = p2;
                p2 = p1;
                p1 = head;
            }

            //下移指针
            p2 = p2->mnext;
            p1 = p1->mnext;
            p0 = p0->mnext;
        }
    }
    return head0.mnext;
}

//**************************************************************************************************
gLIST * TurnList(gLIST * head)
{
    gLIST *p1 = head;
    gLIST *p2;
    gLIST *p2back;

    if ( NULL == head)
    {
        return NULL;
    }

    p2 = p1->mnext;

    while( NULL != p2 )
    {
        p2back = p2->mnext;
        p2->mnext = p1;
        p1 = p2;
        p2 = p2back;
    }
    head->mnext = NULL;
    return p1;
}