一、线性表基础13题

1.线性表的建立

1、定义顺序表存储结构

2、初始化顺序表为空（InitList_Sq）

3、输入顺序表数据（CreateList_Sq）

4、遍历（输出）顺序表数据（TraverseList_Sq）

5、销毁顺序表数据（DestroyList_Sq）

例如：

输入元素个数和数据如下：

5 3 8 7 9

程序输出为：

5,3,8,7,9

#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100
typedef struct
{
    int *elem;
    int length;
}SqList;
SqList InitList_Sq(SqList L)
{
   L.elem=(int *) malloc(100* sizeof(int));
   L.length=0;
   return L;
}
SqList CreateList_Sq(SqList L)
{
    int a;
    scanf("%d",&a);
    for(int i=0;i<a;i++)
    {
        int b;
        scanf("%d",&b);
        L.elem[i]=b;
        L.length++;
    }
    return L;
}
SqList TraverseList_Sq(SqList L)
{
    for(int i=0;i<L.length;i++)
    {
        if(i<L.length-1)
        {
            printf("%d,",L.elem[i]);
        }
        else
        {
            printf("%d",L.elem[i]);
        }
    }
}
SqList DestroyList_Sq(SqList L)
{
    L.length=0;
    free(L.elem);
    return L;
}
int main()
{
    SqList L;
    L=InitList_Sq(L);
    L=CreateList_Sq(L);
    TraverseList_Sq(L);
    L=DestroyList_Sq(L);
    return 0;
}

2.单链表的建立-前插法

1、定义单链表存储结构

2、初始化一个空的单链表L（InitList_L）

3、用前插法创建单链表数据（CreateList_F）

4、遍历（输出）单链表表数据（TraverseList_L）

5、销毁单链表表数据（DestroyList_L）

例如：

输入单链表结点个数和数据如下：

9 7 8 3 5

程序输出为：

5,3,8,7,9

# include <stdio.h>
# include <stdlib.h>
typedef struct Lnode{
    int data;
    struct Lnode *next;
}Lnode;
void InitList_L(Lnode * L)
{
//  Lnode *p;
    //   L =(Lnode *) malloc (sizeof(Lnode)) ;
       L->next=NULL;
} 
    int CreateList_F(Lnode * L,int n)
{
    Lnode * p ;
   p=L;
    for(int i=0;i<n;i++)
  { 
  Lnode * s=(Lnode *) malloc (sizeof(Lnode));
   scanf("%d", & (s->data));
        s -> next = p -> next;
    p -> next = s ;
     }   
}
     int  TraverseList_L (Lnode*L,int n)
     {
         Lnode *p;
         Lnode *q;
         q=L;
         p=q->next;
         while(p!=NULL)
         {
          if(p->next!=NULL)
             printf("%d,",p->data);
             if(p->next==NULL)
             {
              printf("%d",p->data);
       }
             p=p->next;
         }
     }
            int DestroyList_L(Lnode *  L)
{
    Lnode * p;
    p=L->next;
    Lnode * q;
      while(p!=NULL)
{
    q=p;
    free (q);
    p=p->next;
}
}
int main(void)
{
    int n;
    scanf("%d",&n);
          Lnode*L;
          InitList_L(L);
          CreateList_F (L,n);
          TraverseList_L(L,n);
          DestroyList_L(L);
          return 0;
}

3.单链表的建立-后插法

1、定义单链表存储结构

2、初始化一个空的单链表L（InitList_L）

3、用后插法创建单链表数据（CreateList_L）

4、遍历单链表表数据（TraverseList_L）

5、销毁单链表表数据（DestroyList_L）例如：

输入元素个数和数据如下：

5 3 8 7 9

程序输出为：

5,3,8,7,9

#include <stdio.h>
# include <stdlib.h>
#define  MAXSIZE 100  
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct LNode {
  ElemType data; //结点的数据域
  struct LNode *next; //结点的指针域
} LNode, *LinkList; //LinkList为指向结构体LNode的指针类型
void InitList_L(LinkList L) 
{ 
  L->next = NULL; 
}
Status CreateList_L(LinkList L,int n)
{
    LinkList p;
    L->next=NULL;
    p=L;
    for(int i=0;i<n;i++)
    {
       LinkList s =(LinkList)malloc(sizeof(LNode));
        scanf("%d",&s->data);
        s->next=NULL;
       p->next=s;
       p=s;
    }
}
void TraverseList_L(LinkList L,int n) 
//依次输出单链表里的每个元素
{ int i = 0;
  LNode *p;
  p = L->next;
  while (p)
  {
        if(p->next!=NULL)
             printf("%d,",p->data);
             if(p->next==NULL)
             {
              printf("%d",p->data);
       }
             p=p->next;
  }
} 
Status DestroyList_L(LinkList  L)
{
    LinkList p ;
    LinkList q;
    p=L->next;  
       while(p)
        {
            q=p;
           p=p->next;
        free (q) ;  
        }
 }
