C语言/C++实现链表的详细教程

小灰灰 2024-03-16 18:14 58阅读 0赞

### C语言/C++实现链表的详细教程 ###

#### 1. 什么是链表 ####

链表是一种常用的数据结构，它由一系列节点组成，每个节点包含两部分内容：数据和指向下一个节点的指针,最后一个节点指向空。链表的节点可以动态添加和删除，因此可以方便地进行插入、删除等操作。链表有多种类型，包括单向链表、双向链表和循环链表等。

##### 1.1 单向链表（Singly Linked List） #####

单向链表是最简单的链表类型，它的每个节点只包含一个指向下一个节点的指针。单向链表的优点是插入和删除节点的速度较快，但查找节点的速度较慢。单向链表的数据结构如下所示：

cstruct ListNode {
        
        int val;  // 节点的值
        struct ListNode *next;  // 指向下一个节点的指针
    };

##### 1.2 双向链表（Doubly Linked List） #####

双向链表是在单向链表的基础上增加了一个指向前一个节点的指针。这样一来，双向链表可以从前往后遍历，也可以从后往前遍历，但相应地，插入和删除节点的操作会稍微复杂一些。双向链表的数据结构如下所示：

cstruct ListNode {
        
        int val;  // 节点的值
        struct ListNode *prev;  // 指向前一个节点的指针
        struct ListNode *next;  // 指向下一个节点的指针
    };

##### 1.3 循环链表（Circular Linked List） #####

循环链表是一种特殊的链表类型，它的最后一个节点指向第一个节点（或者说，第一个节点指向最后一个节点）。这样一来，循环链表可以无限循环下去，因此常用于循环队列等数据结构中。循环链表的数据结构和单向链表或双向链表类似，只是最后一个节点的指针指向第一个节点。

**本教程主要演示的是单向链表的使用。**

#### 2. 节点的定义 ####

首先，我们需要定义链表的节点结构。每个节点包含一个数据元素和一个指向下一个节点的指针。在C语言中，我们可以使用结构体来定义节点。

typedef struct Node {
        
        int data;           // 数据元素
        struct Node* next;  // 指向下一个节点的指针
    } Node;

#### 3. 创建和初始化链表 ####

下面是一个函数，用于创建并初始化一个空链表。

Node* createLinkedList() {
        
        return NULL;  // 返回空链表
    }

#### 4. 插入节点 ####

接下来，我们需要实现在链表中插入新节点的功能。我们可以根据需要在链表的开头、末尾或中间插入新节点。

// 插入节点到链表开头
    Node *insertAtBeginning(Node *head, int data) {
        
        // 创建新节点
    	Node *newNode = (Node*)malloc(sizeof(Node));  
        // 设置节点数据
    	newNode->data = data;  
    	// 将新节点指向原来的头节点                        
        newNode->next = head; 
    	// 返回新的链表头节点                         
        return newNode;                                
    }
    
    // 插入节点到链表末尾
    Node *insertAtEnd(Node *head, int data) {
        
        // 创建新节点
    	Node *newNode = (Node*)malloc(sizeof(Node)); 
        newNode->data = data;
        // 将新节点的下一个节点指针设置为NULL
        newNode->next = NULL;                          
    	// 如果链表为空，将新节点作为链表的唯一节点
        if (head == NULL) {
        
            return newNode;  
        }
    
        Node* current = head;
    
        // 遍历链表直到达到最后一个节点
        while (current->next != NULL) {
        
            current = current->next;
        }
    	// 将新节点插入到已有链表的末尾
        current->next = newNode;  
        // 返回原来的头节点
        return head;              
    }
    
    // 在指定位置插入节点
    Node* insertAtPosition(Node* head, int data, int position) {
        
        // 创建新节点
    	Node* newNode = (Node*)malloc(sizeof(Node));  
        newNode->data = data;
    	 // 如果插入位置为0，则将新节点作为新的头节点
        if (position == 0) {
        
            newNode->next = head;
            return newNode; 
        }
        Node* current = head;
    
        // 找到插入位置的前一个节点
        for (int i = 0; i < position - 1; i++) {
        
            if (current == NULL) {
        
                printf("位置超出链表存储范围。\n");
                return head;
            }
            current = current->next;
        }
    	// 将新节点的next指针指向当前位置的节点
        newNode->next = current->next;  
        // 将当前位置的节点指向新节点
    	current->next = newNode;        
        // 返回原来的头节点
    	return head;                    
    }

