单个链接列表的C ++实现

单链表是一个相对简单的线性数据结构. 对于顺序表，通常在插入和删除数据时会移动相对大量的元素，并且当单链接列表处理这种情况时c/c++链表，只需要更改一些指针即可，这样效率更高.

单个链接列表概述:

链表中的数据由节点表示. 每个节点的结构是: 元素（数据元素的图像）+指针（指示后续元素的存储位置）. 连接每个节点的地址数据. 由“节点序列”表示的线性列表称为线性链接列表或单个链接列表.

实施过程:

首先构造一个节点结构:

typedef struct Node {

int数据； //节点的data字段用于存储数据，这里定义为整数或其他类型的变量

节点*接下来； //节点的指针字段，用于存储后续节点的地址

} M_Node； //将其重命名为其自身的结构M_Node.

接下来是列表类的构建

班级列表{

M_Node *头； //定义的头指针

公开

:

list（）{head = NULL;} //构造函数将链接列表初始化为空列表（头指针指向NULL）

void M_Insert（int ac/c++链表，intb）; //插入列表节点，在元素a之前插入b

void M_Delete（int a）; //删除链接列表节点

void M_Output（）; //列表节点的输出

M_Node * Gethead（）{return head;}​​ //获取头节点的数据

};

链接列表元素的访问过程:

由于链接列表中的节点是通过指针链接的，因此存储单元是连续的. 因此，列表中任何节点的地址都不能与数组相同. 它使用简单的随机访问公式来计算. . 它只能从链接列表的头指针（即头）开始. 使用指针p首先指向第一个节点，然后根据节点p找到下一个节点. 依此类推，直到找到您要访问的节点或直到最后一个节点（指针为空）为止.

成员函数的实现如下:

首先是M_Output（）函数，其功能是输出链接列表的所有元素.

1. 构造指向第一个节点头节点的指针.

2. 使用指针输出该节点的数据.

3. 向后移动指针

4. 循环执行步骤2和3，直到指针指向NULL

无效列表:: M_Output（）

{

M_Node * current = head;

同时（当前！= NULL）

{

cout << current->数据<<“”;

current = current-> next;

}

cout << endl;

}

接下来看看如何实现元素插入操作:

元素插入的功能是在元素a之前插入元素b. 有几种情况需要考虑:

1. 如果原始链表为空列表，则将插入的元素用作头节点.

2. 如果元素a是头节点，则插入的元素b将替换a作为头节点

3. 如果元素a在链表中而不是第一个元素，则首先找到a的前一个元素a_1，然后让a_1的指针字段指向b，b的指针字段指向a，然后插入完成

4. 如果元素a不在列表中，则将其插入末尾. 找到最后一个元素a_n，a_n的指针字段指向b，b的指针字段指向null.

无效列表:: M_Insert（int a，int b）

{

M_Node * p，* q，* s; // p指向节点a，q指向节点a_k，s指向节点b

s =（M_Node *）新（M_Node）; //动态分配新节点

s->数据= b; //设b为该节点

p =头;

if（head == NULL）//如果为空列表，则将b设为第一个节点

{

head = s;

s-> next = NULL;

}

其他

if（p-> Data == a）//如果a是第一个节点

{

s-> next = p;

head = s;

}

其他

{

while（p-> Data！= a && p-> next！= NULL）//查找节点a

{

q = p;

p = p->接下来；

}

if（p-> Data == a）///如果存在节点a

{

q-> next = s;

s-> next = p;

}

else //如果没有节点a；

{

p-> next = s;

s-> next = NULL;

}

}

}

接下来，查看删除操作，该操作可以分为以下几种情况:

1. 如果链表为空或被删除的元素不存在，则删除操作错误并且不执行任何操作.

2. 如果第一个节点被删除，则将头指向a的下一个节点

3. 如果a在链接列表中，并且不是第一个元素，请找到a的上一个节点，并将其指针字段指向a的下一个节点.

无效列表:: M_Delete（int a）

{

节点* p，* q; // p用于指向节点a，q用于指向节点a的上一个节点

p =头;

if（p == NULL）//如果是空表

返回；

if（p-> Data == a）//如果a是第一个节点

{

head = p->接下来；

删除p;

}

其他

{

while（p-> Data！= a && p-> next！= NULL）//查找节点a

{

q = p;

p = p->接下来；

}

if（p-> Data == a）//如果有节点a

{

q->下一步= p->下一步;

删除p;

}

}

}

最后，让我们尝试此链接列表的功能.

int main（int argc，char ** argv）{

列表A，B；

int数据[10] = {12,23,45,32,65,33,75,3,67,22};

A.M_Insert（0，数据[0]）；

for（int i = 1; i <10; i ++）

A.M_Insert（数据[i-1]，数据[i]）；

cout <<“插入列表A向前” << endl;

A.M_Output（）;

for（int i = 0; i <10; i ++）

B.M_Insert（0，数据[i]）；

cout <<“链接列表B向后插入” << endl;

B.M_Output（）;

A.M_Delete（23）;

cout <<“列表23删除23个元素之后” << endl;

A.M_Output（）;

B.M_Insert（65,33）;

cout <<“列表B在33之前的65个元素之后插入” << endl;

B.M_Output（）;

返回0；

}

链接列表的实现环境为DEV C ++

写得好，欢迎来吐槽.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-154530-1.html