for Robot Artificial Inteligence

9. Array ADT represented problem solving

03 Jun 2020 | Algorithm

Searching in a Array

#include<stdio.h>
struct Array
{
  int A[10];
  int size;
  int length;
};
void Display(struct Array arr)
{
int i;
printf("\nElements are\n");
for(i=0;i<arr.length;i++)
printf("%d ",arr.A[i]);
}
void swap(int * x,int * y)
{
  int temp=* x;
  * x = * y;
  * y=temp;
}
int LinearSearch(struct Array *arr,int key)
{
  int i;
  for(i=0;i<arr->length;i++)
  {
    if(key==arr->A[i])
    {
      swap(&arr->A[i],&arr->A[0]);
      return i;
    }
  }
  return -1;
}
int main()
{
  struct Array arr1={2,23,14,5,6,9,8,12},10,8;
  // {}여기 더 붙여야한다.
  printf("%d",LinearSearch(&arr1,14));
  Display(arr1);
  return 0;
}

Binary Search in Array

#include<stdio.h>
struct Array
{
  int A[10];
  int size;
  int length;
};
void Display(struct Array arr)
{
  int i;
  printf("\nElements are\n");
  for(i=0;i<arr.length;i++)
    printf("%d ",arr.A[i]);
}
void swap(int * x,int *y)
{
  int temp=* x;
  * x=* y;
  * y=temp;
}
int BinarySearch(struct Array arr,int key)
{
  int l,mid,h;
  l=0;
  h=arr.length-1;
  while(l<=h)
  {
    mid=(l+h)/2;
    if(key==arr.A[mid])
      return mid;
    else if(key<arr.A[mid])
      h=mid-1;
    else
      l=mid+1;
  }
  return -1;
}
int RBinSearch(int a[],int l,int h,int key)
{
  int mid=0;
  if(l<=h)
  {
    mid=(l+h)/2;
    if(key==a[mid])
      return mid;
    else if(key<a[mid])
      return RBinSearch(a,l,mid-1,key);
  }
  else
    return RBinSearch(a,mid+1,h,key);
  return -1;
}
int main()
{
  struct Array arr1={2,3,9,16,18,21,28,32,35},10,9;
  // {}여기 더 붙여야한다.
  printf("%d",BinarySearch(arr1,16));
  Display(arr1);
  return 0;
}

Get Set Max Min on Array

#include<stdio.h>
struct Array
{
  int A[10];
  int size;
  int length;
};
void Display(struct Array arr)
{
  int i;
  printf("\nElements are\n");
    for(i=0;i<arr.length;i++)
      printf("%d ",arr.A[i]);
}
void swap(int *x,int *y)
{
  int temp=* x;
  * x=* y;
  * y=temp;
}
int Get(struct Array arr,int index)
{
  if(index>=0 && index<arr.length)
    return arr.A[index];
  return -1;
}
void Set(struct Array *arr,int index,int x)
{
  if(index>=0 && index<arr->length)
    arr->A[index]=x;
}
int Max(struct Array arr)
{
  int max=arr.A[0];
  int i;
  for(i=1;i<arr.length;i++)
  {
    if(arr.A[i]>max)
    max=arr.A[i];
  }
  return max;
}
int Min(struct Array arr)
{
  int min=arr.A[0];
  int i;
  for(i=1;i<arr.length;i++)
  {
    if(arr.A[i]<min)
    min=arr.A[i];
  }
  return min;
}
int Sum(struct Array arr)
{
  int s=0;
  int i;
  for(i=0;i<arr.length;i++)
    s+=arr.A[i];
  return s;
}
float Avg(struct Array arr)
{
return (float)Sum(arr)/arr.length;
}
int main()
{
  struct Array arr1={2,3,9,16,18,21,28,32,35},10,9;
  // {}여기 더 붙여야한다.
  printf("%d",Sum(arr1));
  Display(arr1);
  return 0;
}

Reversing Array

#include<stdio.h>
#include<stdlib.h>
struct Array
{
  int A[10];
  int size;
  int length;
};
void Display(struct Array arr)
{
  int i;
  printf("\nElements are\n");
  for(i=0;i<arr.length;i++)
    printf("%d ",arr.A[i]);
}
void swap(int *x,int *y)
{
    int temp=* x;
    * x=* y;
    * y=temp;
}
void Reverse(struct Array *arr)
{
    int * B;
    int i,j;
    B = new int[arr->length];
    for(i=arr->length-1,j=0;i>=0;i--,j++)
        B[j]=arr->A[i];
    for(i=0;i<arr->length;i++)
        arr->A[i]=B[i];
}
void Reverse2(struct Array *arr)
{
    int i,j;
    for(i=0,j=arr->length-1;i<j;i++,j--)
    {
        swap(&arr->A[i],&arr->A[j]);
    }
}
int main()
{
    struct Array arr1={2,3,9,16,18,21,28,32,35},10,9;
    // {}여기 더 붙여야한다.
    Reverse(&arr1);
    Display(arr1);
    return 0;
}

Checking if Array is sorted

#include<stdio.h>
#include<stdlib.h>
struct Array
{
  int A[10];
  int size;
  int length;
};
void Display(struct Array arr)
{
  int i;
  printf("\nElements are\n");
  for(i=0;i<arr.length;i++)
      printf("%d ",arr.A[i]);
}
int isSorted(struct Array arr)
{
  int i;
  for(i=0;i<arr.length-1;i++)
  {
    if(arr.A[i]>arr.A[i+1])
      return 0;
  }
  return 1;
}
int main()
{
  struct Array arr1={2,3,9,16,18,21,28,32,35},10,9;
  // {}여기 더 붙여야한다.
  printf("%d",isSorted(arr1));
  Display(arr1);
  return 0;
}

