UNIX环境编程-数据结构部分（5）

数据结构

一、顺序存储的线性表

gcc提供了许多的宏，如printf("%d\n",__LINE__)可用于打印出程序中的行，用于测试程序是那一部分出现了问题

1.sqlist.h

#ifndef SQLIST_H_
#define SQLIST_H_

#define DATASIZE 1024
typedef int datatype;

struct node_st
{
	datatype data[DATASIZE];
	int last;
};

typedef struct node_st sqlist;


// 创建线性表
sqlist *sqlist_create();



// 插入数据
int sqlist_insert(sqlist *me,int i,datatype *data);


// 删除数据
int sqlist_delete(sqlist *me,int i);


// 销毁线性表
int sqlist_destory(sqlist *me);


//查找数据 
int sqlist_find(sqlist *me,datatype *data);


// 线性表是否为空
int sqlist_isempty(sqlist *me);

// 将线性表设置为空
int sqlist_setempty(sqlist *me);


// 线性表中有多少元素
int sqlist_getnum(sqlist *me);


// 线性表合并
int sqlist_union(sqlist *list1, sqlist *list2);

// 遍历
void sqlist_display(sqlist *me);

#endif

2.sqlist.c

#include <stdio.h>
#include <stdlib.h>
#include "sqlist.h"

// 创建线性表
sqlist *sqlist_create()
{
	// 创建一个sqlist 指针变量
	sqlist *me;
	
	me = malloc(sizeof(*me));
	
	if(me == NULL)
	{
		return NULL;
	}
	
	// 线性表创建开始的时，线性表中没有元素，因此me->last = 0或者-1
	me->last = -1;
	
	// 返回线性表地址
	return me;
	
}


// 插入数据
int sqlist_insert(sqlist *me,int i,datatype *data)
{
	// 满
	if(me->last == DATASIZE-1)
		return -1;
		
	// 非法位置
	if(i<0 || i>me->last+1)
		return -2;
		
	// 将i位置以及之后位置原来的值依次向后面移动一位
	for(int j=me->last; i<=j ; j--)
		me->data[j+1] = me->data[j];
		
	// 将i位置的值赋值为 *data
	me->data[i] = *data;
	
	// 元素个数 +1   me->last从从索引0开始，即若me->last==0代表其中有一个元素
	me->last++;
	return 0;	
}


// 删除数据
int sqlist_delete(sqlist *me,int i)
{
	if(i<0 || i>me->last)
		return -1;
		
	// 将表中数据上移，把删除位置的元素用后一个元素进行填充
	for(int j = i+1;j<=me->last;j++)
		me->data[j-1] = me->data[j];
		
	// 线性表数据-1
	me->last--;
	return 0;
}


// 销毁线性表
int sqlist_destory(sqlist *me)
{
	// 将线性表开辟的空间进行动态释放
	free(me);
	return 0;
}

//查找数据 
int sqlist_find(sqlist *me,datatype *data)
{
	if(sqlist_isempty(me) == 0)
		return -1;
	
	// 遍历线性表，找到了则返回元素下标
	for(int i = 0;i<=me->last;i++)
		if(me->data[i] == *data)
			return i;
	
	// 没有找到，则返回-2
	return -2;
}


// 线性表是否为空
int sqlist_isempty(sqlist *me)
{
	if(me->last == -1)
		return 0;
	else 
		return -1;
}


// 将线性表设置为空
int sqlist_setempty(sqlist *me)
{
	// 若之后对线性表进行插入数据就会对之前的数据进行填充覆盖
	me->last = -1;
	return 0;
}

// 线性表中有多少元素
int sqlist_getnum(sqlist *me)
{
	// me->last 代表同数组索引从0开始
	return (me->last + 1);
}


// 线性表合并
int sqlist_union(sqlist *list1, sqlist *list2)
{
	// list1 -> 12 23 34 45 56
	// list2 -> 78 89 56 23 10
	// 将list2 中的数据插入到 list1 (前提list1中不存在list2中的该元素)
	int i =0;
	while(i<=list2->last)
	{
		// 遍历list2中的元素，若此时sqlist_find为<0,则说明list1中无重复元素，则list1进行该元素的插入
		if(sqlist_find(list1,&list2->data[i]) < 0)
		{
			sqlist_insert(list1,i,&list2->data[i]);
		}
		i++;
	}
		
	
}

// 遍历
void sqlist_display(sqlist *me)
{
	// 若线性表为空
	if(me->last == -1)
		return ;
	
	// 遍历线性表进行输出
	for(int i=0; i<=me->last; i++)
	{
		printf("%d ",me->data[i]);
	}
	printf("\n");
	return;
}

3.main.c

#include <stdio.h>
#include <stdlib.h>

#include "sqlist.h"

int main()
{

	sqlist *list;
	sqlist *list1;
	
	list  = sqlist_create();
	list1 = sqlist_create();
	
	datatype arr[6] = {11,22,33,44,55,66};
	datatype arr1[6] = {77,88,99,1010,1111,2222};
	int i;
	int err;
	
	if(list == NULL)
	{
		fprintf(stderr, "sqlist_create() failed!\n");
		// 程序中止异常退出
		exit(1);
	}
	
	if(list1 == NULL)
	{
		fprintf(stderr, "sqlist_create() failed!\n");
		// 程序中止异常退出
		exit(1);
	}
	
	
	// 将创建的数组 arr 按照数组顺序插入到线性表list中
	for(i = 0;i<sizeof(arr)/sizeof(*arr);i++)
	{
		err = sqlist_insert(list,i,&arr[i]);
		if(err != 0)
		{
			// 线性表已满
			if(err == -1)
				fprintf(stderr,"the arr is full!\n");
			// 插入的位置存在问题
			else if (err == -2)
				fprintf(stderr,"the pose you want to insert is wrong!\n");
			else 
				// 其他错误
				fprintf(stderr,"ERROR!\n");
			// 程序异常，中止
			exit(1);
		}
	}
	
	// 将创建的数组 arr1 按照数组顺序插入到线性表list1中
	for(i = 0;i<sizeof(arr1)/sizeof(*arr1);i++)
	{
		err = sqlist_insert(list1,i,&arr1[i]);
		if(err != 0)
		{
			// 线性表已满
			if(err == -1)
				fprintf(stderr,"the arr is full!\n");
			// 插入的位置存在问题
			else if (err == -2)
				fprintf(stderr,"the pose you want to insert is wrong!\n");
			else 
				// 其他错误
				fprintf(stderr,"ERROR!\n");
			// 程序异常，中止
			exit(1);
		}
	}
	
	// 显示list
	sqlist_display(list);
	
	// 显示list1
	sqlist_display(list1);
	
# if 0	
	// 删除选择(索引为1)下标处的元素
	if(sqlist_delete(list,1)==-1)
		fprintf(stderr,"输入的参数出错!\n");
	
	// 输出删除相应位置的元素后的线性表
	sqlist_display(list);	
	
# endif	

	// 进行列表合并
	sqlist_union(list,list1);
	
	// 显示合并后的list
	sqlist_display(list);
	
	
	// 销毁
	sqlist_destory(list);
	sqlist_destory(list1);
	

	
	
	// 正常的退出程序
	exit(0);
}

makefile

mytool:main.o sqlist.o
	gcc main.o sqlist.o -o mytool
	
main.o:main.c
	gcc main.c -c -o main.o
	
sqlist.o:sqlist.c
	gcc sqlist.c -c -o sqlist.o
	
clean:
	rm *.o mytool -rf

makefile

OBJS = main.o sqlist.o
CC = gcc

mytool: $(OBJS)
	$(CC) $^ -o $@
	
%.o:%.c
	$(CC) $^ -c  -o $@
	
clean:
	rm *.o mytool -rf

CMakeLists.txt

cmake_minimum_required(VERSION 3.16)
project(sqlist)

# 添加可执行文件   直接编译
add_executable(1  sqlist.h  sqlist.c  main.c)

4.运行结果：

make或者cmake(对应于写了CMakeLists.txt的情况)

二、链式存储

1.单向带头链表的实现

有头链表的实现,插入元素从索引0开始

在if的判断中，若判断条件的值小于0也为True，为0的时候才为False

链表形式如图所示:

(1) list.h

#ifndef LIST_H_
#define LIST_H_

typedef int datatype;

typedef struct node_st
{
	datatype data;
	struct node_st *next;
}list;

// 创建链表
list *list_create();

// 在索引i处插入
int list_insert_at(list *,int i,datatype *);

// 按照顺序插入
int list_order_insert(list *, datatype *);

// 将索引i处的元素删除
int list_delete_at(list *,int i,datatype *);

// 将链表删除
int list_delete(list *,datatype *);

// 链表是否为空
int list_isempty(list *);


// 链表销毁
void list_destory(list *);

// 显示
void list_display(list *);

#endif

(2) list.c

#include<stdio.h>
#include <stdlib.h>
#include "list.h"

// 创建链表(带头节点的)
list *list_create()
{
	list *me;
	
	me = malloc(sizeof(*me));
	if(me==NULL)
		fprintf(stderr,"create() failed!\n");
	me->next = NULL;
	
	return me;
}

// 在索引i处插入
int list_insert_at(list *me,int i,datatype *data)
{
	int j = 0;
	// 让node 指向头节点的位置
	list *node = me;
	list *newnode;
	
	// 位置不合法
	if(i<0)
		return -1;
	
	while(j<i && node != NULL)
	{
		node = node -> next;
		j++;
	}
	
	if(node)
	{
		newnode = malloc(sizeof(*newnode));
		if(newnode == NULL)
			return -2;
		newnode->data = *data;
		newnode->next = NULL;
		
		newnode->next = node->next;
		node->next = newnode;
		return 0;
	}
	else
		return -3;
}

// 按照顺序插入(从小到大)
int list_order_insert(list *me, datatype *data)
{
	list *p = me;
	list *q;
	
	// 插入值 比前一个节点的数据大 比后一个节点数据小
	// p->next 为 真即不为空
	while(p->next && p->next->data < *data)
		p = p->next;
		
	q = malloc(sizeof(*q));
	q->next=NULL;
	// 若分配空间失败则返回-1
	if(q==NULL)
		return -1;
		
	q->data = *data;
	// 开始插入
	q->next = p->next;
	p->next = q;
	
	return 0;
}

// 将索引i处的元素删除，并且将值进行返回
int list_delete_at(list *me,int i,datatype *data)
{
	int j = 0;
	list *p = me;
	*data = -1;
	
	// 位置不合法
	if(i<0)
		return -1;
		
	while(j<i && p)
	{
		p = p->next;
		j++;
	}
	
	// 若p 不为空，则说明，此时的j==i成立，即索引i没有超过链表的长度
	if(p)
	{
		// 将需要删除的节点，用一个指针直线，便于释放
		list *q = p->next;
		// p的后继指针，指向下下个节点
		p->next = p->next->next;
		// 将需要删除的值进行存储返回
		*data = q->data;
		// 释放
		free(q);
		q = NULL;
		return 0;
	}
	// 索引i已经超过了链表长度，则找不到要删除的索引位置i
	else 
		return -2;
}

