天津企商网站建设公司,wordpress房产主题汉化版,闲鱼网站建设费用,百度关键词排名手机目录一.链表的分类二.与单链表相比三.实现增删查改1.双向循环链表结构的创建2.创建新节点3.初始化链表4.头插和尾插5.判断链表是否为空6.头删和尾删7.打印函数8.查找函数9.删除pos位置节点10.在pos前位置插入数据11.优化升级一.链表的分类
链表可有根据单向双向、有无哨兵位、…
目录一.链表的分类二.与单链表相比三.实现增删查改1.双向循环链表结构的创建2.创建新节点3.初始化链表4.头插和尾插5.判断链表是否为空6.头删和尾删7.打印函数8.查找函数9.删除pos位置节点10.在pos前位置插入数据11.优化升级一.链表的分类
链表可有根据单向双向、有无哨兵位、是否循环分为八种类型只要我们学习最简单的无头单向非循环链表以及最复杂的双向循环链表其他的类型也就可以很好地解决了。
二.与单链表相比
与单链表相比较单链表结构简单一般不会单独用来存储数据一般作为其他数据结构的子结构来使用。而双向循环链表结构复杂但功能丰富使用便捷。
三.实现增删查改
1.双向循环链表结构的创建
双向链表与之前我们剖析的单链表不同单链表只能通过next指针向后访问导致单链表的局限性大而双向链表不仅可以向后访问还可以向前访问。所以在创建双向链表时就需要多一个指针:
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;
2.创建新节点
在初始化和后续进行插入操作时我们都需要创建出一个新节点进行使用所以我们编写分装创建新节点的函数:
LTNode* CreateList(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(newnode malloc);return NULL;}newnode-next NULL;newnode-data x;newnode-prev NULL;return newnode;
}3.初始化链表
因为是双向循环的链表所以哨兵位的头节点的next和prev指针都指向自己:
LTNode* LTInit()
{LTNode* phead CreateList(-1);phead-next phead;phead-prev phead;return phead;}4.头插和尾插
在双向循环的结构便利下相较于单链表找尾的操作会非常简单只需要访问哨兵位的上一个节点即可。
void PushFront(LTNode* head, LTDataType x)
{assert(head);LTNode* newnode CreateList(x);LTNode* tailhead-next;newnode-next head-next;newnode-prev head;tail-prev newnode;head-next newnode;}
void PushBack(LTNode* head, LTDataType x)
{assert(head);LTNode* newnode CreateList(x);LTNode* tail head-prev;tail-next newnode;newnode-prev tail;newnode-next head;head-prev newnode;
}5.判断链表是否为空
我们在进行删除操作前应判断此时链表是否为空如果已经为空则不能进行删除操作。
bool Empty(LTNode* head)
{assert(head);return head-next head;
}
6.头删和尾删
void PopFront(LTNode* head)
{assert(head);assert(!Empty(head));LTNode* tail head-next;head-next head-next-next;free(tail);tail NULL;}void PophBack(LTNode* head)
{assert(head);assert(!(Empty(head)));LTNode* tail head-prev;LTNode* tailprev tail-prev;tailprev-next head;head-prev tailprev;free(tail);tail NULL;
}
7.打印函数
在编写链表的插入删除功能时我们常需要对代码进行测试所以编写打印函数:
void LTPrin(LTNode* phead)
{assert(phead);printf(head);LTNode* cur phead-next;while (cur ! phead){printf(%d, cur-data);cur cur-next;}printf(\n);
}8.查找函数
LTNode* ListFind(LTNode* head, LTDataType x)
{assert(head);LTNode* cur head;while (cur-data ! x){cur cur-next;}return cur;}9.删除pos位置节点
void ListErase(LTNode* pos)
{assert(pos);LTNode* tail pos;pos-next-prev pos-prev;pos-prev-next pos-next;free(tail);tail NULL;
}10.在pos前位置插入数据
void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev pos-prev;LTNode* newnode CreateList(x);newnode-next pos;newnode-prev prev;pos-prev newnode;prev-next newnode;
}11.优化升级
在我们编写完pos位置插入和删除后其实对上文的头删尾删头插尾插都可以使用这两个函数来完成:
void PushBack(LTNode* head, LTDataType x)
{assert(head);ListInsert(head, x);
}void PushFront(LTNode* head, LTDataType x)
{assert(head);ListInsert(head-next, x);
}void PopFront(LTNode* head)
{assert(head);assert(!Empty(head));ListErase(head-next);
}void PophBack(LTNode* head)
{assert(head);assert(!(Empty(head)));ListErase(head-prev);
}
