1、循环列表:表中的最后一个节点的指针域指向头结点,整个链表形成一个环,从表中的任一节点出发均可找到表中其他节点。
2、双向链表:某个指针只能从顺指针往后查其他节点,如要查询前驱节点,需要从表头指针出发,双向链表有前驱,有后继。
3、双向循环链表以上两种性质叠加
1、节点结构 prior element next
2、空的双向循环链表 L->next = L; L->prior = L;
3、非空双向循环链表:头节点的前驱指向最后一个节点,最后一个节点的后驱指向头结点
4、相关操作
1、引用头文件和宏定义
#include<stdio.h> #include<stdlib.h> #define ERROR 0 #define OK 1 #define Elemtype int #define Status int
2、结构体定义
typedef struct DulNode { Elemtype data; struct DulNode *prior; struct DulNode *next; }DulNode,*DulLinkList;
3、创造链表(只写了尾插法,头插法感觉有点绕,可能后期会补)
//双向循环链表 void Create_L(DulLinkList L,int n) { DulLinkList p; DulLinkList q; int i; p = L; for(i = 1;i <= n;i++)//尾插法 { q = (DulLinkList)malloc(sizeof(DulNode)); printf("please input a num:"); scanf("%d",&q->data); q->next = p->next; p->next = q; q->prior = p; p = p->next; } L->prior = p; }
4、寻找i位置元素
//寻找第i个元素 Status GetElem_Dul(DulLinkList L,int i,Elemtype *e) { int j = 1; DulLinkList p; p = L->next; while(p&&j<i) { p = p->next; j++; } if(!p||j>i) { return ERROR; } *e = p->data; return OK; }
5、在i位置插入e元素(这是找到插入节点的前一个节点,也可以找到当前节点,把插入节点放到前一个)
Status ListInsert_Dul(DulLinkList L,int i,Elemtype e) { int n = 1; DulLinkList p; DulLinkList s; p = L->next; while(p&&n<i-1) { p = p->next; n++; } if(!p||n>i-1) { return ERROR; } s = (DulLinkList)malloc(sizeof(DulNode)); s->data = e; p->next->prior = s; s->next = p->next; s->prior = p; p->next = s; return OK; }
6、输出i位置节点,保存其元素
/删除第i个元素,并且保存值 Status ListDelete_Dul(DulLinkList L,int i,Elemtype *e) { DulLinkList p; int j = 1; p = L->next; while(p&&j<i) { p = p->next; j++; } if(!p||j>i) { return ERROR; } *e = p->data; p->prior->next = p->next; p->next->prior = p->prior; free(p); return OK; }
7、主函数
int main() { DulLinkList L1 = (DulLinkList)malloc(sizeof(DulNode)); L1->next = L1; L1->prior = L1; int e = 3; int i = 2; int n; printf("please input the length:"); scanf("%d",&n); Create_L(L1,n); Output(L1); ListInsert_Dul(L1,i,e); Output(L1); ListDelete_Dul(L1,i,&e); Output(L1); free(L1); return 0; }
链表到此位置了哈哈哈哈终于结束了一块