Introduction in C

Data Structures

• Data structures define how data is represented, organized, stored, and operated on.
• They are essential for data representation and critical for time and space efficiency in programming.

CP164 vs CP264

• CP164 covered basic data structure concepts, abstract data types (ADT), fundamental data structures, and application programming in Python.
• CP264 delves deeper into data structure principles, focusing on design, analysis, and implementation in C at a low memory level.
• CP264 covers arrays, linked lists, queues, stacks, trees, hash tables, heaps, and graphs.
• CP264 involves the design, analysis, and implementation of high-performance, application-specific data structures in C.

Why C?

• C is a foundational programming language that is over 50 years old and also the first standardized one.
• Many languages and interpreters are based on C, including C++, Java, C#, Python, PHP, and JavaScript.
• C is used in operating systems, high-performance applications, and embedded systems.
• C has powerful features such as being a high-level compiled language, capable of memory address and bit level operations, and is small, extensible, stable, and portable.

Why C in Data Structures II?

• Data structures are understood fundamentally in terms of memory and CPU instruction level.
• It allows for design and implementation of data structures down to the memory level.
• C enables the design and implementation of application-specific data structures for improved performance

Why Data Structures II?

• Data Structures II provides an understanding of how data structures and programs function at memory and CPU levels.
• It provides foundational knowledge for computer science and software engineering careers.
• Data Structures II serves as a foundation for courses like Algorithm Design & Analysis I, System Programming, Operating Systems, and Computer Graphics.

Course Structure

• The course includes 12 weekly lessons serving as a textbook with self-evaluated quizzes.
• There are 34 lectures focused on core concepts, principles, and delivered with notes/slides, demonstrations, and Q&A.
• It also includes 10 graded individual labs for data structure programming in C, submitted through MyLS.
• There are 10 graded individual assignments for designing and implementing data structures in C, submitted via MyLS.
• The course has midterm and final exams that test lectures, lessons, and assignments, and are in person and paper based.

Evaluation Breakdown

• 10 labs are 10% of the grade
• 10 assignments are 30% of the grade
• The Midterm is 15% of the grade
• The Final Exam is 45% of the grade
• All tasks count with no dropping and weight transfer.
• A minimum of 50% is required on the final exam and a 50% overall grade to pass.

Introduction to the C Language

• C is a general-purpose language created by Dennis Ritchie at AT&T Bell Labs (1969-1973).
• UNIX OS was created by Ken Thompson, and Dennis Ritchie invented C to export UNIX to different platforms.
• ANSI approved the first C standard in 1989 (ANSI C or C89).
• ISO approved a revised standard in 1999 (C99), followed by C11, C17, and C23.

C Features

• C is a compiled programming language where source code is converted to machine code.
• A compiler converts source code to executable programs.
• C is small, simple, but powerful, with 32 keywords and supports memory address operations.
• Bitwise operations are processor instruction operations.
• C is stable and portable due to standardization, allowing compilation by cross-platform compilers.
• Libraries can be added for extended functionalities, making C extensible.
• C is the primary language for the procedural programming paradigm, featuring structured programs with program controls, blocks, and functions.

C Applications

• C is used for writing OS kernels, device drivers, system and utility programs, such as Unix, Linux, Windows, and macOS.
• C is used for interpreters of languages like Python, PHP, Java(JVM), and JavaScript.
• C is used for high-performance computing, graphics programs, browsers, GUIs, and large-scale parallel programs.
• C influenced C++ (Bjarne Stroustrup, 1979), an extension for OOP.
• Java (James Gosling, 1984) is an OOP language that runs on JVM, like C++.

Compiling and Execution

• A simple "hello world" program in the C language looks like:

#include <stdio.h>
void main() {
 printf("hello, world\n");
}

C Compilation Steps

• Pre-processing resolves lines starting with "#", using pre-processor directives.
• Compilation converts the C program into assembly code.
• Assembling converts assembly code into binary object programs.
• Linking combines object programs to create an executable (binary machine code program).

C Compilers

• C Compilers are programs that compile C Code
• MinGW (Minimalist GNU C Compiler for Windows) is one such compiler.
• Mac OS includes Clang as a compiler.
• Command-line compilation: gcc hello.c uses the default C99 standard.
• This creates a.exe on Windows or a.out on Linux/Mac (executable program).
• Execute programs via command line, i.e. a.exe on Windows or ./a.out on Linux/Mac

Compiler Options

• -std=c99 is used to enforce the C99 standard.
• The command for this would be gcc -std=c99 hello.c
• -c suppresses linking during compilation and generates an object file.
  • For instance gcc -c hello.c will output hello.o
• -g embeds diagnostic information into the object file.
  • For instance gcc -g hello.c will output a.exe
• -o names the executable program from linking instead of a.out.
  • For instance gcc hello.c -o hello.exe, or gcc hello.c -o hello.
• -S suppresses assembling and linking.
  • For instance gcc -S hello.c to generate the assembly filehello.s.
• -On (optimize) is used to optimize, 0 is off, default is 1, 2,3,6 are higher optimization levels.
  • For instance gcc -O3 -o hello hello.c => hello.exe (executable, optimized with level 3)
• -Wall command gives compiling warnings.
• -Idirectory command gives the list of directories for include files.
• -larg command searches /lib and /usr/lib for library libarg.lib.
• -Ldirectory provides a list of directories for library specific files by -l.

File Extensions

• .c is a C language source code file.
• .h is a C language header file.
• .exe is an executable file (or .out for Unix/Linux).
• .o is an object file.
• .s is an assembly language source file.
• .lib is a static library of object modules (.a for Unix/Linux).
• .dll is a dynamic library file (.so for Unix/Linux).

C Program Execution

• The executable program, consisting of instructions, is loaded into the main memory.
• Execution starts from the first instruction of the main function, one by one controlled by the program's flow control, stopping at the end.
• When executing, an instruction is read from memory to the CPU register and then executed by the CPU.