数据结构——单向链表

一、数据结构：

①常用的数据存储结构

②算法

③面向对象的编程思想

什么是数据结构？

①、用来组织和存储数据

②程序 = 数据结构 + 算法

二、数据与数据之间的关系

①逻辑结构：数据元素与元素之间的关系

集合：数据元素与数据元素之间平等的集合关系

线性结构：数据元素与元素之间存在一对一的关系（如：顺序表，链表，队列、栈）

树形结构：数据元素与元素之间存在一对多的关系（如：二叉树）

图形结构：数据元素与元素之间存在多对多的关系（如：网状结构）

②物理结构：数据元素在计算机内存中的存储方式

顺序结构：在内存中选用一段连续的内存空间进行存储

Ⅰ数据访问方便（O(1)）

Ⅱ插入和删除数据是需要移动大量数据

Ⅲ需要预内存分配

Ⅳ可能造成大量的内存碎片

struct data
{
    char a;
    int b;
};

(原来只需char（一个字节）+ int（四个字节) 即五个字节，但在结构体中则需要八个字节进行存储）

链式结构：可以在内存中选用一段非连续的内存空间进行存储

Ⅰ数据访问时必须要从头遍历

Ⅱ插入和删除数据方便

Ⅲ不需要预内存分配，是一种动态存储方式

索引结构：将要存储的数据的关键字和存储位置之间构建构建一个索引表

散列结构（哈希结构）：将数据的存储位置与数据元素之间的关键字建立起对应的关系（哈希函数），根据该关系进行数据的存储和查找

二、单向链表

由数据域和指针域组成结点

链表：对象（存储数据的对象） ——> 属性（变量）、行为（函数）

创建的链表指针指向 phead

接下里将从创建链表对象，插入数据，删除数据，查找数据，修改数据，销毁数据介绍单向链表

①创建链表对象

先建立三个文件分别是 （link .c(用于封装函数),link.h(用于存放函数声明),main.c(创建链表，调用函数进行编译)）

在头文件中声明链表：

//链表存储的数据的数据类型
typedef int Date_type_t;

//链表节点类型
typedef struct node
{
    Date_type_t date;
    struct node *pnext;
}Node_t;

//链表的对象类型
typedef struct link
{
    Node_t *phead;
    int clen;
}Link_t;

Link_t *create_link()
{
    Link_t *plink = malloc(sizeof(Link_t));
    {
        if(NULL == plink)
        {
            printf("error!\n");
            return NULL;
        }
    }
    plink -> phead = NULL;
    plink -> clen = 0;
    return plink;
}

#include <stdio.h>
#include "link.h"

int main(int argc,const char *arvg[])
{
    Link_t *plink = create_link();
    if(NULL == plink)
    {
        return -1;
    }
}

②插入数据（需要从堆上开辟空间，即动态分配内存，调用malloc函数）

Ⅰ头插

int insert_link_head(Link_t *plink,Date_type_t date)
{
    Node_t *pnode = malloc(sizeof(Node_t));
    if(NULL == plink )
    {
        printf("error!\n");
        return -1;
    }
    pnode -> date = date;  
    pnode -> pnext = NULL;   //数据初始化
   
    pnode -> pnext = plink ->phead;
    plink -> phead = pnode;

    plink -> clen++;
    return 0;
}//头插

（先使结构体指针指向节点，在于链表产生联系）

Ⅱ 尾插

int insert_link_tail(Link_t *plink,Date_type_t data)
{
    if(plink -> phead == NULL)
    {
        return -1;
    }
    Node_t *ptmp = NULL;
    Node_t *pnode = malloc(sizeof(Node_t));
    if(pnode == NULL)
    {
        return -2;
    }
    pnode -> date = data;
    pnode -> pnext = NULL;
    if(plink -> phead == NULL)//链表为空尾插即头插
    {
       plink -> phead = pnode; 
    }
    else 
    {
        ptmp = plink -> phead; 
        while(ptmp -> pnext != NULL)//利用循环找到最后一个节点
        {
            ptmp = ptmp -> pnext;
        }
    }
    ptmp -> pnext = pnode；//找到最后一个节点插入数据
    
    plink -> clen ++;//扩展链表长度
    return 0;
}//尾插

③遍历链表

void link_for_each(Link_t *plink)
{
    Node_t *ptmp;
    ptmp = plink -> phead;
    while(ptmp != NULL)
    {
        printf("%d\n",ptmp -> date);
        ptmp = ptmp -> pnext;
    }
}

③ 删除

Ⅰ头删

int delate_link_head(Link_t *plink)
{
    Node_t *ptmp = NULL; 
    ptmp = plink-> phead;
    if(plink -> phead == NULL)
    {
        return 0;
    }
    plink -> phead = ptmp -> pnext;
    free(ptmp);
    ptmp = NULL;
    plink -> clen--;
    return 1;
}

Ⅱ尾删

int delate_link_tail(Link_t *plink)
{
    Node_t *ptmp = NULL;
    ptmp = plink -> phead;
    if(ptmp == NULL)
    {
        return -1;
    }
    if(ptmp -> pnext == NULL) //只有一个节点头删
    {
        free(ptmp);
        plink -> phead = NULL;
        plink -> clen = 0;
        return 1;
    }
    while(ptmp -> pnext -> pnext != NULL)//找倒数第二个节点
    {
        ptmp = ptmp -> pnext;
    }
    free(ptmp -> pnext);
    ptmp -> pnext = NULL;
    plink -> clen--;
    return 0;
}//尾删

④查找

