清河做网站哪儿好,苏州博客关键词优化,建设银行国管公积金管理中心网站,网站调用网页怎么做目录 概念 链表的单个结点 链表的打印操作
新结点的申请
尾部插入 头部插入
尾部删除
头部删除 查找
在指定位置之前插入数据
在任意位置之后插入数据
测试运行一下#xff1a; 删除pos结点 删除pos之后结点 销毁链表 概念
单链表是一种在物理存储结构上非连续、非顺序…目录 概念 链表的单个结点 链表的打印操作
新结点的申请
尾部插入 头部插入
尾部删除
头部删除 查找
在指定位置之前插入数据
在任意位置之后插入数据
测试运行一下 删除pos结点 删除pos之后结点 销毁链表 概念
单链表是一种在物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接顺序实现的。 链表的每个结点有两个部分分别是数据和指向下个结点的指针每个链表的最后一个结点的下一个结点为NULL不能对NULL解引用。 放一张bit课件里的图,我觉得很形象 链表的单个结点
typedef int SLDataType;//重定义一下在链表内存放的数据类型方便后期对类型进行统一修改//链表的单个结点
typedef struct SListNode {//Single List Node :链表结点SLDataType data;//存放的数据struct SListNode* next;//指向下一个结点的指针
}SLNode;//重定义名字方便后期使用 链表的打印操作
//链表的打印操作
void SLPrint(SLNode* phead) {assert(phead);//不能传入空指针SLNode* pcur phead;//pointer cursor:指针光标不让头结点丢失(虽然不会改变头结点的指向)while (pcur) {//等同于pcur!NULLprintf(%d-, pcur-data);//打印此结点的数据pcur pcur-next;//使pcur指向下一个结点}printf(NULL\n);
} 新结点的申请
后面会涉及到新结点的插入申请新结点可以封装成一个函数避免代码冗余
//新结点的申请
SLNode* SLBuyNode(SLDataType x) {SLNode* node (SLNode*)malloc(sizeof(SLNode));if (!node) {//返回值为空,申请失败(一般是空间不足了)直接退出perror(malloc fail);exit(1);}node-data x;//将数据赋给datanode-next NULL;//将下一个节点置为NULL;return node;
} 尾部插入
//尾部插入
void SLPushBack(SLNode** pphead, SLDataType x) {//注意在这里我们传参的是二级指针因为我们需要在函数内部改变头结点的指向assert(pphead);//不能传NULL//新结点的申请SLNode* nodeSLBuyNode(x);if (*pphead NULL) {*pphead node;}else {SLNode* pcur *pphead;while (pcur-next) {//找到next元素为NULL的结点也就是为链表尾部pcur pcur-next;}pcur-next node;}}
测试运行一下 头部插入
//头部插入
void SLPushFront(SLNode** pphead, SLDataType x) {assert(pphead);SLNode* node SLBuyNode(x);//这里需要处理头结点为空的情况吗不需要因为没有涉及到解引用其元素node-next *pphead;*pphead node;
}测试运行一下 尾部删除
//尾部删除
void SLPopBack(SLNode** pphead) {assert(*pphead pphead);//if (!(*pphead)-next) {//处理只有一个元素的情况free(*pphead);*pphead NULL;}else {SLNode* prev NULL;SLNode* pcur *pphead;while (pcur-next) {//找到尾结点前一个结点prev pcur;pcur pcur-next;}free(pcur);//将尾结点释放pcur NULL;prev-next NULL;//将尾结点的前一个结点的next元素置为NULL}
}
测试运行一下 头部删除
//头部删除
void SLPopFront(SLNode** pphead) {assert(*pphead pphead);SLNode* next (*pphead)-next;//保存头结点的下一个结点地址free(*pphead);//释放头结点*pphead next;//使头结点指向下一个结点
}
测试运行一下 查找
在链表中想要对指定位置进行操作不能使用下标所以我们必须找到指定位置的地址才能对其进行操作。
//查找
SLNode* SLFind(SLNode* phead, SLDataType x) {assert(phead);SLNode* pcur phead;while (pcur) {if (pcur-data x) {return pcur;}pcur pcur-next;}return NULL;
} 在指定位置之前插入数据
//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x) {assert(pphead pos *pphead);//pos和pphead不能为空,以及pphead指向空间不能为空if (*pphead pos) {//处理头插的情况SLPushFront(pphead,x);}else {SLNode* node SLBuyNode(x);SLNode* pcur *pphead;while (pcur-next ! pos) {//找到pos前一个结点pcur pcur-next;}node-next pcur-next;pcur-next node;}
}
测试运行一下 在任意位置之后插入数据
//在任意位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x) {assert(pos);//pos不能为空SLNode* node SLBuyNode(x);node-next pos-next;pos-next node;
}
测试运行一下 删除pos结点
//删除pos结点
void SLErase(SLNode** pphead, SLNode* pos) {assert(*pphead pphead pos);if (*pphead pos) {//处理头删的情况SLPopFront(pphead);}else {SLNode* pcur *pphead;while (pcur-next! pos) {pcur pcur-next;}pcur-next pos-next;free(pos);pos NULL;}
} 测试运行一下 删除pos之后结点
//删除pos之后结点
void SLEraseAfter(SLNode* pos) {assert(pos pos-next);//pos后面的结点也不能为空SLNode* next pos-next;pos-next next-next;free(next);next NULL;
} 测试运行一下 销毁链表
//销毁链表
void SLDestory(SLNode** pphead) {assert(pphead *pphead);SLNode* pcur *pphead;while (pcur) {SLNode* nextnode pcur-next;//使用一个变量接受下一个结点地址free(pcur);pcur nextnode;}*pphead NULL;
}