// 将链表中节点值为*data的节点删除
int list_delete(list *me,datatype *data)
{
	list *p = me;
	
	// 前提是p的后继节点不为空，指针才能后移动
	while(p->next && p->next->data!=*data)
		p = p->next;
	
	// 没有找到	
	if(p->next==NULL)
		return -1;
	// 找到了
	else 
	{
		// 将其用指针变量q去指向，这样可以将指针变量q用于释放
		list *q = p->next;
		// 将指针p的后驱指针指向下下个节点，跳过要删除的节点
		p->next = p->next->next;
		// 释放指针q
		free(q);
	}
}

// 链表是否为空
int list_isempty(list *me)
{
	if(me->next == NULL) 
	{
		// 为空
		return 0;
	}
	return 1;
}


// 链表销毁
void list_destory(list *me)
{
	list *node,*next;
	for(node = me->next;node!=NULL;node=next)
	{
		next = node -> next;
		free(node);
	}
	// 将头节点销毁
	free(me);
	return ;
}

// 显示
void list_display(list *me)
{
	// 创建一个指针，指向链表头节点的后一个节点
	list *node = me->next;
	// 判断是否为空
	if(list_isempty(me) == 0)
		return;
		
	while(node!=NULL)
	{
		printf("%d ",node->data);
		node = node -> next;
	}
	printf("\n");
	
	return;
}

(3) main.c

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

int main()
{
	list *l;
	datatype delete_value;  // 返回的删除元素
	datatype err;
	
	l = list_create();
	datatype arr[] = {11,9,8,5,2,1,22,33,44,55};
	
	if(l == NULL)
		exit(1);
	
	for(int i=0;i<sizeof(arr)/sizeof(*arr);i++)
	{
		// 插入失败得到的值都是 小于 0 则进入 if 
		if(list_order_insert(l,&arr[i]))
			// 插入失败
			exit(-1);
	}
	
	//显示
	list_display(l);
	
	int value = 22;
	// 删除节点元素
	list_delete(l,&value);
	
	// 显示
	list_display(l);
	
	// 删除
	err = list_delete_at(l,2,&delete_value);
	// 删除出错，则异常中止程序
	if(err)
		exit(-1);
	// 显示
	list_display(l);
	printf("detele:%d\n",delete_value);
	
	// 销毁
	list_destory(l);
			
}

(4) makefile

OBJS = main.o list.o
CC = gcc

mytool: $(OBJS)
	$(CC) $^ -o $@
	
%.o:%.c
	$(CC) $^ -c  -o $@
	
clean:
	rm *.o mytool -rf

运行结果：

2.二级指针

用于存储一级指针的地址

1	数据类型 ** 指针变量名 = &一级指针变量名

#include <stdio.h>
#include <stdlib.h>

int main()
{
	int age = 18;
	int *p = &age;
	int **pp = &p;

	printf("&age=%p  p=%p  *pp=%p  &p=%p pp=%p  age=%d  *p =%d  **pp=%d  &pp=%p\n",&age,p,*pp,&p,pp,age,*p,**pp,&pp);
	return 0;
}

笔误：上图的*pp为为**pp二级指针

指针*p指向age,则指针变量p存放的为整型变量age的地址，*p得到age的值。而二级指针变量pp存放的是一级指针变量p的地址，*pp得到为指针变量p内存放的值。*pp将得到age的值。

3.单向无头链表的实现

使用二级指针传参数

无头链表的实现必须使用二级指针进行传参数，进行链表的插入与删除

（1）nohead_link.h

#ifndef NOHEAD_LINK_H__
#define NOHEAD_LINK_H__

#define NAMESIZE 1024

struct score_st
{
	int id;
	char name[NAMESIZE];
	int math;
	int chinese;
};

struct node_st
{
	struct score_st data;
	struct score_st *next;
};

int list_insert(struct node_st **,struct score_st *data);
void list_show();
int list_delete(struct node_st **);
struct score_st *list_find(struct node_st *,int id);
void list_destory(struct node_st *);

#endif

（2）nohead_link.c

#include"nohead_link.h"
#include <stdlib.h>
#include <stdio.h>

// 只完成首部的插入(使用二级指针进行操作)
int list_insert(struct node_st **list,struct score_st *data)
{
	struct node_st *new;
	
	new = malloc(sizeof(*new));
	if(new == NULL)
		return -1;
		
	new->data = *data;
	new->next = *list;
	*list = new;
	
	return 0;
}


void list_show(struct node_st *list)
{
	struct node_st *cur;
	
	for(cur = list; cur != NULL; cur = cur->next)
	{
		printf("%d  %s  %d  %d\n",cur->data.id,cur->data.name,cur->data.math,cur->data.chinese);
	}	
}



// 只进行第一个节点的删除
int list_delete(struct node_st **list)
{
	struct node_st *cur;

	if(*list == NULL )
		return -1;
		
	cur = *list;
	*list  = (*list)->next;
	
	free(cur);
	
	return 0;
		
	
}


// 在链表中查找对应id的值，若找到则返回 对应id下的数据data的地址  若没有找到则返回一个NULL指针
struct score_st *list_find(struct node_st *list,int id)
{
	struct node_st *cur;
	
	for(cur = list; cur != NULL; cur = cur->next)
	{
		// 找到了对应id的元素
		if(cur->data.id == id)
			return &cur->data;
	}
	// 没有找到
	return NULL;
}


// 对链表进行销毁操作
void list_destory(struct node_st *list)
{

	struct node_st *cur;
	// 当前链表为NULL 不需要进行销毁
	if(list ==NULL)
		return ;
	
	for(cur=list;cur!=NULL;cur=list)
	{
		list  = cur->next;
		free(cur);
	}
	
}

（3）main.c

#include <stdio.h>
#include<stdlib.h>
#include "nohead_link.h"


int main()
{
	int ret;
	struct node_st *list = NULL;
	struct score_st tmp;
	for(int i = 0;i < 7;i++)
	{
		tmp.id = i;
		// io函数 在tmp.name位置  可用内存大小为NAMESIZE 写入"stu%d" 其中%d 为 i
		snprintf(tmp.name,NAMESIZE,"stu%d",i);
		tmp.math = rand() % 100;
		tmp.chinese = rand() % 100;
		
		// 插入数据
		ret = list_insert(&list,&tmp);
		if(ret != 0)
			// 异常中止
			exit(1);
	}
	
	list_show(list);
	
	struct score_st *find_data;
	int id = 8;
	find_data = list_find(list,id);
	if(find_data != NULL)
	{
		printf("the id = %d is exist!\n",id);
	}
	else
		printf("the id = %d is not exist!\n",id);
	
	// list_delete(&list);
	
	// printf("after delete:\n");
	
	// list_show(list);
	
	list_destory(list);
	
	return 0;
}

（4）makefile

OBJS = main.o nohead_link.o
CC = gcc

mytool: $(OBJS)
	$(CC) $^ -o $@
	
%.o:%.c
	$(CC) $^ -c  -o $@
	
clean:
	rm *.o mytool -rf

运行结果:

4.约瑟夫算法

使用无头环路链表进行实现

约瑟夫问题：n个人围成一圈，初始编号从1~n排列，从约定编号为x的人开始报数，数到第m个人出圈，接着又从1开始报数，报到第m个数的人又退出圈，以此类推，最后圈内只剩下一个人，这个人就是赢家，求出赢家的编号。

问题定义：

// 环路链表的长度
#define JOSE_NUM 10
// 数到 m 则出局
#define m 3

mian.c

#include <stdio.h>
#include <stdlib.h>

// 环路链表的长度
#define JOSE_NUM 10
// 数到NUM则出局
#define m 3

struct node_st
{
	int data;
	struct node_st *next;
};

// 创建链表(环)
struct node_st *jose_create(int num)
{
	int i = 1;
	// 创建第一个节点使其自己指向自己
	struct node_st *me;
	me = malloc(sizeof(*me));
	if(me == NULL )
		return NULL;
	me->data = i;
	me->next = me;
	i++;
	
	// flag节点用于保存指向首节点的节点位置
	struct node_st *flag = me;
	for(;i<=num;i++)
	{
		// 创建新的节点然后插入之前的约瑟夫环
		struct node_st *new;
		new = malloc(sizeof(*new));
		// 若申请失败了 返回 NULL
		if(new == NULL)
			return NULL;
		new->data = i;
		
		// 插入工作
		// 新建的节点指向首节点
		new -> next = me;
		// 原来环路的最后一个节点指向新节点
		flag -> next  = new;
		// 重新定义新环路最后一个节点
		flag = new;
	}
	// 返回环路的首节点
	return me;
}

// 数到数字为n的人则出局
// 出局的节点则在环路中进行该节点的delete操作
// 在delete之前会将需要删除节点的data进行printf
void jose_kill(struct node_st **me,int n)
{
	struct node_st *cur = *me;
	struct node_st *node;
	int flag = 1;
	
	// 当链表中只剩下一个节点时，则停止while循环
	while(cur != cur->next)
	{
		// 当flag数到n-1时，cur指针已经指向了需要出局的节点
		while(flag < n)
		{
			node = cur;
			cur = cur -> next;
			flag++;
		}
		
		// 将需要删除节点的data进行打印
		printf("%d ",cur->data);
		// 对cur节点进行delete操作
		node->next = cur->next;
		free(cur);
		
		// 进行后一轮数数
		cur = node->next;
		flag = 1;
	}
	// 环路中还剩下最后一个节点不会进行delete
	// 此时 cur指向 最后一个节点
	*me = cur; // 此时的环路为只剩下一个节点的环路
	printf("\n");
}


// 输出环路元素
void jose_show(struct node_st *me)
{
	struct node_st *cur;
	// 这个循环会少输出最后一个节点元素
	for(cur=me;cur->next!=me;cur=cur->next)
	{	
		printf("%d ",cur->data);
	}
	printf("%d \n",cur->data);
}

int main()
{
	struct node_st *list;
	
	// 将约瑟夫环的第一个位置的地址返回
	list = jose_create(JOSE_NUM);
	if(list == NULL)
		exit(1);
	// 显示
	jose_show(list);
	
	// 进行约瑟夫循环
	jose_kill(&list,m);
	
	// 显示最后一个节点
	jose_show(list);
	
	
	exit(0);
}

代码解析：

struct node_st
{
	int data;
	struct node_st *next;
};

链表中每个节点的结构如上的结构体

（1）`jose_create()` 创建无头的环路链表

struct node_st *jose_create(int num)
{
	int i = 1;
	// 创建第一个节点使其自己指向自己
	struct node_st *me;
	me = malloc(sizeof(*me));
	if(me == NULL )
		return NULL;  
	me->data = i;
	me->next = me;
	i++;
	
	// flag节点用于保存指向首节点的节点位置(环路中最后一个插入进来节点的位置)
	struct node_st *flag = me;
	for(;i<=num;i++)
	{
		// 创建新的节点然后插入之前的约瑟夫环
		struct node_st *new;
		new = malloc(sizeof(*new));
		// 若申请失败了 返回 NULL
		if(new == NULL)
			return NULL;
        
		new->data = i;
		
		// 插入工作
		// 新建的节点指向首节点
		new -> next = me;
		// 原来环路的最后一个节点指向新节点
		flag -> next  = new;
		// 重新定义新环路最后一个节点
		flag = new;
	}
	// 返回环路的首节点
	return me;
}

解析：

（2）`jose_kill()` 数数到n的人出局

