Public speaking course notes Read "Dynamo, Amazon’s Highly Available Key-value Store" Read "Bigtable, A Distributed Storage System for Structured Data" Read "Streaming Systems" 3, Watermarks Read "Streaming Systems" 1&2, Streaming 101 Read "F1, a distributed SQL database that scales" Read "Zanzibar, Google’s Consistent, Global Authorization System" Read "Spanner, Google's Globally-Distributed Database" Read "Designing Data-intensive applications" 12, The Future of Data Systems IOS development with Swift Read "Designing Data-intensive applications" 10&11, Batch and Stream Processing Read "Designing Data-intensive applications" 9, Consistency and Consensus Read "Designing Data-intensive applications" 8, Distributed System Troubles Read "Designing Data-intensive applications" 7, Transactions Read "Designing Data-intensive applications" 6, Partitioning Read "Designing Data-intensive applications" 5, Replication Read "Designing Data-intensive applications" 3&4, Storage, Retrieval, Encoding Read "Designing Data-intensive applications" 1&2, Foundation of Data Systems Three cases of binary search TAMU Operating System 2 Memory Management TAMU Operating System 1 Introduction Overview in cloud computing 2 TAMU Operating System 7 Virtualization TAMU Operating System 6 File System TAMU Operating System 5 I/O and Disk Management TAMU Operating System 4 Synchronization TAMU Operating System 3 Concurrency and Threading TAMU Computer Networks 5 Data Link Layer TAMU Computer Networks 4 Network Layer TAMU Computer Networks 3 Transport Layer TAMU Computer Networks 2 Application Layer TAMU Computer Networks 1 Introduction Overview in distributed systems and cloud computing 1 A well-optimized Union-Find implementation, in Java A heap implementation supporting deletion TAMU Advanced Algorithms 3, Maximum Bandwidth Path (Dijkstra, MST, Linear) TAMU Advanced Algorithms 2, B+ tree and Segment Intersection TAMU Advanced Algorithms 1, BST, 2-3 Tree and Heap TAMU AI, Searching problems Factorization Machine and Field-aware Factorization Machine for CTR prediction TAMU Neural Network 10 Information-Theoretic Models TAMU Neural Network 9 Principal Component Analysis TAMU Neural Network 8 Neurodynamics TAMU Neural Network 7 Self-Organizing Maps TAMU Neural Network 6 Deep Learning Overview TAMU Neural Network 5 Radial-Basis Function Networks TAMU Neural Network 4 Multi-Layer Perceptrons TAMU Neural Network 3 Single-Layer Perceptrons Princeton Algorithms P1W6 Hash Tables & Symbol Table Applications Stanford ML 11 Application Example Photo OCR Stanford ML 10 Large Scale Machine Learning Stanford ML 9 Anomaly Detection and Recommender Systems Stanford ML 8 Clustering & Principal Component Analysis Princeton Algorithms P1W5 Balanced Search Trees TAMU Neural Network 2 Learning Processes TAMU Neural Network 1 Introduction Stanford ML 7 Support Vector Machine Stanford ML 6 Evaluate Algorithms Princeton Algorithms P1W4 Priority Queues and Symbol Tables Stanford ML 5 Neural Networks Learning Princeton Algorithms P1W3 Mergesort and Quicksort Stanford ML 4 Neural Networks Basics Princeton Algorithms P1W2 Stack and Queue, Basic Sorts Stanford ML 3 Classification Problems Stanford ML 2 Multivariate Regression and Normal Equation Princeton Algorithms P1W1 Union and Find Stanford ML 1 Introduction and Parameter Learning

C advanced

2017-04-21

Function

Definition and declaration

Examples

sqrt(100.0)
pow(x,y)
strlen(str1)
strcmp (str1,str2) // compare
atoi(str1) // convert "12345" to 12345

usage

// independent
stringPrint();
// part of expression
num = max(a,b)/2;
// as args
num = min(sum(a,b),c);

Can use files file.h to store functions.

#include "file.h"

definition


void delay(int n) {
    for (int i = 0; i<n*100000; i++);
    return; // or none
    }

