数据结构 链表类定义代码上课讲义

数据结构—链表详解浅谈数据结构——链表本篇随笔就数据结构——链表进⾏讲解。

链表是⼀种特别实⽤的数据结构，我把它理解为数组的升级版，也就是在数组的基础上，它能做到在任意位置添加或者删除元素，⽽不影响其他元素。

链表还是我们进⾏图论学习时，图的常⽤存储⽅式——邻接表（链式前向星）的实现基础。

学习链表需要读者具有⼀定的语法基础，最好会⼀点点指针。

（不会也没关系，我们主要讲解数组模拟链表）什么是链表链表，顾名思义，就是带链的表。

我已经说过，链表属于数组的加强版。

那我们可以借助数组来理解链表：如果说数组是⼀长排连在⼀起的“⽅块”的话，那么链表就是把这些⽅块“拉开“，每个⽅块还有两个箭头，分别指向这个⽅块前⾯的⽅块和后⾯的⽅块。

这样我们就可以理解，为什么链表可以⽀持随机插⼊和删除了。

从某种意义上来说，这⾥的每⼀个⽅块都是离散的，我们在某两点插⼊的时候，只需要把要插⼊的元素，这个元素⽬标位置前⾯的元素、后⾯的元素的箭头改⼀下，就做到了插⼊的操作。

删除同理。

链表的实现原理根据刚才的理解，我们可以发现，我们可以⽤⼀个结构体来模拟每⼀个⽅块，结构体中存⼀个元素和两个指针，指针分别指向上⼀个元素的位置和下⼀个元素的位置。

但是蒟蒻不会指针指针的实现⽐较⿇烦，⽽且在调试的时候也不是很理想。

所以我们来想指针的本质就是告诉你⼀个位置，那么针对于”加强数组“链表来讲，这个位置可以⽤什么来表⽰呢？对，数组下标。

所以我们刚才的结构体就可以简化，变成存⼀个元素和两个int变量（存储数组下标）。

这样，我们就可以⽤结构体数组模拟链表的实现。

链表基本操作的代码实现链表实现的精髓就是更改指针，改掉了三个元素（前，中，后）的指针使链表合法，就完成了我们需要做的操作，本部分不再就每段代码进⾏过多讲解，请⼤家⾃⾏理解代码含义，最好借助纸笔推演，看的会更明⽩⼀些。

(1)初始化我们初始化链表的时候，要根据题⽬意思处理开头的第⼀个元素，这很重要！并且，我们把所有的指针都清成-1，这样保证了链表初始绝对合法。

c++链表的详细讲解在C++中，链表是一种常见的数据结构，用于存储有序的元素集合。

每个元素在链表中都有一个唯一的地址，并且通过指针链接在一起。

下面是对C++链表的详细讲解：1.定义链表节点：链表由节点组成，每个节点包含两个部分：数据和指向下一个节点的指针。

