scratch网站开发,wordpress dz论坛,网站建设数据表设计 性别,新闻资讯专业翻译公司目录
1.双向链表的结构
2.双向链表的实现
2.1初始化
以参数的形式初始化链表#xff1a;
以返回值的形式初始化链表#xff1a;
2.2尾插
2.3打印
2.4头插
2.5尾删
2.6头删
2.7查找
2.8在指定位置之后插入数据编辑
2.9删除pos节点
2.10销毁
3.整理代码
3.1…目录
1.双向链表的结构
2.双向链表的实现
2.1初始化
以参数的形式初始化链表
以返回值的形式初始化链表
2.2尾插
2.3打印
2.4头插
2.5尾删
2.6头删
2.7查找
2.8在指定位置之后插入数据编辑
2.9删除pos节点
2.10销毁
3.整理代码
3.1 List.h
3.2 List.c
3.3 Test.c 1.双向链表的结构 带头链表里的头节点实际为“哨兵位”哨兵位节点不存储任何有效元素只是站在那里“放哨”。 “哨兵位”存在的意义 遍历循环链表避免死循环。 2.双向链表的实现 不带头节点的单链表为空链表的判条件headNULL因为head本来指向链表的第一个节点如果head为NULL说明链表没有节点为空链表。 而带头结点的单链表为空链表的判定条件head-nextNULL; 双向链表为空链表的判定条件链表中只剩下一个头结点。 2.1初始化
申请节点函数
LTNode* LTBuyNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){perror(malloc fail!);exit(1);}node-data x;node-next node-prev node;//自己指向自己return node;
}
以参数的形式初始化链表 开始的时候创建一个空链表LTNode* plist NULL;我们要对空链表进行初始化保证让链表只有一个头结点哨兵位为我们后续插入操作做准备。由于要改变plist的指向所以传二级指针。 void LTInit(LTNode** pphead)
{//给双向链表创建一个哨兵位*pphead LTBuyNode(-1);//哨兵位里面不需要有值为了调用申请节点函数传一个值-1好了
}
以返回值的形式初始化链表 初始化可以不传递二级指针以返回值的形式返回哨兵位调用完LTInit函数后plist指针接收其返回值LTNode* plist LTInit(); LTNode* LTInit()
{LTNode* phead LTBuyNode(-1);return phead;
}
2.2尾插 void LTPushBack(LTNode* phead, LTDataType x)//不改变哨兵位的地址传一级指针即可
{assert(phead);LTNode* newnode LTBuyNode(x);//phead phead-prev newnodenewnode-prev phead-prev;newnode-next phead;phead-prev-next newnode;phead-prev newnode;//注意这两行代码不能颠倒位置
}
2.3打印
void LTPrint(LTNode* phead)
{LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}
2.4头插 void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead newnode phead-nextnewnode-next phead-next;newnode-prev phead;newnode-next-prev newnode;phead-next newnode;//注意这两行代码不能颠倒位置
}
2.5尾删 void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空(只有一个哨兵位)assert(phead phead-next!phead);LTNode* del phead-prev;//phead del-prev deldel-prev-next phead;phead-prev del-prev;//删除del节点free(del);del NULL;
}2.6头删 void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);LTNode* del phead-next;//phead del del-nextphead-next del-next;del-next-prev phead;//删除del节点free(del);del NULL;
}
2.7查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}//没有找到return NULL;
}
2.8在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//pos newnode pos-nextnewnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}
2.9删除pos节点 为了保持接口的一致性这里传的是一级指针对形参的修改不影响实参pos置为空不影响find , find此时是野指针所以调用完 LTERase 函数后要手动将find置为空findNULL; void LTErase(LTNode* pos)
{assert(pos);// pos-prev pos pos-nextpos-next-prev pos-prev;pos-prev-next pos-next;//删除pos节点free(pos);pos NULL;
}2.10销毁 同样为了保持接口的一致性这里也传一级指针对形参的修改不影响实参phead置为空不影响实参plist所以调用完 LTDesTroy 函数后要手动将plist置为空plistNULL; void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead NULL;
}
3.整理代码
3.1 List.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h//定义双向链表节点的结构
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化
//void LTInit(LTNode** pphead);//以二级指针形式初始化
LTNode* LTInit();//以返回值形式初始化
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
//销毁
void LTDesTroy(LTNode* phead);
3.2 List.c
#includeList.h
//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){perror(malloc fail!);exit(1);}node-data x;node-next node-prev node;//自己指向自己return node;
}//初始化
//以返回值形式初始化
LTNode* LTInit()
{LTNode* phead LTBuyNode(-1);return phead;
}//以二级指针形式初始化
//void LTInit(LTNode** pphead)
//{
// *pphead LTBuyNode(-1);
//}//打印
void LTPrint(LTNode* phead)
{LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)//不改变哨兵位的地址传一级指针即可
{assert(phead);LTNode* newnode LTBuyNode(x);//phead phead-prev newnodenewnode-prev phead-prev;newnode-next phead;phead-prev-next newnode;phead-prev newnode;//注意这两行代码不能颠倒位置
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead newnode phead-nextnewnode-next phead-next;newnode-prev phead;newnode-next-prev newnode;phead-next newnode;//注意这两行代码不能颠倒位置
}//尾删
void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空(只有一个哨兵位)assert(phead phead-next!phead);LTNode* del phead-prev;//phead del-prev deldel-prev-next phead;phead-prev del-prev;//删除del节点free(del);del NULL;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);LTNode* del phead-next;//phead del del-nextphead-next del-next;del-next-prev phead;//删除del节点free(del);del NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}//没有找到return NULL;
}//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//pos newnode pos-nextnewnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;}//删除pos节点
void LTErase(LTNode* pos)
{ assert(pos);// pos-prev pos pos-nextpos-next-prev pos-prev;pos-prev-next pos-next;//删除pos节点free(pos);pos NULL;
}//销毁
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead NULL;
}
3.3 Test.c
#includeList.h
void ListTest01()
{ //传二级指针形式初始化/*LTNode* plist NULL;LTInit(plist); *///以返回值形式初始化LTNode* plist LTInit();//尾插LTPushBack(plist, 1);LTPushBack(plist, 2); LTPushBack(plist, 3);LTPrint(plist);//打印//头插LTPushFront(plist,4); LTPushFront(plist,5); LTPrint(plist);//打印//尾删LTPopBack(plist);LTPrint(plist);//打印//头删LTPopFront(plist);LTPrint(plist);//打印//查找LTNode* find LTFind(plist,4);//删除pos节点LTErase(find);LTPrint(plist);//打印find NULL;//手动置空//销毁 LTDesTroy(plist);plist NULL;//手动置空
}
int main()
{ListTest01();return 0;
}
