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 指向新插入的节点 newNode

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

}

}