for Robot Artificial Inteligence

16. Linked List 1

15 Jun 2020 | Algorithm

  1. Problem with Arrays
  2. Difference B/W array & Linked lists

Why linked list

  • Array 말고 Linked list 쓰는 이유는 사용자가 얼마나 많은 어레이가 필요한지 모르는 동적 상태일때 쓰인다.
  • Linked list는 Array 보다 느리지만 이런 동적인 상태에서는 더 효과적이다.
  • pre, current, post 데이터가 나누어져있어 서칭하기도 쉽다.

  • Linked List는 Node들이 post, prev로 연결되어있는 구조이다.

  • point 값들은 랜덤으로 initilize되기 때문에 항상 Null을 해줘야 한다.

Checking Linked List

Display for Linked List

class Node
{
public:
  int data;
  Node* next;
};
int main()
{
  int A[]={3,5,7,10,15};
  Node* head = new Node;
  Node* temp;
  Node* last;

  head->data = A[0];
  head->next = nullptr;
  last = head;

  //Create a Linked list
  for(int i=1;i<sizeof(A)/sizeof(A[0]);i++)
  {
    // Create Temporary node
    temp = new Node;

    // Populate Temporary Node
    temp->data = A[i];
    temp->next = nullptr;

    // last's next is poting to temp
    last->next = temp;
    last = temp;
  }

  //Distplay Linked List
  Node* p= haed;

  while(p!=nullptr)
  {
    cout<<p->data<<"->"<<flush;
    p=p->next;
  }

}

Recursive Method

  • O(n)
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
class Node
{
public:
    int data;
    Node* next;
};

Node* create(int A[],int n)
{
    int i;
    Node* t, *last;
    Node* head;
    head = new Node;
    head->data = A[0];
    head->next = NULL;
    last = head;
    for(i=1;i<n;i++)
    {
        t = new Node;
        t->data = A[i];
        t->next =NULL;
        last->next = t;
        last = t;
    }
    return head;
}
void Display(Node* p)
{
    while(p!=NULL)
    {
        cout<<p->data<<endl;
        p = p->next;
    }
}
int main()
{
    int A[]={3,8,7,10,25,8,32,2};
    Node* temp;
    temp = create(A,sizeof(A)/sizeof(A[0]));
    Display(temp);
    return 0;

}

Counting and sum for Linked list

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
class Node
{
public:
    int data;
    Node* next;
};

Node* create(int A[],int n)
{
    int i;
    Node* t, *last;
    Node* head;
    head = new Node;
    head->data = A[0];
    head->next = NULL;
    last = head;
    for(i=1;i<n;i++)
    {
        t = new Node;
        t->data = A[i];
        t->next =NULL;
        last->next = t;
        last = t;
    }
    return head;
}
void Display(Node* p)
{
    while(p!=NULL)
    {
        cout<<p->data<<endl;
        p = p->next;
    }
}
int count_(Node* p)
{
    int l =0;
    while(p)
    {
        l++;
        p=p->next;
    }
    return l;
}
int sum_(Node* p)
{
    int i =0;
    while(p)
    {
        i=p->data+i;
        p=p->next;
    }
    return i;
}
int main()
{
    int A[]={3,8,7,10,25,8,32,2};
    Node* temp;
    temp = create(A,sizeof(A)/sizeof(A[0]));
    cout<< "count is "<<count_(temp)<<endl;
    cout<< "sum is "<<sum_(temp)<<endl;
    return 0;

}

Recursive Method

Max and Min

  • Max = Min-INT
  • Max = -32768
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
class Node
{
public:
    int data;
    Node* next;
};

