909-2015-T1

1.原题

线性表使用公式化描述方式存储。编写一个函数，从一给定的线性表A中删除值在x ~ y（x到y，x<=y）之间的所有元素，要求以较高的效率来实现。提示：可以先将线性表中所有值在x~y之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删除掉。

2.算法思想

不需要管提示，有更好的算法。对于在x ~ y之间的元素，不需要管。对于不在x ~ y之间的元素，移动到指定的位置。通过双指针来实现，这样免去了每次删除的复杂操作，降低时间复杂度

3.关键代码

typedef struct {int data[MAX_SIZE]; /**< 用数组存储线性表的元素 */int length; /**< 记录线性表的当前长度 */
} LinearList;/*** @brief 删除线性表中所有值介于 x 和 y 之间的元素** @param list 指向 LinearList 结构的指针* @param x 范围的下限值* @param y 范围的上限值*/
void deleteInRange(LinearList *list, int x, int y) {int insertPos = 0; // 插入位置的指针for (int i = 0; i < list->length; i++) {if (list->data[i] < x || list->data[i] > y) {if (i != insertPos) {list->data[insertPos] = list->data[i];}insertPos++;}}list->length = insertPos; // 更新线性表的长度
}

4.完整代码

/*** @file linear_list.c* @brief 实现了线性表的基本操作，如初始化、插入、删除、输出和删除范围内的元素。*/#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100 /**< 定义线性表的最大长度为100 */typedef struct {int data[MAX_SIZE]; /**< 用数组存储线性表的元素 */int length; /**< 记录线性表的当前长度 */
} LinearList;/*** @brief 删除线性表中所有值介于 x 和 y 之间的元素** @param list 指向 LinearList 结构的指针* @param x 范围的下限值* @param y 范围的上限值*/
void deleteInRange(LinearList *list, int x, int y) {int insertPos = 0; // 插入位置的指针for (int i = 0; i < list->length; i++) {if (list->data[i] < x || list->data[i] > y) {if (i != insertPos) {list->data[insertPos] = list->data[i];}insertPos++;}}list->length = insertPos; // 更新线性表的长度
}/*** @brief 初始化线性表** @param list 指向 LinearList 结构的指针*/
void initList(LinearList *list) {list->length = 0;
}/*** @brief 插入元素到线性表指定位置** @param list 指向 LinearList 结构的指针* @param element 要插入的元素值* @param position 插入的位置* @return int 插入成功返回1，失败返回0*/
int insertElement(LinearList *list, int element, int position) {if (position < 0 || position > list->length || list->length == MAX_SIZE) {return 0; // 插入失败}// 将插入位置之后的元素依次向后移动一位for (int i = list->length - 1; i >= position; i--) {list->data[i + 1] = list->data[i];}list->data[position] = element;list->length++; // 长度加一return 1; // 插入成功
}/*** @brief 删除线性表指定位置的元素** @param list 指向 LinearList 结构的指针* @param position 要删除的元素位置* @return int 删除成功返回1，失败返回0*/
int deleteElement(LinearList *list, int position) {if (position < 0 || position >= list->length) {return 0; // 删除失败}// 将删除位置之后的元素依次向前移动一位for (int i = position; i < list->length - 1; i++) {list->data[i] = list->data[i + 1];}list->length--; // 长度减一return 1; // 删除成功
}/*** @brief 输出线性表中的元素** @param list LinearList 结构*/
void displayList(LinearList list) {printf("Linear List: ");for (int i = 0; i < list.length; i++) {printf("%d ", list.data[i]);}printf("\n");
}/*** @brief 销毁线性表** @param list 指向 LinearList 结构的指针*/
void destroyList(LinearList *list) {list->length = 0;// 可选的：将数组元素清零// memset(list->data, 0, sizeof(list->data));
}/*** @brief 主函数** @return int 程序执行结果*/
int main() {LinearList list;initList(&list);int elements[] = {21, 22, 5, 6, 23, 7, 24, 8, 25, 9, 10, 26, 27, 28};int numElements = sizeof(elements) / sizeof(elements[0]);for (int i = 0; i < numElements; i++) {insertElement(&list, elements[i], i);}displayList(list);int x = 6;int y = 25;deleteInRange(&list, x, y);displayList(list);destroyList(&list);return 0;
}

5.运行结果