创建新结点
继续单链表的其他接口函数之前，先定义一个创建新结点的函数，方便后续使用。
SLTNode* CreateListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); newnode->data = x; newnode->next = NULL; return newnode; }
单链表的头插函数
相比于之前的尾插函数，头插函数较简单
代码实现
void SListPushFront(SLTNode ** pphead,SLTDataType x) { SLTNode * newnode = CreateListNode(x); newnode->next = *pphead; *pphead = newnode; }
实现思路
单链表的尾删函数
在写单链表尾删函数时，应该进行分类讨论。
分类讨论
一是链表为空时；二是链表中只有一个结点时；三是链表中大于等于2个结点时。
为什么要分类讨论呢？我们从第三种情况往回分析就可以得到答案了：
讨论完第三种情况的尾删了。看看第二种情况，这种思路是否可行：
因此将这两种情况分开来讨论的。
第一种情况则是出于严谨，没有结点时，不进行尾删。
代码实现
void SListPopBack(SLTNode** pphead) { //第一种情况 if (*pphead == NULL) { return; } //或者-> /*assert(*pphead != NULL);*/ //第二种情况 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } //第三种情况 else { SLTNode* prev = NULL; SLTNode* tail = *pphead; while (tail->next) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL; } }
单链表的头删函数
代码实现
void SListPopFront(SLTNode ** pphead) { assert(*pphead != NULL); SLTNode *next = (*pphead)->next; free(*pphead); *pphead = next; }
实现思路
单链表的查找函数
代码实现
SLTNode* SListFind(SLTNode* phead,SLTDataType x) { SLTNode* cur = phead; while(cur) { if(cur->data == x) { return cur; } else { cur = cur->next; } } return NULL; }
单链表查找的思路是很简单的，直接进行遍历就可以了。
需要考虑的是，当查找的目标不止存在一个时应该怎么处理：
查找多个相同目标
//假设我们要查找头结点为plist的单链表中数据是2的结点，且不止一个。 SLTNode* pos = SListFind(plist,2); int i = 1; while(pos) //判断pos返回的值是否为NULL，为NULL则证明已找不到 { printf("第%d个pos结点：%p->%d\n",i++,pos,pos->data); pos = SListFind(pos->next,2);//在pos的下一个位置开始查找 }
同时，运用这个函数返回值的特性，可以顺便实现修改数据的作用
修改指定结点的数据
//以之前的情景为例,我们把找到的2改为20 pos = SListFind(plist,2); if(pos) { pos->data = 20; }
pos位置前一个结点插入数据
实现思路
代码实现
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { SLTNode* newnode = CreateListNode(x); if (*pphead == pos) //当要在第一个位置的前面插入数据时，则为头插 { //用头插的思路来写即可 newnode->next = *pphead; *pphead = newnode; } else { //找到pos的前一个位置 SLTNode* posPrev = *pphead; while (posPrev->next != pos) { posPrev = posPrev->next; } posPrev->next = newnode; newnode->next = pos; } }
pos位置后一个结点插入数据
代码实现
//在pos的后面插入，这个更适合用于单链表，效率也更高一些 void SListInsertAfter(SLTNode* pos, SLTDataType x) { SLTNode* newnode = CreateListNode(x); newnode->next = pos->next; pos->next = newnode; }
pos位置删除结点
代码实现
void SListErase(SLTNode** pphead, SLTNode* pos) { if (*pphead == pos) { //直接使用头删函数 SListPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos)//与之前类似，找结点 { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }
pos位置后删除结点
void SListEraseAfter(SLTNode* pos) { assert(pos->next); SLTNode* next = pos->next; pos->next = next->next; free(next); //next = NULL; }
单链表的销毁
void SListDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