Declaration

If we want to put funcions after main func, we need to declare those functions before main.

float max(float, float);

int main() {

}
float max(float a, float b) {
}

Execution

pass value

m = max(a,b);

variable field

Global variables are defined outside functions.

#include<iostream>
using namespace std;
int a = 0, b = 0;
void exchange() {
    int p;
    if (a < b) {
        p = a; a = b; b = p;
    }
}

int main() {

    cin >> a >> b;
    exchange();
    return 0;
}

If a function variable has the same name as the global variable, global variable won’t work in this function.

arrays as args

Pass values as well while pass array elements as args.

If we use array name as args, it acts like passing ref. The operation inside will change array values. Pass the array name to the args. The array name is not a variable, but the location in memory.

void change(int a[]) {
    a[0] = 30; a[1] = 50;
}

int main() {
    int a[2] = {3,5};
    change(a);
    cout << a[0] << ' ' << a[1];
}
// will be 30 50

Excercise

// fill the extra width with '0' before the string 
cout << setfill('0') << setw(2) << day << endl;

Recursion

An example: reverse word

int recur() {
    char c;
    c = cin.get();
    if (c != '\n') 
        recur();
    cout << c;
    return 0;
}

Pointer

Get address operator &:

int c = 1;
cout << &c << endl;

Pointer operator * to access the resource:

cout << *&c << endl;
cout << c << endl;

Pointer variable

Definition

A variable to store the pointer of another variable

int *pointer = NULL; // int is base type, which is the type of the variable pointed to, usually use NULL to initialize
int c = 76;
pointer = &c;
pointer = c; //invalid

Content:

*pointer // return the variable c, not value 76

Order:

int *pointer = NULL;
int a = 1;
pointer = &a;
(*pointer)++ // a++, a value
// not equal to 
*pointer++ // same as (*pointer)++

//
pointer++ // will jump over the variable (like an int), move to next bit

Array

The case with pointer to array element makes no difference with the case of a variable.

int a[5] = {1,2,3,4,5};
int *p = &a[3];
// *p is a[3]
int a[5] = {1,2,3,4,5};
cout << a << endl; // an address
cout << *a << endl; // return the value of a[0]
cout << &a[0] << endl; // an address same as the first one
  • The name of an array represents the address of the first element in array
  • Array name is the pointer to the first element
  • Array name is not a variable, cannot assign a value to

Use pointer access array

int a[5] = {1,2,3,4,5};
int *p = NULL;
cout << a << endl;
p = a;

cout << p << endl;  // address
cout << *p << endl; // value of a[0]
cout << (*p)++ << endl; // a[0], "++" is do the front thing first then + 1
cout << *p++ << endl; // a[0]

If we have:

int a[10];
int *pointer;

pointer = a; 
// equivalent to
pointer = &a[0];
  • pointer + i == a + i == &a[i]
  • *(pointer + i) == *(a + i) == a[i]
  • pointer[i] == *(pointer + i)

Assign value to array

int a[10], i, *p = a;
for (i=0;i<10;i++)
    cin >> *p++;
for (p--;p >= a;)
    cout<<setw(3)<<*p--;
  • a++ is nonsense
  • p++ will change p
  • p can point to area other than array elements
    • pay attention to the range
  • *--p: - 1 first then *

Reverse array

int a[10], *p = NULL, *q = NULL, temp;
for (p = a; p < a + 10;p++)
    cin >> *p;
for (p = a, q = a + 9;p < q;p++,q--)
{
    temp = *p; *p = *q; *q = temp;
}

2-D array

int a[3][4] = {1,2,...,12};
int *p;
// store and print row by row
for (p = &a[0][0]; p < &a[0][0] + 12; p++) 
    cout << p << " " << *p << endl;

Access an element

int a[3][4] = {1,2,...,12};
int (*p)[4];    // define a pointer pointing to an array of 4 elements
p = a;  // The first element of a is an array of 4 elements, so p should be the same
// access a[i][j]
cout << setw(4) << *(*(p+i)+j);
  • p+i == &a[i]
  • *(p+i) == a[i]
  • *(p+i) + j == a[i] + j
  • a[i] + j == &a[i][j]

Pointer & string

char a[10];
char *p;
p = a;

StrCPY

#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
    char a[] = "How are you?", b[20];
    char *p1, *p2;
    for (p1 = a, p2 = b; *p1 != '\0'; p1++, p2++)
        *p2 = *p1;
    *p2 = '\0';
}

Print pointer of string

int main() {
    char c[6] = {'h','i','\0'};
    char *pc = c;
    
    cout << c << endl;  // hi
    cout << pc << endl; // hi, not address
}

Application

Assign string value directly to string pointer

#include<iostream>
using namespace std;
int main()
{
    char buf[10] = "ABC";
    char *pc;
    pc = "hello";   // a constant, cannot be modified
    cout << pc << endl; // hello
    pc++;
    cout << pc << endl; // ello
    cout << *pc << endl; // e
    pc = buf;
    cout << pc << endl; // ABC
    return 0;
}

& and *

  • a == &a[0]
  • &a is the pointer to the entire array
    • &a+1 will jump over entrie array to outside
    • &a will promote the domain of the pointer
  • *a == a[0]
    • *a will decrease the domain of the pointer
    • *(&a) == a
#include<iostream>
using namespace std;
int main()
{
    int a[4] = {1,3,5,7};
    cout << a << endl;  // pointer to a[0], address of a[0]
    cout << a + 1 << endl;  // address of a[1]
    cout << &a << endl;  // pointer to a, address of a, not a[0]
    cout << &a + 1 << endl; // address after array a
    cout << *(&a) << endl; // adress of a[0], like a single a
    cout << *(&a) + 1 << endl; // address of a[1]
}

Pointer to 2D array

Definition of 2D array

  • 2D array a[3][4] consists of 3 elements: a[0], a[1] and a[2]
  • a[0] is the first element in 2D array
  • a[0] is a 1D array consisting of 4 elements
  • a == &a[0]
  • a[0] == &a[0][0]
  • &a > a == &a[0] > a[0] == &a[0][0] == *a > a[0][0] == **a

3 principles

  • array name is the pointer to the first element in array
  • &E promotes the domain of E by one level
  • *E decreases the domain of E by one level

Pointer and function

Pointer as function args

#include<iostream>
using namespace std;

void Rank(int *q1, int *q2)
{
    int temp;
    if (*q1 < *q2)
    {
        temp = *q1;
        *q1 = *q2;
        *q2 = temp;
    }
}
// Rank function will manipulate a and b directly
int main()
{
    int a, b, *p1, *p2;
    cin >> a >> b;
    p1 = &a; p2 = &b;
    Rank(p1,p2);
}

Use array name as func args

#include<iostream>
using namespace std;
void sum(int *p, int n)
{
    int total = 0;
    for (int i=0;i<n;i++)
        total += *p++;
    cout << total << endl;
}

int main()
{
    int a[4] = {1,2,3,4};
    sum(a, 4);
    return 0;
}

Use multi-D array name as function args

#include<iostream>
using namespace std;
// the definition of arg must have the same type as input a;
// a is a pointer to the first element in 2D array
int maxvalue(int (*p)[3])
{
    int max = p[0][0];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 4;j++)
            if (p[i][j] > max)
                max = p[i][j];
            return max;
}
int main()
{
    int a[3][2] = { {1,2},{6,4},{3,5} };
    cout << maxvalue(a);
    return 0;
}

Can use array name as formal parameters. C++ compiler will treat formal parameter array name as pointer variable.

Can constrain functions to prevent modifying array

#include<iostream>
using namespace std;
// array elements are modified
int sum(int array[], int n)
{
    // start from the first element
    for (int i=0;i<n - 1;i++)
    {
        *(array + 1) = *array + *(array+1);
        array++;
    }
    return *array;
}

// array elements will not be modified
int sum(const int array[], int n)
{
    // start from the first element
    for (int i=0;i<n - 1;i++)
    {
    // error, cannot modify constant
        *(array + 1) = *array + *(array+1); 
        array++;
    }
    return *array;
}