在C++中，我们可以定义一个结构体来表示节点，如下所示：cpp复制代码struct Node {int data; // 存储数据Node* next; // 指向下一个节点的指针};2.创建链表：要创建链表，我们需要创建一个指向链表第一个节点的头指针。

头指针可以指向链表的第一个节点或为空（表示空链表）。

以下是如何创建空链表的代码示例：cpp复制代码Node* head = nullptr;3.插入节点：要向链表中插入节点，我们需要遵循以下步骤：a. 创建一个新的节点。

b. 将数据存储在新节点中。

c. 将新节点的next指针指向当前链表的最后一个节点（或空节点）。

d. 如果链表为空，将头指针指向新节点。

否则，找到链表的最后一个节点，并将其next指针指向新节点。

以下是向链表中插入节点的代码示例：cpp复制代码Node* createNode(int data) {Node* newNode = new Node(); // 创建新节点newNode->data = data; // 将数据存储在新节点中newNode->next = nullptr; // 将新节点的next指针初始化为nullptrreturn newNode; // 返回新节点}void insertNode(Node* head, int data) {Node* newNode = createNode(data); // 创建新节点if (head == nullptr) { // 如果链表为空，将头指针指向新节点head = newNode;} else {Node* current = head; // 找到链表的最后一个节点while (current->next != nullptr) {current = current->next;}current->next = newNode; // 将最后一个节点的next指针指向新节点}}4.删除节点：要从链表中删除节点，我们需要遵循以下步骤：a. 找到要删除的节点。

数据结构--链表⼊门超详细解析（简单易懂纯原篇）个⼈博客:链表的基础概念这⾥就不讲了，随便⼀个搜索引擎就能找到⽆数答案，我这⾥想讲点别⼈不会讲的东西，以及尝试如何让⼀窍不通于链表的同学快速理解和⼊门。

此处我们使⽤C进⾏演⽰⽂章⽬录结点的创建我们知道链表是由⼀个个结点串联⽽成的，⽽每个结点分为两块区域，⼀块是数据域，相当于数组中存储的那个数据；另⼀块是指针域，这⾥存放的是指向下⼀个结点的地址。

在链表遍历的过程中，我们根据前⼀个结点的指针域中的那个地址找到下⼀个结点，就这样⼀个接⼀个往下遍历，进⾏增删改查等⼀系列基础操作。

知道了结点的基础结构就可以来进⾏创建了。

typedef struct lint{// 数据域int score;// 指针域struct lint* next; // 因为next是指向结点的，因此也要是结点的类型}Lint;这⾥使⽤typedef是为了重命名，省的以后创建指针时还要连带着 struct lint*。

之后创建指针就可以直接Lint* p⽽不是struct lint* p链表初始化链表中有⼀个特殊的结点–头结点。

头结点的数据域⼀般不⽤来存放和其他节点同类的数据，它的诞⽣是为了在实际应⽤过程中存放⼀些数据(下⾯会演⽰到)。

我们先来进⾏⽆头结点的初始化。

Lint * initLint(){// 创建头指针Lint* p = NULL;// 创建⼀个临时指针初始化⾸元结点，并且⽤于移动和调整后续结点Lint* temp = (Lint*)malloc(sizeof(Lint));temp->score = 90;temp->next = NULL;// 头指针需要指向⾸元结点，这样才能定位这串链表的位置p = temp;// ⼿动创建10个元素for(int i = 0;i < 10;i++){// 从第⼆个结点开始创建Lint * a = (Lint*) malloc(sizeof(Lint));a->score = i + 91;a->next = NULL;// 将当前temp指向的结点的next指向下⼀个结点temp->next = a;// temp移到下⼀个结点。

Python数据结构之链表详解⽬录0.学习⽬标1.线性表的链式存储结构1.1指针相关概念1.2指针结构1.3结点1.4结点类2.单链表的实现2.1单链表的初始化2.2获取单链表长度2.3读取指定位置元素2.4查找指定元素2.5在指定位置插⼊新元素2.6删除指定位置元素2.7其它⼀些有⽤的操作3.单链表应⽤3.1单链表应⽤⽰例3.2利⽤单链表基本操作实现复杂操作0. 学习⽬标在顺序存储⽅式中，根据数据元素的序号就可随机存取表中任何⼀个元素，但同时在插⼊和删除运算需要移动⼤量的元素，造成算法效率较低。

解决此缺陷的⼀个办法是：对线性表采⽤链式存储⽅式。

在链表存储⽅式中，在逻辑上相邻的数据元素在存储空间中不⼀定相邻，数据元素的逻辑次序是通过链表中指针链接实现的。

本节将介绍链式存储结构的特点以及各种基本操作的实现。

通过本节学习，应掌握以下内容：线性表的链式存储及实现⽅法链表基本操作的实现利⽤链表的基本操作实现复杂算法1. 线性表的链式存储结构链式存储结构⽤于存放线性表中的元素的存储单元在内存中可以是连续的，也可以是零散分布的。

由于线性表中各元素间存在着线性关系，为了表⽰元素间的这种线性关系，链式存储结构中不仅要存储线性表中的元素，还要存储表⽰元素之间逻辑关系的信息。

所以⽤链式存储结构表⽰线性表中的⼀个元素时⾄少需要两部分信息，除了存储每⼀个数据元素值以外，还需存储其后继或前驱元素所在内存的地址。

采⽤链式存储结构表⽰的线性表简称链表 (Linked List)。

1.1 指针相关概念在继续进⾏讲解前，我们⾸先来了解指针的相关概念，以便更好的理解链表。

假设我们需要处理⼀个⼤型数据⽂件，这⼀⽂件已经被读取保持在内存中，当我们在函数间传递⽂件时，并不会直接传递整个⽂件，我们需要创建变量来保存⽂件在内存中的位置，这些变量很⼩，很容易在不同的函数之间传递。

使⽤指针的好处之⼀就是可以⽤⼀个简单的内存地址就可以指向⼀个更⼤的内存地址段。

数据结构链式表基本操作代码链式表是一种常用的数据结构，它可以用来存储和操作大量数据元素。

在这篇文章中，我们将介绍链式表的基本操作，并给出相应的代码实现。

1. 链式表的定义链式表是由若干个节点构成的数据结构，每个节点包含两部分数据：一个是存储实际数据的数据域，另一个是指向下一个节点的指针。

链式表的头节点是一个特殊的节点，它不存储实际数据，只有指向下一个节点的指针。

2. 链式表的基本操作2.1 链式表的创建链式表的创建需要先创建头节点，然后逐个创建节点并将它们插入链表中。

创建节点时需要为节点分配内存空间，并将节点的数据域和指针域初始化。

//定义链式表节点类型typedef struct node {int data; //数据域struct node *next; //指针域} Node;//创建链式表Node *createList() {Node *head = (Node *)malloc(sizeof(Node)); //创建头节点head->next = NULL; //将头节点的指针域初始化Node *p = head; //p指向头节点int x;while (1) {scanf('%d', &x); //输入新节点的数据if (x == -1) break; //输入-1表示输入结束Node *newNode = (Node *)malloc(sizeof(Node)); //创建新节点newNode->data = x; //初始化新节点的数据域newNode->next = NULL; //将新节点的指针域初始化p->next = newNode; //将新节点插入链表尾部p = newNode; //p指向新节点}return head; //返回头节点}2.2 链式表的遍历链式表的遍历是指依次访问链表中的每个节点，并对每个节点进行相应的操作。

链表类定义：将该类保存在文件LinkList.h中。

//链表类定义：将该类保存在文件LinkList.h中。

template <class T>struct Node{T data;Node<T> *next; //此处<T>也可以省略};template <class T>class LinkList{public:LinkList( ){first=new Node<T>;first->next=NULL;} //建立只有头结点的空链表LinkList(T a[ ], int n); //建立有n个元素的单链表~LinkList( ); //析构函数int Length( ); //求单链表的长度T Get(int i); //取单链表中第i个结点的元素值int Locate(T x); //求单链表中值为x的元素序号void Insert(int i, T x); //在单链表中第i个位置插入元素值为x的结点T Delete(int i); //在单链表中删除第i个结点void PrintList( ); //遍历单链表，按序号依次输出各元素private:Node<T> *first; //单链表的头指针};template <class T>LinkList<T>:: ~LinkList( ){Node<T> * p=first; //工作指针p初始化while (p) //释放单链表的每一个结点的存储空间{Node<T> * q=p; //暂存被释放结点p=p->next; //工作指针p指向被释放结点的下一个结点，使单链表不断开delete q;}}template <class T>T LinkList<T>::Get(int i){Node<T> *p; int j;p=first->next; j=1; //或p=first; j=0;while (p && j<i){p=p->next; //工作指针p后移j++;}if (!p) throw "位置";else return p->data;}template <class T>void LinkList<T>::Insert(int i, T x){Node<T> *p; int j;p=first ; j=0; //工作指针p初始化while (p && j<i-1){p=p->next; //工作指针p后移j++;}if (!p) throw "位置";else {Node<T> *s;s=new Node<T>;s->data=x; //向内存申请一个结点s，其数据域为xs->next=p->next; //将结点s插入到结点p之后p->next=s;}}template <class T>T LinkList<T>::Delete(int i){Node<T> *p; int j;p=first ; j=0; //工作指针p初始化while (p && j<i-1) //查找第i-1个结点{p=p->next;j++;}if (!p || !p->next) throw "位置"; //结点p不存在或结点p的后继结点不存在else {Node<T> *q; int x;q=p->next; x=q->data; //暂存被删结点p->next=q->next; //摘链delete q;return x;}}template <class T>LinkList<T>:: LinkList(T a[ ], int n){first=new Node<T>;first->next=NULL; //初始化一个空链表for (int i=0; i<n; i++){Node<T> * s=new Node<T>;s->data=a[i]; //为每个数组元素建立一个结点s->next=first->next; //插入到头结点之后first->next=s;}}template <class T>void LinkList<T>::PrintList( ){Node<T> *p;p=first->next;while (p){cout<<p->data<<" ";p=p->next;}}#include <iostream.h>#include"LinkList.h"void main( ){int r[ ]={10,9,8,7,6,5,4,3,2,1};LinkList <int> a( r , 10 );cout<<"原表为:"<<endl;a.PrintList();cout<<endl;a.Insert(1,-2); //执行插入操作;a.Insert(2,-1);a.Insert(3,0 );cout<<"执行插入后输出为:"<<endl;a.PrintList();cout<<endl;a.Delete(0);a.Delete(-1);a.Delete(-2);cout<<"执行删除后输出为:"<<endl;a.PrintList();cout<<endl;cout<<"按位查找第二个元素:"<<endl;cout<<"第5 个元素为: ";cout<<a.Get(5)<<endl; //查找链表中第5 个元素cout<<endl;}。