Linear Data Structure: Array, List

Array

A data structure consisting of a collection of values

• Each identified by array index
  • In C/C++/Java programming languages, array index begins from 0.
  • The range of array index is [0, size -1].

int score[10];//Data type Array name [Array size];

In C/C++ programming language,

• A consecutive set of memory location
• Logical order is the same as the physical order
• Creation of an array

Type d[10];
Type *d = new Type[size];//Dynamically assign the size of the array. 1) Declare the type and d as pointers 2) Use "new" operator
// We can assign the size of the array according to the specific number

Accessing an element by array index

d[5] = 2;

Release the allocated

delete [] d;

Creation of Arrays in C++ Programming Language

• 1-dimmensional array

int arr[10];

or

int* arr = new int[10];

• 2-dimensional array

int a[3][4];

or

int** a = new int* [3];
  for(int i=0;i<3;i++)
      a[i] = new int[4];

Array in Memory

int score[3] = {52, 17, 61};
// When we declare an array, each value gets stored sequentially in the actual RAM.

Example

#include <cstdio>

int matrix[6][6];

for(int row = 0; row<6; row++)
{
  for(int col = 0; col <6; col++)
  {
    if(row<col)
      matrix[row][col] = 1;
    else if(row==col)
      matrix[row][col] = 0;
    else
      matrix[row][col] = -1;
  }
}

Pointer

A variable storing a memory address

• Represent the variable with 3 axes: name, value, address of memory

int n = 3; //If you put *, it becomes the pointer data type.
int* pn = &n; //pointer called pn. Initialize the variable pn with the address of n.
// the value of pn becomes the address of n
// *pn is an integer

& (Ampersand) Operator

Reference operator

• Returns the address of a variable.

#include <cstdio>

int main()
{
  char c = 'A';
  char* pc = &c;// pointer pc points the location of

A  printf("%c %p\n", c, pc);
  printf("%p %p\n", &c, &pc);
  printf("%d %d\n", sizeof(c), sizeof(pc));//size of character, size of pointer

  return 0;
}

* (Asterisk) Operator

Deference operator

• Returns the value at the pointer address.
• In other words, if you put * to the pointer, you can access the value of the variable that the pointer is pointing.

#include <cstdio>

int main()
{
  char c = 'A';
  char* pc = &c;// a pointer pc is pointing to a variable c
  //If you put * to the pointer pc, it (*pc) prints the value of variable c.

  printf("%c %c\n", c *pc);// A A

  *pc = 'C'; // If you declare 'C' to the *pc,
  //You can change the value of variable c
  //directly through the pointer (pc) that is pointing //to the variable c
  printf("%c %c\n", c, *pc);// C C

  return 0;
}

answer: A A C C

Example: What are the results?

#include <cstdio>

int main()
{
  int a, b, c;
  int* pa = &a, *pb = &b, *pc = &c;

  *pa = 10, *pb = 20;
  *pc = *pa + *pb;

  printf("%d %d %d", a, b, c);

  return 0;
}

answer: 10 20 30

Function Call with Pointers

Two types of passing augments to a function:

• Call by value: passing values. Cannot change the value.
• Call by reference: passing addresses (pointers). Can change the value of the variable.

#include <cstdio>

 void swap1(int x, int y);//Call by value
 void swap2(int* px, int* py);//Call by reference

 int main()
 {
  int a = 5, b = 7;
  swap1(a, b);// swap1 cannot change the value of a and b in the main function.
  printf("%d %d\n", a, b);// 5 7
  swap2(&a, &b);// *px == a, *py == b. Change the addresses of a and b.
  // swap2 can change the value of a and b. a == *py, b == *px.
  printf("%d %d\n", a, b);// 7 5
  return 0;
 }

void swap1(int x, int y)
{
  int temp = x;
  x = y;
  y = temp;
}

void swap2(int* px, int* py)
{
  int temp = *px;
  *px = *py;
  *py = temp;
}

Insertion and Deletion in Arrays

Insertion and deletion can require significant number of operations in arrays.

Linked Lists

A linear collection of data elements

• Order is not given by their physical placement in memory.
• Each element points to the next.
• Each node consists of an item and a link (hook)
• We can Insert & Delete an Element into a Linked List

Linked List Implementation

• A node consists of an item and a next pointer
• A linked list has its length and a pointer to the head node.

typedef int Data;

typedef struct _Node
{
  Data item;
  struct _Node* next;
} Node;

typedef struct
{
  Node* head;
  int len;
} LinkedList;

Arrow and Box Representation

• Box: an item
• Arrow: a pointer to the next box
  • If the arrow points nothing, it is called the NULL pointer.
• The head points the fist node.

source “K-MOOC 허재필 교수님의 <인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고> 강좌의 2-1 강좌의 배열과 리스트 중(http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2020_T1)”

back next

Comments

Post comment

Loading...