// 数到数字为n的人则出局
// 出局的节点则在环路中进行该节点的delete操作
// 在delete之前会将需要删除节点的data进行printf
void jose_kill(struct node_st **me,int n)
{
	struct node_st *cur = *me;
	struct node_st *node;
	int flag = 1;
	
	// 当链表中只剩下一个节点时，则停止while循环
	while(cur != cur->next)
	{
		// 当flag数到n-1时，cur指针已经指向了需要出局的节点
		while(flag < n)
		{
			node = cur;
			cur = cur -> next;
			flag++;
		}
		
		// 将需要删除节点的data进行打印
		printf("%d ",cur->data);
		// 对cur节点进行delete操作
		node->next = cur->next;
		free(cur);
		
		// 进行后一轮数数
		cur = node->next;
		flag = 1;
	}
	// 环路中还剩下最后一个节点不会进行delete
	// 此时 cur指向 最后一个节点
	*me = cur; // 此时的环路为只剩下一个节点的环路
	printf("\n");
}

解析：

5.双向循环链表

io函数在tmp.name位置可用内存大小为NAMESIZE 写入"stu%d" 其中%d 为 i

1	snprintf(tmp.name,NAME_SIZE,"std%d",i);

memcpy()

从存储区 str2 复制 n 个字节到存储区 str1

1 2	#include <string.h> void memcpy(void str1, const void *str2, size_t n)

typedef

1 2	// llist_op 被定义为返回值为void 类型参数为 const void 的函数 typedef void llist_op(const void );

项目结构目录:

$ tree
.
├── bin
│   └── doubleLinklist
├── build
├── CMakeLists.txt
├── include
│   └── llist.h
├── lib
│   └── libd_link.so
├── main.c
└── src
    └── llist.c

（1）llist.h

#pragma once

// 插入模式的宏定义
#define LLIST_FORWARD 1
#define LLIST_BACKWARD 2

// llist_op 被定义为 返回值为void 类型 参数为 const void *的函数
typedef void llist_op(const void *);
typedef int llist_cmp(const void*, const void*);

// 一般节点
struct llist_node_st{
    struct llist_node_st *pre;  // 四个字节
    struct llist_node_st *next; // 四个字节
    void *data;
};

// 头节点
typedef struct{
    int size;
    // 此处的head 只是一个结构体对象，不是指针
    struct llist_node_st head;
}LLIST;



LLIST * llist_create(int initsize);

int llist_insert(LLIST *,const void *data, int mode);

void* llistt_find(LLIST *ptr,const void *key,llist_cmp *);

int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp);

int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp,void *data);

void llist_travel(LLIST *,llist_op *);

int llist_destory(LLIST * list_head);

注意：

const void *a定义一个指针a,a可以指向任意类型的值，且它指向的值必须是常量。在这种情况下，我们不能修改被指向的对象，但可以使指针指向其他对象。
void* const a定义了一个const指针a，a可以指向任意类型的值，但a是指向某个对象的常量指针。我们不能修改指针中存储的地址，但可以修改指针指向的对象。

const void *a；中const修饰的是*a。在void* const a中，const 修饰的是a

（2）llist.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "../include/llist.h"

/*
 * function: 创建链表
 * parameter:
 *          init_size: 节点的data内存大小
 * */
LLIST * llist_create(int init_size)
{
    LLIST *new;

    new = malloc(sizeof(*new));
    if(new==NULL)
    {
        return NULL;
    }

    // 头节点不存储数据
    new->size = init_size;
    new->head.data=NULL;
    new->head.pre = &new->head;
    new->head.next = &new->head;

    return new;
}


/*
 * function: 节点数据的插入
 * parameter:
 *          ptr:链表头节点
 *          data:插入的数据，传入数据的地址
 *          mode:选择插入模式(首部or尾部)
 * return:
 *          是否插入成功
 * */
int llist_insert(LLIST *ptr,const void *data, int mode)
{
    struct llist_node_st *new_node;

    new_node = malloc(sizeof(*new_node));
    if(new_node == NULL)
        return -1;

    new_node->data = malloc(ptr->size);
    if(new_node->data == NULL)
        return -2;
    // 将存储区 data 复制ptr_size个字节数据到存储区 new_node->data
    memcpy(new_node->data, data, ptr->size);

    if(mode == LLIST_FORWARD){
        // 首部插入
        new_node->pre = &(ptr->head);
        new_node->next = ptr->head.next;
        new_node->pre->next = new_node;
        new_node->next->pre = new_node;

    }else if(mode == LLIST_BACKWARD){
        // 尾部插入
        new_node->pre = ptr->head.pre;
        new_node->next = &(ptr->head);
        new_node->pre->next = new_node;
        new_node->next->pre = new_node;
    } else{
        //ERROR
        return -3;
    }
    return 0;
}


/**
* 当前函数使用static修饰，只在当前c文件可见（作用范围）
*/
static struct llist_node_st *find_(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *cur;

    for(cur = ptr->head.next; cur != &(ptr->head); cur = cur->next)
    {
        if(cmp(key,cur->data) == 0)
        {
            break;
        }
    }
    // 返回该节点 ，若最后没有找到 cur 当前为ptr->head,head.data==NULL
    return cur;
}

/*
 * function: 在链表中根据 key 进行查找节点
 * parameter:
 *          ptr:链表头节点
 *          key:链表中查找的key  可以是id 也可以是 name 等，但是要与对应的cmp函数匹配
 *          cmp:比较函数（若为id查找，则在当前迭代的节点中的id 与key相同时，就返回当前节点中的data域）
 * */
void* llistt_find(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    // 将该节点中的data域取出
    return find_(ptr,key,cmp)->data;
}

/*
 * function: 删除链表中的节点
 * */
int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *node;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return -1;
    node -> pre ->next = node->next;
    node->next->pre = node->pre;
    // 在llist_insert()函数中 对new_node以及new_node->data都使用了动态内存的开辟
    free(node->data);
    free(node);
    return 0;
}

/*
 * function: 在链表中按照key进行查找，并且返回删除的节点数据
 * */
int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp,void *data)
{
    struct llist_node_st *node;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return -1;
    node -> pre ->next = node->next;
    node->next->pre = node->pre;

    // 若给的data指针为NULL，则表示不需要进行data回填
    if(data!=NULL)
        memcpy(data,node->data,ptr->size);
    free(node->data);
    free(node);
    return 0;
}


/*
 * function: 遍历链表
 * Note:此处用回调函数(函数指针)实现一个通用型的接口(并不清楚用户定义的数据类型的内部结构)
 * parameter:
 *          ptr: 链表头节点
 *          llist_op *: 函数指针，指向一个函数，当运行到该段代码时，则运行该函数
 * */
void llist_travel(LLIST *ptr,llist_op *op)
{
    struct llist_node_st *cur;

    for(cur = ptr->head.next; cur != &(ptr->head); cur = cur->next)
    {
        // 调用回调函数
        op(cur->data);
    }
}


int llist_destory(LLIST * ptr)
{
    struct llist_node_st *cur,*next;

    for (cur = ptr->head.next; cur != &(ptr->head); cur = next)
    {
        next = cur->next;
        free(cur->data);
        free(cur);
    }
    // 头节点destory
    free(ptr);
}

static修饰函数:函数的返回类型前加上关键字static，函数就被定义成为静态函数.函数的定义和声明默认情况下是extern的，但静态函数只是在声明他的文件当中可见，不能被其他文件所用

（3）main.c

#include <stdio.h>
#include <stdlib.h>
#include "include/llist.h"
#include "string.h"

#define NAME_SIZE 32

// 用户自定义的结构体数据类型
struct score_st{
    int id;
    char name[NAME_SIZE];
    int math;
    int chinese;
};

// 回调函数，用户根据自己定义的数据类型进行函数功能定义
static void print_s(const void *record)
{
    const struct score_st *r = record;
    printf("%d %s %d %d \n",r->id,r->name,r->math,r->chinese);
}

// 按照id 相等则查找成功
static int id_cmp(const void *key,const void *record)
{
    const int *k = key;
    const struct score_st *r = record;

    return (*k - r->id);
}

static int name_cmp(const void *key,const void *record)
{
    const char *k = key;
    const struct score_st *r = record;

    return strcmp(k,r->name);
}

int main() {

    // 创建链表
    LLIST *handler;
    if(handler == NULL)
        // 结束当前进程
        exit(1);
    handler = llist_create(sizeof(struct score_st));

    // 创建插入数据
    struct score_st tmp;
    for (int i = 0; i < 7; i++) {
        tmp.id = i;
        snprintf(tmp.name,NAME_SIZE,"std%d",i);
        tmp.math = rand()%100;
        tmp.chinese = rand()%100;

        int ret = llist_insert(handler,&tmp,LLIST_FORWARD);
        if(ret)
            // ERROR 不为0  结束当前进程
            exit(1);
    }


    llist_travel(handler,print_s);

    printf("\n\n");

    int id_delete = 3;
    int ret = llist_delete(handler,&id_delete, id_cmp);
    if(ret)
        printf("delete failed!\n");

    llist_travel(handler,print_s);

    printf("\n\n");
    // 查找id为3
    int id = 4;
    struct  score_st *data;
    data = llistt_find(handler,&id,id_cmp);
    if(data == NULL)
        printf("Can not find!\n");
    else
        print_s(data);


    llist_destory(handler);


    return 0;
}

（4）CMakeLists.txt

cmake_minimum_required(VERSION 3.20)
project(doubleLinklist C)

# 设置编译标准
set(CMAKE_C_STANDARD 99)

# 定义可执行文件的输出路径
set(HOME ${PROJECT_SOURCE_DIR}/bin)

# 指定可执行文件的输出路径
set(EXECUTABLE_OUTPUT_PATH ${HOME})

# 包含头文件
include_directories(${PROJECT_SOURCE_DIR}/include)

