双向循环链表实现(c语言）

蔚落 2022-04-03 02:56 240阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    typedef int ElemType;
    typedef struct node
    {
    
        ElemType data;
        struct node*next;
        struct node*rear;
    }*linkList,linkNode;
    
    //链表初始化
    linkList initLinkList()
    {
        linkList head=(linkList)malloc(sizeof(linkNode));
        if(!head)
        {
            printf("动态内存分配失败!\n");
            exit(0);
        }
        head->next=head;
        head->rear=head;
    
        printf("链表初始化成功!\n");
        return head;
    }
    //头插法建立链表
    void creatLinkList(linkList l,int a[],int n)
    {
        int i;
        linkList p,q;
        q=l;
        for(i=0; i<n; i++)
        {
            p=(linkList)malloc(sizeof(linkNode));
            p->data=a[i];
            p->next=q->next;
            q->next->rear=p;
    
            q->next=p;
            p->rear=q;
            q=p;
    
        }
        q->next=l;
        l->rear=q;
    
    
        printf("链表建立成功!\n");
    }
    //打印链表
    void printLinkListRear(linkList head)
    {
        linkList p=head->rear;
        printf("反向打印链表:\n");
        while(p!=head)
        {
            printf("%d ",p->data);
            p=p->rear;
        }
        printf("\n");
    }
    //打印链表
    void printLinkListNext(linkList head)
    {
        linkList p=head->next;
        printf("正向打印链表:\n");
        while(p!=head)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
    }
    //查找链表元素下标
    int linkListFind(linkList head,int data)
    {
        linkList p=head->next;
        int i=0;
        while(p!=head)
        {
            i++;
            if(p->data==data)
                return i;
    
            p=p->next;
        }
        return 0;
    }
    //链表插入
    int linkListInsert(linkList head,int data1,int data2)
    {
        linkList p=head->next,q;
        while(p!=head)
        {
            if(p->data==data1)
            {
                q=(linkList)malloc(sizeof(linkNode));
                q->data=data2;
                q->next=p->next;
                p->next->rear=q;
                p->next=q;
                q->rear=p;
                return 1;
            }
            p=p->next;
        }
        return 0;
    }
    //链表删除
    int linkListDelete(linkList head,int data)
    {
        linkList p=head,q;
        while(p->next!=head)
        {
    
            if(p->next->data==data)
            {
                q=p->next;
                p->next=q->next;
                q->next->rear=p;
                free(q);
                return 1;
            }
            p=p->next;
    
        }
        return 0;
    }
    //判断链表是否为空
    int isEmpty(linkList head)
    {
        if(head->next==head)
        {
            return 1;
        }
        return 0;
    }
    //清空链表
    int linkListClear(linkList head)
    {
        if(head->next!=head)
        {
            head->next=head;
            return 1;
        }
        return 0;
    
    }//销毁链表
    int linkListDestory(linkList head)
    {
        if(head)
        {
            linkList p=head->next,q;
            while(p!=head)
            {
                q=p->next;
                free(p);
                p=q;
    
            }
            free(head);
            return 1;
        }
        return 0;
    
    }
    //求链表长度
    int linkListLength(linkList head)
    {
          int i=0;
          linkList p=head->next;
          while(p!=head)
          {
                i++;
                p=p->next;
          }
          return i;
    }
    //求结点后继
    int nextElem(linkList head,ElemType e)
    {
          linkList p=head->next;
          while(p!=head)
          {
                if(p->data==e)
                {
                      if(p->next!=head)
                            return p->next->data;
                      else
                            return head->next->data;
                }
                p=p->next;
          }
          return 0;
    }
    
    //求结点前趋
    int priorElem(linkList head,ElemType e)
    {
          linkList p=head;
    
          while(p->next!=head)
          {
                if(p->next->data==e)
                {
                      if(p!=head)
    
                            return p->data;
    
                }
    
    
                p=p->next;
          }
             if(head->next->data==e)
                {
                      return p->data;
                }
    
          return 0;
    }
    //获取第index个元素
    int getElem(linkList head,int index)
    {
          linkList p=head->next;
          int i=0;
          while(p!=head)
          {
                i++;
                if(i==index)
                {
                      return p->data;
                }
                p=p->next;
          }
          return 0;
    
    }
    
    int main()
    {
        linkList head=initLinkList();
        int length;
        if(isEmpty(head))
        {
              length=linkListLength(head);
            printf("当前链表为空表,长度为%d\n",length);
        }
    
        int n,a[100],i;
        printf("请输入数字n:\n");
        scanf("%d",&n);
        printf("请输入%d个数字建立链表:\n",n);
        for(i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
        }
        creatLinkList(head,a,n);
        printLinkListNext(head);
        printLinkListRear(head);
        int insertNum,newNode;
        printf("请输入要插入的位置的结点和插入的结点:\n");
        scanf("%d %d",&insertNum,&newNode);
        if(linkListInsert(head,insertNum,newNode))
        {
            printf("插入成功!\n");
            printLinkListNext(head);
             printLinkListRear(head);
        }
        else
        {
            printf("插入失败!\n");
        }
        int deleteNum;
        printf("请输入要删除的结点:\n");
        scanf("%d",&deleteNum);
        if( linkListDelete(head,deleteNum))
        {
            printf("删除成功!\n");
            printLinkListNext(head);
             printLinkListRear(head);
        }
        else
        {
    
            printf("删除失败!\n");
        }
        int findNum,index,k1,no;
        printf("请输入要查找的元素:\n");
        scanf("%d",&findNum);
        if(index=linkListFind(head,findNum))
        {
            printf("查找成功,这是第%d个元素\n",index);
        }
        else
        {
            printf("查找失败!\n");
        }
        if(k1=priorElem(head,findNum))
        {
    
                    printf("%d的前趋为%d\n",findNum,k1);
    
        }
        else
        {
              printf("未找到该元素!\n");
        }
        if(k1=nextElem(head,findNum))
        {
    
                    printf("%d的后继为%d\n",findNum,k1);
    
    
        }
        else
        {
              printf("未找到该元素!\n");
        }
        printf("请输入下标:\n");
    
        scanf("%d",&no);
        if(k1=getElem(head,no))
        {
              printf("第%d个元素为%d\n",no,k1);
        }
        else
        {
    
              printf("下标输入错误\n");
        }
    
        /* if(linkListClear(head))
         {
               printf("链表已经清空!\n");
               printLinkList(head);
         }*/
         if(linkListDestory(head))
         {
               printf("链表销毁成功!\n");
               //printLinkList(head);
         }
    
    
    
        return 0;
    }