C_线性表(ADT)-单向循环链表的表示和实现
程序员文章站
2022-08-04 18:11:12
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。表中最后一个结点的指针域指向头结点，整个链表形成一个环。嗯下面就网上找的一张单链的循环链表
单...
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。表中最后一个结点的指针域指向头结点，整个链表形成一个环。嗯下面就网上找的一张单链的循环链表
单项链表定义：
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(countnext;
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(countnext;
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(countnext;
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
#include
#include
#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)" true;="" else="" error;="" void="" visit(elemtype="" e)="" printf("%d="" \n",e);="" print(elemtype="" c)="" ",c);="" *操作结果：构造一个空的线性表l*="" 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(countnext;
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(countnext;
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(countnext;
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;
}