链表

定义

• n 个节点离散分配；
• 彼此通过指针相连；
• 每个节点只有一个前驱节点，每个节点只有一个后续节点；
• 首节点没有前驱节点，尾节点没有后续节点；

专业术语

• 首节点：第一个有效节点；
• 尾结点：最后一个有效节点；
• 头节点：第一个有效节点之前的节点，头节点并不存放有效数据，加头节点的目的主要是为了方便对链表的操作。
• 头指针：指向头节点的指针变量。
• 尾指针：指向尾节点的指针变量。

如果希望通过一个函数对链表进行处理，我们至少接受链表的那些参数：

只需要一个参数：头指针。
因为我们通过头指针可以推算出链表其它所有参数。

节点的数据类型表示

struct Node {
    int data;  //数据域
    struct Node *pNext;  // 指针域
}

链表的分类

• 单链表
• 双链表：每一个节点有两个指针域；
• 循环链表：能通过任何一个节点找到其它所有节点；
• 非循环链表

算法

• 遍历
• 查找
• 清空
• 销毁
• 求长度
• 排序
• 删除节点
• 插入节点

非循环单链表插入节点

在节点 p 后面插入节点 q:

q->pNext = p->pNext;  
p->Next = q;

其中 p 和 q 存的是所在节点的地址。

非循环单链表删除节点

删除节点 p 后面插入节点 ：

r = p->pNext;  //r 指向 p 后面那个节点；
p->pNext = p->pNext->pNext;
free(r);//删除 r 指向节点所占内存，不是删除 r 本身所占内存。

创建链表

# include <stdio.h>
# include <malloc.h>  //包含 maclloc() 函数
# include <stdlib.h>  //包含 exit() 函数

typedef struct Node
{
    int data;  //数据域
    struct Node *pNext;  //指针域
}NODE,*PNODE;  //NODE 等价于 struct Node，PNODE 等价于 struct Node *

//函数声明
PNODE create_list(void);  //创建链表
void traverse_list(PNODE pHead);  //遍历链表
bool is_empty(PNODE pHead);  //判断链表是否为空
int length_list(PNODE);  //链表长度
bool insert_list(PNODE,int,int);  //插入节点
bool delete_lsit(PNODE,int,int *);  //删除节点
void sort_list(PNODE);  //排序

int main(void)
{
    PNODE pHead = NULL;  //等价于 struct Node * pHead = NULL
    int val;  //保存删除的值

    pHead = create_list();  //创建一个非循环单链表，并将该链表的头节点的地址赋给 pHead
  
    //插入节点
    insert_list(pHead,2,33);  

     //删除节点
    if(delete_list(pHead,2,&val)) 
    {
        printf("删除成功，您删除的元素是：%d\n",val)
    }
    else
    {
        printf("删除失败\n");
    }

     //遍历链表
    traverse_list(pHead); 


    return 0;
}

//创建一个非循环单链表
PNODE create_list(void)
{
    int len;  //存放有效节点的个数
    int i;
    int val; 临时存放用户输入节点的值
  
    //分配了一个不存放有效数据的头节点
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if(NULL == pHead)
    {
        printf("分配失败，程序终止！\n");
        exit(-1);
    }
    PNODE pTail = pHead;  //pTail 永远指向最后一个节点
    pTail->pNext = NULL;

    for(i = 0;i<len;++i)
    {
        printf("请输入第%d个节点的值：",i+1);
        scanf("%d",&val)

        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if(NULL == pNew)
        {
            printf("分配失败，程序终止！\n");
            exit(-1);
        }
        pNew->data = val;
        pTail-pNext = pNew;
        pNew->pNext = NULL;
        pTail = pNew;  //pTail 永远指向最后一个节点

    }

    return pHead;
}

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

    return;
}

//判断链表是否为空
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;
    while (p->Next != NUll)
    {
        ++len;
        p = p->pNext;
    }
    return len;
}

 //排序
void sort_list(PNODE pHead)
{
    int i,j,t;
    int len = length_list(pHead);
    PNODE p,q;

    for(int i = 0,p=pHead->pNext;i<len-1;++i,p = p->pNext)
    {
        for(j = j+1,q = p->pNext;j<len;++j,q=q->pNext)
        {
            if(p->pData > q->qData)   // 类似于数组中 a[i] > a[j]
            {
                t = p->data;   //类似于数组中: t = a[i]
                p->data = q->data;    //类似于数组中 a[i] = a[j]
                q->data = t;    //类似于数组中 a[j] = t
            }
        }
    }

    return;
}

//插入节点
//在 pHead 所指向链表第 pos 个节点前面插入一个新的节点，该节点的值是 val，并且 pos 的值是从 1 开始。
bool insert_list(PNODE,int pos,int val)
{
    int i  = 0;
    PNODE p  = pHead;
  
    
    while(NULL != p && i<pos - 1)
    {
        p = p->pNext;
        ++i;
    }
    
    //排除不合理的插入，例如链表长度为2，在第4个位置插入链表。
    if(i>pos -1 || NULL = p)
        return false;

    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(NULL == pNew)
    {
        printf("动态内存分配失败！\n");
        exit(-1);
    }

    pNew->data = val;
    PNODE q = p->pNext;
    p->pNext = pNew;
    pNew->pNext = q;

    return true;

}

//删除节点
bool delete_lsit(PNODE, int pos, int * pVal)
{
     int i  = 0;
    PNODE p  = pHead;
  
    //排除不合理的插入，例如链表长度为2，在第4个位置插入链表。
    while(NULL != p->Next && i<pos - 1)
    {
        p = p->pNext;
        ++i;
    }
    
    if(i>pos -1 || NULL = p->Next)
        return false;

    PNODE q = p->pNext;
    *pval = q->data;
    p->pNext = p->pNext->pNext;  //删除 p 节点后面的节点
    free(q)
    q = NULL

    return true;
}

优点：

• 空间没有限制；
• 插入删除元素很快；

缺点：

读取速度慢