职业教育培训网站,重庆市造价工程新希望官网,佛山市专注网站建设平台,那里有正规网站开发培训学校我们之前已经介绍过链表的知识了#xff0c;这里我们直接开始实现带头双向循环链表
数据结构之单链表#xff08;不带头单向非循环链表#xff09;-CSDN博客 第一步#xff1a;定义结构体
//定义结构体
typedef int SLTDateType;
typedef struct Listnode
{SLTDateType d…
我们之前已经介绍过链表的知识了这里我们直接开始实现带头双向循环链表
数据结构之单链表不带头单向非循环链表-CSDN博客 第一步定义结构体
//定义结构体
typedef int SLTDateType;
typedef struct Listnode
{SLTDateType date;struct Listnode* prev;struct Listnode* next;
}SL;
注意我们这里要两个指针一个指向链表前一个一个指向链表下一个。 第二步实现开辟空间函数
//开辟空间函数定义
SL* BuyListNode(SLTDateType x)
{SL* nownode (SL*)malloc(sizeof(SL));//动态开辟一个结构体大小的空间nownode-date x;//将开辟的空间中结构体成员date赋值为xnownode-next NULL;//将该结构体成员尾指针置为空nownode-prev NULL;//将该结构体成员头指针置为空return nownode;//返回该结构体地址
}
第三步实现初始化函数
//初始化函数定义
SL* ListInit()
{//该函数是创造一个head结构体放在链表的开头满足带头链表SL* phead BuyListNode(0);//将该结构开辟空间并且将成员date赋值0phead-next phead;//将phead的尾指针指向自己phead-prev phead;//将phead的头指针指向自己return phead;//返回该结构体地址
}
第四步实现双向链表打印
// 双向链表打印定义
void ListPrint(SL* phead)
{assert(phead);SL* cur phead-next;while (cur ! phead){printf(%d , cur-date);cur cur-next;}printf(\n);
}
第五步实现四大接口头删 尾删 头插 尾插
//双向链表尾插定义
void ListPushBack(SL* phead, SLTDateType x)
{/*尾插的实现可以分成四步1.将链表的最后一个元素尾指针从指向链表第一个元素变成指向开辟的结构体2.将开辟的结构体头指针指向链表最后一个元素3.将链表的第一个元素头指针从指向链表最后一个元素变成指向开辟的结构体4.将开辟的结构体尾指针指向链表第一个元素*/assert(phead);SL* tail phead-prev;//定义一个结构体指针指向头位置的头指针指向的位置即为链表的最后一个元素SL* nownode BuyListNode(x);//开辟一个结构体空间tail-next nownode;//将tail结构体尾指针指向开辟的结构体的位置nownode-prev tail;//将开辟的结构体的头指针指向tail的位置即为链表的最后一个元素nownode-next phead;//将开辟的结构体的尾指针指向链表的开头即为pheadphead-prev nownode;//将phead的头指针指向开辟的结构体nownode
}
// 双向链表头插定义
void ListPushFront(SL* phead, SLTDateType x)
{assert(phead);//检查assert(phead-next!NULL);//检查SL* nownode BuyListNode(x);SL* next phead-next;phead-next nownode;nownode-prev phead;nownode-next next;next-prev nownode;
}
// 双向链表尾删定义
void ListPopBack(SL* phead)
{assert(phead);//检查assert(phead-next ! NULL);//检查SL* first phead-prev;SL* second first-prev;phead-prev second;second-next phead;free(first);//释放firstfirst NULL;//指针置为空
}
// 双向链表头删定义
void ListPopFront(SL* phead)
{assert(phead);SL* first phead-next;SL* second first-next;phead-next second ;second-prev phead ;free(first);first NULL;
}
大家可以自己画图理解下我的第一个注释写的详细
下面我们检验代码
#include SList.h
void test1()
{//我们实现尾插1 2 3再头插3 2 1然后打印观察// 再头删去 3 2 尾删 3 2,然后打印观察//调用函数测试SL* plist ListInit();//双向链表尾插调用ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);// 双向链表头插调用ListPushFront(plist,3);ListPushFront(plist,2);ListPushFront(plist,1);//双向链表打印调用ListPrint(plist);// 双向链表头删调用ListPopFront(plist);ListPopFront(plist);// 双向链表尾删调用ListPopBack(plist);ListPopBack(plist);// 双向链表打印调用ListPrint(plist);
}
int main()
{test1();return 0;
}
结果 噢耶对了现在我们可以继续下一步了 第六步实现特殊接口
// 双向链表查找定义
SL* ListFind(SL* phead, SLTDateType x)
{assert(phead);SL* cur phead-next;while (cur ! phead){if (cur-date x ){return cur;}cur cur-next;}return NULL;
}
// 双向链表在pos的前面进行插入定义
void ListInsert(SL* pos, SLTDateType x)
{assert(pos);SL* first pos-prev;SL* newnode BuyListNode(x);first-next newnode;newnode-prevfirst;newnode-nextpos;pos-prevnewnode;
}
// 双向链表删除pos位置的结点定义
void ListErase(SL* pos)
{assert(pos);SL* first pos-prev;SL* second pos-next;first-next second;second-prev first;
}
// 双向链表销毁定义
void ListDestory(SL* phead)
{assert(phead);SL* cur phead-next;while (cur ! phead){SL* cur2 cur-next;free(cur);cur cur2;}free(phead);phead NULL;
}
再次进行检查
void test2()
{SL* plist ListInit();//双向链表尾插调用ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);// 双向链表打印调用ListPrint(plist);SL* pos ListFind(plist, 2);if(pos ! NULL){// 双向链表在pos的前面进行插入ListInsert(pos, 30);// 双向链表打印调用ListPrint(plist);// 双向链表删除pos位置的结点ListErase(pos);// 双向链表打印调用ListPrint(plist);}free(pos);pos NULL;// 双向链表销毁ListDestory(plist);
}
int main()
{//test1();test2();return 0;
}
结果 综上我们成功实现了带头双向循环链表
全部代码如下
这个是SList.c文件
#include SList.h//开辟空间函数定义
SL* BuyListNode(SLTDateType x)
{SL* nownode (SL*)malloc(sizeof(SL));//动态开辟一个结构体大小的空间if (nownode NULL){perror(nownode);exit(-1);}nownode-date x;//将开辟的空间中结构体成员date赋值为xnownode-next NULL;//将该结构体成员尾指针置为空nownode-prev NULL;//将该结构体成员头指针置为空return nownode;//返回该结构体地址
}
//初始化函数定义
SL* ListInit()
{//该函数是创造一个head结构体放在链表的开头满足带头链表SL* phead BuyListNode(0);//将该结构开辟空间并且将成员date赋值0phead-next phead;//将phead的尾指针指向自己phead-prev phead;//将phead的头指针指向自己return phead;//返回该结构体地址
}
// 双向链表打印定义
void ListPrint(SL* phead)
{assert(phead);SL* cur phead-next; while (cur ! phead){printf(%d , cur-date);cur cur-next;}printf(\n);
}
//双向链表尾插定义
void ListPushBack(SL* phead, SLTDateType x)
{/*尾插的实现可以分成四步1.将链表的最后一个元素尾指针从指向链表第一个元素变成指向开辟的结构体2.将开辟的结构体头指针指向链表最后一个元素3.将链表的第一个元素头指针从指向链表最后一个元素变成指向开辟的结构体4.将开辟的结构体尾指针指向链表第一个元素*/assert(phead);SL* tail phead-prev;//定义一个结构体指针指向头位置的头指针指向的位置即为链表的最后一个元素SL* nownode BuyListNode(x);//开辟一个结构体空间tail-next nownode;//将tail结构体尾指针指向开辟的结构体的位置nownode-prev tail;//将开辟的结构体的头指针指向tail的位置即为链表的最后一个元素nownode-next phead;//将开辟的结构体的尾指针指向链表的开头即为pheadphead-prev nownode;//将phead的头指针指向开辟的结构体nownode
}
// 双向链表头插定义
void ListPushFront(SL* phead, SLTDateType x)
{assert(phead);//检查assert(phead-next!NULL);//检查SL* nownode BuyListNode(x);SL* next phead-next;phead-next nownode;nownode-prev phead;nownode-next next;next-prev nownode;
}
// 双向链表尾删定义
void ListPopBack(SL* phead)
{assert(phead);//检查assert(phead-next ! NULL);//检查SL* first phead-prev;SL* second first-prev;phead-prev second;second-next phead;free(first);//释放firstfirst NULL;//指针置为空
}
// 双向链表头删定义
void ListPopFront(SL* phead)
{assert(phead);SL* first phead-next;SL* second first-next;phead-next second ;second-prev phead ;free(first);first NULL;
}
// 双向链表查找定义
SL* ListFind(SL* phead, SLTDateType x)
{assert(phead);SL* cur phead-next;while (cur ! phead){if (cur-date x ){return cur;}cur cur-next;}return NULL;
}
// 双向链表在pos的前面进行插入定义
void ListInsert(SL* pos, SLTDateType x)
{assert(pos);SL* first pos-prev;SL* newnode BuyListNode(x);first-next newnode;newnode-prevfirst;newnode-nextpos;pos-prevnewnode;
}
// 双向链表删除pos位置的结点定义
void ListErase(SL* pos)
{assert(pos);SL* first pos-prev;SL* second pos-next;first-next second;second-prev first;
}
// 双向链表销毁定义
void ListDestory(SL* phead)
{assert(phead);SL* cur phead-next;while (cur ! phead){SL* cur2 cur-next;free(cur);cur cur2;}free(phead);phead NULL;
}头文件SList.h文件
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
//定义结构体
typedef int SLTDateType;
typedef struct Listnode
{SLTDateType date;struct Listnode* prev;struct Listnode* next;
}SL;
//双向链开辟空间函数声明
SL* BuyListNode(SLTDateType x);
//双向链初始化函数声明
SL* ListInit();
// 双向链表打印声明
void ListPrint(SL* phead);
//双向链表尾插声明
void ListPushBack(SL* phead, SLTDateType x);
// 双向链表头插声明
void ListPushFront(SL* plist, SLTDateType x);
// 双向链表尾删声明
void ListPopBack(SL* phead);
// 双向链表头删声明
void ListPopFront(SL* phead);
// 双向链表查找声明
SL* ListFind(SL* phead, SLTDateType x);
// 双向链表在pos的前面进行插入声明
void ListInsert(SL* pos, SLTDateType x);
// 双向链表删除pos位置的结点声明
void ListErase(SL* pos);
// 双向链表销毁声明
void ListDestory(SL* phead);
下面是我们的调试文件:test.c
#include SList.h
void test1()
{//我们实现尾插1 2 3再头插3 2 1然后打印观察// 再头删去 3 2 尾删 3 2,然后打印观察//调用函数测试SL* plist ListInit();//双向链表尾插调用ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);// 双向链表头插调用ListPushFront(plist,3);ListPushFront(plist,2);ListPushFront(plist,1);//双向链表打印调用ListPrint(plist);// 双向链表头删调用ListPopFront(plist);ListPopFront(plist);// 双向链表尾删调用ListPopBack(plist);ListPopBack(plist);// 双向链表打印调用ListPrint(plist);
}
void test2()
{SL* plist ListInit();//双向链表尾插调用ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);// 双向链表打印调用ListPrint(plist);SL* pos ListFind(plist, 2);if(pos ! NULL){// 双向链表在pos的前面进行插入ListInsert(pos, 30);// 双向链表打印调用ListPrint(plist);// 双向链表删除pos位置的结点ListErase(pos);// 双向链表打印调用ListPrint(plist);}free(pos);pos NULL;// 双向链表销毁ListDestory(plist);
}
int main()
{//test1();test2();return 0;
} 希望大家坚持学下去在链表这里你可以发现无穷的乐趣当然建议大家链表这里还是多刷题这样才能帮助我们更好理解它。
