c语言如何创建链表

admin

2026-01-26 04:51:13

世界杯克罗地亚

C语言创建链表的方法包括：定义链表节点结构、创建节点、插入节点、删除节点和遍历链表。其中，定义链表节点结构是最基础也是最关键的一步。

在C语言中，链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和一个指向下一个节点的指针。链表的创建和操作需要对指针有深入的理解和应用。下面将详细介绍如何在C语言中创建和操作链表。

一、定义链表节点结构

链表节点的定义是创建链表的第一步。在C语言中，链表节点通常使用结构体来定义。每个节点包含两个部分：存储数据的部分和指向下一个节点的指针部分。

struct Node {

int data;

struct Node* next;

};

在上面的代码中，struct Node定义了一个链表节点的结构。data是存储数据的部分，next是一个指向下一个节点的指针。

二、创建链表节点

创建链表节点是链表操作中的基础步骤。我们可以使用malloc函数在堆内存中动态分配内存来创建新的节点。

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (!newNode) {

printf("Memory allocation failedn");

exit(1);

}

newNode->data = data;

newNode->next = NULL;

return newNode;

}

在上面的代码中，createNode函数用于创建一个新的节点，并初始化节点的data和next指针。

三、插入节点

插入节点是链表操作中常见的操作。插入节点的位置可以是链表的头部、中间或尾部。

插入到链表头部

void insertAtHead(struct Node head, int data) {

struct Node* newNode = createNode(data);

newNode->next = *head;

*head = newNode;

}

在上面的代码中，insertAtHead函数用于在链表的头部插入一个新节点。head是指向链表头部的指针的指针。

插入到链表尾部

void insertAtTail(struct Node head, int data) {

struct Node* newNode = createNode(data);

if (*head == NULL) {

*head = newNode;

return;

}

struct Node* temp = *head;

while (temp->next != NULL) {

temp = temp->next;

}

temp->next = newNode;

}

在上面的代码中，insertAtTail函数用于在链表的尾部插入一个新节点。该函数首先检查链表是否为空，如果为空，则直接将新节点作为头节点；否则，遍历链表找到尾节点，并将新节点插入到尾部。

四、删除节点

删除节点也是链表操作中的重要操作。我们可以根据节点的值或位置来删除节点。

根据值删除节点

void deleteNodeByValue(struct Node head, int value) {

struct Node* temp = *head;

struct Node* prev = NULL;

if (temp != NULL && temp->data == value) {

*head = temp->next;

free(temp);

return;

}

while (temp != NULL && temp->data != value) {

prev = temp;

temp = temp->next;

}

if (temp == NULL) return;

prev->next = temp->next;

free(temp);

}

在上面的代码中，deleteNodeByValue函数用于根据节点的值删除节点。该函数首先检查头节点是否是要删除的节点，如果是，则直接删除头节点；否则，遍历链表找到要删除的节点，并更新前一个节点的next指针。

根据位置删除节点

void deleteNodeByPosition(struct Node head, int position) {

if (*head == NULL) return;

struct Node* temp = *head;

if (position == 0) {

*head = temp->next;

free(temp);

return;

}

for (int i = 0; temp != NULL && i < position - 1; i++) {

temp = temp->next;

}

if (temp == NULL || temp->next == NULL) return;

struct Node* next = temp->next->next;

free(temp->next);

temp->next = next;

}

在上面的代码中，deleteNodeByPosition函数用于根据节点的位置删除节点。该函数首先检查头节点是否是要删除的节点，如果是，则直接删除头节点；否则，遍历链表找到要删除节点的位置，并更新前一个节点的next指针。

五、遍历链表

遍历链表是链表操作中最常见的操作之一。我们可以通过遍历链表来打印节点的数据或执行其他操作。

void printList(struct Node* head) {

struct Node* temp = head;

while (temp != NULL) {

printf("%d -> ", temp->data);

temp = temp->next;

}

printf("NULLn");

}

在上面的代码中，printList函数用于遍历链表并打印每个节点的数据。该函数从头节点开始，依次访问每个节点，直到链表的末尾。

六、链表的其他操作

除了上述基本操作外，链表还有其他一些常见操作，如反转链表、查找节点、计算链表长度等。

反转链表

struct Node* reverseList(struct Node* head) {

struct Node* prev = NULL;

struct Node* curr = head;

struct Node* next = NULL;

while (curr != NULL) {

next = curr->next;

curr->next = prev;

prev = curr;

curr = next;

}

head = prev;

return head;

}

在上面的代码中，reverseList函数用于反转链表。该函数使用三个指针prev、curr和next来逐个反转节点的指针，直到链表的末尾。

查找节点

struct Node* searchNode(struct Node* head, int key) {

struct Node* temp = head;

while (temp != NULL) {

if (temp->data == key) {

return temp;

}

temp = temp->next;

}

return NULL;

}

在上面的代码中，searchNode函数用于在链表中查找节点。该函数从头节点开始，依次访问每个节点，直到找到值为key的节点或链表的末尾。

计算链表长度

int getLength(struct Node* head) {

int length = 0;

struct Node* temp = head;

while (temp != NULL) {

length++;

temp = temp->next;

}

return length;

}

在上面的代码中，getLength函数用于计算链表的长度。该函数从头节点开始，依次访问每个节点，并计数节点的数量，直到链表的末尾。

七、链表的实际应用

链表在实际应用中有很多场景，如实现队列、栈、哈希表等。以下是一些链表实际应用的示例。

实现队列

队列是一种先进先出（FIFO）的数据结构，可以使用链表来实现。

struct Queue {

struct Node* front;

struct Node* rear;

};

struct Queue* createQueue() {

struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));