int main()
{
  LinkList  L;             
  int n;
  InitList_L(L);
scanf("%d",&n);
CreateList_L(L,n);
  TraverseList_L(L,n);
  DestroyList_L(L);
  return 0;
}

4.顺序表的插入

1、定义插入函数（ListInsert_Sq）

2、在主函数中遍历输出插入前线性表中的元素

3、在主函数中输入插入元素的位置和数据信息

4、显示插入后的顺序表数据信息（TraverseList_Sq）

例如：

输入元素个数和数据如下：

5 3 8 7 9

插入元素的位置和值为：

程序输出为：

5,3,8,7,9 //在输入插入位置和值之前遍历输出的线性表中的数据元素

5,6,3,8,7,9

#include <stdio.h>
#include<stdlib.h>
#define  MAXSIZE 100  
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef  struct {
      ElemType  *elem;                                   //指向数据元素的基地址
      int  length;                                              //线性表的当前长度                                                   
 }SqList;
Status InitList_Sq(SqList *L)
{      //构造一个空的顺序表L
      L->elem=(ElemType*)malloc(sizeof(MAXSIZE));      //为顺序表分配空间
      if(!L->elem) exit(OVERFLOW);               //存储分配失败
      L->length=0;                                       //空表长度为0
      return OK;
}
void CreateList_Sq(SqList *L,int n)
{
  if(n<0||n>MAXSIZE){
      return ;
  }
  for(int i=0;i<n;i++){
      scanf("%d",&L->elem[i]);
      L->length++;
  }
}
//在此处定义顺序表插入函数ListInsert_Sq
void ListInsert_Sq(SqList *L,int m,int e){
    if(m<1||m>=L->length){
        return ;
    }
    for(int j=L->length;j>=m-1;j--){
        L->elem[j+1]=L->elem[j];
    }
    ++L->length;
    L->elem[m-1]=e;
}
void TraverseList_Sq(SqList *L)
{
    for(int i=0;i<L->length;i++){
        printf("%d",L->elem[i]);
        if(i!=L->length-1)
        {
            printf(",");
        }
    }
}
void DestroyList_Sq(SqList *L)
{
   free(L);    //释放存储空间
}
int main()
{
  SqList L;                            
  int i,n,e;
  InitList_Sq(&L);
        //提示：输入元素个数：
  scanf("%d",&n);
  CreateList_Sq(&L,n);
  TraverseList_Sq(&L);          //遍历输出插入前线性表数据元素
  //提示：在顺序表中输入新元素插入的位置和数据：
    int m;
    scanf("%d %d",&m,&e);
        //在此处编写 ListInsert_Sq函数的调用语句
    ListInsert_Sq(&L,m,e);
    printf("\n");
  TraverseList_Sq(&L);
          //  DestroyList_Sq(&L);
  return 0;
}

5.顺序表的查找—按序号进行查找

1、定义按序查找函数（GetElem_Sq）

2、在主函数中遍历输出查找之前线性表中的元素

2、在主函数中输入待查元素在顺序表中的位序

3、显示查找后的数据

例如：输入顺序表元素个数和数据如下：

5 3 8 7 9

输入查找元素的位序为：

程序输出结果为：

5,3,8,7,9 //在调用查找函数之前遍历输出的线性表中的数据元素

3 //输出的待查元素的位序

#include <stdio.h>
#include<stdlib.h>
#define  MAXSIZE 100  
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef  struct {
  ElemType  *elem;     //指向数据元素的基地址
  int  length;                  //线性表的当前长度                                                     
 }SqList;
