C语言实现动态链表的示例代码

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 *));

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;
}

void init_slink(SLink *link){
	*link = create_node(NULL,0,NULL);	//同样调用生成节点的静态方法
}

bool is_empty(SLink link){
	return link->next == NULL;	
}

}
size_t size(SLink link){
	size_t cnt = 0;	//用来记录节点个数
	SNode *node = link->next;	//从首节点开始算起
	while(node != NULL){	//遍历这个链表
		++cnt;
		node = node->next;
	}
	return cnt;
}

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;	//遍历完成并且返回这个数据的地址即可
}

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;
}

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);
}

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
}

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;
}

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);
}