循环单链表的基本运算

循环单链表的定义

  1. #include <stdio.h>
  2. #include <malloc.h>
  4. typedef char ElemType;
  6. typedef struct node 
  7. {     
  8.     ElemType data;            /*数据域*/
  9.     struct node *next;         /*指针域*/
  10. } SLink;

初始化循环单链表

  1. void InitList(SLink *&L)       /*初始化线性表,L为引用型参数*/
  2. {
  3.     L=(SLink *)malloc(sizeof(SLink));
  4.     L->next=L;
  5. }

求线性表的长度

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

求线性表中第i个元素

  1. int GetElem(SLink *L,int i,ElemType &e)    /*求线性表中第i个元素*/
  2. {
  3.     int j=1;
  4.     SLink *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;
  10.         j++;
  11.     }
  12.     e=p->data;
  13.     return(1);              /*返回1*/
  14. }

按值查找

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

插入结点

  1. int InsElem(SLink *L,ElemType x,int i)    /*插入结点*/
  2. {
  3.     int j=1;
  4.     SLink *p=L,*s;
  5.     s=(SLink *)malloc(sizeof(SLink));
  6.     s->data=x;s->next=NULL;
  7.     if (i<1 || i>GetLength(L)+1) 
  8.         return 0;
  9.     while (j<i) 
  10.     {
  11.         p=p->next;j++;
  12.     }
  13.     s->next=p->next;
  14.     p->next=s;
  15.     return 1;
  16. }

删除结点

  1. int DelElem(SLink *L,int i)    /*删除结点*/
  2. {
  3.     int j=1;
  4.     SLink *p=L,*q;
  5.     if (i<1 || i>GetLength(L)) 
  6.         return 0;
  7.     while (j<i) 
  8.     {
  9.         p=p->next;j++;
  10.     }
  11.     q=p->next;
  12.     p->next=q->next;
  13.     free(q);
  14.     return 1;
  15. }

输出线性表

  1. void DispList(SLink *L)    /*输出线性表*/
  2. {
  3.     SLink *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.     SLink *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. }