双向循环列表是在双向链表的基础上将尾结点的next指针指向头结点,把头结点的prev指针指向尾结点,使得链表形成一个闭环。草图如下:
具体代码:
C文件:
#include "linklist.h"
#include "stdio.h"
#include "stdlib.h"
//创建一个结点
struct node *creatNode(data_t data){
struct node *newnode = (struct node *)malloc(sizeof(struct node));
if(newnode == NULL) {
printf("创建结点失败,申请内存为空!\n");
return NULL;
}
newnode->data = data;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
//创建一个双向循环链表(头结点)
struct node *creatList(void){
struct node* newnode = (struct node *)malloc(sizeof(struct node));
if(newnode == NULL){
printf("创建双向链表失败,申请内存为空!\n");
return NULL;
}
newnode->data = 0;
newnode->next = newnode->prev = newnode;
return newnode;
}
//获取双向链表中指定位置元素
/*
定义头结点的位置为-1
*/
struct node *list_get(struct node *H,int pos){
if(H == NULL) return NULL;
if(pos <-1) return NULL;
int i=-1;
struct node *p = H;
while(i<pos && p->next != H){
p = p->next;
i++;
}
if(i!=pos) return NULL;
return p;
}
//指定位置插入一个数据
/*
定义头结点位置为-1
*/
int list_insert(struct node *H,int pos,data_t data){
if(H==NULL) return -1;
if(pos<0) return -1;
struct node *p = list_get(H,pos-1);//找到该位置的前驱结点
if(p==NULL) return -1;
struct node *newnode = creatNode(data);
//p结点是肯定存在的
newnode->prev = p;
newnode->next = p->next;
p->next->prev = newnode;
p->next = newnode;
return 0;
}
//删除指定位置的结点
int list_delete(struct node *H,int pos){
if(H==NULL) return -1;
if(pos<0) return -1;
struct node *p = list_get(H,pos);
if(p==NULL) return -1;
//p结点是肯定存在的
p->prev->next = p->next;
p->next->prev = p->prev;
free(p);
return 0;
}
//销毁双向链表
struct node *list_free(struct node *H){
if(H==NULL) return NULL;
struct node *q = H;//记录头结点的位置
struct node *p = H;
while(H->next != q){
H = H->next;
free(p);
p = H;
}free(p);
return NULL;
}
//遍历链表
int list_show(struct node *H){
if(H == NULL) return -1;
struct node *p = H->next;
while(p!=H){
printf("%d ",p->data);
p = p->next;
}printf("\n");
return 0;
}
测试代码:
#include "stdio.h"
#include "stdlib.h"
#include "linklist.h"
int main(){
int pos;
data_t value;
struct node *H = creatList();
printf("**********************指定位置插入结点测试*********************\n");
while(1){
printf("请按顺序输入位置和数据,输入-1 -1结束测试:");
scanf("%d %d",&pos,&value);
if(pos == -1 && value == -1) {
printf("测试结束!\n");
break;
}
int res;
res = list_insert(H,pos,value);
if(res==0){
printf("\n插入成功,新链表为:");
list_show(H);
}
else{
printf("插入失败!\n");
}
}
H = list_free(H);
H = creatList();
for(int i=0;i<10;i++){
list_insert(H,i,i);
}
list_show(H);
printf("***********************指定位置查找元素测试********************\n");
while(1){
printf("请输入一个位置,输入-1结束测试:");
scanf("%d",&pos);
if(pos == -1){
printf("测试结束!\n");
break;
}
struct node *p = list_get(H,pos);
if(p == NULL){
printf("查找失败!\n");
}
else{
printf("查找的元素为:%d\n",p->data);
}
}
printf("***********************删除指定位置结点测试********************\n");
printf("当前链表:");
list_show(H);
while(1){
printf("请按顺序输入位置和数据,输入-1结束测试:");
scanf("%d",&pos);
if(pos == -1) {
printf("测试结束!\n");
break;
}
int res;
res = list_delete(H,pos);
if(res == 0){
printf("删除成功,新链表为:");
list_show(H);
}
else{
printf("删除失败!\n");
}
}
return 0;
}
测试结果如下
插入测试:
查找元素
删除元素
By urien 2021年2月4日 17:52:47