单链表的基本操作

单链表的操作是数据结构中最基础的，每次看完就会忘，总是记个大概。总结一下：

单链表中的单位是结点，那么结点中包含数据域和指针域，指针域指向下一个结点的地址。

1、定义结点（定义结构）：

//定义结点结构
typedef struct LNode{
    int data;              //数据域
    struct LNode *next;    //指针域
}LNode,*Linklist;

2、初始化结点：

（结构定义 了，但是数据并没有装进结构，初始化就是把数据域和指针域都初始化，一般情况数据域给定数值或字符，指针域初始化为NULL，还要注意的是初始化的结点返回的都是指针）

// 初始化一个节点
Linklist initnode(int data)
{
    Linklist pnode = (Linklist)malloc(sizeof(LNode));
    pnode->data = data;    // 初始化数据域
    pnode->next = NULL;    // 初始化指针域为NULL

    return pnode;
}

3、尾插法建立链表

//创建一个链表节点(尾插法)
Linklist createlink_bytail(Linklist phead, int data)
{
    Linklist pnode = initNode(data);//初始化结点，这里注意，只要是插入元素，第一步都是要把数据初始化成结点
    Linklist ptmp = phead;          //定义一个临时指针，指向头结点

    if(NULL == phead)               //当链表为空，直接返回初始化的结点
    {              
        return pnode;
    }
    else
    {
        while(ptmp->next != NULL)  //找到最后一个结点，插在尾部
        {
            ptmp = ptmp->next;
        }
        ptmp->next = pnode;
    }
    return phead;
}
    

4、链表的长度

//求链表长度
int linklen(Linklist phead)
{
    int len = 0;            //计数器
    Linklist ptmp = phead;
    
    while(ptmp != NULL)
    {    
        len++;              //遍历链表，计数器加1,这里要注意的是和下一行不能交换位置，因为是第一个结点直接是 1 了
        ptmp = ptmp->next;
    }
    
    return len;
}

5、按位置查找

//按位置查找
int getElem(Linklist phead,int i)
{
    int e;
    Linklist ptmp = phead;
    int j = 0;
    while(ptmp != NULL && j < i)
    {
        ptmp = ptmp ->next;
        ++j;
    }
    e = ptmp ->data;
    return e;        
}

6、按位置插入

//按位置插入
//在 i 位置之前，插入元素数据 e
void insertList(Linklist phead,int i,int e)
{
    Linklist ptmp = phead;
    Linklist pnode = initNode(e);
    int j = 0;
    while(ptmp != NULL && j < i - 1)
    {
        ptmp = ptmp->next;
        ++j;
    }
    pnode->next = ptmp->next;
    ptmp->next = pnode;
}

7、按位置删除

//按位置删除
//删除第 i 个元素
void listDelete(Linklist phead,int i)
{
    Linklist ptmp = phead;
    Linklist q;
    int j = 0;
    while(ptmp != NULL && j < i - 1)// 这里注意想要删除第 i 个元素，首先要找到的是i前面的位置
    {
        ptmp = ptmp ->next;
        ++j;
    }
    q = ptmp ->next;        // 现在ptmp是要删除的结点的上一个的位置，所以要找到它的下个结点再处理
    ptmp ->next = q ->next; // 本来是想这么写，ptmp ->next = ptmp ->next ->next; 然后发现没法释放结点
    free(q);                // 如果想把这个删除的结点值返回可以在做个返回值，要在调用free()之前，e = q ->data
}

8、链表的排序（冒泡）

// 单链表的排序（冒泡排序）
//首先讲正常的一个数组冒泡排序
    const int N = 6;
    int a[N] = {4,5,1,9,7,6};
    for(int i = 0;i < N - 1;i++)
        for(int j = 0;j < N - i - 1;j++)
            if(a[j] > a[j + 1])
            {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
//链表的冒泡排序，虽然链表有两个域，但是其实只是交换数据域即可
Linklist linkSort(Linklist phead)
{
    Linklist p = phead;
    int n = linklen(phead);
    for(int i = 0;i < n - 1;i++)
    {
        p = phead; // 和普通数组做比较，第一轮比较完之后，继续从开始的两个元素开始比较，
                   // 而链表的p已经移到了最后，所以要先挪到最左再重新开始
                   // 而且这里还要看链表是否带有头结点，如果有头结点，我认为应该是 p = phead->next;
        for(int j = 0;j < n - i - 1;j++)
        {
            if(p->data > p->next->data)
            {
                int temp = p->data;
                p->data = p->next->data;
                p->next->data = temp;
            }
            p = p ->next;
        }
    }
    return phead;
}