What is the data structure in C.

1. Data structures in C

Transcript

1 Table of Contents 1. Data Structures in C Targets. Requirements Lists Inserting in a linked list Deleting from a linked list The demo program t_minish.c Example: t_minish.c Trees The Haeder file of a binary search tree Traversing binary trees Searching Inserting Deleting an element Tasks: Binary trees Task: delbinsearch ... 18 Task: BinTreeADB Summary Outlook for data structures in C 1.1. Aims. Requirements You can use and create complex, flexible data storage in RAM Requirements: Basics of programming in C sources: Lists A linked list is a data structure in which objects are arranged linearly. In arrays this is given by the indexing of the array elements. However, since the array size has to be known at compilation time, this can lead to problems (1. array becomes too small at runtime or 2. too much storage space is wasted). Linked lists are more flexible here, since each element refers to the successor. Pointers are used for this under C. The following graphic shows a so-called simply linked list with a list header: Informatik 1/19

2 List head first len ​​= 3 last Data Data Data NULL List element (node) A list element (also known as node) consists of the following 2 components: The date to be saved (int, float, struct person ,, char * void) Pointer to the Next list element Note: In the case of the last list element, this component is assigned a NULL. / * - SLIST node * / struct SList char * Data; struct SList * Next; ; typedef struct SList SLIST; There are different types of implementation. A so-called list header is used here, which consists of 3 components: Pointer to the first list element Pointer to the last list element Number of list elements / * - A header node that contains the list length * / struct SList_Header int Len; SLIST * First, * Last; ; typedef struct SList_Header SLIST_HEADER; In the following we want to develop the program t_minish, which is supposed to save a history of the commands entered in the form of a list. I.e. a list node contains a string (= the command entered). The following graphic shows this fact. Computer science 2/19

3 first len ​​= 3 last data pointer data pointer data pointer NULL "dir" "cd c: \ dev-c" "type t_minish.c" // rough draft of t_minish #include "o_strlist.h" int main () SLIST_HEADER * cmdlist ; cmdlist = createslist (); printf (prompt); fgets (input) ;. while (input! = "quit") insertfirst (cmdlist, input); exec (input); In terms of information hiding, we want to implement data encapsulation to access the actual nodes and list headers only using access functions. I.e. we build an ADT (abstract data type) called SLIST. To do this, we first consider which operations / functions (= behavior of the list) we need. That means we specify the interface of the ADT (see software IC) Informatik 3/19

4 first len ​​= 3 last SLIST_HEADER * createslist (void); Data Data Data NULL SLIST * insertFirst (SLIST_HEADER *, char *); SLIST * insertlast (slist_header *, char *); void deletefirst (slist_header *); void deletelast (slist_header *); void pr_slist (slist_header *, file *); void rm_slist (slist_header *); char * get_entryslist (slist_header *, int); After the interface has been defined, we can create the C header file: / ** * File: o_strlist.h Hofmann Anton * Header file for type agreements. * Singly linked lists as ADTs. ** / / * - SLIST node * / struct SList char * Data; struct SList * Next; ; typedef struct SList SLIST; / * - A head node that contains the list length * / struct SList_Header int Len; SLIST * First, * Last; ; typedef struct SList_Header SLIST_HEADER; / * - access functions * / extern SLIST_HEADER * createslist (void); extern SLIST * insertfirst (slist_header *, char *); extern SLIST * insertlast (slist_header *, char *); extern void deletefirst (slist_header *); Computer science 4/19

5 extern void deletelast (slist_header *); extern void pr_slist (slist_header *, file *); extern void rm_slist (slist_header *); extern char * get_entryslist (slist_header *, int); Before we create the implementation file o_strlist.c, let's take a closer look at inserting and deleting. We limit ourselves to inserting / deleting at the beginning / end of the list, because other operations can also be implemented in this way. LIFO: Stack: push, pop FIFO: Queue: enqueue, dequeue Inserting into a linked list Here you have to implement the following steps: 1. Create storage space for new nodes 2. Assign new nodes with the correct values ​​3. Update lists before inserting : List head first len ​​= 3 last Data Data Data NULL List element (node) After insertion at the beginning of the list: first len ​​= 3 + 1 last Data Data Data NULL Data Informatik 5/19