Status InitList_Sq(SqList *L)
{   
     L->elem=(int*) malloc (4*100);    //为顺序表分配空间
     if(! L-> elem) exit(OVERFLOW);           //存储分配失败
    L-> length=0;                                //空表长度为0
    return OK;
}
Status CreateList_Sq(SqList *L,int n)
{
for(int i=0;i<n;i++)
{
    scanf("%d",&L->elem[i]);
}
}
void TraverseList_Sq(SqList *L,int n)
{
  for(int k=0;k<n;k++){
        if(k==0){
            printf("%d",L->elem[k]);
        }
        if(k!=0){
        printf(",%d",L->elem[k]);
        }
    }
}
Status GetElem_Sq(SqList *L,int n)
{
    for(int i=0;i<n;i++)
    {
        if(i=n-1)
   printf("%d",L->elem[i]);
    }
}
void DestroyList_Sq(SqList *L)
{
    if(L->elem)
    free(L->elem);
}
int main()
{
  SqList L;             
  int i,n;
  ElemType e;
  InitList_Sq(&L);
  //提示:请输入元素个数：
scanf("%d",&n);
  CreateList_Sq(&L,n);
  TraverseList_Sq(&L,n);
  //提示：请输入想要获取的元素位序：";
printf("\n");
scanf("%d",&i);
  //在此处调用按序查找函数GetElem_Sq
GetElem_Sq(&L,i);
DestroyList_Sq(&L);
  return 0;
}

6.顺序表的查找—按值进行查找

1、定义按值查找函数（LocateELem_Sq）

2、在主函数中遍历输出查找前线性表中的元素

3、在主函数中输入待查元素

4、显示待查找元素的位置

例如：输入顺序表元素个数和数据如下：

5 3 8 7 9

输入的待查找元素为：

程序输出结果有：

5,3,8,7,9 //在查找之前遍历输出线性表中的数据元素

2 //待查元素在线性表中的位置

#include <stdio.h>
#include<stdlib.h>
#define  MAXSIZE 100  
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef  struct {
  ElemType  *elem;     //指向数据元素的基地址
  int  length;              //线性表的当前长度                                                     
 }SqList;
Status InitList_Sq(SqList *L)
{    
       L-> elem=(int *) malloc (4*100);  //为顺序表分配空间
    if(! L-> elem) exit(OVERFLOW);           //存储分配失败
    L-> length=0;                   //空表长度为0
      return OK;
}
Status CreateList_Sq(SqList *L,int n)
{
for(int i=0;i<n;i++)
{
 scanf("%d",&L->elem[i]);   
}
}
void TraverseList_Sq(SqList *L,int n)
{
  for(int i=0;i<n;i++)
  {
      if(i==n-1)
      printf("%d",L->elem[i]);
      if(i!=n-1)
      printf("%d,",L->elem[i]);
  }
}
//在此处定义按值查找函数 LocateELem_Sq
Status LocateELem_Sq(SqList * L,int n, int e)
{
//  printf("hell");
    for(int i=0 ;i<n;i++)
        {
           if(L->elem[i]==e)
            {
                  printf("\n");
                  printf("%d",i+1);
            }
        }
}
void DestroyList_Sq(SqList *L)
{
       if (L->elem)
       free (L->elem);             //释放存储空间
}
     int main()
{
  SqList L;        
  int i,n;
  ElemType e;
  InitList_Sq(&L);
  //提示：请输入元素个数：
        scanf("%d",&n);
  CreateList_Sq(&L,n);
  TraverseList_Sq(&L,n);
  //提示：请输入要查找的元素：
     scanf("%d",&e);
    i=LocateELem_Sq(&L,n,e);//在此处调用按值查找函数LocateELem_Sq
  //提示：待查找元素e的位置为：
             DestroyList_Sq(&L);
             return 0;
}

7.单链表的插入

1、定义插入函数（ListInsert_L）

2、在主函数中输出插入新结点之前单链表中的结点信息（TraverseList_L）

3、在主函数中输入插入结点的位置和数据信息

4、显示插入后的单链表数据信息（TraverseList_L）

例如：

输入单链表结点个数和数据如下：

5 3 8 7 9

结点插入的位置和值为：

程序输出为：

5,3,8,7,9 // 插入新结点之前输出的单链表中的结点信息

5,6,3,8,7,9 //插入新结点之后输出的单链表中的结点信息

