diff options
| -rw-r--r-- | 04-13.md | 4 | ||||
| -rw-r--r-- | 04-15.md | 79 |
2 files changed, 83 insertions, 0 deletions
@@ -293,3 +293,7 @@ bool bsearch(int a[], int n, int x){ Is binary search always better than sequential search? Answer: It depends - How about if the sequence is not sorted? + +--- + +[04/15 ->](04-15.md) diff --git a/04-15.md b/04-15.md new file mode 100644 index 0000000..01c0ed2 --- /dev/null +++ b/04-15.md @@ -0,0 +1,79 @@ +[\<- 04/13](04-13.md) + +# Abstract Data Type + +- An abstract data type is a data type whose **implementation has been hidden or abstracted away.** + +- We cannot see the implementation. Instead we have to use a set of functions called the **interface** + +- We say the implementation is kept private and the interface is public + +Encapsulating the **data** and the **operation** on the data, and then hide them from the user +1. Declaration of data +2. Declaration of operations +3. Encapsulation of data and operations + +## Data Structure & ADT + +Data Structure: +- Things to care - how to organize data in memory or disk +- Examples: array; linked list; + +ADT: +- Things to care + - what data + - what operations can be done on these data +- Things not to care + - how to organize data in memory or disk (It can be done through any data structure) + +## Example ADT - FILE + +- We don't know what a FILE looks like +- The file system are likely to change from machine to machine, e.g. MAC/Windows, 64 bit/32 bit +- We don't want our program to have to change from machine to machine, so C hides the low level details (implementation) from us. We only use an interface as declared in `<stdio.h>` + - fopen, fscanf, ... + +## Implementing a SET Using Array + +Pre-knowledge +1. Store string elements in an array +2. Dynamically sized array +3. Structure + +# Store String Elements in an Array + +## One String in C - Character Array + +Character Array + +|m|a|n|g|o|\0| +|-|-|-|-|-|--| + +|b|a|n|a|n|a|\0| +|-|-|-|-|-|-|--| + +Refer to the character array through a character pointer: `char *` + +## Assert + +- An **assertion** specifies that a program satisfies certain conditions at a particular points in its execution +- Common uses + - Pointers are not `NULL` + - Indices and size values are non-negative and less than a known limit +- Ex. + - p is a pointer: `assert(p != NULL);` +- Make sure to test the condition **before** the usage of the variable + +## Strucutre in C + +### Concept +- A structure is **a collection of one or more variables**, possible of different types, grouped together under a single name for convenient handling +- e.g. + +``` +struct mystruct{ + int a; + int b; + char c; +}; +``` |