C语言程序设计第四版（何钦铭、颜晖）第十章函数与程序结构之有序表的操作

【例10-1】有序表的增删查操作。首先输入一个无重复元素的、从小到大排列的有序表,并在屏幕上显示以下菜单(编号和选项),用户可以反复对该有序表进行插入、删除和查找操作,也可以选择结束。当用户输入编号1~3和相关参数时,将分别对该有序表进行插入、删除和查找操作,输入其他编号,则结束操作。对数组a成功插入、删除后,数组元素的数量也会相应地增1或减1,本例使用全局变量Count记录数组a中待处理的元素个数。请读者考虑3个问题并上机实现:如果不使用全局变量Count,如何修改程序;如何修改输入函数input_array()的定义,当输入数据无序或者重复时,使数组a有序且无重复元素;如何修改插入函数insert()的定义,使重复元素不会被插入。本例采用结构化程序设计思想,把一个对相对较大的问题分解为4层结构,7个函数,使程序的构思、编写及上机调试等过程的复杂度大大降低,阅读起来也变得容易。[1] Insert[2] Delete[3] Query[Other option] End#include stdio.h #define MAXN 100 // 函数声明 int input(int a[], int *len); int sort(int a[], int *len); int select(int a[], int *len, int option, int value); int del(int a[], int *len, int value); int insert(int a[], int *len, int value); int query(int a[], int *len, int value); int print(int a[], int *len); int remove_duplicates(int a[], int *len); // 专门去重 int main() { int a[MAXN], n, option, value; printf(Enter array size: \n); scanf(%d, n); printf(Enter %d numbers: \n, n); input(a, n); printf([1] Insert\n); printf([2] Delete\n); printf([3] Query\n); printf([Other option] End\n); while(1) { printf(Enter option: \n); scanf(%d, option); if(option 1 || option 3) break; printf(Input an element:\n ); scanf(%d, value); select(a, n, option, value); } printf(\nThanks!\n); return 0; } // 输入函数 int input(int a[], int *len) { for(int i 0; i *len; i) { scanf(%d, a[i]); } sort(a, len); return 0; } // 排序函数 - 使用选择排序 int sort(int a[], int *len) { int i, j, min_idx, temp; // 1. 排序 for(i 0; i *len - 1; i) { min_idx i; for(j i 1; j *len; j) { if(a[j] a[min_idx]) { min_idx j; } } // 交换 temp a[min_idx]; a[min_idx] a[i]; a[i] temp; } // 2. 去重 remove_duplicates(a, len); return 0; } // 去重函数 - 专门处理有序数组的去重 int remove_duplicates(int a[], int *len) { if(*len 1) return 0; int j 0; // 新数组的索引 for(int i 1; i *len; i) { if(a[i] ! a[j]) { j; a[j] a[i]; } } *len j1; // 更新数组长度 return 0; } // 选择函数 int select(int a[], int *len, int option, int value) { switch(option) { case 1: insert(a, len, value); break; case 2: del(a, len, value); break; case 3: query(a, len, value); break; } return 0; } // 删除函数 int del(int a[], int *len, int value) { int i, index -1; // 查找元素位置 for(i 0; i *len; i) { if(a[i] value) { index i; break; } } if(index -1) { printf(Failed to find the data, deletion failed.\n); } else { // 前移元素 for(i index; i *len - 1; i) { a[i] a[i 1]; } (*len)--; // 注意括号 printf(Element deleted successfully.\n); } print(a, len); return 0; } // 插入函数 int insert(int a[], int *len, int value) { int i, pos *len; // 单循环同时检查重复和查找位置 for(i 0; i *len; i) { if(value a[i]) { printf(The element has repeated.\n); print(a, len); return 0; } if(value a[i] pos *len) { // 只记录第一个大于value的位置 pos i; } } // 检查数组是否已满 if(*len MAXN) { printf(Array is full, cannot insert.\n); return 0; } // 后移元素 for(i *len; i pos; i--) { a[i] a[i - 1]; } // 插入 a[pos] value; (*len); printf(Element inserted successfully.\n); print(a, len); return 0; } // 查询函数 - 修正二分查找 int query(int a[], int *len, int value) { int low 0, high *len - 1, mid; while(low high) { mid (low high) / 2; if(a[mid] value) { printf(The index is %d\n, mid); return 0; } else if(value a[mid]) { high mid - 1; } else { low mid 1; } } printf(This element does not exist.\n); return 0; } // 输出函数 int print(int a[], int *len) { if(*len 0) { printf(Array is empty.\n); return 0; } printf(Current array (%d elements):\n , *len); for(int i 0; i *len; i) { printf(%d , a[i]); } printf(\n); return 0; }输入样例41 5 3 7109输出结果Enter array size:Enter 4 numbers:[1] Insert[2] Delete[3] Query[Other option] EndEnter option:Input an element:Element inserted successfully.Current array (5 elements):0 1 3 5 7Enter option:Thanks!