循环单链表的现实

《数据结构》中静态链表暂时没理解到，所以先写循环单链表的实现。

Status.h

/******************************************************************
      程序中要用到的 函数结果状态代码
******************************************************************/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等

typedef int Boolean;

 

include.h

/******************************************************************
      程序中要用的头文件
******************************************************************/
 #include<string.h>
 #include<ctype.h>
 #include<malloc.h> // malloc()等

 #include<limits.h> // INT_MAX等

 #include<stdio.h> // EOF(=^Z或F6),NULL

 #include<stdlib.h> // atoi()

 #include<io.h> // eof()

 #include<math.h> // floor(),ceil(),abs()

 #include<process.h> // exit()

 #include<iostream.h> // cout,cin




/******************************************************************
      自定义头文件
******************************************************************/
#include "status.h"

list.h

 

#include "status.h"

//--------------线性表单链表的结构体-------------------------

typedef int ElemType;

struct LNode
{
    ElemType data;
    struct    LNode *next;
}LNode;
typedef struct LNode *LinkList;
//--------------线性表单链表的结构体-------------------------



/***********************************************************
* 函数声明 *
************************************************************/
Status InitList_CL(LinkList *L);//循环单链表初始化函数

int ListLength_CL(LinkList L);//求L中的元素的个数

Status ListInsert_CL(LinkList *L,int i ,ElemType e);//在第i个位置之前插入元素e

Status ClrearList_CL(LinkList *L);//置空L表函数 成功返回OK

Status ListEmpty_CL(LinkList L);//判空函数 空返回TRUE 否则返回FALSE

Status GetElem_CL(LinkList L,int i,ElemType *e);//获取第i个元素函数用e返回，成功返回OK 否则ERROR

int LocateElem_CL(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType));//返回与e满足compare函数的元素的位序

Status PriorElem_CL(LinkList L,ElemType cur_e,ElemType *pre_e);//获取cur_e前驱函数，用 pre_e返回 成功返回TRUE 失败返回FALSE，pre_e无定义

Status NextElem_CL(LinkList L,ElemType cur_e,ElemType *next_e);//获取cur_e后继函数，用 next_e返回 成功返回TRUE 失败返回FALSE，next_e无定义

Status ListDelete_CL(LinkList *L,int i,ElemType *e);//删除第i个元素用e返回

Status ListTraverse_CL(LinkList L,void (*vi)(ElemType));//访问函数 对每个元素进行vi操作

Status DestroyList_CL(LinkList *L);

 

list.c

/******************************************************************************
               在list.h中声明函数的实现
             线性表单链表的基本操作有12个
******************************************************************************/
#include "include.h"
#include "list.h"


//-----------------------初始化函数------------------------------------------

Status InitList_CL(LinkList *L)
{//操作结果：构造一个空的线性表L

    *L=(LinkList)malloc(sizeof(LNode));// 产生头结点，并使*L指向此头结点

    if(!*L) //存储非配失败

        exit(OVERFLOW);
    (*L)->next=(*L); //指针域指向头结点

    return OK;
}

//-----------------------求L中的元素的个数----------------------------------

int ListLength_CL(LinkList L)
{//初始条件：L存在

//操作结果：返回L中元素的个数

    int i=0;
    LinkList p=L->next;//p指向头结点

    while(p!=L) //没有到表尾

    {
        i++;
        p=p->next;
    }
    return i;
}


//-----------------------插入元素函数---------------------------------------

Status ListInsert_CL(LinkList *L,int i ,ElemType e)
{//在第i个位置之前插入元素e

    LinkList p=(*L)->next,s;//p指向头结点

    int j=0;
    if(i<=0||i>ListLength_CL(*L)+1) //无法在第i个元素之前插入

        return ERROR;
    while(j<i-1)
    {
        p=p->next;
        j++;
    }
    s=(LinkList)malloc(sizeof(LNode));//生成新结点

    s->data=e; //插入新元素

    s->next=p->next;
    p->next=s;
    if(p=*L) //改变尾结点

        *L=s;
     return OK;
}

//-----------------------置空L表函数------------------------------------------

Status ClrearList_CL(LinkList *L)
{//初始条件：L存在

//操作结果：置空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; //头结点指向自身

     return OK;
}
 
//--------------------判空函数-----------------------------------

