[学习笔记]循环链表

前面复习了单链表,接着复习循环链表.这里以单链表做示范.

什么是循环链表呢?一般的链表中尾结点的next指向的是NULL值,如果我们现在指向最后一个结点,当我们需要指向第一个结点时就只有重新从头结点开始,浪费了时间,现在我们把尾结点的next指向头结点,这样EndNode->next就是FirstNode的地址了不是?这就叫循环链表.

<<大话>>中说循环链表中不用头指针了,改为尾指针,即它的next值指向尾结点而非头结点.这样Header->next->next就是头结点了,确实很方便,但是依旧用头指针可以吗?我们首先来看下,如果头指针依旧指向头结点,那么我们会发现,如果我们在一个链表处插入一个新的头结点,那么按照循环链表的定义来说,我们应该让尾结点指向这个新的头结点,但是问题出来了,尾结点的内存地址是多少呢?不知道.同样的,如果删除头结点也会出现这个问题.因此,循环链表不用头指针而改用尾指针就解决了这个问题.这也是我自己在练习的时候发现的,困扰我的问题也就迎刃而解了.

当然,循环链表属于链表的子类,依旧有遍历,整表创建,整表删除,插入,删除,查找操作.以下是相关代码:

链表结构:

typedef struct Node{
    char Data;
    struct Node *next;
}Node;
typedef struct Node *List;

1.整表插入

BOOL CreateCircularList(List *L,int Length)//循环列表的整表创建
{
    List EndNode,NewEndNode,FirstNode;
    int temp;
    char Chart='a';

    *L=(List)malloc(sizeof(Node));//为尾指针分配内存 
    if(!(*L))
        return false;
    EndNode=*L;
    for(temp=0;temp<Length;temp++,Chart++)
    {
        NewEndNode=(List)malloc(sizeof(Node));//为新的尾结点分配内存 
        if(!NewEndNode)
            return false;
        NewEndNode->Data=Chart;//为新的尾结点赋予相应的值 
        EndNode->next=NewEndNode;//旧的尾结点的next指向新的尾结点的地址
        EndNode=NewEndNode;//把EndNode后移一位 
        if(0==temp) //保存头结点的信息 
            FirstNode=EndNode;
    }
    EndNode->next=FirstNode;//尾结点的next指向头结点 
    (*L)->next=EndNode;//尾指针的next指向尾结点
    (*L)->Data=temp;//保存链表的长度

    return true; 
}

2.整表删除

BOOL EmptyCircularList(List *L)//循环链表的整表删除
{
    List DeleteNode,EndNode;
    int temp;

    if(0==(*L)->Data)
        return false;//当循环链表为空时,返回false

    EndNode=(*L)->next;//取得尾结点的地址

    for(temp=1;temp<(int)((*L)->Data);temp++)//从首节点开始删除,一直到尾结点的前一个结点
    {
        DeleteNode=EndNode->next;//取得要删除的结点(即头结点)
        EndNode->next=DeleteNode->next;//把头结点的next结点改为新的头结点
        free(DeleteNode);//释放旧的头结点的内存
    }

    free(EndNode);//释放尾结点的内存
    (*L)->next=NULL;//头指针指向NULL
    (*L)->Data=0;//链表长度改为0
    
    return true;
}

3.插入操作

BOOL InsertDataCircularList(List *L,int InsertLocation,char InsertData)
{
    List InsertNodePre,InsertNode;
    int temp;

    if(InsertLocation<1)//如果插入的位置小于1,则默认新插入的数据为首结点
        InsertLocation=1;
    if(InsertLocation>((int)(*L)->Data))//如果插入的位置大于链表的长度,则默认新插入的位数为尾结点
        InsertLocation=(*L)->Data;

    InsertNodePre=*L;//将将新增结点的前一个结点设为头指针,原因见删除结点操作的该语句
    for(temp=0;temp<InsertLocation;temp++)//将InsertNodePre指向欲新增的结点的前一个结点
    {
        InsertNodePre=InsertNodePre->next;//结点后移一位
    }

    InsertNode=(List)malloc(sizeof(Node));//为要插入的结点分配内存
    if(!InsertNode)
        return false;
    InsertNode->Data=InsertData;//给插入的结点的数据域赋值
    InsertNode->next=InsertNodePre->next;//指定要插入的结点next值
    InsertNodePre->next=InsertNode;//将要插入的结点的前一个结点的next指向这个插入的结点

    if((*L)->Data==temp+1)//如果这个新插入的结点为新的尾结点,则更新尾指针的next值
        (*L)->next=InsertNode;
    (*L)->Data++;//链表的长度加1

    return true;
}

