C++单链表的基本算法

蔚落 2022-07-12 02:24 205阅读 0赞

线性表是最简单，最常用的一种数据结构。线性表的逻辑结构是n个数据元素的有限序列（a1,a2,…,an）。而线性表的物理结构，我们已经学习过顺序表，也就是数组 ；另一种线性表的物理结构——链表 。

## 什么是单链表 ##

单链表（Singly Linked list）也称线性链表。每个元素占用一个节点（Node）。一个节点至少包含两个域，一个域存放数据信息info，其数据类型由应用问题决定，另一个存放指向该链表中下一个节点的指针link。

## 单链表的c++实现思路 ##

◆ 1、单链表节点的数据类型  
typedef int Datatype; //节点的数据为整型  
struct node  
\{  
    Datatype info;//节点的数据信息  
    node \*link;  
//指向下一个节点的指针，是结构自身的指针类型，决不能是结构自身类型  
\}；

◆ 2、由节点形成单链表  
单链表的第一个节点首先通过new运算获得，并用链表的表头指针head指向， head在使用中必须妥善保存，千万不可丢失，否则单链表整个丢失，内存也发生泄漏。  
    ……//有关node的声明，见上段代码  
    node \*head;  
    head=new node;  
    //第一个节点的数据不赋值，则该节点仅作head  
    head->link=NULL;//指针初始化

单链表后面的节点可以通过插入与删除来维护：只要改变链中节点指针的指向，而无需移动表中的元素，就能实现插入和删除操作。

## 单链表的基本插入算法 ##

现在已经存在单链表“head”，插新节点时考虑三种情况：

1.  新插入节点作为单链表的第一个结点；
2.  也有可能新插入节点是中间节点；
3.  也有可能新插入节点作为最后一个节点。

首先要先产生新节点：  
    ……//有关node的声明  
    node \*newone;  
    newone=new node;  
    newone->info=13;//给该节点的数据赋值  
    newone->link=NULL;//指针初始化

◆ **1、新节点插在链首** （查看动画演示）  
    //注意：链表操作次序非常重要  
    ……//node、head、newone的声明及定义,见上面  
    newone->link=head->link；  
    Head->link=newone；//注意指针赋值

◆ **2、新节点插在单链表中间**  
首先用工作指针p找到指定节点，而让指针q指向紧跟其后的节点；新节点插在p、q之间；  
    node \*p,\*q;  
    ……//此段代码实现：利用查找算法将p定位在指定节点（稍后将学习）  
    q=p->link; //注意指针赋值  
    newone->link=q；  
    //或newone->link=p->link；这样就不需要q了  
    p->link=newone；