c programming and data structure notes for ECE

c programming and data structure 3rd chapter for anna university ECE

1. REPRESENTATION OF LISTS Create a list (N No.of data/elements) : eg: 10 20 30 40

2. MEMORY STATIC (STACK) DYNAMIC (HEAP) RAM

3. ARRAY int a[N]; for( int i =0; i < N;i ++) scanf (“% d”,&a [ i ]); 10 20 30 40 N MEMORY 1000 1002 1004 1006 1008 1010 1012 1014 1016 1018

4. LINKED LIST struct node { int data; struct node *next; } Creation of list struct node *d1,*d2,*d3,*d4; d1 d2 d3 d4 DECLARATION STATIC MEMORY

5. d1= malloc ( sizeof ( struct node)); 1024 d2= malloc ( sizeof ( struct node)); 2024 d3= malloc ( sizeof ( struct node)); 3024 d4= malloc ( sizeof ( struct node)); 4024 d1 1024 d2 2024 d3 3024 d4 4024 1024 2024 3024 4024 data *next Dynamic memory d1 d2 d3 d4

6. d1 ->data = 10; d2 ->data = 20; d3 ->data = 30; d4 ->data = 40; d1 - >next=d2; d2 - >next =d3; d3 - >next=d4; d4 ->next=NULL; struct node *head=d1; data *next 1024 10 2024 2024 20 3024 3024 30 4024 4024 40 NULL head

7. LINKED LIST REPRESENTATION 10 10 10 10 head 1024 10 2024 2024 20 3024 3024 30 4024 4024 40 NULL

8. whike (head!=NULL) { printf (“% d”,head ->data); head=head ->next; } OUTPUT 10 20 30 40 data *next 1024 10 2024 head To Print the List 20 3024 30 4024 40 NULL head head head head

9. A linked list is a data structure which can change during execution. Successive elements are connected by pointers. Last element points to NULL . It can grow or shrink in size during execution of a program. It can be made just as long as required. It does not waste memory space. A B C head

10. Keeping track of a linked list: Must know the pointer to the first element of the list (called start , head , etc.). Linked lists provide flexibility in allowing the items to be rearranged efficiently. Insert an element. Delete an element.

11. Basic Operations on a List Creating a list Traversing the list Inserting an item in the list Deleting an item from the list Concatenating two lists into one

12. Illustration: Insertion A A Item to be inserted X X A B C B C curr tmp

13. Pseudo-code for insertion typedef struct nd { struct item data; struct nd * next; } node; void insert(node *curr) { node * tmp; tmp=(node *) malloc(sizeof(node)); tmp->next=curr->next; curr->next=tmp; }

14. Illustration: Deletion A B A B C C Item to be deleted curr tmp

15. Pseudo-code for deletion typedef struct nd { struct item data; struct nd * next; } node; void delete(node *curr) { node * tmp; tmp=curr->next; curr->next=tmp->next; free(tmp); }

16. In essence ... For insertion: A record is created holding the new item. The next pointer of the new record is set to link it to the item which is to follow it in the list. The next pointer of the item which is to precede it must be modified to point to the new item. For deletion: The next pointer of the item immediately preceding the one to be deleted is altered, and made to point to the item following the deleted item.

17. Array versus Linked Lists Arrays are suitable for: Inserting/deleting an element at the end. Randomly accessing any element. Searching the list for a particular value. Linked lists are suitable for: Inserting an element. Deleting an element. Applications where sequential access is required. In situations where the number of elements cannot be predicted beforehand.

18. Stack Implementations: Using Array and Linked List

19. A Last-in First-out (LIFO) List In Out A B C C B Also called a STACK

20. STACK USING ARRAY top top PUSH

21. STACK USING ARRAY top top POP

22. Stack: Linked List Structure top PUSH OPERATION

23. Stack: Linked List Structure top POP OPERATION

24. Basic Idea We would: Declare an array of fixed size (which determines the maximum size of the stack). Keep a variable which always points to the “top” of the stack. Contains the array index of the “top” element.

25. Basic Idea In the array implementation, we would: Declare an array of fixed size (which determines the maximum size of the stack). Keep a variable which always points to the “top” of the stack. Contains the array index of the “top” element. In the linked list implementation, we would: Maintain the stack as a linked list. A pointer variable top points to the start of the list. The first element of the linked list is considered as the stack top.

26. Applications of stack: 1. Stack is used by compilers to check for balancing of parentheses, brackets and braces. 2. Stack is used to evaluate a postfix expression. 3. Stack is used to convert an infix expression into postfix/prefix form. 4. In recursion, all intermediate arguments and return values are stored on the processor’s stack. 5. During a function call the return address and arguments are pushed onto a stack and on return they are popped off.

27. Converting and evaluating Algebraic expressions Infix: It is the form of an arithmetic expression in which we fix (place) the arithmetic operator in between the two operands. Example: A + B Prefix: It is the form of an arithmetic notation in which we fix (place) the arithmetic operator before (pre) its two operands. The prefix notation is called as polish notation. Example: + A B Postfix: It is the form of an arithmetic expression in which we fix (place) the arithmetic operator after (post) its two operands. The postfix notation is called as suffix notation and is also referred to reverse polish notation. Example: A B +

28. Conversion from infix to postfix: Scan the infix expression from left to right. If the scanned symbol is left parenthesis, push it onto the stack. If the scanned symbol is an operand, then place directly in the postfix expression (output). If the symbol scanned is a right parenthesis, then go on popping all the items from the stack and place them in the postfix expression till we get the matching left parenthesis. If the scanned symbol is an operator, then go on removing all the operators from the stack and place them in the postfix expression, if and only if the precedence of the operator which is on the top of the stack is greater than ( or equal) to the precedence of the scanned operator and push the scanned operator onto the stack.

29. The order of precedence ( highest to lowest)

30. Convert infix to postfix :A + B * C – D / E * H A + B * C – D / E * H + A + AB +* AB +* ABC - ABC*+ -/ ABC*+D -/ ABC*+DE -* ABC*+DE/ -* ABC*+DE/H A ABC*+DE/H* - - lower priority than *, so POP *. +equal priority with -, so POP +. * equal priority with /, so POP /.

31. Evaluation of postfix expression The postfix expression is evaluated easily by the use of a stack. 1. When a number is seen, it is pushed onto the stack; 2. When an operator is seen, the operator is applied to the two numbers that are popped from the stack and the result is pushed onto the stack. 3. When an expression is given in postfix notation, there is no need to know any precedence rules; this is our obvious advantage.

32. Queue Implementation using Linked List

33. A First-in First-out (FIFO) List Also called a QUEUE In Out A C B A B

34. Basic Idea Basic idea: Create a linked list to which items would be added to one end and deleted from the other end. Two pointers will be maintained: One pointing to the beginning of the list (point from where elements will be deleted). Another pointing to the end of the list (point where new elements will be inserted). Front Rear DELETION INSERTION

35. QUEUE: LINKED LIST STRUCTURE front rear ENQUEUE

36. QUEUE: LINKED LIST STRUCTURE front rear DEQUEUE

37. Spring 2012