# include <stdio.h>
# include <stdlib.h>
typedef int Status;
typedef int ElemType;
typedef struct LNode {
  ElemType data; //结点的数据域
  struct LNode * next; //结点的指针域
} LNode, *LinkList; //LinkList为指向结构体LNode的指针类型
LinkList InitList_L(LinkList L) 
{ 
    L = (LinkList)malloc(sizeof(LNode));
  //构造一个空的单链表L
//  L = new LNode;                //生成新结点作为头结点，用头指针L指向头结点
  L->next = NULL;               //头结点的指针域置空
  return L;
}
void CreateList_L(LinkList L,int n)
{ 
       LinkList p,q;
       //L=(LinkList)malloc(sizeof(LNode));
       L->next=NULL;
       p=L;
   for(int i=0;i<n;i++)
    {
      q=(LinkList)malloc(sizeof(LNode));
    scanf("%d",&q->data);
      //printf("jjj");
      q->next=NULL;
      p->next=q;
      p=q;
}
  }
//在此处定义单链表的插入函数ListInsert_L
Status ListInsert_L(LinkList L,int x,ElemType i)
{
  LinkList p;
  p=L;
 int j=0;
 while(p){//   先到i-1个节点
 p=p->next;
 j++;//
 if(j==x-1)
 {
   LinkList s;
    s=(LinkList)malloc(sizeof(LNode));
   s->data=i;
   s->next=p->next;
   p->next=s;
 }
 }
}
void TraverseList_L(LinkList L) 
//依次输出单链表里的每个元素
{
  LNode *o ;
            o=L->next; //o为头结点  
  while(o)
  {
    if(o!=NULL)
    { 
      printf("%d",o->data);
      if(o->next!=NULL)
      printf(",");
        o=o->next;
    }
}
}
Status DestroyList_L(LinkList L)
{
    LinkList p;
       while(L)
        {
            p=L;  
            L=L->next;
           free(p);  
        }
     return 1 ;
 }
int main()
{
  LinkList  L; 
  int n,i ;
  ElemType e;
  L=InitList_L(L);
    scanf("%d",&n);
  CreateList_L(L,n);  
TraverseList_L(L);
  scanf("%d%d",&i,&e);
  ListInsert_L(L,i,e);
  printf("\n");
  TraverseList_L(L);
    DestroyList_L(L);
  return 0 ;
}

8.顺序表删除_新

1、定义删除函数（ListDelete_Sq）

2、在主函数中遍历输出插入前线性表中的元素

3、在主函数中输入被删元素的位置

4、显示删除后的线性表元素

例如：输入顺序表元素个数和数据如下：

5 3 8 7 9

输入被删元素的位置：

程序输出结果为：

5,3,8,7,9 //删除元素之前输出的线性表中的数据元素

3 //输出的被删除元素

5,8,7,9 //输出删除元素之后线性表中的数据元素

# include <stdio.h>
# include <stdlib.h>
typedef struct Lnode{
    struct Lnode*next;
    int data;
}Lnode,*LinkList;
LinkList Inint_L(LinkList L)
{
  L=(LinkList) malloc (sizeof(Lnode));
  L->next=NULL;
}
void shuru(LinkList L,int n)
{     LinkList q;
          q=L;
      LinkList p;
          for(int i=0;i<n;i++)
          {
            p=(LinkList) malloc (sizeof(Lnode));
            scanf("%d",&p->data);
            p->next=NULL;
            q->next=p;
      q=p;
      }
}
void shuchu(LinkList L)
{
  LinkList p;
  p=L->next;
  while(p)
  {
    printf("%d",p->data);
    p=p->next;
    if(p!=NULL)
    {
      printf(",");
    }
  }
}
 int shanchu(LinkList L,int i)
 {
  printf("\n");
  int j=0;
  LinkList p,q;
  p=L;//L为头指针   只有指向  无内容  next域存首元结点地址  
  while(j<i-1&&p->next)
  {
      p=p->next;//   1-0. p指向寿元节点   i-1--- i-2=j 
      j++;
   }
  if(!(p->next)||(j>i-1))
  {
    return -1;
   }
q=p->next;   // q为要找的节点  p为前一个节点
p=q->next;   // 存   第i个节点的下一个地址
q->next=p->next;   //p为前一个节点   进行重新连接  
int e=p->data;
printf("%d\n",e);
free(p);
  return 1;
 }
int main()
{
  LinkList L;
  L=Inint_L(L);
  int n;
  scanf("%d",&n);
  shuru(L,n);
  shuchu(L);
  int i,e;
  e=shanchu(L,scanf("%d",&i));
  shuchu(L);
  return 0;
}

