无人机公司网站建设,岳阳棋牌软件定制开发公司,营销策略分析包括哪些内容,网站开发者工具的网络选项文章目录 Ⅰ 概念及结构Ⅱ 基本操作实现1. 结点的定义2. 创建头节点3. 创建新结点4. 双向链表销毁5. 双向链表打印6. 双向链表尾插7. 双向链表尾删8. 双向链表头插9. 双向链表头删10. 双向链表查找11. 在指定 pos 位置前插入新结点12. 删除指定 pos 位置的结点 Ⅲ 十分钟手搓链… 文章目录 Ⅰ 概念及结构Ⅱ 基本操作实现1. 结点的定义2. 创建头节点3. 创建新结点4. 双向链表销毁5. 双向链表打印6. 双向链表尾插7. 双向链表尾删8. 双向链表头插9. 双向链表头删10. 双向链表查找11. 在指定 pos 位置前插入新结点12. 删除指定 pos 位置的结点 Ⅲ 十分钟手搓链表 Ⅰ 概念及结构
双向链表的每一个结点中不仅仅只有指向后继结点的 next 指针还有指向其前趋结点的 prev 指针。双向链表的头节点的 prev 指针域指向链表的尾结点双向链表的尾结点的 next 域指向链表的头结点因此在双向链表中不存在指向 NULL 的指针。在带头结点的双向链表中头节点不存储有效数据。因此即使链表为空双向链表中还要有一个头节点头结点的前趋和后继指针都指向自己。 Ⅱ 基本操作实现
1. 结点的定义
双向循环链表的结点结构应该包含三部分存储有效数据的数据域、存储前趋结点的前趋指针域、存储后继结点的后继指针域。
typedef int LTDataType; //数据域的数据类型typedef struct ListNode //双向链表结点
{LTDataType data; //存储有效数据struct ListNode* prev; //存储前趋结点struct ListNode* next; //存储后继结点
}ListNode;2. 创建头节点
只有一个头结点时链表是空的。头结点的前趋和后继都指针头节点本身。 代码实现
// 创建返回链表的头结点.
ListNode* ListCreate()
{ListNode* head (ListNode*)malloc(sizeof(ListNode));if (NULL head){perror(malloc);exit(-1);}head-prev head; //头结点的前趋指针指向自己head-next head; //头结点的后继指针指向自己return head; //返回创建好的头结点
}3. 创建新结点
实现方法
创建除了头结点之外的新结点这种结点存储有效数据。在创建新结点时前趋和后继指针域都不指针任何结点暂时都为 NULL。 代码实现
// 创建一个新结点
ListNode* BuySListNode(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (NULL newnode){perror(malloc);exit(-1);}newnode-data x; //新结点数据域存储传来的数据newnode-next NULL; //新结点前趋指针暂时指向 NULLnewnode-prev NULL; //新结点后继指针暂时指向 NULLreturn newnode; //返回创建好的新结点
}4. 双向链表销毁
实现方法
先定义一个 cur 指针指向头结点的后继结点删除链表时有两种情况。
链表为空此时头节点的后继结点就是头结点本身直接释放头结点即可。链表非空使用一个指针 next 指向 cur 的下一个结点然后删除 cur 指向的结点再将 cur 指向 cur 的下一个结点直到删的只剩头结点为止。 代码实现
// 双向链表销毁
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next; //指向头结点的下一个结点while (cur ! pHead) {ListNode* next cur-next; //存储当前结点的下一个结点的地址free(cur); //释放当前结点cur next; //让 cur 指向 cur 的下一个结点}free(pHead); //不管链表开始是不是为空最后都会释放头结点pHead NULL;
}5. 双向链表打印
实现方法
定义一个 cur 指针指向头节点的下一个结点 (head-next)输出 cur 指向的结点的数据域的内容然后让 cur 指向下一个结点。只有在 cur 指针指向头结点的时候打印才会结束。如果链表本身为空则 cur 一开始就会指向头结点自然什么都不会打印。
代码实现
// 双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead); //传过来的不是个空指针ListNode* cur pHead-next; //指向头结点的下一个结点首结点printf(头结点-);while (cur ! pHead) //不指向头结点时说明链表中还有结点未遍历到{printf(%d-, cur-data); //输出结点数据域的内容cur cur-next; //指向当前结点的下一个结点}printf(\n);
}6. 双向链表尾插
实现方法 代码实现
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead); //传过来的不是个空指针ListNode* newnode BuySListNode(x); //先创建要插入的新结点ListNode* tail pHead-prev; //找到双向链表的尾结点tail-next newnode; //尾结点的后继指针指向新结点newnode-prev tail; //新结点的前趋指针指向尾结点newnode-next pHead; //新结点的后继结点指向头结点pHead-prev newnode; //头结点的前趋指针指向新结点
}7. 双向链表尾删
实现方法 代码实现
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead-next ! pHead-prev); //不是空链表ListNode* tail pHead-prev; //找到链表的尾结点ListNode* tail_prev tail-prev; //找到尾结点的前一个结点pHead-prev tail_prev; //让头结点的前趋指针指向尾结点的前一个结点tail_prev-next pHead; //让尾结点的前一个结点的后继指针指向头结点free(tail); //删除尾结点tail NULL;
}8. 双向链表头插
实现方法
定义一个 first 指针指向链表的首结点之后就随便插入新结点了。因为已经用 first 指针保存了首结点的地址所以不用担心会因为插入顺序导致出现 BUG。 代码实现
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode BuySListNode(x); //创建新结点ListNode* first pHead-next; //保存首结点地址pHead-next newnode; //头结点后继指向新结点newnode-prev pHead; //新结点前趋指向头结点newnode-next first; //新结点后继指向首结点first-prev newnode; //首结点前趋指向新结点
}9. 双向链表头删
实现方法
定义一个 first 指针指向首结点再定义一个 second 指针指向第二个结点。让头结点后继指向第二个结点让第二个结点前趋指向头结点。最后即可删除 first 指向的首结点。 代码实现
// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead-next ! pHead-prev); //链表不为空ListNode* first pHead-next; //指向首结点ListNode* second first-next; //指向第二个结点pHead-next second; //头结点的后继指针指向第二个结点second-prev pHead; //第二个结点的前趋指针指向头结点free(first); //释放首结点first NULL;
}10. 双向链表查找
使用一个 cur 指针遍历链表返回第一个出现要查找的数据的结点的地址。
代码实现
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur pHead-next; //链表不为空时指向首结点链表为空时最后直接返回 NULLwhile (cur ! pHead) //链表还没彻底遍历一遍时继续指向循环体内容{if (cur-data x) //结点数据域等于要查找的数{return cur; //返回出现要查找的数据的结点地址}cur cur-next;}return NULL;
}11. 在指定 pos 位置前插入新结点
获取 pos 位置
利用双向链表查找找到要插入的 pos 位置。
实现方法
定义一个 posprev 指针保存 pos 结点的前一个结点之后可按照任意顺序插入新结点 代码实现
// 双向链表在 pos 的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos); //传过来的不是空指针ListNode* newnode BuySListNode(x); //创建新结点ListNode* posprev pos-prev; //保存 pos 的前一个结点posprev-next newnode; //前一个结点的 next 域指向新结点newnode-prev posprev; //新结点的 prev 域指向前一个结点newnode-next pos; //新结点的 next 域指向 pos 结点pos-prev newnode; //pos 的 prev 域指向新结点
}功能特点
如果 pos 是头结点的话那么 pos 的前一个结点就是链表的尾结点执行该函数就会变成对链表执行尾插。 如果 pos 是首结点的话执行该函数功能就相当于直接对链表执行头插。 12. 删除指定 pos 位置的结点
获取 pos 位置
利用双向链表查找找到要删除的 pos 位置。
实现方法
定义一个 posprev 指针指向 pos 位置的前一个结点定义一个 posnext 指针指向 pos 位置的后一个结点。将 posprev 结点的后继指向 posnext将 posnext 结点的前趋指向 posprev最后再删除 pos 结点即可。 代码实现
// 双向链表删除 pos 位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* posprev pos-prev; //保存 pos 位置结点的前趋结点ListNode* posnext pos-next; //保存 pos 位置结点的后继结点posprev-next posnext; //pos 前一个结点的后继指向 pos 的后一个结点posnext-prev posprev; //pos 后一个结点的前趋指向 pos 的前一个结点free(pos);pos NULL;
}功能特点
如果 pos 是尾结点该函数执行的功能就是尾删操作。如果 pos 是首结点该函数执行的功能就是头删操作。
Ⅲ 十分钟手搓链表
根据在指定 pos 位置前插入新结点和删除指定 pos 位置的结点这两个函数的功能特点可以直接对进行函数的头尾插和头尾删功能。
// 双向链表在 pos 的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);// 双向链表删除 pos 位置的节点
void ListErase(ListNode* pos);1. 指向头尾插功能
头插直接将 pos 定为首结点即可
ListInsert(pHead-next, xxx); //首结点为 pos执行的是头插尾插直接将 pos 定为头结点即可
ListInsert(pHead, xxx); //头结点为 pos执行的是尾插2. 执行头尾删功能
头删直接将 pos 定为首结点即可
ListErase(pHead-next) //首结点为 pos执行的是头删尾删直接将 pos 定位尾结点即可
ListErase(pHead-prev) //尾结点为 pos执行的是尾删
