C语言——头插法和尾插法动态创建链表
在C语言中,动态创建列表通常指的是使用链表(Linked List)这种数据结构。链表由一系列节点(Node)组成,每个节点包含数据部分和指向下一个节点的指针。根据插入节点的位置不同,链表的插入操作可以分为头插法和尾插法。下面将详细介绍这两种方法。
头插法动态创建链表
头插法是将新节点插入到链表的头部,这样新节点将成为链表的第一个节点。由于每次插入都在头部进行,因此这种方法不需要遍历链表来找到尾部,插入操作的时间复杂度为O(1)。
步骤
- 定义节点结构体:包含一个数据域和一个指向下一个节点的指针。
- 初始化链表:通常将头指针初始化为NULL,表示一个空链表。
- 创建新节点:使用
malloc
或calloc
动态分配内存给新节点。 - 插入新节点:将新节点的
next
指针指向当前的头节点,然后更新头指针指向新节点。 - 重复:根据需要重复步骤3和4,直到所有节点都被插入。
示例代码
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 头插法插入节点
void insertAtHead(Node** head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->next = *head;
*head = newNode;
}
// 打印链表
void printList(Node* head) {
Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
// 释放链表内存
void freeList(Node* head) {
Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}
int main() {
Node* list = NULL; // 初始化空链表
insertAtHead(&list, 1);
insertAtHead(&list, 2);
insertAtHead(&list, 3);
printList(list); // 输出: 3 -> 2 -> 1 -> NULL
freeList(list); // 释放链表内存
return 0;
}
尾插法动态创建链表
尾插法是将新节点插入到链表的尾部,这样新节点将成为链表的最后一个节点。由于每次插入都需要找到链表的尾部,因此这种方法在最坏情况下的时间复杂度为O(n),其中n是链表的长度。
步骤
- 定义节点结构体:与头插法相同。
- 初始化链表:将头指针和尾指针都初始化为NULL。
- 创建新节点:使用
malloc
或calloc
动态分配内存给新节点。 - 检查链表是否为空:
- 如果为空(头指针为NULL),新节点既是头节点也是尾节点。
- 如果不为空,将尾节点的
next
指针指向新节点,并更新尾指针指向新节点。
- 更新头指针(可选):如果链表之前为空,现在需要更新头指针指向新节点(但这一步在插入操作中通常已经隐含在更新尾指针的操作中了)。
- 重复:根据需要重复步骤3、4和5,直到所有节点都被插入。
示例代码
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 尾插法插入节点
void insertAtTail(Node** head, Node** tail, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) { // 链表为空
*head = newNode;
*tail = newNode;
} else {
(*tail)->next = newNode;
*tail = newNode;
}
}
// 打印链表
void printList(Node* head) {
// 与头插法示例中的打印函数相同
}
// 释放链表内存
void freeList(Node* head) {
// 与头插法示例中的释放函数相同
}
int main() {
Node* list = NULL; // 初始化空链表
Node* tail = NULL; // 初始化尾指针
insertAtTail(&list, &tail, 1);
insertAtTail(&list, &tail, 2);
insertAtTail(&list, &tail, 3);
printList(list); // 输出: 1 -> 2 -> 3 -> NULL
freeList(list); // 释放链表内存
return 0;
}
注意事项
- 内存管理:确保在链表不再需要时释放所有节点的内存。
- 错误处理:检查
malloc
是否成功,并在失败时适当处理。 - 链表遍历:可以通过遍历链表来验证插入操作是否正确。
- 头指针和尾指针:在尾插法中,同时维护头指针和尾指针可以方便地实现插入操作,而不需要每次都遍历链表找到尾部。
简易代码:
#include<stdio.h>
#include<stdlib.h>
struct Test{
int data;
struct Test *next;
};
void printLink(struct Test *head)
{
while(1){
if(head != NULL){
printf("%d ",head->data);
head = head->next;
}else{
putchar('\n');
break;
}
}
}
struct Test* insertFromBehind(struct Test *head,struct Test *new)
{
struct Test *p = head;
if(p == NULL){
head = new;
return head;
}
while(p->next != NULL){
p = p->next;
}
p->next = new;
return head;
}
struct Test* creatFromTail(struct Test* head)
{
struct Test *new;
while(1){
new = (struct Test*)malloc(sizeof(struct Test));
printf("input your number of node\n");
scanf("%d",&(new->data));
if(new->data == 0){
printf("0 quit\n");
free(new);
return head;
}
head = insertFromBehind(head,new);
}
}
struct Test* insertFromForward(struct Test *head,struct Test *new)
{
if(head == NULL){
head = new;
}else{
new->next = head;
head = new;
}
return head;
}
struct Test* creatFromHead(struct Test* head)
{
struct Test *new;
while(1){
new = (struct Test*)malloc(sizeof(struct Test));
printf("input your number of node\n");
scanf("%d",&(new->data));
if(new->data == 0){
printf("0 quit\n");
free(new);
return head;
}
head = insertFromForward(head,new);
}
}
int main()
{
struct Test *head = NULL;
printf("this is link be creative insert head\n");
head = creatFromHead(head);
printLink(head);
struct Test *head1 = NULL;
printf("this is link be creative insert tail\n");
head1 = creatFromTail(head1);
printLink(head1);
return 0;
}
原文地址:https://blog.csdn.net/weixin_45720999/article/details/143019954
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!