#### 5. 删除节点 ####

我们也可以从链表中删除节点。下面是一些用于删除节点的函数示例。

// 从链表开头删除节点
    Node* deleteAtBeginning(Node* head) {
        
        if (head == NULL) {
        
            printf("链表为空");
            return NULL;
        }
    
        Node* temp = head;
        // 更新头节点
        head = head->next;  
        // 释放删除节点的内存
        free(temp);  
    	// 返回新的头节点       
        return head;        
    }
    
    // 从链表末尾删除节点
    Node* deleteAtEnd(Node* head) {
        
        if (head == NULL) {
        
            printf("链表为空！！！\n");
            return NULL;
        }
    	// 如果只有一个节点，直接删除
        if (head->next == NULL) {
        
            free(head);   
            return NULL;
        }
    
        Node *current = head, *prev;
        // 找到倒数第二个节点
        while (current->next != NULL) {
        
            prev = current;
            current = current->next;
        }
    	//将倒数第二个节点的next指针设置为NULL，删除最后一个节点
        prev->next = NULL;  
        // 释放删除节点的内存
    	free(current);      
        // 返回原来的头节点
    	return head;        
    }
    
    // 根据数据值删除节点
    Node* deleteByValue(Node* head, int data) {
        
        if (head == NULL) {
        
            printf("链表为空！！！\n");
            return NULL;
        }
        Node *current = head, *prev;
        // 遍历链表找到要删除的节点
        while (current != NULL && current->data != data) {
        
            prev = current;
            current = current->next;
        }
    
        if (current == NULL) {
        
            printf("数据不存在！！！\n");
            return head;
        }
    
        if (current == head) {
        
            //如果删除节点是头节点，则更新头节点
    		head = head->next;  
        } else {
        
        	//将前一个节点的next指针跳过删除节点
            prev->next = current->next; 
        }
        free(current);// 释放删除节点的内存
        return head;
    }

#### 6. 打印链表 ####

为了验证链表的操作，我们可以编写一个函数来打印链表的所有节点。

//打印链表数据 
    void printList(Node* head) {
        
        Node* current = head;
        printf("链表所存数据: ");
    	//表头为空，结束循环 
        while (current != NULL) {
        
            printf("%d ", current->data);
            current = current->next;
        }
        printf("\n");
    }

#### 7. 测试代码 ####

我们可以编写一段测试代码来验证我们的链表代码：