4.删除操作

BOOL DeleteDataCircularList(List *L,int DeleteLocation,char *OutputDeleteValue)
{
    int temp;
    List DeleteNodePre,DeleteNode,DeleteNodeNext;

    if(DeleteLocation<1)//如果删除的位置小于1,则将删除位置设为头结点
        DeleteLocation=1;
    if(DeleteLocation>((int)(*L)->Data))//如果删除的位置大于链表长度,则将删除位置设置为尾结点
        DeleteLocation=((int)(*L)->Data);

    DeleteNodePre=*L;//首先将结点首先设置为头指针,为什么是头指针而不是头结点或者尾结点呢,因为如果是头结点下面的for循环的话就是删除正确的删除结点后的第2个结点了,而如果设为尾结点的话则是正确的删除结点后的那个结点
    
    for(temp=0;temp<DeleteLocation;temp++)//将结点位置设置为与删除的前一个结点
    {
        DeleteNodePre=DeleteNodePre->next;//结点后移一位
    }

    DeleteNode=DeleteNodePre->next;
    DeleteNodeNext=DeleteNode->next;
    DeleteNodePre->next=DeleteNodeNext;
    *OutputDeleteValue=DeleteNode->Data;
    free(DeleteNode);//释放欲删除结点的内存

    if(temp==((int)(*L)->Data))//如果删除的节点是尾结点,那么我们让尾指针指向新的尾结点
        (*L)->next=DeleteNodePre;
    (*L)->Data--;//链表的结点数减去1

    return true;
}

5.遍历链表

BOOL LookUpCircularList(List L)
{
    List CurrentNode;
    int count=1;

    if(0==L->Data)//如果链表为空,返回错误
        return false;
    CurrentNode=L->next->next;//当前结点指向链表头结点
    while((L->next)!=CurrentNode)//不断输出当前结点的数据域的值
    {
        printf("%3c",CurrentNode->Data);
        if(0==count%6)
            printf("\n");
        CurrentNode=CurrentNode->next;//结点后移
        count++;
    }
    printf("%3c\n",CurrentNode->Data);//输出尾结点的值

    return true;
}

然后用一个小程序跑一下,以下是代码:

int main(void)
{

List Cl;
char InsertData,DeleteData;
int InsertPosition,DeletePosition;

if(true==CreateCircularList(&Cl,26))
    printf("循环链表创建成功!");
else
    return false;
printf("现在链表数据如下:\n");
LookUpCircularList(Cl);
printf("请输入要插入的字符:");
scanf("%c",&InsertData);
fflush(stdin);
printf("请输入要插入的位置:");
scanf("%d",&InsertPosition);
if(true==InsertDataCircularList(&Cl,InsertPosition,InsertData))
    printf("插入数据成功!插入的字符为%c,",InsertData);
else
    return false;
printf("新的链表数据如下:\n");
LookUpCircularList(Cl);
printf("请输入要删除的数据的位置:");
if(1==scanf("%d",&DeletePosition))
    DeleteDataCircularList(&Cl,DeletePosition,&DeleteData);
else
    return false;
printf("删除数据成功!删除的字符为:%c\n",DeleteData);
fflush(stdin);
printf("是否清空链表?1代表清空,0代表不清空:");
scanf("%d",&DeletePosition);
if(1==DeletePosition)
{
    if(true==EmptyCircularList(&Cl))
        printf("清空数据成功!现在链表长度为%d\n",Cl->Data);
}
else
    printf("数据未清空!链表长度为%d\n",Cl->Data);
fflush(stdin);
getchar();
return 0;

}

运行结果

Capture.PNG

当然,有了循环链表,还有双向链表,时间不早了,明天再回顾