9.单链表的查找-按序号查找_新

1、定义按序查找函数（GetElem_Sq）

2、在主函数中输出插入新结点之前单链表中的结点信息（TraverseList_L）

3、在主函数中输入待查元素在单链表中的位序

4、显示查找后的数据

例如：输入单链表结点个数和数据如下：

5 3 8 7 9

输入查找结点的位序为：

程序输出结果为：

5,3,8,7,9 // 插入新结点之前输出的单链表中的结点信息

3 //输出该位置上的结点信息

# include <stdio.h>
# include <stdlib.h>
/*1、定义按序查找函数（GetElem_Sq）
2、在主函数中输出插入新结点之前单链表中的结点信息（TraverseList_L）
3、在主函数中输入待查元素在单链表中的位序
4、显示查找后的数据
例如： 输入单链表结点个数和数据如下：
5
5  3  8  7  9
输入查找结点的位序为：
2
程序输出结果为：
5,3,8,7,9     // 插入新结点之前输出的单链表中的结点信息
3                 //输出该位置上的结点信息*/
typedef struct Lnode{
  int data;
  struct Lnode *next;
}Lnode ,*LinkList;
  LinkList Init_L(LinkList L)
{
  L=(LinkList) malloc (sizeof(Lnode));
  L->next=NULL;
  return L;
}
     void  shuru (LinkList L,int n)
{
L->next=NULL;
  LinkList q,p;
  p=L;
  for(int i=0;i<n;i++)
  {
    q=(LinkList) malloc (sizeof(Lnode));
    scanf("%d",&q->data);
    q->next=NULL;
  p->next=q;
  p=q;  
  }
}
void shuchu(LinkList L)
{
  LinkList q,p;
  q=L;
  while(q->next)
  {
    p=q->next;
    if(p->next!=NULL)
    printf("%d,",p->data);
    else
    printf("%d",p->data);  
    q=q->next;
  }
}
int chazhao(LinkList L,int i)
{
  LinkList p,q;
    int j=1;
    p=L;
  while(p->next)
  {
    p=p->next;
    j++;
    if(j==i)
{
  p=p->next;
  return p->data; 
    }   
  }
}
int main()
{
  int n,i,e;
  scanf("%d",&n);
  LinkList L;
L=Init_L(L);
//  printf("jjjjjjjjjj"); 
            shuru(L,n);
  shuchu(L);
  printf("\n");
  scanf("%d",&i);
  e=chazhao(L,i);
  printf("%d",e);
  return 0;
}

10.单链表结点的删除_ 新

1、定义删除函数（ListDelete_L

2、在主函数中遍历输出删除前单链表中的结点信息

3、在主函数中输入被删结点的位置

4、显示删除后的单链表的结点信息

例如：输入单链表结点个数和数据如下：

5 3 8 7 9

输入被删结点的位置：

程序输出结果为：

5,3,8,7,9 //删除结点之前遍历输出的单链表中的结点信息

3 //输出被删除结点的结点信息

5,8,7,9 //删除结点之后遍历输出的单链表中的结点信息

# include <stdio.h>
# include <stdlib.h>
typedef struct Lnode{
    struct Lnode*next;
    int data;
}Lnode,*LinkList;
LinkList Inint_L(LinkList L)
{
  L=(LinkList) malloc (sizeof(Lnode));
  L->next=NULL;
}
void shuru(LinkList L,int n)
{     LinkList q;
          q=L;
      LinkList p;
          for(int i=0;i<n;i++)
          {
            p=(LinkList) malloc (sizeof(Lnode));
            scanf("%d",&p->data);
            p->next=NULL;
            q->next=p;
      q=p;
      }
}
void shuchu(LinkList L)
{
  LinkList p;
  p=L->next;
  while(p)
  {
    printf("%d",p->data);
    p=p->next;
    if(p!=NULL)
    {
      printf(",");
    }
  }
}
 int shanchu(LinkList L,int i)
 {
  printf("\n");
  int j=0;
  LinkList p,q;
  p=L;//L为头指针   只有指向  无内容  next域存首元结点地址  
  while(j<i-1&&p->next)
  {
      p=p->next;//   1-0. p指向寿元节点   i-1--- i-2=j 
      j++;
   }
  if(!(p->next)||(j>i-1))
  {
    return -1;
   }
q=p->next;   // q为要找的节点  p为前一个节点
p=q->next;   // 存   第i个节点的下一个地址
q->next=p->next;   //p为前一个节点   进行重新连接  
int e=p->data;
printf("%d\n",e);
free(p);
  return 1;
 }