Merging 2 Arrays

#include<stdio.h>
#include<stdlib.h>
struct Array
{
    int A[10];
    int size;
    int length;
};
void Display(struct Array arr)
{
    int i;
    printf("\nElements are\n");
    for(i=0;i<arr.length;i++)
        printf("%d ",arr.A[i]);
}
struct Array* Merge(struct Array * arr1,struct Array * arr2)
{
    int i,j,k;
    i=j=k=0;
    struct Array * arr3 = new Array[20];
    while(i<arr1->length && j<arr2->length)
    {
        if(arr1->A[i]<arr2->A[j])
            arr3->A[k++]=arr1->A[i++];
        else
        arr3->A[k++]=arr2->A[j++];
    }
    for(;i<arr1->length;i++)
        arr3->A[k++]=arr1->A[i];
    for(;j<arr2->length;j++)
        arr3->A[k++]=arr2->A[j];
    arr3->length=arr1->length+arr2->length;
    arr3->size=10;
    return arr3;
}
int main()
{
    struct Array arr1={2,9,21,28,35},10,5;
    struct Array arr2={2,3,16,18,28},10,5;
    //{} 추가
    struct Array * arr3;
    arr3=Merge(&arr1,&arr2);
    Display(*arr3);
    return 0;
}

Set Operations on Arrays

#include<stdio.h>
#include<stdlib.h>
struct Array
{
    int A[10];
    int size;
    int length;
};
void Display(struct Array arr)
{
    int i;
    printf("\nElements are\n");
    for(i=0;i<arr.length;i++)
        printf("%d ",arr.A[i]);
}
struct Array* Union(struct Array * arr1,struct Array * arr2)
{
    int i,j,k;
    i=j=k=0;
    //struct Array * arr3=(struct Array * )malloc(sizeof(struct Array));
    struct Array * arr3= new Array[arr1->length*2];
    while(i<arr1->length && j<arr2->length)
    {
        if(arr1->A[i]<arr2->A[j])
            arr3->A[k++]=arr1->A[i++];
        else if(arr2->A[j]<arr1->A[i])
            arr3->A[k++]=arr2->A[j++];
        else
        {
            arr3->A[k++]=arr1->A[i++];
            j++;
        }
    }
    for(;i<arr1->length;i++)
        arr3->A[k++]=arr1->A[i];
    for(;j<arr2->length;j++)
        arr3->A[k++]=arr2->A[j];
        arr3->length=k;
        arr3->size=10;
    return arr3;
}
struct Array* Intersection(struct Array * arr1,struct Array* arr2)
{
    int i,j,k;
    i=j=k=0;
    //struct Array * arr3=(struct Array * )malloc(sizeof(struct Array));
    struct Array * arr3= new Array[arr1->length*2];
    while(i<arr1->length && j<arr2->length)
    {
        if(arr1->A[i]<arr2->A[j])
            i++;
        else if(arr2->A[j]<arr1->A[i])
            j++;
        else if(arr1->A[i]==arr2->A[j])
    {
        arr3->A[k++]=arr1->A[i++];
        j++;
    }
    }
    arr3->length=k;
    arr3->size=10;
    return arr3;
}
struct Array* Difference(struct Array* arr1,struct Array* arr2)
{
    int i,j,k;
    i=j=k=0;
    // struct Array * arr3=(struct Array * )malloc(sizeof(struct Array));
    struct Array * arr3= new Array[arr1->length*2];
    while(i<arr1->length && j<arr2->length)
    {
        if(arr1->A[i]<arr2->A[j])
            arr3->A[k++]=arr1->A[i++];
        else if(arr2->A[j]<arr1->A[i])
            j++;
        else
        {
            i++;
            j++;
        }
    }
    for(;i<arr1->length;i++)
        arr3->A[k++]=arr1->A[i];
        arr3->length=k;
        arr3->size=10;
    return arr3;
}
int main()
{
    struct Array arr1={2,9,21,28,35},10,5;
    // {}추가
    struct Array arr2={2,3,9,18,28},10,5;
    // {} 추가
    struct Array * arr3;
    arr3=Union(&arr1,&arr2);
    Display(*arr3);
    return 0;
}

Array C++ class

#include <iostream>
using namespace std;
template<class T>
class Array
{
private:
    T * A;
    int size;
    int length;
public:
    Array()
    {
        size=10;
        A=new T[10];
        length=0;
    }
    Array(int sz)
    {
        size=sz;
        length=0;
        A=new T[size];
    }
    ~Array()
    {
    delete []A;
    }
    void Display();
    void Insert(int index,T x);
    T Delete(int index);
};
template<class T>
void Array<T>::Display()
{
    for(int i=0;i<length;i++)
    cout<<A[i]<<" ";
    cout<<endl;
}
template<class T>
void Array<T>::Insert(int index,T x)
{
    if(index>=0 && index<=length)
    {
        for(int i=length-1;i>=index;i--)
            A[i+1]=A[i];
        A[index]=x;
        length++;
    }
}
template<class T>
T Array<T>::Delete(int index)
{
    T x=0;
    if(index>=0 && index<length)
    {
        x=A[index];
        for(int i=index;i<length-1;i++)
            A[i]=A[i+1];
        length--;
    }
    return x;
}
int main()
{
    Array<char> arr(10);
    arr.Insert(0,'a');
    arr.Insert(1,'c');
    arr.Insert(2,'d');
    arr.Display();
    cout<<arr.Delete(0)<<endl;
    arr.Display();
    return 0;
}

Comments