Looking for a Tutor Near You?

Post Learning Requirement »
x

Choose Country Code

x

Direction

x

Ask a Question

x

x
x
For better view click here
x
Hire a Tutor
DISCOVER

C Programming Overview-Lecture VI

Loading...

Published in: C / C++
2,007 Views

C Programming Overview - O Notation

Akhilesh K / Lucknow

4 years of teaching experience

Qualification: M.Sc (NIT Rourkela - 2019)

Teaches: All Subjects, English, Mathematics, Science, Chemistry, Physics, Algebra, IIT JEE Mains, AIPMT, NEET

Contact this Tutor
  1. C Programming - Lecture 6 This lecture we will learn: — Error checking in C — What is a wrappered function? — How to assess efficiency. — What is a clean interface? — How can structures contain other structures? — What is a linked list?
  2. Error checking in programs A good programmer always checks file reading, user input and memory allocation (see later) for errors. Nothing convinces a user of your program that you're an idiot faster than it crashing when they type "the wrong thing". Take some action to avert the error even if that action is stopping the program. It is best to print errors to the stderr stream. f print f (stderr, "There is an error! \ n")
  3. Wrappered function Isn't it pretty boring to write an error check every time you try a malloc. Most of the time, after all, you just say "out of memory" and exit. It seems like lots of effort to write the same bit of code every time. The solution is to write your own "wrappered" malloc. You might want to "wrapper" other functions (though this is less common).
  4. safe malloc # include void *safe mal loc (size t) / * Error trapping mal loc wrapper * / void *safe mal loc (size t size) / * Allocate memory or print an error and exit * / void *ptr; ptr= mal loc (size) • if (ptr NULL) { f print f (stderr, LINE exit (—1); return ptr; "No memory line: Ood file: % s \ n" FILE ) ;
  5. The O-notation The O-notation is used to approximate the efficiency of an algorithm. ' If we say that the execution time is O(f(n)) we mean: g(n) = O(f(n)) 3(M) : Vn>0 Ig(n) < Mf(n) Note therefore that: O(n) O(n2) though generally we specify the execution time in the strongest possible terms
  6. O-notation (getting the feel) n 967,296 775,616 ni 25 112 1 16 256 4,096 65,536 16, 4 8 12 16 20 24 2,048 49,152 402, 614,784 1 32 I 024 32,768 1,073, 613,825 1 256 65,536 179,456
  7. O-notation Inserting into an array — an O(n) operation 4 Insert new Blank bits number of array here 1 1 2 3 3 4 These numbers have to be moved 57889 Blank bits of array 9
  8. The Travelling Salesman The most famous O(n!) problem is the travelling salesman problem A salesman must visit all of n cities — what is his shortest path to do so? At the moment we must check all of his possible routes (n!/2 — we can divide by 2 due to symmetry) We will hear more about the TSP later.
  9. Other efficiency considerations Fewer characters typed is not more efficient. ' Sometimes you can trade memory for execution time (e.g. the sieve) Allocating memory (with pointers or arrays) is slow. File access is very slow. ' Consider your algorithms carefully — see where gains can be made.
  10. Good programming practice "a clean interface" A good programmer makes their code useful to other programmers. The best way to do this is to write useful functions which are easy to use. ' If your functions are good then there shouldn't be _ too _ many arguments passed to them. Think about "what do I need to pass to this function" and "what do I need back from it". ' If you have written a clean interface then your functions will almost explain themselves.
  11. What are the rules for writing functions in a "clean interface" The functions should be simple - don't try to force your function to do too much - nor make them too limited. In the is _ prime examples, it would be silly to write a function which found the lowest prime from 123 to 142 But it might not be unreasonable to write one which took two numbers and found the lowest prime in that range
  12. Example structure pay. h Header file - Pay. CPP enums, structs, # include "pay. h" prototypes int main() Get user input Call appropriate routine file io . cpp # include "pay. h" Read records when called Writes records Make backup copies update . cpp # include "pay. h" Type in a new file for a new lecturer Change file for existing lecturer printout . cpp # include "pay. h" Print a cheque run for all lecturers Print records of individual lecturers for inspection
  13. By using structs, we can make our functions look simpler Sometimes we need to pass a LOT of information to a function. void write record (FILE *fptr, char name C] int wage, int hire date) / * Function to write info about a lecturer * / Nicer to bundle it as a struct - and we can add stuff later void write record (FILE *fptr, LECTURER this lecturer) / * Function to write info about a lecturer * /
  14. Functions should be "consistent" ' If you write a lot of similar functions it is best to make them work the "same way" int write / * Return record (char fname C] , LECTURER lect) —1 for FAIL 0 for success The second function is perverse given the first int add record (LECTURER lect, char fname C] ) / * Return 0 for FAIL 1 for success Another programmer reading your code will be justified in anything short of actual bodily harm if your code works like this.
  15. Functions should be predictable ' Don't make your function change arguments it doesn't NEED TO. Unless your function is explicitly supposed to change arrays, DON'T change the array. FILE *fptr,• " file . txt " char fname [ ] fptr= f open (fname, r"); if (fptr NULL) { print f ("Can't open 00 s \ n" , fname) • return -1; Wouldn't you be annoyed if fopen had unexpectedly changed what was in fname?
  16. Structs which contain themselves Sometimes programmers want structs in C to contain themselves. For example, we might design an electronic dictionary which has a struct for each word and we might want to refer to synonyms which are also word structures. wordl : run word3: jog sprint word 2 : synonym 1 synonym 1 synonym2 synonym 1 s ynonym2 synonym2
  17. How structs can contain themselves Clearly a struct cannot literally contain itself. / * This doesn't work * / struct silly struct { struct silly struct sl; But it can contain a pointer to the same type of struct struct good struct { / * This does work * / struct *good struct s 2;
  18. The linked list - a common use of structs which contain themselves ' Imagine we are reading lines from a file but don't know how many lines will be read. We need a structure which can extend itself. head of list informa t ion nextptr in forma t i on nextptr in forma t i on nextptr= NULL This is known as a linked list. By passing the value of the head of the list to a function we can pass ALL the information.
  19. How to set up a linked list typedef struct list item { information in each item struct list item *nextptr; } LIST ITEM; This structure (where information is what you want each "node" of your linked list to contain). It is important that the nextptr of the last bit of the list contains NULL so that you know when to stop. head of NULL list
  20. Linked list pros & cons Pro: Can easily add items to the head or middle of the list (tough with array) - good for ordered lists Pro: We can make the list as big as we like Con: Complicated for a beginner to program (don't underestimate this) ' Con: Hard to find nth element Con: Slightly larger since we store pointer and information More will be said on this useful technique next lecture.

Need a Tutor or Coaching Class?

Post an enquiry and get instant responses from qualified and experienced tutors.

Post Requirement

Related PPTs

Upload PPTs

If you have your own PowerPoint Presentations which you think can benefit others, please upload on LearnPick. For each approved PPT you will get 100 Credit Points and 100 Activity Score which will increase your profile visibility.

Upload Now
Home > PowerPoint Slides > C Programming Overview-Lecture VI