C语言之链表操作
概述
单链表是一种数据结构，每个节点包含数据域和指向下一节点的指针域，只能单向依次访问节点。
双链表同样是数据结构，其节点除数据域外，还有指向前驱和后继节点的两个指针域，可双向遍历访问节点。
定义节点
一个节点就是一个结构体变量
1,单链表节点
typedef struct node
{
//数据域
int num;
char c;
//地址域
struct node *next;
}Node;
2,双链表节点
typedef struct node
{
//数据域
int num;
char c;
//地址域
struct node *next;
struct node *head;
}Node;
创建链表
静态创建
//静态组建链表
#include<stdio.h>typedef struct node
{
//数据域
int num;
//地址域
struct node *next;
struct node *head;
}Node;//链表的遍历
void printf_link(Node *head)
{
Node *n = head;
while(1)
{
printf("%d\n",n->num);
if(n->next==NULL)
{
break;
}
n=n->next;
}
}int main()
{
Node n01 = {1,NULL,NULL};
Node n02 = {2,NULL,NULL};
Node n03 = {3,NULL,NULL};
n01.next=&n02;
n02.next=&n03;
n03.head=&n02;
n02.head=&n01;
printf_link(&n01);return 0;
}
动态创建
//动态创建链表
#include<stdio.h>
#include<stdlib.h>typedef struct node
{
//数据域
int num;
//地址域
struct node *next;
struct node *head;
}Node;void printf_link(Node *head)
{
Node *n = head;
while(1)
{
printf("%d\n",n->num);
if(n->next==NULL)
{
break;
}
n=n->next;
}
}int main()
{
Node*n01=(Node*)calloc(1,sizeof(Node));
Node*n02=(Node*)calloc(1,sizeof(Node));
Node*n03=(Node*)calloc(1,sizeof(Node));
Node*n04=(Node*)calloc(1,sizeof(Node));
n01->head = NULL;
n01->next = n02;
n02->next = n03;
n03->next = n04;
n04->next = NULL;
n04->head = n03;
n03->head = n02;
n02->head = n01;n01->num = 4;
n02->num = 3;
n03->num = 2;
n04->num = 1;printf_link(n01);
return 0;
}
链表的操作
添加
//在链表尾部添加节点
//head:链表的首节点
Node* add_node(Node *head,Node *newNode)
{
//判断是否有首节点
if(head == NULL)
{
//没有首节点,那么本次添加的节点就是首节点
head = newNode;
return head;
}
//有首节点,查找当前链表的最后一个节点
Node *n = head;
while(n->next !=NULL)
{
n=n->next;
}
//当循环结束后n就是最后一个节点
n->next = newNode;
//将新节点的上一个节点设置为原来的最后一个节点
newNode->head = n;
return head;
}
遍历
//遍历链表
//head:要遍历的链表的首节点
void printf_link(Node *head)
{
Node *n = head;
//判断当前节点是否为NULL
while(n != NULL)
{
//当前节点不为空,打印其数据
printf("%d\n",n->num)
//移动当前节点到下一个节点
n=n->next;
}
}
删除
//删除指定节点
//head:头节点,delNode:要删除的节点
Node* del_node(Node *head,Node *delNode)
{
if(head ==NULL)
{
printf("没有首节点\n");
return NULL;
}
if(delNode == NULL)
{
printf("要删除的节点为NULL\n");
return head;
}
if(head == delNode)
{
//要删除的节点为首节点,将下一个节点设为首节点
head=head->next;
//将当前的首节点的前驱置空
head->head = NULL;
//释放原来的首节点
free(delNode);
return head;
}
//要删除的节点不是首节点和尾节点时
Node *n = head;
while(n!=delNode && n!=NULL)
{
n=n->next;
}
if(n == NULL)
{
printf("没有要删除的节点\n");
return head;
}
//如果要删除的节点为最后一个节点
if(n->next == NULL)
{
Node *headNode = n->head;
headNode->next = NULL;
free(n)
return head;
}
//当n为要删除的节点时
Node*headNode = n->head;//取出n的上一个节点
Node*nextNode = n->next;//取出n的下一个节点
free(n);释放n
headNode->next = nextNode;
headNode->head = headNode;
return head;
}
查找
按值查找
//按结构体中存储的值查找对应的节点
//head:首节点 num:查找的值
Node *find_v(Node *head,int num)
{
Node *n =head;
while(n !=NULL)
{
if(n->num == num)
{
return n;
}
n=n->next;
}
return NULL;
}
按位查找
//按结构体在链表中的位置查找对应的节点
//head:首节点 index:下标
//注意:链表本身没有下标的概念
Node* find-i(Node *head,int index)
{
Node *n = head;
int i=0;
while(n!=NULL)
{
if(i == index)
{
return n;
}
n = n->next;
i++;
}
return NULL;
}
修改
按值修改
//根据值修改指定节点的值
//head:首节点,num:查找的值,newNum:修改后的值
void updata_v(Node *head,int num,int newNum)
{
Node *n = find_v(head,num);
if(n == NULL)
return;
n->num = newNum;
}
按位查找
//根据位置修改指定节点的值
//head:首节点,index:修改后的位置,newNum:修改后的值
void updata_i(Node *head,int index,int newNum)
{
Node *n = find_i(head,index);
if(n ==NULL)
return;
n->num = newNum;
}
插入
//按位插入新节点
//head:首节点,index:位置,newNode:新节点
Node* insert(Node *head,int index,Node *newNode)
{
if(index == 0)
{
newNode->next = head;
head->head = newNode;
head = newNode;
//将链表的头指针
head指向新插入的节点newNodereturn head;
}
Node *n = find_i(head,index);
//当插入节点是尾节点
if(n == NULL)
{
add_node(head,newNode);
return head;
}
Node *headNode = n->head;
headNode->next = newNode;
newNode->head = headNode;
newNode->next = n;
n->head = newNode;
return head;
}
获取链表长度
//获取链表长度
int get_len(len *head)
{
int i = 0;
Node *n = head;
while(n !=NULL)
{
i++;
n=n->next;
}
return i;
}
逆序排序
void printf_link(Node *head)
{
int len = get_len(head);
int index = len -1;
Node *n = (head,index);
while(n !=NULL)
{printf("%d\n",n->num);
n = n->head;
}
}
释放链表
void free_link(Node *head)
{
Node *n = head;
while(n != NULL)
{Node *nextNode = n->next;
free(n);
n=nextNode;
}
}