当前位置： 首页 > news >正文

牡丹区住房城乡建设局网站企业培训课程安排表

news 2025/12/20 8:49:43
牡丹区住房城乡建设局网站,企业培训课程安排表,三合一网站建设多少钱,新疆网站建设多少钱目录 双链表的定义与接口函数 定义双链表 接口函数 详解接口函数的实现 创建新节点（BuyLTNode） 初始化双链表（ListInit） 双向链表打印（ListPrint） 双链表查找（ListFind） 双链…

目录

双链表的定义与接口函数

定义双链表

 接口函数

详解接口函数的实现

创建新节点（BuyLTNode）

初始化双链表（ListInit）

双向链表打印（ListPrint）

双链表查找（ListFind）

双链表销毁（ListDestory）

        1、双链表pos位置之前插入（ListInsert）

        2、双链表删除pos位置（ListEarse）

        3、双向链表尾插（ListPushBack）

        4、双向链表头插（ListPushFront）

        5、双链表头删（ListPopFront）

        6、双链表尾删（ListPopBack）

总结

完整代码

链表OJ练习巩固

前言：

为了更好地理解本节，建议先阅读： 数据结构 - c语言链表操作

实际中要实现的链表的结构非常多样，以下情况组合起来有多种链表结构：

  1.  单向、双向
  2.  带头、不带头
  3.  循环、非循环

解读： 

带头：

存在一个哨兵位的节点，该节点不存储任何有效数据，属于无效节点，但通过这个无效节点当头节点让我们在某些方面使用会有一些优势。

双向：

指的是节点中不再只有一个指针，而是有两个指针，一个指向前一个节点，另一个指向后一个节点。

循环：

尾指针不再指向NULL，而是指向头节点。 

然而，现实中实用的只有两种：分别是无头单向非循环链表；带头双向循环链表。

  • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  • 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外，这个结构虽然结构复杂，但是使用代码实现后会发现结构会带来很多优势。双向链表严格来说只需要快速的实现两个接口，insert 和 earse 头尾的插入和删除就可以搞定了！

双链表的定义与接口函数

定义双链表

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

 接口函数

void ListPrint(LTNode* phead);
//void ListInit(LTNode** pphead);
LTNode* ListInit();
LTNode* BuyLTNode(LTDataType x);
void ListPushBack(LTNode* phead, LTDataType x);
void ListPopBack(LTNode* phead);void ListPushFront(LTNode* phead, LTDataType x);
void ListPopFront(LTNode* phead);
LTNode* ListFind(LTNode* phead, LTDataType x);// 在pos之前插入
void ListInsert(LTNode* pos, LTDataType x);
//void ListInsert(int i, LTDataType x);// 删除pos位置的节点
void ListErase(LTNode* pos);
void ListDestory(LTNode* phead);

详解接口函数的实现

 创建新节点（BuyLTNode）

LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

初始化双链表（ListInit）

LTNode* ListInit()
{LTNode* phead = BuyLTNode(0);phead->next = phead;phead->prev = phead;return phead;
}

这里我们使用 BuyLTNode 函数开辟一块空间作为 "哨兵位" pHead ，最后将其进行一个初始化。最后再将 pHead 作为结果返回回去，外面就可以接收到了。这就是返回值的方法，当然这里也可以采用二级指针的方法来完成。

双向链表打印（ListPrint）

void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n\n");
}

双链表查找（ListFind）

LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

双链表销毁（ListDestory）

void ListDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;//ListErase(cur);free(cur);cur = next;}free(phead);//phead = NULL;
}

1、双链表pos位置之前插入（ListInsert）

void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);/*LTNode* newnode = BuyLTNode(x);pos->prev->next = newnode;newnode->prev = pos->prev;pos->prev = newnode;newnode->next = pos;*/LTNode* newnode = BuyLTNode(x);LTNode* posPrev = pos->prev;newnode->next = pos;pos->prev = newnode;posPrev->next = newnode;newnode->prev = posPrev;
}

非常简单，假设d2是新节点，就是让新节点的两条链接在d3上，然后把d1的两条链接新节点上

2、双链表删除pos位置（ListEarse）

void ListErase(LTNode* pos)
{assert(pos);LTNode* prev = pos->prev;LTNode* next = pos->next;free(pos);pos = NULL;prev->next = next;next->prev = prev;
}

 假设要删除d2，那么只需要直接把d1的两条链接d3上即可

