#include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<assert.h> //双向循环链表的结构体定义 typedef struct node { int data; struct node *prior; struct node *next; }NODE,*PNODE,*LINKLIST; //初始化 void init(LINKLIST *list) { *list = (PNODE)malloc(sizeof(NODE)); (*list)->next = *list; (*list)->prior = *list; } //添加 void add(LINKLIST list,int data) { PNODE p=list,q; q=(PNODE)malloc(sizeof(NODE));//q为要插入的节点 q->data =data; q->next = p; q->prior = p->prior; if(p->prior) p->prior->next = q; p->prior = q; } //插入 i>=1 void insert(LINKLIST list,int i,int data) { PNODE p=list,q; //将p移动到i-1个位置 while(--i && p->next!=list) { p=p->next; } assert(i==0); q = (PNODE)malloc(sizeof(NODE));//q为需要插入的节点 q->data =data; q->next = p->next; q->prior = p; if(p->next) p->next->prior = q; p->next = q; } //删除 void del(LINKLIST list,int i,int *data) { PNODE p=list,q; //将p移动到第i-1个位置 while(--i && p->next!=list) { p=p->next; } assert(i==0 && p->next!=list); q = p->next;//q为要删除的节点 *data = q->data;//将删除的节点的数据域返回 p->next = q->next;//p断开与q连接,和q的后继相连 if(q->next) q->next->prior = p;//如果删除节点存在后继，那么将这个的prior的指向p }//end del //获取双向循环链表的长度 int getLen(LINKLIST list) { PNODE p=list; int i=0; while((p=p->next)!=list) { i++; } return i; } //获取第i个位置的数据 int getData(LINKLIST list,int i) { PNODE p=list; //将p移动到第i个位置 while(i--) { p=p->next; assert(p!=list); } return p->data; } //正转一圈输出 void display1(LINKLIST list) { PNODE p=list; while((p=p->next)!=list) { printf("%d ",p->data); }//end while printf(" "); } //正转两圈输出 void display2(LINKLIST list) { int count=0;//统计p转到list个数 PNODE p=list; while(count<2) { p=p->next; if(p==list) { count++; continue; }else { printf("%d ",p->data); } } printf(" "); } //反转一圈输出 void display_1(LINKLIST list) { PNODE p=list; while((p=p->prior)!=list) { printf("%d ",p->data); } printf(" "); } //反转两圈输出 void display_2(LINKLIST list) { int count=0;//统计p转到list个数 PNODE p=list; while(count<2) { p=p->prior; if(p==list) { count++; continue; }else { printf("%d ",p->data); } } printf(" "); } //销毁 void destroy(LINKLIST *list) { PNODE p = *list,q; while(p->next != *list) { q=p->next; free(p); p = q; } *list = NULL; } //显示菜单 void displaymenu() { printf("**********这是一个双向循环链表的基本操作程序********** "); printf(" 1,添加 "); printf(" 2,插入 "); printf(" 3,删除 "); printf(" 4,获取长度 "); printf(" 5,获取数据 "); printf(" 6,正转输出一圈 "); printf(" 7,正转输出两圈 "); printf(" 8,反转输出一圈 "); printf(" 9,反转输出两圈 "); printf(" 0,销毁退出 "); }//end displaymenu int main() { int i,j,choice,flag=1; LINKLIST list=NULL; init(&list);//初始化链表 displaymenu();//显示菜单 while(flag) { printf("请选择你要的操作："); scanf("%d",&choice);//输入 switch (choice) { case 1: printf("--你当前选择了添加操作-- (说明：按组合键ctrl+Z并回车可结束添加操作) "); while(scanf("%d",&i)!=EOF) { add(list,i); }//end while printf("--添加操作结束-- "); break; case 2: printf("--你当前选择了插入操作-- "); printf("--请输入插入元素的数据："); scanf("%d",&j); printf("--请输入插入位置："); scanf("%d",&i); insert(list,i,j); printf("--插入结束-- "); break; case 3: printf("--你当前选择了删除操作-- "); printf("--请输入删除位置："); scanf("%d",&i); del(list,i,&j); printf("--你删除的元素的数据：%d ",j); printf("--删除结束-- "); break; case 4: printf("--你当前选择了获取长度操作-- "); printf("双向循环链表的长度：%d ",getLen(list)); printf("--获取表长结束-- "); break; case 5: printf("--你当前选择了获取数据操作-- "); printf("--请输入你要获取元素的位置："); scanf("%d",&i); printf("第%d个位置的数据为：%d ",i,getData(list,i)); printf("--获取数据结束-- "); break; case 6: printf("--你当前选择了正转输出一圈操作-- "); display1(list); printf("--正转输出一圈操作结束-- "); break; case 7: printf("--你当前选择了正转输出两圈操作-- "); display2(list); printf("--正转输出两圈操作结束-- "); break; case 8: printf("--你当前选择了反转输出一圈操作-- "); display_1(list); printf("--反转输出一圈操作结束-- "); break; case 9: printf("--你当前选择了反转输出两圈操作-- "); display_2(list); printf("--反转输出两圈操作结束-- "); break; case 0: printf("--你当前选择了销毁并退出操作-- "); destroy(&list);//销毁链表 flag=0;//退出循环 printf("--退出操作结束-- "); break; default: printf("--你选择错误！ "); break; }//end switch }//end while(flag) system("pause"); return 0; }