Node* create(int A[],int n)
{
    int i;
    Node* t, *last;
    Node* head;
    head = new Node;
    head->data = A[0];
    head->next = NULL;
    last = head;
    for(i=1;i<n;i++)
    {
        t = new Node;
        t->data = A[i];
        t->next =NULL;
        last->next = t;
        last = t;
    }
    return head;
}
void Display(Node* p)
{
    while(p!=NULL)
    {
        cout<<p->data<<endl;
        p = p->next;
    }
}
int count_(Node* p)
{
    int l =0;
    while(p)
    {
        l++;
        p=p->next;
    }
    return l;
}
int sum_(Node* p)
{
    int i =0;
    while(p)
    {
        i=p->data+i;
        p=p->next;
    }
    return i;
}
int max_(Node* p)
{
    int maxx = INT32_MIN;
    while(p)
    {
        if(p->data>maxx)
            maxx = p->data;
        p=p->next;
    }
    return maxx;
}
int main()
{
    int A[]={3,8,7,10,25,8,32,2};
    Node* temp;
    temp = create(A,sizeof(A)/sizeof(A[0]));
    cout<< "max is "<<max_(temp)<<endl;
    return 0;

}

Comment  Read more

15. Polynomial Representation

15 Jun 2020 | Algorithm

  1. Polynomial Representation
  2. Evaluation of polynomial
  3. addition of two polynomial

Polynomial Representation

SUM

struct term
{
  int coef;
  int Exp;
};
struct poly
{
  int n;
  struct term* t;
};
int main()
{
  struct Poly p;
  printf("no of non-zero");
  scanf("%d\n",&p.n );
  p.t= new term[p.n];
  printf("Enter terms\n");
  for(i=0;i<p.n;i++)
  {
    scanf("%d, %d", &p.t[i].coef, &p->t[i].exp);
  }
  for(int i=0; i<p.n;i++)
  {
    sum+=p.t[i].coef* pow(x,p.t[i]* Exp)
  }
  return 0;
}

Add

struct Term
{
  int coeff;
  int exp;
};
struct Poly
{
  int n;
  struct Term * terms;
};
void create(struct Poly *p)
{
  int i;
  printf("Number of terms?");
  scanf("%d",&p->n);
  p->terms = new Term[p->n]
  printf("Enter terms\n");
  for(i=0;i<p->n;i++)
    scanf("%d%d",&p->terms[i].coeff,&p->terms[i].exp);
}
struct Poly* add(struct Poly* p1,struct Poly* p2)
{
  int i,j,k
  struct Poly* sum;
  sum = new Poly;
  sum->terms = new Term[p1->n+p2->n];
  i=j=k=0;
  while(i<p1->n && j<p2->n)
  {
    if(p1->terms[i].exp>p2->terms[j].exp)
      sum->terms[k++]=p1->terms[i++];
    else if(p1->terms[i].exp < p2->terms[j].exp)
      sum->terms[k++]=p2->terms[j++];
    else
    {
      sum->terms[k].exp=p1->terms[i].exp;
      sum->terms[k++].coeff=p1->terms[i++].coeff+p2->terms[j++].coeff;
    }
  }
  for(;i<p1->n;i++)
    sum->terms[k++]=p1->terms[i];
  for(;j<p2->n;j++)
    sum->terms[k++]=p2->terms[j];
  sum->n=k;
  return sum;
};
void display(struct Poly p)
{
  int i;
  for(i=0;i<p.n;i++)
    printf("%dx%d+",p.terms[i].coeff,p.terms[i].exp);
  printf("\n");
}
int main()
{
  struct Poly p1,p2, * p3;

  create(&p1);
  create(&p2);
  p3=add(&p1,&p2);
  printf("\n");
  display(p1);
  printf("\n");
  display(p2);
  printf("\n");
  display(*p3);
  return 0;
}

Comment  Read more

14. Application of Matrix Menu

15 Jun 2020 | Algorithm

Menu

  1. Create
  2. Get
  3. Set
  4. Display

Diagonal

