复杂的链式存储结构
循环链表
定义:是一种头尾相接的链表(即表中最后一个结点的指针域指向头结点,整个链表形成一个环)
优点:从表中任一节点出发均可找到表中其他结点
注意:涉及遍历操作时,终止条件是判断 p->next == L?
双向链表
定义:在单链表的每个结点离再增加一个指向直接前驱的指针域 prior,这样链表中就形成了有
两个方向不用的链,故称为双向链表
双向循环链表
定义:
和单链的循环表类似,双向链表也可以有循环表
·让头节点的前驱指针指向链表的最后一个结点
·让最后一个结点的后继指针指向头结点
示例图(2张):
注意:
在双向链表中有些操作(如:ListLength、GetElem等),
因仅涉及一个方向的指针,故它们的算法与线性链表的相同。
但在插入、删除时,需同时修改两个方向上的指针
算法:
#include <stdio.h> #include <stdlib.h> #define ERROR 0 #define OK 1 // 双向循环链表 typedef struct Londe{ int number; struct Londe *prev; // struct Londe *next; }Londe; typedef Londe *Linklist; // LinkList为指向结构体 Londe 的指针类型 // 初始化 int initList_L(Linklist *L); // 通过索引获取结点对象 Linklist getLinkListByI(Linklist *L,int i); // 遍历结点 int showList_L(Linklist L); // 插入数据 int insertList_L(Linklist *L,int number); // 删除指定索引的结点 int delLinkByI(Linklist *L,int i); int main(void){ Linklist L = NULL; // 初始化单链表 initList_L(&L); // 插入数据 insertList_L(&L,2); insertList_L(&L,3); delLinkByI(&L,1); showList_L(L); } // 初始化 int initList_L(Linklist *L){ Linklist node = (Linklist)malloc(sizeof(Londe)); if(!node){ return ERROR; } node->number = 1; node->next = node; node->prev = node; *L = node; return OK; } // 插入数据 int insertList_L(Linklist *L,int number){ Linklist node = (Linklist)malloc(sizeof(Londe)); if(!node){ return ERROR; } node->number = number; (*L)->prev->next = node; node->prev = (*L)->prev; node->next = (*L); (*L)->prev = node; return OK; } // 遍历结点 int showList_L(Linklist L){ Linklist temp = L; do{ printf("前驱指针%p;值:%d;后继指针%p \n",L->prev,L->number,L->next); L = L->next; }while(temp != L); return OK; } // 通过索引获取结点对象 Linklist getLinkListByI(Linklist *L,int i){ int ii = 0; Linklist T = *L; while(ii != i){ T = T->next; ii++; } return T; } // 删除指定索引的结点 int delLinkByI(Linklist *L,int i){ printf("打点1"); Linklist temp = getLinkListByI(L,i); printf("值是%d \n",temp->number); temp->prev->next = temp->next; temp->next->prev = temp->prev; return OK; }