潍坊市网站建设设计,去掉自豪地采用wordpress,网站制作的服务商,如何修改网站后台时间前言
上一章#xff0c;我们讲了数据结构--动态顺序表#xff0c;我们会发现有以下问题#xff1a; 1.当我们要头部或者插入或删除时#xff0c;都需要进行位置挪动#xff0c;腾出某一个位置#xff0c;时间复杂度为0(N)#xff1b; 2.增容需要申请新空间#xff0c;…前言
上一章我们讲了数据结构--动态顺序表我们会发现有以下问题 1.当我们要头部或者插入或删除时都需要进行位置挪动腾出某一个位置时间复杂度为0(N) 2.增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 3.增容会有一定的浪费空间例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 下面我们来看看单链表这种线性结构 链表
概念与结构
链表是一种常见的数据结构用于存储和组织数据。它由一系列节点组成每个节点包含两部分数据和指向下一个节点的指针。
链表中的节点在内存中可以分布在任意位置不像数组那样需要连续的存储空间。每个节点都包含了存储的数据以及指向下一个节点的指针。通过这种方式链表可以灵活地分配和管理内存空间。就像一节节连动的火车车厢 在数据结构中呈现 逻辑图中呈现 在逻辑图中链式结构是连续性的但实际上不一样连续从数据结构中看出链表是通过地址来联系在一起的不需要地址的连续性在我们要解决链表相关问题时只需要画出逻辑图即可 注意 结点的空间在堆区中开辟堆区中申请出的空间会按照一定的策略进行分配两次申请的空间可能连续可能不连续 链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
可以通过一定的组合达成不同种类的链表
这里我们比较常用的是有两种结构 在这里我们将先实现无头单向非循环链表这是链表中结构最为简单的简称单链表。 单链表的接口实现
先写一下它的结构
#includestdio.h
#includeassert.h
#includestdlib.htypedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SListNode* next;}SLTNode; 结构体中放入一个数据存储类型和一个结构体指针结构体指针存放下一个结点的地址 单链表打印
void SLTrint(SLTNode* phead)
{SLTNode* cur phead;while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
} 将链表从头到尾遍历一遍用一个cur指针来进行移动在while循环中不断遍历打印出结果打印完就进入下一个结点 增加链表结点
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(mallco fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
} 用动态内存分配进行扩容同时对data和next进行初始化最后返回结点 尾插
void SLPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);if (* pphead NULL){* pphead newnode;}else{SLTNode* tail * pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}} 这里要注意我们的形参用到了二级指针因为当结构体指针为空时我们就需要对结构体指针进行改变用二级指针接收结构体指针的地址能够有效的访问否则将会报错当结构体指针不为空时就利用结构体指针通过循环访问到尾结点然后在尾结点进行连接 验证
void Test3()
{SLTNode* plist NULL;SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLTrint(plist);}
int main()
{Test3();return 0;
} 尾删
void SLPopBack(SLTNode** pphead)
{assert(pphead);//判空assert(*pphead);//一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//其他else{SLTNode* tailPrev NULL;SLTNode* tail *pphead;while (tail-next){tailPrev tail;tail tail-next;}free(tail);tailPrev-next NULL;}
} 当删除的是第一个结点将会改变结构体指针的地址所以形参要引用二级指针其他情况就先找到尾结点然后进行删除 验证
void Test3()
{SLTNode* plist NULL;SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLTrint(plist);SLPopBack(plist);SLTrint(plist);}
int main()
{Test3();return 0;
} 头插头删
void SLPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;}void SLPopFront(SLTNode** pphead)
{ assert(pphead);//判空assert(*pphead);//其他SLTNode* newhead (*pphead)-next;free(*pphead);*pphead newhead;
} 头插相对尾插来说比较容易因为有头指针所以不用遍历循环来找到尾结点并且无论头节点是否为空操作程序都保持一致 头删只要找到头结点的下一个结点那么就可以删除了 验证
void Test2()
{SLTNode* plist NULL;SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPushBack(plist, 5);SLTrint(plist);SLPushFront(plist, 6);SLPushFront(plist, 7);SLPushFront(plist, 8);SLPushFront(plist, 9);SLTrint(plist);SLPopFront(plist);SLTrint(plist);}int main()
{Test2();return 0;
} 查找与插入
SLTNode* SLFind(SLTNode* phead, SLTDataType x)
{//判空assert(phead);SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;} 查找在循环里面通过结点的data与x进行匹配找到就返回该结点找不到返回空如果有多个结点的data与x一致返回链表最接近头指针的 插入是在pos后面进行插入这样插入比较方便不用考虑头指针是否为空的问题 验证
void Test3()
{SLTNode* plist NULL;SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLTrint(plist);SLTNode* pos SLFind(plist, 3);SLTInsertAfter(pos, 88);SLTrint(plist);}
int main()
{Test3();return 0;
} 删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (pos *pphead){SLPopFront(pphead);}else{SLTNode* perv *pphead;while (perv-next ! pos){perv perv-next;}perv-next pos-next;free(pos);}
}void SLTEraseAfter(SLTNode* pos)
{assert(pos);//检查尾节点assert(pos-next);SLTNode* posNext pos-next;pos-next posNext-next;free(posNext);} 第一种删除是删除pos结点但需要判断该结点是否为首结点而且需要遍历找到pos结点的前一个结点比较麻烦 第二种删除是删除pos结点后一个结点只需要通过pos结点连接到下下一个结点即可最后free掉pos的下一个结点 验证
void Test3()
{SLTNode* plist NULL;SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLTrint(plist);SLTNode* pos SLFind(plist, 3);SLTInsertAfter(pos, 88);SLTrint(plist);SLTErase(plist, pos);SLTrint(plist);}
int main()
{Test3();return 0;
} void Test3()
{SLTNode* plist NULL;SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLTrint(plist);SLTNode* pos SLFind(plist, 3);SLTInsertAfter(pos, 88);SLTrint(plist);SLTEraseAfter(pos);SLTrint(plist);}
int main()
{Test3();return 0;
} 摧毁
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur *pphead;while (cur){SLTNode* prev cur;cur cur-next;free(prev);}*pphead NULL;
} 通过记住头结点的下一个结点free掉头节点然后头节点的下一个结点成为新的头节点 验证
void Test3()
{SLTNode* plist NULL;SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLTrint(plist);SLTNode* pos SLFind(plist, 3);SLTInsertAfter(pos, 88);SLTrint(plist);SLTDestroy(plist);SLTrint(plist);
}
int main()
{Test3();return 0;
} 完整代码
slist.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.htypedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SListNode* next;}SLTNode;void SLTrint(SLTNode* phead);
SLTNode* BuySListNode(SLTDataType x);
void SLPushBack(SLTNode** pphead, SLTDataType x);
void SLPushFront(SLTNode** pphead, SLTDataType x);
void SLPopBack(SLTNode** pphead);
void SLPopFront(SLTNode** pphead);
SLTNode* SLFind(SLTNode* phead, SLTDataType x);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode** phead);
slist.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSlist.hvoid SLTrint(SLTNode* phead)
{SLTNode* cur phead;while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(mallco fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}void SLPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);if (* pphead NULL){* pphead newnode;}else{SLTNode* tail * pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}}void SLPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;}void SLPopBack(SLTNode** pphead)
{assert(pphead);//判空assert(*pphead);//一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//其他else{SLTNode* tailPrev NULL;SLTNode* tail *pphead;while (tail-next){tailPrev tail;tail tail-next;}free(tail);tailPrev-next NULL;}
}
void SLPopFront(SLTNode** pphead)
{ assert(pphead);//判空assert(*pphead);//其他SLTNode* newhead (*pphead)-next;free(*pphead);*pphead newhead;
}SLTNode* SLFind(SLTNode* phead, SLTDataType x)
{//判空assert(phead);SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (pos *pphead){SLPopFront(pphead);}else{SLTNode* perv *pphead;while (perv-next ! pos){perv perv-next;}perv-next pos-next;free(pos);}
}void SLTEraseAfter(SLTNode* pos)
{assert(pos);//检查尾节点assert(pos-next);SLTNode* posNext pos-next;pos-next posNext-next;free(posNext);}void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur *pphead;while (cur){SLTNode* prev cur;cur cur-next;free(prev);}*pphead NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSlist.hvoid Test1()
{int n;SLTNode* plist NULL;printf(请输入链表长度);scanf(%d, n);printf(请输入值);for (int i 0; i n; i){int val;scanf(%d, val);SLTNode* newnode BuySListNode(val);newnode-next plist;plist newnode;}SLTrint(plist);
}void Test2()
{SLTNode* plist NULL;SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPushBack(plist, 5);SLTrint(plist);SLPushFront(plist, 6);SLPushFront(plist, 7);SLPushFront(plist, 8);SLPushFront(plist, 9);SLTrint(plist);SLPopFront(plist);SLTrint(plist);}void Test3()
{SLTNode* plist NULL;SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLTrint(plist);SLTNode* pos SLFind(plist, 3);SLTInsertAfter(pos, 88);SLTrint(plist);SLTDestroy(plist);SLTrint(plist);
}
int main()
{Test3();return 0;
}
