当前位置：首页 > news >正文

习题1.9 有序数组的插入

news 2026/5/12 5:31:01

习题1.9 有序数组的插入

分数 20

作者陈越

单位浙江大学

本题要求将任一给定元素插入从大到小排好序的数组中合适的位置，以保持结果依然有序。

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递减有序的。函数Insert要将X插入Data[]中合适的位置，以保持结果依然有序（注意：元素从下标0开始存储）。但如果X已经在Data[]中了，就不要插入，返回失败的标记false；如果插入成功，则返回true。另外，因为Data[]中最多只能存MAXSIZE个元素，所以如果插入新元素之前已经满了，也不要插入，而是返回失败的标记false。

输入样例1：

35 12 8 7 3

输出样例1：

35 12 10 8 7 3

Last = 5

输入样例2：

35 12 10 8 7 3

输出样例2：

Insertion failed.

35 12 10 8 7 3

Last = 5

#include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 typedef enum { false, true } bool; typedef int ElementType; typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */ }; List ReadInput() /* 裁判实现，细节不表。元素从下标0开始存储 */ { List L = (List)malloc(sizeof(struct LNode)); int n; scanf("%d", &n); L->Last = n - 1; // 元素从下标0开始存储 for (int i = 0; i < n; i++) { scanf("%d", &L->Data[i]); } return L; } void PrintList(List L) /* 裁判实现，细节不表 */ { for (int i = 0; i <= L->Last; i++) { printf("%d", L->Data[i]); if (i < L->Last) printf(" "); } printf("\n"); printf("Last = %d\n", L->Last); } bool Insert(List L, ElementType X) { int n = L->Last; if (n == MAXSIZE - 1) //表满？ return false; for (int i = 0; i <= n; i++) //重复？ { if (L->Data[i] == X) { return false; break; } } int pos; // X的位置 for (pos = 0; pos <= n; pos++) { if (L->Data[pos] < X) //找到第一个比X小的数，插入这个数的前边，X的位置就是这个数的位置 break; } for (int i = n; i >= pos; i--) //后移，n的位置上是空的，直接覆盖就行，后序也是直接覆盖 L->Data[i + 1] = L->Data[i]; L->Data[pos] = X; //插入X /* L->Data[n + 1] = X; for (int i = 0; i < n + 1; i++)//冒泡排序，时间复杂度高，不用 { for (int j = 0; j < n - i + 1; j++) { if (L->Data[j] < L->Data[j + 1]) { int temp = L->Data[j]; L->Data[j] = L->Data[j + 1]; L->Data[j + 1] = temp; } } }*/ L->Last++; } int main() { List L; //下标从0开始 ElementType X; //要插入的新元素 L = ReadInput(); scanf("%d", &X); if (Insert(L, X) == false) printf("Insertion failed.\n"); PrintList(L); return 0; } /* 你的代码将被嵌在这里 */

查看全文

http://www.jsqmd.com/news/475941/