C

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。表中最后一个结点的指针域指向头结点，整个链表形成一个环。嗯下面就网上找的一张单链的循环链表

单项链表定义：

typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; 单向循环链表基本操作：

/*操作结果：构造一个空的线性表L*/ void InitList(LinkList &L) /*初始条件：单循环链表L存在*/ /*操作结果：摧毁单循环链表L*/ void DestroyList(LinkList &L) /*初始条件：单循环链表L存在*/ /*操作结果：将L重置为空表*/ Status ClearList(LinkList &L) /*初始条件：单循环链表L存在*/ /*操作结果：若L为空表，则返回TRUE，否则返回FALSE*/ Status ListEmpty(LinkList L) /*初始条件：单循环链表L存在*/ /*操作结果：返回L中数据元素个数*/ int ListLength(LinkList L) /*初始条件：单循环链表L存在*/ /*操作结果：当第i个元素存在时，其值赋给e并返回OK，否则返回FALSE。*/ Status GetElem(LinkList L,int i,ElemType &e) /*初始条件：单循环链表L存在，compare()是数据元素判定的函数*/ /*操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为ERROR*/ Status LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) /*初始条件：单循环链表L存在*/ /*操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱；否则，操作失败，pre_e无定义*/ Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) /*初始条件：单循环链表L存在*/ /*操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继；否则，操作失败，next_e无定义*/ Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e) /*初始条件：单循环链表L存在*/ /*操作结果：在L的第i个位置之前插入元素e*/ Status ListInsert(LinkList &L,int i,ElemType e) /*初始条件：单循环链表L存在*/ /*操作结果：删除L的第i个元素，并由e返回其值*/ Status ListDelete(LinkList &L,int i,ElemType &e) /*初始条件：单循环链表L存在*/ /*操作结果：依次对每个数据元素调用函数visit()*/ void ListTraverse(LinkList L,void(*visit)(ElemType))

单向链表操作基本实现：

构造一个空的线性表L