# 搜索 src 目录下的源文件,并且存储值SRC_LIST中(数组)
file(GLOB SRC_LIST ${CMAKE_CURRENT_SOURCE_DIR}/src/*.c)

# 设置动态(静态)库生成路径
set(LIBRARY_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/lib)
datatype
# 生成动态库
add_library(d_link SHARED ${SRC_LIST})

# 生成可执行文件
add_executable(doubleLinklist main.c)

# 链接库
target_link_libraries(doubleLinklist d_link)

（5）运行结果

6 std6 90 59 
5 std5 62 27 
4 std4 49 21 
3 std3 86 92 
2 std2 93 35 
1 std1 77 15 
0 std0 83 86 


6 std6 90 59 
5 std5 62 27 
4 std4 49 21 
2 std2 93 35 
1 std1 77 15 
0 std0 83 86 


4 std4 49 21

重点: 当前的程序llist.h中，每一个一般节点中均存在一个指向数据域的指针*data,用户可以在main.c中对data指针所指向的数据类型进行自主的定义，但是在一般节点中，void *data指针实际也是占用了四个字节的内存，如何避免这多余的四个字节的内存的浪费？下面的第6节进行解答

6.双向循环链表(一般节点的变长结构体实现)

在第5小节中，llist.h中的双向环链中一般节点struct llist_node_st中的void *data指针不是必要的，可以进行变化，将整个struct llist_node_st变为一个变长的数据结构体

c99标准才支持长度为0的数组

将上述的struct llist_node_st变为一个变长的数据结构体

// 一般节点
struct llist_node_st{
    struct llist_node_st *pre; // 四字节
    struct llist_node_st *next;// 四字节
    char data[0];   // 这是一地址的占位符
};

将第5小节代码中的free(cur->data)进行注释，因为这不是一个动态开辟的内存了，是一个数组

将llist_inseert.c中的new_node->data = malloc(ptr->size)注释

（1）llist.h

#pragma once

// 插入模式的宏定义
#define LLIST_FORWARD 1
#define LLIST_BACKWARD 2

// llist_op 被定义为 返回值为void 类型 参数为 const void *的函数
typedef void llist_op(const void *);
typedef int llist_cmp(const void*, const void*);

// 一般节点
struct llist_node_st{
    struct llist_node_st *pre;
    struct llist_node_st *next;
    char data[0];
};

// 头节点
typedef struct{
    int size;
    // 此处的head 只是一个结构体对象，不是指针
    struct llist_node_st head;
}LLIST;


LLIST * llist_create(int initsize);

int llist_insert(LLIST *,const void *data, int mode);

void* llist_find(LLIST *ptr,const void *key,llist_cmp *);

int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp);

int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp,void *data);

void llist_travel(LLIST *,llist_op *);

int llist_destory(LLIST * list_head);

（2）llist.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "../include/llist.h"

/*
 * function: 创建链表
 * parameter:
 *          init_size: 节点的data内存大小
 * */
LLIST * llist_create(int init_size)
{
    LLIST *new;

    new = malloc(sizeof(*new));
    if(new==NULL)
    {
        return NULL;
    }

    // 头节点不存储数据/
    new->size = init_size;
    // new->head.data=NULL;
    new->head.pre = &new->head;
    new->head.next = &new->head;

    return new;
}


/*
 * function: 节点数据的插入
 * parameter:
 *          ptr:链表头节点
 *          data:插入的数据，传入数据的地址
 *          mode:选择插入模式(首部or尾部)
 * return:
 *          是否插入成功
 * */
int llist_insert(LLIST *ptr,const void *data, int mode)
{
    struct llist_node_st *new_node;

    new_node = malloc(sizeof(*new_node) + ptr->size);
    if(new_node == NULL)
        return -1;

    // new_node->data = malloc(ptr->size);
    if(new_node->data == NULL)
        return -2;
    // 将存储区 data 复制ptr_size个字节数据到存储区 new_node->data
    memcpy(new_node->data, data, ptr->size);

    if(mode == LLIST_FORWARD){
        // 首部插入
        new_node->pre = &(ptr->head);
        new_node->next = ptr->head.next;
        new_node->pre->next = new_node;
        new_node->next->pre = new_node;

    }else if(mode == LLIST_BACKWARD){
        // 尾部插入
        new_node->pre = ptr->head.pre;
        new_node->next = &(ptr->head);
        new_node->pre->next = new_node;
        new_node->next->pre = new_node;
    } else{
        //ERROR
        return -3;
    }
    return 0;
}


static struct llist_node_st *find_(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *cur;

    for(cur = ptr->head.next; cur != &(ptr->head); cur = cur->next)
    {
        if(cmp(key,cur->data) == 0)
        {
            break;
        }
    }
    // 返回该节点 ，若最后没有找到 cur 当前为ptr->head,head.data==NULL
    return cur;
}

/*
 * function: 在链表中根据 key 进行查找节点
 * parameter:
 *          ptr:链表头节点
 *          key:链表中查找的key  可以是id 也可以是 name 等，但是要与对应的cmp函数匹配
 *          cmp:比较函数（若为id查找，则在当前迭代的节点中的id 与key相同时，就返回当前节点中的data域）
 * */
void* llistt_find(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *node;
    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return NULL;
    // 将该节点中的data域取出
    return node->data;
}

/*
 * function: 删除链表中的节点
 * */
int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *node;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return -1;
    node -> pre ->next = node->next;
    node->next->pre = node->pre;
    // free(node->data);
    free(node);
    return 0;
}

/*
 * function: 在链表中按照key进行查找，并且返回删除的节点数据
 * */
int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp,void *data)
{
    struct llist_node_st *node;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return -1;
    node -> pre ->next = node->next;
    node->next->pre = node->pre;

    // 若给的data指针为NULL，则表示不需要进行data回填
    if(data!=NULL)
        memcpy(data,node->data,ptr->size);
    // free(node->data);
    free(node);
    return 0;
}


/*
 * function: 遍历链表
 * Note:此处用回调函数(函数指针)实现一个通用型的接口(并不清楚用户定义的数据类型的内部结构)
 * parameter:
 *          ptr: 链表头节点
 *          llist_op *: 函数指针，指向一个函数，当运行到该段代码时，则运行该函数
 * */
void llist_travel(LLIST *ptr,llist_op *op)
{
    struct llist_node_st *cur;

    for(cur = ptr->head.next; cur != &(ptr->head); cur = cur->next)
    {
        // 调用回调函数
        op(cur->data);
    }
}


int llist_destory(LLIST * ptr)
{
    struct llist_node_st *cur,*next;

    for (cur = ptr->head.next; cur != &(ptr->head); cur = next)
    {
        next = cur->next;
        // free(cur->data);
        free(cur);
    }
    // 头节点destory
    free(ptr);
}

（3）main.c

#include <stdio.h>
#include <stdlib.h>
#include "include/llist.h"
#include "string.h"

#define NAME_SIZE 32

// 用户自定义的结构体数据类型
struct score_st{
    int id;
    char name[NAME_SIZE];
    int math;
    int chinese;
};

// 回调函数，用户根据自己定义的数据类型进行函数功能定义
static void print_s(const void *record)
{
    const struct score_st *r = record;
    printf("%d %s %d %d \n",r->id,r->name,r->math,r->chinese);
}

// 按照id 相等则查找成功
static int id_cmp(const void *key,const void *record)
{
    const int *k = key;
    const struct score_st *r = record;

    return (*k - r->id);
}

static int name_cmp(const void *key,const void *record)
{
    const char *k = key;
    const struct score_st *r = record;

    return strcmp(k,r->name);
}

int main() {

    // 创建链表
    LLIST *handler;
    if(handler == NULL)
        // 结束当前进程
        exit(1);
    handler = llist_create(sizeof(struct score_st));

    // 创建插入数据
    struct score_st tmp;
    for (int i = 0; i < 7; i++) {
        tmp.id = i;
        snprintf(tmp.name,NAME_SIZE,"std%d",i);
        tmp.math = rand()%100;
        tmp.chinese = rand()%100;

        int ret = llist_insert(handler,&tmp,LLIST_FORWARD);
        if(ret)
            // ERROR 不为0  结束当前进程
            exit(1);
    }


    llist_travel(handler,print_s);

    printf("\n\n");

    int id_delete = 3;
    int ret = llist_delete(handler,&id_delete, id_cmp);
    if(ret)
        printf("delete failed!\n");

    llist_travel(handler,print_s);

    printf("\n\n");
    // 查找id为3
    int id = 4;
    struct  score_st *data;
    data = llistt_find(handler,&id,id_cmp);
    if(data == NULL)
        printf("Can not find!\n");
    else
        print_s(data);


    llist_destory(handler);


    return 0;
}

7.双向循环链表(封装为类)

（1）llist.h

#pragma once

// 插入模式的宏定义
#define LLIST_FORWARD 1
#define LLIST_BACKWARD 2

// llist_op 被定义为 返回值为void 类型 参数为 const void *的函数
typedef void llist_op(const void *);
typedef int llist_cmp(const void*, const void*);

// 一般节点
struct llist_node_st{
    struct llist_node_st *pre;
    struct llist_node_st *next;
    char data[0];
};

// 头节点
typedef struct llist_head{
    int size;
    // 此处的head 只是一个结构体对象，不是指针
    struct llist_node_st head;
    // 定义函数指针
    int (*insert)(struct llist_head *,const void *,int);
    void * (*find)(struct llist_head *ptr,const void *key,llist_cmp *);
    int (*delete)(struct llist_head *ptr,const void *key,llist_cmp *cmp);
    int (*fetch)(struct llist_head *ptr,const void *key,llist_cmp *cmp,void *data);
    void (*travel)(struct llist_head *,llist_op *);
    int (*destory)(struct llist_head * list_head);
}LLIST;


LLIST * llist_create(int initsize);

（2）llist.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "../include/llist.h"

int llist_insert(LLIST *,const void *data, int mode);
void *llistt_find(LLIST *ptr,const void *key,llist_cmp *);
int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp);
int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp,void *data);
void llist_travel(LLIST *,llist_op *);
int llist_destory(LLIST * list_head);

/*
 * function: 创建链表
 * parameter:
 *          init_size: 节点的data内存大小
 * */
LLIST * llist_create(int init_size)
{
    LLIST *new;

    new = malloc(sizeof(*new));
    if(new==NULL)
    {
        return NULL;
    }

    // 头节点不存储数据/
    new->size = init_size;
    // new->head.data=NULL;
    new->head.pre = &new->head;
    new->head.next = &new->head;

    new->insert = llist_insert;
    new->find = llistt_find;
    new->delete = llist_delete;
    new->fetch = llist_fetch;
    new->travel = llist_travel;
    new->destory = llist_destory;

    return new;
}


/*
 * function: 节点数据的插入
 * parameter:
 *          ptr:链表头节点
 *          data:插入的数据，传入数据的地址
 *          mode:选择插入模式(首部or尾部)
 * return:
 *          是否插入成功
 * */
int llist_insert(LLIST *ptr,const void *data, int mode)
{
    struct llist_node_st *new_node;

    new_node = malloc(sizeof(*new_node) + ptr->size);
    if(new_node == NULL)
        return -1;

    // new_node->data = malloc(ptr->size);
    if(new_node->data == NULL)
        return -2;
    // 将存储区 data 复制ptr_size个字节数据到存储区 new_node->data
    memcpy(new_node->data, data, ptr->size);

    if(mode == LLIST_FORWARD){
        // 首部插入
        new_node->pre = &(ptr->head);
        new_node->next = ptr->head.next;
        new_node->pre->next = new_node;
        new_node->next->pre = new_node;

    }else if(mode == LLIST_BACKWARD){
        // 尾部插入
        new_node->pre = ptr->head.pre;
        new_node->next = &(ptr->head);
        new_node->pre->next = new_node;
        new_node->next->pre = new_node;
    } else{
        //ERROR
        return -3;
    }
    return 0;
}


static struct llist_node_st *find_(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *cur;

    for(cur = ptr->head.next; cur != &(ptr->head); cur = cur->next)
    {
        if(cmp(key,cur->data) == 0)
        {
            break;
        }
    }
    // 返回该节点 ，若最后没有找到 cur 当前为ptr->head,head.data==NULL
    return cur;
}

/*
 * function: 在链表中根据 key 进行查找节点
 * parameter:
 *          ptr:链表头节点
 *          key:链表中查找的key  可以是id 也可以是 name 等，但是要与对应的cmp函数匹配
 *          cmp:比较函数（若为id查找，则在当前迭代的节点中的id 与key相同时，就返回当前节点中的data域）
 * */
void* llistt_find(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *node;
    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return NULL;
    // 将该节点中的data域取出
    return node->data;
}

/*
 * function: 删除链表中的节点
 * */
int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *node;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return -1;
    node -> pre ->next = node->next;
    node->next->pre = node->pre;
    // free(node->data);
    free(node);
    return 0;
}

/*
 * function: 在链表中按照key进行查找，并且返回删除的节点数据
 * */
