这次来介绍一下数据结构里面的单链表。

这是一个简单的链表，它是单向的，没有(哨兵位置)头结点，不循环，有一个头指针指向第一个节点。

和上次介绍线性表一样，我们同样研究它的增，删，查，改。

1.什么是链表

2.链表的功能

2.1 基本功能

1）打印链表

2）创建新结点

3）获取链表长度

4）查找节点

2.2增加元素

1）头部增加

2）尾部增加

3）中间增加

2.3删除元素

1)头部删除

2)尾部删除

2.4修改元素

2.5销毁链表

测试

1.增加元素的测试

2.删除元素测试

3.修改元素测试

1.什么是链表

首先，链表是线性表的一种，它的存储方式是链式存储。链表是由一个个节点组成，连接每个节点的关键是指针，每一个节点，我们用结构体实现。

代码如下：

typedef int SLTDataType;//int类型的重定义
//用结构体创建一个节点
typedef struct SListNode
{SLTDataType data;//节点的数据域SListNode *next;//结点的指针域
}SLT;

SLTDataType是int类型的重定义， next 是一个结构体指针，负责存放下一个节点的地址。

我们看一下物理存储结构和逻辑结构：

如图所示：

我们图中有四个节点，1 、2、3、4，节点的前边存的是一个整型数据，后边存的是一个地址。

这个地址就是后一个节点的地址，最后一个节点，也就是尾结点存的是NULL。

再看看看逻辑结构，对于指针，指针存放的地址，我们认为指针指向这片内存块，所以我们用箭头来表示节点与节点之间的关系，事实上并没有这个箭头，这只是方便我们理解。

链表的结构了解之后，我们来看实现的功能。

2.链表的功能

1.基本功能1）打印链表2)创建新节点3）获取链表长度 4）查找节点

2.增加元素：1）头部增加 2）尾部增加 3）中间增加

3.删除元素: 1)头部删除 2）尾部删除 3）中间删除

4.修改元素：找到某个元素，把它修改掉

5.销毁顺序表

2.1 基本功能

1）打印链表

打印链表就是，遍历整个链表，把每个节点存的数据输出出来即可。

代码如下：

void SListPrint( SLT *&phead)
{SLT *cur = phead;if (phead == NULL){cout << "链表为空,无法打印" << endl;return;}while (cur){cout << cur->data << "->";cur = cur->next;}cout << "NULL" << endl;
}

形参是对头指针的引用，如果不了解这个知识的话，这里就把它当做我们头指针的一个别名，当成我们的头指针就行了，它存的是第一个节点的地址。

我们用cur指针来遍历链表，首先，如果链表为空，即我们的头指针存的是NULL，不打印，直接return。链表不为空，一个一个打印。

关键的代码:

cur = cur->next;

我们用这种写法，把我们下一个节点的地址在上一个节点打印完成后，赋给我们的cur，接下来打印下一个数据。

最后，当cur打印完最后一个数据的时候，前面提到，最后一个节点存的是NULL，把它赋给cur，它为空，然后判断循环，退出循环，打印完毕。

打印效果如下：

2）创建新结点

新结点的创建，就是动态申请一块内存区域，并给它初始化。

代码如下：

