链表基本操作

1、删除单链表节点

r = p->pNext; // p后面的结点
p->pNext = r->pNext; // 修改p的Next结点
free(r); // 释放内存

2、插入单链表结点

r = p->pNext;
p->pNext = q; // p的Next结点指向新结点q
q->pNext = r; // 新插入结点的Next结点指向r

单链表具体实现

#include <stdio.h>
#include <malloc.h>

typedef struct Node
{
    int data;
    struct Node *pNext;
}NODE, *PNODE; // NODE等价于struct Node、 PNODE等价于struct NODE *

// 函数声明
PNODE create_list(void);
// 判断链表是否为空
bool is_empty(PNODE pHead);
// 链表的长度
int length_list(PNODE);
// 遍历链表
void traverse_list(PNODE pHead);
// 在某个位置上插入结点 
bool insert_list(PNODE, int, int *);
// 删除链表
bool delete_list(PNODE, int, int *);
// 链表排序
void sort_list(PNODE);

int main(id)
{
    
    PNODE pHead = NUll;
    
    pHead = create_list();
    traverse_list(pHead);
    sort_list(pHead);
    
    return 0;
}

// 创建链表
PNODE create_list(void)
{
    int len; // 链表长度
    int i;
    int val; // 临时存放用户输入的结点的值
    
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    
    printf("请输入您需要生产的链表结点个数: len = ");
    scanf("%d",&len);
    
    for (i =0; i<len; ++i)
    {
        printf("请输入第%d个结点的值："， i+1);
        scanf("%d", &val);
        
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (NULL != pNew)
        {
            printf("分配失败，程序终止！")    
            exit(-1);
        }
        
        // 将pNew挂到链表尾部
        pNex->data = val;
        pHead->pNext = pNew;
        pNew->pNext = NULL:
    }
    
    return pHead;
    
}

// 判断链表是否为空
bool is_empty(PNODE pHead)
{
    if (NULL == pHead->pNext)
    {
        return true;  
    }else{
        return false;
    }
}

// 链表长度
int length_list(PNODE pHead)
{
    PNODE p = pHead->pNext;
    int len = 0;
    while(NULL ! = p)
    {
        ++len;
        p = p->pNext;
    }
    
    return len;
}

// 遍历
void traverse_list(PNODE pHead)
{
    PNODE p = pHead->pNext;
    while(NULL != p)
    {
        printf("%d ", p->data);
        p = p->pNext;
    }
}

// 链表排序
void sort_list(PNODE pHead)
{
    int i, j, t;
    PNODE p, q;
    int len = length_list(pHead);
    
    // 冒泡排序
    for (i=0,p=pHead->pNext; i< len - 1; ++i, p  p->pNext)
    {
        
        for(j=i+1, q=p->pNext; j < len; ++j,q=q->pNext)
        {
            // 后面的结点比前面的大，则交换位置
            if (p->data > q->data) 
            {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
    
    return;
}


// 在某个位置上插入结点 
bool insert_list(PNODE pHead, int pos, int val)
{
    int i = 0;
    PNODE p = pHead;
    
    while(NULL ! = p && i < pos -1)
    {
        p = p->pNext;
        ++i;
    }
    
    if (i > pos - 1 || NULL == p)
        return false;
    
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (NULL == pNew)
    {
        printf("动态分配内存失败！")
    }
    
    pNew->data = val;
    PNODE q = p->pNext;
    p->pNext = pNew;
    pNew->pNext = q;
    return true;
    
}

// 删除链表中某个下标的结点并返回删除元素pVal 
bool delete_list(PNODE pHead, int pos, int *pVal)
{
    int i = 0;
    PNODE p = pHead;
    
    while(NULL ! = p->pNext && i < pos -1)
    {
        p = p->pNext;
        ++i;
    }
    
    if (i > pos - 1 || NULL == p->pNext)
        return false;
    

    PNODE q = p->pNext;
    // 删除的值
    *pVal = q->data;
    
    // 删除结点后面的结点
    p->pNext = p->pNext->pNext;
    free(q);
    q = NULL:
    return true;
    
}