int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp,void *data)
{
    struct llist_node_st *node;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return -1;
    node -> pre ->next = node->next;
    node->next->pre = node->pre;

    // 若给的data指针为NULL，则表示不需要进行data回填
    if(data!=NULL)
        memcpy(data,node->data,ptr->size);
    // free(node->data);
    free(node);
    return 0;
}


/*
 * function: 遍历链表
 * Note:此处用回调函数(函数指针)实现一个通用型的接口(并不清楚用户定义的数据类型的内部结构)
 * parameter:
 *          ptr: 链表头节点
 *          llist_op *: 函数指针，指向一个函数，当运行到该段代码时，则运行该函数
 * */
void llist_travel(LLIST *ptr,llist_op *op)
{
    struct llist_node_st *cur;

    for(cur = ptr->head.next; cur != &(ptr->head); cur = cur->next)
    {
        // 调用回调函数
        op(cur->data);
    }
}


int llist_destory(LLIST * ptr)
{
    struct llist_node_st *cur,*next;

    for (cur = ptr->head.next; cur != &(ptr->head); cur = next)
    {
        next = cur->next;
        // free(cur->data);
        free(cur);
    }
    // 头节点destory
    free(ptr);
}

（3）main.c

#include <stdio.h>
#include <stdlib.h>
#include "include/llist.h"
#include "string.h"

#define NAME_SIZE 32

// 用户自定义的结构体数据类型
struct score_st{
    int id;
    char name[NAME_SIZE];
    int math;
    int chinese;
};

// 回调函数，用户根据自己定义的数据类型进行函数功能定义
static void print_s(const void *record)
{
    const struct score_st *r = record;
    printf("%d %s %d %d \n",r->id,r->name,r->math,r->chinese);
}

// 按照id 相等则查找成功
static int id_cmp(const void *key,const void *record)
{
    const int *k = key;
    const struct score_st *r = record;

    return (*k - r->id);
}

static int name_cmp(const void *key,const void *record)
{
    const char *k = key;
    const struct score_st *r = record;

    return strcmp(k,r->name);
}

int main() {

    // 创建链表
    LLIST *handler;
    if(handler == NULL)
        // 结束当前进程
        exit(1);
    handler = llist_create(sizeof(struct score_st));

    // 创建插入数据
    struct score_st tmp;
    for (int i = 0; i < 7; i++) {
        tmp.id = i;
        snprintf(tmp.name,NAME_SIZE,"std%d",i);
        tmp.math = rand()%100;
        tmp.chinese = rand()%100;

        int ret = handler->insert(handler,&tmp,LLIST_FORWARD);
        if(ret)
            // ERROR 不为0  结束当前进程
            exit(1);
    }


    handler->travel(handler,print_s);

    printf("\n\n");

    int id_delete = 3;
    int ret = handler->delete(handler,&id_delete, id_cmp);
    if(ret)
        printf("delete failed!\n");

    handler->travel(handler,print_s);

    printf("\n\n");
    // 查找id为3
    int id = 4;
    struct  score_st *data;
    data = handler->find(handler,&id,id_cmp);
    if(data == NULL)
        printf("Can not find!\n");
    else
        print_s(data);


    handler->destory(handler);


    return 0;
}

8.双向循环链表(封装为类-将来使用`llist.c`作为动态库使用)

将真正的数据结构进行隐藏，之后直接可以链接llist.c动态库使用其函数，更加保护源码

（1）llist.h

#pragma once

// 插入模式的宏定义
#define LLIST_FORWARD 1
#define LLIST_BACKWARD 2

typedef void LLIST;

// llist_op 被定义为 返回值为void 类型 参数为 const void *的函数
typedef void llist_op(const void *);
typedef int llist_cmp(const void*, const void*);


LLIST * llist_create(int initsize);

int llist_insert(LLIST *,const void *data, int mode);

void* llistt_find(LLIST *p,const void *key,llist_cmp *);

int llist_delete(LLIST *p,const void *key,llist_cmp *cmp);

int llist_fetch(LLIST *p,const void *key,llist_cmp *cmp,void *data);

void llist_travel(LLIST *,llist_op *);

int llist_destory(LLIST * list_head);

（2）llist.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "../include/llist.h"

// 一般节点
struct llist_node_st{
    struct llist_node_st *pre;
    struct llist_node_st *next;
    char data[0];
};

// 头节点
struct llist_head_st{
    int size;
    // 此处的head 只是一个结构体对象，不是指针
    struct llist_node_st head;
};


/*
 * function: 创建链表
 * parameter:
 *          init_size: 节点的data内存大小
 * */
LLIST * llist_create(int init_size)
{
    struct llist_head_st *new;

    new = malloc(sizeof(*new));
    if(new==NULL)
    {
        return NULL;
    }

    // 头节点不存储数据/
    new->size = init_size;
    // new->head.data=NULL;
    new->head.pre = &new->head;
    new->head.next = &new->head;

    return new;
}


/*
 * function: 节点数据的插入
 * parameter:
 *          ptr:链表头节点
 *          data:插入的数据，传入数据的地址
 *          mode:选择插入模式(首部or尾部)
 * return:
 *          是否插入成功
 * */
int llist_insert(LLIST *p,const void *data, int mode)
{
    struct llist_node_st *new_node;
    struct llist_head_st *ptr = p; // 类型强转

    new_node = malloc(sizeof(*new_node) + ptr->size);
    if(new_node == NULL)
        return -1;

    // new_node->data = malloc(ptr->size);
    if(new_node->data == NULL)
        return -2;
    // 将存储区 data 复制ptr_size个字节数据到存储区 new_node->data
    memcpy(new_node->data, data, ptr->size);

    if(mode == LLIST_FORWARD){
        // 首部插入
        new_node->pre = &(ptr->head);
        new_node->next = ptr->head.next;
        new_node->pre->next = new_node;
        new_node->next->pre = new_node;

    }else if(mode == LLIST_BACKWARD){
        // 尾部插入
        new_node->pre = ptr->head.pre;
        new_node->next = &(ptr->head);
        new_node->pre->next = new_node;
        new_node->next->pre = new_node;
    } else{
        //ERROR
        return -3;
    }
    return 0;
}


static struct llist_node_st *find_(struct llist_head_st *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *cur;

    for(cur = ptr->head.next; cur != &(ptr->head); cur = cur->next)
    {
        if(cmp(key,cur->data) == 0)
        {
            break;
        }
    }
    // 返回该节点 ，若最后没有找到 cur 当前为ptr->head,head.data==NULL
    return cur;
}

/*
 * function: 在链表中根据 key 进行查找节点
 * parameter:
 *          ptr:链表头节点
 *          key:链表中查找的key  可以是id 也可以是 name 等，但是要与对应的cmp函数匹配
 *          cmp:比较函数（若为id查找，则在当前迭代的节点中的id 与key相同时，就返回当前节点中的data域）
 * */
void* llistt_find(LLIST *p,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *node;
    struct llist_head_st *ptr = p;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return NULL;
    // 将该节点中的data域取出
    return node->data;
}

/*
 * function: 删除链表中的节点
 * */
int llist_delete(LLIST *p,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *node;
    struct llist_head_st *ptr = p;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return -1;
    node -> pre ->next = node->next;
    node->next->pre = node->pre;
    // free(node->data);
    free(node);
    return 0;
}

/*
 * function: 在链表中按照key进行查找，并且返回删除的节点数据
 * */
int llist_fetch(LLIST *p,const void *key,llist_cmp *cmp,void *data)
{
    struct llist_node_st *node;
    struct llist_head_st *ptr = p;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return -1;
    node -> pre ->next = node->next;
    node->next->pre = node->pre;

    // 若给的data指针为NULL，则表示不需要进行data回填
    if(data!=NULL)
        memcpy(data,node->data,ptr->size);
    // free(node->data);
    free(node);
    return 0;
}


/*
 * function: 遍历链表
 * Note:此处用回调函数(函数指针)实现一个通用型的接口(并不清楚用户定义的数据类型的内部结构)
 * parameter:
 *          ptr: 链表头节点
 *          llist_op *: 函数指针，指向一个函数，当运行到该段代码时，则运行该函数
 * */
void llist_travel(LLIST *p,llist_op *op)
{
    struct llist_node_st *cur;
    struct llist_head_st *ptr = p;

    for(cur = ptr->head.next; cur != &(ptr->head); cur = cur->next)
    {
        // 调用回调函数
        op(cur->data);
    }
}


int llist_destory(LLIST * p)
{
    struct llist_node_st *cur,*next;
    struct llist_head_st *ptr = p;

    for (cur = ptr->head.next; cur != &(ptr->head); cur = next)
    {
        next = cur->next;
        // free(cur->data);
        free(cur);
    }
    // 头节点destory
    free(ptr);
}

（3）main.c

#include <stdio.h>
#include <stdlib.h>
#include "include/llist.h"
#include "string.h"

#define NAME_SIZE 32

// 用户自定义的结构体数据类型
struct score_st{
    int id;
    char name[NAME_SIZE];
    int math;
    int chinese;
};

// 回调函数，用户根据自己定义的数据类型进行函数功能定义
static void print_s(const void *record)
{
    const struct score_st *r = record;
    printf("%d %s %d %d \n",r->id,r->name,r->math,r->chinese);
}

// 按照id 相等则查找成功
static int id_cmp(const void *key,const void *record)
{
    const int *k = key;
    const struct score_st *r = record;

    return (*k - r->id);
}

static int name_cmp(const void *key,const void *record)
{
    const char *k = key;
    const struct score_st *r = record;

    return strcmp(k,r->name);
}

int main() {

    // 创建链表
    LLIST *handler;
    if(handler == NULL)
        // 结束当前进程
        exit(1);
    handler = llist_create(sizeof(struct score_st));

    // 创建插入数据
    struct score_st tmp;
    for (int i = 0; i < 7; i++) {
        tmp.id = i;
        snprintf(tmp.name,NAME_SIZE,"std%d",i);
        tmp.math = rand()%100;
        tmp.chinese = rand()%100;

        int ret = llist_insert(handler,&tmp,LLIST_FORWARD);
        if(ret)
            // ERROR 不为0  结束当前进程
            exit(1);
    }


    llist_travel(handler,print_s);

    printf("\n\n");

    int id_delete = 3;
    int ret = llist_delete(handler,&id_delete, id_cmp);
    if(ret)
        printf("delete failed!\n");

    llist_travel(handler,print_s);

    printf("\n\n");
    // 查找id为3
    int id = 4;
    struct  score_st *data;
    data = llistt_find(handler,&id,id_cmp);
    if(data == NULL)
        printf("Can not find!\n");
    else
        print_s(data);


    llist_destory(handler);


    return 0;
}

（4）CMakeLists.txt

cmake_minimum_required(VERSION 3.16)
project(doubleLinklist_5 C)

# 设置编译标准
set(CMAKE_C_STANDARD 99)

# 定义可执行文件的输出路径
set(HOME ${PROJECT_SOURCE_DIR}/bin)

# 指定可执行文件的输出路径
set(EXECUTABLE_OUTPUT_PATH ${HOME})

# 包含头文件
include_directories(${PROJECT_SOURCE_DIR}/include)

# 告知程序链接的动态库路径（至关重要）
link_directories(./lib)

# 生成可执行文件
add_executable(doubleLinklist main.c)

