上海自助建站 上海网站建设,网站打开是目录结构图,宜兴做网站哪家好,济南单位网站建设双向链表实质上是在单向链表的基础上加上了一个指针指向后面地址
单向链表请参考http://t.csdn.cn/3Gxk9
物理结构 首先我们看一下两种链表的物理结构 我们可以看到#xff1a;双向在单向基础上加入了一个指向上一个地址的指针#xff0c;如此操作我们便可以向数组一样操作…双向链表实质上是在单向链表的基础上加上了一个指针指向后面地址
单向链表请参考http://t.csdn.cn/3Gxk9
物理结构 首先我们看一下两种链表的物理结构 我们可以看到双向在单向基础上加入了一个指向上一个地址的指针如此操作我们便可以向数组一样操作了而且尾插也更加方便复杂度从原来的O(n)变为O(1)并且查找也可以运用二分查找。
一些基础操作
头插 头删 尾插 尾删 接下来我们来进行代码实现
头文件以及要实现的函数声明
#pragma once
#includestdio.h
#includestdlib.h
#includestring.h
typedef int LTDataType;
typedef struct Slist
{LTDataType val;struct Slist* next;struct Slist* random;
}ListNode;// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
// 扩容
ListNode* my_malloc(LTDataType x);
函数实现
#include dslist.hListNode* my_malloc(LTDataType x)//由于后续要频繁使用到扩容所以我们直接创一个扩容函数
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));newnode-val x;newnode-random NULL;newnode-next NULL;return newnode;
}ListNode* ListCreate() //创建一个双向链表
{ListNode* head (ListNode * )malloc(sizeof(ListNode));head-val -1; head-next NULL;head-random NULL;return head;
}void ListDestory(ListNode* pHead) //销毁这个双线链表
{while (pHead)//将每个节点都free掉{ListNode* mid pHead;pHead pHead-next;mid-next NULL;free(mid);}
}void ListPrint(ListNode* pHead) //打印双向链表
{ListNode* mid pHead;while (mid) //循环一个一个打印{printf(%d-, mid-val);mid mid-next;}printf(NULL);
}void ListPushBack(ListNode* pHead, LTDataType x) //尾插
{ListNode* newnode my_malloc(x);if (pHead-next NULL) //判断链表是否为空如果为空则只需要插入一个。{newnode-random pHead; //由于循环链表需要将头节点的random指向插入元素 newnode-next NULL;pHead-next newnode;pHead-random newnode;}else //如果不为空则正常尾插{ListNode* mid pHead-random; //由于双向 头节点的random指针直接指向尾部所以不需要循环找尾mid-next newnode;newnode-random mid;pHead-random newnode;}
}void ListPopBack(ListNode* pHead) //尾删
{if (pHead-next NULL) //判断是否为空{return;}else{ListNode* mid pHead-random; //正常尾删pHead-random mid-random;mid-random-next NULL;free(mid);}
}void ListPushFront(ListNode* pHead, LTDataType x) //头插
{if (pHead-next NULL) //如果为空 则相当于尾插 调用尾插函数即可{ListPushBack(pHead, x);}else //不为空正常头插{ListNode* nownode my_malloc(x); nownode-next pHead-next; //将nownode 的next指向 phead的nextnownode-random pHead; //nownode的random指向 pheadpHead-next nownode; //phead的next指向nownodenownode-next-random nownode;}
}void ListPopFront(ListNode* pHead) //头删
{if (pHead-next NULL){return;}else{if (pHead-next pHead-random){ListPopBack(pHead);}else{ListNode* mid pHead-next;pHead-next mid-next;mid-next-random pHead;free(mid);}}
}ListNode* ListFind(ListNode* pHead, LTDataType x) //寻找元素
{ListNode* left pHead-next;ListNode* right pHead-random;while (left right) //二分查找{if (left-val x){return left;}if (right-val x){return right;}left left-next;right right-random;}return NULL;
}void ListInsert(ListNode* pos, LTDataType x)
{ListNode* newnode my_malloc(x);ListNode* mid pos-random;mid-next newnode;pos-random newnode;newnode-next pos;
}void ListErase(ListNode* pos)
{ListNode* next pos-next;ListNode* last pos-random;next-random last;last-next next;free(pos);
}有什么疑惑欢迎大家留言。
