网站制作推荐,创网站需要什么,中文网站模板,广东建泰建设有限公司网站铁汁们大家好#xff0c;我们上一篇博客学习了单链表#xff0c;这节课让我们继续往深学习#xff0c;学习一下双线链表#xff0c;话不多说#xff0c;我们开始吧#xff01; 目录
1.双向链表
2.顺序表和链表的优缺点
3.双向链表的实现 1.双向链表 1.我们要实现的双线…铁汁们大家好我们上一篇博客学习了单链表这节课让我们继续往深学习学习一下双线链表话不多说我们开始吧 目录
1.双向链表
2.顺序表和链表的优缺点
3.双向链表的实现 1.双向链表 1.我们要实现的双线链表是带头双向循环链表它的结构最复杂一般用在单独的存储数据。我们实际中使用的链表数据结构都是带头双向循环链表。 2.它虽然结构复杂但是在我们用代码实现过程中它比单链表简单。 3.相信很多铁汁不清楚双向链表的结构是什么如下图 2.顺序表和链表的优缺点
我们在这里总结一下这两种线性表方便之后的学习。 顺序表 优点空间连续支持随机访问 缺点中间或前面部分的插入和删除时间复杂度是O(n) 增容很不方便代价较大。 链表 优点任意位置的插入删除时间复杂度为O1 没有增容销耗按需申请节点空间不用了直接释放。 缺点以节点为单位存储不支持随机访问 3.双向链表的实现 经过上面的铺垫我们来实现一个带头双向循环链表 List.h文件
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int ADataType;
typedef struct ListNode
{ADataType data;struct ListNode* prev;//双线链表前驱指针struct ListNode* next;//后继指针
}LN;//双向链表初始化
LN* ListInit();
//为节点开辟空间
LN* BuyListCapacity(ADataType x);
//链表的销毁
void ListDestory(LN* phead);
//头插
void ListPushFront(LN* phead, ADataType x);
//尾插
void ListPushBack(LN* phead, ADataType x);
//打印
void ListPrint(LN* phead);
//头删
void ListPopFront(LN* phead);
//尾删
void ListPopBack(LN* phead);
//查找链表中的数据
LN* ListSearch(LN* phead, ADataType x);
//修改找到的数据
void ListModify( LN* pos, ADataType y);
//在这个位置后插入数据
void ListInsert(LN* pos, ADataType x);
//删除这个位置之后的数据
void ListErase(LN* pos);
//判断链表是否为空
bool ListEmpty(LN* phead);
List.c文件
#includeList.h//为节点开辟空间
LN* BuyListCapacity(ADataType x)
{LN* newnode (LN*)malloc(sizeof(LN));if (newnode NULL){perror(malloc is false!\n);exit(-1);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}//双向链表初始化
LN* ListInit()
{//开辟空间LN* phead BuyListCapacity(0);//让头节点的前驱和后继都指向自己是一个循环phead-next phead;phead-prev phead;return phead;
}//链表的销毁
void ListDestory(LN* phead)
{assert(phead);LN* tail phead-next;while (tail ! phead)//链表的头尾相连当尾等于头时说明链表空了{LN* next tail-next;free(tail);tail next;}free(phead);phead NULL;
}
//头插
void ListPushFront(LN* phead, ADataType x)
{assert(phead);LN* newnode BuyListCapacity(x);//若这里不使用新的变量来存储原来第一个节点的值就先链接后在链接前newnode-next phead-next;phead-next-prev newnode;phead-next newnode;newnode-prev phead;
}
//尾插
void ListPushBack(LN* phead, ADataType x)
{assert(phead);LN* newnode BuyListCapacity(x);//找到尾进行插入节点LN* tail phead-prev;tail-next newnode;newnode-prev tail;phead-prev newnode;newnode-next phead;
}
//打印
void ListPrint(LN* phead)
{assert(phead);LN* tail phead-next;while (tail ! phead){printf( %d , tail-data);tail tail-next;}printf(\n);
}
//头删
void ListPopFront(LN* phead)
{assert(phead);//判断链表是否为空为空则删不了if (phead-next phead){printf(List is NULL!\n);return;}//先记录下后一个节点LN* first phead-next;LN* second first-next;phead-next second;second-prev phead;free(first);first NULL;
}
//尾删
void ListPopBack(LN* phead)
{assert(phead);//判断链表是否为空if (phead-prev phead){printf(List is NULL!\n);return;}LN* tail phead-prev;LN* prev tail-prev;prev-next phead;phead-prev prev;free(tail);tail NULL;
}
//查找链表中的数据
LN* ListSearch(LN* phead, ADataType x)
{assert(phead);LN* cur phead-next;while (cur-data ! x){cur cur-next;}if (cur-data x){return cur;}return NULL;
}
//修改找到的数据
void ListModify( LN* pos, ADataType y)
{assert(pos);pos-data y;
}
//在这个位置后插入数据
void ListInsert(LN* pos, ADataType x)
{assert(pos);LN* newnode BuyListCapacity(x);LN* next pos-next;pos-next newnode;newnode-prev pos;newnode-next next;next-prev newnode;
}
//删除这个位置之后的数据
void ListErase(LN* pos)
{assert(pos);LN* cur pos-next;LN* next cur-next;pos-next next;next-prev pos;free(cur);cur NULL;
}
//判断链表是否为空
bool ListEmpty(LN* phead)
{assert(phead);if (phead-prev phead || phead-next phead){return true;}return false;
}Test.c文件
#includeList.h
//带头双向循环链表的实现void Test1()
{LN* head ListInit();ListPushFront(head, 33);ListPushFront(head, 22);ListPushFront(head, 11);ListPushBack(head, 4);ListPushBack(head, 5);ListPushBack(head, 6);ListPushBack(head, 7);ListPushBack(head, 8);ListPushBack(head, 9);ListPushBack(head, 10);printf(ListNode: );ListPrint(head);ListPopFront(head);ListPopBack(head);printf(ListNode: );ListPrint(head);LN* pos ListSearch(head, 7);if (pos NULL){printf(Not Find!\n);}else{printf(the number is %d\n, pos-data);ListModify(pos, 77);printf(ListNode: );ListPrint(head);ListInsert(pos, 13);ListInsert(pos, 14);ListInsert(pos, 15);printf(ListNode: );ListPrint(head);ListErase(pos);printf(ListNode: );ListPrint(head);}if (ListEmpty(head)){printf(List is NULL!\n);}else{printf(List is Notnull!\n);}ListDestory(head);printf(List is disory!\n);
}int main()
{Test1();return 0;
} 结果结果就是这样的大家可以自己尝试一下 这就是双向链表的实现大家还是要自己敲一遍代码帮助自己更好的掌握知识点。
谢谢铁汁们的支持咱们下期再见