# 链接库
target_link_libraries(doubleLinklist libd_link.so)

9.顺序栈的实现

栈数据结构，先入后出，顺序栈使用数组作为数据区域的存储结构，其数据结构如下定义：

#define MAXSIZE 5
typedef int datatype;

// 节点
typedef struct node_st
{
    // 栈的容量
    datatype data[MAXSIZE];
    int top;
}sqstack;

项目结构目录:

$ tree
.
├── bin
│   └── sqstack
├── build
├── CMakeLists.txt
├── include
│   └── sqstack.h
├── lib
│   └── libstack_arr.so
├── main.c
└── src
    └── sqstack.c

（1）sqstack.h

#pragma once

#define MAXSIZE 5
typedef int datatype;

// 节点
typedef struct node_st
{
    // 栈的容量
    datatype data[MAXSIZE];
    int top;
}sqstack;

// 创建
sqstack *st_create(void);

// 入栈
int st_push(sqstack *,datatype *);

// 出栈
int st_pop(sqstack *,datatype *);

// 查看栈顶元素
int st_top(sqstack *,datatype *);

// 遍历
void st_travel(sqstack *);

// 销毁
void st_destory(sqstack *);

// 判空
int st_isempty(sqstack *);

（2）sqstack.c

#include <stdio.h>
#include <stdlib.h>
#include "sqstack.h"

/**
 * 创建栈
 * 成功返回 指向栈的指针  失败 返回NULL
 */
sqstack *st_create(void)
{
    sqstack *st;
    st = malloc(sizeof(*st));
    if(st == NULL )
        return NULL;
    st->top = -1;
    return st;
}

/**
 * 将数据*data 放入栈中
 * 栈满return -1   正常入栈return 0
 */
int st_push(sqstack *st,datatype *data)
{
    // 栈满
    if (st->top == MAXSIZE -1)
        return -1;
    // 入栈
    st->data[++st->top] = *data;
    return 0;
}

/**
 * 栈顶元素出栈，并存储 *data中
 * 失败返回-1  成功返回0
 */
int st_pop(sqstack *st,datatype *data)
{
    if (st_isempty(st))
        return -1;
    *data = st->data[st->top];
    st->top--;
    return 0;
}

/**
 * 查看栈顶元素，并存储 *data中
 * 失败返回-1  成功返回0
 */
int st_top(sqstack *st,datatype *data)
{
    if(!st_isempty(st))
        return -1;
    *data = st->data[st->top];
    return 0;
}

/**
 * 从栈底到栈顶 遍历栈
 */
void st_travel(sqstack *st)
{
    if (st_isempty(st))
        return;
    for(int i=0;i<=st->top;i++ )
    {
        printf("%d ",st->data[i]);
    }
    printf("\n");
}

/**
 * 销毁 栈
 */
void st_destory(sqstack *st)
{
    free(st);
}


/**
 *  若栈为空 return 1  否则 return 0
 */
int st_isempty(sqstack *st)
{
    if (st->top == -1)
        return 1;
    else
        return 0;
}

（3）main.c

#include <stdio.h>
#include <stdlib.h>
#include "sqstack.h"

int main() {
    datatype arr[] = {15,45,20,36};

    sqstack *st = st_create();
    if(st == NULL)
        // 创建失败 中止
        exit(1);


    for(int i = 0;i<=sizeof(arr)/sizeof(*arr)-1;i++)
        st_push(st,&arr[i]);

    st_travel(st);

    datatype tmp = 22;
    int ret = st_push(st,&tmp);
    if (ret != 0)
        printf("st_push failed. \n");
    else
        st_travel(st);




    // 出栈
    datatype tmp_1;
    while(st_pop(st,&tmp_1) == 0)
    {
        printf("%d ",tmp_1);
    }
    printf("\n");

    // 销毁
    st_destory(st);
    return 0;
}

（4）CMakeLists.txt

cmake_minimum_required(VERSION 3.16)
project(arr C)

# 设置编译标准
set(CMAKE_C_STANDARD 99)

# 定义可执行文件的输出路径
set(HOME ${PROJECT_SOURCE_DIR}/bin)

# 指定可执行文件的输出路径
set(EXECUTABLE_OUTPUT_PATH ${HOME})

# 包含头文件
include_directories(${PROJECT_SOURCE_DIR}/include)

# 搜索 src 目录下的源文件,并且存储值SRC_LIST中(数组)
file(GLOB SRC_LIST ${CMAKE_CURRENT_SOURCE_DIR}/src/*.c)

# 设置动态(静态)库生成路径
set(LIBRARY_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/lib)

# 生成动态库
add_library(stack_arr SHARED ${SRC_LIST})

# 生成可执行文件
add_executable(sqstack main.c)

# 链接库
target_link_libraries(sqstack stack_arr)

10.链式栈的实现

链式栈，从之前的变长结构体的双向循环链表进行二次封装

使用变长结构体的双向循环链表作为链式栈的底层实现

项目结构目录:

$ tree
.
├── bin
│   └── list_stack
├── build
├── CMakeLists.txt
├── include
│   └── stack.h
│   └── llist.h
├── lib
│   └── liblink_stack.so
├── main.c
└── src
    └── sqstack.c
    └── llist.c

（1）llist.h & stack.h

llist.h

#pragma once

// 插入模式的宏定义
#define LLIST_FORWARD 1
#define LLIST_BACKWARD 2

// llist_op 被定义为 返回值为void 类型 参数为 const void *的函数
typedef void llist_op(const void *);
typedef int llist_cmp(const void*, const void*);

// 一般节点
struct llist_node_st{
    struct llist_node_st *pre;
    struct llist_node_st *next;
    char data[0];
};

// 头节点
typedef struct{
    int size;
    // 此处的head 只是一个结构体对象，不是指针
    struct llist_node_st head;
}LLIST;


LLIST * llist_create(int initsize);

int llist_insert(LLIST *,const void *data, int mode);

void* llistt_find(LLIST *ptr,const void *key,llist_cmp *);

int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp);

int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp,void *data);

void llist_travel(LLIST *,llist_op *);

int llist_destory(LLIST * list_head);

stack.h

# pragma once
#include <stdio.h>
#include "llist.h"

typedef LLIST STACK;

STACK  *stack_create(int initsize);

int stack_push(STACK *ptr,const void *data);

int stack_pop(STACK *ptr,void *data);

void stack_destory(STACK *ptr);

（2）llist.c & stack.c

llist.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "../include/llist.h"

/*
 * function: 创建链表
 * parameter:
 *          init_size: 节点的data内存大小
 * */
LLIST * llist_create(int init_size)
{
    LLIST *new;

    new = malloc(sizeof(*new));
    if(new==NULL)
    {
        return NULL;
    }

    // 头节点不存储数据/
    new->size = init_size;
    // new->head.data=NULL;
    new->head.pre = &new->head;
    new->head.next = &new->head;

    return new;
}


/*
 * function: 节点数据的插入
 * parameter:
 *          ptr:链表头节点
 *          data:插入的数据，传入数据的地址
 *          mode:选择插入模式(首部or尾部)
 * return:
 *          是否插入成功
 * */
int llist_insert(LLIST *ptr,const void *data, int mode)
{
    struct llist_node_st *new_node;

    new_node = malloc(sizeof(*new_node) + ptr->size);
    if(new_node == NULL)
        return -1;

    // new_node->data = malloc(ptr->size);
    if(new_node->data == NULL)
        return -2;
    // 将存储区 data 复制ptr_size个字节数据到存储区 new_node->data
    memcpy(new_node->data, data, ptr->size);

    if(mode == LLIST_FORWARD){
        // 首部插入
        new_node->pre = &(ptr->head);
        new_node->next = ptr->head.next;
        new_node->pre->next = new_node;
        new_node->next->pre = new_node;

    }else if(mode == LLIST_BACKWARD){
        // 尾部插入
        new_node->pre = ptr->head.pre;
        new_node->next = &(ptr->head);
        new_node->pre->next = new_node;
        new_node->next->pre = new_node;
    } else{
        //ERROR
        return -3;
    }
    return 0;
}


static struct llist_node_st *find_(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *cur;

    for(cur = ptr->head.next; cur != &(ptr->head); cur = cur->next)
    {
        if(cmp(key,cur->data) == 0)
        {
            break;
        }
    }
    // 返回该节点 ，若最后没有找到 cur 当前为ptr->head,head.data==NULL
    return cur;
}

/*
 * function: 在链表中根据 key 进行查找节点
 * parameter:
 *          ptr:链表头节点
 *          key:链表中查找的key  可以是id 也可以是 name 等，但是要与对应的cmp函数匹配
 *          cmp:比较函数（若为id查找，则在当前迭代的节点中的id 与key相同时，就返回当前节点中的data域）
 * */
void* llistt_find(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *node;
    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return NULL;
    // 将该节点中的data域取出
    return node->data;
}

/*
 * function: 删除链表中的节点
 * */
int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *node;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return -1;
    node -> pre ->next = node->next;
    node->next->pre = node->pre;
    // free(node->data);
    free(node);
    return 0;
}

/*
 * function: 在链表中按照key进行查找，并且返回删除的节点数据
 * */
int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp,void *data)
{
    struct llist_node_st *node;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return -1;
    node -> pre ->next = node->next;
    node->next->pre = node->pre;

    // 若给的data指针为NULL，则表示不需要进行data回填
    if(data!=NULL)
        memcpy(data,node->data,ptr->size);
    // free(node->data);
    free(node);
    return 0;
}


/*
 * function: 遍历链表
 * Note:此处用回调函数(函数指针)实现一个通用型的接口(并不清楚用户定义的数据类型的内部结构)
 * parameter:
 *          ptr: 链表头节点
 *          llist_op *: 函数指针，指向一个函数，当运行到该段代码时，则运行该函数
 * */
void llist_travel(LLIST *ptr,llist_op *op)
{
    struct llist_node_st *cur;

    for(cur = ptr->head.next; cur != &(ptr->head); cur = cur->next)
    {
        // 调用回调函数
        op(cur->data);
    }
}


int llist_destory(LLIST * ptr)
{
    struct llist_node_st *cur,*next;

    for (cur = ptr->head.next; cur != &(ptr->head); cur = next)
    {
        next = cur->next;
        // free(cur->data);
        free(cur);
    }
    // 头节点destory
    free(ptr);
}

stack.c

#include "stack.h"

/**
 * 创建栈
 * 创建失败返回 NULL
 */
STACK  *stack_create(int initsize)
{
    return llist_create(initsize);
}

/**
 * 压入栈
 * 压入成功 返回0
 */
int stack_push(STACK *ptr,const void *data)
{
    return llist_insert(ptr,data,LLIST_FORWARD);
}


static int always_match(const void *p1,const void *p2)
{
    return 0;
}

/**
 * 出栈
 */
int stack_pop(STACK *ptr,void *data)
{
    return llist_fetch(ptr,(void *)0,always_match,data);
}


/**
 * 销毁栈
 */
void stack_destory(STACK *ptr)
{
    llist_destory(ptr);
}

注意:(void *)0通常可以视作为NULL

（3）main.c

#include <stdio.h>
#include <stdlib.h>
#include "include/llist.h"
#include "include/stack.h"


#define NAME_SIZE 32

// 用户自定义的结构体数据类型
struct score_st{
    int id;
    char name[NAME_SIZE];
    int math;
    int chinese;
};


