欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

不带头结点的单链表(增、删、查、改)

程序员文章站 2024-03-22 15:00:04
...
#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;
}