双向循环链表
双向循环链表能够访问前驱和后继,快速定位到尾节点,并在在尾部进行插入和删除,也能够找到任意节点前驱和后继,方便添加和删除元素。
双向链表的存储结构
1 2 3 4
| typedef struct DulNode{ ElemType data; struct DulNode *next,*prior; }DulNode,*DulLinkList;
|
一个双向链表结点由三部分组成,分别是前驱指针,数据域,后驱指针。DulNode表示节点,*DulLinkList表示链表的头指针。
![image-20240626094457416](https://cdn.jsdelivr.net/gh/qianxiaolin/picgo/202406260946759.png)
链表初始化
1 2 3 4 5 6 7 8 9 10
| Status InitList(LinkList &L) { L=(LinkList)malloc(sizeof(LNode)); if(L==NULL) return ERROR; L->next==L; L->prior=L; L->data=0; return OK; }
|
初始化过程中,将前驱指向L自身,L的后继也指向自身,形成闭环。
![image-20240626094828769](https://cdn.jsdelivr.net/gh/qianxiaolin/picgo/202406260948959.png)
头插法和尾插法
头插法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| Status HeadCreateList(LinkList &L) { int num; ElemType data; std::cin>>num; for(int i=0;i<num;i++){ std::cin>>data; LNode *s=(LNode *)malloc(sizeof(LNode)); if(!s) return ERROR; s->data=data; s->prior=L; s->next=L->next; L->next->prior=s; L->next=s; } return OK; }
|
尾插法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| Status TailCreateList(DulLinkList &L) { LNode *tail=L; int num; ElemType data; std::cin>>num; for(int i=0;i<num;i++){ std::cin>>data; LNode *s=(LNode *)malloc(sizeof(LNode)); if(!s) return ERROR; s->data=data;
s->prior=L->prior; L->prior->next=s; L->prior=s; s->next=L;
} return OK; }
|
定位元素
获取第i个的元素的值
1 2 3 4 5 6 7 8 9 10 11 12 13
| Status GetElem(LinkList L,int i,ElemType &e) { int j=1; LNode *p=L->next; while(p!=L&&j<i){ p=p->next; j++; } if(p==NULL||j>i) return ERROR; e=p->data; return OK; }
|
按值查找元素
1 2 3 4 5 6 7 8 9
| LNode *LocateElem(LinkList L,ElemType e) { LNode *p=L->next; while(p!=L&&p->data!=e){ p=p->next; } return p; }
|
插入元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
Status ListInsert(DulLinkList &L,int i,ElemType e) { int j=1; LNode* p=L->next; while(p!=L&&j<i-1){ p=p->next; j++; } LNode* s=(DulNode*)malloc(sizeof(LNode)); if(!s) return ERROR; s->data=e; s->prior=p->prior; p->prior->next=s;
s->next=p; p->prior=s; return OK; }
|
删除元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| Status ListDelete(LinkList &L,int i) { int j=1; LNode* p=L->next; while(p&&j<i-1){ p=p->next; j++; } DulNode *s=p->next; p->prior->next=s; s->prior=p->prior; free(s); return OK; }
|
遍历链表
1 2 3 4 5 6 7 8 9 10 11
| Status PrintList(LinkList L) { LNode *p=L->next; while(p!=L){ std::cout<<p->data<<"->"; p=p->next; } std::cout<<std::endl; return OK; }
|