//主函数 
    int main() {
        
    	//创建链表 
        Node* head = createLinkedList();
        printf("链表已经创建完成，可以正常使用！！！\n");
    	while(true){
        
    		printf("1、添加新的数据到链表头。\n"); 
    		printf("2、添加新的数据到链表尾。\n");
    		printf("3、添加新的数据到固定位置。\n");
    		printf("4、删除链表头的数据。\n");
    		printf("5、删除链表尾的数据。\n");
    		printf("6、删除指定数据。\n");
    		printf("7、退出程序。\n");
    		printf("请输入你的选择：");
    		int ch;
    		bool flag=false;
    		scanf("%d",&ch);
    		system("cls");
    		switch(ch){
        
    			case 1:
    				int insertN;
    				printf("请输入需要插入的数据：");
    				scanf("%d",&insertN); 
    				head = insertAtBeginning(head, insertN);
    				break;
    			case 2:
    				int insertEndN;
    				printf("请输入需要插入的数据：");
    				scanf("%d",&insertEndN);
    				head = insertAtEnd(head, insertEndN);
    				break;
    			case 3:
    				int insertPosN,pos;
    				printf("请输入需要插入的数据和位置：");
    				scanf("%d %d",&insertPosN,&pos);
    				head = insertAtPosition(head, insertPosN, pos-1);
    				break;
    			case 4:
    				head = deleteAtBeginning(head);
    				break;
    			case 5:
    				head = deleteAtEnd(head);
    				break;
    			case 6:
    				int delN;
    				printf("请输入需要删除的数据：");
    				scanf("%d",&delN); 
    				head = deleteByValue(head, delN);
    				break;
    			case 7:printf("程序结束，欢迎使用。\n");exit(0);
    			default:
    				printf("您的输入有误，请检查后重新输入！\n");
    				flag=true;
    				break;
    		}
    		if(!flag){
        
    			printf("****-----------------------------****\n");
    			printList(head);
    			printf("****-----------------------------****\n\n");
    		}
    		getchar();
    	}
        return 0;
    }

#### 8. 总结 ####

恭喜你！你已经完成了C语言实现链表的教程。链表是一种非常有用的数据结构，可以在运行时动态管理数据。通过学习链表的实现，您可以对如何操作和管理数据有更深入的了解。希望本教程对你有所帮助，谢谢！