SLT *BuyNewNode(SLTDataType x)//创建新的节点
{SLT *newnode = new SLT;//new一个结构体大小的空间
//返回值是结构体指针，用newnode来接收newnode->data = x;//给data赋值newnode->next = NULL;//把里面的指针域置为空return newnode;//返回创造节点的地址
//不了解new的话，用malloc来创建效果是一样的
//SLT *newnode=(SLT *)malloc(sizeof(SLT));
//newnode->data=x;
//return newnode;

如果不了解的new的用法，用注释里面的malloc来实现也是完全OK的。

3）获取链表长度

这个功能是来辅助后边的功能的，比较简单，直接上代码：

SLTDataType SListLength(SLT *&phead)
{if (phead == NULL){return 0;//链表为空返回0}else{SLTDataType count = 0;//count来记录节点个数SLT *cur = phead;//cur来遍历链表while (cur){count++;cur = cur->next;}return count;//返回链表个数}
}

4）查找节点

这个查找结点在后边的功能中是要用到的，所以我们先来介绍一下。

我们的单链表有一个特点，就如它的名字一样，单向的，有些功能不做特殊处理，实现起来很尴尬。就比如我们的在中间某个节点前面插入数据，如果仅仅找找到这个节点，把新节点放在那里，我们发现，很尴尬，不知道前一个节点的地址，没法通过找到的那个节点来确定前边节点，这也是它的一个缺点，所以，干脆点，我们就找待找节点前面一个位置的节点，这个问题就解决了。

所以，代码如下：

SLT * NodeFind(SLT *&phead, SLTDataType i)//查找某个节点，返回前一个位置的地址
{SLTDataType len = SListLength(phead);if (i<0 || i>len){cout << "输入的节点不合法！！" << endl;return NULL;}SLTDataType pos = 1;SLT *cur = phead;while (pos<i-1){pos++;cur = cur->next;}return cur;
}

这里我们先判断输入的节点是否合理，前面说的获取链表长度的函数就有用了。为了找到目标节点前一个位置的节点，我们最关心的就是循环的次数，什么时候算找到。其实当我们限定了节点的输入范围，循环结束后，肯定是能找到它的。

看我们的循环条件，i-1，i是1或2的时候，我们返回的都是首节点的地址，1的时候是头插，比较特特殊，2的时候正常，就是第二个节点前边的节点，也就是首节点地址。

其它情况，比如，我们i为6,i-1为5，从1到5（不包括5），刚好四次，找到了第五个节点，即找到第六个节点前边的节点。

这样，查找功能就实现了。

单链表这样找前一个节点，看上去有点麻烦，后边会介绍双链表，它的查找直接找目标节点就可以了。

2.2增加元素

1）头部增加

在链表的头部增加节点。

思路是：让新的头结点指向旧的头结点，头指针指向新的头结点即可。

代码如下：

void SListPushFront(SLT *&phead, SLTDataType x)//头插
{SLT *newnode = BuyNewNode(x);//创建新节点newnode->next = phead;//新的首节点 指向旧的首节点phead = newnode;//头节点指向新的首节点
}

2）尾部增加

在链表尾部增加节点。

思路是：找到尾，连接新节点。

考虑，如果链表为空，这个时候的尾部增加，就是头插。

代码如下：

void SListPushBack(SLT *&phead, SLTDataType x)//尾插
{SLT *newnode = BuyNewNode(x);if (phead == NULL)//链表为空的尾插就是头插{phead = newnode;}else//不为空，单链表的尾插就要找尾节点{SLT *tail = phead;while (tail->next != NULL){tail = tail->next;//这种类型的表达是链表最常用写法}                     //这种写法让指针在链表中移动起来//退出循环，tail就在尾部tail->next = newnode;//新节点接在尾部}
}

while（tail->next != NULL），看这个循环条件，我们要找到的是尾节点，我们判断tail当前位置的下一个位置是否为空，如果为空，那么它就是尾节点，我们退出循环。

但是，while（tail != NULL）,如果这样写，会出现很尴尬的情况，就是我们的tail最后会指向空，而不是刚好停留在尾节点上。

3）中间增加

中间增加，就是找到目标节点前面的节点，在它的后边增加即可，这时候，前面写的查找函数就用上了。

代码如下：

void SListInsert(SLT *&phead, SLTDataType x,SLTDataType pos)//任意位置插入（前边）
{if (phead == NULL){cout << "链表为空，无法插入" << endl;return;}else{if (pos == (SListLength(phead) + 1))//特殊情况,尾插{SListPushBack(phead, x);}else{SLT *temp = NodeFind(phead, pos);if (temp == phead&&pos==1)//特殊情况，pos为1时，返回的是首节点的地址，这时相当于头插{SListPushFront(phead, x);}else{SLT *newnode = BuyNewNode(x);SLT *cur = temp->next;temp->next = newnode;newnode->next = cur;}}}
}

看代码，因为我们的插入是向某个节点的前面插入，所以当链表为空的时候，我们直接退出不让插入。

不为空的时候

第一考虑尾插，因为我们的插入是向某个节点的前面插入，所以尾插很尴尬，我们只能单独判断用户输入的节点，调用尾插函数。

第二考虑头插，就是前面我们提到的，查找函数返回值是首元素地址的时候的一种情况。

看一般情况：

               {SLT *newnode = BuyNewNode(x);//创建新节点SLT *cur = temp->next;//记录目标节点temp->next = newnode;//目标节点前一个节点指向新节点newnode->next = cur;//新节点指向目标节点}

我们先创建一个新节点，然后我们通过SLT *cur = temp->next; 来保存我们想要找的节点，因为temp存的是目标节点前一个位置的地址，然后我们就把它们连接起来就好了。

2.3删除元素

1)头部删除

这个比较简单，因为我们的头指针指向的就是首节点，但要注意的是，删除之前，要把首节点后边的一个节点的地址给头指针，不然直接释放它，就找不到后边的节点了。

代码如下：

void SListPopFront(SLT *&phead)//头删
{if (phead == NULL){cout << "链表为空，无法删除！！" << endl;return;}else{SLT *second = phead->next;delete phead;//free(phead);phead = second;//两种写法都可以//SLT *first = phead;//SLT *second = first->next;//phead = second;//delete first;free(first)}
}

首先，链表为空，不删除。

其次就是正常的释放空间了，上面给了两种写法，其实是一样的，只不过第二种是把phead的值作了传递，最后还是释放首节点，效果是一样的，只是或许看上去会更好理解一点。

delete不太熟悉，就用free，但是new必须和delete搭配，malloc和free必须搭配，切不可混着用。

2)尾部删除

尾部删除就得找尾，单链表找尾，我们选择的是遍历找尾。

代码如下：

void SListPopBack(SLT *&phead)//尾删
{if (phead == NULL){cout << "链表为空，无法删除！！" << endl;}else if (phead->next==NULL)//特殊情况，只有一个节点{delete phead;phead = NULL;}else//一般情况{SLT *tail = phead;//找尾SLT *cur = NULL;//记录tail前一个节点while (tail->next != NULL){cur = tail;tail = tail->next;}cur->next = NULL;//cur即新的尾，尾要指向空delete tail;//free(tail);}
}

首先链表为空，我们不删。

我们先考虑一般情况,tail是用来找尾的,cur是用来找新的尾节点，while (tail->next != NULL)，这循环条件，最终tail会停到尾节点上，cur刚好停在尾结点前面一个节点上，即新的尾节点。我们找到尾结点后，释放它，再让新的尾结点指向空，就完成了。

再说特殊情况，假如我们的链表只有一个节点，还按照一般情况处理，就会出问题。

这个时候，tail->next是为空的，循环不会进去，cur也是空，再写cur->next，就不合适了，对NULL进行->操作，也就是解引用操作是不可以的。

所以，我们要单独考虑，即直接释放第一个节点，在让头指针指向空就好了。

3)中间删除

找到它，释放掉，连接它前后的节点。

代码如下：

void SListDelete(SLT *&phead, SLTDataType pos)//任意位置删除
{if (phead == NULL){cout << "链表为空,无法删除！！" << endl;return;}else{SLT *temp = NodeFind(phead, pos);//删除位置前一个节点的地址if (temp == phead&&pos==1)//特殊情况，头删{SListPopFront(phead);return;}else{SLT *cur = temp->next;//要删除的节点SLT *next = temp->next->next;//我们还要找到删除节点后一个节点temp->next = next;//连接前后节点delete cur;}}
}

同样的，链表为空，我们不删。再来，特殊情况，pos为1那么就是头删，其它情况。我们temp找的是待删节点前面的一个，所以为了找到后边的节点，我们必须写出这样的代码SLT *next = temp->next->next，cur记录要删的节点，链接完成之后，释放cur指向的节点就好了。

不知道大家有没有疑惑，为什么找节点，这么麻烦，直接根据数据元素找不就行了，但你有没有想过，数据元素是可以重复的，那么这样你只能找到第一个相同的元素，找不到后边相同的元素。

而且为啥非得找前一个，直接找它不就好了，这个刚刚我也提到了，这就是单链表的一个缺点，在之后的双链表中，这个问题可以很好的解决。

2.4修改元素

这个简单，明白我们如何查找之后，修改它就很容易实现了。

代码如下：

void SListModify(SLT *&phead, SLTDataType pos, SLTDataType y)
{if (phead == NULL){cout << "链表为空，无法修改" << endl;return;}else{SLT *temp = NodeFind(phead, pos);if (temp == phead&&pos == 1)//特殊情况，修改第一个元素{phead->data = y;}else{SLT *cur = temp->next;//记录要修改的节点cur->data = y;//修改它的值}}
}

首先，链表为空，不修改。

其次，特殊情况，修改第一个节点的值单独考虑，再来，其它的情况，就通过temp找到它，用cur来修改就好了。

最后，销毁链表~~

2.5销毁链表

链表的销毁也很简单，但要注意的是，销毁前一个节点之前，要把后一个节点的地址记录一下，然后用循环一次销毁就好了。

代码如下：

void SListDestory(SLT *&phead)//销毁链表
{if (phead == NULL){return;//链表为空,没有需要销毁的节点，直接推出}else{   SLT *cur = phead;//要释放的节点SLT *next = NULL;while (cur){next = cur->next;//记录下一个要释放的节点delete cur;//释放当前节点cur = next;//后节点传递}phead=cur = next = NULL;}
}

首先，链表为空，就不用销毁了，也不用头指针置为空了。

再来，分析过程，我们知道，next是指向cur后边一个的节点，那么当我们的cur成功释放掉最后一个节点时，next是指向NULL的，那么赋值后，cur为空，那么循环就结束了。

最后，把指针都置为空，这个功能就实现了。

以上就是，我们单链表的常用功能！！！

老规矩，接下来，我们做测试！！！

测试

1.增加元素的测试

代码如下：

void test03()
{SLT *phead = NULL;int i = 0;for (i = 0; i < 5; i++){SListPushBack(phead, i + 1);}cout << "初始状态，链表值为：" << endl;SListPrint(phead);cout << endl;//头插区SListPushFront(phead, 450);cout << "头插450后，链表值为:" << endl;SListPrint(phead);SListPushFront(phead, 500);cout << "头插500后，链表值为:" << endl;SListPrint(phead);//-------------////尾插区SListPushBack(phead, 300);cout << "尾插300后，链表值为:" << endl;SListPrint(phead);SListPushBack(phead, 700);cout << "尾插700后，链表值为:" << endl;SListPrint(phead);//-------------////中间插SListInsert(phead, 100, 5);//一般情况cout << "第5个位置插入100后，链表值为：" << endl;SListPrint(phead);SListInsert(phead, 74, 1);//头插cout << "用Insert头插后,链表值为:" << endl;SListPrint(phead);SListInsert(phead, 600, 2);//第二个位置插入cout << "第2个位置插入600后，链表值为：" << endl;SListPrint(phead);SListInsert(phead, 780, SListLength(phead) + 1);//尾插cout << "用Insert尾插780后,链表值为:" << endl;SListPrint(phead);//-------------//
}

运行结果如下：

2.删除元素测试

代码如下：

void test04()
{SLT *phead = NULL;int i = 0;for (i = 0; i < 10; i++){SListPushBack(phead, i + 1);}cout << "初始状态，链表值为：" << endl;SListPrint(phead);cout << endl;//头删区SListPopFront(phead);cout << "头删 1 后，链表的值为" << endl;SListPrint(phead);cout << endl;//尾删区SListPopBack(phead);cout << "尾删10后，链表的值为:" << endl;SListPrint(phead);cout << endl;//中间删SListDelete(phead, 1);cout << "用Delete头删 2 后，链表的值为：" << endl;SListPrint(phead);cout << endl;SListDelete(phead, 2);cout << "用Delete 删 4 后，链表的值为：" << endl;SListPrint(phead);cout << endl;SListDelete(phead, SListLength(phead));//尾删cout << "用Delete尾删 9 后，链表的值为：" << endl;SListPrint(phead);cout << endl;
//-------------//
}

运行结果如下:

3.修改元素测试

代码如下：

void test05()
{SLT *phead = NULL;int i = 0;for (i = 0; i < 10; i++){SListPushBack(phead, i + 1);}cout << "初始状态，链表值为：" << endl;SListPrint(phead);cout << endl;SListModify(phead, 1, 30);cout << "用Modify修改把第1个节点的数据修改为30后，链表的值为：" << endl;SListPrint(phead);cout << endl;SListModify(phead, 2, 45);cout << "用Modify修改把第2个节点的数据修改为45后，链表的值为：" << endl;SListPrint(phead);cout << endl;SListModify(phead, 6, 78);cout << "用Modify修改把第6个节点的数据修改为78后，链表的值为：" << endl;SListPrint(phead);cout << endl;SListModify(phead,SListLength(phead), 100);cout << "用Modify修改把尾节点的数据修改为100后，链表的值为：" << endl;SListPrint(phead);cout << endl;SListDestory(phead);
}

运行结果: