循环双链表的基本运算
循环双链表的定义
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *prior,*next;
} DLink;
初始化循环双链表
void InitList(DLink *&L)
{
L=(DLink *)malloc(sizeof(DLink));
L->prior=L->next=L;
}
求表长运算
int GetLength(DLink *L)
{
int i=0;
DLink *p=L->next;
while (p!=L)
{
i++;p=p->next;
}
return i;
}
求线性表中第i个元素
int GetElem(DLink *L,int i,ElemType &e)
{
int j=1;
DLink *p=L->next;
if (i<1 || i>GetLength(L))
return(0);
while (j<i)
{
p=p->next;j++;
}
e=p->data;
return(1);
}
按值查找
int Locate(DLink *L,ElemType x)
{
int i=1;
DLink *p=L->next;
while (p!=L && p->data!=x)
{
p=p->next;
i++;
}
if (p==L)
return(0);
else
return(i);
}
插入运算
int InsElem(DLink *L,ElemType x,int i)
{
int j=1;
DLink *p=L,*s;
s=(DLink *)malloc(sizeof(DLink));
s->data=x;s->prior=s->next=NULL;
if (i<1 || i>GetLength(L)+1)
return 0;
while (j<i)
{
p=p->next;j++;
}
s->next=p->next;
s->next->prior=s;
p->next=s;
s->prior=p;
return 1;
}
删除运算
int DelElem(DLink *L,int i)
{
int j=1;
DLink *p=L,*q;
if (i<1 || i>GetLength(L))
return 0;
while (j<i)
{
p=p->next;j++;
}
q=p->next;
p->next=q->next;
q->next->prior=p;
free(q);
return 1;
}
输出线性表
void DispList(DLink *L)
{
DLink *p=L->next;
while (p!=L)
{
printf("%c ",p->data);p=p->next;
}
printf("\n");
}
main
void main()
{
int i;
ElemType e;
DLink *L;
InitList(L);
InsElem(L,'a',1);
InsElem(L,'c',2);
InsElem(L,'a',3);
InsElem(L,'e',4);
InsElem(L,'d',5);
InsElem(L,'b',6);
printf("线性表:");DispList(L);
printf("长度:%d\n",GetLength(L));
i=3;GetElem(L,i,e);
printf("第%d个元素:%c\n",i,e);
e='a';
printf("元素%c是第%d个元素\n",e,Locate(L,e));
i=4;printf("删除第%d个元素\n",i);
DelElem(L,i);
printf("线性表:");DispList(L);
}