queue->front = queue->rear = NULL;

return queue;

}

void enqueue(struct Queue* queue, int data) {

struct Node* newNode = createNode(data);

if (queue->rear == NULL) {

queue->front = queue->rear = newNode;

return;

}

queue->rear->next = newNode;

queue->rear = newNode;

}

int dequeue(struct Queue* queue) {

if (queue->front == NULL) {

printf("Queue is emptyn");

return -1;

}

struct Node* temp = queue->front;

int data = temp->data;

queue->front = queue->front->next;

if (queue->front == NULL) {

queue->rear = NULL;

}

free(temp);

return data;

}

在上面的代码中，Queue结构体定义了一个队列，包含指向队列头部和尾部的指针。createQueue函数用于创建一个新的队列，enqueue函数用于将数据插入到队列尾部，dequeue函数用于从队列头部移除数据。

实现栈

栈是一种后进先出（LIFO）的数据结构，可以使用链表来实现。

struct Stack {

struct Node* top;

};

struct Stack* createStack() {

struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));

stack->top = NULL;

return stack;

}

void push(struct Stack* stack, int data) {

struct Node* newNode = createNode(data);

newNode->next = stack->top;

stack->top = newNode;

}

int pop(struct Stack* stack) {

if (stack->top == NULL) {

printf("Stack is emptyn");

return -1;

}

struct Node* temp = stack->top;

int data = temp->data;

stack->top = stack->top->next;

free(temp);

return data;

}

在上面的代码中，Stack结构体定义了一个栈，包含指向栈顶的指针。createStack函数用于创建一个新的栈，push函数用于将数据压入栈顶，pop函数用于从栈顶弹出数据。

实现哈希表

哈希表是一种用于存储键值对的数据结构，可以使用链表来处理哈希冲突。

#define TABLE_SIZE 10

struct HashTable {

struct Node* table[TABLE_SIZE];

};

unsigned int hash(int key) {

return key % TABLE_SIZE;

}

struct HashTable* createHashTable() {

struct HashTable* hashTable = (struct HashTable*)malloc(sizeof(struct HashTable));

for (int i = 0; i < TABLE_SIZE; i++) {

hashTable->table[i] = NULL;

}

return hashTable;

}

void insert(struct HashTable* hashTable, int key, int value) {

unsigned int index = hash(key);

struct Node* newNode = createNode(value);

newNode->data = key;

newNode->next = hashTable->table[index];

hashTable->table[index] = newNode;

}

struct Node* search(struct HashTable* hashTable, int key) {

unsigned int index = hash(key);

struct Node* temp = hashTable->table[index];

while (temp != NULL) {

if (temp->data == key) {

return temp;

}

temp = temp->next;

}

return NULL;

}

在上面的代码中，HashTable结构体定义了一个哈希表，包含一个链表数组。hash函数用于计算键的哈希值，createHashTable函数用于创建一个新的哈希表，insert函数用于将键值对插入到哈希表中，search函数用于在哈希表中查找键值对。

八、链表的优缺点

链表作为一种常见的数据结构，具有许多优点，但也有一些缺点。

优点

动态内存分配：链表可以在需要时动态分配内存，不需要预先分配固定大小的内存。

插入和删除操作高效：在链表中插入和删除节点只需要修改指针，不需要移动其他节点。

灵活性：链表的长度可以根据需要动态变化，不受固定大小的限制。

缺点

内存开销大：链表中的每个节点都需要额外的内存来存储指针。

访问速度慢：链表的随机访问速度较慢，因为需要从头节点开始逐个遍历。

复杂性高：链表操作涉及指针的管理，容易出现指针错误和内存泄漏问题。

九、链表的优化和改进

为了提高链表的性能和减少内存开销，可以对链表进行一些优化和改进。

双向链表

双向链表是一种改进的链表，每个节点包含指向前一个节点和下一个节点的指针。双向链表可以更高效地进行插入、删除和遍历操作。

struct DNode {

int data;

struct DNode* prev;

struct DNode* next;

};

struct DNode* createDNode(int data) {

struct DNode* newNode = (struct DNode*)malloc(sizeof(struct DNode));

newNode->data = data;

newNode->prev = NULL;

newNode->next = NULL;

return newNode;

}

在上面的代码中，DNode结构体定义了一个双向链表节点，包含数据、前驱指针prev和后继指针next。createDNode函数用于创建一个新的双向链表节点。

循环链表

循环链表是一种改进的链表，链表的尾节点指向头节点，形成一个环。循环链表可以更高效地进行循环遍历操作。

struct Node* createCircularList(int data) {

struct Node* newNode = createNode(data);

newNode->next = newNode;

return newNode;

}

void insertAtEndCircular(struct Node* head, int data) {

struct Node* newNode = createNode(data);

struct Node* temp = head;

while (temp->next != head) {

temp = temp->next;

}

temp->next = newNode;

newNode->next = head;

}

在上面的代码中，createCircularList函数用于创建一个循环链表，insertAtEndCircular函数用于在循环链表的尾部插入一个新节点。

十、总结

链表是一种常见的数据结构，具有动态内存分配、插入和删除操作高效、灵活性强等优点，但也有内存开销大、访问速度慢、复杂性高等缺点。通过定义链表节点结构、创建节点、插入节点、删除节点和遍历链表等操作，可以在C语言中实现链表。链表在实际应用中有很多场景，如实现队列、栈、哈希表等。为了提高链表的性能和减少内存开销，可以对链表进行一些优化和改进，如双向链表和循环链表。理解和掌握链表的创建和操作，对于深入学习数据结构和算法具有重要意义。

第一届世界杯_瑞典世界杯 - cytear.com

c语言如何创建链表