单链表C语言实现

文章列表

单链表C语言实现

链表就是许多节点在逻辑上串起来的数据存储方式是通过结构体中的指针将后续的节点串联起来

typedef int SLTDataType;//数据类型
typedef struct SListNode//节点
{SLTDataType data;//存储的数据struct SListNode* next;//指向下一个节点地址的指针
}SLTNode;//结构体类型的简化

上面的代码只是声明并没有定义也就是没有创建结构体变量

SListNode* pc = NULL;//定义结构体

下面开始实现链表的各个接口让链表可以存储和删除数据

链表的打印

void SListPrint(SListNode* phead)
{while (phead != NULL){printf("%d->", phead->val);phead = phead->next;}printf("NULL");
}

链表的插入会向内存申请空间去创造一个新的节点所以后续的头部插入尾部插入还是任意位置的插入都会进行相同的操作所以这里将开辟节点这个过程单独分装为一个函数方便后面的操作

static SListNode* CreatNode(DataType x)
{SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));if (tmp == NULL){printf("failed to allocate memory.");exit(-1);}tmp->val = x;tmp->next = NULL;return tmp;
}

这里使用了static将函数的作用域限制在该函数所在的项目中在其它项目中无法访问

链表的头部插入

void SListFront(SListNode** phead, DataType x)
{SListNode* tmp = CreatNode(x);tmp->next = *phead;tmp->val = x;*phead = tmp;
}

链表的尾部插入

链表的尾部插入相比于头部插入就显得不是那么好写

因为你要考虑链表中是否有数据也就是*phead是否为空并且还要考虑当链表不为空时尾插该怎样插入我们可以使用if语句进行判断

void SListBackPush(SListNode** phead, DataType x)
{SListNode* newnode = CreatNode(x);if (*phead == NULL){*phead = newnode;}else{SListNode* tail = *phead;//定义一个变量去向后寻找尾部while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

任意位置的插入（从1位置向后插超出范围将该节点插入到尾部）

当链表有数据时尾部插入和头部插入是一样的流程用一个临时变量tmp 向后寻找pos位置再将该位置的下一个节点的地址给要插入节点的指针最后将要插入节点的地址给前一个节点的指针这样就将该节点插进去了

但是头部插入不太一样因为头部之前没有节点了就只能将头节点先给要插入的节点再将要插入的节点作为头部这样就完成了头部插入

void SListPosPush(SListNode** phead, DataType x , int pos)
{SListNode* newnode = CreatNode(x);if (pos == 1){newnode->next = *phead;*phead = newnode;}else{SListNode* tmp = *phead;//如果所给的pos位置超出了链表的长度就将其插入到尾部while (tmp->next!=NULL && pos>2){tmp = tmp->next;--pos;}newnode->next = tmp->next;tmp->next = newnode;}
}

运行结果如下以上就是插入接口函数的实现

删除的相关节点

头删

void SListPopFront(SListNode** phead)
{assert(*phead);SListNode* tmp = *phead;*phead = (*phead)->next;free(tmp);tmp = NULL;
}

尾删

尾删和头删不一样因为当链表只有一个节点时尾删就变成了头删这样就和有多个数据时尾部删除不一样这就分情况讨论

void SListPopBack(SListNode** phead)
{assert(*phead);if ((*phead)->next == NULL){free(*phead);*phead = NULL;}else{//找尾SListNode* tmp = *phead;//防止头节点丢失SListNode* str = *phead;while (tmp->next != NULL){str = tmp;tmp = tmp->next;}free(tmp);tmp = NULL;str->next = NULL;}
}

上面是两个指针配合删除下面是一个指针去完成

void SListPopBack(SListNode** phead)
{assert(*phead);if ((*phead)->next == NULL){free(*phead);*phead = NULL;}else{//找尾SListNode* tmp = *phead;//防止头节点丢失SListNode* str = *phead;while (tmp->next->next!=NULL){tmp = tmp->next;}free(tmp->next);tmp->next = NULL;}
}

链表pos位置删除

void SListPopPos(SListNode** phead, int pos)
{assert(*phead);//空链表就不用删除了if (pos == 1){SListNode* tmp = *phead;*phead = (*phead)->next;free(tmp);tmp = NULL;}else{SListNode* tmp = *phead;SListNode* str = tmp;while (pos > 1 && tmp->next != NULL){str = tmp;tmp = tmp->next;--pos;}//找到pos位置之后将 pos的下一个节点的地址给pos前面的节点的指针//再将pos所在的节点进行释放str->next = tmp->next;free(tmp);tmp = NULL;}
}

对链表的查找修改其实就是将链表遍历一遍上面的寻找尾部打印链表就是遍历链表所以大家可以将其修改修改

对单链表就介绍到这里后续还有双向链表

单链表C语言实现

相关问题

公告