int main()
{
    int a[4] = {1,2,3,4};
    cout << sum(a, 4);
    return 0;
}

const

Definition

const float PI = 3.14f;
float const PI = 3.14f;

Usage:

#include<iostream>
using namespace std;

void mystrcpy(char *dest, const char *src)
{...}

int main()
{
    int a = 256;
    const int *p = &a;
    *p = 257;   // error
}
#include<iostream>
using namespace std;
int main()
{
    const int a = 78; const int b = 28; int c = 18;
    const *pi = &a;
    *pi = 58;   // *p cannot be assigned value, cannot modify the value pi points to
    pi = &b;    // valid, can assign value to pi
}

Pointer as a return value

int *function(int x, int y)

Example

#include<iostream>
using namespace std;
int *get(int arr[][4], int n, int m)
// or int *get(int (*arr)[4], int n, int m)
{
    int *pt;
    pt = *(arr + n-1) + m - 1;
    return(pt);
}
int main()
{
    int a[3][2] = {1,2,3,4,5,6};
    int *p;
    p = get(a,2,3);
    cout << *p << endl;
}

Local variable

// wouldn't be valid, local variable will be discarded after execution of function
// can use global variable
// better: user static variable
int *getint1()
{
    int value1 = 20;
    return &value1;
}
// static local variable wouldn't be disgarded after execution
int *getint1()
{
    static int value1 = 20;
    return &value1;
}

Struct

Example:

struct student      // struct type named student
{
    int id;
    char name[20];
    char sex;
    int age;
    float score;
    char addr[30];
} st_1, st_2;  // ; is needed
// define two variables at the same time
#include<iostream>
using namespace std;
struct student
{
    int id_num;
    char name[10];
};

int main()
{
    
    student mike = {123,{'m','i','k','e','\0'}};
    student mike2;
    mike.id_num = 20130000 + mike.id_num;
    mike2 = mike;   // just copy
}

Struct and func

  • args: Pass a copy to the function, unlike array
  • return: Pass a copy back
#include<iostream>
using namespace std;
struct student
{
    int id_num;
    char name[10];
};

student newone()
{
    student one = {2013, {'m','i','k','e','\0'}};
    return one;
}

int main()
{
    student mike = newone();
}

Struct and pointer

#include<iostream>
using namespace std;
struct student
{
    int id_num;
    char name[10];
};

// pass pointer to function, will modify original variable
void renew(student *one)
{
    one->id_num = 2000000 + one->id_num;
}

int main()
{
    student mike = {123,{'m','i','k','e','\0'}};
    student *one = &mike;
    cout << (*one).id_num << endl;
    // or
    cout << one->id_num << endl;    // -> is an operator
    return 0;
}

Array struct

student myclass[3] = {...};
student *one = myclass;
cout one->id_num<<endl;
// will jump to next struct element
one++;
cout one->id_num<<endl;

Linked list

Definition

Structure

  • head: pointer to the first node
  • node: every element in the list
    • value in current node
    • address of next node
  • tail: won’t point to other node
    • address is NULL

Create dynamically

// create memory space (initial value)
int *pint = new int(1024);  
// erase memory space
delete pint;

int *pia = new int[4];      delete[] pia;
struct student
{
    int id;
    student *next;
};

// step 1
student *head;
head = new student;
student *temp = head;

// step 2
// continue?
// yes
temp->next = new student;
temp = temp->next;
    // goto step 2
// no
temp->next = NULL;

Example

student *create()
{
    student *head, *temp; int num, n = 0;
    head = new student;
    temp = head;
    cin >> num;
    while (num!=-1)
    {
        n++;
        temp->id = num;
        temp->next = new student;
        temp = temp->next;
        cin >> num;
    }
    if (n == 0) head = NULL; else temp->next = NULL; //? temp = NULL?
    return head;
}

Operation

  • traversal
  • delete node
    • head
    • internal
  • insert node

2-direction linked list

  • temp->num
  • temp->next
  • temp->ahead

Creative Commons License
Melon blog is created by melonskin. This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
© 2016-2024. All rights reserved by melonskin. Powered by Jekyll.