int main()
{
  int * A, n, ch, x;
  printf("Enter Dimension");
  scanf("%d", &n);
  A = int new[n];
  int i,j;
  do
  {
    //Display Menu
    switch(ch)
    {
      case 1:
        for(i=1;i<=n,i++)
        {
          scanf("%d\n", &A[i-1] );
        }
      case 2:
        printf("enter index");
        scanf("%d,%d \n",&i,&j);
        if(i==j)
          printf("%d \n",A[i-1] );
        else
        {
          printf("0");
        }
      case 3:
        printf("Endter row,col, and ele);
        scanf("%d,%d,%d \n",&i,&j,&x);
        if(i==j)
          A[i-1]=x;
        break;
      case 4:
        for(i=1; i<=n; i++)
        {
          for(j=1; j<=n; j++)
          {
            if(i==j)
              printf("%d\n", A[i-1] );
            else
              printf("0");
          }
        }
    }
  }

}

Lower Triangular

int main()
{
  int * A, n, ch, x;
  printf("Enter Dimension");
  scanf("%d", &n);
  A = int new[n];
  int i,j;
  do
  {
    //Display Menu
    switch(ch)
    {
      case 1:
        for(i=1;i<=n,i++)
        {
          scanf("%d\n", &A[i-1] );
        }
      case 2:
        printf("enter index");
        scanf("%d,%d \n",&i,&j);
        if(i==j)
          printf("%d \n",A[i-1] );
        else
        {
          printf("0");
        }
      case 3:
        printf("Endter row,col, and ele);
        scanf("%d,%d,%d \n",&i,&j,&x);
        if(i>=j)
          A[i+(i-1)/2+j-1]=x;
        break;
      case 4:
        for(i=1; i<=n; i++)
        {
          for(j=1; j<=n; j++)
          {
            if(i>=j)
              printf("%d\n", A[i+(i-1)/2+j-1] );
            else
              printf("0");
          }
        }
    }
  }

}

Quiz

Comment  Read more

13. Matrices(Symmetric Mattrix, Tridiagonal Matrix, Band Matrix, Toeplitz Matrix, Sparse Matrix)

15 Jun 2020 | Algorithm

  1. Diagonal Matrix
  2. Lower Triangular Matrix
  3. Upper Triangular Matrix
  4. Symmetric Matrix
  5. Tridiagonal Matrix
  6. Band Matrix
  7. Toeplitz Matrix
  8. sparse matrix

4. Symmetrix Matrix

5. Tridiagonal Matrix

6. Square Band Matrix

7. Toeplitz Matrix

Sparse Matrix

Create a sparse matrix

struct Element
{
  int i;
  int j;
  int x;
};
struct Sparse
{
  int m;
  int n;
  int num;
  struct Element * ele;
};
void create(Sparse* s)
{
  int i;
  printf("Eneter Dimensions");
  scanf("%d%d",&s->m,&s->n);
  printf("Number of non-zero");
  scanf("%d",&s->num);
  s->ele= new Element[s->num];
  printf("Eneter non-zero Elements");
  for(i=0;i<s->num;i++)
    scanf("%d%d%d",&s->ele[i].i,&s->ele[i].j,&s->ele[i].x);
}
struct Sparse* add(struct Sparse* s1,struct Sparse* s2)
{
  struct Sparse* sum;
  int i,j,k;
  i=j=k=0;
  if(s1->n != s2->n && s1->m != s2->m)
    return NULL;
  sum= new Spares;
  sum->ele= new Spares(s1->num+s2->num)
  while(i<s1->num && j<s2->num)
  {
    if(s1->ele[i].i<s2->ele[j].i)
      sum->ele[k++]=s1->ele[i++];
    else if(s1->ele[i].i>s2->ele[j].i)
      sum->ele[k++]=s2->ele[j++];
    else
    {
      if(s1->ele[i].j<s2->ele[j].j)
        sum->ele[k++]=s1->ele[i++];
      else if(s1->ele[i].j>s2->ele[j].j)
        sum->ele[k++]=s2->ele[j++];
      else
      {
        sum->ele[k]=s1->ele[i];
        sum->ele[k++].x=s1->ele[i++].x+s2->ele[j++].x;
      }
    }
  }
  for(;i<s1->num;i++)
    sum->ele[k++]=s1->ele[i];
  for(;j<s2->num;j++)
    sum->ele[k++]=s2->ele[j];
  sum->m=s1->m;
  sum->n=s1->n;
  sum->num=k;
  return sum;
}
void display(struct Sparse s)
{
  int i,j,k=0;
  for(i=0;i<s.m;i++)
  {
    for(j=0;j<s.n;j++)
    {
      if(i==s.ele[k].i && j==s.ele[k].j)
      {
        printf("%d ",s.ele[k++].x);
      }
      else
      {
        printf("0 ");
      }
    }
    printf("\n");
  }
}
int main()
{
  struct Sparse s1,s2,* s3;

  create(&s1)
  create(&s2)

  s3=add(&s1,&s2);

  printf("First Matrix\n");
  display(s1);
  printf("Second Matrix\n");
  display(s2);
  printf("Sum Matrix\n");
  display(*s3);
  return 0;
}

Comment  Read more

12. Matrices(Diagonal Matrix, Lower Triangular Matrix, Upper Triangular Matrix)

15 Jun 2020 | Algorithm

  1. Diagonal Matrix
  2. Lower Triangular Matrix
  3. Upper Triangular Matrix
  4. Symmetric Matrix
  5. Tridiagonal Matrix
  6. Band Matrix
  7. Toeplitz Matrix
  8. sparse matrix

1.Diagonal Matrix

Diagonal matrix in Structure

#include <stdio.h>
struct Matrix
{
  int A[10];
  int n;
};
void Set(struct Matrix *m,int i,int j,int x)
{
  if(i==j)
    m->A[i-1]=x;

}
int Get(struct Matrix m,int i,int j)
{
  if(i==j)
    return m.A[i-1];
  else
    return 0;
}
void Display(struct Matrix m)
{
  int i,j;
  for(i=0;i<m.n;i++)
  {
    for(j=0;j<m.n;j++)
    {
      if(i==j)
        printf("%d ",m.A[i]);
      else
        printf("0 ");
    }
    printf("\n");
 }
}
int main()
{
  struct Matrix m;
  m.n=4;

  Set(&m,1,1,5);Set(&m,2,2,8);Set(&m,3,3,9);Set(&m,4,4,12);
  printf("%d \n",Get(m,2,2));
  Display(m);
  return 0;
}

Diagonal Matrix in Class

class Diagonal
{
private:
  int n;
  int * A;
public:
  Diagonal(int n)
  {
    this->n;
    A= new int[n];
  }
  void set(int i, int j, int x);
  int get(int i, intj);
  void Display()
  ~Diagonal();
};
void Diagonal::Set(int i,int j,int x)
{
  if(i==j)
    A[i-1]=x;
}
int Diagonal::Get(int i,int j)
{
  if(i==j)
    return A[i-1];
  return 0;
}
void Diagonal::Display()
{
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      if(i==j)
        cout<<A[i-1]<<“ ";
      else
        cout<<"0 ";
    }
    cout<<endl;
 }
}
int main()
{
  int d;
  cout<<"Enter Dimensions";
  cin>>d;

  Diagonal dm(d);
  int x;
  cout<<"enter All elements";
  for(int i=1;i<=d;i++)
  {
    for(int j=1;j<=d;j++)
    {
      cin>>x;
      dm.Set(i,j,x);
    }
  }
  dm.Display();
  return 0;
}