6 After inserting at the end of the list: first len ​​= 3 + 1 last Data Data Data Data NULL Deleting from a linked list Delete at the beginning: first len ​​= 3 last Data Data Data NULL first len ​​= 2 last Data Data NULL So we can use the Create actual implementation: / ** * File: o_strlist.c Hofmann Anton * Simply linked lists as ADTs. ** / #include #include #include "o_strlist.h" / ** * Local OPERATIONS that are kept private. * * / IT 6/19

7 static SLIST * makeslistnode (char * userdata, SLIST * aptr) SLIST * newptr; / * Pointer to allocated memory * / if ((newptr = (slist *) malloc (sizeof (slist)))! = NULL) newptr-> data = (char *) malloc (strlen (userdata) +1); if (newptr-> data == (char *) NULL) free (newptr); return ((slist *) NULL); else strcpy (newptr-> data, userdata); newptr-> next = aptr; return (newptr); / ** * ACCESS OPERATIONS visible from the outside * * / / * - Build a new list * / SLIST_HEADER * createslist () SLIST_HEADER * alist; if ((alist = (SLIST_HEADER *) malloc (sizeof (slist_header)))! = NULL) alist-> len = 0; alist-> first = (SLIST *) NULL; alist-> last = (SLIST *) NULL; return (alist); / * - Enter at the beginning of the list * / SLIST * insertfirst (slist_header * alist, char * userdata) SLIST * newptr; if ((newptr = makeslistnode (userdata, alist-> first))! = NULL) alist-> first = newptr; if (alist-> len == 0) / * - first entry? * / alist-> last = newptr; alist-> len ++; return (newptr); Computer science 7/19

8 / * - Enter at the end of the list * / SLIST * insertlast (slist_header * alist, char * userdata) SLIST * newptr; if ((newptr = makeslistnode (userdata, (SLIST *) NULL))! = NULL) if (alist-> len! = 0) / * - List not empty? * / alist-> last-> next = newptr; else alist-> first = newptr; alist-> last = newptr; alist-> len ++; return (newptr); / * - delete the first list entry * / void deletefirst (slist_header * alist) SLIST * temp; char * userdata; if (alist-> len> 0) / * list not empty * / temp = alist-> first; userdata = temp-> data; alist-> first = temp-> next; alist-> len--; if (alist-> len == 0) / * If the list is empty, last pointer to NULL * / alist-> last = (SLIST *) NULL; free ((void *) temp-> data); / * Release string * / free ((void *) temp); / * Release node * / / * - delete the last list entry * / void deletelast (slist_header * alist) SLIST * temp, * help; char * userdata; int i; if (alist-> len> 0) / * List not empty * / Informatik 8/19

9

