中国十大旅游网站,值得做的网站,淘宝客帮做网站,网站建设收费标准信息目录
关于链表的分类 双向链表结构体
初始化
尾插 头插
打印
判断是否为空
尾删
头删
查找
指定位置之后的插入
指定位置的删除
销毁 关于链表的分类
根据链表的三大特性#xff0c;单向or双向、带头or不带头、循环or不循环#xff0c;可将链表分为2*2*2#xf…目录
关于链表的分类 双向链表结构体
初始化
尾插 头插
打印
判断是否为空
尾删
头删
查找
指定位置之后的插入
指定位置的删除
销毁 关于链表的分类
根据链表的三大特性单向or双向、带头or不带头、循环or不循环可将链表分为2*2*28种链表前面我们已经实现了单链表即不带头单向非循环链表它的结构简单不常用于单独存储数据而是作为其他数据结构的子结构。
实际运用中只有单链表不带头单向非循环链表和双向链表带头双向循环链表运用最多带头双向循环链表结构最复杂常常运用于单独存储数据使用的链表结构也几乎都是双向带头链表。
附上一张bit课件的图 双向链表结构体
放一张bi课件的图片很形象 //重定义一下类型方便统一修改
typedef int LNDataType;typedef struct ListNode {LNDataType data;//数据struct ListNode* prev;//前一个结点struct ListNode* next;//后一个结点
}LN;初始化
双向链表的初始化应创建一个哨兵结点也称头结点它存放的数据是无效数据假定-1
所以我们先实现一个创建单节点的函数
//创建新节点
LN* LNBuyNode(LNDataType x) {LN* node (LN*)malloc(sizeof(LN));//开辟空间if (!node) {//判断为空perror(malloc fail!);exit(1);}node-data x;//传入数据node-next node-prev node;//双向循环链表单节点也应满足循环不能初始化为NULL;return node;
}
接着我们就可方便地调用创建一个哨兵结点
//初始化
void LNInit(LN** pphead) {assert(pphead);*ppheadLNBuynode(-1);
} 尾插
//尾插
void LNPushBack(LN* phead, LNDataType x) {assert(phead);LN* node LNBuyNode(x);//创建新结点node-next phead;//先对新申请的结点参数进行操作防止对原链表造成改变node-prev phead-prev;phead-prev-next node;//更改尾结点的next参数的指向phead-prev node;//更改头结点prev结点的指向
}
运行测试一下 头插
注意头插的操作是在哨兵位后插入双向链表为空的情况也是只剩下哨兵位因为哨兵位并没有存储有效数据。
//头插
void LNPushFront(LN* phead, LNDataType x) {assert(phead);LN* node LNBuyNode(x);//创建新结点node-next phead-next;//先对新申请的结点参数进行操作防止对原链表造成改变node-prev phead;phead-next-prev node;//更改头结点的下一个结点的prev指向phead-next node;//更改头结点的next指向
}
运行测试一下 打印
//打印
void LNPrint(LN* phead) {assert(phead);LN* pcur phead-next;//因为头结点内存储的是无效数据所以我们让它指向下一个结点while (pcur!phead) {//与头结点相遇说明我们已经遍历完整个链表了printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
} 判断是否为空
双向链表为空的情况是只有一个哨兵结点而不是NULL
//判断是否为空
bool LNEmpty(LN* phead) {assert(phead);return phead-next phead;
} 尾删
//尾删
void LNPopBack(LN* phead) {assert(phead);assert(!LNEmpty(phead));//删除操作至少有一个有效数据//LNEmptys是空返回true,取反保证不为空LN* del phead-prev;//保存要删除的结点phead-prev del-prev;//对要受影响的结点的参数进行更改phead-prev-next phead;free(del);//释放掉该地址del NULL;
}
运行测试一下 头删
//头删
void LNPopFront(LN* phead) {assert(phead);assert(!LNEmpty(phead));LN* del phead-next;//保存要删除的结点phead-next del-next;//对要受影响的结点的参数进行更改phead-next-prev phead;free(del);//释放掉该地址del NULL;
}
运行测试一下 查找
因为后面涉及到任意位置的操作所以这里要写一个查找方法
//查找
LN* LNFind(LN* phead, LNDataType x) {assert(phead);assert(!LNEmpty(phead));LN* pcur phead-next;while (pcur!phead) {//判断条件为!phead,遇到哨兵位说明已经遍历完if (pcur-data x) {return pcur;}pcur pcur-next;}return NULL;
}
运行测试一下 指定位置之后的插入
//指定位置之后的插入
void LNInsert(LN* pos, LNDataType x) {assert(pos);LN* node LNBuyNode(x);node-next pos-next;//先对要受影响的结点的参数进行更改node-prev pos;pos-next-prev node;//更改pos结点的后一个结点的prev参数pos-next node;//更改pos结点的next参数
}
运行测试一下 指定位置的删除
//任意位置的删除
void LNErase(LN* pos) {assert(pos);pos-next-prev pos-prev;pos-prev-next pos-next;free(pos);pos NULL;
}
运行测试一下 销毁
//销毁
void LNDestory(LN** phead) {assert(phead *phead);LN* pcur (*phead)-next;while (pcur ! *phead) {LN* next pcur-next;free(pcur);pcur next;}free(*phead);*phead pcur NULL;
}