Lower Triangular Matrix

Code 1

struct Matrix
{
  int * A;
  int n;
};

void Set(struct Matrix *m,int i,int j,int x)
{
  if(i>=j)
    m->A[m->n*(j-1)+(j-2)* (j-1)/2+i-j]=x;
}
int Get(struct Matrix m,int i,int j)
{
  if(i>=j)
    return m.A[m.n*(j-1)+(j-2)* (j-1)/2+i-j];
  else
    return 0;
}
void Display(struct Matrix m)
{
  int i,j;
  for(i=1;i<=m.n;i++)
  {
    for(j=1;j<=m.n;j++)
    {
      if(i>=j)
        printf("%d ",m.A[m.n*(j-1)+(j-2)* (j-1)/2+i-j]);
      else
        printf("0");
    }
    printf("\n");
  }
}
int main()
{
  struct Matrix m;
  int i,j,x;
  printf("Enter Demension");
  scanf("%d \n",&m.n);
  m.A=(int *)malloc(m.n*(m.n+1)/2*sizeof(int));
  printf("enter all elements");
  for(i=1;i<=m.n;i++)
  {
    for(j=1;j<=m.n;j++)
    {
      scanf("%d\n", &x);
      Set(&m,i,j,x);
    }
  }
  printf("\n\n");
  Display(m);
  return 0;
}

