B站-3.单链表

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
离散存储：链表
定义：
    n个节点离散分配
    彼此通过指针相连
    每个节点只有一个前驱与后继节点 除第一个与最后一个

    专业术语：
        首节点、尾节点、头指针、尾指针、头结点
    头结点：
        没有存放数据、没有存放位数，头结点的数据类型与首节点的一样
        作用：方便对链表进行操作
    头指针：指向头结点的指针变量
    尾指针：指向头节点的指针变量
    尾节点：指针域为空

确定一个链表需要几个参数：
    只需要头指针
分类：
    单链表
    双链表：每一个节点有两个指针域
    循环链表：能通过任何一个节点能找到其他所有的节点
    非循环链表
算法：
    创建
    遍历
    查找
    清空
    销毁
    求长度
    排序
    删除节点
    插入节点
*/
typedef struct Noode
{
    int data;//数据域
    struct Node * pNext;//指针域
} NODE,*PNODE; //struct Noode，struct Noode *

PNODE create_list();//创建非循环单链表
void traverse_list(PNODE pHead);//遍历
bool is_empty(PNODE pHead);//链表是否为空
int length_list(PNODE pHead);//链表长度
bool insert_list(PNODE pHead,int pos,int val);//插入pos位节点之后(头结点为0)
bool delete_list(PNODE pHead,int pos);//删除pos节点
void sort_list(PNODE pHead);//排序

int main()
{
    PNODE pHead = NULL;
    pHead = create_list();//创建一个非循环单链表
    if(is_empty(pHead))
    {
        printf("链表为空！\n");
    }
    else
    {
        printf("链表不为空！\n");
    }
    traverse_list(pHead);
    printf("\n链表长度为:%d\n",length_list(pHead));
    printf("节点插入：\n");
    if(insert_list(pHead,3,123))
    {
        traverse_list(pHead);
    }
    else
    {
        printf("插入节点失败！\n");
    }
    sort_list(pHead);
    traverse_list(pHead);
    if(delete_list(pHead,2))
    {
        printf("删除节点成功！\n");
    }
    return 0;
}

void sort_list(PNODE pHead)
{
    PNODE p,q;
    int i,j,t;
    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;
            }
        }
    }
}

bool delete_list(PNODE pHead,int pos)
{
    int i;
    PNODE p = pHead;
    //循环到p指向pos-1的位置
    while( NULL != p->pNext && i<pos-1)
    {
        p = p->pNext;
        ++i;
    }
    if (NULL == p->pNext || i > pos -1)
    {
        return false;
    }
    PNODE q = p->pNext;
    p->pNext=q->pNext;
    free(q);
    q=NULL;
    return true;
}

bool insert_list(PNODE pHead,int pos,int val)
{
    if(is_empty(pHead)||pos<0)
    {
        return false;
    }
    else
    {
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        pNew->data=val;
        PNODE pMove = pHead;
        if(pos==0)
        {
            pNew->pNext=pMove->pNext;
            pMove->pNext=pNew;
            return true;
        }
        else if(pos<=length_list(pHead))
        {
            while(pos>0)
            {
                pos--;
                pMove = pMove->pNext;
            }
            pNew->pNext=pMove->pNext;
            pMove->pNext=pNew;
            return true;
        }
        else
        {
            return false;
        }
    }
}

int length_list(PNODE pHead)
{
    PNODE pLen = pHead->pNext;
    int sum=0;
    if(is_empty(pHead))
    {
        return 0;
    }
    else
    {
        while(pLen!=NULL)
        {
            sum++;
            pLen = pLen->pNext;
        }
        return sum;
    }
}

bool is_empty(PNODE pHead)
{
    if(pHead->pNext==NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}
PNODE create_list()
{
    int len=0;//有效节点的个数
    int i;
    int val;//用来存放用户输入的节点的值
    //1.分配了一个链表所需的头结点
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    //判断头结点是否分配了空间
    if(NULL == pHead)
    {
        printf("分配失败，程序终止!\n");
        exit(-1);
    }
    //使pTail永远指向尾节点
    PNODE pTail = pHead;
    pTail->pNext=NULL;

    //需要多少了节点
    printf("需要生成的链表节点的个数:len = ");
    scanf("%d",&len);
    //循环输入各节点的data，形成链表
    for(i=0; i<len; i++)
    {
        printf("请输入第%d个节点的值:",i+1);
        scanf("%d",&val);
        //生成一个新的节点，存放data，连接链表
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if(NULL == pNew)
        {
            printf("分配失败，程序终止!\n");
            exit(-1);
        }
        pNew->data=val;
        pTail->pNext = pNew;
        pNew->pNext=NULL;
        pTail=pNew;
    }
    return pHead;
}
void traverse_list(PNODE pHead)
{
    PNODE p = pHead->pNext;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p = p->pNext;
    }
    printf("\n");
}

```