当前位置：首页 > ds >正文

弄清C语言中的链表

ds 2025/7/5 16:24:49

弄清C语言中的链表

节点结构

链表由节点（Node）组成，每个节点包含：

数据域：存储实际数据（如整数、字符等）。
指针域：指向下一个节点的地址（单链表）或前驱和后继节点的地址（双向链表）

链表是，利用结构体，在堆上开辟内存空间去作为指针，这个指针总是指向下一个节点，结点通过指针相互串联，形成链表。

在这里插入图片描述
DATA作为结构体中自定义的数据类型；NEXT为指向链表结点的指针，通过访问NEXT，可以去访问链表的下一个结点。

//定义结点类型
//定义结点类型
typedef struct Node{int data;//数据类型struct Node* next;//指向下一个链表结点的指针
}Node;

链表类型

单向链表：节点仅包含指向下一个节点的指针。
双向链表：节点包含指向前驱和后继的指针，支持双向遍历。
循环链表：尾节点指向头节点，形成环形结构。

单链表概念和简单的设计

在这里插入图片描述

//定义结点类型
typedef struct Node {int data;       //数据类型struct Node *next;//单链表的指针域
} Node,*LinkedList;  
//Node表示结点的类型，LinkedList表示指向Node结点类型的指针类型

链表的创建

创建一个单链表的前置节点并向后逐步添加节点，一般指的是申请结点的空间，同时对一个结点赋空值(NULL)。

LinkedList listinit()
{Node* newNode = (Node*)malloc(sizeof(Node));//开辟空间if(newNode == NULL)//如果开辟空间失败{printf("申请空间失败");//exit(0);                  //开辟空间失败可以考虑直接结束程序}newNode->next = NULL;//指针指向空return;
}

注意：一定要判断是否开辟空间失败，否则生产中由于未知的情况造成空间开辟失败，仍然在继续执行代码，后果将不堪设想啦，因此养成这样的判断是很有必要的。

尾插入法创建单链表

在这里插入图片描述

//尾插法建立单链表
LinkedList LinkedListCreatT(int x)
{Node* newNode = (Node*)malloc(sizeof(Node));//开辟空间if(newNode == NULL)//如果开辟空间失败{printf("申请空间失败");//exit(0);                  //开辟空间失败可以考虑直接结束程序return 0;}newNode->next = NULL;//指针指向空//定义辅助指向Node结点类型的指针类型Node *r;r = newNode;//r始终指向终端结点，开始时指向头结点while(scanf("%d",&x) != EOF) {Node *p;p = (Node *)malloc(sizeof(Node));   //申请新的结点p->data = x;                     //结点数据域赋值r->next = p;            //将结点插入到表头L-->|1|-->|2|-->NULLr = p;}r->next = NULL;return newNode;}

//使用数组创建链表
struct node* list_create(int data[],int n)
{//创建头结点struct node* list = (struct node*)malloc(sizeof(struct node));if(list == NULL){return NULL;}//创建结构体指针指向头结点struct node* p = list;for(int i = 0;i < n;i++){struct node* tmp = (struct node*)malloc(sizeof(struct node));//设置数据tmp->value = data[i];//连接p->next = tmp;//p指针后移p = p->next;}p->next = NULL;return list;
}