C语言数据结构单链表的相关操作汇总

我就是我 2022-01-21 09:19 228阅读 0赞

/\*  
\*链表的相关操作集合  
\*链表的创建 头插法 尾插法  
\*链表元素的排序(递增排序)  
\*链表的遍历  
\*链表节点点的插入 前插 后插 在指点位置插入数据  
\*删除指点位置的节点  
\*按值进行查找 按序号进行查找  
\*/

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<time.h>
    #define OK 1
    #define ERROR 0
    typedef char*NameType;//链表节点名称的数据类型
    //static int id=0;
    typedef struct element
    {
        int id;
        NameType name;//节点的名称
    
    }ElementType;//链表节点的数据域结构体
    typedef struct linklist
    {
        ElementType data;
        struct linklist *next;//指向下一个节点点的指针
    }LinkList;//链表的数据类型
    LinkList*create_linklist();//创建单链表
    void Display_linklist(LinkList*head);//链表的遍历
    int  insert_after_linklist(LinkList*p,LinkList*s);//在p后面插入s节点
    int  insert_before_linklist(LinkList*head,LinkList*p,LinkList*s);//在指定节点的前面进行插入
    int  insert_position(LinkList*head,int i,LinkList*p);//在指定的位置进行插入
    void sort_node(LinkList*head);//对链表的节点进行排序
    int  delete_position(LinkList*head,int i );//删除指定位置的节点
    int delet_node(LinkList*head,LinkList*p);//删除指点的节点
    LinkList*search_index_linklis(LinkList*head,int i);//按序号进行查找
    LinkList*search_data_linklist(LinkList*head,ElementType key);//按值进行查找
    int length_linklist(LinkList*head);//返回链表的长度
    int dele_node(LinkList*p);//对节点后继节点进行删除
    void main()
    {
        LinkList*head;
        LinkList*r;
        LinkList*s;//在后面进行插入的节点
        LinkList*s1;//在指定位置进行插入
        int index;//要插入的位置
        ElementType str;//要查询的数据的名称
        head=create_linklist();
        if(head==NULL)
            printf("链表创建失败!\n");
          else
          {
              printf("链表创建成功！\n");
              printf("链表遍历的结果为:\n");
              Display_linklist(head);
          }
          printf("\n");
           s=(LinkList*)malloc(sizeof(LinkList));//对其进行指向操作（同下）
           s1=(LinkList*)malloc(sizeof(LinkList));//对其进行动态赋存储空间
          printf("请输入要插入节点的数据:\n");
            s->data.name=(NameType)malloc(sizeof(char)*20);
            s->next=NULL;
              scanf("%s",s->data.name);
            s->data.id=rand()%50;
            printf("输入查询的数据-名称\n");
            str.name=(NameType)malloc(sizeof(char)*20);
              scanf("%s",str.name);
              str.id=rand()%50;
             r= search_data_linklist(head,str);
             if(r==NULL)
             {
                 printf("要查询的数据没有找到:\n");
    
             }
             else
             {
                 //将节点s插入到查询到的节点的后面
                 printf("查询节点成功\n");
                  int result=insert_after_linklist(r,s);
                  if(result==0)
                  {
                      printf("插入节点失败\n");
                  }
                  else
                  {
                      printf("插入节点成功\n");
                  }
             }
             s1=(LinkList*)malloc(sizeof(LinkList));
             printf("请输入要插入节点的名称:\n");
             s1->data.name=(NameType)malloc(sizeof(char)*20);
              scanf("%s",s1->data.name);
                 s1->data.id=rand()%50;
                printf("请输入要插入的位置：\n");
                  scanf("%d",&index);
                  int result1= insert_position(head,index,s1);
                  if(result1==0)
                  {
                      printf("插入指定位置插入节点失败\n");
    
                  }
                  else
                  {
                      printf("在指定位置插入节点成功\n");
                  }
                   printf("\n");
                  printf("对查询到的节点进行删除:\n");
                 int result2=delet_node(head,r);
                  if(result2==0)
                  {
                      printf("对指定节点的删除失败:\n");
                  }
                  else
                  {
                      printf("对指定节点的删除成功:\n");
                  }
                  printf("请输入要删除的节点的位置:\n");
                  int index1;//要删除的指定节点的下标
                  scanf("%d",&index1);
                  int result3=delete_position(head,index1);
                  if(result3==0)
                  {
                      printf("删除指定位置节点失败:\n");
    
                  }
                  else
                  {
                      printf("删除指定位置节点成功：\n");
                  }
                  //printf("\n");
                  printf("链表节点的个数为:%d",length_linklist(head));
              printf("链表节点的数据排序的结果为:\n");
             sort_node(head);
             Display_linklist(head);
    }
    LinkList*create_linklist()//创建单链表
    {
        LinkList*head;
        ElementType data;
        LinkList*p;
         head=(LinkList*)malloc(sizeof(LinkList));//动态赋储存空间
        LinkList*tail;
        //尾插法创建单链表
        if(head==NULL)
        {
            printf("链表创建失败！\n");
            return NULL;
    
        }
        else
        {
            tail=head;
        }
        printf("请输入数据:\n");
        data.name=(NameType)malloc(sizeof(char)*20);
        while(1)
        {
            gets(data.name);
            p=(LinkList*)malloc(sizeof(LinkList));
            p->data.name=(NameType)malloc(sizeof(LinkList));//赋动态存储空间
             if(strcmp(data.name,"^")==0)//strcmp是在字符串之间的比较
             {
                 break;
             }
             else
                {
                 p->data.id=rand()%50;//随机时间函数 以时间为种子 产生随机数字
            strcpy(p->data.name,data.name);
                 tail->next=p;
                 tail=p;
                 p->next=NULL;//使最后一个节点的next指针为空  等价于tail->next=NULL
    
                }
             data.name=(NameType)malloc(sizeof(LinkList));
           }
        /* //头插法创建单链表
        if(head==NULL)
        {
            printf("创建单链表失败!\n");
            return NULL;
        }
        else{
            head->next=NULL;
        }
          data.name=(NameType)malloc(sizeof(char)*20);//字符串
          printf("请输入数据:\n");
          while(1)
          {    gets(data.name);
              p=(LinkList*)malloc(sizeof(LinkList));
              p->data.name=(NameType)malloc(sizeof(char)*20);//动态赋储存空间
              p->data.id=++id;
              if(strcmp(data.name,"^")==0)
                break;
              else
              {
                   strcpy(p->data.name,data.name);
                   p->next=head->next;
                   head->next=p;
                   data.name=(NameType)malloc(sizeof(char)*20);
    
              }
          }*/
    
          return head;
    }
    void Display_linklist(LinkList*head)
    {
        LinkList*p;
        p=head->next;
        if(p==NULL)
        {
            printf("链表有误，遍历失败!\n");
            return ;
        }
    
        else
        {
            printf("HEAD->");
            while(p!=NULL)
            {
                printf("[%d,%s]->",p->data.id,p->data.name);
                p=p->next;
            }
            printf("END");
        }
    }
    int   insert_after_linklist(LinkList*p,LinkList*s)//在p后面插入s节点
    {
        s->next=p->next;
        p->next=s;
        return 1;
    }
    int   insert_before_linklist(LinkList*head,LinkList*p,LinkList*s)//在指定节点的前面进行插入
    {
        if(p==head)//s想插入到head的前面的时候插入失败
        {
            return 0;
        }
        else
        {
            LinkList*q;
            q=head;
            while(q->next!=p)
            {
                q=q->next;
            }
            insert_after_linklist(q,s);//在q的后面插入s
    
        }
    }
    void sort_node(LinkList*head)//对链表的节点进行排序
    {
        //对链表节点进行递增排序
        LinkList*p,*q;
        ElementType *temp;//中间值变量
        temp=(ElementType*)malloc(sizeof(ElementType));
        for(p=head->next;p->next!=NULL;p=p->next)
            for(q=head->next;q->next!=NULL;q=q->next)
        {
            if(q->data.id>q->next->data.id)
            {
                *temp=q->data;
                q->data=q->next->data;
                q->next->data=*temp;//数值进行交换
            }
        }
    }
    LinkList*search_data_linklist(LinkList*head,ElementType key)//按值进行查找
    {
        LinkList*p;
        p=head->next;
        if(p==NULL)
        {
            return NULL;
        }
        else
        {
            while(p!=NULL)
            {
                if(strcmp(p->data.name,key.name)==0)
                {
                    break;
                }
                else
                p=p->next;
            }
            return p;//找到数据对应的节点
        }
    
    }
    int  insert_position(LinkList*head,int i,LinkList*p)//在指定的位置进行插入
    {
        LinkList*q;
        if(i<=0)//在head指针处或者前面进行插入是失败的
        {
            return 0;
    
        }
        else if(i==1)
        {
            q=head;//在head指针后面进行插入
    
        }
        else
        {
            q=search_index_linklis(head,i-1);//在i顶点下标前面进行插入 利用search函数进行查找
        }
        insert_after_linklist(q,p);
          return 1;
    }
    LinkList*search_index_linklis(LinkList*head,int i)//按序号进行查找
    {
        int j=0;
        LinkList*q;
        q=head;
        //head的位置对应的是0
        if(i<0)
        {
            return NULL;//没有找到
        }
        else
        {
            while(q->next!=NULL&&i>j)
            {
                j++;
                q=q->next;
    
            }
        }
            if(i==j)
            {
                return q;
    
            }
            else
            {
                return NULL;
            }
    }
    int dele_node(LinkList*p)//对节点后继节点进行删除
    {
        //对节点的后继节点进行删除
        LinkList*s;
        s=p->next;
        p->next=s->next;
        free(s);//对删除节点进行释放空间
        return 1;
    }
    int delet_node(LinkList*head,LinkList*p)//对指定节点进行删除
    {
        LinkList*s;
        //假如节点有后继节点的存在
        if(p->next!=NULL)//后继节点不为空
        {
            s=p->next;
            p->data=s->data;
            p->next=s->next;//将后继节点的值赋值给其要删除的节点的数据域
            return 1;
    
        }
        else
        {
            //找到节点的前继接节点
            s=head;
            while(s->next!=p)
            {
                s=s->next;
    
            }
            dele_node(s);//将s的后继节点进行删除（达到删除指定节点的目的）
              return 1;//删除成功
        }
        return 0;//删除失败
    }
    
    int  delete_position(LinkList*head,int i )//删除指定位置的节点
    {
        //对不可能的情况进行判断
        LinkList*p;
        LinkList*s;
        p=head;
        if(i<0)
    
        {
            printf("删除节点失败！\n");
            return 0;
    
    
        }
        else
        {
            //对其前继节点进行查找
            s=search_index_linklis(head,i);
            if(s==NULL)
                return 0;
            while(p->next!=s)
            {
                p=p->next;
            }
            dele_node(p);//删除后继节点即是指定位置的节点
          return 1;
          }
    
    }
    int length_linklist(LinkList*head)//返回链表的长度
    {
        //返回链表的长度(链表的长度代表链表节点的个数)
        int count=0;//计算链表的长度
        LinkList*p;
        p=head->next;//指向第一你链表数据节点
        while(p!=NULL)
        {
            count++;
            p=p->next;
    
        }
        return count;//返回链表节点的个数
    }