0 preparation
How to use: copy the code in each question to the online running website above
Chapter 1: sequential representation of linear tables
01
Title: suppose the sequence table is not empty. Find the minimum value and its subscript from the sequence table and return it by reference
Idea:
① Application variable value, pos initialization value is the value of the first element of the sequence table, pos=0
② Starting from the second bit of the sequence table, when an element smaller than value is encountered, value is updated as the current element, and pos is the subscript of the current element
#define MaxSize 50
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
//Print out array elements separated by commas
void printList(SqList L) {
for(int i = 0; i < L.length; i++) {
cout << L.data[i] << ", ";
}
cout << endl;
}
// Number represents the number of elements in the array, and l represents the number saved in the L linked list
// The range of the array is 1 ~ 100
SqList getRandomSqList(int number) {
SqList L;
L.length = number;
srand((unsigned)time(NULL));
for(int i = 0; i < number;i++ ) {
int val = rand() % 100;
L.data[i] = val;
// cout << number << "\t";
}
// cout << endl;
return L;
}
// Assuming that the sequence table is not empty, find the smallest one from the sequence table and its subscript, and return it by reference
void findMin(SqList &L, ElemType &value, int &pos) {
// The value of the first element in the table
value = L.data[0];
pos = 0;
// Start from the second position
for(int i = 1; i < L.length; i++) {
// Smaller updates encountered
if(L.data[i] < value) {
value = L.data[i];
pos = i;
}
}
// After exiting
// pos: is the subscript of the smallest element in the array
// Value: is the value of the smallest element
}
//Test findMin function
void test_findMin() {
SqList L = getRandomSqList(10);
printList(L);
cout << "--------------------------------" << endl;
ElemType value;
int pos;
findMin(L, value, pos);
cout << "Minimum:" << value << ",Subscript:" << pos << endl;
}
int main() {
test_findMin();
return 0;
}02
Title: delete the element with the minimum value from the sequence table (assuming unique) and return the value of the deleted element by the function. The empty position is filled by the last element. If the sequence table is empty, an error message will be displayed and exit
Thought:
① When the table is empty: Return
② Table is not empty
1: Minimum element found
2: Then cover with the footer element and subtract 1 from the table length
#define MaxSize 50
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
//Print out array elements separated by commas
void printList(SqList L) {
for(int i = 0; i < L.length; i++) {
cout << L.data[i] << ", ";
}
cout << endl;
}
// Number represents the number of elements in the array, and l represents the number saved in the L linked list
// The range of the array is 1 ~ 100
SqList getRandomSqList(int number) {
SqList L;
L.length = number;
srand((unsigned)time(NULL));
for(int i = 0; i < number;i++ ) {
int val = rand() % 100;
L.data[i] = val;
// cout << number << "\t";
}
// cout << endl;
return L;
}
// Assuming that the sequence table is not empty, find the smallest one from the sequence table and its subscript, and return it by reference
void findMin(SqList &L, ElemType &value, int &pos) {
// The value of the first element in the table
value = L.data[0];
pos = 0;
// Start from the second position
for(int i = 1; i < L.length; i++) {
// Smaller updates encountered
if(L.data[i] < value) {
value = L.data[i];
pos = i;
}
}
// After exiting
// pos: is the subscript of the smallest element in the array
// Value: is the value of the smallest element
}
//Delete the element with the minimum value in the sequence table, and a function returns the minimum value. The vacated position is supplemented by the last element
bool delMin(SqList &L, ElemType &value) {
// Empty table judgment
if(L.length == 0) {
return false;
}
// Find minimum element, minimum element subscript
int pos;
findMin(L, value, pos);
// Last
int end = L.length - 1;
// Perform override
L.data[pos] = L.data[end];
// Table length minus one
L.length--;
return true;
}
//Test findMin function
void test_delMin() {
SqList L = getRandomSqList(10);
printList(L);
cout << "--------------------------------" << endl;
ElemType value;
int value1;
delMin(L, value1);
cout << "Minimum:" << value1 << endl;
cout << "--------------------------------" << endl;
printList(L);
}
int main() {
test_delMin();
return 0;
}03
Title: exchanging ab element values
Thought:
Apply for variable C, first let c = a, then let a = b, then let b = c, and the exchange is completed
#define MaxSize 50
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
//Print out array elements separated by commas
void printList(SqList L) {
for(int i = 0; i < L.length; i++) {
cout << L.data[i] << ", ";
}
cout << endl;
}
// Number represents the number of elements in the array, and l represents the number saved in the L linked list
// The range of the array is 1 ~ 100
SqList getRandomSqList(int number) {
SqList L;
L.length = number;
srand((unsigned)time(NULL));
for(int i = 0; i < number;i++ ) {
int val = rand() % 100;
L.data[i] = val;
// cout << number << "\t";
}
// cout << endl;
return L;
}
//Exchange the value of ab
void swap(ElemType &a, ElemType &b) {
ElemType c = a;
a = b;
b = c;
}
void test_swap() {
ElemType a = 10, b = 20;
cout << "a = " << a << ", b = " << b << endl;
swap(a, b);
cout << "a = " << a << ", b = " << b << endl;
}
int main() {
test_swap();
return 0;
}04
Title: design an efficient algorithm to reverse all elements of the sequential Table L, requiring the spatial complexity O(1) of the algorithm
Idea: double pointer, exchange n/2 times
① The table length is even, and the head and tail are exchanged
② The table length is an odd number, and the middle number does not need to be exchanged
#define MaxSize 50
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
//Print out array elements separated by commas
void printList(SqList L) {
for(int i = 0; i < L.length; i++) {
cout << L.data[i] << ", ";
}
cout << endl;
}
// Number represents the number of elements in the array, and l represents the number saved in the L linked list
// The range of the array is 1 ~ 100
SqList getRandomSqList(int number) {
SqList L;
L.length = number;
srand((unsigned)time(NULL));
for(int i = 0; i < number;i++ ) {
int val = rand() % 100;
L.data[i] = val;
// cout << number << "\t";
}
// cout << endl;
return L;
}
//Exchange the value of ab
void swap(ElemType &a, ElemType &b) {
ElemType c = a;
a = b;
b = c;
}
//Inverting all elements of the sequence table L requires the spatial complexity of the algorithm to be O(1)
void reverse(SqList &L) {
for(int i = 0; i < L.length/2; i++) {
// End element subscript
int end = L.length - i - 1;
// exchange
swap(L.data[i], L.data[end]);
}
}
void test_reverse() {
SqList L = getRandomSqList(11);
cout << "surface L:";
printList(L);
cout << "--------------------------------" << endl;
reverse(L);
cout << "inverse L:";
printList(L);
}
int main() {
test_reverse();
return 0;
}05
Title: use the sequence table to realize simple selection and sorting
Thought:
① The ith trip: the final position of an element can be determined in each trip, and the element with the smallest keyword can be selected from L[i...n] to exchange with L[i]
② After n-1 sorting, the whole sorting table can be ordered
#define MaxSize 50
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
//Print out array elements separated by commas
void printList(SqList L) {
for(int i = 0; i < L.length; i++) {
cout << L.data[i] << ", ";
}
cout << endl;
}
// Number represents the number of elements in the array, and l represents the number saved in the L linked list
// The range of the array is 1 ~ 100
SqList getRandomSqList(int number) {
SqList L;
L.length = number;
srand((unsigned)time(NULL));
for(int i = 0; i < number;i++ ) {
int val = rand() % 100;
L.data[i] = val;
// cout << number << "\t";
}
// cout << endl;
return L;
}
//Exchange the value of ab
void swap(ElemType &a, ElemType &b) {
ElemType c = a;
a = b;
b = c;
}
//Simple selection and sorting with sequence table
//Found subscript start End, and returns
int findMinIndex(SqList A, int start, int end) {
int minIndex = start;
for(int j = start+1; j <= end; j++) {
if(A.data[minIndex] > A.data[j]) {
minIndex = j;
}
}
return minIndex;
}
//Select sort
//The table is divided into two parts, orderly in the front and disordered in the back
//Find the smallest element between i~end. If the value of the smallest element is not equal to i, exchange i with the smallest element
//i from 0 to length-1
//A must be referenced, otherwise the array and length will be copied
void selectSort(SqList &A) {
for(int i = 0; i < A.length; i++) {
// In the i-th pass, find the subscript of the minimum value of the unordered part
int minIndex = findMinIndex(A, i, A.length-1);
// Put the minimum value of the unordered part into the tail of the ordered part
if(minIndex != i) {
swap(A.data[i], A.data[minIndex]);
}
}
}
void test_selectSort() {
SqList L = getRandomSqList(10);
cout << "surface L:";
printList(L);
cout << "--------------------------------" << endl;
selectSort(L);
cout << "order L:";
printList(L);
}
int main() {
test_selectSort();
return 0;
}06
Title: for the sequential Table L with length N, write an algorithm with time complexity O(n) and space complexity O(1). The algorithm deletes all data elements with value x in the linear table
Idea: traverse the whole table and record the number of elements that are not equal to x, assuming K. Put the element not equal to X on the subscript k, and finally modify the table length to K
#define MaxSize 50
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
//Print out array elements separated by commas
void printList(SqList L) {
for(int i = 0; i < L.length; i++) {
cout << L.data[i] << ", ";
}
cout << endl;
}
// Number represents the number of elements in the array, and l represents the number saved in the L linked list
// The range of the array is 1 ~ 100
SqList getRandomSqList(int number) {
SqList L;
L.length = number;
srand((unsigned)time(NULL));
for(int i = 0; i < number;i++ ) {
int val = rand() % 100;
L.data[i] = val;
// cout << number << "\t";
}
// cout << endl;
return L;
}
//For the sequential Table L with length N, time complexity O(n) and space complexity O(1), delete all x data elements in L
//Table L is divided into three parts. The first part is the elements that are not 20, the second part is 20, and the third part is the elements to be sorted
//Because the second part is logical, it is covered in practice
void delX(SqList &L, ElemType x) {
// The number of elements whose value in the record table is not equal to x
// It's also the length of the watch
int k = 0;
// Traversal, execute processing
for(int i = 0; i < L.length; i++) {
if(L.data[i] != x) {
// Place the current element at the subscript k
L.data[k] = L.data[i];
// k increment
k += 1;
}
// else: elements equal to x are skipped directly
}
// The meter length is finally equal to k
L.length = k;
}
void test_delX() {
SqList L = getRandomSqList(10);
// Randomly set the three elements in L to 20
for(int i = 0; i < 3; i++) {
L.data[rand() % 10] = 20;
}
cout << "surface L:";
printList(L);
cout << "--------------------------------" << endl;
delX(L, 20);
cout << "surface L:";
printList(L);
}
int main() {
test_delX();
return 0;
}07
Title: delete all elements whose bit order is between I and j from the sequence table
Idea: if i and j are illegal, return false. Otherwise, move the elements after bit order J to the position starting from bit order i in turn. Finally, modify the table length to L.length-(j-i+1) and return true
#define MaxSize 50
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
//Print out array elements separated by commas
void printList(SqList L) {
for(int i = 0; i < L.length; i++) {
cout << L.data[i] << ", ";
}
cout << endl;
}
// Number represents the number of elements in the array, and l represents the number saved in the L linked list
// The range of the array is 1 ~ 100
SqList getRandomSqList(int number) {
SqList L;
L.length = number;
srand((unsigned)time(NULL));
for(int i = 0; i < number;i++ ) {
int val = rand() % 100;
L.data[i] = val;
// cout << number << "\t";
}
// cout << endl;
return L;
}
//Delete the elements between bit orders i and j from the sequence table L
//The bit order is from 1 to length
//L is divided into three segments, in which 0~i-2 is the first segment, i-1~j-1 is the second segment and j~length-1 is the third segment
//The first paragraph is plus one, the third paragraph is minus one, and the second paragraph does not need to be managed
bool deli2j(SqList &L, int i, int j) {
// First, judge the legitimacy of i and j
if(i < 1 || j > L.length || j < i) {
return false;
}
// Bit order conversion to subscript
i--;
j--;
// Move indexJ out element to indexI
// Stop at end of table
// Move an element back one bit
for(int indexI = i, indexJ = j+1; indexJ < L.length; indexI++, indexJ++) {
// move
L.data[indexI] = L.data[indexJ];
}
// Modify table length
L.length -= j - i + 1;
return true;
}
void test_deli2j() {
SqList L = getRandomSqList(16);
cout << "Note that there is a gap of 1 between bit order and subscript" << endl;
cout << "surface L:";
printList(L);
cout << "----------------------------------------------------------------" << endl;
cout << "Original table length:" << L.length << endl;
deli2j(L, 4, 8);
cout << "Now watch length:" << L.length << endl;
cout << "surface L:";
printList(L);
}
int main() {
test_deli2j();
return 0;
}08
Title: find out all elements with values between the given values s and t in the ordered table, and return the subscript range
Idea: determine the subscript of an element with a value between [s,t]
① Traversing from beginning to end, the first element whose value is greater than or equal to s
② Traversing from beginning to end, the first element whose value is greater than t is the previous element
#define MaxSize 50
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
//Print out array elements separated by commas
void printList(SqList L) {
for(int i = 0; i < L.length; i++) {
cout << L.data[i] << ", ";
}
cout << endl;
}
// Number represents the number of elements in the array, and l represents the number saved in the L linked list
// The range of the array is 1 ~ 100
SqList getRandomSqList(int number) {
SqList L;
L.length = number;
srand((unsigned)time(NULL));
for(int i = 0; i < number;i++ ) {
int val = rand() % 100;
L.data[i] = val;
// cout << number << "\t";
}
// cout << endl;
return L;
}
//Exchange the value of ab
void swap(ElemType &a, ElemType &b) {
ElemType c = a;
a = b;
b = c;
}
void bubbSort(SqList &L) {
int n = L.length;
for(int i = 0; i < n - 1; i++) {
// Used to mark whether this round of bubble sorting has been exchanged
bool isBubble = false;
// Bubbling from back to front
for(int j = n - 1; j > i; j--) {
// If the front is larger, it needs to be exchanged
if(L.data[j - 1] > L.data[j]) {
swap(L.data[j - 1], L.data[j]);
isBubble = true;
}
}
// If there is no exchange, it proves to be in order
if(!isBubble) {
return;
}
}
}
//Find all elements with values between the given s and t (s < T is required) in the ordered order table, and return the subscript range
//Traversing from beginning to end, the subscript positions of s and t appear first
bool finds2t(SqList &L, ElemType s, ElemType t, int &start, int &end) {
// Legitimacy judgment
if(s >= t || L.length == 0) {
return false;
}
int indexS;
for(indexS = 0; indexS < L.length && L.data[indexS] < s; indexS++);
if(indexS >= L.length) {
return false;
}
int indexT;
for(indexT = indexS; indexT < L.length && L.data[indexT] <= t; indexT++);
start = indexS;
end = indexT - 1;
return true;
}
void test_finds2t() {
SqList L = getRandomSqList(10);
bubbSort(L);
cout << "surface L:";
printList(L);
cout << "--------------------------------" << endl;
ElemType s = 10, t = 40;
int start, end;
cout << "seek[" << s << ", " << t << "]Elements between: ";
bool isSuccess = finds2t(L, s, t, start, end);
cout << "[" << start << ", " << end << "]" << endl;
}
int main() {
test_finds2t();
return 0;
}09
Title: delete all elements whose values are between the given values s and t from the ordered sequence table. If s or t is unreasonable or the sequence table is empty, an error message will be displayed and the operation will exit
Thought:
① Ordered order table: the elements in the table are assumed to be increasing
② Determines the subscript of an element with a value between [s,t]
③ Execute interval deletion
#define MaxSize 50
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
//Print out array elements separated by commas
void printList(SqList L) {
for(int i = 0; i < L.length; i++) {
cout << L.data[i] << ", ";
}
cout << endl;
}
// Number represents the number of elements in the array, and l represents the number saved in the L linked list
// The range of the array is 1 ~ 100
SqList getRandomSqList(int number) {
SqList L;
L.length = number;
srand((unsigned)time(NULL));
for(int i = 0; i < number;i++ ) {
int val = rand() % 100;
L.data[i] = val;
// cout << number << "\t";
}
// cout << endl;
return L;
}
void bubbSort(SqList &L) {
int n = L.length;
for(int i = 0; i < n - 1; i++) {
// Used to mark whether this round of bubble sorting has been exchanged
bool isBubble = false;
// Bubbling from back to front
for(int j = n - 1; j > i; j--) {
// If the front is larger, it needs to be exchanged
if(L.data[j - 1] > L.data[j]) {
swap(L.data[j - 1], L.data[j]);
isBubble = true;
}
}
// If there is no exchange, it proves to be in order
if(!isBubble) {
return;
}
}
}
//Find all elements with values between the given s and t (s < T is required) in the ordered order table, and return the subscript range
//Traversing from beginning to end, the subscript positions of s and t appear first
bool finds2t(SqList &L, ElemType s, ElemType t, int &start, int &end) {
// Legitimacy judgment
if(s >= t || L.length == 0) {
return false;
}
int indexS;
for(indexS = 0; indexS < L.length && L.data[indexS] < s; indexS++);
if(indexS >= L.length) {
return false;
}
int indexT;
for(indexT = indexS; indexT < L.length && L.data[indexT] <= t; indexT++);
start = indexS;
end = indexT - 1;
return true;
}
//Delete the elements between bit orders i and j from the sequence table L
//The bit order is from 1 to length
//L is divided into three segments, in which 0~i-2 is the first segment, i-1~j-1 is the second segment and j~length-1 is the third segment
//The first paragraph is plus one, the third paragraph is minus one, and the second paragraph does not need to be managed
bool deli2j(SqList &L, int i, int j) {
// First, judge the legitimacy of i and j
if(i < 1 || j > L.length || j < i) {
return false;
}
// Bit order conversion to subscript
i--;
j--;
// Move indexJ out element to indexI
// Stop at end of table
// Move an element back one bit
for(int indexI = i, indexJ = j+1; indexJ < L.length; indexI++, indexJ++) {
// move
L.data[indexI] = L.data[indexJ];
}
// Modify table length
L.length -= j - i + 1;
return true;
}
//Delete all elements with values between S and t from the ordered order table. If s and t are unreasonable or the order table is empty, an error message will be displayed and the operation will be exited
bool dels2t(SqList &L, ElemType s, ElemType t) {
int start, end;
bool isSuccess;
isSuccess = finds2t(L, s, t, start, end);
if(!isSuccess) {
return false;
}
return deli2j(L, start+1, end+1);
}
void test_dels2t() {
SqList L = getRandomSqList(10);
bubbSort(L);
cout << "surface L:";
printList(L);
cout << "--------------------------------" << endl;
ElemType s = L.data[4], t = L.data[7];
cout << "delete[" << L.data[4] << "," << L.data[7] << "]Elements between" << endl;
dels2t(L, s, t);
cout << "Delete L:";
printList(L);
}
int main() {
test_dels2t();
return 0;
}10
Title: delete all elements with duplicate values from the ordered order table, so that the values of all elements in the table are different
Idea:
① Divide the table into table A and table B; Table A is the first half of the ordered sequence table, and table B is the second half of the table
② Initialization is that there is only one element in table A, that is, the first element of the ordered order table, and table B has the remaining n-1 elements
③ Compare the last element of table A with table B from the beginning. If there is no difference, add it to the tail of table A
④ Repeat ③ until table B is empty, and then modify the length of the new table to the length of table A
#define MaxSize 50
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
//Print out array elements separated by commas
void printList(SqList L) {
for(int i = 0; i < L.length; i++) {
cout << L.data[i] << ", ";
}
cout << endl;
}
// Number represents the number of elements in the array, and l represents the number saved in the L linked list
// The range of the array is 1 ~ 100
SqList getRandomSqList(int number) {
SqList L;
L.length = number;
srand((unsigned)time(NULL));
for(int i = 0; i < number;i++ ) {
int val = rand() % 100;
L.data[i] = val;
// cout << number << "\t";
}
// cout << endl;
return L;
}
bool delSame(SqList &L) {
// Table empty does not exist delete
if(L.length == 0) {
return false;
}
// Pointers indexed in tables A,B
int indexA, indexB;
for(indexA = 0, indexB = 1; indexB < L.length; indexB++) {
// If different elements appear, they should be put on the tail of table A
if(L.data[indexA] != L.data[indexB]) {
L.data[++indexA] = L.data[indexB];
}
}
// The final table length is the length of table A
L.length = indexA + 1;
// Whether to add 1 Be sure to make sure that the current indexA is only the last element of table A (plus 1)
// Or the next element that points to the last element of table A (without 1)
return true;
}
void test_delSame() {
SqList L;
ElemType A[] = {1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5};
L.length = sizeof(A) / sizeof(ElemType);
for(int i = 0; i < L.length; i++) {
L.data[i] = A[i];
}
cout << "surface L:";
printList(L);
cout << "--------------------------------" << endl;
delSame(L);
printList(L);
}
int main() {
test_delSame();
return 0;
}