两个单链表的合并及求相同集合

2018-06-10 本文已影响0人乔落_fe6f

两个单链表的合并及求相同集合

1.定义

 #include<stdio.h> 
 #include<stdlib.h>
 #define OK 1
 #define ERROR 0
 typedef int ElemType;
 typedef int Status;
 typedef struct Node//单链表节点
 {
    ElemType element;
    struct Node *link;
 }Node;
 typedef struct//链表
 {
    struct Node *first;
    int n;
 }SingleList;//单链表
 Status Init(SingleList *L);//初始化
 Status Find(SingleList L, int i, ElemType *x);//查找
 Status Insert(SingleList *L, int i, ElemType x);//插入
 Status Delete(SingleList *L, int i);//删除
 Status Bubble_sort(SingleList L);//有序递增排序
 Status Get_Interserction(SingleList L, SingleList H, int* same);
 //两单链表的交集
Status Output(SingleList L);//输出
Status Destoroy(SingleList *L);//撤销

2.初始化

 Status Init(SingleList *L)//链表初始化
 {
   L->first = NULL;
   L->n = 0;
   return OK；
 }

3.查找

 Status Find(SingleListL,int i,ElemType *x)//查找
 {
   if (i<0||i>L.n-1)//判断i是否越界
     {
           return ERROR;
     }
   Node *p;
   int j;
   p = L.first;
   for (j=0;j<i;j++)
    {
          p = p->link;
    }
   *x = p->element;
    return OK;
 }

4.插入

  Status Insert(SingleList *L, int i, ElemType x)//插入
   {
     if (i<-1 || i>L->n - 1)//判断i是否越界
       {
           return ERROR;
       }
     Node *p,*q;
     int j;
     p = L->first;
     for (j = 0; j<i; j++)
       {
           p = p->link;
       }
     q = (Node*)malloc(sizeof(Node));//申请空间
     q->element = x;
     if (i > -1)
       {
          q->link = p->link;
          p->link = q;
       }
     else
       {
          q->link = L->first;
          L->first = q;
       }
     L->n++;
     return OK;
   }

5.删除

Status Delete(SingleList *L, int i)//删除节点
 {
   if (!L->n)//判断单链表是否为空
     {
         return ERROR;
     }
   if (i<0 || i>L->n - 1)//判断i是否越界
    {
         return ERROR;
    }
   int j;
   Node *p, *q;
   if (i ==0)//删除为头节点
    {
       q = L->first->link;
       free(L->first);
       L->first = q;
    }
   else
   {
      q = L->first;
      p = L->first;
      for (j = 0; j < i - 1; i++)
       {
           q = p->link;
       }
      p = q->link;
      q->link = p->link;
      free(p);
   }
   L->n--;
  return OK;
 }

5.排序

   Status Bubble_sort(SingleList L)//冒泡排序法
   {
          if (!L.n)//判断单链表是否为空
               {
                    return ERROR;
                }
          Node *p;
          for (int i = 0; i < L.n-1; i++)
         {
              p = L.first;
                 for (int j=0;j<L.n-1;j++)
                      {
                          int temp;
                           if (p->element > p->link->element)
                                 {
                                   temp = p->element;
                                   p->element = p->link->element;
                                   p->link->element = temp;
                                }
                            p = p->link;
                          }
           }
          return OK;
      }

6.获取相同集合

    Status Get_Interserction(SingleList L, SingleList H,int *same)//获取
    {
        if (!L.n||!H.n)//判断两个单链表是否为空
          {
            return ERROR;
          }
        Node *p, *q;
        int k = 0;
        p = L.first;
       for (int j = 0; j < L.n; j++)
        {
         q = H.first;
         for (int i = 0; i < H.n; i++)
         {
           if (p->element == q->element)
           {
              same[k] = p->element;
              k++;
           }
           q = q->link;
         }
         p = p->link;
        }
         return k;
    }

7.输出

   Status Output(SingleList L)//输出链表
  {
    if (!L.n)//判断单链表是否为空
    {
      return ERROR;
    }
    Node *p;
    p = L.first;
    for (int i = 0; i < L.n; i++)
      {
         printf(" %d",p->element);
         p = p->link;
      }
     return OK;
  }

8.撤销

    Status Destroy(SingleList *L)//撤销单链表
     {
       if (!L->n)//判断单链表是否为空
           {
            return ERROR;
           }
      Node *p;
      for (int i = 0; i < L->n - 1; i++)
         {
           p = L->first->link;
           free(L->first);
           L->first = p;
         }
       return OK;
     }

9.主函数

   int main()
    {
      printf("链表L\n");
      SingleList L;
      if (Init(&L))
         {
           printf("初始化成功!\n");
           int x;
           printf("请输入单链表L的数据,以‘-1’结束\n");
           for (int i = 0;; i++)
             {
               scanf_s("%d", &x);
               if (x == -1)
                 {
                   break;
                 }
               Insert(&L, i - 1, x);
             }
           Bubble_sort(L);
         }
      else
        {
        printf("初始化失败!\n");
        }
      printf("链表H\n");
      SingleList H;
      if (Init(&H))
     {
    printf("初始化成功!\n");
    int x;
    printf("请输入单链表H的数据,以‘-1’结束\n");
    for (int i = 0;; i++)
    {
        scanf_s("%d", &x);
        if (x == -1)
        {
            break;
        }
        Insert(&H, i - 1, x);
    }
    Bubble_sort(H);
}
else
{
    printf("初始化失败!\n");
}
system("CLS");
printf("链表L\n");
Output(L);
printf("\n");
printf("链表H\n");
Output(H);
printf("\n");
printf("合并单链表L和H形成G链表\n");
SingleList G;
if (Init(&G))
{
    printf("初始化成功!\n");
    for (int i = 0; i < L.n + H.n; i++)
    {
        Insert(&G, i - 1, 0);
    }
    Node *p1, *p2, *p3;
    p1 = G.first;
    p2 = L.first;
    p3 = H.first;
    for (int i = 0; i < L.n; i++)
    {
        p1->element = p2->element;
        p1 = p1->link;
        p2 = p2->link;
    }
    for (int j = 0; j < H.n; j++)
    {
        p1->element = p3->element;
        p1 = p1->link;
        p3 = p3->link;
    }
    /*
    另一种合并两单链表的方法
    for (int i = 0; i <L.n; i++)
    {
    Insert(&G, i-1,p2->element);
    p2 = p2->link;
    }
    for (int i = 0; i < H.n; i++)
    {
    Insert(&G, i+L.n- 1, p3->element);
    p3 = p3->link;
    }
    */
    Bubble_sort(G);
    printf("链表G:\n");
    Output(G);
    printf("\n");
}
else
{
    printf("初始化失败!\n");
}
printf("链表L和H的交集:\n");
int *same = new int[100];
int k=Get_Interserction(L,H,same);
for(int i=0;i<k;i++)
{
    printf(" %d", same[i]);
}
printf("\n");
    }

10.运行结果

TIM图片20180610094452.png

TIM图片20180610094501.png

TIM图片20180610094506.png

两个单链表的合并及求相同集合

两个单链表的合并及求相同集合

猜你喜欢

热点阅读