// 回调函数，用户根据自己定义的数据类型进行函数功能定义
static void print_s(const void *record)
{
    const struct score_st *r = record;
    printf("%d %s %d %d \n",r->id,r->name,r->math,r->chinese);
}

int main() {

    STACK *st;
    struct score_st tmp;
    int i;
    int ret;

    // 创建栈
    st = stack_create(sizeof(struct score_st));
    if (st == NULL)
    {
        exit(1);
    }

    // 压入栈
    for (i = 0;i<7;i++)
    {
        tmp.id = i;
        snprintf(tmp.name,NAME_SIZE,"stu%d",i);
        tmp.chinese = rand()%100;
        tmp.math = rand()%100;

        if (stack_push(st,&tmp))
            // 判断入栈是否成功，失败则中止
            exit(1);
    }

    while(1)
    {
        ret = stack_pop(st,&tmp);
        if (ret == -1)
            break;
        print_s(&tmp);
    }


    exit(0);

}

（4）CMakeLists.txt

cmake_minimum_required(VERSION 3.20)
project(list_stack C)

# 设置编译标准
set(CMAKE_C_STANDARD 99)

# 定义可执行文件的输出路径
set(HOME ${PROJECT_SOURCE_DIR}/bin)

# 指定可执行文件的输出路径
set(EXECUTABLE_OUTPUT_PATH ${HOME})

# 包含头文件
include_directories(${PROJECT_SOURCE_DIR}/include)

# 搜索 src 目录下的源文件,并且存储值SRC_LIST中(数组)
file(GLOB SRC_LIST ${CMAKE_CURRENT_SOURCE_DIR}/src/*.c)

# 设置动态(静态)库生成路径
set(LIBRARY_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/lib)

# 生成动态库
add_library(link_stack SHARED ${SRC_LIST})

# 生成可执行文件
add_executable(list_stack main.c)

# 链接库
target_link_libraries(list_stack link_stack)

11.顺序存储队列的实现

队列先入先出

存在一个队头指针队尾指针

每次增加一个元素入队队尾指针向后移动一次

每次减少一个元素出队队首指针向后移动一次

项目结构目录:

$ tree
.
├── bin
│   └── arr_quene
├── build
├── CMakeLists.txt
├── include
│   └── queue.h
├── lib
│   └── liba_queue.so
├── main.c
└── src
    └── sqeue.c

（1）quene.h

#pragma once


typedef int  datatype;
#define MAXSIZE 1024

typedef struct score_st
{
    datatype data[MAXSIZE];
    int head,tail;
}queue;

queue * qu_create();

int qu_isempty(queue *);

int qu_enqueue(queue *,datatype *);

int qu_dequeue(queue *,datatype *);

void qu_travel(queue *);

// 清空队列里面的数据
void qu_clear(queue * );

// 销毁
void qu_destroy(queue *);

（2）quene.c

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"


queue * qu_create()
{
    queue *sq;

    sq = malloc(sizeof(*sq));

    if(sq == NULL)
        return NULL;

    sq->head = 0;
    sq->tail = 0;

    return sq;
}

/**
 * 队列是否为空
 * 参数：
 *  sq:操作的队列指针
 * 返回：
 *  1:队列为空
 *  0:队列不为空
 */
int qu_isempty(queue *sq)
{
    if(sq->head == sq->tail)
        return 1;
    return 0;
}


/**
 *  入队
 * 参数：
 *  sq:操作的队列指针
 *  data:入队的数据指针
 * 返回：
 *  -1:队满-入队失败
 *  0:入队成功
 */
int qu_enqueue(queue *sq,datatype *data)
{
    // 队列满,不允许继续进行入队操作
    if ((sq->tail + 1) % MAXSIZE == sq->head)
        return -1;
    // 循环队列需要取模
    sq->tail = (sq->tail + 1) % MAXSIZE;
    sq->data[sq->tail] = *data;
    return 0;
}


/**
 *  出队
 * 参数：
 *  sq:操作的队列指针
 *  data:出队回传的数据指针
 * 返回：
 *  -1:队空-出队失败
 *  0:出队成功
 */
int qu_dequeue(queue *sq,datatype *data)
{
    // 队空 出队失败
    if (qu_isempty(sq))
        return -1;

    sq->head = (sq->head + 1) % MAXSIZE;
    *data = sq->data[sq->head];

    // 出队成功
    return 0;

}

/**
 * 遍历队列
 * 参数：
 *  sq:操作的队列指针
 */
void qu_travel(queue *sq)
{
    int i;
    // 队列为空不进行遍历
    if (qu_isempty(sq))
        return;
    i = (sq->head + 1) % MAXSIZE;
    while (i != sq->tail)
    {
        printf("%d ",sq->data[i]);
        i = (i+1)%MAXSIZE;
    }
    // 队尾 存在数据 打印
    printf("%d\n", sq->data[i]);
}

// 清空队列里面的数据
void qu_clear(queue *sq)
{
    // 将队列首尾进行对等处理（队列就为空）
    sq->head = sq->tail;
}

// 销毁
void qu_destroy(queue *sq)
{
    free(sq);
}

（3）main.c

#include <stdio.h>
#include "queue.h"
#include <stdlib.h>

int main() {
    // 创建
    queue *sq;
    datatype arr[6] = {2,34,98,12,3,5};
    int i,ret;

    sq = qu_create();
    if(sq==NULL)
        exit(1);

    for(i = 0;i<sizeof(arr)/sizeof(*arr);i++)
    {
        // 入队操作
        qu_enqueue(sq,&arr[i]);
    }

    // 遍历输出测试
    qu_travel(sq);
    // 再一次遍历测试
    datatype tmp = 100;
    ret = qu_enqueue(sq,&tmp);
    if(ret == -1)
        printf("queue is full!\n");
    else
        qu_travel(sq);

    // 出队测试
    datatype de_tmp;
    ret = qu_dequeue(sq,&de_tmp);
    if (ret == -1)
        printf("queue is empty!dequeue failed!\n");
    else
        printf("DEQUEUE:%d\n",de_tmp);

    // 出队后 遍历测试
    qu_travel(sq);

    // 销毁
    qu_destroy(sq);

    exit(0);
}

（4）CMakeLists.txt

cmake_minimum_required(VERSION 3.16)
project(arr_queue C)

# 设置编译标准
set(CMAKE_C_STANDARD 99)

# 定义可执行文件的输出路径
set(HOME ${PROJECT_SOURCE_DIR}/bin)

# 指定可执行文件的输出路径
set(EXECUTABLE_OUTPUT_PATH ${HOME})

# 包含头文件
include_directories(${PROJECT_SOURCE_DIR}/include)

# 搜索 src 目录下的源文件,并且存储值SRC_LIST中(数组)
file(GLOB SRC_LIST ${CMAKE_CURRENT_SOURCE_DIR}/src/*.c)

# 设置动态(静态)库生成路径
set(LIBRARY_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/lib)

# 生成动态库
add_library(a_queue SHARED ${SRC_LIST})

# 生成可执行文件
add_executable(arr_queue main.c)

# 链接库
target_link_libraries(arr_queue a_queue)

12.链式存储队列的实现

链式队列，从之前的变长结构体的双向循环链表进行二次封装

使用变长结构体的双向循环链表作为链式队列的底层实现

项目结构目录:

$ tree
.
├── bin
│   └── link_queue
├── build
├── CMakeLists.txt
├── include
│   └── stack.h
│   └── queue.h
├── lib
│   └── libl_queue.so
├── main.c
└── src
    └── queue.c
    └── llist.c

（1）llist.h & queue.h

llist.h

#pragma once

// 插入模式的宏定义
#define LLIST_FORWARD 1
#define LLIST_BACKWARD 2

// llist_op 被定义为 返回值为void 类型 参数为 const void *的函数
typedef void llist_op(const void *);
typedef int llist_cmp(const void*, const void*);

// 一般节点
struct llist_node_st{
    struct llist_node_st *pre;
    struct llist_node_st *next;
    char data[0];
};

// 头节点
typedef struct{
    int size;
    // 此处的head 只是一个结构体对象，不是指针
    struct llist_node_st head;
}LLIST;


LLIST * llist_create(int initsize);

int llist_insert(LLIST *,const void *data, int mode);

void* llistt_find(LLIST *ptr,const void *key,llist_cmp *);

int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp);

int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp,void *data);

void llist_travel(LLIST *,llist_op *);

void llist_destory(LLIST * list_head);

queue.h

#pragma once
#include "llist.h"

typedef LLIST QUEUE;

QUEUE *qu_create(int initsize);

int qu_en(QUEUE *ptr,void *data);

int qu_de(QUEUE *ptr,void *data);

// 销毁
void qu_destroy(QUEUE *ptr);

（2）llist.c & queue.c

llist.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "../include/llist.h"

/*
 * function: 创建链表
 * parameter:
 *          init_size: 节点的data内存大小
 * */
LLIST * llist_create(int init_size)
{
    LLIST *new;

    new = malloc(sizeof(*new));
    if(new==NULL)
    {
        return NULL;
    }

    // 头节点不存储数据/
    new->size = init_size;
    // new->head.data=NULL;
    new->head.pre = &new->head;
    new->head.next = &new->head;

    return new;
}


/*
 * function: 节点数据的插入
 * parameter:
 *          ptr:链表头节点
 *          data:插入的数据，传入数据的地址
 *          mode:选择插入模式(首部or尾部)
 * return:
 *          是否插入成功
 * */
int llist_insert(LLIST *ptr,const void *data, int mode)
{
    struct llist_node_st *new_node;

    new_node = malloc(sizeof(*new_node) + ptr->size);
    if(new_node == NULL)
        return -1;

    // new_node->data = malloc(ptr->size);
    if(new_node->data == NULL)
        return -2;
    // 将存储区 data 复制ptr_size个字节数据到存储区 new_node->data
    memcpy(new_node->data, data, ptr->size);

    if(mode == LLIST_FORWARD){
        // 首部插入
        new_node->pre = &(ptr->head);
        new_node->next = ptr->head.next;
        new_node->pre->next = new_node;
        new_node->next->pre = new_node;

    }else if(mode == LLIST_BACKWARD){
        // 尾部插入
        new_node->pre = ptr->head.pre;
        new_node->next = &(ptr->head);
        new_node->pre->next = new_node;
        new_node->next->pre = new_node;
    } else{
        //ERROR
        return -3;
    }
    return 0;
}


static struct llist_node_st *find_(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *cur;

    for(cur = ptr->head.next; cur != &(ptr->head); cur = cur->next)
    {
        if(cmp(key,cur->data) == 0)
        {
            break;
        }
    }
    // 返回该节点 ，若最后没有找到 cur 当前为ptr->head,head.data==NULL
    return cur;
}

/*
 * function: 在链表中根据 key 进行查找节点
 * parameter:
 *          ptr:链表头节点
 *          key:链表中查找的key  可以是id 也可以是 name 等，但是要与对应的cmp函数匹配
 *          cmp:比较函数（若为id查找，则在当前迭代的节点中的id 与key相同时，就返回当前节点中的data域）
 * */
void* llistt_find(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *node;
    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return NULL;
    // 将该节点中的data域取出
    return node->data;
}

/*
 * function: 删除链表中的节点
 * */
int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp)
{
    struct llist_node_st *node;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return -1;
    node -> pre ->next = node->next;
    node->next->pre = node->pre;
    // free(node->data);
    free(node);
    return 0;
}

/*
 * function: 在链表中按照key进行查找，并且返回删除的节点数据
 * */
int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp,void *data)
{
    struct llist_node_st *node;

    node = find_(ptr,key,cmp);
    if(node == &(ptr->head))
        return -1;
    node -> pre ->next = node->next;
    node->next->pre = node->pre;

    // 若给的data指针为NULL，则表示不需要进行data回填
    if(data!=NULL)
        memcpy(data,node->data,ptr->size);
    // free(node->data);
    free(node);
    return 0;
}