int main()
{
  LinkList L;
  L=Inint_L(L);
  int n;
  scanf("%d",&n);
  shuru(L,n);
  shuchu(L);
  int i,e;
  e=shanchu(L,scanf("%d",&i));
  shuchu(L);
  return 0;
}

11.线性表的合并_新

假设利用两个线性表LA和LB分别表示两个集合A和B,现要求一个新的集合 A=A∪B，例如，设LA=（7 5 3 11 ），LB=（ 2 6 3），合并后LA=（7 5 3 11 2 6）

1、定义线性表的顺序存储结构

2、初始化线性表（InitList_Sq）

3、创建线性表（CreateList_Sq）

4、定义线性表的合并函数（unionList_Sq）,将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中，

（在合并函数中，还将包含对函数ListLengtht_Sq、ListInsert_Sq、LocateElem_Sq和GetElem_Sq的调用）

5、在主函数中输入两个线性表LA,LB,调用合并函数

6、遍历合并后的线性表LA,并输出数据（TraverseList_Sq）

例如：

输入线性表LA的元素个数和数据如下：

7 5 3 11

输入有序表LB的元素个数和数据如下：

2 6 3

输出为：

7,5,3,11 //输出线性表LA的数据元素

2,6,3 //输出线性表LB的数据元素

7,5,3,11,2,6 //输出合并后的线性表LA的数据元素

# include <stdio.h>
# include <stdlib.h>
# define MAXSIZE 100
typedef struct SeqList{
    int *elem;
    int length;
}SeqList;
void Init_S(SeqList *L)
{
    L->elem=(int*)malloc (sizeof(int)*MAXSIZE);
    L->length=0;
}
 int chuangjian(SeqList *L,int n)
{
  for(int i=0;i<n;i++)
  {
    scanf("%d",&L->elem[i]);
    ++L->length;
  }
  return 1;
}
  int getelem(SeqList *L,int i)
{
//printf("%d",L->elem[i-1]);
int u=L->elem[i-1];
return (u);
}
  int  bijiao(SeqList * L,int y )
{
  for(int i=0;i<L->length;i++)
  {
    if(L->elem[i-1]==y)
    return 6;
  }
   return 7 ;
}
SeqList* hebing(SeqList *La,SeqList Lb)
{
  int y;
  int p;
  int i=1;
  for(i=1;i<=Lb.length;i++)
  {//printf("jjjj");
    y=getelem(&Lb,i);
    p=bijiao(La,y);
    if(p==6)
    {
      continue;
    } 
    if(p==7)
    {
        ++La->length;
        La->elem[La->length-1]=y;
    } 
      }
  return La;
}
void shuchu(SeqList *L,int n)
{
  for(int i=0;i<n;i++)
  {
    if(i!=n-1)
    {
      printf("%d,",L->elem[i]);
    }
    if(i==n-1)
    {
      printf("%d",L->elem[i]);
    }
  }
  } 
int main()
{
  SeqList La,Lb;
  Init_S(&La);
  Init_S(&Lb);
  int n1,n2;
  scanf("%d",&n1);
  chuangjian(&La,n1);
  shuchu(&La,n1);
  printf("\n");
  scanf("%d",&n2);
  chuangjian(&Lb,n2);
  shuchu(&Lb,n2);
  printf("\n");
  hebing(&La,Lb);
  shuchu(&La,La.length);
  return 0;
}

12.有序表的合并_新

已知线性表LA 和LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的数据元素仍按值非递减有序排列.

1、定义有序表合并函数（MergeList_Sq）,将两个非递减的有序表LA和LB合并为一个新的有序表LC，且LC中的数据元素仍按值非递减有序排列

（在合并函数中，还将包含对ListLength_Sq的调用）

2、在主函数中输出LA表的数据元素（TraverseList_Sq）

3、在主函数中输出LB表的数据元素（TraverseList_Sq）

4、在主函数中输入两个非递减的有序表LA,LB,调用合并函数

5、遍历合并后的有序表LC,并输出数据（TraverseList_Sq）

例如：

