链表操作 全

今天下午码的代码，注意，有时候有些链表需要一个链表头，而有些链表不用链表头，这样的话就需要区别对待。

#include<stdio.h>

typedef struct node{
    int data;
    struct node *next;
}node;
/**************************************
node *list_creat(void)；

创建一个新链表（包含表头）
输入的数的个数作为链表的长度的
输入的数作为链表的数据
输入0则返回
**************************************/
node *list_creat(void)
{
    node *head, *new, *p;
    int num = 0;
    int cycle = 1;
    head = (node*)malloc(sizeof(node));
    head->next = NULL;
    p = head;


    while(cycle)
    {
        printf("please enter a num\n");
        scanf("%d", &num);

        if(num != 0)
        {
            new = (node*)malloc(sizeof(node));
            p->next = new;
            new->next = NULL;
            new->data = num;
            p = new;
        }
        else
            cycle = 0;
    }

    return head;
}
/**************************************
void list_print_length(node *head)


打印节点的数据并打印链表的总长度
**************************************/
void list_print_length(node *head)
{
    node *p;
    int num = 0;
    p = head->next;//因为head只是头没有数据

    if(head->next != NULL)
    {
        while(p->next != NULL)
        {
            num++;
            printf("p->data = %d\n", p->data);
            p = p->next;
        }
        num++;
        printf("p->data = %d\n", p->data);
    }

    printf("the length of list is %d \n", num);
}
/********************************************************
node list_sort(node *head)
对链表的数据进行排序
要点:是对数据排序，指针并不动

********************************************************/
void list_sort(node *head)
{
    int i, tmp, j;
    int num = 0;

    node *p = NULL;
    p = head->next;

    while(p != NULL)
    {
        p = p->next;
        num++;
    }
    for(i = 0; i < num - 1; i++)
    {
        p = head->next;//这步很重要！
        for(j = 0; j + i < num - 1; j++)
        {
            if(p->data > p->next->data)
            {
                tmp = p->data;
                p->data = p->next->data;
                p->next->data = tmp;
            }
            p = p->next;//控制着在节点上的行走
        }
    }
}

/***************************************************************
void list_insert(node *head, int data)

插入是将数据插入到有序单链表中
***************************************************************/
void list_insert(node *head, int data)
{
    node *new, *pre , *cur;
    int num;
    new = (node*)malloc(sizeof(node));
    new->data = data;

    pre = cur = head->next;
    if(cur->data > data)
    {
        new->next = cur;
        head->next = new;
    }
    else
    {
        while((cur != NULL) && (cur->data < new->data))
        {//(cur != NULL)要放在前面，因为&&是从左至右访问，若不放在前面，则可能访问到NULL->data，出现非法访问
            pre = cur;
            cur = cur->next;
        }
        pre->next = new;
        new->next = cur;
    }
}

/*******************************************************
int node_delete(node *head, int data)

删除链表所有数据为data的节点

********************************************************/
int node_delete(node *head, int data)
{
    node *pre, *cur, *p;
    int num = 0;
    int count = 0;
    pre = head;
    p = cur = head->next;

    while(p != NULL)
    {
        num++;
        p = p->next;
    }
    if(num == 0)
        return NULL;

    while(cur != NULL)
    {
        cur = pre; //很重要
        while((cur != NULL) &&(cur->data != data))
        {
            pre = cur;
            cur = cur->next;
        }
        if((cur != NULL) && (cur->data == data))
        {
            pre->next = cur->next;
            free(cur);
            count++;
        }
    }
    if(count ==0)
        printf("cannot find the node\n");
    return 1;
}
/*******************************************************
node* list_reverse(head)

链表的逆序

********************************************************/
node* list_reverse(node *head)
{
    node *p1, *p2, *p3, *tmp;


#if 1 //1表示有链表头部的输出方法，0表示无链表头部的输出方法

    //有链表头部的写法
    tmp = p1 = head->next;
    p2 =head->next->next;
    if(head == NULL)
        return NULL;
    if(head->next == NULL || head->next->next == NULL)
        return head;

    while(p2 != NULL)
    {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }
    tmp->next = NULL;
    head->next = p1;
    return head;

#else

    //无链表头部写法
    p1 = head;
    p2 = head->next;
    if(head == NULL || head->next == NULL)
        return NULL;

    while(p2 != NULL)
    {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }

    head->next = NULL;
    head = p1;
    return head;
#endif

}

int main(int argc, char **argv)
{
    int i;
    node *head;

    head = list_creat();
/*
    printf("please enter the num you want insert!\n");
    scanf("%d", &i);
    list_insert(head, i);

    printf("please enter the num you want delete!\n");
    scanf("%d", &i);
    node_delete(head, i);
*/
//    list_sort(head);

//    list_print_length(head);

    head = list_reverse(head);
    list_print_length(head);

    while(1);
}