/*
 * function: 遍历链表
 * Note:此处用回调函数(函数指针)实现一个通用型的接口(并不清楚用户定义的数据类型的内部结构)
 * parameter:
 *          ptr: 链表头节点
 *          llist_op *: 函数指针，指向一个函数，当运行到该段代码时，则运行该函数
 * */
void llist_travel(LLIST *ptr,llist_op *op)
{
    struct llist_node_st *cur;

    for(cur = ptr->head.next; cur != &(ptr->head); cur = cur->next)
    {
        // 调用回调函数
        op(cur->data);
    }
}


void llist_destory(LLIST * ptr)
{
    struct llist_node_st *cur,*next;

    for (cur = ptr->head.next; cur != &(ptr->head); cur = next)
    {
        next = cur->next;
        // free(cur->data);
        free(cur);
    }
    // 头节点destory
    free(ptr);
}

queue.c

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

/**
 * 创建队列
 * 创建失败返回 NULL
 */
QUEUE *qu_create(int initsize)
{
    return llist_create(initsize);
}

/**
 * 入队
 * 队列尾部插入
 * 返回:
 *  0 则入队成功
 */
int qu_en(QUEUE *ptr,void *data)
{
    // 尾部插入
    return llist_insert(ptr,data,LLIST_BACKWARD);
}



static int always_match(const void *p1,const void *p2)
{
    return 0;
}

/**
 * 出队
 * 队列首部出队
 * 返回:
 *  0 则插入成功
 */
int qu_de(QUEUE *ptr,void *data)
{
    return llist_fetch(ptr,(void *)0,always_match,data);
}

// 销毁
void qu_destroy(QUEUE *ptr)
{
    llist_destory(ptr);
}

注意:(void *)0通常可以视作为NULL

（3）main.c

#include <stdio.h>
#include "queue.h"
#include <stdlib.h>

#define NAME_SIZE 1024

// 用户自定义的结构体数据类型
struct score_st{
    int id;
    char name[NAME_SIZE];
    int math;
    int chinese;
};

// 回调函数，用户根据自己定义的数据类型进行函数功能定义
static void print_s(const void *record)
{
    const struct score_st *r = record;
    printf("%d %s %d %d \n",r->id,r->name,r->math,r->chinese);
}


int main() {

    struct score_st tmp;
    int i;
    int ret;

    // 创建
    QUEUE *qu;
    qu = qu_create(sizeof(struct score_st));
    if(qu ==NULL)
        exit(1);

    // 压入栈
    for (i = 0;i<7;i++)
    {
        tmp.id = i;
        snprintf(tmp.name,NAME_SIZE,"stu%d",i);
        tmp.chinese = rand()%100;
        tmp.math = rand()%100;

        if (qu_en(qu,&tmp))
            // 判断入栈是否成功，失败则中止
            exit(1);
    }

    while(1)
    {
        ret = qu_de(qu,&tmp);
        if (ret == -1)
            break;
        print_s(&tmp);
    }

    exit(0);
}

（4）CMakeLists.txt

cmake_minimum_required(VERSION 3.20)
project(list_stack C)

# 设置编译标准
set(CMAKE_C_STANDARD 99)

# 定义可执行文件的输出路径
set(HOME ${PROJECT_SOURCE_DIR}/bin)

# 指定可执行文件的输出路径
set(EXECUTABLE_OUTPUT_PATH ${HOME})

# 包含头文件
include_directories(${PROJECT_SOURCE_DIR}/include)

# 搜索 src 目录下的源文件,并且存储值SRC_LIST中(数组)
file(GLOB SRC_LIST ${CMAKE_CURRENT_SOURCE_DIR}/src/*.c)

# 设置动态(静态)库生成路径
set(LIBRARY_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/lib)

# 生成动态库
add_library(l_queue SHARED ${SRC_LIST} )

# 生成可执行文件
add_executable(link_queue main.c)

# 链接库
target_link_libraries(link_queue l_queue)

13.动态库以及静态库

（1）静态库

libxx.a

xx 指代库名

可是使用gcc命令将.o（目标文件gcc -c xx.c -o xx.o）文件编译为静态库

1	ar -cr libxx.a yyy.o

发布到linux系统下

1 2	cp xx.h /usr/local/include # 头文件 cp libxx.a /usr/local/lib # 静态库

gcc命令行链接静态库

1
2
3

gcc -o main main.c -lxx   # main 生成的目标文件名字  main.c为生成main所依赖的文件  -lxx  -l 为链接的意思 xx 为库名
    或者
gcc -L /usr/local/lib -o main main.c -lxx   # -L /usr/local/li 为链接库文件的路径

此时可以通过

1	ldd ./xx # 查看xx目标文件所依赖的库

（2）动态库

libxx.so

使用gcc 生成动态库

1	gcc -shared -fpic -o libxx.so yyy.c # -yyy.c 为动态库所依赖的c文件

-fpic为位置无关代码

发布到linux系统下

1 2	cp xx.h /usr/local/include # 头文件 cp libxx.so /usr/local/lib # 动态库

动态库需要在/etc/lb.so.confg中添加路径

1 2	# /etc/lib.so.confg 文件下添加动态库路径 /usr/local/lib/

添加路径之后，需要在终端中使用命令重读刚刚修改的配置文件

1	$ /sbin/ldconfg # /etc/lib.so.confg 配置文件

编译调用链接库的.c文件

gcc -I /usr/local/include/ -L /usr/local/lib -o main main.c -lxx
# -I 后引出动态库所需要的头文件路径
# -L 后引出动态库所需要的库文件路径
# main 为main.c所生成的目标文件 -lxx xx文件为动态库库名

当一个目录下存在重名的动态库以及静态库则会优先链接动态库

非root用户

1 2	cp xx.so ~/lib export LD_LIBRARY_PATH = ~/lib

当链接的多个库彼此之间存在链接关系时，如生成main目标文件时，需要依赖libx.a 但是libx.a有需要依赖 liby.a

1	gcc -o main main.c -lx -ly # 被依赖的库写在后面

14.树状存储

（1）基本概念

二叉树的顺序存储非常浪费空间

二叉树链式存储，包含左孩子指针与右孩子指针

遍历方式

按层序遍历、先序、后序、中序

（2）二叉树的链式存储实现

插入数据方式：遍历数组，小的数字放在左节点大的节点放在右节点

main.c

#include <stdio.h>
#include <stdlib.h>

#define NAMESIZE 1024

// 数据结构体
struct score_st
{
    int id;
    char name[NAMESIZE];
    int math;
    int chinese;
};

// 节点结构体
struct node_st
{
    struct score_st  data;
    struct node_st *l,*r; // 左孩子指针，右孩子指针
};

/**
 * 插入数据方式：遍历数组，比较data中的id,小的数字放在左节点 大的节点放在右节点
 * 递归插入
 */
int insert(struct node_st **root,struct score_st *data)
{
    struct node_st *node;
    // 当其递归到的叶子节点
    if (*root == NULL)
    {
        node = malloc(sizeof(*node));
        if(node ==NULL)
            return -1;
        node->data = *data;
        node->l = NULL;
        node->r = NULL;

        // 当其创建的节点 地址赋值给 根节点指针
        *root = node;
        return 0;
    }

    if(data->id <= (*root)->data.id)
    {
        // 递归插入
        return insert(&((*root)->l),data);
    }
    else
        return insert(&((*root)->r),data);;
}


/**
 * 递归查找
 */
struct score_st *find(struct node_st *root,int id)
{
    // 若当前递归到的叶子节点为空
    if(root == NULL)
        return NULL;
    // 找到了
    if (id == root->data.id)
        return &(root->data);

    // 若id比当前节点的id小的话，就在左子树去找
    if(id < root->data.id)
        return find(root->l,id);
    else
        return find(root->r,id);
}


// 回调函数，用户根据自己定义的数据类型进行函数功能定义
void print_s(struct score_st *d)
{
    printf("%d %s %d %d \n",d->id,d->name,d->math,d->chinese);
}

int main() {
    int i ;
    int arr[] = {1,2,3,7,6,5,9,8,4};
    struct node_st *tree = NULL;
    struct score_st tmp;
    struct score_st *datap;

    for (i = 0; i < sizeof(arr)/sizeof(*arr);i++)
    {
        tmp.id = arr[i];
        snprintf(tmp.name,NAMESIZE,"stu%d",arr[i]);
        tmp.math = rand()%100;
        tmp.chinese = rand()%100;

        // 插入数据
        insert(&tree,&tmp);
    }


    int tmpid = 2;
    datap = find(tree,tmpid);
    if (datap == NULL)
        printf("Can not find the id %d\n",tmpid);
    else
        print_s(datap);

    return 0;
}

cmake_minimum_required(VERSION 3.16)
project(Btree C)

set(CMAKE_C_STANDARD 99)

add_executable(Btree main.c)

数据结构

一、 顺序存储的线性表

1.sqlist.h

2.sqlist.c

3.main.c

4.运行结果：

二、链式存储

1.单向带头链表的实现

(1) list.h

(2) list.c

(3) main.c

(4) makefile

2.二级指针

3.单向无头链表的实现

（1）nohead_link.h

（2）nohead_link.c

（3）main.c

（4）makefile

4.约瑟夫算法

（1）jose_create() 创建无头的环路链表

（2）jose_kill() 数数到n的人出局

5.双向循环链表

（1）llist.h

（2）llist.c

（3）main.c

（4）CMakeLists.txt

（5）运行结果

6.双向循环链表(一般节点的变长结构体实现)

（1）llist.h

（2）llist.c

（3）main.c

7.双向循环链表(封装为类)

（1）llist.h

（2）llist.c

（3）main.c

8.双向循环链表(封装为类-将来使用llist.c作为动态库使用)

（1）llist.h

（2）llist.c

（3）main.c

（4）CMakeLists.txt

9.顺序栈的实现

（1）sqstack.h

（2）sqstack.c

（3）main.c

（4）CMakeLists.txt

10.链式栈的实现

（1）llist.h & stack.h

（2）llist.c & stack.c

（3）main.c

（4）CMakeLists.txt

11.顺序存储队列的实现

（1）quene.h

（2）quene.c

（3）main.c

（4）CMakeLists.txt

12.链式存储队列的实现

（1）llist.h & queue.h

（2）llist.c & queue.c

（3）main.c

（4）CMakeLists.txt

13.动态库以及静态库

（1）静态库

（2）动态库

14.树状存储

（1）基本概念

（2）二叉树的链式存储实现

一、顺序存储的线性表

（1）`jose_create()` 创建无头的环路链表

（2）`jose_kill()` 数数到n的人出局

8.双向循环链表(封装为类-将来使用`llist.c`作为动态库使用)