C语言 动态链表
欧拉恒等式 人气:0链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
结构体定义已经函数声明
节点结构体定义
typedef struct SNode{
void *pdata; //存储数据，这个数据可以是任意类型
struct SNode *next; //节点的下一个节点地址
}SNode;
typedef struct SNode* SLink; //定义一个链表
函数声明
//创建一个链表 SLink create_slink(); //初始化一个链表 void init_slink(SLink *link); //判断链表是否为空 bool is_empty(SLink link); //获得链表存储的个数 size_t size(SLink link); //插入元素 元素存储在pdata,一共size个字节 int insert(SLink link,size_t index,void *pdata,size_t size); //获得指定下标的节点元素，并且返回其地址 void *get(SLink link,size_t index); //删除一个节点 int remove_data(SLink link,size_t index); //链表逆序 SLink reverse(SLink link); //清空链表 void clear(SLink link); //销毁链表 void destroy(SLink link); //遍历链表(通过函数指针完成用户需要的要求) void foreach(SLink link,void (*func)(const void *)); //通过值查找某个节点 void *find(SLink link,void *pdata,int (*compare)(const void *,const void*)); //通过值删除所有需要删除的节点 int remove_all(SLink link,void *pdata,int (*compare)(const void *,const void *)); //链表排序，通过冒泡排序 void sort(SLink link,int (*compare)(const void *,const void *));
函数实现
创建一个链表
首先动态链表一般有一个头结点(也不是必须有，但是头结点可以让后面的算法变得简单些)，这个头结点不存储数据，只存放第一个节点(存放数据的节点，也叫作首节点)的地址，所以我们可以让节点的pdata为null。
具体实现如下:
首先我们写一个函数实现生成一个节点，这样在我们以后只要有插入节点的操作就可以用这个静态方法来实现；这个函数我们需要传数据的地址，数据的大小(这样我们才能把数据拷贝到节点里面去)，还有下一个节点的地址；
static SNode *create_node(void *pdata,size_t size,SNode *next){
SNode *node = malloc(sizeof(SNode)); //先用malloc申请一块动态内存
if(pdata == NULL){ //如果传进来的数据地址为null
node->pdata = NULL;
}else{
node->pdata = malloc(size); //否则为数据也申请一块大小为size的动态内存，
memcpy(node->pdata,pdata,size); //把pdata指向的数据通过memcpy拷贝到node->pdata里去，拷贝size个字节
}
node->next = next; //让节点指向下一个节点
return node; //返回这个节点
}
所以有了上面这个静态方法，后面的创建一个链表还是插入一个节点就变得很简单了
因为我们刚开始创建的是一个空链表，即只有一个头结点，因此不传数据
SLink create_slink(){
//return create_node(NULL,0,NULL);
SNode *head = create_node(NULL,0,NULL);
return head;
}
除了创建一个链表，我们还可以初始化一个链表，(即在其他函数里先定义一个节点)再给它初始化。
这里我们传进来一个链表的地址,链表类型为SNode *,它的地址即为SNode **类型，因为只有传递一个元素得地址，我们才能在一个函数中改变这个元素得值(函数间的传参是值赋值）。
void init_slink(SLink *link){
*link = create_node(NULL,0,NULL); //同样调用生成节点的静态方法
}
判断链表是否为空
所谓空链表就是指只有一个头结点,这个头结点并不存储数据，只是记录首节点的地址，如果这个首节点的地址为空，那么这就是一个空链表
bool is_empty(SLink link){
return link->next == NULL;
}
获得链表中节点的个数
链表中的节点是指存储了元素的节点，所以不能包含头结点，我们只需要把这个节点遍历一遍，如果某个节点的下一个地址(next)为空，那这个节点就是尾结点
}
size_t size(SLink link){
size_t cnt = 0; //用来记录节点个数
SNode *node = link->next; //从首节点开始算起
while(node != NULL){ //遍历这个链表
++cnt;
node = node->next;
}
return cnt;
}
在某个特定的位置插入一个元素
在index的位置插入一个元素，就是我们需要把index的位置变成我们新插入的节点。
在链表中插入一个节点，并不像在线性表(数组)中那么复杂，在线性表中插入一个元素我们需要把插入节点后面的元素都往后移，这样增加了很多负担，但是在链表中的插入节点(或者删除节点)，都只需要改变一下附近节点的指针指向就OK了，所以操作变得简单了很多，下面我们来详细讲解一下如何插入一个节点。
首先肯定是找到我们插入的位置
如上图所示，我们需要在下标为3的位置插入一个节点，那我们该怎么做呢?
是的我们可以想办法获得下标为2这个节点，然后断开2和3之间的连线,再把new节点插入进去
如图，我们把2节点的next指向了新插入的new节点，把new的next指向了3的节点,那2和3之间的连系就顺利成章的断掉了,那我们的插入就算完成了。
所以我们来看一下代码
首先当然是获得我们需要插入位置的前一个节点,即上图的2节点
static SNode *get_prev_node(SLink link,size_t index){ //获得前一个节点
SNode *node = link;//从头结点开始找，比如我们插入在链表首插入一个节点就是插入到头结点后面
//我们在链表尾插入一个节点就是当node->next为null的时候插入
size_t i;
for(i=0;i<index && node != NULL;i++){
node = node->next;
}
return node; //这里的返回值可能为null,比如当node为尾结点的时候,它的node->next就为null
}
插入操作
int insert(SLink link,size_t index,void *pdata,size_t size){
if(pdata == NULL){ //如果没有传进来数据，那就插入失败
return -1;
}
SNode *prev = get_prev_node(link,index);
if(prev == NULL){ //获得插入位置的前一个节点,当它为Null时也不能插入数据，
return -1;
}
SNode *node = create_node(pdata,size,prev->next); //调用生成节点的静态方法生成一个节点,
//并且传入pdata,size,如上图所示,新插入的节点的next指向的是原本前一个节点prev的next
prev->next = node; //把prev->next重新指向新插入的节点,这样插入就完成了
//完成了new节点旁边两条线的链接工作
//prev->next = create_node(pdata,size,prev->next);
return 0;
}
关于在链表首或者链表尾插入数据
这里其实很简单，就是新插入的节点的前一个节点为头结点或者尾结点的问题，大家可以自己写一下
获得指定下标的节点的元素
这个操作比较简单，只需要在满足条件下把这个下标遍历完就可以了，没有什么难点
void *get(SLink link,size_t index){
SNode *node = link->next; //这里我们不能从头结点开始遍历，因为头结点并不存储数据所以只能从首节点开始遍历
size_t i;
for(i=0;i<index && node != NULL;i++){
node = node->next;
}
if(node == NULL){
return NULL;
}
return node->pdata; //遍历完成并且返回这个数据的地址即可
}
删除一个节点
删除可以说是插入的反过来的操作
比如上图，我们需要删除3这个节点,那我们该怎么办呢？其实比插入更简单，我们只需要让2的next指向需要删除节点的next(也就是3的next)，并且把3节点给释放掉，把里面的数据也释放掉就OK了
首先我们也可以写一个静态方法来实现删除某个节点
static void remove_node(SNode *prev){ //这里的prev为需要被删除的节点的前一个节点
SNode *node = prev->next; //记录被删除的节点
SNode *next = node->next; //记录被删除的节点的下一个节点
free(node->pdata);
free(node);
prev->next = next;
}
然后删除节点的操作
int remove_data(SLink link,size_t index){
SNode *prev = get_prev_node(link,index); //获得被删除节点的前一个节点
if(link == NULL || prev == NULL || prev->next == NULL){
//如果链表不存在或者被删除节点的前一个节点不存在或者被删除的节点不存在，那就删除失败
return -1;
}
remove_node(prev);
return 0;
}
大家自己也可以写一下删除首节点或者尾结点
链表逆序
所谓链表逆序就是将链表的存储顺序反过来，
比如上图，它的逆序结果是什么呢？
我们来看一下，就是让5节点的next指向4节点,4指向3,3指向2,2指向1,1的next指向NULL，然后再把头结点指向5，就完成了逆序,如下图所示
那我们该怎么用代码实现呢？
SLink reverse(SLink link){
if(link==NULL || link->next == NULL || link->next->next == NULL){
//如果链表不存在或者只存在头结点或者只存在一个节点,那么我们就不需要进行逆序操作
return link;
}
SNode *prev = link->next;//记录第一个节点
SNode *curr = link->next->next;//记录第二个节点
SNode *next;
while(curr != NULL){ //只要当前节点不为空就继续执行下去
next = curr->next; //记录curr的下一个节点
curr->next = prev; //让指针反过来指向，即当前节点的指针指向前一个节点
prev = curr; //然后往后移
curr = next;
}
//最后还有两条线没有连上
//即以前的首节点（即上图的节点1）的next应该指向null,首节点再变为prev，即上图的节点5
link->next->next = NULL; //
link->next = prev;
return link;
}
链表的清空
清空链表只需要一个一个的遍历，把节点里的数据释放掉，再释放掉该节点
void clear(SLink link){
SNode *node = link->next; //从首节点开始遍历
while(node != NULL){
SNode *next = node->next; //记录需要被释放的节点的下一个节点
free(node->pdata);
free(node);
node = next;
}
link->next = NULL;
}
链表的销毁
这个更为简单，只需要先清空里面的节点，在把头结点释放掉即可
void destroy(SLink link){
clear(link);
free(link);
}
链表的遍历
链表的遍历也无需多说，我们只需要从首节点开始遍历，并且把节点的数据传给函数指针，这样也更加灵活，一直遍历到null为止
void foreach(SLink link,void (*func)(const void *)){
SNode *node = link->next; //从首节点开始遍历
for(;node != NULL; node = node->next){
func(node->pdata); //把节点的数据传给func这个函数，
//然后用户需要对这个数据进行什么样的处理由用户自己决定，不仅仅是局限于把这些数据给打印出来
//这样的好处是对数据的处理更加灵活了
}
}
按特定的元素查找节点
我们也是从首节点开始遍历，对首节点里的数据进行比较，如果找到相同的数据，那就返回这个数据的地址
void *find(SLink link,void *pdata,int (*compare)(const void *,const void*)){
SNode *node = link->next; //从首节点开始查找
for(;node != NULL; node = node->next){
if(compare(node->pdata,pdata)==0){ //如果该节点的数据和带查找的数据相等
return node->pdata; //那就返回这个数据的地址
}
}
return NULL; //如果没有找到就返回null
}
这里的compare也是函数指针，都是同样的道理，对于需要找什么由用户自己决定，不在局限于查找某个特定的元素
比如在一个学生信息的结构体中，我们可以按学号进行查找，也可以按姓名进行查找，也可以按年龄、班级、等等进行查找，让这些使用起来更加灵活
比如我给大家写一个查找的函数,就按学生的学号进行查找
int compare(const void* v1,const void* v2){
Stu *stu1 = (Stu *)v1;
Stu *stu2 = (Stu *)v2;
return v1->no-v2->no;
}
按某些特定的条件删除所有符合情况的节点
这个删除的操作其实和上面的删除特定下标的节点的操作大同小异，都是找到待删除节点的前一个节点，然后进行操作，这里找到后并不急于退出，而是继续往下查找，直到找完整个链表并且删除所有符合条件的节点
int remove_all(SLink link,void *pdata,int (*compare)(const void *,const void *)){
SNode *prev = link;
int cnt = 0;
while(prev->next != NULL){
if(compare(prev->next->pdata,pdata)==0){ //找到待删除节点的前一个节点
remove_node(prev); //删除该节点
cnt++; //删除的个数++
}else{
prev = prev->next; //否则没找到就是往下继续查找
}
}
return cnt>0?0:-1;
}
链表的排序
排序我这里选择冒泡排序，如果大家想看更多的排序方法也可以看我以前写的博客，我总共写了12种排序方法
这里的排序和我以前写的几乎一模一样，我就不再多说了，唯一需要讲解的还是函数指针的应用，比如我们可以选择对学生的学号进行排序，也可以对学生的姓名、成绩、身高、年龄等等都可以进行升降序的排序
void sort(SLink link,int (*compare)(const void *,const void *)){
if(link->next == NULL || link->next->next == NULL){
return;
}
size_t i;
SNode *tail = NULL;
SNode *n = link->next;
for(;n != NULL;n = n->next){
SNode *node;
bool swap = false;
for(node = link->next;node->next != tail;node = node->next){
SNode *prev = node;
SNode *next = prev->next;
if(compare(prev->pdata,next->pdata)>0){
//这里选择的排序方式或者进行排序的元素
swap(prev->pdata,next->pdata);
swap = true;
}
}
tail = node;
if(!swap){
break;
}
}
}
我再来写一个对学生的姓名按照升序进行排序的方法
int cmopare(const void *v1,const void* v2){
Stu *s1 = (Stu *)v1;
Stu *s2 = (Stu *)v2;
return strcmp(s1->name,s2->name);
}
总结
一个链表的功能的实现就这样完成了，实现的功能也比较齐全，由于存储的数据可以是任意类型的数据，可以是整型，也可以是浮点型，结构体类型等等都可以存储，并且在实现的过程中也大量用到了函数指针，这样让这些操作的适用性更加广泛，可以在许多项目中直接使用。
加载全部内容