今天我们继续来完成链表,但是今天我们来实现双向带头循环链表,这与我们之前写的单项不带头非循环链表相对应,链表一共可以有8种形式,学会了这两种,其他6种也都游刃有余。
(7条消息) 链表与其多种接口实现1_KLZUQ的博客-CSDN博客
这是上一期的链表,大家可以参考一下。
还是和之前一样,我们使用工程一点的写法
我们先来完成链表的结构创建已经宏定义
typedef struct ListNode {
接着我们来完成链表的初始化
ListNode* ListInit()//初始化 ListNode* phead = BuyListNode(0);
因为初始化时要创建新的节点,并且我们在之后也需要一直创建新的节点,所以我们把创建新节点封装成一个函数
ListNode* BuyListNode(LTDataType x)//创建新节点 ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
有了这些,我们来完成链表的尾插
void ListPushBack(ListNode* phead, LTDataType x)//尾插 ListNode* tail = phead->prev; ListNode* newnode = BuyListNode(x);
双向带头循环链表的结构看起来很复杂,但我们实现它时却非常简单。加断言是为了防止头节点为空(比如使用链表时因为某些原因导致程序崩溃,断言可以帮助你迅速找到错误的位置),这个链表的结构非常完美,链表不为空和为空时都可以完成自己的工作,容错率非常高。
有了尾插,我们接着来实现打印,方便我们观察和调试
void ListPrint(ListNode* phead)//打印 ListNode* cur = phead->next; printf("%d ", cur->data);
我们看到,当链表为空时它仍然不会出现错误,这个结构是最优的,我在结尾会告诉大家这个链表的真正优点,接下来就不再啰嗦。
有了打印,我们来测试一下我们的代码,还是那句话,写一步测一步,不然写到后面几十个错误心态就炸了
很好,我们接着来完成头插
void ListPushFront(ListNode* phead, LTDataType x)//头插 ListNode* first = phead->next; ListNode* newnode = BuyListNode(x);
很多人在别的书上看到头插可能有顺序问题,但我们这个是不需要考虑顺序的,如果去掉first的话直接来完成才需要考虑顺序问题。那时候,我们需要先把newnode和它的后续节点连起来,然后再连接头节点和newnode
接着我们来完成头删
void ListPopFront(ListNode* phead)//头删 assert(phead->next!=phead); ListNode* first = phead->next; ListNode* second = first->next;
我们创建first和second两个指针,这样就可以不用考虑顺序问题。第二个断言可以防止链表删除头节点。
接着是尾删
void ListPopBack(ListNode* phead)//尾删 assert(phead->next != phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev;
尾删同样创建两个指针,不考虑顺序
然后是查找
ListNode* ListFind(ListNode* phead, LTDataType x)//查找 ListNode* cur = phead->next;
查找也是相当简单,这个查找我们也可以用来修改当前位置的值
非常的好用
接着我们来写任意位置插入
void ListInsert(ListNode* pos, LTDataType x)//任意位置前插入(pos前) ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x);
同样,定义一个指针可以让我们不用考虑顺序。这个配合查找使用非常方便
然后我们来写任意位置删除
void ListErase(ListNode* pos)//任意位置删除(pos位置) ListNode* prev = pos->prev; ListNode* next = pos->next;
到这里,我们的接口也基本都实现了,如果让大家在10分钟内实现这个链表和它的接口,大家可以完成吗?
这里我们就要来提高代码的复用性
我们有了任意位置的插入和删除,我们就可以修改代码
void ListPopBack(ListNode* phead)//尾删 assert(phead->next != phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev;
void ListPopFront(ListNode* phead)//头删 assert(phead->next!=phead); ListNode* first = phead->next; ListNode* second = first->next;
最后,我们来写一下清空链表
void ListDestory(ListNode* phead)//清空 ListNode* cur = phead->next; ListNode* next = cur->next;
以上就是我们完成的所有接口,大家自己试一下会发现,这个链表的结构非常完美,它的插入和删除的时间复杂度都是o(1),只有查找我们是用的是正常方法,时间复杂度为o(n)。
最后附上所有代码,希望各位有所收获
typedef struct ListNode { void ListPrint(ListNode* phead);//打印 ListNode* ListInit();//初始化 void ListDestory(ListNode* phead);//清空 void ListPushBack(ListNode* phead, LTDataType x);//尾插 void ListPushFront(ListNode* phead, LTDataType x);//头插 void ListPopBack(ListNode* phead);//尾删 void ListPopFront(ListNode* phead);//头删 ListNode* ListFind(ListNode* phead, LTDataType x);//查找 void ListInsert(ListNode* pos, LTDataType x);//任意位置前插入(pos前) void ListErase(ListNode* pos);//任意位置删除(pos位置)
ListNode* BuyListNode(LTDataType x)//创建新节点 ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); ListNode* ListInit()//初始化 ListNode* phead = BuyListNode(0); void ListDestory(ListNode* phead)//清空 ListNode* cur = phead->next; ListNode* next = cur->next; void ListPrint(ListNode* phead)//打印 ListNode* cur = phead->next; printf("%d ", cur->data); void ListPushBack(ListNode* phead, LTDataType x)//尾插 ListNode* tail = phead->prev; ListNode* newnode = BuyListNode(x); void ListPushFront(ListNode* phead, LTDataType x)//头插 ListNode* first = phead->next; ListNode* newnode = BuyListNode(x); void ListPopBack(ListNode* phead)//尾删 assert(phead->next != phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev; void ListPopFront(ListNode* phead)//头删 assert(phead->next!=phead); ListNode* first = phead->next; ListNode* second = first->next; ListNode* ListFind(ListNode* phead, LTDataType x)//查找 ListNode* cur = phead->next; void ListInsert(ListNode* pos, LTDataType x)//任意位置前插入(pos前) ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); void ListErase(ListNode* pos)//任意位置删除(pos位置) ListNode* prev = pos->prev; ListNode* next = pos->next;
ListNode* plist = ListInit(); ListNode* plist = ListInit(); ListNode* pos = ListFind(plist, 3);
如有错误,还请指正。
|