数据结构与算法

A-3 循环链表

菠萝猫 · 4月13日 · 2020年 130次已读

file

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
双链表:每一个节点有两个指针域
循环链表:能通过任何一个节点能找到其他所有的节点
将单链表中终端结点的指针端由空指针改为指向头结点, 就使整个
单链表形成一个环, 这种头尾相接的单链表称为单循环链表, 简称循环链表

其实循环链表和单链表的主要差异就在于循环的判断条件上, 原来是判断p->next
是否为空, 现在则是p -> next不等于头结点,则循环未结束。
*/
typedef struct Noode
{
    int data;//数据域
    struct Node * pNext;//指针域
} NODE,*PNODE; //struct Noode,struct Noode *

PNODE create_list();//创建循环链表
void traverse_list(PNODE pHead);//遍历
bool is_empty(PNODE pHead);//链表是否为空

int main()
{
    PNODE pHead = NULL;
    pHead = create_list();//创建一个循环链表
    if(is_empty(pHead))
    {
        printf("链表为空!\n");
    }
    else
    {
        printf("链表不为空!\n");
    }
    traverse_list(pHead);
    return 0;
}

PNODE create_list()
{
    int len=0;//有效节点的个数
    int i;
    int val;//用来存放用户输入的节点的值
    //1.分配了一个链表所需的头结点
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    //判断头结点是否分配了空间
    if(NULL == pHead)
    {
        printf("分配失败,程序终止!\n");
        exit(-1);
    }
    //使pTail永远指向尾节点
    PNODE pTail = pHead;
    pTail->pNext=NULL;

    //需要多少了节点
    printf("需要生成的链表节点的个数:len = ");
    scanf("%d",&len);
    //循环输入各节点的data,形成链表
    for(i=0; i<len; i++)
    {
        printf("请输入第%d个节点的值:",i+1);
        scanf("%d",&val);
        //生成一个新的节点,存放data,连接链表
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if(NULL == pNew)
        {
            printf("分配失败,程序终止!\n");
            exit(-1);
        }
        pNew->data=val;
        pTail->pNext = pNew;
        pNew->pNext=pHead;//最后的指针指向头结点
        pTail=pNew;
    }
    return pHead;
}
void traverse_list(PNODE pHead)
{
    PNODE p = pHead->pNext;
    while(p!=pHead)
    {
        printf("%d ",p->data);
        p = p->pNext;
    }
    printf("\n");
}

bool is_empty(PNODE pHead)
{
    if(pHead->pNext==NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

```


版权声明:本站采用 “知识共享署名 – 非商业性使用 – 相同方式共享 4.0 中国大陆许可协议” 进行许可,您可以转载本站文章,转载时请以超链接形式标明文章原始出处,Thanks.


0 条回应