Lect 1 DS PDF

Introduction to Data Structures Dr. Rima Rhaim Data Structure ITGS220 1 Dr. Rima Rhaim Data Structure ITGS220 2 What is a Computer Program? n To exactly know, what is data structure? We must know: n What is a computer program? Some mysterious...

Introduction to Data Structures Dr. Rima Rhaim Data Structure ITGS220 1 Dr. Rima Rhaim Data Structure ITGS220 2 What is a Computer Program? n To exactly know, what is data structure? We must know: n What is a computer program? Some mysterious processing Output Input Dr. Rima Rhaim Data Structure ITGS220 3 Definition n An organization of information, usually in memory, for better algorithm efficiency n such as queue, stack, linked list, heap, dictionary, and tree, Dr. Rima Rhaim Data Structure ITGS220 4 3 steps in the study of data structures n Logical or mathematical description of the structure n Implementation of the structure on the computer n Quantitative analysis of the structure, which includes determining the amount of memory needed to store the structure and the time required to process the structure Dr. Rima Rhaim Data Structure ITGS220 5 n Data may be organized in many ways n E.g., arrays, linked lists, trees etc. n The choice of particular data model depends on two consideration: n It must be rich enough in structure to mirror the actual relationships of data in the real world n The structure should be simple enough that one can effectively process the data when necessary Dr. Rima Rhaim Data Structure ITGS220 6 Example n Data structure for storing data of students:- n Arrays n Linked Lists n Issues n Space needed n Operations efficiency (Time required to complete operations) n Retrieval n Insertion n Deletion Dr. Rima Rhaim Data Structure ITGS220 7 What data structure to use? Data structures let the input and output be represented in a way that can be handled efficiently and effectively. array Linked list queue tree stack Dr. Rima Rhaim Data Structure ITGS220 8 Why Data Structure? n Data structure is a way of storing and organizing information in a computer so that it can be retrieved and used most productively. Dr. Rima Rhaim Data Structure ITGS220 9 Definition n Data structure is representation of the logical relationship existing between individual elements of data. n In other words, a data structure is a way of organizing all data items that considers not only the elements stored but also their relationship to each other. Dr. Rima Rhaim Data Structure ITGS220 10  Introduction n Data structure affects the design of both structural & functional aspects of a program. Program=algorithm + Data Structure n You know that a algorithm is a step by step procedure to solve a particular function. Dr. Rima Rhaim Data Structure ITGS220 11  Algorithms n An algorithm is a step-by-step procedure for calculations. n An algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Dr. Rima Rhaim Data Structure ITGS220 12 Algorithm n That means, algorithm is a set of instruction written to carry out certain tasks & the data structure is the way of organizing the data with their logical relationship retained. n To develop a program of an algorithm, we should select an appropriate data structure for that algorithm. n Therefore algorithm and its associated data structures from a program. Dr. Rima Rhaim Data Structure ITGS220 13  Data Structure Classification n Primitive / Non-primitive n Basic Data Structures available / Derived from Primitive Data Structures n Homogeneous / Heterogeneous n Elements are of the same type / Different types n Static / Dynamic n memory is allocated at the time of compilation / run- time n Linear / Non-linear n Maintain a Linear relationship between element Dr. Rima Rhaim Data Structure ITGS220 14 Classification of Data Structure n Data structure are normally divided into two broad categories: n Primitive Data Structure n Non-Primitive Data Structure Dr. Rima Rhaim Data Structure ITGS220 15  Classification of Data Structure Data structure Primitive DS Non-Primitive DS Integer Float Character Pointer Dr. Rima Rhaim Data Structure ITGS220 16  Classification of Data Structure Non-Primitive DS Linear List Non-Linear List Array Queue Graph Trees Link List Stack Dr. Rima Rhaim Data Structure ITGS220 17 Primitive Data Structure n There are basic structures and directly operated upon by the machine instructions. n Integer, Floating-point number, Character constants, string constants, pointers etc, fall in this category. Dr. Rima Rhaim Data Structure ITGS220 18 Non-Primitive Data Structure n There are more sophisticated data structures. n These are derived from the primitive data structures. n The non-primitive data structures emphasize on structuring of a group of homogeneous (same type) or heterogeneous (different type) data items. Dr. Rima Rhaim Data Structure ITGS220 19 Non-Primitive Data Structure n Lists, Stack, Queue, Tree, Graph are example of non-primitive data structures. n The design of an efficient data structure must take operations to be performed on the data structure. Dr. Rima Rhaim Data Structure ITGS220 20 Non-Primitive Data Structure n The most commonly used operation on data structure are broadly categorized into following types: n Create n Selection n Updating n Searching n Sorting n Merging n Destroy or Delete Dr. Rima Rhaim Data Structure ITGS220 21 Different between them n A primitive data structure is generally a basic structure that is usually built into the language, such as an integer, a float. n A non-primitive data structure is built out of primitive data structures linked together in meaningful ways, such as a or a linked-list, binary search tree, AVL Tree, graph etc. Dr. Rima Rhaim Data Structure ITGS220 22 ‫المصفوفة ‪ :‬ھً متغٌر ٌحوي مجموعة من القٌم من نوع واحد‬ ‫‪‬‬ ‫انواعھا ‪ :‬مصفوفه ذات بعد واحد ‪ ،‬مصفوفه متعددة االبعاد‬ ‫‪‬‬ ‫تحجز مجموعة من المواقع المتتالٌة فً الذاكرة‬ ‫‪‬‬ ‫‪Dr. Rima Rhaim‬‬ ‫‪ITGS 220‬‬ ‫‪Data Structure‬‬  ‫المصفوفة ذات البعد الواحد‬ ‫االعالن عن مصفوفه ذات بعد واحد ‪:‬‬ ‫الشكل العام‬ ‫مثال ‪:‬‬ ‫; ]‪int x [5‬‬ ‫حجم المصفوفة (عدد عناصر المصفوفة)‬ ‫اسم المصفوفة‬ ‫نوع بٌانات عناصر المصفوفة‬ ‫‪Dr. Rima Rhaim‬‬ ‫‪ITGS 220‬‬ ‫‪Data Structure‬‬  ‫المصفوفة تحتوي على مجموعة من العناصر التً لھا نفس النوع‬ ‫‪‬‬ ‫ھذه العناصر تحجز مواقع فً الذاكرة بشكل متتالً‬ ‫‪‬‬ ‫كل عنصر لدٌة موقع فً المصفوفة ٌسمى (المؤشر ‪)index‬‬ ‫‪‬‬ ‫الـ ‪ index‬للعنصر االول ھو ‪0‬‬ ‫الـ ‪ index‬للعنصر الثانً ھو ‪1‬‬ ‫الـ ‪ index‬للعنصر الثالث ھو ‪.3‬‬ ‫‪.‬‬ ‫الـ ‪ index‬للعنصر االخٌر ھو (حجم المصفوفة – ‪)1‬‬ ‫للوصول الى أي عنصر بالمصفوفة نكتب‬ ‫‪‬‬ ‫شكلھا بالذاكرة‬ ‫‪‬‬ ‫‪Dr. Rima Rhaim‬‬ ‫‪ITGS 220‬‬ ‫‪Data Structure‬‬  ‫المصفوفات األحادية األبعاد ‪:‬‬ ‫أن المتغٌر (‪ )x‬حاجز مكان فً الذاكرة وخازن قٌمته بداخلة‬ ‫‪Dr. Rima Rhaim‬‬ ‫‪ITGS 220‬‬ ‫‪Data Structure‬‬  ‫]‪Type arrrayname[size of array‬‬ ‫‪‬‬ ‫)‪(index‬ھو عنوان الموقع الذي نرٌد أن نصل إلى محتوٌاتھا فً داخل المصفوفة لنعدل علٌھا‬ ‫‪‬‬ ‫أو نطبعھا ‪.‬‬ ‫مثال أردنا وضع ) ‪( 79‬بثالث موقع فً المصفوفة نكتب ھكذا‬ ‫‪‬‬ ‫;‪first array =79‬‬ ‫‪Dr. Rima Rhaim‬‬ ‫‪ITGS 220‬‬ ‫‪Data Structure‬‬  ‫‪ ‬عند االعالن عن المصفوفة ٌمكننا تھٌئتھا‬ ‫‪ ‬العناصر توضع داخل } { وبٌن كل عنصر واالخر فاصلة ‪,‬‬ ‫‪ ‬مثال‬ ‫; }‪int x = {10 , 20 , 30 , 40 , 50‬‬ ‫شكلھا بالذاكرة‬ ‫‪Dr. Rima Rhaim‬‬ ‫‪ITGS 220‬‬ ‫‪Data Structure‬‬  ‫اذا كان عدد العناصر اكبر من حجم‬ ‫اذا كان عدد العناصر اقل من حجم المصفوفة‬ ‫المصفوفة‬ ‫مثل ‪:‬‬ ‫مثل ‪:‬‬ ‫; }‪int x = {10 , 20 , 30‬‬ ‫‪int x = {10 , 20 , 30 , 40 , 50 ,‬‬ ‫; }‪60 , 70‬‬ ‫سوف ٌظھر خطأ ‪error‬‬ ‫ٌتم تھٌئة العناصر المتبقٌة إلى الصفر‬ ‫‪Dr. Rima Rhaim‬‬ ‫‪ITGS 220‬‬ ‫‪Data Structure‬‬ ‫ماذا ٌحدث اذا لم ٌتم كتابة حجم المصفوفة عند االعالن عنھا ؟‬ ‫‪‬‬ ‫; }‪int x [ ] = {10 , 20 , 30 , 40 , 50‬‬ ‫عندئذ ٌقوم المترجم بتحدٌد حجمھا تلقائٌا وذلك استنادا على عدد‬ ‫عناصرھا المدخلة‬ ‫قوم بطباعة قٌمة العنصر الثالث فً المصفوفة ‪.. x‬‬ ‫‪‬‬ ‫; ]‪Std::cout a[i]; for(i=0;i