-
数据结构与算法课后题-第二章(顺序表)
第二章
01题目，存储相对紧凑，所以存储的密度大。
04题目，顺序表可以按照序号随机存取，时间的复杂度为O(1)。
第7题目分析
#includeusing namespace std; #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; //-----------------代码核心--------------------// bool Del_Min(SqList &L, ElemType& value) { if (L.length == 0) return false; value = L.data[0]; int pos = 0; for (int i = 1; i < L.length; i++) { if (value > L.data[i]) { value = L.data[i]; pos = i; } } L.data[pos] = L.data[L.length - 1]; L.length--; return true; } //---------------------------------------------------// int main(void) { SqList L; //初始化顺序表 //... int value = 0; Del_Min(L, value); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
#include#include using namespace std; #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; //1 2 3 4 5 6 ---- 6 5 4 3 2 1 length = 6 // 1 2 3 4 5 6 7 ---- 7 6 5 4 3 2 1 length = 7 //-------------------------代码核心------------------------// bool reverse(SqList& L) { ElemType temp; //辅助变量 for (int i = 0; i <(L.length) / 2; i++) { temp = L.data[i]; L.data[i] = L.data[L.length - 1 - i]; L.data[L.length - 1 - i] = temp; } return true; } //-------------------------代码核心------------------------// int main(void) { SqList L; //初始化顺序表 L.length = 6; for (int i = 0; i < L.length; i++) L.data[i] = i; reverse(L); for (int i = 0; i < L.length; i++) //cout << L.data[i] << endl; printf("L.data[%d]=%d\n", i, L.data[i]); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
#include#include using namespace std; #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; //-------------------------代码核心------------------------// bool Delete_all_x_value(SqList& L, ElemType x) //1 2 3 3 4 5 { int k = 0; for (int i = 0; i < L.length; i++) { if (L.data[i] != x) { L.data[k] = L.data[i]; k++; } } L.length = k; return true; } //-------------------------代码核心------------------------// int main(void) { SqList L; //初始化顺序表 L.length = 6; L.data[0] = 1; L.data[1] = 2; L.data[2] = 3; L.data[3] = 3; L.data[4] = 4; L.data[5] = 5; int value = 3; Delete_all_x_value(L,value); for (int i = 0; i < L.length; i++) //cout << L.data[i] << endl; printf("L.data[%d]=%d\n", i, L.data[i]); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
#include#include using namespace std; #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; //-------------------------代码核心------------------------// //法1 //bool Delete_all_range_value(SqList& L, ElemType s, ElemType t) //1 2 3 3 4 5 //{ // int k = 0; // if (L.length == 0||s>=t) // return false; // for (int i = 0; i < L.length; i++) // { // if (L.data[i] < s|| L.data[i] > t) // { // L.data[k] = L.data[i]; // k++; // } // } // L.length = k; // return true; //} bool Delete_all_range_value(SqList& L, ElemType s, ElemType t) //1 2 3 3 4 5 { int i = 0, j = 0; if (L.length == 0||s>=t)//判断 return false; for (i = 0; i < L.length && L.data[i] < s; i++); //寻找大于或等于s的第一个元素 if(i>=L.length) //所有的数都比s小 return false; for (j = i; j < L.length && L.data[j] <= t; j++);//寻找大于t的第一个元素 for (; j < L.length; i++, j++) L.data[i] = L.data[j]; L.length = i; return true; } //-------------------------代码核心------------------------// int main(void) { SqList L; //初始化顺序表 L.length = 6; L.data[0] = 1; L.data[1] = 2; L.data[2] = 3; L.data[3] = 3; L.data[4] = 4; L.data[5] = 5; int s = 2; int t = 3; Delete_all_range_value(L, s, t); for (int i = 0; i < L.length; i++) { printf("L.data[%d]=%d\n", i, L.data[i]); } printf("L.length=%d\n", L.length); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
#include#include using namespace std; #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; //-------------------------代码核心------------------------// bool Delete_all_range_value(SqList& L, ElemType s, ElemType t) //1 2 3 3 4 5 { int k = 0; if (L.length == 0||s>=t) return false; for (int i = 0; i < L.length; i++) { if (L.data[i]<s|| L.data[i] > t) { L.data[k] = L.data[i]; k++; } } L.length = k; return true; } //-------------------------代码核心------------------------// int main(void) { SqList L; //初始化顺序表 L.length = 6; L.data[0] = 1; L.data[1] = 2; L.data[2] = 3; L.data[3] = 3; L.data[4] = 4; L.data[5] = 5; int s = 2; int t = 3; Delete_all_range_value(L, s, t); for (int i = 0; i < L.length; i++) { printf("L.data[%d]=%d\n", i, L.data[i]); } printf("L.length=%d\n", L.length); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
#include#include using namespace std; #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; //-------------------------代码核心------------------------// bool Delete_same(SqList& L) //1 2 2 2 3 3 3 3 4 4 4 5 5 5 { if(L.length==0) return false; int i = 0, j = 0; for (i = 0, j = 1; j < L.length; j++) { if (L.data[i] != L.data[j]) L.data[++i] = L.data[j]; } L.length = i + 1; return true; } //-------------------------代码核心------------------------// int main(void) { SqList L; //初始化顺序表 L.length = 14; L.data[0] = 1; L.data[1] = 2; L.data[2] = 2; L.data[3] = 2; L.data[4] = 3; L.data[5] = 3; L.data[6] = 3; L.data[7] = 3; L.data[8] = 4; L.data[9] = 4; L.data[10] = 4; L.data[11] = 5; L.data[12] = 5; L.data[13] = 5; Delete_same(L); for (int i = 0; i < L.length; i++) { printf("L.data[%d]=%d\n", i, L.data[i]); } printf("L.length=%d\n", L.length); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
#include#include using namespace std; #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; //-------------------------代码核心------------------------// bool merge(SqList A, SqList B, SqList &C) { if (A.length + B.length > MaxSize) return false; int i = 0, j = 0, k = 0; while (i < A.length && j < B.length) { if (A.data[i] <= B.data[j]) C.data[k++] = A.data[i++]; else //B.data[j] <= A.data[j] C.data[k++] = B.data[j++]; } while (i < A.length) C.data[k++] = A.data[i++]; while (j < B.length) C.data[k++] = B.data[j++]; C.length = k; return true; } //-------------------------代码核心------------------------// int main(void) { SqList A; SqList B; SqList C;//合并后的顺序表 //初始化顺序表 //-------------L1-------------// A.length = 3; A.data[0] = 5; A.data[1] = 6; A.data[2] = 7; //-------------L2-------------// B.length = 4; B.data[0] = 1; B.data[1] = 2; B.data[2] = 3; B.data[3] = 4; merge(A, B, C); for (int i = 0; i < C.length; i++) { printf("L.data[%d]=%d\n", i, C.data[i]); } printf("L.length=%d\n", C.length); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
#include#include using namespace std; #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; //-------------------------代码核心------------------------// typedef int DataType; bool Reverse(DataType A[], int left, int right, int arraysize) { if (left >= right || right >= arraysize) return false; //0 1 2 3 4 5 //0 1 2 3 4 5 6 int mid = (left + right) / 2; //11 12 13 14 15 16 奇数 //21 22 23 24 25 26 27 偶数 for (int i = 0; i <= mid - left; i++) { DataType temp = A[left + i]; A[left + i] = A[right - i]; A[right - i] = temp; } } void Exchange(DataType A[], int m, int n, int arraysize) { Reverse(A, 0, m + n - 1, arraysize); Reverse(A, 0, n - 1, arraysize); Reverse(A, n, m + n - 1, arraysize); } //-------------------------代码核心------------------------// int main(void) { SqList A; SqList B; int arraysize = 50; int data[MaxSize] = { 0 }; //初始化顺序表 //-------------L1-------------// A.length = 3; data[0] = A.data[0] = 5; data[1] = A.data[1] = 6; data[2] = A.data[2] = 7; //-------------L2-------------// B.length = 4; data[3] = B.data[0] = 1; data[4] = B.data[1] = 2; data[5] = B.data[2] = 3; data[6] = B.data[3] = 4; Exchange(data, A.length,B.length, arraysize); for (int i = 0; i < A.length + B.length; i++) { printf("data[%d]=%d\n", i,data[i]); } printf("L.length=%d\n", A.length + B.length); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
#include#include using namespace std; #define ERROR 0; #define OK 1; #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; //-------------------------代码核心------------------------// bool SearchExchangeInsert(SqList& L, int x) { //折半查找法,这种办法所用的时间最少 int low = 0, high = L.length-1, mid=0; int temp = 0; while (low <= high) { mid = (low + high) / 2;//找出中间位置 if (L.data[mid] == x) break; else if (L.data[mid] < x) low = mid + 1; else high = mid - 1; } if (L.data[mid] == x && mid != L.length - 1) { cout << "data find"<<endl; temp = L.data[mid]; L.data[mid] = L.data[mid + 1]; L.data[mid + 1] = temp; } if (low > high) { cout << "data not find" << endl; int i = 0; for (i = L.length - 1; i > high; i--) L.data[i + 1] = L.data[i]; L.data[i + 1] = x; } return OK; } //-------------------------代码核心------------------------// int main(void) { SqList L; //初始化顺序表 //-------------L1-------------// L.length = 7; L.data[0] = 1; L.data[1] = 3; L.data[2] = 5; L.data[3] = 7; L.data[4] = 9; L.data[5] = 11; L.data[6] = 13; SearchExchangeInsert(L, 5); for (int i = 0; i < L.length; i++) { printf("data[%d]=%d\n", i, L.data[i]); } printf("L.length=%d\n", L.length); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
#include#include using namespace std; #define ERROR 0; #define OK 1; #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int length; }SqList; //-------------------------代码核心------------------------// bool Reverse(SqList& L, int left, int right) { int mid = (left + right) / 2; for (int i = 0; i <= mid - left; i++) { int temp = L.data[left + i]; L.data[left + i] = L.data[right - i]; L.data[right - i] = temp; } return OK; } void Converse(SqList& L, int p) { Reverse(L, 0, p - 1); Reverse(L, p, L.length - 1); Reverse(L, 0, L.length - 1); } //-------------------------代码核心------------------------// int main(void) { SqList L; //初始化顺序表 //-------------L1-------------// L.length = 7; L.data[0] = 1; L.data[1] = 2; L.data[2] = 3; L.data[3] = 4; L.data[4] = 5; L.data[5] = 6; L.data[6] = 7; Converse(L, 3); for (int i = 0; i < L.length; i++) { printf("data[%d]=%d\n", i, L.data[i]); } printf("L.length=%d\n", L.length); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
-
相关阅读:
彻底掌握Protobuf编码原理与实战
12代CPU启用SR-IOV vGPU，实现一台电脑当七台用
最好的RabbitMQ新手入门学习笔记，我们一起来学习
springboot基于Web的社区医院管理服务系统springboot025
python继承
IO 模型的演变
python-opencv视频中的人脸检测
tomcat
CentOS和Ubuntu命令行方式配置静态IP
C#学习中关于Visual Studio中ctrl+D快捷键（快速复制当前行）失效的解决办法
- 原文地址：https://blog.csdn.net/qq_41735476/article/details/132672723
