• 循环双链表的基本运算
    • 循环双链表的定义
    • 初始化循环双链表
    • 求表长运算
    • 求线性表中第i个元素
    • 按值查找
    • 插入运算
    • 删除运算
    • 输出线性表
    • main

    循环双链表的基本运算

    循环双链表的定义

    1. #include <stdio.h>
    2. #include <malloc.h>
    4. typedef char ElemType;
    6. typedef struct node
    7. {    
    8.     ElemType data;                /*数据域*/
    9.     struct node *prior,*next;  /*分别指向前驱结点和后继结点的指针*/
    10. } DLink;

    初始化循环双链表

    1. void InitList(DLink *&L)
    2. {
    3.     L=(DLink *)malloc(sizeof(DLink));
    4.     L->prior=L->next=L;
    5. }

    求表长运算

    1. int GetLength(DLink *L)    /*求表长运算*/
    2. {
    3.     int i=0;
    4.     DLink *p=L->next;
    5.     while (p!=L) 
    6.     {
    7.         i++;p=p->next;
    8.     }
    9.     return i;
    10. }

    求线性表中第i个元素

    1. int GetElem(DLink *L,int i,ElemType &e)    /*求线性表中第i个元素*/
    2. {
    3.     int j=1;
    4.     DLink *p=L->next;  
    5.     if (i<1 || i>GetLength(L)) 
    6.         return(0);                /*i参数不正确,返回0*/
    7.     while (j<i)                  /*从第1个结点开始,查找第i个结点*/
    8.     { 
    9.         p=p->next;j++;
    10.     }
    11.     e=p->data;
    12.     return(1);                  /*返回1*/
    13. }

    按值查找

    1. int Locate(DLink *L,ElemType x)    /*按值查找*/
    2. {
    3.     int i=1;
    4.     DLink *p=L->next;
    5.     while (p!=L && p->data!=x)      /*从第1个结点开始查找data域为x的结点*/
    6.     {
    7.         p=p->next;
    8.         i++;
    9.     }
    10.     if (p==L)
    11.         return(0);
    12.     else
    13.         return(i);
    14. }

    插入运算

    1. int InsElem(DLink *L,ElemType x,int i)    /*插入运算*/
    2. {
    3.     int j=1;
    4.     DLink *p=L,*s;
    5.     s=(DLink *)malloc(sizeof(DLink));
    6.     s->data=x;s->prior=s->next=NULL;
    7.     if (i<1 || i>GetLength(L)+1) 
    8.             return 0;
    9.     while (j<i)              /*找到第i-1个结点,由p指向它*/
    10.     {
    11.            p=p->next;j++;
    12.     }
    13.     s->next=p->next;      /*s的next域指向p之后的结点*/
    14.     s->next->prior=s;     /*p之后结点的prior域指向s*/
    15.     p->next=s;             /*p的next域指向s*/
    16.     s->prior=p;            /*s的prior域指向p*/
    17.     return 1;
    18. }

    删除运算

    1. int DelElem(DLink *L,int i)    /*删除运算*/
    2. {
    3.     int j=1;
    4.     DLink *p=L,*q;
    5.     if (i<1 || i>GetLength(L)) 
    6.             return 0;
    7.     while (j<i)         /*找到第i-1个结点,由p指向它*/
    8.     {
    9.            p=p->next;j++;
    10.     }
    11.     q=p->next;          /*q指向p的下一个结点,即要删除的结点*/
    12.     p->next=q->next;       /*p的next指向q的下一个结点*/
    13.     q->next->prior=p;    /*q的下一个结点的prior域指向p*/
    14.     free(q);            /*释放q所占用的空间*/
    15.     return 1;
    16. }

    输出线性表

    1. void DispList(DLink *L)    /*输出线性表*/
    2. {
    3.     DLink *p=L->next;
    4.     while (p!=L) 
    5.     {
    6.         printf("%c ",p->data);p=p->next;
    7.     }
    8.     printf("\n");
    9. }

    main

    1. void main()
    2. {
    3.     int i;
    4.     ElemType e;
    5.     DLink *L;
    6.     InitList(L);        /*初始化双链表L*/
    7.     InsElem(L,'a',1);    /*插入元素*/
    8.     InsElem(L,'c',2);
    9.     InsElem(L,'a',3);
    10.     InsElem(L,'e',4);
    11.     InsElem(L,'d',5);
    12.     InsElem(L,'b',6);
    13.     printf("线性表:");DispList(L);
    14.     printf("长度:%d\n",GetLength(L));
    15.     i=3;GetElem(L,i,e);
    16.     printf("第%d个元素:%c\n",i,e);
    17.     e='a';
    18.     printf("元素%c是第%d个元素\n",e,Locate(L,e));
    19.     i=4;printf("删除第%d个元素\n",i);
    20.     DelElem(L,i);
    21.     printf("线性表:");DispList(L);
    22. }