输入有序表LA的元素个数和数据如下：

2 5 8 9

输入有序表LB的元素个数和数据如下：

3 4 8 10 12 20

输出为：

2,5,8,9 //输出LA表的数据元素

3,4,8,10,12,20 //输出LB表的数据元素

2,3,4,5,8,8,9,10,12,20 //输出合并后的LC表的数据元素

/*已知线性表LA 和LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的数据元素仍按值非递减有序排列.
1、定义有序表合并函数（MergeList_Sq）,将两个非递减的有序表LA和LB合并为一个新的有序表LC，且LC中的数据元素仍按值非递减有序排列
   （在合并函数中，还将包含对ListLength_Sq的调用）
2、在主函数中输出LA表的数据元素（TraverseList_Sq）
3、在主函数中输出LB表的数据元素（TraverseList_Sq）
4、在主函数中输入两个非递减的有序表LA,LB,调用合并函数
5、遍历合并后的有序表LC,并输出数据（TraverseList_Sq）
例如：
输入有序表LA的元素个数和数据如下：
4
2  5  8  9
输入有序表LB的元素个数和数据如下：
6
3  4  8  10  12  20   
输出为：
2,5,8,9                    //输出LA表的数据元素
3,4,8,10,12,20       //输出LB表的数据元素
2,3,4,5,8,8,9,10,12,20  //输出合并后的LC表的数据元素*/
# include <stdio.h>
# include <stdlib.h>
# define MAXSIZE 100
typedef struct SeqList{
    int *elem;
    int length;
}SeqList;
void Init_S(SeqList *L)
{
    L->elem=(int*)malloc (sizeof(int)*MAXSIZE);
    L->length=0;
}
 int chuangjian(SeqList *L,int n)
{
  for(int i=0;i<n;i++)
  {
    scanf("%d",&L->elem[i]);
    ++L->length;
  }
  return 1;
}
/*int getelem(SeqList *L,int i)
{
//printf("%d",L->elem[i-1]);
int u=L->elem[i-1];
return (u);
}*/
void hebing(SeqList La,SeqList Lb,SeqList* Lc)
 {
         int p=0,q=0,k=0;
         int f=La.length;
         int e=Lb.length;
       Lc->length=e+f;
while(p<f&&q<e)
{
  if(La.elem[p]<=Lb.elem[q])
      {
        Lc->elem[k]=La.elem[p];             
      k++;
        p++;
    }
  else
  {
    Lc->elem[k]=Lb.elem[q];
    k++;
    q++;
  }
}
while(p<La.length)
{
  Lc->elem[k]=La.elem[p];
  k++;
  p++;
}
while(q<Lb.length)
{
  Lc->elem[k]=Lb.elem[q];
  k++;
  q++;
}}
void shuchu(SeqList *L,int n)
 {
  for(int i=0;i<n;i++)
  {
    if(i!=n-1)
    {
      printf("%d,",L->elem[i]);
    }
    if(i==n-1)
    {
      printf("%d",L->elem[i]);
    }
  }
}
  int main()
  {
    SeqList La;
    SeqList Lb;
    SeqList Lc;
    Init_S(&La);
    Init_S(&Lb);
    Init_S(&Lc);
    int n1,n2;
    scanf("%d",&n1);
    chuangjian(&La,n1);
    shuchu(&La,n1);
    printf("\n");
    scanf("%d",&n2);
    chuangjian(&Lb,n2);
    shuchu(&Lb,n2);
    printf("\n");
      hebing(La,Lb,&Lc);
      int t=Lc.length;
    //  printf("\n");
  //printf(",,,,");
      shuchu(&Lc,t);
    return 0;
  }

13.有序链表的合并_新

已知线性表LA 和LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的数据元素仍按值非递减有序排列.

1、用后插法创建单链表数据（CreateList_L）

2、定义遍历函数输出单链表数据（TraverseList_L）

3、定义有序链表合并函数（MergeList_L）,将两个非递减的有序链表LA和LB合并为一个新的有序链表LC，且LC中的结点元素仍按值非递减有序排列

4、在主函数中输出LA和LB表的结点信息（TraverseList_L）

5、在主函数中调用合并函数（MergeList_L）

6、遍历合并后的有序链表LC,并输出结点信息（TraverseList_L）

例如：

输入有序链表LA的结点个数和数据如下：

2 5 8 9

