循环单链表(C语言实现)

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h> 
typedef int DataType;
typedef struct Node
{
    DataType data;        //    数据域 
    struct Node * next;    //    指针域 
        
}LinkList;

LinkList* Init_List();            //    链表初始化 
bool Creat_List(LinkList * L);    //    创建链表 
int Length_List(LinkList * L);    //    链表长度 
bool Empty_List(LinkList * L);    //    判空 
bool Insert_List(LinkList * L, int pos, DataType x);    //    插入元素 
bool Delete_List(LinkList * L, int pos, DataType * x);    //    删除元素 
bool Destroy_List(LinkList * L);    //    销毁链表 
bool Traverse_List(LinkList * L);    //    遍历链表 

int main()
{
    DataType x;
    
    LinkList * L = Init_List();
    if(Creat_List(L))
        printf("循环单链表构造成功!\n");
    else
        printf("循环单链表构造失败!\n");
    printf("遍历链表:");
    Traverse_List(L);
    
    printf("循环单链表结点个数:%d\n\n", Length_List(L));
    
    if(Insert_List(L, 2, 5))
    {
        printf("插入成功\n");
        printf("插入结点:第2个结点\n");
        printf("插入元素:5");
    }
    else
        printf("插入失败\n");
    printf("\n遍历链表:");
    Traverse_List(L);
    
    if(Delete_List(L, 3, &x))
    {
        printf("删除成功\n");
        printf("删除结点:第3个结点\n");
        printf("删除元素:%d\n",x);
    }
    else
        printf("删除失败\n");
    
    printf("遍历链表:");
    Traverse_List(L);
    
    if(Destroy_List(L))
        printf("销毁成功!\n");
    else
        printf("销毁失败!\n");

    return 0; 

LinkList* Init_List()
{
    LinkList * L = (LinkList *)malloc(sizeof(LinkList));    //    创建头结点,返回头结点的地址给主函数 
    if(!L)
    {
        printf("申请空间失败!\n");
        exit(-1);
    }
    
    L->next = L;    //    头结点指针域指向自身时,则为空表 
    return L;         //    返回头结点的地址 
}

bool Creat_List(LinkList * L)
{
    int i,n,val;
    LinkList * p = L;    //    保证L始终指向头结点 
    
    printf("请输入循环单链表的结点个数:");
    scanf("%d",&n);
    
    for(i=0; i<n; ++i)
    {
        printf("第%d个结点:",i+1);
        scanf("%d",&val);
        LinkList * q = (LinkList*)malloc(sizeof(LinkList));
        q->data = val;
        p->next = q;
        p = q;
    }
    
    p->next = L;    //    循环单链表:保证最后一个结点的指针域指向头结点 
    return true;
}

int Length_List(LinkList * L)
{
    int len = 0;
    LinkList * q = L->next;
     
    while(q!=L)
    {
        len++;
        q = q->next;
    }
    
    return len;
}

bool Empty_List(LinkList * L)
{
    if(L->next==L)
        return true;
    else
        return false;
}

bool Insert_List(LinkList * L, int pos, DataType x)
{
    int i = 1;
    LinkList * p = L->next;
    
    if(pos<1||pos>Length_List(L))
        return false;
    
    while(i<pos-1&&L!=p)    //    指针移动到被插入结点的前一个结点 
    {
        i++;
        p = p->next;
    }
    
    LinkList * q = (LinkList*)malloc(sizeof(LinkList));
    q->data = x;
    q->next = p->next;
    p->next = q;
    return true;
}

bool Delete_List(LinkList * L, int pos, DataType * x)
{
    int i = 1;
    LinkList * p = L->next;
    
    if(pos<1||pos>Length_List(L))
        return false;
    
    while(i<pos-1&&L!=p)    //    指针移动到被删除结点的前一个结点 
    {
        i++;
        p = p->next;
    }
    
    LinkList * q = p->next;
    *x = q->data;
    p->next = q->next;
    free(q);
    return true;
}

bool Destroy_List(LinkList * L)
{
    /*
        将循环单链表变成单链表: 
                            空表时,头结点的指针域是指向其本身 
                            销毁时,头结点的指针域为空 
    */
    LinkList * p = L->next;        
    L->next = NULL;    
    
    while(p)
    {
        LinkList * q = p->next;
        free(p);
        p = q;
    }
    
    return true;
}

bool Traverse_List(LinkList * L)
{
    if(Empty_List(L))
        return false;
         
    LinkList * p = L->next;
    
    while(p!=L)
    {
        printf("%3d",p->data);
        p = p->next;
    }
    
    printf("\n\n");
}

循环单链表(C语言实现)

 

 

上一篇:单链表的构建、遍历、带头结点与不带头结点的插入


下一篇:1.3求la,lb两个递增链表的交集链表,并存放在la链中