不带头结点的单链表（增、删、查、改）

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

typedef int ElemType_t;

typedef struct Node
{
    ElemType_t data;
    struct Node* pNext;

}Node_t,*pNode_t;

/*
函数名:  create_list
函数参数：data--第一个结点的数据元素的值
函数返回值： 返回堆区创建出来的第一个结点首地址
函数作用： 创建一个只有一个结点的链表
*/
pNode_t create_list(ElemType_t data)
{
    pNode_t head = (pNode_t)malloc(sizeof(Node_t));
    if(head == NULL)
    {
        printf("malloc error.\n");
        return NULL;
    }

    //初始化
    head->data = data;
    head->pNext = NULL;

    return head;
}

/*
函数名:  insert_nodeToList_tail
函数参数：head--将结点插入到哪个链表中  data--插入结点的数据元素的值
函数返回值： void
函数作用： 在链表的尾部插入一个结点
*/
void insert_nodeToList_tail(pNode_t head,ElemType_t data)
{
    //1.创建一个新的结点
    pNode_t new = (pNode_t)malloc(sizeof(Node_t));
    if(new == NULL)
    {
        printf("malloc error.\n");
        return ;
    }
    //2.初始化
    new->pNext = NULL;
    new->data = data;
    
    //3.将指针指向最后一个结点
    pNode_t p = head;

    while(p->pNext != NULL) //相当于 p != NULL 
    {
        p = p->pNext;    
    }

    //4.将最后一个结点的pNext指向新创建出来的结点
    p->pNext = new;    
}


/*
函数名:  deleteNodeToList
函数参数：head--删除结点的链表头指针  data--删除结点的数据元素的值
函数返回值： 由于可能更改头结点的值，但head的修改无法影响实参因此需要返回head
函数作用： 头插入一个结点
*/
pNode_t insert_nodeToList_head(pNode_t head,ElemType_t data)
{
    //1.创建新结点
    pNode_t new = (pNode_t)malloc(sizeof(Node_t));
    if(new == NULL)
    {
        printf("malloc error.\n");
        return NULL;
    }
    //2.初始化新结点
    new->data = data;
    new->pNext = NULL;
    //3.新结点的pNext指向头结点
    new->pNext = head;

    //4.头结点更新指向新结点(无法影响实参，返回值来修改)
    head = new;

    return head;
}


/*
函数名:  find_nodeToList
函数参数：head--寻找数据是否存在于该链表的头指针  data--寻找结点的数据元素的值
函数返回值： 链表中有该数据返回0，寻找失败返回-1
函数作用： 查询链表中是否有相同的数据元素
*/
int find_nodeToList(pNode_t head,ElemType_t data)
{
    pNode_t p = head;

    while(p)
    {
        if(p->data == data)
            break;
        p = p->pNext;
    }

    if(p==NULL)
    {
        printf("find this data error...\n");
        return -1;
    }

    printf("find this data successful...\n");
    return 0;
}


/*
函数名:  bubbleSort_nodeToList
函数参数：head--冒泡排序的链表头结点  
函数返回值： void
函数作用： 冒泡排序
*/
void bubbleSort_nodeToList(pNode_t head)
{
    pNode_t p = head;
    int cnt = 0;

    while(p)
    {
        cnt++;
        p = p->pNext;
    }

    for(int i = 0; i <cnt-1;i++)
    {
        p = head;
        for(int j = 0; j < cnt-i-1; j++)
        {
            if(p->data > p->pNext->data)
            {
                ElemType_t temp = p->data;
                p->data = p->pNext->data;
                p->pNext->data = temp;
            }
            p = p->pNext;
        }
    }
        

}



/*
函数名:  deleteNodeToList
函数参数：head--删除结点的链表头指针  data--删除结点的数据元素的值
函数返回值： 由于可能更改头结点的值，但head的修改无法影响实参因此需要返回head
函数作用： 删除链表中数据为data的结点
*/
pNode_t deleteNodeToList(pNode_t head,ElemType_t data)
{
    pNode_t p = head;
    pNode_t pBack = NULL;

    //删除的是第一个结点，head指针被修改指向第二个结点
    while(p)
    {
        if(p->data == data)
            break;
        pBack = p;
        p = p->pNext;
    }
    if(p == NULL)
    {
        printf("can't find this data,delete error.\n");
        return head;
    }
    //删除的是第一个结点，head指针被修改指向第二个结点
    if(p == head)
    {
        head = p->pNext;
    }
    //删除的是其他结点，跳过这个结点并释放
    else
    {
        pBack->pNext = p->pNext;
    }
    free(p);
    return head;
}


/*
函数名:  insert_nodeToList_sort
函数参数：head--插入哪个链表  data--插入链表的结点数据
函数返回值： 可能会插入到最前面，需要返回head的更新值
函数作用： 在一个有序的链表中插入一个结点
*/
pNode_t insert_nodeToList_sort(pNode_t head,ElemType_t data)
{
    pNode_t p = head;
    pNode_t pBack = NULL;

    pNode_t new = (pNode_t)malloc(sizeof(Node_t));
    if(new == NULL)
    {
        printf("malloc error\n");
        return head;
    }

    new->data = data;
    new->pNext = NULL;

    while (p)
    {
        if(data < p->data)
            break;
        pBack = p;
        p = p->pNext;
    }
    
    if(p == head)
    {
        new->pNext =head;
        head = new;
    }
    else
    {
        new->pNext = pBack->pNext;
        pBack->pNext = new; 
    }
    return head;
}

/*
函数名:  change_nodeToList
函数参数：head--修改哪个链表的数据的头指针  data--原数据 changeData--修改后数据
函数返回值： 修改成功返回0，修改失败返回-1
函数作用： 修改链表中的数据
*/
int change_nodeToList(pNode_t head,ElemType_t data,ElemType_t changeData)
{
    pNode_t p = head;

    while(p)
    {
        if(p->data == data)
            break;
        p = p->pNext;
    }

    if(p == NULL)
    {
        printf("can't find this data,change error.\n");
        return -1;
    }
    p->data = changeData;
    return 0;
}

pNode_t reverse_NodeToList(pNode_t head)
{
    pNode_t p = head;
    pNode_t pBack = NULL;

    if( (p == NULL) || (p->pNext == NULL) )
        return head;

    while(p)
    {
        pBack = p->pNext;
        
        if(p == head)
        {
            p->pNext = NULL;
        }
        else
        {
            p->pNext = head;
        }
        head = p;
        p = pBack;
    }
    return head;
}

/*
函数名:  traverseList
函数参数：head--要遍历的链表的头指针
函数返回值： void
函数作用： 遍历链表
*/
void traverseList(pNode_t head)
{
    pNode_t p = head;
    while(p)
    {
        printf("node data : %d\n",p->data);
        p = p->pNext;
    }
}


int main(int argc, char **argv)
{
    pNode_t head = create_list(4); //不带头结点，第一个结点就存放有效数据

    head = insert_nodeToList_head(head,7);
    head = insert_nodeToList_head(head,2);
    head = insert_nodeToList_head(head,6);
    head = insert_nodeToList_head(head,10);

    //head = deleteNodeToList(head,2);
    //find_nodeToList(head,3);
    bubbleSort_nodeToList(head);

    head = insert_nodeToList_sort(head,1);
    change_nodeToList(head,10,200);
    head = reverse_NodeToList(head);
    traverseList(head);


    return 0;
}