网站导航
> 文章列表 > 【单链表】

【单链表】

网友: 文章列表 2024-03-22 05:31:34

【单链表】

单链表

  • 1. 函数的声明部分
  • 2. 函数的实现部分
    • （1）打印链表
    • （2）头插
    • （3）尾插
    • （3）头删
    • （4）尾删
    • （5）单链表的查找
    • （6）删除pos位置之后的值
    • （7）在pos位置之后插入x
  • 3. 函数的测试部分

单链表概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

1. 函数的声明部分

		#pragma once#include <stdio.h>#include <stdlib.h>#include <assert.h>typedef int SLTDateType;typedef struct SingleListNode{SLTDateType data;struct SingleListNode* next;}SLTNode;//打印void SLTPrint(SLTNode* phead);//头插void SLTPushFront(SLTNode pphead, SLTDateType x);//尾插void SLTPushBack(SLTNode pphead, SLTDateType x);//头删void SLTPopFront(SLTNode pphead);//尾删void SLTPopBack(SLTNode pphead);//在pos位置之后插入xvoid SLTInsertAfter(SLTNode* pos, SLTDateType x);//删除pos位置之后的值void SLTEraseAfter(SLTNode* pos);//单链表查找SLTNode* SLTFind(SLTNode pphead, SLTDateType x);

2. 函数的实现部分

由于头插，尾插等需要开辟一个节点，所以把开辟节点单独作为一个函数，需要开辟节点的时候直接调用；

		SLTNode* BuyListNode(SLTDateType x){//开辟一个节点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));assert(newnode);//对newnode初始化newnode->data = x;newnode->next = NULL;return newnode;}

（1）打印链表

		//打印void SLTPrint(SLTNode* phead){SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\\n");}

（2）头插

头插需要传二级指针，因为在调用函数SLTPushFront的时候，实参plist本来是结构体指针，现在头插需要改变链表的头，即需要传地址去改变plist的头；

如进行以下操作，值传递操作：

【单链表】
【单链表】
假设链表是如下形式：

【单链表】

当头插函数使用一级指针接收实参时，实参和形参同为一级指针，它们是同等类型的，它们在两个不同的栈空间，假如进行以下操作：

【单链表】
实际上phead并不会改变plist的值：

【单链表】

因为它们两个在不同的栈空间，phead只是plist的临时拷贝，只要出了SLTPushFront这个函数，栈帧被销毁，phead也被销毁了，但是phead的改变也没有改变plist的值，所以相当于什么也没有发生；

所以需要传二级指针，存放plist的指针，到函数内部需要解引用找到plist，再去改变plist的值，这样才能达到我们想要的效果；

		//头插void SLTPushFront(SLTNode pphead, SLTDateType x){SLTNode* newnode = BuyListNode(x);//将newnode的next更新为原来的头节点newnode->next = *pphead;//将newnode更新为新的头节点*pphead = newnode;}

（3）尾插

尾插的时候，当链表为空时，需要改变的是plist这个结构体指针，所以这个时候也是要传二级指针；当链表为非空链表时，需要改变的是结构体，所以不需要用到二级指针；但为了防止链表为空，这里干脆直接传二级指针；

		//尾插void SLTPushBack(SLTNode pphead, SLTDateType x){SLTNode* newnode = BuyListNode(x);//空链表if (*pphead == NULL){*pphead = newnode;}//非空链表else{SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = newnode;}}

（3）头删

		//头删void SLTPopFront(SLTNode pphead){//没有节点assert(*pphead);//一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//多个节点else{SLTNode* cur = *pphead;*pphead = cur->next;free(cur);cur = NULL;}}

（4）尾删

		//尾删void SLTPopBack(SLTNode pphead){//空链表assert(*pphead);//一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//多个节点else{SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}}

（5）单链表的查找

		SLTNode* SLTFind(SLTNode* phead, SLTDateType x){SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;	}return NULL;}

（6）删除pos位置之后的值

		void SLTEraseAfter(SLTNode* pos){assert(pos && pos->next);SLTNode* cur = pos;cur->next = cur->next->next;}

（7）在pos位置之后插入x

		void SLTInsertAfter(SLTNode* pos, SLTDateType x){SLTNode* cur = BuyListNode(x);assert(cur);cur->next = pos->next;pos->next = cur;}

3. 函数的测试部分

		#define _CRT_SECURE_NO_WARNINGS 1#include "Single List.h"int main(){SLTNode* plist = NULL;SLTPushFront(&plist, 2);SLTPushFront(&plist, 1);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);//SLTPopFront(&plist);//SLTPopBack(&plist);//SLTInsertAfter(plist->next->next, 10);SLTEraseAfter(plist);SLTPrint(plist);SLTNode* ret = SLTFind(plist, 5);if (ret != NULL){printf("%d->", ret->data);}else{printf("NULL\\n");}SListDestroy(&plist);return 0;}

相关问题