做网站与运营一般多少钱,查询网站最新域名,网站建设范文,品牌策划全案公司Hello#xff0c;好久不见#xff0c;今天我们讲链表的双向链表#xff0c;这是一个很厉害的链表#xff0c;带头双向且循环#xff0c;学了这个链表#xff0c;你会发现顺序表的头插头删不再是一个麻烦问题#xff0c;单链表的尾插尾删也变得简单起来了#xff0c;那废… Hello好久不见今天我们讲链表的双向链表这是一个很厉害的链表带头双向且循环学了这个链表你会发现顺序表的头插头删不再是一个麻烦问题单链表的尾插尾删也变得简单起来了那废话不多说让我们开始我们的学习吧 首先我们要了解它的物理和逻辑结构那他们的样子是怎样的呢首先是一个带头的那这个难道是我们的哨兵位吗又是双向且循环那让我们来画图了解它吧。 大致就是这样的一个形状那我们现在需要这样的一个结构体来实现这样的功能首先应该有一个存储数据的就是data然后就是得有两个指针一个指向前面的节点一个就是指向后面的节点那我们就叫它们一个pre指向前面一个next指向后面我们来实现一下吧。
typedef int DListType;
typedef struct DList
{struct DList* pre;struct DList* next;DListType data;}DLNode;为了方便我们写后面的时候结构体方便一点我们先定义结构体为DLNode这样更加方便使用。 现在我们要实现下面的各种接口来完成双链表 首先最重要的就是怎么初始化 初始化的话我们先要想想这个接口函数改的参数和返回值 因为是双向链表所以得有一个head的头节点这样才能链接后面的内容 初始化双链表 DLNode* DListInit();接口函数的名字 这里我们分析首先我们得返回值为什么不是void而是DLNode* 因为我们要在这里面创建一个头节点这个节点我们后面都得使用其次还有一个原因就是这样头节点就不会被销毁当然我们也可以在外面创建一个节点然后我们在传它的指针进去对结构体的内容进行修改都可以达到相同的作用废话不多说我们来实现吧
DLNode* DListInit()
{DLNode* pHead (DLNode*)malloc(sizeof(DLNode));assert(pHead);pHead-next pHead;pHead-pre pHead;
}其实很简单这里必须指针指向自己才可以如果不这样的话那我们的循环就不能实现了。 接下来就是怎么打印打印很简单我们将它这个指针传过去就行了。 打印双链表 void DListPrint(DLNode* pHead)
{assert(pHead);DLNode* cur pHead-next;while (cur ! pHead){printf(%d , cur-data);cur cur-next;}printf(\n);
}打印函数的想法就是我们找head后面的那个节点然后打印因为头节点我们不打印所以取cur开始因为是循环所以cur最后会等于pHead这样的话就是一个循环所以我们找下一个就行了然后打印后更新cur。 接下来我们要创建一个节点这样才能链接起来我们的节点。
DLNode* CreatNewNode(DListType x)DLNode* CreatNewNode(DListType x)
{DLNode* newnode (DLNode*)malloc(sizeof(DLNode));assert(newnode);newnode-data x;newnode-next NULL;newnode-pre NULL;return newnode;
}
创造节点好了接下来就是尾插一个节点进去我们前面单链表尾插首先要找到尾的位置然后再去尾插同时要先找到尾的前一个位置然后free尾这样时间复杂度就是ON所以效率不是特别高那我们现在因为head的位置里存放的就是尾的位置所以不用进行查找了。我们现在来实现一下吧 双链表尾插 void DListPushBACK(DLNode* pHead, DListType x)
{assert(pHead);DLNode* newnode CreatNewNode(x);DLNode* pre pHead-pre;pHead-pre newnode;newnode-next pHead;pre-next newnode;newnode-pre pre;
}其实尾插也很简单我们这里先用一个指针保存位置这样的话下一次插入就可以找到尾的位置而且还不用注重顺序这样大大的提升效率
有了尾插那就肯定有头插一样的办法我们来实现一下 双链表的头插 void DListPushFront(DLNode* pHead, DListType x)
{assert(pHead);DLNode* newnode CreatNewNode(x);DLNode* next pHead-next;pHead-next newnode;newnode-pre pHead;newnode-next next;next-pre newnode;
}有了头插这些那肯定还有头删和尾删 那我们也来实现一下吧 尾删 void DListPopBack(DLNode* pHead)
{assert(pHead);if (pHead-next ! pHead){DLNode* del pHead-pre;del-pre-next pHead;pHead-pre del-pre;free(del);}
}前面写的代码都需要测试一下我们先来测试三个
#includeDList.h
void test()
{DLNode* head DListInit();DListPushBack(head, 1);DListPushBack(head, 2);DListPushBack(head, 3);DListPushBack(head, 4);DListPrint(head);DListPushFront(head, 111);DListPushFront(head, 111);DListPushFront(head, 111);DListPrint(head);DListPopBack(head);DListPopBack(head);DListPopBack(head);DListPrint(head);
}
int main()
{test();return 0;
}发现我们的程序没有问题我们再来实现一下头删
void DListPopFront(DLNode* pHead)
{assert(pHead);if (pHead-next ! pHead){DLNode* del pHead-next;pHead-next del-next;del-next-pre pHead;free(del);}
}接下来就是双链表的查找有了查找我们才能和在任意位置的删除和插入连用那我们现在来实现一下吧 DLNode* DListFind(DLNode* pHead, DListType x)
{assert(pHead);DLNode* cur pHead-next;while (cur ! pHead){if (cur-data x){return cur;}cur cur-next;}return NULL;
} 随机插入 void DListInsert(DLNode* pos, DListType x)
{assrt(pos);DLNode* newnode CreatNewNode(x);DLNode* pospre pos-pre;pospre-next newnode;newnode-pre pospre;newnode-next pos;pos-pre newnode;}也不是随机插入是在pos位置之前插入我们直接传pos和x就行然后在根据之前的想法一步一步的进行插入链接就行
这里可以更新一下头插和尾插这里就不演示了 那我们在写一个删除pos位置的函数 删除pos位置 void DListPop(DLNode* pos)
{assert(pos);DLNode* pospre pos-pre;DLNode* posnext pos-next;pospre-next posnext;posnext-pre pospre;free(pos);
}还有一个destory我们开辟的空间这个遍历一遍数组 然后一个一个释放就行但是会有问题我们释放的时候必须看要机记住位置可以从尾巴开始释放用一个指针记住前面一个的位置然后释放掉尾巴然后更新前一个位置用while控制一下就行了
#includestdio.h
#includeassert.h
#includestdlib.h
typedef int DListType;
typedef struct DList
{struct DList* pre;struct DList* next;DListType data;}DLNode;DLNode* DListInit();void DListPrint(DLNode* pHead);DLNode* CreatNewNode(DListType x);void DListPushBack(DLNode* pHead, DListType x);void DListPushFront(DLNode* pHead, DListType x);void DListPopBack(DLNode* pHead);void DListPopFront(DLNode* pHead);DLNode* DListFind(DLNode* pHead, DListType x);void DListInsert(DLNode* pos, DListType x);void DListPop(DLNode* pos);#includeDList.hDLNode* DListInit()
{DLNode* pHead (DLNode*)malloc(sizeof(DLNode));pHead-next pHead;pHead-pre pHead;
}void DListPrint(DLNode* pHead)
{assert(pHead);DLNode* cur pHead-next;while (cur ! pHead){printf(%d , cur-data);cur cur-next;}printf(\n);
}DLNode* CreatNewNode(DListType x)
{DLNode* newnode (DLNode*)malloc(sizeof(DLNode));assert(newnode);newnode-data x;newnode-next NULL;newnode-pre NULL;return newnode;
}void DListPushBack(DLNode* pHead, DListType x)
{DLNode* newnode CreatNewNode(x);DLNode* pre pHead-pre;pHead-pre newnode;newnode-next pHead;pre-next newnode;newnode-pre pre;
}void DListPushFront(DLNode* pHead, DListType x)
{DLNode* newnode CreatNewNode(x);DLNode* next pHead-next;pHead-next newnode;newnode-pre pHead;newnode-next next;next-pre newnode;
}void DListPopBack(DLNode* pHead)
{assert(pHead);if (pHead-next ! pHead){DLNode* del pHead-pre;del-pre-next pHead;pHead-pre del-pre;free(del);}
}void DListPopFront(DLNode* pHead)
{assert(pHead);if (pHead-next ! pHead){DLNode* del pHead-next;pHead-next del-next;del-next-pre pHead;free(del);}
}DLNode* DListFind(DLNode* pHead, DListType x)
{assert(pHead);DLNode* cur pHead-next;while (cur ! pHead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}void DListInsert(DLNode* pos, DListType x)
{assrt(pos);DLNode* newnode CreatNewNode(x);DLNode* pospre pos-pre;pospre-next newnode;newnode-pre pospre;newnode-next pos;pos-pre newnode;}void DListPop(DLNode* pos)
{assert(pos);DLNode* pospre pos-pre;DLNode* posnext pos-next;pospre-next posnext;posnext-pre pospre;free(pos);
}谢谢大家我们下期再见