Code 2

#include <iostream>
using namespace std;

class LTMatrix{
private:
    int n;
    int* A;
public:
    LTMatrix(int n){
        this->n = n;
        A = new int [n * (n + 1)/2];
    }
    ~LTMatrix(){ delete[] A; }
    void Display(bool row=true);
    void setRowMajor(int i, int j, int x);
    void setColMajor(int i, int j, int x);
    int getRowMajor(int i, int j);
    int getColMajor(int i, int j);
    int getN(){ return n; }

};

void LTMatrix::setRowMajor(int i, int j, int x) {
    if (i >= j){
        int index = ((i * (i - 1))/2) + j - 1;
        A[index] = x;
    }
}

void LTMatrix::setColMajor(int i, int j, int x) {
    if (i >= j){
        int index = (n * (j-1) - (((j-2) * (j-1))/2)) + (i-j);
        A[index] = x;
    }
}

int LTMatrix::getRowMajor(int i, int j) {
    if (i >= j){
        int index = ((i * (i - 1))/2) + j - 1;
        return A[index];
    } else {
        return 0;
    }
}

int LTMatrix::getColMajor(int i, int j) {
    if (i >= j){
        int index = (n * (j-1) - (((j-2) * (j-1))/2)) + (i-j);
        return A[index];
    } else {
        return 0;
    }
}

void LTMatrix::Display(bool row) {
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            if (i >= j){
                if (row){
                    cout << getRowMajor(i, j) << " ";
                } else {
                    cout << getColMajor(i, j) << " ";
                }
            } else {
                cout << 0 << " ";
            }
        }
        cout << endl;
    }
}

int main() {

    LTMatrix rm(4);
    rm.setRowMajor(1, 1, 1);
    rm.setRowMajor(2, 1, 2);
    rm.setRowMajor(2, 2, 3);
    rm.setRowMajor(3, 1, 4);
    rm.setRowMajor(3, 2, 5);
    rm.setRowMajor(3, 3, 6);
    rm.setRowMajor(4, 1, 7);
    rm.setRowMajor(4, 2, 8);
    rm.setRowMajor(4, 3, 9);
    rm.setRowMajor(4, 4, 10);

    rm.Display();
    cout << endl;

    LTMatrix cm(4);
    cm.setColMajor(1, 1, 1);
    cm.setColMajor(2, 1, 2);
    cm.setColMajor(2, 2, 3);
    cm.setColMajor(3, 1, 4);
    cm.setColMajor(3, 2, 5);
    cm.setColMajor(3, 3, 6);
    cm.setColMajor(4, 1, 7);
    cm.setColMajor(4, 2, 8);
    cm.setColMajor(4, 3, 9);
    cm.setColMajor(4, 4, 10);

    cm.Display(false);

    return 0;
}

Upper Triangular Matrix

Comment  Read more