10 int i; SLIST * node; node = alist-> first; for (i = 1; i next; return (node-> data); else return ((char *) NULL); The demo program t_minish.c Finally, we can create the t_minish program that should show the use of the list ADTs: / * * File: t_minish.c Hofmann Anton * gcc t_minish.c o_strlist.c -o t_minish * Uses the chained List (o_strlist.h o_strlist.c) * implements a minishell * / #include #include #include #include "o_strlist.h" enum BOOL false, true; typedef enum BOOL BOOLEAN; char help [] = "\ nminishell :: help \ n \ hi ... history \ n \! # ... execute #th command \ n \! save Filename ... save history list \ n \! load Filename. .. load history list from Filename \ n \! do ... execute current history list \ n \ quit ... quit MINISHELL \ n \ n "; char prompt [] = "\ nminish->"; #define MAXCMD 128 char cmd [maxcmd]; / * contains command read in * / SLIST_HEADER * cmdslist; / * History list * / void do_history (); Computer science 10/19

11 main () BOOLEAN end = false; / * * Generate list for storing commands * * / cmdslist = createslist (); if (cmdslist == (SLIST_HEADER *) NULL) fprintf (stderr, "not enough memory \ n"); exit (1); / * * Output logo and help * * / printf ("\ nminishell :: (Hofmann Anton, :: Demo for linked lists \ n"); printf (help); / * * Main loop for processing the entries * * / while ( end == false) / * - Output prompt and read in command * / printf (prompt); fgets (cmd, maxcmd, stdin); cmd [strlen (cmd) -1] = '\ 0'; / * - command process * / if (strcmp (cmd, "hi") == 0) / * - output history * / pr_slist (cmdslist, stdout); else if (strcmp (cmd, "help") == 0) / * - - output help * / printf (help); else if (cmd [0] == '!') / * - command from history * / do_history (); else if (strcmp (cmd, "quit") == 0 ) / * - quit MINISHELL * / rm_slist (cmdslist); / * release list * / end = true; else insertlast (cmdslist, cmd); / * - enter command in history and execute it * / Informatik 11/19

12 system (cmd); / * end_while * / / * end_main * / void do_history () int number; FILE * fp; if (strncmp (cmd + 1, "save", 4) == 0) / * - SAVE history * / fp = fopen (cmd + 6, "w"); if (fp == (file *) NULL) perror (cmd + 6); else pr_slist (cmdslist, fp); fclose (fp); else if (strncmp (cmd + 1, "load", 4) == 0) / * - LOAD history list * / fp = fopen (cmd + 6, "r"); if (fp == (file *) NULL) perror (cmd + 6); else rm_slist (cmdslist); / * remove history list and build a new one from file * / cmdslist = createslist (); if (cmdslist == (SLIST_HEADER *) NULL) fprintf (stderr, "not enough memory \ n"); else while (fgets (cmd, MAXCMD, fp)) cmd [strlen (cmd) -1] = '\ 0'; / * delete '\ n' * / insertlast (cmdslist, cmd + 7); else if (strncmp (cmd + 1, "do", 2) == 0) / * - EXECUTE current hi list * / int i; char * cmdptr; for (i = 1; cmdptr = get_entryslist (cmdslist, i); i ++) Informatik 12/19

13 printf ("% s% s \ n", prompt, cmdptr); system (cmdptr); else if (isdigit (cmd [1])) / * - EXECUTE #th history command * / number = atoi (cmd + 1); system (get_entryslist (cmdslist, number)); / * end_do_history * / Example: t_minish.c Start the minishell program from above. Files: t_minish.c, o_strlist.h, o_strlist.c 1.3. Trees Trees are understood to be the following data structures: Trees consist of nodes. Each node has zero or more successor nodes. Every node, except for one, has a previous node. The node with no predecessor is the root node. A node without a successor is a leaf. Binary trees are a special case of trees. The maximum number of successor nodes here is 2. A special case of binary trees are binary search trees: Each node has a so-called key value and the following applies: Each node in the left subtree is smaller than the root and each node in the right subtree is larger than the root. Computer science 13/19

14 The following is an example of a node of a bin. Search tree: typedef struct Bnode int key; // data set struct Bnode * Left; // Pointer to the left subtree struct Bnode * Right; // Pointer to the right subtree BNODE; If it is a leaf, Left and Right are NULL. We now want to develop a BinSearchTree module The Haeder file of a binary search tree // BinSearchTree.h // A.hofmann sept // 1. Define nodes typedef struct Bnode int key; // data set struct Bnode * Left; // Pointer to the left subtree struct Bnode * Right; // Pointer to the right subtree BNODE; // 2. define interface (access functions / methods) typedef BNODE * BinSearchTree; // traverse void inorder (BinSearchTree root, FILE * stream); void postorder (BinSearchTree root, FILE * stream); void preorder (BinSearchTree root, FILE * stream); // Search BinSearchTree search (int key, BinSearchTree root); Computer science 14/19

15 // Insert BinSearchTree insert (int key, BinSearchTree * root); // delete void delete (int key, BinSearchTree * root); Traversing binary trees Traversing means visiting each node exactly once. Let: L / RV move left / right to visit a node (visit) Then: LVR inorder LRV postorder VLR preorder Examples: + * 5 * 4 / void inorder (BinSearchTree ptr, FILE * stream) if (ptr) inorder (ptr -> left, stream); fprintf (stream,% d, ptr-> key); inorder (ptr-> right, stream); Computer science 15/19

16 // 1/2 * 3 * track of the inorder () program: call value in action inorder () of the root * 3 * 4 / NULL 5 1 printf 7 NULL 4 / printf NULL 8 2 printf 10 NULL 3 * printf NULL 11 3 printf 13 NULL 2 * printf NULL 14 4 printf 16 NULL 1 * printf NULL 17 5 printf 19 NULL void postorder (BinSearchTree ptr, FILE * stream) if (ptr) postorder (ptr-> left, stream); postorder (ptr-> right, stream); fprintf (stream,% d, ptr-> key); // 1 2/3 * 4 * 5 + void preorder (BinSearchTree ptr, FILE * stream) if (ptr) fprintf (stream,% d, ptr-> key); preorder (ptr-> left, stream); preorder (ptr-> right, stream); Computer science 16/19

17 // + * * / Search BinSearchTree search (int key, BinSearchTree root) if (root == NULL) return NULL; else if (key == root-> key) return root; else if (key key) return search (key, root-> left); else return search (key, root-> right); Insert BinSearchTree insert (int key, BinSearchTree * root) BinSearchTree curr = * root; BinSearchTree prev = * root; // 1. If the tree is empty if (* root == NULL) * root = make_node (key); return * root; // 2. Find space to insert while (curr! = NULL) prev = curr; if (key> curr-> key) curr = curr-> right; else if (key key) curr = curr-> left; else // element already exists return NULL; Computer science 17/19

18 // 3. Insert at prev if (key> prev-> key) prev-> right = make_node (key); return prev-> right; else prev-> left = make_node (key); return prev-> left; The deletion of an element is not dealt with here. Tasks: Binary trees + Task: delbinsearch Write the function void delete (int key, BinSearchTree * root), which deletes the element (int key) from the tree. Task: BinTreeADB In the following we want to develop a binary search tree for the address book example. An address book data record (ADB_RECORD) consists of the following components: typedef struct char nickname [128]; // key char [128]; // value1 char comment [128]; // value2 ADB_RECORD; // Type: Address database RECORD We define a node for a binary tree: typedef struct Bnode ADB_RECORD entry; // data set struct Bnode * Left; // Pointer to the left subtree struct Bnode * Right; // Pointer to the right subtree BNODE; A proposal for a module design. Computer science 18/19

19 Test program: t_adb2_test.c Address book module: adb2.h adb2.c adb_open (char * filename); void adb_list (FILE *); char * adb_get_ (char * nickname, char *); void adb_close (void); Binary tree module: adb_btree.h adb_btree.c adb_insert () adb_search () adb_inorder () Write, analogous to the task in worksheet 2, access to the address database of artum, that a binary search tree is used. Summary We have in This chapter got to know the basics of data structures in C Outlook In the following chapters we want to get to know similar functionalities in object-oriented programming languages ​​such as C ++ and Java. Task list Task: tminish.c, o_strlist.h, o_strlist.c ... 13 Get the Minishell program running Task: Dlist ... 13 Create a module for a doubly linked list ... 13 Task: sort .. .13 Add the access function sort () to the above singly linked list, which sorts all list entries ... 13 Task: InsertSorted ... 13 Add the access function to the above singly linked list so that entries can be entered in sorted order Task: delbinsearch ... 18 Write the function void delete (int key, BinSearchTree * root), which deletes the element (int key) from the tree ... 18 Task: BinTreeADB ... 18 In the following we want a binary one Develop a search tree for the address book example. An address book data record (ADB_RECORD) consists of the following components: Informatik 19/19