摘要:由于太久没有复习数据结构了,导致该忘的都忘了,所以在这里记录重新学习数据结构的笔记,以备以后查看。
双链表
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
存储结构
1 | typedef struct DLNode{ |
与单链表的区别就是定义了一个指向前驱的指针。
初始化结点
1 | DLNode *create_node(ElemType data) |
尾插法创建双链表
1 | DLNode *create_link_tail(DLNode *L,ElemType data[],int n) |
查找结点某个位置的指针
1 | //查找某个位置的结点的指针 |
在某个结点后面插入结点
1 | //在某个结点后面插入结点 |
此处记得判断是否是最后一个结点插入。
删除结点
1 | //删除某个结点并返回 |
获取链表长度
1 | int link_length(DLNode *L) |
打印双链表
1 | int printf_link(DLNode *L) |
完整函数(包含测试)
1 |
|
循环链表
循环单链表和循环双链表是由对应的单链表和双链表改造而来,只需要在终点结点和头结点间建立联系即可。循环单链表终端结点的next结点指针指向头结点。循环双链表终端结点的next指针指向表头结点,头节点的prior指针指向表尾节点即可。
tips:
如果P指针沿着循环链表行走,则判断p走到尾节点的条件是p->next == head。循环链表的操作均与非循环链表类似。