/*操作结果：构造一个空的线性表L*/ void InitList(LinkList &L) { L=(LinkList)malloc(sizeof(LNode)); //产生头结点，并使L指向此头结点 if(!L){//空的线性表构造失败 printf("空的线性表构造失败，退出程序!\n"); exit(0); } L->next=L; //指针域指向头结点 }

摧毁单循环链表L

/*初始条件：单循环链表L存在*/ /*操作结果：摧毁单循环链表L*/ void DestroyList(LinkList &L) { LinkList q; LinkList p=L->next; //p指向头结点 while(p!=L) //没到表尾 { q=p->next; free(p); p=q; } free(L); L=NULL; }

将L重置为空表

/*初始条件：单循环链表L存在*/ /*操作结果：将L重置为空表*/ Status ClearList(LinkList &L) { LinkList p,q; L=L->next; //L指向头结点 p=L->next; //p指向第一个结点 while(p!=L) //没到表尾 { q=p->next; free(p); p=q; } L->next=L; //头结点指针域指向自身 } 对线性表进行判空

/*初始条件：单循环链表L存在*/ /*操作结果：若L为空表，则返回TRUE，否则返回FALSE*/ Status ListEmpty(LinkList L) { if(L->next==L) //线性表为空表 return TRUE; else return FALSE; } 返回表长

/*初始条件：单循环链表L存在*/ /*操作结果：返回L中数据元素个数*/ int ListLength(LinkList L) { int i=0; LinkList p=L->next; //p指向头结点 while(p!=L) //没到表尾 { i++; p=p->next; } return i; } 求链表位序结点

/*初始条件：单循环链表L存在*/ /*操作结果：当第i个元素存在时，其值赋给e并返回OK，否则返回FALSE。*/ Status GetElem(LinkList L,int i,ElemType &e) { int count=1; LinkList p=L->next->next; //p指向第一个结点 if(i<=0||i>ListLength(L)) //第i个元素不存在时 return ERROR; while(count<i) {//顺指针向后查找，直到p指向第i个元素 p=p->next; count++; } e=p->data; //取第i个元素 return OK; } 求链表结点位序

/*初始条件：单循环链表L存在，compare()是数据元素判定的函数*/ /*操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 若这样的数据元素不存在，则返回值为ERROR*/ Status LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { int i=0; LinkList p=L->next->next; //p指向第一个结点 while(p!=L->next) { i++; if(compare(p->data,e)) //满足关系 return i; p=p->next; } return 0; } 求前驱结点

/*初始条件：单循环链表L存在*/ /*操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱； 否则，操作失败，pre_e无定义*/ Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) { LinkList q; LinkList p=L->next->next; //p指向第一个结点 q=p->next; while(q!=L->next) //p没到表尾 { if(q->data==cur_e) { pre_e=p->data; return TRUE; } p=q; q=q->next; } return FALSE; //操作失败 } 求结点后继

/*初始条件：单循环链表L存在*/ /*操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继； 否则，操作失败，next_e无定义*/ Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e) { LinkList p=L->next->next; //p指向第一个结点 while(p!=L) //p没有到达链表尾 { if(p->data==cur_e) { next_e=p->next->data; return TRUE; } p=p->next; } return FALSE; //操作失败 } 链表中插入新结点

/*初始条件：单循环链表L存在*/ /*操作结果：在L的第i个位置之前插入元素e*/ Status ListInsert(LinkList &L,int i,ElemType e) { LinkList s; LinkList p=L->next; //p指向头结点 int count=0; if(i<0||i>ListLength(L)+1) //无法在第i个元素前插入 return ERROR; while(count<i-1) //寻找第i-1个结点 { p=p->next; count++; } s=(LinkList)malloc(sizeof(LNode)); //生成新结点 s->data=e; //插入L中 s->next=p->next; p->next=s; if(p==L) //改变尾结点 L=s; return OK; } 链表中删除结点

/*初始条件：单循环链表L存在*/ /*操作结果：删除L的第i个元素，并由e返回其值*/ Status ListDelete(LinkList &L,int i,ElemType &e) { LinkList p=L->next,q; //p指向头结点 int count=0; if(i<=0||i>ListLength(L)) //第i个元素不存在 return ERROR; while(count<i-1) //寻找第i-1个结点 { p=p->next; count++; } q=p->next; //q指向删除结点 p->next=q->next; e=q->data; if(L==q) //删除的是表尾元素 L=p; free(q); return OK; } 依次查看结点元素

/*初始条件：单循环链表L存在*/ /*操作结果：依次对每个数据元素调用函数visit()*/ void ListTraverse(LinkList L,void(*visit)(ElemType)) { LinkList p=L->next->next; //p指向第一个结点 while(p!=L->next) //p不指向头结点 { visit(p->data); p=p->next; } printf("\n"); }

嗯下面就是在VC中的测试

//单循环链表 #include<stdio.h> #include<stdlib.h> #include<string.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int ElemType; typedef int Status; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; Status compare(ElemType e1,ElemType e2) { if(e1==e2) return 0; else if(e1>e2) return 1; else if(e1<e2) return -1; } Status equal(ElemType c1,ElemType c2) { if(c1==c2) return TRUE; else return ERROR; } void visit(ElemType e) { printf("%d \n",e); } void print(ElemType c) { printf("%d ",c); } /*操作结果：构造一个空的线性表L*/ void InitList(LinkList &L) { L=(LinkList)malloc(sizeof(LNode)); //产生头结点，并使L指向此头结点 if(!L){//空的线性表构造失败 printf("空的线性表构造失败，退出程序!\n"); exit(0); } L->next=L; //指针域指向头结点 } /*初始条件：单循环链表L存在*/ /*操作结果：摧毁单循环链表L*/ void DestroyList(LinkList &L) { LinkList q; LinkList p=L->next; //p指向头结点 while(p!=L) //没到表尾 { q=p->next; free(p); p=q; } free(L); L=NULL; } /*初始条件：单循环链表L存在*/ /*操作结果：将L重置为空表*/ Status ClearList(LinkList &L) { LinkList p,q; L=L->next; //L指向头结点 p=L->next; //p指向第一个结点 while(p!=L) //没到表尾 { q=p->next; free(p); p=q; } L->next=L; //头结点指针域指向自身 } /*初始条件：单循环链表L存在*/ /*操作结果：若L为空表，则返回TRUE，否则返回FALSE*/ Status ListEmpty(LinkList L) { if(L->next==L) //线性表为空表 return TRUE; else return FALSE; } /*初始条件：单循环链表L存在*/ /*操作结果：返回L中数据元素个数*/ int ListLength(LinkList L) { int i=0; LinkList p=L->next; //p指向头结点 while(p!=L) //没到表尾 { i++; p=p->next; } return i; } /*初始条件：单循环链表L存在*/ /*操作结果：当第i个元素存在时，其值赋给e并返回OK，否则返回FALSE。*/ Status GetElem(LinkList L,int i,ElemType &e) { int count=1; LinkList p=L->next->next; //p指向第一个结点 if(i<=0||i>ListLength(L)) //第i个元素不存在时 return ERROR; while(count<i) {//顺指针向后查找，直到p指向第i个元素 p=p->next; count++; } e=p->data; //取第i个元素 return OK; } /*初始条件：单循环链表L存在，compare()是数据元素判定的函数*/ /*操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 若这样的数据元素不存在，则返回值为ERROR*/ Status LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { int i=0; LinkList p=L->next->next; //p指向第一个结点 while(p!=L->next) { i++; if(compare(p->data,e)) //满足关系 return i; p=p->next; } return 0; } /*初始条件：单循环链表L存在*/ /*操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱； 否则，操作失败，pre_e无定义*/ Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) { LinkList q; LinkList p=L->next->next; //p指向第一个结点 q=p->next; while(q!=L->next) //p没到表尾 { if(q->data==cur_e) { pre_e=p->data; return TRUE; } p=q; q=q->next; } return FALSE; //操作失败 } /*初始条件：单循环链表L存在*/ /*操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继； 否则，操作失败，next_e无定义*/ Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e) { LinkList p=L->next->next; //p指向第一个结点 while(p!=L) //p没有到达链表尾 { if(p->data==cur_e) { next_e=p->next->data; return TRUE; } p=p->next; } return FALSE; //操作失败 } /*初始条件：单循环链表L存在*/ /*操作结果：在L的第i个位置之前插入元素e*/ Status ListInsert(LinkList &L,int i,ElemType e) { LinkList s; LinkList p=L->next; //p指向头结点 int count=0; if(i<0||i>ListLength(L)+1) //无法在第i个元素前插入 return ERROR; while(count<i-1) //寻找第i-1个结点 { p=p->next; count++; } s=(LinkList)malloc(sizeof(LNode)); //生成新结点 s->data=e; //插入L中 s->next=p->next; p->next=s; if(p==L) //改变尾结点 L=s; return OK; } /*初始条件：单循环链表L存在*/ /*操作结果：删除L的第i个元素，并由e返回其值*/ Status ListDelete(LinkList &L,int i,ElemType &e) { LinkList p=L->next,q; //p指向头结点 int count=0; if(i<=0||i>ListLength(L)) //第i个元素不存在 return ERROR; while(count<i-1) //寻找第i-1个结点 { p=p->next; count++; } q=p->next; //q指向删除结点 p->next=q->next; e=q->data; if(L==q) //删除的是表尾元素 L=p; free(q); return OK; } /*初始条件：单循环链表L存在*/ /*操作结果：依次对每个数据元素调用函数visit()*/ void ListTraverse(LinkList L,void(*visit)(ElemType)) { LinkList p=L->next->next; //p指向第一个结点 while(p!=L->next) //p不指向头结点 { visit(p->data); p=p->next; } printf("\n"); } int main() { int n; int ch; LinkList L; ElemType e; InitList(L); //初始化单循环链表 printf("单循环链表构造成功!\n"); printf("请输入单循环链表的长度："); scanf("%d",&n); printf("请输入单循环链表各个数据："); for(int i=1;i<=n;i++) { scanf("%d",&e); ListInsert(L,i,e); //在第i个结点前插入e } printf("*********************************\n"); printf("1、插入结点\n2、删除结点\n3、链表判空\n"); printf("4、链表长度\n5、清空链表\n6、销毁链表\n"); printf("7、结点前驱\n8、结点后续\n9、遍历链表\n"); printf("10、查询位序结点\n"); printf("11、查询结点位序\n"); printf("0、退出操作\n"); printf("*********************************\n"); printf("请选择接下来要进行的操作:"); while(scanf("%d",&ch)&&ch!=0) { if(ch==1){ int set; printf("请输入在第几个结点之前插入新结点:"); scanf("%d",&set); printf("请输入要插入结点的数据:"); scanf("%d",&e); if(ListInsert(L,set,e)) printf("操作成功!\n"); } if(ch==2){ int set; printf("请输入要删除第几个结点："); scanf("%d",&set); if(ListDelete(L,set,e)) printf("成功删除第%d个结点，其值为%d\n",set,e); } if(ch==3){ if(ListEmpty(L)) printf("这是一个空的链表!\n"); else printf("这不是一个空的链表!\n"); } if(ch==4){ printf("链表的长度为:%d\n",ListLength(L)); } if(ch==5){ if(ClearList(L)) printf("已成功清空链表!\n"); } if(ch==6){ DestroyList(L); } if(ch==7){ printf("请输入要查找元素的前驱:"); scanf("%d",&n); if(PriorElem(L,n,e)) printf("%d元素的前驱是%d\n",n,e); else printf("输入错误!\n"); } if(ch==8){ printf("请输入要查找元素的后续:"); scanf("%d",&n); if(NextElem(L,n,e)) printf("%d元素的后续是%d\n",n,e); else printf("输入错误!\n");//输入的是尾结点也会判断尾输入错误 } if(ch==9){ printf("正序输出链表:"); ListTraverse(L,print); } if(ch==10){ printf("请输入要匹配的数据元素:"); scanf("%d",&n); if(LocateElem(L,n,equal)) printf("等于%d的元素是第%d个\n",n,LocateElem(L,n,equal)); else printf("链表中不存在元素%d\n",n); } if(ch==11){ int set; printf("请输入要查询链表位序的值:"); scanf("%d",&set); if(GetElem(L,set,e)) printf("链表的第%d个元素的值为%d\n",set,e); else printf("输入错误!\n"); } printf("请选择接下来要进行的操作:"); } printf("成功退出操作!\n"); return 0; }