【数据结构基础应用】【顺序表】

文章目录

• ​​前言​​

• ​​1、合并两个顺序表​​

前言

本章总结在看书过程中的一些关于顺序表的算法题并可能含有一些自己的一些疑问。题目数量不定，随阅历增加而增加；

1、合并两个顺序表

题目要求：

有两个顺序存储的线性表，分别存放了一些整数数据，每个顺序表中存放的数据从小到大排列。写一个程序，将两个表合并，生成一个新的顺序表，里面的顺序仍然按照从小到大排列。

例如:

list1:1,2,4,8,10

list2:3,9,11

合并之后的list3:1,2,3,4,8,9,10,11

#include <stdio.h>
#include <stdlib.h>
#include "malloc.h"
#include "conio.h"
typedef int ElemType;

typedef struct {
  int* elem;
  int length;
  int listsize;
}Sqlist;

//初始化顺序表
void InitSqlist(Sqlist *L,int size)
{
  L->elem = (int*)malloc(sizeof(ElemType)*size);      //在堆内存上开辟空间,并将地址指针传给elem
  if (!L->elem)
  {
    printf("顺序表内存开辟失败");
    exit(0);
  }
  L->length = 0;                //最开始的表长0
  L->listsize = size;
}

//向顺序表中插入元素
//向顺序表L第i个位置插入元素item
void InsertElem(Sqlist* L,int i, ElemType item)
{
  //追加内存后的新的基址、指向插入位置的指针、移动数据的指针中间变量
  ElemType* base, * insertPtr, * p;
  if (i<1 || i>L->length + 1)   
  {
    printf("非法插入");
    exit(0);
  }
  if (L->length >= L->listsize)   //顺序表的空间不够，追加内存
  {
    base = (ElemType*)realloc(L->elem, (L->listsize + 10) * sizeof(ElemType));    //将追加内容后的内存首地址传给base
    L->elem = base;
    L->listsize = L->listsize + 100;
  }
  insertPtr = &(L->elem[i-1]);    //指针指向插入位置
  for (p = &L->elem[L->length - 1];p >= insertPtr;p--)
  {
    //移动顺序表中数据
    *(p+1) = *p;
  }
  *insertPtr = item;        //插入数据元素
  L->length++;
}
//销毁顺序表
void DestroySqlist(Sqlist* list)
{
  int* p = list->elem;
  free(p);
  list->elem = NULL;
  list->length = 0;
  list->listsize = 0;
}
//两个顺序表内容的合并,返回一个新的list
Sqlist MergeList(Sqlist list1, Sqlist list2)
{
  //将list1和list2的内容合并到list3并返回
  int* p1, * p2, * p3, * p1_last, * p2_last;
  Sqlist list3;

  p1 = list1.elem;    //p1指向list1第一个元素
  p2 = list2.elem;    //p2指向list2第一个元素

  //初始化list3，其长度为list1 list2 长度之和
  InitSqlist(&list3,list1.length+list2.length);

  p3 = list3.elem;    //p3指向list3第一个元素
  p1_last = list1.length + list1.elem - 1;  //p1_last指向list1的表尾
  p2_last = list2.length + list2.elem - 1;  //p2_last指向list2的表尾

  //实现合并
  while (p1<=p1_last && p2<=p2_last)    //当list1与list2中有一个list被遍历完
  {
    if (*p1 <= *p2) //当p1指向的元素小于p2指向的元素
    {
      *p3 = *p1;
      p3++;
      p1++;
    }
    else
    {
      *p3 = *p2;
      p3++;
      p2++;
    }
    list3.length++;
  }
  //将list1或者list2中剩余元素并入list3中
  if (p1 <= p1_last)    //p1有剩余
  {
    while (p1 <= p1_last)
    {
      *p3 = *p1;
      p3++;
      p1++;
      list3.length++;
    }
  }
  else
  {
    while (p2 <= p2_last)
    {
      *p3 = *p2;
      p3++;
      p2++;
      list3.length++;
    }
  }
  //当搬移完成后，返回list3
  return list3;
}
//测试程序
int main()
{
  Sqlist list1, list2, list3;   //实例化3个顺序表
  int n, i;         //存放list长度中间变量、累加器
  ElemType e;         //插入元素中间变量
  printf("请输入list1的长度\n");
  scanf("%d",&n);
  InitSqlist(&list1,n);
  printf("请输入list1的元素\n");
  for (i=1;i<=n;i++)
  {
    scanf("%d",&e);
    InsertElem(&list1,i,e);
  }
  printf("请输入list2的长度\n");
  scanf("%d", &n);
  InitSqlist(&list2, n);
  printf("请输入list2的元素\n");
  for (i = 1;i <= n;i++)
  {
    scanf("%d", &e);
    InsertElem(&list2, i, e);
  }
  list3 = MergeList(list1,list2);
  printf("输出合并后的结果\n");
  for (i = 0;i < list3.length;i++)
  {
    printf("%d ",list3.elem[i]);      //这里%d根据ElemType类型来进行修改
  }
  //销毁list，释放内存
  DestroySqlist(&list1);
  DestroySqlist(&list2);
  DestroySqlist(&list3);
  _getche();
  return 0;
}