Node_t *find_link(Link_t *plink,Data_type_t mydata)
{

    Node_t *ptmp;
    ptmp = plink -> phead;
    while(ptmp != NULL)
    {
        Data_type_t s;
        s = ptmp -> date;
        if(s == mydata)
        {
            break;
        }
        
        ptmp = ptmp -> pnext;
    }
    if(ptmp != NULL)
    {
        return ptmp;
    }
    return NULL; 
}

⑤修改

int change_link(Link_t *plink,Date_type_t olddata,Date_type_t newdata)
{
    Node_t *p = NULL;
    p = find_link(plink,olddata);
    if(p == NULL)
    {
        return -1;
    }
    p -> date = newdata;
    return 0;
}

⑥销毁

void destroy_link_head(Link_t *plink)
    
{
    if(plink -> phead == NULL)
    {
        return;
    }
    Node_t *ptmp = NULL;
    Node_t *pnode = NULL;
    ptmp = plink -> phead;
    while(ptmp != NULL)
    {
        pnode = ptmp -> pnext;
        free(ptmp);
        ptmp = pnode;
    }
    free(plink);
}//销毁链表

三、单向链表基础进阶

①查找中间值

int find_link_middle(Link_t *plink)//计数遍历找中间值
{
    Node_t *ptmp = NULL;
    int counter =  0;
    if(plink -> phead == NULL)
    {
        return -1;
    }
    ptmp = plink -> phead;
    while(ptmp != NULL)
    {
        ++counter;
        ptmp = ptmp -> pnext;
    }
    ptmp = plink -> phead;
    for(int i = 0;i < counter / 2; ++i)
    {
        ptmp = ptmp -> pnext;
    }
    return ptmp -> date;
}

Node_t *find_link_middle2(Link_t *plink) //快慢指针法
{
    if(plink -> phead == NULL)
    {
        return NULL;
    }
    Node_t *pfast = plink -> phead;
    Node_t *pslow = plink -> phead;
    while(pfast != NULL)
    {
        pfast = pfast -> pnext;
        if(pfast == NULL)
        {
            break;
        }
        pfast = pfast -> pnext;
        pslow = pslow -> pnext;
    }
    return pslow;
}

②查倒数第k个节点

Node_t *find_link_random(Link_t *plink,int k)
{
    if(plink -> phead == NULL)
    {
        return NULL;
    }
    
    Node_t *pfast = plink -> phead;
    for(int i = 0; i < k; ++i)
    {
        pfast = pfast -> pnext;
        if(pfast == NULL)
        {
            break;
        }
    }
    Node_t  *pslow = plink -> phead;
    while(pfast)
    {
        pfast = pfast -> pnext;
        pslow = pslow -> pnext;
    }
    return pslow;
}

③链表逆序

void reverse_link(Link_t *plink)
{
    if(plink -> phead == NULL)
    {
        return ;
    }
    Node_t *ptmp = plink -> phead;
    Node_t *pinsert = NULL;
    plink -> phead = NULL;
    while(ptmp)
    {
        pinsert = ptmp;
        ptmp = ptmp -> pnext;
        pinsert -> pnext = plink -> phead ;
        plink -> phead = pinsert;
    }
}

⑤链表排序

void sort_link(Link_t *plink)
{
    if(plink -> phead == NULL)
    {
        return ;
    }
    Node_t *ptmp = plink -> phead -> pnext;
    plink -> phead -> pnext = NULL;
    Node_t *pinsert = NULL;
    while(ptmp != NULL)
    {
        pinsert = ptmp;
        ptmp = ptmp -> pnext;
        if(plink -> phead -> date >= pinsert -> date)
        {
            pinsert -> pnext = plink -> phead;
            plink -> phead = pinsert;
        }
        else
        {
           Node_t *p = plink -> phead;
            while(p -> pnext != NULL && pinsert -> date > p -> pnext -> date)
            {
                p = p -> pnext;
            }
            pinsert -> pnext = p -> pnext;
            p -> pnext = pinsert;
        }
    }

}

⑥判断链表是否有环

Node_t *link_hascycle(Link_t *plink)
{
    if(plink -> phead == NULL)
    {
        return NULL;
    }
    Node_t *pfast = plink -> phead;
    Node_t *pslow = plink -> phead;
    while(pfast != NULL && pfast -> pnext != NULL)
    {
        pfast = pfast -> pnext -> pnext;
        pslow = pslow -> pnext;
        if(pslow == pfast)
        {
            return pslow;
        }
    }
    return NULL;
}

⑦约瑟夫环问题

Node_t *is_link_joseph(Link_t *plink,int n)
{
    if(plink -> phead == NULL)
    {
        return NULL;    
    }
    if(plink -> clen ==1)
    {
        return plink -> phead;
    }
    Node_t *pnode = NULL;
    pnode = plink -> phead;
    
    Node_t *p = NULL;
    p = plink -> phead;
    while(p -> pnext != NULL)
    {
        p = p -> pnext;
    }
    p -> pnext = plink -> phead;
    Node_t *ptmp = NULL;
    ptmp = p;
    while(plink -> clen > 1)
    {
        int i;
        for(i = 0; i < n - 1; ++i)
        {
            ptmp = pnode;
            pnode = pnode -> pnext;
        }
        ptmp -> pnext = pnode -> pnext;
        if(pnode == plink -> phead)
        {
            plink -> phead = pnode -> pnext;
        }
        Node_t *q = pnode;
        pnode = pnode -> pnext;
        free(q);
        plink -> clen--;
    }
    pnode = pnode -> pnext;
    return pnode; 
}