Data StructuresDeclaring a struct:
typedef struct {
int x;
int y;
} point;
Declaring a variable and accessing members:
point first;
first.x = 1;
first.y = 4;
printf("(%d, %d) \n", first.x, first.y); |
Omega| | lower (Ω) | upper (O) | insertion into a hash table with separate chaining | 1 | 1 | insertion into a trie | 1 | 1 | insertion into a sorted linked list | 1 | n | deletion from a sorted linked list | 1 | n | deletion from an unsorted linked list | 1 | n |
Common StructsHashtable:
typedef struct _node
{
char word[50]; // 50-char word
struct _node *next;
}
node;
Tree:
typedef struct _tree3 {
bool valid; // exists or not
struct _tree3 *child1;
struct _tree3 *child2;
struct _tree3 *child3;
}
tree3;
Trie:
typedef struct _btrie {
bool valid;
struct _btrie *children[2];
}
btrie; |
StacksPop:
int pop(void)
{
if (stack.size == 0)
return -1;
return stack.numbers[--stack.size];
}
Push:
bool push(int n)
{
if (stack.size == CAPACITY || n < 0)
return false;
stack.numbers[stack.size++] = n;
return true;
} |
| | PointersDeclaration and initialization:
int a = 14;
int b = 15;
int * iPtr;
iPtr = &a;
int * anotherPtr = &b;
Accessing pointers and values:
// assign an address to another pointer
anotherPtr = iPtr;
// change the value stored in the memory
// location being pointed to
*iPtr = 3;
// print the address held be a pointer
printf("%x \n", iPtr);
// print the value being pointed to
printf("%d \n", *iPtr); |
&b = "address of" operator
*iPtr = dereference operator
iPtr -> a = 14; //shortcut DefinitionsValgrind: used for detecting memory leaks from forgetting to fclose() and free()
- syntax: valgrind –v --leak–check=full <executable file>
Bitwise Operators – see table to the right.
Find if a number is odd: if (num & 1) print(“Odd”);
Hashtable - has 2 main parts: (1) a hash function, and (2) an array the hash function maps to. Often times, each index of the array will be a linked list to store the values that are hashed to a specific index. Struct of a hashtable node is below at left:
Tree - a data structure made up of nodes that have the following 2 rules: (1) A tree node can point at its children or at NULL, and (2) A tree node may not point at any other node other than those listed in (1), including itself. Struct of a 3-child tree is above right. In the diagram, black (top) is the root node and grey (point to NULL) are leave nodes. A binary tree is a special kind of tree that has 2 children left and right.
Trie – Just like tree but can have arbitrary number of children. Below are examples of binary trie and 6-child trie. |
| | File Input / OutputDeclaring a FILE pointer:
FILE * inputFile;
FILE * outputFile;
Opening a file:
inputFile = fopen("file1.txt", "r");
outputFile = fopen("file2.txt", "w");
Input / Output:
fscanf(inputFile, "%d", &x);
fprintf(outputFile, "%f \n", 3.14);
Closing a file:
fclose(inputFile);
fclose(outputFile); |
"r" for read
"w" for write
"a" for append Operatorsincrement, decrement | ++, -- | multiply, divide, modulus | *, /, % | add, subtract | +, - | relational comparisons | >, >=, <, <= | equality comparisons | ==, != | and | && | or | || | assignment | =, +=, -=, *=, /=, %= |
Linked ListsLinked list is sorted with NULL pointer after 42. Doubly Linked Listtypedef struct node
{
struct node* prev;
unsigned int i;
struct node* next;
}
node; |
Created By
Metadata
Favourited By
Comments
No comments yet. Add yours below!
Add a Comment