北京网站设计公司youx成都柚米科技15,成都开发网站建设,长沙仿站定制模板建站,wordpress布谷鸟主题单链表
结构 单链表结构中有两个数据#xff0c;一个是存储数据的#xff0c;还有一个指针指向下一个节点。 该图就是一个简单单链表的结构图。
接口实现
SLNode* CreateNode(SLNDataType x);//申请节点
void SLTprint(SLNode* head);//打印链表
void SLTPushBack(SLNode*…单链表
结构 单链表结构中有两个数据一个是存储数据的还有一个指针指向下一个节点。 该图就是一个简单单链表的结构图。
接口实现
SLNode* CreateNode(SLNDataType x);//申请节点
void SLTprint(SLNode* head);//打印链表
void SLTPushBack(SLNode** pphead, SLNDataType x);//尾插
void SLTPushFront(SLNode** pphead, SLNDataType x);//头插
void SLTPopBack(SLNode** pphead);//尾删
void SLTPopFront(SLNode** pphead);//头删
SLNode* SLTFind(SLNode* phead, SLNDataType x);//查找
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);//任意位置插入
void SLTErase(SLNode** pphead, SLNode* pos);//任意位置删除
void SLTDestroy(SLNode** pphead);//销毁链表结构体的定义
typedef int SLNDataType;
typedef struct SListNode
{SLNDataType val;struct SList* next;
}SLNode;首先我们需要定义这样一个结构体用来实现链表。本章禁用数字来实现想用链表写一些学生信息的朋友们可以参考一下。
申请节点
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode(SLNode*)malloc(sizeof(SLNode));//动态申请内存SLNode大小即可存放到SLNode* 的指针中去if (newnode NULL)//如果申请失败则提醒一下{perror(malloc fail);exit(-1);}newnode-val x;//申请成功后将该数据存放到该指针指向的val中去newnode-next NULL;//将下一个节点设置为空指针return newnode;//返回值为该节点
}首先我们插入一个数据的时候必须要开辟一个空间也就是申请一个节点用来存放数据所以单独封装这个函数来实现这个功能。
链表的打印
void SLTprint(SLNode* head)
{assert(head);//断言保证传入指针非空SLNode* cur head;while (cur!NULL)//打印循环{printf(%d-, cur-val);//打印当前指针指向的val值cur cur-next;//将该指针指向的下一个指针的地址赋给该指针实现链表的遍历}printf(NULL\n);
}我们接受该指针之后检查是否为空把该指针重新赋给一个SLNode* 类型的cur进入打印循环循环结束条件为尾指针指向的指针不为空指针即可。
尾插
我们插入删除数据时候需要注意的一点是我们需要遍历修改的时一级指针那么我们就要用二级指针去接受这个参数了。
void SLTPushBack(SLNode** pphead, SLNDataType x)
{assert(pphead);//断言非空SLNode* newnode CreateNode(x);//将新开辟的节点赋给newnodeif (*pphead NULL)//链表为空{*pphead newnode;//直接将newnode赋给头节点}else{SLNode* tmp *pphead;//将头节点给一个临时变量while (tmp-next ! NULL)//遍历循环{tmp tmp-next;//可实现链表移动从而遍历}tmp-next newnode;//让最后一个节点指向newnode即可}
}我们实现尾部插入有两种情况首先就是如果该链表为空也就是头节点指向的是空指针那么我们直接将新开辟的节点赋给头节点即可其他的情况首先需要遍历链表到最后一个节点然后让最后一个节点指向新开辟的节点即可实现尾部插入。
头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{assert(pphead);//断言非空SLNode* newnode CreateNode(x);//将新开辟的节点赋给newnode节点newnode-next *pphead;//新开辟的节点指向的是pphead节点*pphead newnode;//newnode成为新的头节点
}实现头插是十分简单的直接看代码注释即可
尾删
void SLTPopBack(SLNode** pphead)
{assert(*pphead);//保证头节点不为空指针if ((*pphead)-next NULL)//仅有一个节点的情况{free(*pphead);//释放掉头节点*pphead NULL;//并将其赋值为空指针即可}else//多个节点的情况{SLNode* prev NULL;//双指针移动之实际指针SLNode* tail *pphead;//双指针移动之遍历指针while (tail-next! NULL)//遍历循环结束条件为tail的下一个节点不为空指针{prev tail;//将遍历指针赋值给实际指针tail tail-next;//遍历指针向后移动}
//循环结束此时实际指针指向倒数第二个节点而遍历指针指向最后一个节点free(tail);//释放掉此时指向最后一个节点的遍历节点tail NULL;//将释放后的遍历指针赋值为空指针prev-next NULL;//实际指针变成最后一个指针最后一个指针指向的是空指针}
}尾删我们需要分为两种情况首先是该链表只有一个头节点这种情况直接将头节点释放掉在赋值为空指针即可另外的就是该链表有多个节点那么此时我们选哟做到的就是遍历到最后一个节点之后将该节点释放掉即可这里我们用双指针的移动来实现释放节点。
头删
void SLTPopFront(SLNode** pphead)
{assert(*pphead);//保证头节点不为空SLNode* tmp *pphead;//将头节点赋给临时节点(*pphead) tmp-next;//临时节点也就是头节点指向的下一个节点赋给头节点成为新的头节点free(tmp);//释放掉已经不是头节点的节点tmp NULL;//将释放掉的节点赋值为空指针
}头删十分简单直接看代码注释即可。
查找
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{if (phead NULL)//头节点为空指针也就是链表为空无需打印{printf(链表为空无需查找);return NULL;//返回空指针}else//链表不为空{SLNode* cur phead;//将头节点赋给临时变量curwhile (cur)//遍历循环{if (cur-val x)//如果遍历的数据是所需要的数据{return cur;//返沪该指针}cur cur-next;//如果不是则移动临时变量cur实现链表的遍历}}return NULL;//找完没有则返回空指针
}查找的实现也很简单如果链表为空那么我们就无需查找返回空指针即可不为空我们遍历找到需要数据存放的节点之后返回这个节点就可以了如果遍历完没有找到就说明不存在该节点返回空指针即可。
任意位置的插入
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);//断言非空if (*pphead pos)//头插情况{SLTPushFront(pphead,x);}else//非头部插入情况{SLNode* newnode CreateNode(x);//新开辟的节点赋给newnode指针SLNode* cur *pphead;//头节点给临时变量curwhile (cur-next ! pos)//遍历到pos前一个位置{cur cur-next;//遍历移动}cur-next newnode;//此时让pos位置前一个节点指向要插入的节点newnode-next pos;//要插入的节点指向之后的节点实现链表的完整}
}首先如果插入的位置是头节点那么也就是头插了如果是其他位置那么首先需要遍历到该位置的前一个节点让该节点指向新插入的节点新插入的节点在指向原来该位置的节点就实现了该位置的数据插入。
任意位置的删除
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);//断言非空if (*pphead pos)//头删情况{SLTPopFront(pphead);}else//非头删情况{SLNode* cur *pphead;//头节点赋给临时变量curwhile (cur-next ! pos)//遍历到pos位置的前一个节点循环{cur cur-next;//临时变量移动链表的遍历}cur-next pos-next;//pos位置的前一个节点直线pos的下一个节点free(pos);//释放pospos NULL;//pos赋值为空指针}
}首先也是如果删除的节点是头节点直接头删即可不是则遍历到该位置的前一个位置跳过该位置指向下一个节点再将该位置节点释放掉即可。
链表的销毁
void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur *pphead;while (cur){SLNode* pur cur;cur cur-next;free(pur);}printf(链表已经成功销毁);
}链表的销毁十分简单遍历释放即可。
代码参考
鄙人不才大家可以参考一下链表代码的实现
SList.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.htypedef int SLNDataType;
typedef struct SListNode
{SLNDataType val;struct SList* next;
}SLNode;
SLNode* CreateNode(SLNDataType x);//申请节点
void SLTprint(SLNode* head);//打印链表
void SLTPushBack(SLNode** pphead, SLNDataType x);//尾插
void SLTPushFront(SLNode** pphead, SLNDataType x);//头插
void SLTPopBack(SLNode** pphead);//尾删
void SLTPopFront(SLNode** pphead);//头删
SLNode* SLTFind(SLNode* phead, SLNDataType x);//查找
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);//任意位置插入
void SLTErase(SLNode** pphead, SLNode* pos);//任意位置删除
void SLTDestroy(SLNode** pphead);//销毁链表SList.c
#define _CRT_SECURE_NO_WARNINGS
#includeSList.h
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode(SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-next NULL;return newnode;
}
void SLTprint(SLNode* head)
{assert(head);SLNode* cur head;while (cur!NULL){printf(%d-, cur-val);cur cur-next;}printf(NULL\n);
}
void SLTPushBack(SLNode** pphead, SLNDataType x)
{SLNode* newnode CreateNode(x);if (*pphead NULL){*pphead newnode;}else{SLNode* tmp *pphead;while (tmp-next ! NULL){tmp tmp-next;}tmp-next newnode;}
}
void SLTPushFront(SLNode** pphead, SLNDataType x)
{SLNode* newnode CreateNode(x);newnode-next *pphead;*pphead newnode;
}
void SLTPopBack(SLNode** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLNode* prev NULL;SLNode* tail *pphead;while (tail-next! NULL){prev tail;tail tail-next;}free(tail);tail NULL;prev-next NULL;}
}
void SLTPopFront(SLNode** pphead)
{assert(*pphead);SLNode* tmp *pphead;(*pphead) tmp-next;free(tmp);tmp NULL;
}
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{if (phead NULL){printf(链表为空无需查找);return NULL;}else{SLNode* cur phead;while (cur){if (cur-val x){return cur;}cur cur-next;}}return NULL;
}
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);if (*pphead pos){SLTPushFront(pphead,x);}else{SLNode* newnode CreateNode(x);SLNode* cur *pphead;while (cur-next ! pos){cur cur-next;}cur-next newnode;newnode-next pos;}
}
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);if (*pphead pos){SLTPopFront(pphead);}else{SLNode* cur *pphead;while (cur-next ! pos){cur cur-next;}cur-next pos-next;free(pos);pos NULL;}
}
void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur *pphead;while (cur){SLNode* pur cur;cur cur-next;free(pur);}printf(链表已经成功销毁);
}test.c
这个文件主要是为了检测链表代码是否有误用于调试链表。
#define _CRT_SECURE_NO_WARNINGS
#includeSList.h
void test1()
{SLNode* S1NULL;SLTPushBack(S1, 1);SLTPushBack(S1, 2);SLTPushBack(S1, 3);SLTPushBack(S1, 4);SLTprint(S1);
}
void test2()
{SLNode* S1 NULL;SLTPushBack(S1, 1);SLTPushBack(S1, 2);SLTPushBack(S1, 3);SLTPushBack(S1, 4);SLTPushFront(S1, 4);SLTprint(S1);
}
void test3()
{SLNode* S1 NULL;SLTPushBack(S1, 1);SLTPushBack(S1, 2);SLTPushBack(S1, 3);SLTPushBack(S1, 4);SLTPushFront(S1, 4);SLTPopBack(S1);SLTprint(S1);
}
void test4()
{SLNode* S1 NULL;SLTPushBack(S1, 1);SLTPushBack(S1, 2);SLTPushBack(S1, 3);SLTPushBack(S1, 4);SLTPushFront(S1, 4);SLTPopBack(S1);SLTPopFront(S1);SLTprint(S1);
}
void test5()
{SLNode* S1 NULL;SLTPushBack(S1, 1);SLTPushBack(S1, 2);SLTPushBack(S1, 3);SLTPushBack(S1, 4);SLTPushFront(S1, 5);SLNode* x SLTFind(S1,3);SLTprint(S1);printf(%d, x-val);}
void test6()
{SLNode* S1 NULL;SLTPushBack(S1, 1);SLTPushBack(S1, 2);SLTPushBack(S1, 3);SLTPushBack(S1, 4);SLTPushFront(S1, 4);SLTInsert(S1, S1, 5);SLNode* S2 S1-next;SLTInsert(S1, S2, 8);SLTprint(S1);
}
void test7()
{SLNode* S1 NULL;SLTPushBack(S1, 1);SLTPushBack(S1, 2);SLTPushBack(S1, 3);SLTPushBack(S1, 4);SLTPushFront(S1, 4);SLTInsert(S1, S1, 5);SLNode* S2 S1-next;SLTInsert(S1, S2, 8);SLTErase(S1, S1);SLTErase(S1, S2);SLTprint(S1);
}
void test8()
{SLNode* S1 NULL;SLTPushBack(S1, 1);SLTPushBack(S1, 2);SLTPushBack(S1, 3);SLTPushBack(S1, 4);SLTPushFront(S1, 4);SLTInsert(S1, S1, 5);SLNode* S2 S1-next;SLTInsert(S1, S2, 8);SLTErase(S1, S1);SLTErase(S1, S2);SLTprint(S1);SLTDestroy(S1);
}
int main()
{/*test1();*//*test2();*//*test3();*//*test4();*//*test5();*//*test6();*//*test7();*/test8();return 0;
}最后谢谢大家观看以后会奉上更多内容大家共同进步
