C语言 数据结构之单链表基本操作
单链表的各种操作，适合于初学，也适合于复习
单链表操作介绍
1. 创建头节点
2. 创建有数据节点
3. 判断链表是否为空
4. 遍历链表(有头节点链表)
5. 遍历链表(无头节点链表)
6. 头插、头删、尾插、尾删
7. 按照顺序插入(自带排序)
8. 按照位置插入数据
9. 按照数据修改数据
10. 按照节点位置查找数据
11. 判断某个值是否在当前链表中（按数据查找数据）
12. 面试中常见：单链表翻转
13. 已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序，要求用递归方法
/*================================================================
* Copyright (C) 2021 HSW_study Ltd. All rights reserved.
*
* 文件名称：link.c
* 创 建 者：HSW
* 创建日期：2021年10月05日
* 描 述：数据结构单链表基本操作复习
*
================================================================*/
#include <stdio.h>
#include <stdlib.h>
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 error\n");
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 error\n");
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;i<pos;i++)
{
h=h->next;
}
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;i<pos;i++)
{
h = h->next;
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;i<pos;i++)
{
h = h->next;
flags++;
}
}
printf("查到下标为[%d]数据为%d\n",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("链表中没有数据为%d\n",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);
/*方法二：
pnode pri = NULL;
pri = reverse(h2);
printf("翻转后为 ：");
print_link(pri);
*/
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;
}
运行结果：
有需要可以直接免费下载，相互交流，共同学习，若有不足之处请指点。