王道数据结构编程题(顺序表)
2022/3/1 22:51:48
本文主要是介绍王道数据结构编程题(顺序表),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删运算的值。空出的位置由最后一个元素填补,若顺序表为空,则显示出错信息并退出运行。
输入样例: 5 3 4 1 6 7 6 5 2 7 9 3 6 0 输出样例: 1 3 4 6 7 2 5 6 7 9 3 error
#include <stdio.h> #define MAX_SIZE 100 typedef struct SqList { int data[MAX_SIZE]; int length; } SqList; void ListPrint(SqList L); int ListDelete(SqList *L); int main() { SqList L; while (scanf("%d", &L.length) && L.length!= 0) { for (int i = 0; i < L.length; i++) { scanf("%d", &(L.data[i])); } printf("%d\n", ListDelete(&L)); ListPrint(L); } printf("error"); return 0; } void ListPrint(SqList L) { for (int i = 0; i < L.length; i++) { printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32); } } int ListDelete(SqList *L) { int min_pos = 0, min_val = 0; for (int i = 0; i < L->length; i++) { if (L->data[i] < L->data[min_pos]) min_pos = i; } min_val = L->data[min_pos]; L->data[min_pos] = L->data[L->length - 1]; L->length--; return min_val; }
2.设计一个高效算法,将顺序表L的所有元素逆置,要求算法的空间复杂度为 O ( 1 ) O(1) O(1)。
输入样例: 5 3 4 1 6 7 6 5 2 7 9 3 6 0 输出样例: 7 6 1 4 3 6 3 9 7 2 5
#include <stdio.h> #define MAX_SIZE 100 typedef struct SqList { int data[MAX_SIZE]; int length; } SqList; void ListPrint(SqList L); void ListInvert(SqList *L); int main() { SqList L; while (scanf("%d", &L.length) && L.length!= 0) { for (int i = 0; i < L.length; i++) { scanf("%d", &(L.data[i])); } ListInvert(&L); ListPrint(L); } return 0; } void ListPrint(SqList L) { for (int i = 0; i < L.length; i++) { printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32); } } void ListInvert(SqList *L) { for (int i = 0; i < L->length / 2; i++) { L->data[i] = L->data[i] + L->data[L->length - i - 1]; L->data[L->length - i - 1] = L->data[i] - L->data[L->length - i - 1]; L->data[i] = L->data[i] - L->data[L->length - i - 1]; } }
3.对长度为n的顺序表L,编写一个时间复杂度为 O ( n ) O(n) O(n)、空间复杂度为 O ( 1 ) O(1) O(1)的算法,该算法删除线性表中所有值为x的数据元素。
输入样例: 5 3 5 8 3 1 3 5 3 5 8 3 1 8 0 输出样例: 5 8 1 3 5 3 1
#include <stdio.h> #define MAX_SIZE 100 typedef struct SqList { int data[MAX_SIZE]; int length; } SqList; void ListPrint(SqList L); void ListDelete(SqList *L, int x); void ListDelete_(SqList *L, int x); int main() { SqList L; while (scanf("%d", &L.length) && L.length!= 0) { int x; for (int i = 0; i < L.length; i++) { scanf("%d", &(L.data[i])); } scanf("%d", &x); ListDelete(&L, x); /*ListDelete_(&L, x);*/ ListPrint(L); } return 0; } void ListPrint(SqList L) { for (int i = 0; i < L.length; i++) { printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32); } } void ListDelete(SqList *L, int x) { int cursor = 0, offset = 0;//offset记录等于x的元素的个数 while (cursor + offset < L->length) { if (L->data[cursor + offset] == x) { offset++; } else { L->data[cursor] = L->data[cursor + offset];//将当前不等于x的元素向前偏移offset cursor++; }; } L->length -= offset;//更新顺序表长度 } void ListDelete_(SqList *L, int x) { int slow = 0; for (int fast = 0; fast < L->length; fast++) { if (L->data[fast] != x) { L->data[slow] = L->data[fast]; slow++; } } L->length = slow;//更新顺序表长度 }
4.从有序顺序表中删除其值在给定值s与t之间(s<t)的所有元素,若s或t不合理或顺序表为空,则显示出错信息并退出运行。
输入样例: 5 1 2 3 4 5 2 4 6 5 6 7 8 9 10 8 10 0 输出样例: 1 5 5 6 7 error
#include <stdio.h> #define MAX_SIZE 100 typedef struct SqList { int data[MAX_SIZE]; int length; } SqList; void ListPrint(SqList L); void ListDelete(SqList *L, int s, int t); int main() { SqList L; while (scanf("%d", &L.length) && L.length!= 0) { int s, t; for (int i = 0; i < L.length; i++) { scanf("%d", &(L.data[i])); } scanf("%d %d", &s, &t); if (s >= t) break; ListDelete(&L, s, t); ListPrint(L); } printf("error"); return 0; } void ListPrint(SqList L) { for (int i = 0; i < L.length; i++) { printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32); } } void ListDelete(SqList *L, int s, int t) { int slow = 0; for (int fast = 0; fast < L->length; fast++) { if (L->data[fast] < s || L->data[fast] > t) { L->data[slow] = L->data[fast]; slow++; } } L->length = slow; }
5.从顺序表中删除其值在给定值s与t之间(包含s和t,要求s<t)的所有元素,若s或t不合理或顺序表为空,则显示出错信息并退出运行。
输入样例: 5 3 4 1 6 7 4 6 6 5 2 7 9 3 6 7 9 0 输出样例: 3 1 7 5 2 3 6
#include <stdio.h> #define MAX_SIZE 100 typedef struct SqList { int data[MAX_SIZE]; int length; } SqList; void ListPrint(SqList L); void ListDelete(SqList *L, int s, int t); int main() { SqList L; while (scanf("%d", &L.length) && L.length!= 0) { int s, t; for (int i = 0; i < L.length; i++) { scanf("%d", &(L.data[i])); } scanf("%d %d", &s, &t); if (s >= t) break; ListDelete(&L, s, t); ListPrint(L); } printf("error"); return 0; } void ListPrint(SqList L) { for (int i = 0; i < L.length; i++) { printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32); } } void ListDelete(SqList *L, int s, int t) { int slow = 0; for (int fast = 0; fast < L->length; fast++) { if (L->data[fast] < s || L->data[fast] > t) { L->data[slow] = L->data[fast]; slow++; } } L->length = slow; }
6.从有序表中删除所有其值重复的元素,使表中所有元素的值均不同。
输入样例: 5 1 2 2 2 3 10 1 2 2 2 3 4 4 4 5 5 输出样例: 1 2 3 1 2 3 4 5
#include <stdio.h> #define MAX_SIZE 10 typedef struct SqList { int data[MAX_SIZE]; int length; } SqList; void ListPrint(SqList L); void ListDelete(SqList *L); void ListDelete_(SqList *L); int main() { SqList L; while (scanf("%d", &L.length) && L.length!= 0) { for (int i = 0; i < L.length; i++) { scanf("%d", &(L.data[i])); } ListDelete(&L); /*ListDelete_(&L);*/ ListPrint(L); } printf("error"); return 0; } void ListPrint(SqList L) { for (int i = 0; i < L.length; i++) { printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32); } } /*对有序表和无序表都适用*/ void ListDelete(SqList *L) { for (int i = 0; i < L->length; i++) { int same = 0;//重复元素的个数 /*将当前元素与后面的所有元素进行比较*/ for (int j = i + 1; j < L->length; j++) { if (L->data[i] == L->data[j]) { same++; } else { L->data[j - same] = L->data[j]; } } L->length -= same; } } /*只能处理有序表*/ void ListDelete_(SqList *L) { int slow = 0, fast = 0; while (fast < L->length) { while (L->data[fast] == L->data[fast + 1]) { fast++; } L->data[slow++] = L->data[fast++]; } L->length = slow; }
7.将两个有序顺序表合并为一个新的有序顺序表。
输入样例: 3 4 1 3 5 2 4 6 8 0 0 输出样例: 1 2 3 4 5 6 8
#include <stdio.h> #define MAX_SIZE 10 typedef struct SqList { int data[MAX_SIZE]; int length; } SqList; void ListPrint(SqList L); void ListMerge(SqList A, SqList B, SqList *L); int main() { SqList A; SqList B; while (scanf("%d %d", &A.length, &B.length) && A.length != 0 && B.length != 0) { SqList L; L.length = 0; for (int i = 0; i < A.length; i++) { scanf("%d", &(A.data[i])); } for (int i = 0; i < B.length; i++) { scanf("%d", &(B.data[i])); } ListMerge(A, B, &L); ListPrint(L); } return 0; } void ListPrint(SqList L) { for (int i = 0; i < L.length; i++) { printf("%d%c", L.data[i], (i == L.length - 1) ? 10 : 32); } } void ListMerge(SqList A, SqList B, SqList *L) { int cur_a = 0, cur_b = 0, cursor = 0; while (cur_a < A.length && cur_b < B.length) { if (A.data[cur_a] < B.data[cur_b]) { L->data[cursor++] = A.data[cur_a++]; L->length++; } else { L->data[cursor++] = B.data[cur_b++]; L->length++; } } while (cur_a < A.length) { L->data[cursor++] = A.data[cur_a++]; L->length++; } while (cur_b < B.length) { L->data[cursor++] = B.data[cur_b++]; L->length++; } }
8.已知在一维数组A[m+n]中依次存放两个线性表 ( a 1 , a 2 , a 3 , … a m ) (a_1, a_2, a_3, \dots a_m) (a1,a2,a3,…am)和 ( b 1 , b 2 , b 3 , … b n ) (b_1, b_2, b_3, \dots b_n) (b1,b2,b3,…bn)。试编写一个函数,将数组中两个顺序表的位置互换,即将 ( b 1 , b 2 , b 3 , … b n ) (b_1, b_2, b_3, \dots b_n) (b1,b2,b3,…bn)放在 ( a 1 , a 2 , a 3 , … a m ) (a_1, a_2, a_3, \dots a_m) (a1,a2,a3,…am)前面。
输入样例: 2 3 1 2 3 4 5 3 4 1 2 3 4 5 6 7 0 0 输出样例: 3 4 5 1 2 4 5 6 7 1 2
9.
输入样例: 5 3 4 1 6 7 6 5 2 7 9 3 6 0 输出样例:
10.
输入样例: 5 3 4 1 6 7 6 5 2 7 9 3 6 0 输出样例:
11.
输入样例: 5 3 4 1 6 7 6 5 2 7 9 3 6 0 输出样例:
12.
输入样例: 5 3 4 1 6 7 6 5 2 7 9 3 6 0 输出样例:
13.
输入样例: 5 3 4 1 6 7 6 5 2 7 9 3 6 0 输出样例:
14.
输入样例: 5 3 4 1 6 7 6 5 2 7 9 3 6 0 输出样例:
这篇关于王道数据结构编程题(顺序表)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?