输入有序链表LB的结点个数和数据如下：

3 4 8 10 12 20

输出为：

2,5,8,9 //输出LA表的结点信息

3,4,8,10,12,20 //输出LB表的结点信息

2,3,4,5,8,8,9,10,12,20 //输出合并后的LC表的结点信息

/*已知线性表LA 和LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的数据元素仍按值非递减有序排列.
1、用后插法创建单链表数据（CreateList_L）
2、定义遍历函数输出单链表数据（TraverseList_L）
3、定义有序链表合并函数（MergeList_L）,将两个非递减的有序链表LA和LB合并为一个新的有序链表L`C，且LC中的结点元素仍按值非递减有序排列
4、在主函数中输出LA和LB表的结点信息（TraverseList_L）
5、在主函数中调用合并函数（MergeList_L）
6、遍历合并后的有序链表LC,并输出结点信息（TraverseList_L）
例如：
输入有序链表LA的结点个数和数据如下：
4
2  5  8  9
输入有序链表LB的结点个数和数据如下：
6
3  4  8  10  12  20   
输出为：
2,5,8,9                    //输出LA表的结点信息
3,4,8,10,12,20               //输出LB表的结点信息
2,3,4,5,8,8,9,10,12,20          //输出合并后的LC表的结点信息
*/
# include <stdio.h>
# include <stdlib.h>
typedef struct Lnode{
  int data;
struct Lnode * next;
}Lnode,*LinkList;
LinkList Init_L(LinkList L)
{
  L=(LinkList)malloc (sizeof(Lnode));
  L->next=NULL;
  return L;
}
  void shuru(LinkList L,int n)                  
    {
      LinkList q,p;
    p=L;    
    for(int i=0;i<n;i++)
  {
  q=(LinkList) malloc(sizeof(Lnode)); 
  scanf("%d",&(q->data));     //
  q->next=NULL;
  p->next=q;
  p=q;
   } 
     }
    void shuchu(LinkList L)
        {
        LinkList q;
        q=L;
        while(q->next!=NULL)
        {
          q=q->next;
          if(q->next)
          {
            printf("%d,",q->data);
      }
          else
          {
            printf("%d",q->data);
      }
    }
    }
               LinkList hebing(LinkList La,LinkList Lb,LinkList Lc)
         {
          LinkList pc;
          LinkList pa;
          LinkList pb;
          pa=La->next;
          pb=Lb->next;
           Lc=La;
           pc=Lc; 
          while(pa&&pb)
          {  
        if(pa->data<=pb->data)
        {//printf("lllllllll");
          pc->next=pa;
          pc=pa;
          pa=pa->next;
             }    
        else
        {
          pc->next=pb;
          pc=pb;
          pb=pb->next;
        }
           }
      if(pa)
      pc->next=pa;
      if(pb)
      pc->next=pb;
        //  pc->next=pa?pa:pb;
         }  
       int main()
       {
        LinkList La;
        LinkList Lb;
        LinkList Lc;
       int n1;
        scanf("%d",&n1);
        La=Init_L(La);
        shuru(La,n1);
        shuchu(La);
        printf("\n");
             int n2;
        scanf("%d",&n2);
        Lb=Init_L(Lb);
        shuru(Lb,n2);
        shuchu(Lb);
        printf("\n");
        hebing(La,Lb,Lc);
        shuchu(La);
        return 0;
     }

数据结构51道基础题之线性表13题

一、线性表基础13题

1.线性表的建立

2.单链表的建立-前插法

3.单链表的建立-后插法

4.顺序表的插入

5.顺序表的查找—按序号进行查找

6.顺序表的查找—按值进行查找

7.单链表的插入

8.顺序表删除_新

9.单链表的查找-按序号查找_新

10.单链表结点的删除_ 新

11.线性表的合并_新

12.有序表的合并_新

13.有序链表的合并_新

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构51道基础题之线性表13题

一、线性表基础13题

1.线性表的建立

2.单链表的建立-前插法

3.单链表的建立-后插法

4.顺序表的插入

5.顺序表的查找—按序号进行查找

6.顺序表的查找—按值进行查找

7.单链表的插入

8.顺序表删除_新

9.单链表的查找-按序号查找_新

10.单链表结点的删除_ 新

11.线性表的合并_新

12.有序表的合并_新

13.有序链表的合并_新

热门文章

最新文章

相关课程

相关电子书