循环双向链表的初始化及创建-头插法和尾插法
温馨提示:
本文最后更新于 2021年02月08日,已超过 1,396 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我。
什么是循环双向链表?
为克服单链表的这种单向性特点,在双向链表的结点有两个指针域,一个指向直接后继,另一个指向直接前驱。
循环双向链表的操作
1.初始化
2.头插法创建链表
3.尾插法创建链表
4.打印链表中的所有元素
5.可以把循环单链表和循环双向链表来对比一下来理解。参考文章:
循环单链表基本操作
循环双链表的结构
这个地方要区别循环单链表,单链表中只有一个指针域,而循环双链表有两个指针域。
typedef struct DuLNode{
int data; //数据域
struct DuLNode *prior; //头指针
struct DuLNode *next; //尾指针
}DuLNode,*DuLinkList;
初始化链表
/*循环双链表的初始化*/
int InitDuList_L(DuLinkList &L){
L = (DuLinkList)malloc(sizeof(DuLNode));
if(L==NULL) {
return 1;
}
L->prior = L; //头结点的头指针指向自己
L->next = L; //头结点的
return 0;
}
头插法创建链表
/*循环双链表的创建 头插法*/
int InsertDuList_Head_L(DuLinkList &L,int n){
for(int i = n;i>0;i--){
DuLinkList newNode = (DuLinkList)malloc(sizeof(DuLNode));
printf("请输入第%d个元素值:",n-i+1);
scanf("%d",&newNode->data); //将输入的元素值 赋值给新创建的结点
newNode->next = L->next;
L->next->prior = newNode;
newNode->prior = L;
L->next = newNode;
}
return 0;
}
尾插法创建链表
/*循环双链表的创建 尾插法*/
int InsertDuList_Rear_L(DuLinkList &L,int n){
DuLinkList p = L;
while(p->next != L){ //将指针移动到最后一个结点
p = p->next;
}
for(int i = 0;i<n;i++){
DuLinkList newNode = (DuLinkList)malloc(sizeof(DuLNode));
printf("请输入第%d个元素:",i+1);
scanf("%d",&newNode->data);
newNode->next = p->next;
p->next->prior = newNode;
newNode->prior = p;
p->next = newNode;
p = p->next; //将p一直指到最后一个结点
}
return 0;
}
打印链表中的元素
/*打印链表中的元素*/
int PrintList_L(DuLinkList L) {
DuLinkList p = L;
int i=1;
while(p->next != L){
p = p->next;
printf("第%d个元素为:%d\n",i,p->data);
i++;
}
}
完整代码
#include<stdio.h>
#include<stdlib.h>
typedef struct DuLNode{
int data; //数据域
struct DuLNode *prior; //头指针
struct DuLNode *next; //尾指针
}DuLNode,*DuLinkList;
/*循环双链表的初始化*/
int InitDuList_L(DuLinkList &L){
L = (DuLinkList)malloc(sizeof(DuLNode));
if(L==NULL) {
return 1;
}
L->prior = L; //头结点的头指针指向自己
L->next = L; //头结点的
return 0;
}
/*循环双链表的创建 头插法*/
int InsertDuList_Head_L(DuLinkList &L,int n){
for(int i = n;i>0;i--){
DuLinkList newNode = (DuLinkList)malloc(sizeof(DuLNode));
printf("请输入第%d个元素值:",n-i+1);
scanf("%d",&newNode->data); //将输入的元素值 赋值给新创建的结点
newNode->next = L->next;
L->next->prior = newNode;
newNode->prior = L;
L->next = newNode;
}
return 0;
}
/*循环双链表的创建 尾插法*/
int InsertDuList_Rear_L(DuLinkList &L,int n){
DuLinkList p = L;
while(p->next != L){ //将指针移动到最后一个结点
p = p->next;
}
for(int i = 0;i<n;i++){
DuLinkList newNode = (DuLinkList)malloc(sizeof(DuLNode));
printf("请输入第%d个元素:",i+1);
scanf("%d",&newNode->data);
newNode->next = p->next;
p->next->prior = newNode;
newNode->prior = p;
p->next = newNode;
p = p->next; //将p一直指到最后一个结点
}
return 0;
}
/*打印链表中的元素*/
int PrintList_L(DuLinkList L) {
DuLinkList p = L;
int i=1;
while(p->next != L){
p = p->next;
printf("第%d个元素为:%d\n",i,p->data);
i++;
}
}
main(){
DuLinkList L;
int initStatus;
int headStatus;
int rearStatus;
//循环链表的初始化
initStatus = InitDuList_L(L);
if(initStatus==0){
printf("链表初始化成功\n");
printf("===============\n");
}else{
printf("链表初始化失败\n");
}
//头插法
headStatus = InsertDuList_Head_L(L,3);
if(headStatus==0){
printf("头插法插入成功\n");
}else{
printf("头插法插入失败\n");
}
//尾插法
rearStatus = InsertDuList_Rear_L(L,3);
if(rearStatus==0){
printf("尾插法插入成功\n");
}else{
printf("尾插法插入失败\n");
}
//打印链表中的数据元素
PrintList_L(L);
}
运行结果
头插法插入的元素与输入的元素顺序相反,尾插法插入的元素顺序与插入的顺序相同。
正文到此结束
- 本文标签: c语言 数据结构 线性表
- 本文链接: https://www.it1997.com/article/39
- 版权声明: 本文由小陈没烦恼原创发布,转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权