当前位置：网站首页>Wang Dao Chapter II linear table exercises
Wang Dao Chapter II linear table exercises
2022-06-13 04:59:00 【Be nice 123】
P17 Comprehensive application questions
bool DeleteMin(SqList &L,ElemType &min){
if(L.length==0){
printf(" Sequence table is empty \n");
return false;
}
else{
// Find the position of the smallest element first
min=L.data[0];
int index=0;// The subscript of the smallest element in the array
for(int i=1;i<L.length;i++){
if(L.data[i]<min){
min=L.data[i];
index=i;
}
}
/* if(index == L.length-1){// Explain that this is the last element L.length--; return true; } else{*/
L.data[index]=L.data[L.length-1];// Fill in the last element
return true;
//}
}
}
bool ReverseList(SqList &L){
if(L.length==0){
printf(" Table empty \n");
return false;
}
Elemtype t;
for(int i=0;i<(L.length/2);i++){
t=L.data[L.length-1-i];
L.data[L.length-1-i]=L.data[i];
L.data[i]=t;
}
return true;
}
use k Record sequence table L Middle is not equal to x Number of elements of ( That is, the number of elements to be saved ), Edge scan L Edge statistics k, And will not equal x Move the element forward k A place , Last modified L The length of
bool DeleteX(SqList &L,Elemtype x){
if(L.length==0){
printf(" Table empty \n");
return false;
}
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;//@@@
}
This solution can ignore the ascending and descending order of the ordered table , But it doesn't take advantage of ordered tables
bool DeleteStoT(SqList &L, Elemtype s,Elemtype t){
if(s>=t || L.length==0){
printf("Error\n");
return false;
}
int k=0;
for(int i=0;i<L.length;i++){
if(!(L.data[i] >= s && L.data[i] <= t)){
// Elements that do not meet the deletion criteria are moved forward k A place , Last modified L The length of
L.data[k]=L.data[i];
k++;
}
}
L.length=k;
return true;
}
solution 2： But the following answers are in ascending order by default …
bool DeleteStoT(SqList &L, Elemtype s,Elemtype t){
if(s>=t || L.length==0){
printf("Error\n");
return false;
}
int i,j;
for(i=0;i<L.length && L.data[i]<s;i++);// Find the first >=s The location of the elements of
if(i>=L.length){
return false;// All elements are <s;
}
for(j=i;j<L.length && L.data[j]<=t;j++);// Find the first >t The location of the elements of
for(;j<L.length;i++,j++){
L.data[i]=L.data[j];
}
L.length=i;
return true;
}
bool DeleteStoT(SqList &L, Elemtype s,Elemtype t){
if(s>=t || L.length==0){
printf("Error\n");
return false;
}
int k=0;
for(int i=0;i<L.length;i++){
if(!(L.data[i] >= s && L.data[i] <= t)){
// Elements that do not meet the deletion criteria are moved forward k A place , Last modified L The length of
L.data[k]=L.data[i];
k++;
}
}
L.length=k;
return true;
}
bool DeleteSame(SqList &L){
if(L.length==0){
printf("Error\n");
return false;
}
int k=0;
for(int i=1;i<L.length;i++){
if(L.data[i] != L.data[k])){
// If the following elements are different from the previous elements, add k in
L.data[++k]=L.data[i];
}
}
L.length=k+1;// because k Represents array subscript
return true;
}
bool MergeOrderedList(SqList A,SqList B,SqList &C){
if(A.length+B.length > C.maxsize){
return false;
}
int i,j,k;
k=0;
for(i=0,j=0;i<A.length && j<B.length;){
if(A.data[i]<B.data[j]){
C.data[k++]=A.data[i++];
}else{
C.data[k++]=B.data[j++];
}
}
while(i<A.length){
C.data[k++]=A[i++];
}
while(j<B.length){
C.data[k++]=B[j++];
}
C.length=k;
return true;
}
bool ExchangeAB(int A[],int m,int n){
int i,j;
i=m-1;
j=m+n-1;
int t;
for(;i>=0;i--,j--){
t=A[i];
A[i]=A[j];
A[j]=t;
}
return true;
}
// Binary search
void FindOrInsert(List &L,Elemtype x){
int low=0,high=L.length-1;
int mid;
while(low < high){
mid=(low+high)/2;
if(L.data[mid] == x)
break;
if(L.data[mid] < x){
low=mid+1;
}else{
high=mid-1;
}
}
if(L.data[mid]==x && mid != L.length-1){
// Found and not the last element , Then swap positions with the next element
Elemtype t=L.data[mid+1];
L.data[mid+1]=L.data[mid];
L.data[mid]=t;
}
if(low > high){
for(int i=L.length-1; i>high;i--){
A[i+1]=A[i];
}
A[i+1]=x;
A.length++;
}
}
// My solution And the 8 It's like , I feel this solution is better
#include<stdio.h>
bool ExchangeAB(int A[],int m,int n){
int i,j;
i=m-1;
j=m+n-1;
int t;
for(;i>=0;i--,j--){
t=A[i];
A[i]=A[j];
A[j]=t;
}
return true;
}
int main(){
int a[10]={
1,2,3,4,5,6,7,8,9,10};
ExchangeAB(a,4,6);
for(int i=0;i<10;i++){
printf("%d ",a[i]);
}
}
Official answer
- The basic idea of algorithm , Think of this as an array ab Convert to array ba(a Represents the front of the array p Elements ,b Represents the remaining... In the array n-p Elements ), First the a Inversion , then b Inversion , Then the results obtained above are inversed as a whole
- Code
- Time complexity O(n), Spatial complexity O(1)
void Reverse(int R[], int from, int to){
int i,temp;
for(i=0;i <(to-from+1)/2;i++){
temp=R[i+from];
R[i+from]=R[to-i];
R[to-i]=temp;
}
}
void Converse(int R[], int n, int p){
if(p>=n){
p=p%n;
}
Reverse(R,0,p-1);
Reverse(R,p,n-2);
Reverse(R,0,n-1);
}
#include<stdio.h>
int M_Search(int A[],int B[],int n){
int s1=0,d1=n-1,s2=0,d2=n-1;
int m1,m2;
while(s1 != d1 || s2!=d2 ){
// Personally, I think it's OK to keep one here
m1=(s1+d1)/2;
m2=(s2+d2)/2;
if(A[m1] == B[m2])
return A[m1];
if(A[m1]<B[m2]){
//
if((s1+d1)%2==0){
// Odd length
s1=m1;
d2=m2;
}else{
s1=m1+1;
d2=m2;
}
}
else{
//A[m1]>B[m2]
if((s2+d2)%2==0){
s2=m2;
d1=m1;
}else{
d1=m1;
s2=m2+1;
}
}
}
return A[s1]<B[s2]?A[s1]:B[s2];
}
int main(){
int a[]={
11,13,15,17,19};
int b[]={
2,4,5,8,20};
int len = sizeof(a)/sizeof(int);
printf("len = %d\n\n",len);
int mid = M_Search(a,b,len);
printf("%d",mid);
return 0;
}
Remember that the main element is p
Because the number of candidate primary elements is greater than half of the total number , namely >= n/2+1. So if there is a primary element, its count It must be >1. The analysis is as follows ：
- Suppose the total number is an even number , Of the candidate primary element count In the worst case, the candidate primary elements are evenly distributed in the array , Then because the total number is even and the number of main elements is >= n/2+1, So in the worst case, it must be p In the middle of the array, there are two consecutive positions p Together , So at worst count It must be greater than 1 .
- Suppose the total number is an odd number , At worst m It is distributed one by one , And the beginning and end of the array are m, So in this worst case count It must be greater than 1 .
- Sum up , It can be used count This clever way to determine whether there is a primary element . Note that the number of primary elements is required to be greater than half of the total number , Then use this condition to figure out the features .
4. Of course , The main element must have count>=1; however count>=1 But not necessarily the main element , So finally, we need to count this count>=1 How many elements are there , whether >=n/2+1;
#include<stdio.h>
int MainElement(int A[],int n){
int e,count=1;
e=A[0];
for(int i=0;i<n;i++){
if(A[i]==e){
count++;
}
else{
if(count > 0){
count--;
}
else{
e=A[i];
count=1;
}
}
}
if(count > 0){
count =0;
for(int i=0;i<n;i++){
if(A[i]==e){
count++;
}
}
}
if(count > n/2 ){
return e;
}
return -1;
}
int main(){
int a[8]={
0,5,5,3,5,7,5,5};
int b[8]={
0,5,5,3,5,1,5,7};
int maina=MainElement(a,8);
int mainb=MainElement(b,8);
printf("maina=%d\n\nmainb=%d\n\n",maina,mainb);
return 0;
}
The number of elements in the array is n, from 1 Start to check to n, If you don't find anything, you've found it , But the time complexity is O(n^2)
#include<stdio.h>
int MinInteger(int A[],int n){
int i,j;
for(i=1;i<=n;i++){
int flag=0;
for(j=0;j<n;j++){
if(i == A[j]){
flag=1;// Description find and i Same
break;
}
}
if(j==n && flag==0){
// If you find the last one that hasn't been found and i same A[j], Exit loop
if(i <= n)
return i;
else
return i+1;
}
}
}
int main(){
int a[8]={
1,2,3,4,5,6,8,7};
int b[8]={
0,5,5,3,5,1,5,7};
int x=MinInteger(a,8);
int y=MinInteger(b,8);
printf("x=%d\n\ny=%d\n\n",x,y);
return 0;
}
The standard answer
memset Function to initialize memory blocks by bytes , So you can't use it to int The array is initialized to 0 and -1 Other values （ Unless the high and low bytes of the value are the same ）
Space for time
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int MinInteger(int A[],int n){
int i,*B;
B=(int*)malloc(sizeof(int) * n);
memset(B,0,sizeof(int)*n);
for(i=0;i<n;i++){
if(A[i]>0 && A[i]<=n)
B[A[i]-1]=1;
}
for(i=0;i<n;i++){
if(B[i]==0)
break;
}
return i+1;
}
int main(){
int a[8]={
1,2,3,4,5,6,8,7};
int b[8]={
0,5,5,3,5,1,5,7};
int x=MinInteger(a,8);
int y=MinInteger(b,8);
printf("x=%d\n\ny=%d\n\n",x,y);
return 0;
}
Violent solution
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int MinDistance(int A[],int a,int B[],int b,int C[],int c){
int mins=abs(A[0]-B[0])+abs(A[0]-C[0])+abs(B[0]-C[0]);
int group[3]={
A[0],B[0],C[0]};
int sum;
for(int i=0;i<a;i++)
for(int j=0;j<b;j++)
for(int k=0;k<c;k++){
sum=abs(A[i]-B[j])+abs(A[i]-C[k])+abs(C[k]-B[j]);
if(sum<mins){
mins=sum;
group[0]=A[i];
group[1]=B[j];
group[2]=C[k];
}
}
printf("tuple is: ");
for(int i=0;i<3;i++)
printf("%d ",group[i]);
return mins;
}
int main(){
int S1[3]={
-1,0,9};
int S2[4]={
-25,-10,10,11};
int S3[5]={
2,9,17,30,41};
int d=MinDistance(S1,3,S2,4,S3,5);
printf("\n");
printf("%d\n",d);
return 0;
}
The standard answer ：
Why should we put the subscript of the minimum value +1, Because if you put the subscript of a non minimum value +1, Obtained Distance It will only be bigger than the original .
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
bool isMin(int a,int b,int c){
//a Is it the smallest one
if(a<=b && a<=c)
return true;
else
return false;
}
int MinDistance(int A[],int a,int B[],int b,int C[],int c){
int group[3]={
A[0],B[0],C[0]};
int i,j,k,d;
int mind=abs(A[0]-B[0])+abs(A[0]-C[0])+abs(B[0]-C[0]);
i=j=k=0;
for(;i<a && j<b && k<c;){
d=abs(A[i]-B[j])+abs(A[i]-C[k])+abs(B[j]-C[k]);
if(d < mind){
mind = d;
group[0]=A[i];group[1]=B[j];group[2]=C[k];
}
if(isMin(A[i],B[j],C[k])){
// If A[i] The smallest of the three
i++;
}
else if(isMin(B[j],C[k],A[i])){
j++;
}
else{
k++;
}
}
printf("tuple is: ");
for(int p=0;p<3;p++){
printf("%d ",group[p]);
}
printf("\n");
return mind;
}
int main(){
int S1[3]={
-1,0,9};
int S2[4]={
-25,-10,10,11};
int S3[5]={
2,9,17,30,41};
int d=MinDistance(S1,3,S2,4,S3,5);
printf("\n");
printf("%d\n",d);
return 0;
}
边栏推荐
- Internet people a few years ago vs Internet people today
- 1.2 differences caused by keywords
- Logical point
- Mysql8.0.13 installation tutorial (with pictures)
- C language exercise 1
- Draw a hammer
- Clause 27: alternatives to overloading with familiar universal reference types
- Clause 30: be familiar with the failure of perfect forwarding
- Analysis on the similarities and differences of MVC, MVP and mvvc
- Ruoyi cloud startup tutorial (hand-held graphics)
猜你喜欢
What is the saturate operation in opencv
Section 7 - structures
Ruoyi cloud startup tutorial (hand-held graphics)
Advantages of win8.1 and win10
QT signal is automatically associated with the slot
PostgreSQL Guide: Insider exploration (Chapter 7 heap tuples and index only scanning) - Notes
Logical point
![[LeetCode]-二分查找](/img/7f/7d1f616c491c6fb0be93f591da6df1.png)
[LeetCode]-二分查找
![[try to hack] upload labs (temporarily write to 12)](/img/df/dbb78121f7428e25ffb73cfc43ce1b.png)
[try to hack] upload labs (temporarily write to 12)
Spice story
随机推荐
What is the saturate operation in opencv
QT signal is automatically associated with the slot
E - Lucky Numbers
Autumn wind, dust, youth
Section 8 - Practical commissioning techniques
自动评教脚本使用的配置
Sampo Lock
详解OpenCV的函数cv::add(),并附各种情况的示例代码和运行结果
SQL notes
Cesium:cesiumlab makes image slices and loads slices
Conception d'un système basé sur MVC avec javaswing JDBC
How to use redis
Elliptic curve encryption
Avantages de win8.1 et win10
Force buckle 92 Reverse linked list II
Section 3 - functions
rust编程-链表：使用struct实现链表，使用堆合并k个升序链表，自定义Display
Explain the role of key attribute in V-for
C language learning log 1.17
Spread your wings and soar