3、双向链表尾插（ListPushBack）

void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

4、双向链表头插（ListPushFront）

void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead->next, x);
}

5、双链表头删（ListPopFront）

void ListPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);ListErase(phead->next);
}

6、双链表尾删（ListPopBack）

void ListPopBack(LTNode* phead)
{assert(phead);// 链表为空assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tail = NULL;tailPrev->next = phead;phead->prev = tailPrev;}

总结：

用ListInsert和ListEarse的复用优化后：

void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead, x);
}void ListPopBack(LTNode* phead)
{assert(phead);// 链表为空assert(phead->next != phead);ListErase(phead->prev);
}void ListPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);ListErase(phead->next);
}void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead->next, x);
}

所以，双向链表严格来说只需要快速地实现 insert 和 earse 这两个接口就可以搞定了。如果以后让你快速实现一个双向链表，你把 "pos位置之前插入" 和 "删除pos位置" 这两个接口写好，头尾的插入和删除直接复用就可以搞定了。

完整代码

List.h

#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;void ListPrint(LTNode* phead);
//void ListInit(LTNode** pphead);
LTNode* ListInit();
LTNode* BuyLTNode(LTDataType x);
void ListPushBack(LTNode* phead, LTDataType x);
void ListPopBack(LTNode* phead);void ListPushFront(LTNode* phead, LTDataType x);
void ListPopFront(LTNode* phead);
LTNode* ListFind(LTNode* phead, LTDataType x);// 在pos之前插入
void ListInsert(LTNode* pos, LTDataType x);
//void ListInsert(int i, LTDataType x);// 删除pos位置的节点
void ListErase(LTNode* pos);
void ListDestory(LTNode* phead);

List.c

#include"List.h"LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n\n");
}//void ListInit(LTNode** pphead)
//{
//	assert(pphead);
//	*pphead = BuyLTNode(0);
//	(*pphead)->next = *pphead;
//	(*pphead)->prev = *pphead;
//}LTNode* ListInit()
{LTNode* phead = BuyLTNode(0);phead->next = phead;phead->prev = phead;return phead;
}void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);//LTNode* tail = phead->prev;//LTNode* newnode = BuyLTNode(x);//tail->next = newnode;//newnode->prev = tail;//newnode->next = phead;//phead->prev = newnode;ListInsert(phead, x);
}void ListPopBack(LTNode* phead)
{assert(phead);// 链表为空assert(phead->next != phead);/*	LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tail = NULL;tailPrev->next = phead;phead->prev = tailPrev;*/ListErase(phead->prev);
}void ListPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);ListErase(phead->next);
}void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead->next, x);
}LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);/*LTNode* newnode = BuyLTNode(x);pos->prev->next = newnode;newnode->prev = pos->prev;pos->prev = newnode;newnode->next = pos;*/LTNode* newnode = BuyLTNode(x);LTNode* posPrev = pos->prev;newnode->next = pos;pos->prev = newnode;posPrev->next = newnode;newnode->prev = posPrev;
}// 驼峰法
// 函数和类型所有单词首字母大写
// 变量：第一个单词小写后续单词首字母大写
void ListErase(LTNode* pos)
{assert(pos);LTNode* prev = pos->prev;LTNode* next = pos->next;free(pos);pos = NULL;prev->next = next;next->prev = prev;
}void ListDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;//ListErase(cur);free(cur);cur = next;}free(phead);//phead = NULL;
}------------------------------------------------------------------------------#include "List.h"ListNode* BuyListNode(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));node->data = x;node->next = NULL;node->prev = NULL;return node;
}ListNode* ListCreate()
{ListNode* head = (ListNode*)malloc(sizeof(ListNode));head->next = head;head->prev = head;return head;
}void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){printf("%d->", cur->data);cur = cur->next;}printf("\n");
}void ListDestroy(ListNode* pHead)
{ListNode* cur = pHead->next;while (cur != pHead){ListNode* next = cur->next;free(cur);cur = next;}free(pHead);
}void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);//ListNode* newnode = BuyListNode(x);phead         tail   newnode//ListNode* tail = pHead->prev;//tail->next = newnode;//newnode->prev = tail;//newnode->next = pHead;//pHead->prev = newnode;ListInsert(pHead, x);
}void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);//ListNode* newnode = BuyListNode(x);//ListNode* first = pHead->next;//pHead->next = newnode;//newnode->prev = pHead;//newnode->next = first;//first->prev = newnode;/*ListNode* newNode = BuyListNode(x);newNode->next = pHead->next;pHead->next->prev = newNode;pHead->next = newNode;newNode->prev = pHead;*/ListInsert(pHead->next, x);
}void ListPopBack(ListNode* pHead)
{assert(pHead);//ListNode* tail = pHead->prev;//ListNode* tailPrev = tail->prev;pHead     tailPrev tail//tailPrev->next = pHead;//pHead->prev = tailPrev;//free(tail);/*ListNode* tail = pHead->prev;pHead->prev = tail->prev;tail->prev->next = pHead;free(tail);*/ListErase(pHead->prev);
}void ListPopFront(ListNode* pHead)
{//...ListErase(pHead->next);
}// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* prev = pos->prev;ListNode* newnode = BuyListNode(x);// prev newnode posprev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);
}