#### 9. 完整代码 ####

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node {
        
        int data;           // 数据元素
        struct Node *next;  // 指向下一个节点的指针
    } Node;
    
    //创建并初始化链表
    Node *createLinkedList() {
        
        return NULL;  // 返回空链表
    }
    
    // 插入节点到链表开头
    Node *insertAtBeginning(Node *head, int data) {
        
        // 创建新节点
    	Node *newNode = (Node*)malloc(sizeof(Node));  
        // 设置节点数据
    	newNode->data = data;  
    	// 将新节点指向原来的头节点                        
        newNode->next = head; 
    	// 返回新的链表头节点                         
        return newNode;                                
    }
    
    // 插入节点到链表末尾
    Node *insertAtEnd(Node *head, int data) {
        
        // 创建新节点
    	Node *newNode = (Node*)malloc(sizeof(Node)); 
        newNode->data = data;
        // 将新节点的下一个节点指针设置为NULL
        newNode->next = NULL;                          
    	// 如果链表为空，将新节点作为链表的唯一节点
        if (head == NULL) {
        
            return newNode;  
        }
    
        Node* current = head;
    
        // 遍历链表直到达到最后一个节点
        while (current->next != NULL) {
        
            current = current->next;
        }
    	// 将新节点插入到已有链表的末尾
        current->next = newNode;  
        // 返回原来的头节点
        return head;              
    }
    
    // 在指定位置插入节点
    Node* insertAtPosition(Node* head, int data, int position) {
        
        // 创建新节点
    	Node* newNode = (Node*)malloc(sizeof(Node));  
        newNode->data = data;
    	 // 如果插入位置为0，则将新节点作为新的头节点
        if (position == 0) {
        
            newNode->next = head;
            return newNode; 
        }
        Node* current = head;
    
        // 找到插入位置的前一个节点
        for (int i = 0; i < position - 1; i++) {
        
            if (current == NULL) {
        
                printf("位置超出链表存储范围。\n");
                return head;
            }
            current = current->next;
        }
    	// 将新节点的next指针指向当前位置的节点
        newNode->next = current->next;  
        // 将当前位置的节点指向新节点
    	current->next = newNode;        
        // 返回原来的头节点
    	return head;                    
    }
    
    // 从链表开头删除节点
    Node* deleteAtBeginning(Node* head) {
        
        if (head == NULL) {
        
            printf("链表为空");
            return NULL;
        }
    
        Node* temp = head;
        // 更新头节点
        head = head->next;  
        // 释放删除节点的内存
        free(temp);  
    	// 返回新的头节点       
        return head;        
    }
    
    // 从链表末尾删除节点
    Node* deleteAtEnd(Node* head) {
        
        if (head == NULL) {
        
            printf("链表为空！！！\n");
            return NULL;
        }
    	// 如果只有一个节点，直接删除
        if (head->next == NULL) {
        
            free(head);   
            return NULL;
        }
    
        Node *current = head, *prev;
        // 找到倒数第二个节点
        while (current->next != NULL) {
        
            prev = current;
            current = current->next;
        }
    	//将倒数第二个节点的next指针设置为NULL，删除最后一个节点
        prev->next = NULL;  
        // 释放删除节点的内存
    	free(current);      
        // 返回原来的头节点
    	return head;        
    }
    
    // 根据数据值删除节点
    Node* deleteByValue(Node* head, int data) {
        
        if (head == NULL) {
        
            printf("链表为空！！！\n");
            return NULL;
        }
        Node *current = head, *prev;
        // 遍历链表找到要删除的节点
        while (current != NULL && current->data != data) {
        
            prev = current;
            current = current->next;
        }
    
        if (current == NULL) {
        
            printf("数据不存在！！！\n");
            return head;
        }
    
        if (current == head) {
        
            //如果删除节点是头节点，则更新头节点
    		head = head->next;  
        } else {
        
        	//将前一个节点的next指针跳过删除节点
            prev->next = current->next; 
        }
        free(current);// 释放删除节点的内存
        return head;
    }
    //打印链表数据 
    void printList(Node* head) {
        
        Node* current = head;
        printf("链表所存数据: ");
    	//表头为空，结束循环 
        while (current != NULL) {
        
            printf("%d ", current->data);
            current = current->next;
        }
        printf("\n");
    }
    
    //主函数 
    int main() {
        
    	//创建链表 
        Node* head = createLinkedList();
        printf("链表已经创建完成，可以正常使用！！！\n");
    	while(true){
        
    		printf("1、添加新的数据到链表头。\n"); 
    		printf("2、添加新的数据到链表尾。\n");
    		printf("3、添加新的数据到固定位置。\n");
    		printf("4、删除链表头的数据。\n");
    		printf("5、删除链表尾的数据。\n");
    		printf("6、删除指定数据。\n");
    		printf("7、退出程序。\n");
    		printf("请输入你的选择：");
    		int ch;
    		bool flag=false;
    		scanf("%d",&ch);
    		system("cls");
    		switch(ch){
        
    			case 1:
    				int insertN;
    				printf("请输入需要插入的数据：");
    				scanf("%d",&insertN); 
    				head = insertAtBeginning(head, insertN);
    				break;
    			case 2:
    				int insertEndN;
    				printf("请输入需要插入的数据：");
    				scanf("%d",&insertEndN);
    				head = insertAtEnd(head, insertEndN);
    				break;
    			case 3:
    				int insertPosN,pos;
    				printf("请输入需要插入的数据和位置：");
    				scanf("%d %d",&insertPosN,&pos);
    				head = insertAtPosition(head, insertPosN, pos-1);
    				break;
    			case 4:
    				head = deleteAtBeginning(head);
    				break;
    			case 5:
    				head = deleteAtEnd(head);
    				break;
    			case 6:
    				int delN;
    				printf("请输入需要删除的数据：");
    				scanf("%d",&delN); 
    				head = deleteByValue(head, delN);
    				break;
    			case 7:printf("程序结束，欢迎使用。\n");exit(0);
    			default:
    				printf("您的输入有误，请检查后重新输入！\n");
    				flag=true;
    				break;
    		}
    		if(!flag){
        
    			printf("****-----------------------------****\n");
    			printList(head);
    			printf("****-----------------------------****\n\n");
    		}
    		getchar();
    	}
        return 0;
    }

以上就是C语言实现链表的详细教程。希望对您有所帮助！如果您还有其他问题，请随时提问。