C++链表操作入门

数据结构基础：链表操作入门

在计算机科学中，数据结构是组织和存储数据的方式，它对程序的执行效率有着至关重要的影响。链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。在本文中，我们将通过C++语言探讨链表的基本概念和操作。

链表的基本概念

链表中的每个节点通常包含两个部分：存储数据的 val 和指向下一个节点的 next 指针。在单链表中，每个节点只有一个指向后续节点的指针。这是链表节点的基本结构：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL) {}
};

链表的基本操作

输出链表

首先，我们需要一种方法来输出链表中的所有元素，以便于观察链表的内容。以下是输出链表的函数：

void print(ListNode *n) {
    ListNode *p = n;
    while(p != NULL) {
        cout << p->val << "->";
        p = p->next;
    }
    cout << endl;
}

插入节点

在链表中插入新节点是一个常见的操作。我们可以在链表的任意位置插入一个新节点：

void insert(ListNode *n, int val) {
    ListNode *p = new ListNode(val);
    p->next = n->next;
    n->next = p;
}

删除节点

删除操作涉及找到特定节点并将其从链表中移除。以下是删除节点的函数：

void remove(ListNode *n) {
    if(n->next == NULL) {
        return;
    }
    ListNode *t = n->next;
    n->val = t->val;
    n->next = t->next;
    delete(t);
}

查找值

在链表中查找特定值的位置也是一个基本操作。以下是查找函数的实现：

int find(ListNode *n, int val) {
    int index = 1;
    while(n != NULL) {
        if(n->val == val) {
            return index;
        } else {
            n = n->next;
            index++;
        }
    }
    return -1;
}

完整的链表操作示例

在 main 函数中，我们创建了一个简单的链表，并演示了如何进行插入、删除和查找操作：

int main() {
    ListNode *n0 = new ListNode(1);
    ListNode *n1 = new ListNode(2);
    // ... 其他节点创建和链接

    // 输出链表
    print(n0);

    // 在链表中插入节点
    insert(n0, 666);
    print(n0);

    // 删除链表中的节点
    remove(n0);
    print(n0);

    // 查找节点
    cout << find(n0, 2) << endl;
    cout << find(n0, 8888) << endl;

    return 0;
}

结语

链表是一种强大且灵活的数据结构，它在内存分配和动态数据存储方面具有优势。理解链表的工作原理和操作对于任何学习计算机科学的学生或编程爱好者都是基础且必要的。通过本文的示例和解释，读者应该能够对链表有一个基本的了解，并能够开始在自己的程序中实现和使用链表。

本文适合青少年学生和编程教师作为学习数据结构链表知识的入门材料。通过实际的代码示例，读者可以更容易地理解链表的工作原理和操作方法。希望本文能够帮助你在编程的道路上更进一步！

完整代码：

#include<bits/stdc++.h>
using namespace std;
struct ListNode{	//链表节点结构体 
	int val; 		//值 
	ListNode *next; //节点指针
	ListNode(int x):val(x),next(NULL){}  //构造函数,使用链表初始化 
}; 
//1.输出链表 
void print(ListNode *n){
	ListNode *p = n;
	while(p!=NULL){ 		//当链表不为空 
		cout<<p->val<<"->"; //输出节点的值 
		p = p->next; 		//更新p指针指向 
	}
	cout<<endl; 
}

//2.插入节点 
void insert(ListNode *n, int val){
	ListNode *p = new ListNode(val); //初始化p节点
	ListNode *t = n->next; //t指向 n的下一个节点
	p->next = t; //p的下一个节点是t
	n->next = p; //n的下一个节点就是p 
}

//3.删除节点
void remove(ListNode *n){
	if(n->next==NULL){
		return ;
	}
	//开始删除
	ListNode *t = n->next; //t指向 n的下一个节点
	n->val = t->val; 	//后面的节点值往前推一位
	n->next = t->next; //节点也往前推一位 
	delete(t); 		  //删除临时节点，释放空间 
} 

//4.查找值 
int find(ListNode *n,int val){
	int index = 1; 			//从第一个节点位置查
	while(n!=NULL){
		if(n->val==val){   //节点值==查值 
			return index; //返回位置 
		}
		else{
			n = n->next;  //节点后移 
			index++; 	 //位置+1 
		} 
	}
	return -1; //查不到，返回-1 
} 

int main(){
	// n0=1 n1=2 n2=3 n3=5 n4=6 
	ListNode *n0 = new ListNode(1);
	ListNode *n1 = new ListNode(2);
	ListNode *n2 = new ListNode(3);
	ListNode *n3 = new ListNode(5);
	ListNode *n4 = new ListNode(6);
	//节点连接：1->2->3->5->6 
	n0->next = n1;
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	
	//1.输出函数：从n0节点往后输出链表 
	print(n0); 
	
	//2.插入：从n0节点位置后插入节点 
	insert(n0,666);
	print(n0); 
	
	//3.删除: 删除n0节点
	remove(n0);
	print(n0); 
	
	//4.查找值在不在链表中，在输出位置，不在输出-1
	cout<<find(n0,2)<<endl; 
	cout<<find(n0,8888)<<endl; 
	return 0;
}