链表OJ练习巩固

138. 复制带随机指针的链表 - 力扣（LeetCode）

 

解题思路：
此题可以分三步进行：
1.拷贝链表的每一个节点，拷贝的节点先链接到被拷贝节点的后面
2.复制随机指针的链接：拷贝节点的随机指针指向被拷贝节点随机指针的下一个位置
3.拆解链表，把拷贝的链表从原链表中拆解出来 

class Solution {
public:Node* copyRandomList(Node* head) {// 1.拷贝链表，并插入到原节点的后面，如图1Node* cur = head;while(cur){Node* next = cur->next;Node* copy = (Node*)malloc(sizeof(Node));copy->val = cur->val;// 插入cur->next = copy;copy->next = next;// 迭代往下走cur = next;}// 2.置拷贝节点的random，如图2cur = head;while(cur){Node* copy = cur->next;if(cur->random != NULL)copy->random = cur->random->next;elsecopy->random = NULL;cur = copy->next;}// 3.解拷贝节点，链接拷贝节点，如图3Node* copyHead = NULL, *copyTail = NULL;cur = head;while(cur){Node* copy = cur->next;Node* next = copy->next;// copy解下来尾插if(copyTail == NULL){copyHead = copyTail = copy;}else{   copyTail->next = copy;copyTail = copy;}cur->next = next;cur = next;}return copyHead;}
};

图1： 

 图2：

图3： 

链表知识点题库 - 力扣（LeetCode）

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网 (nowcoder.com)

 

http://www.wangmingla.cn/news/153514.html

相关文章：

  • 昌平区网站建设汕头seo代理
  • 现在最常用网站开发工具广告竞价排名
  • 品牌 网站建设网络销售怎么样
  • 专业格泰建站百度官方电话号码
  • 自己做的网站 网站备案流程百度小说app下载
  • 商标注册证曲靖seo建站
  • 省心的免费建站服务热线网站分析案例
  • 建设门户网站都需要什么推广引流平台
  • 网站死链怎么解决长沙网络优化产品
  • 企业建网站的目的软文广告成功案例
  • 网站建设制作设计seo优化珠海在线生成网页网站
  • 电子商务网站建设评价广东又出现新病毒
  • 网站测试页面怎么做的百度 个人中心首页
  • 网站建设一般多少钱要如何选择seo 优化技术难度大吗
  • 长沙专业网站制作网络运营和网络营销的区别
  • 公司商标注册怎么弄seo优化视频教程
  • 做地方门户网站的排名长尾关键词什么意思
  • 网站开发 q3687474小区推广最有效的方式
  • 网站建设优化合同中国最新领导班子
  • 龙岩城乡建设局网站山东泰安网络推广
  • 个人域名可以备案企业网站吗企业网站推广效果指标分析
  • 凤山网站seo保定网站建设方案优化
  • 外包做网站价格2023年7月疫情爆发
  • 益阳网络营销广州seo关键词优化外包
  • 山东学生做自我评价的网站百度云app
  • 如何用社交网站开发客户关键词排名关键词快速排名
  • 网站怎样做https爱客crm
  • 建湖做网站找哪家好网络销售平台上市公司有哪些
  • 济南网站建站模板营销推广方案案例
  • 有做翻页相册的网站吗个人如何注册网站