网站seo问题诊断工具,网站建设页头的设计,百度提交入口网站怎么看,服装设计网站有哪些单链表 1 链表的概念及结构 概念#xff1a;链表是一种物理存储结构上非连续、非顺序的存储结构#xff0c;数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。
在我们开始讲链表之前#xff0c;我们是写了顺序表#xff0c;顺序表就是类似一个数组的东西#xff0…
单链表 1 链表的概念及结构 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。
在我们开始讲链表之前我们是写了顺序表顺序表就是类似一个数组的东西它的存放是连续的优点有很多比如支持我们随机访问连续存放命中率高区别于单链表我们可以用类似数组的下标进行访问这大大的提高我们的效率但是也有缺点空间不够就要需要扩容扩容存在消耗的头部或者中间位置的插入删除需要挪动挪动数据也是存在消耗的。避免频繁扩容一次一般都是按倍数扩容可能存在空间扩容。
链表的优点 按需申请空间不用释放空间。 头部或者中间位置的插入和删除不需要挪动数据。 不存在空间浪费。
链表的缺陷 每一个数据都要存放一个指针去链表后面节点的地址。 不支持随机访问。
链表的结构
typedef int SLNodedataType;
typedef struct SList
{SLNodedataType data;struct SList* next;}SLNode;这个就是我们单链表的基本代码我们来用图更加清清楚的表示一下它完整的样子。 这就我们基本的逻辑结构它前一个的next是存放后面的地址的这样就能找到我们下一个节点。
单链表使用的时候相比和顺序表比较的话它的使用不会浪费空间我们需要一个节点就可以开辟一个节点出来供我们使用。但是它存储就不是连续的了。
那我们现在开始写代码来实现单链表。 单链表 首先我们要创建一个结构体。
typedef int SLNodedataType;
typedef struct SList
{SLNodedataType data;struct SList* next;}SLNode;接下来我们首先要打印我们的单链表 在这之前我们应该创建节点创捷节点很简单就是按照我们上面的图的前一个存放后面的地址。
//创建节点SLNode* n1 (SLNode*)malloc(sizeof(SLNode));assert(n1);SLNode* n2 (SLNode*)malloc(sizeof(SLNode));assert(n2);SLNode* n3 (SLNode*)malloc(sizeof(SLNode));assert(n3);SLNode* n4 (SLNode*)malloc(sizeof(SLNode));assert(n4);n1-data 1;n2-data 2;n3-data 3;n4-data 4;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;那下面就是我们的打印单链表。
void SListPrint(SLNode* plist)
{SLNode* cur plist;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL);printf(\n);}我们来测试一下看看效果。 可以看到我们的单链表也是成功的打印那接下来就是要写出我们的尾插函数。 写之前我们先来分析分析首先尾插一个节点进去那我们是不是要有一个这样的节点竟然这样就可以写一个创造节点的函数。就叫他CreateSListNode
SLNode* CreateSListNode(SLNodedataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));newnode-data x;newnode-next NULL;return newnode;
}写完这个那我们写一个尾插函数尾插的时候我们要想一想要传什么地址过去如果是有数据的话其实我们传一级地址就行但是如果是空的话就得传二级因为我们要改变plist的位置。但是也其实是相当于头插没节点的时候总不能在空指针后面插入。那我们写一个 吧。
void SListPushBcak(SLNode** plist, SLNodedataType x)
{SLNode*newnodeCreateSListNode(x);assert(plist);if (*plist NULL){plist newnode;}else{SLNode* tail *plist;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}}看一下我们编译的结果 最后也是成功的尾插进去那尾插之后就应该要写一个尾删。 写尾删的时候我们要先考虑怎么找到最后这和尾插一样遍历一遍找到最后一个然后free掉就行了。 代码
void SListPopBack(SLNode** plist)
{SLNode* tail *plist;SLNode* prev NULL;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;
}这其实就是用了一个双指针的方法找最后一个的前一个但是我们还需要注意链表不能为空空了怎么删除啊。所以改进一下。
void SListPopBack(SLNode** plist)
{assert(plist);assert(*plist);SLNode* tail *plist;SLNode* prev NULL;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;
}void test1()
{//创建节点SLNode* n1 (SLNode*)malloc(sizeof(SLNode));assert(n1);SLNode* n2 (SLNode*)malloc(sizeof(SLNode));assert(n2);SLNode* n3 (SLNode*)malloc(sizeof(SLNode));assert(n3);SLNode* n4 (SLNode*)malloc(sizeof(SLNode));assert(n4);n1-data 1;n2-data 2;n3-data 3;n4-data 4;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;SListPrint(n1);SListPushBcak(n1, 5);SListPushBcak(n1, 6);SListPushBcak(n1, 7);SListPushBcak(n1, 8);SListPrint(n1);SListPopBack(n1);SListPopBack(n1);SListPrint(n1);
}不过其实我们也可以不用双指针的办法。 那也整一个玩玩吧 void SListPopBack(SLNode** plist)
{assert(plist);assert(*plist);SLNode* tail *plist;while (tail-next-next ! NULL){tail tail-next;}free(tail-next);tail-next NULL;
其实道理是一样的就是找下下一个的节点是不是为空。 尾插写好就是头插来吧展示。
void SListPushFront(SLNode** plist, SLNodedataType x)
{assert(plist);SLNode* newnode CreateSListNode(x);if (*plist NULL){*plist newnode;}else{newnode-next *plist;*plist newnode;}}其实想明白也不难接下来就是头删。
void test1()
{//创建节点SLNode* n1 (SLNode*)malloc(sizeof(SLNode));assert(n1);SLNode* n2 (SLNode*)malloc(sizeof(SLNode));assert(n2);SLNode* n3 (SLNode*)malloc(sizeof(SLNode));assert(n3);SLNode* n4 (SLNode*)malloc(sizeof(SLNode));assert(n4);n1-data 1;n2-data 2;n3-data 3;n4-data 4;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;SListPrint(n1);SListPushBcak(n1, 5);SListPushBcak(n1, 6);SListPushBcak(n1, 7);SListPushBcak(n1, 8);SListPrint(n1);SListPopBack(n1);SListPopBack(n1);SListPrint(n1);SListPushFront(n1, 111);SListPushFront(n1, 222);SListPrint(n1);SListPopFront(n1);SListPopFront(n1);SListPopFront(n1);SListPrint(n1);}void SListPopFront(SLNode** plist)
{assert(plist);assert(*plist);SLNode* cur (*plist)-next;free(*plist);*plist cur;
}我们在写一个查找功能的代码
SLNode* SLFind(SLNode* plist, SLNodedataType x);查找我们可以返回这个节点这样就能和其他功能一起用比如修改数据或者在任意位置插入和删除。
SLNode* SLFind(SLNode* plist, SLNodedataType x)
{SLNode* pos plist;while (pos-data x){return pos;pos pos-next;}
}这是只考虑找到的情况下但是难免有时候会出现找不到的情况让我们来看一下吧写一个找不到情况下和找到情况下的代码。‘
SLNode* SLFind(SLNode* plist, SLNodedataType x)
{SLNode* pos plist;while (pos ! NULL){if (pos-data x){return pos;}pos pos-next;}return NULL;
}然后我们可以写一个函数来判断有没有找到。
SLNode*pos SLFind(n1, 111);if (pos ! NULL){printf(找到了\n);}else{printf(找不到\n);}
我们看完整代码。
void test1()
{//创建节点SLNode* n1 (SLNode*)malloc(sizeof(SLNode));assert(n1);SLNode* n2 (SLNode*)malloc(sizeof(SLNode));assert(n2);SLNode* n3 (SLNode*)malloc(sizeof(SLNode));assert(n3);SLNode* n4 (SLNode*)malloc(sizeof(SLNode));assert(n4);n1-data 1;n2-data 2;n3-data 3;n4-data 4;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;SListPrint(n1);SListPushBcak(n1, 5);SListPushBcak(n1, 6);SListPushBcak(n1, 7);SListPushBcak(n1, 8);SListPrint(n1);SListPopBack(n1);SListPopBack(n1);SListPrint(n1);SListPushFront(n1, 111);SListPushFront(n1, 222);SListPrint(n1);SListPopFront(n1);SListPopFront(n1);SListPopFront(n1);SListPrint(n1);SLNode*pos SLFind(n1, 111);if (pos ! NULL){printf(找到了\n);}else{printf(找不到\n);}}我们如果要找111发现没有找到因为头删的时候改掉其实我们竟然这样写了就可以写一个修改的代码这里就不演示了。 接下来我们要写的是在任意位置删除和插入节点。
void SListPushInsert(SLNode** plist, SLNode* pos, SLNodedataType x)
{assert(plist);assert(pos);SLNode* newnode CreateSListNode(x);if (pos *plist){SListPushFront(plist, x);}else{SLNode* prev *plist;while (prev-next ! pos){prev prev-next;}prev-next newnode;newnode-next pos;}
}测试代码
void test1()
{//创建节点SLNode* n1 (SLNode*)malloc(sizeof(SLNode));assert(n1);SLNode* n2 (SLNode*)malloc(sizeof(SLNode));assert(n2);SLNode* n3 (SLNode*)malloc(sizeof(SLNode));assert(n3);SLNode* n4 (SLNode*)malloc(sizeof(SLNode));assert(n4);n1-data 1;n2-data 2;n3-data 3;n4-data 4;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;SListPrint(n1);SListPushBcak(n1, 5);SListPushBcak(n1, 6);SListPushBcak(n1, 7);SListPushBcak(n1, 8);SListPrint(n1);SListPopBack(n1);SListPopBack(n1);SListPrint(n1);SListPushFront(n1, 111);SListPushFront(n1, 222);SListPrint(n1);SListPopFront(n1);SListPopFront(n1);SListPopFront(n1);SListPrint(n1);SLNode*pos SLFind(n1,3);if (pos ! NULL){printf(找到了\n);SListPushInsert(n1, pos, 10086);}else{printf(找不到\n);}SListPrint(n1);
}在任意位置删除
void SListPopInsert(SLNode** plist, SLNode* pos)
{assert(plist);assert(*plist);assert(pos);if (*plist pos){SListPopFront(plist);}else{SLNode* prev *plist;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);}
}其实还有可以在任意位置后删除这样更快就不用找那个位置前一个位置了这里就不展示了 完整代码
#define _CRT_SECURE_NO_WARNINGS 1#includestdio.h
#includeassert.h
#includestdlib.htypedef int SLNodedataType;
typedef struct SList
{SLNodedataType data;struct SList* next;}SLNode;void SListPrint(SLNode* plist);SLNode* CreateSListNode(SLNodedataType x);void SListPushBcak(SLNode** plist, SLNodedataType x);void SListPopBack(SLNode** plist);void SListPushFront(SLNode** plist, SLNodedataType x);void SListPopFront(SLNode** plist);SLNode* SLFind(SLNode* plist, SLNodedataType x);void SListPushInsert(SLNode** plist, SLNode* pos, SLNodedataType x);void SListPopInsert(SLNode** plist, SLNode* pos);
#includeSList.hvoid SListPrint(SLNode* plist)
{SLNode* cur plist;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL);printf(\n);}SLNode* CreateSListNode(SLNodedataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));newnode-data x;newnode-next NULL;return newnode;
}void SListPushBcak(SLNode** plist, SLNodedataType x)
{SLNode*newnodeCreateSListNode(x);assert(plist);if (*plist NULL){plist newnode;}else{SLNode* tail *plist;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}}void SListPopBack(SLNode** plist)
{assert(plist);assert(*plist);SLNode* tail *plist;SLNode* prev NULL;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;
}
//
//void SListPopBack(SLNode** plist)
//{
// assert(plist);
// assert(*plist);
// SLNode* tail *plist;
//
// while (tail-next-next ! NULL)
// {
//
// tail tail-next;
// }
// free(tail-next);
// tail-next NULL;
//
//}void SListPushFront(SLNode** plist, SLNodedataType x)
{assert(plist);SLNode* newnode CreateSListNode(x);if (*plist NULL){*plist newnode;}else{newnode-next *plist;*plist newnode;}}void SListPopFront(SLNode** plist)
{assert(plist);assert(*plist);SLNode* cur (*plist)-next;free(*plist);*plist cur;
}//SLNode* SLFind(SLNode* plist, SLNodedataType x)
//{
// SLNode* pos plist;
// while (pos-data x)
// {
// return pos;
// pos pos-next;
// }
//}SLNode* SLFind(SLNode* plist, SLNodedataType x)
{SLNode* pos plist;while (pos ! NULL){if (pos-data x){return pos;}pos pos-next;}return NULL;
}void SListPushInsert(SLNode** plist, SLNode* pos, SLNodedataType x)
{assert(plist);assert(pos);SLNode* newnode CreateSListNode(x);if (pos *plist){SListPushFront(plist, x);}else{SLNode* prev *plist;while (prev-next ! pos){prev prev-next;}prev-next newnode;newnode-next pos;}
}void SListPopInsert(SLNode** plist, SLNode* pos)
{assert(plist);assert(*plist);assert(pos);if (*plist pos){SListPopFront(plist);}else{SLNode* prev *plist;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);}
}测试主函数的也发一下吧大家可以不用放一起测试有点看不过来。
#includeSList.hvoid test1()
{//创建节点SLNode* n1 (SLNode*)malloc(sizeof(SLNode));assert(n1);SLNode* n2 (SLNode*)malloc(sizeof(SLNode));assert(n2);SLNode* n3 (SLNode*)malloc(sizeof(SLNode));assert(n3);SLNode* n4 (SLNode*)malloc(sizeof(SLNode));assert(n4);n1-data 1;n2-data 2;n3-data 3;n4-data 4;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;SListPrint(n1);SListPushBcak(n1, 5);SListPushBcak(n1, 6);SListPushBcak(n1, 7);SListPushBcak(n1, 8);SListPrint(n1);SListPopBack(n1);SListPopBack(n1);SListPrint(n1);SListPushFront(n1, 111);SListPushFront(n1, 222);SListPrint(n1);SListPopFront(n1);SListPopFront(n1);SListPopFront(n1);SListPrint(n1);SLNode*pos SLFind(n1,3);if (pos ! NULL){printf(找到了\n);SListPushInsert(n1, pos, 10086);}else{printf(找不到\n);}SListPrint(n1);
}
int main()
{test1();return 0;
}今天的分享就到这里我们下次再见。
