C语言 数据结构之单链表基本操作

C语言 数据结构之单链表基本操作
单链表的各种操作，适合于初学，也适合于复习
单链表操作介绍
1. 创建头节点
2. 创建有数据节点
3. 判断链表是否为空
4. 遍历链表(有头节点链表)
5. 遍历链表(无头节点链表)
6. 头插、头删、尾插、尾删
7. 按照顺序插入(自带排序)
8. 按照位置插入数据
9. 按照数据修改数据
10. 按照节点位置查找数据
11. 判断某个值是否在当前链表中（按数据查找数据）
12. 面试中常见：单链表翻转
13. 已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序，要求用递归方法

#include 
#include 
typedef int data_t;
typedef struct Node{
	data_t data;
	struct Node * next;	
} link, *pnode;

//创建头节点
link *create_head()
{
	link *head = NULL;
	head = (link*)malloc(sizeof(link));
	if(NULL == head)
	{
		printf("malloc errorn");
		return NULL;
	}
	head->next = NULL;
	return head;
}
//创建有数据节点
link *create_node(data_t data)
{
	link *node = NULL;
	node = (link*)malloc(sizeof(link));
	if(NULL == node)
	{
		printf("create_node errorn");
		return NULL;
	}
	node->data = data;
	node->next = NULL;
	return node;
}
//判断链表是否为空
int link_empty(link *h)
{
	return (h->next == NULL)?1:0;
}
//遍历链表(有头节点链表)
void print_link(link *h)
{
	while(h->next != NULL)
	{
		printf("  %d  ",h->next->data);
		h = h->next;
	}
	putchar(10);
}
//遍历链表(无头节点链表)
void print_link_nohead(link *h)
{
	while(h != NULL)
	{
		printf("  %d  ",h->data);
		h = h->next;
	}
	putchar(10);
}
//头插
void insert_link_head(link *h,data_t data)
{
	link *node = create_node(data);
	if(NULL == node)
	{
		return ;
	}
	node->next = h->next;
	h->next = node;

}
//按照顺序插入(自带排序)
void insert_link_sort(link *h,data_t data)
{
	link * node = create_node(data);
	while((h->next != NULL) && (h->next->data < data))
	{
		h = h->next;
	}
	node->next = h->next;
	h->next = node;

}
//按照位置插入数据
void insert_link_pos_val(link *h,data_t pos,data_t data)
{
	link *node = create_node(data);
	int flags = 0;
	if(h->next != NULL)
	{
		for(int i = 0;inext; 
		}
		node->next = h->next;
		h->next = node;
	}
	if(flags==0)
	{
		h->next = node;
	}
}
//头删
data_t link_del_head(link *h)
{
	if(link_empty(h))
	{
		printf("链表为空n");
		return -1;
	}
	link *del = NULL;
	del = h->next;
	data_t val = del->data;
	h->next = del->next;
	free(del);
	del = NULL;
	return val;
}
//尾插
void insert_link_tail(link *h,data_t data)
{
	link *node = create_node(data);
	if(NULL == node)
	{
		printf("节点创建失败n");
	}
	while(h->next != NULL)
	{
		h = h->next; 
	}
	h->next = node;
}
//尾删
data_t link_del_tail(link *h)
{
	while(h->next->next != NULL)
	{
		h = h->next;
	}
	link *del = h->next;
	data_t val = del->data;
	h->next = NULL;
	free(del);
	del = NULL;

	return val;
}
//按数据修改数据
void link_updata_val(link *h,data_t old_data,data_t new_data)
{
	int flags = 0;
	while(h->next != NULL)
	{
		if(h->next->data == old_data)
		{
			h->next->data = new_data;
			flags ++;
		}
		h = h->next;
	}
	if(flags == 0)
	{
		printf("%d 不在链表中n",old_data);
	}
}
//按位置修改数据
void link_updata_val_pos(link *h,data_t pos,data_t data)
{
	int flags =0;
	if(h->next != NULL)
	{
		for(int i = 0;inext;
			flags++;
		}
		h->next->data = data;
	}
	if(flags == 0)
	{
		printf(" 链表中不存在此位置的节点n");	
	}
}

