数据结构

顺序表练习题

1.已知一个顺序表L，其中的元素递增有序排列，设计一个算法，插入一个元素x(x为int型)后保持该顺序表仍然递增有序排列(假设插入操作总能成功)。

/**************************************************************************************
 *
 *
 *  file name:  demo_1.c
 *  author   :  Tongyaqi1110@163.com
 *  date     :  2024/04/21
 *  function :  设计一个算法，在有序的顺序表中插入一个数，且递增有序
 *  note     :  None
 *
 *  CopyRight (c)   2024    Tongyaqi1110@163.com   All Right Reserved
 *************************************************************************************/

#include <stdio.h>
// 假设插入操作总能成功，所以不必判断该顺序表L容量有没有满的问题
// 但是要分顺序表L为空和非空的情况，如果为空可直接插入到数组的第一个位置，非空的话需要进行查找才能插入到指定位置。
// 1.顺序表L不为空在顺序表中从后往前开始遍历，找到第一个大于等于x的位置，记为max
// 2.将max及比x大的元素都往后移动一位，方便x插入
// 3.更新顺序表L的长度
#define MAX_SIZE 100
typedef struct
{
  int data[MAX_SIZE];
  int length;
} SeqList;
// 插入元素并保持递增有序
void InsertElement(SeqList *L, int x)
{
  int max = L->length - 1;
  while (max >= 0 && L->data[max] > x)
  {
    L->data[max + 1] = L->data[max];
    max--;
  }
  L->data[max + 1] = x;
  L->length++;
}
int main()
{
  SeqList L = {{1, 2, 4, 8, 9}, 5};
  int x;
  printf("请输入要插入的元素");
  scanf("%d", &x);
  // printf("%d", x);
  InsertElement(&L, x);
  printf("插入后顺序表L的元素为：");
  for (int i = 0; i < L.length; i++)
  {
    printf("%d\n", L.data[i]);
  }
  return 0;
}