数据结构——单向链表
一、数据结构：
①常用的数据存储结构
②算法
③面向对象的编程思想
什么是数据结构？
①、用来组织和存储数据
②程序 = 数据结构 + 算法
二、数据与数据之间的关系
①逻辑结构：数据元素与元素之间的关系
集合：数据元素与数据元素之间平等的集合关系
线性结构：数据元素与元素之间存在一对一的关系（如：顺序表，链表，队列、栈）
树形结构：数据元素与元素之间存在一对多的关系（如：二叉树）
图形结构：数据元素与元素之间存在多对多的关系（如：网状结构）
②物理结构：数据元素在计算机内存中的存储方式
顺序结构：在内存中选用一段连续的内存空间进行存储
Ⅰ数据访问方便（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;
}