//按位置查找数据
void find_pos_link(link *h,data_t pos)
{
	data_t flags = 0;
	if(h->next != NULL)
	{
		for(int i=0;inext;
			flags++;
		}
	}
	printf("查到下标为[%d]数据为%dn",pos,h->data);
	if(flags == 0)
	{
		printf("此位置不在链表中n");
	}
}
//按数据查找数据
void find_val_link(link *h,data_t data)
{
	data_t flags = 0;
	while(h->next != NULL)
	{
		if(h->next->data ==data)
		{
			printf("所查数据存在链表当中，值为%d的下标为[%d]n",h->next->data,flags+1);
		}
		h = h->next;
		flags++;
	}
	if(flags==0)
	{
		printf("链表中没有数据为%dn",data);
	}
}
//单链表翻转
void link_return(link *h)
{
	link *temp=NULL,*prc=NULL;
	temp = h->next;
	h->next = NULL;
	while(temp != NULL)
	{
		prc = temp; 
		temp = temp->next;
		prc->next = h->next;
		h->next = prc;
	}
}

pnode reverse(pnode head)//两两节点之间不断交换
{
   if(head == NULL || head->next == NULL)
	   return head;
   pnode pre = NULL;
   pnode next = NULL;
   while(head != NULL){
      next = head->next;
      head->next = pre;
      pre = head;
      head = next;
	}
    return pre;
}
//两个链表合并(递归)
//已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序，要求用递归方法进行
link *merge_two_lists(link *l1,link *l2)
{
	
	if(l1 == NULL){
		return l2;
	}
	else if(l2 ==NULL){
		return l1;
	}
	if (l1->data <= l2->data)
	{
		l1->next = merge_two_lists(l1->next,l2);
		return l1;
	}
	else
	{
		l2->next = merge_two_lists(l1,l2->next);
		return l2;
	}
}


int main(int argc, char *argv[])
{
	link *h1 = create_head();

	insert_link_head(h1,7);
	insert_link_head(h1,5);
	insert_link_head(h1,1);
	printf("头插:");
	print_link(h1);
	printf("按照位置插入数据：");
	insert_link_pos_val(h1,1,3);
	print_link(h1);
	printf("尾插：");
	insert_link_tail(h1,9);
	print_link(h1);
	insert_link_sort(h1,11);
	printf("按照排序大小插入：");
	print_link(h1);
	
	link_updata_val(h1,11,200);
	printf("按照数据修改数据：");
	print_link(h1);

	link_updata_val_pos(h1,4,100);
	printf("按照下标修改数据:");
	print_link(h1);
	
	link_del_head(h1);
	printf("头删：");
	print_link(h1);

	link_del_tail(h1);


	printf("尾删：");
	print_link(h1);

	find_pos_link(h1,2);
	find_val_link(h1,7);

	printf("----------------------------------------------------------n");

	link *h2 = create_head();
	//	for(int i=1;i<5;i++)
	//	{


	insert_link_head(h2,2);
	insert_link_head(h2,4);
	insert_link_head(h2,6);
	insert_link_head(h2,8);

	//	}
	printf("新建链表二：");
	print_link(h2);
	printf("---------------------单链表翻转--------------------------n");
	link_return(h2);
	printf("翻转后为  ：");
	print_link(h2);
	
	 printf("----------------------------------------------------------n");
	 printf("已知两个链表head1和head2各自有序，请把它们合并成一个链表n依然有序，要求用递归方法进行n");
	 printf("----------------------------------------------------------n");
	 link *h3 = create_node(0);
	 link *h4 = create_node(1);
	 for(int i=9;i>1;i--)
	 {
		 if(i%2==0)
		 {
			 insert_link_head(h3,i);
		 }
		 else{
			 insert_link_head(h4,i);
		 }
	 }
	 printf("链表3：");
	 print_link_nohead(h3);
	 printf("链表4：");
	 print_link_nohead(h4);

	 link *h5 = merge_two_lists(h3,h4);
	 printf("合并及结果为：");
	 print_link_nohead(h5);

	 return 0;
}

运行结果：

有需要可以直接免费下载，相互交流，共同学习，若有不足之处请指点。