Status ListEmpty_CL(LinkList L)
{//初始条件：L存在。 操作结果：判断L是否为空,空返回TRUE,否则返回FALSE

    if(L->next==L) //空

        return TRUE;
    else
        return FALSE;    
}

//-------------------获取元素函数---------------------------------

Status GetElem_CL(LinkList L,int i,ElemType *e)
{//初始条件：L已存在且存在i元素

//操作结果：把第i个元素赋给e，成功返回OK，失败返回ERROR

     int j=1;//初始化计数器

     LinkList p=L->next->next;//p指向第一个元素

     if(i<=0||i>ListLength_CL(L)) //第i个元素不存在

         return ERROR;
     while(j<i) //向后查找直到p指向第i个元素

     {
         p=p->next;
         j++;
     }
     *e=p->data; // 取第i个元素

     return OK;
}

//-------------------------LocateElem函数------------------------

int LocateElem_CL(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{// 初始条件：线性表L已存在，compare()是数据元素判定函数。

 // 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。

 // 若这样的数据元素不存在，则返回值为0。

    int i=0;
    LinkList p=L->next->next;//指向第一个元素

    while(p!=L->next)
    {
        i++ ;
        if(compare(p->data,e)) //满足关系

            return i;
        p=p->next;
    }
    return 0;
}

//--------------------------获取前驱函数-------------------------

Status PriorElem_CL(LinkList L,ElemType cur_e,ElemType *pre_e)
{// 初始条件：L已存在

//操作结果：cur_e是L中的元素且不是第一个元素，用pre_e返回它的前驱元素，

//操作失败是pre_e无定义

    LinkList q,p=L->next->next;//p指向第一个结点

    q=p->next;// q指向p的后继

    while(q!=L->next) //向后找

    {
        if(q->data==cur_e)
        {
            *pre_e=p->data;
            return TRUE;
        }
        p=q;
        q=q->next;
    }
    return FALSE;
}

//--------------------------获取后继函数-------------------------

Status NextElem_CL(LinkList L,ElemType cur_e,ElemType *next_e)
{ // 初始条件：线性表L已存在。

   // 操作结果：若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继，

   // 否则操作失败，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;
}

//---------------------------删除函数---------------------------------------

Status ListDelete_CL(LinkList *L,int i,ElemType *e)
{//删除L中的第i个元素。并由e返回

    LinkList p=(*L)->next,q;//p指向头结点

    int j=0;
    if(i<0||i>ListLength_CL(*L)) //第i个元素不存在

        return ERROR;
    while(j<i-1)//寻找第i-1个节点

    {
        p=p->next;
        j++;
    }
    q=p->next;//q指向待删除的结点

    p->next=q->next;
    *e=q->data;
    if(*L==q)//删除元素是尾元素

        *L=p;
    free(q); //释放结点

    return OK;
}

//-------------------Traveres函数--------------------------------------------

Status ListTraverse_CL(LinkList L,void (*vi)(ElemType))
{//初始条件：L已存在

//操作结果：依次对L中的每个元素调用vi()函数，一旦vi失败则操作失败

    LinkList p=L->next->next;//p指向第一个元素

    while(p!=L->next) //没有到头结点

    {
        vi(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

//------------------------销毁函数------------------------------------------

Status DestroyList_CL(LinkList *L)
 { // 操作结果：销毁线性表L。

   LinkList q,p=(*L)->next; // p指向头结点

   while(p!=*L) // 没到表尾

   {
     q=p->next;
     free(p);
     p=q;
   }
   free(*L);
   *L=NULL;
   return OK;
}

main.c

#include "include.h"
#include "list.h"


Status compare(ElemType c1,ElemType c2)
{//判断两个数是否相等

   if(c1==c2)
     return TRUE;
   else
     return FALSE;
}

void visit(ElemType c)
{
    printf("%d ",c);
}

void main()
{
    LinkList L,p;
    Status result; //返回状态 OK TRUE ,FALSE

    int i;
    ElemType e;
    //------------------------初始化函数测试-------------------------------

    printf("初始化函数测试\n");
    //printf("初始化L前：L=%u\n",L);

    result=InitList_CL(&L);
    if(result==OK)
        printf("L初始化成功\n");
    else
        printf("L初始化失败\n");
    printf("初始化L后：L=%u\n",L);
    //---------------------------------------------------------------------

    //------------------------求L中的元素个数函数测试----------------------

    printf("求初始化后L中元素的个数\n");
    i=ListLength_CL(L);
    printf("初始化后L中元素的个数为%d\n",i);

    //---------------------------------------------------------------------

    //------------------------插入函数测试---------------------------------

    printf("向L依次插入1 3 5\n");
    result=ListInsert_CL(&L,1,1);
    result=ListInsert_CL(&L,2,3);
    result=ListInsert_CL(&L,3,5);
    printf("插入后L中的元素为：\n");
    p=L->next->next; //p指向第一个元素 (L->next是头结点)

    while(p!=L->next)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    //---------------------------------------------------------------------

    //--------------------------置空/ 判空 函数测试------------------------

    i=ListLength_CL(L);
    printf("置空前L的长度为：%d\n",i);
    printf("判断L是否为空\n");
    result=ListEmpty_CL(L);
    if(result==TRUE)
        printf("L 是一个空表\n");
    else
        printf("L 不为空\n");
    printf("置空L...\n");
    result=ClrearList_CL(&L);
    i=ListLength_CL(L);
    printf("置空后L的长度为：%d\n",i);
    result=ListEmpty_CL(L);
    if(result==TRUE)
        printf("L 是一个空表\n");
    else
        printf("L 不为空\n");

    //---------------------------------------------------------------------

    //--------------------------获取第i个元素函数测试----------------------

    printf("向L依次插入1 3 5 7 9\n");
    result=ListInsert_CL(&L,1,1);
    result=ListInsert_CL(&L,2,3);
    result=ListInsert_CL(&L,3,5);
    result=ListInsert_CL(&L,4,7);
    result=ListInsert_CL(&L,5,9);
    printf("插入后L中的元素为：\n");
    p=L->next->next; //p指向第一个元素 (L->next是头结点)

    while(p!=L->next)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    printf("获取第3个元素的值并赋给e\n");
    result=GetElem_CL(L,3,&e);
    if(result==OK)
        printf("第3个元素的值为 :%d\n",e);

    //---------------------------------------------------------------------

    //-------------------------LocateElem函数测试--------------------------

    printf("查看L中是否有与3和4相等的元素\n");
    i=LocateElem_CL(L,3,compare);
    if(i==0)
        printf("没有与3相等的元素\n");
    else
        printf("第%d个元素的值与3相等\n",i);
    i=LocateElem_CL(L,4,compare);
    if(i==0)
        printf("没有与4相等的元素\n");
    else
        printf("第%d个元素的值与4相等\n",i);
    //---------------------------------------------------------------------

    //-------------------------获取前驱函数测试----------------------------

    result=PriorElem_CL(L,3,&e);
    if(result==TRUE)
        printf("元素3的前驱元素是：%d\n",e);
    else
        printf("元素3没有前驱函数\n");

    result=PriorElem_CL(L,1,&e);
    if(result==TRUE)
        printf("元素1的前驱元素是：%d\n",e);
    else
        printf("元素1没有前驱元素\n");

    //---------------------------------------------------------------------

    //-------------------------获取后继函数测试----------------------------

    result=NextElem_CL(L,3,&e);
    if(result==TRUE)
        printf("元素3的后继元素是：%d\n",e);
    else
        printf("元素3没有后继函数\n");

    result=NextElem_CL(L,9,&e);
    if(result==TRUE)
        printf("元素9的后继元素是：%d\n",e);
    else
        printf("元素9没有前驱元素\n");

    //---------------------------------------------------------------------

    //-----------------------------删除函数测试----------------------------

    p=L->next->next; //p指向第一个元素 (L->next是头结点)

    printf("删除元素钱L中的元素值\n");
    while(p!=L->next)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    printf("删除第3个元素\n");
    result = ListDelete_CL(&L,3,&e);
    if(result==OK)
        printf("删除的第3个元素的值为：%d\n");
    else
        printf("删除失败\n");
    printf("删除后L中的元素\n");
    p=L->next->next; //p指向第一个元素 (L->next是头结点)

    printf("删除元素钱L中的元素\n");
    while(p!=L->next)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");

    //------------------------------------------------------------------------

    //----------------------------ListTraverse--------------------------------

    printf("输出L中的元素\n");
    result=ListTraverse_CL(L,visit);
    //------------------------------------------------------------------------

    //----------------------------销毁L---------------------------------------

    printf("销毁L前：L=%u\n",L);
    result=DestroyList_CL(&L);
    if(result==OK)
        printf("销毁L成功，销毁L后：L=%u\n",L);
}