Scribd
Importer
373 vues308 pages

Ds Notes

Le document présente une introduction aux structures de données, y compris les types de données fondamentaux, les algorithmes et leur efficacité, ainsi que les listes chaînées et les tableaux. Il décrit les différences entre les structures de données linéaires et non linéaires, ainsi que les structures de données statiques et dynamiques. Les applications des listes chaînées et des files d'attente dans divers contextes, tels que les systèmes d'exploitation et les opérations mathématiques, sont également abordées.

Transféré par

sahuanshika557
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
373 vues308 pages

Ds Notes

Le document présente une introduction aux structures de données, y compris les types de données fondamentaux, les algorithmes et leur efficacité, ainsi que les listes chaînées et les tableaux. Il décrit les différences entre les structures de données linéaires et non linéaires, ainsi que les structures de données statiques et dynamiques. Les applications des listes chaînées et des files d'attente dans divers contextes, tels que les systèmes d'exploitation et les opérations mathématiques, sont également abordées.

Transféré par

sahuanshika557
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
CU Genes) sae CS IT & CS Allied PRA Unit-1 Lecture-1 Today’s Target Pen Seah siiintilied Mati ile By Dr. Nidhi Parashar Ma'am Ph.D (CSE) [Link] Gold Medalist Net Qualified CS IT & CS Allied Ill-Sem Se ER a3 emer US RY GLI Introduction: Basic Terminology, Elementary Data Organization, Built in Data Types in C. Algorithm, Efficiency of an Algorithm, Time and Space Complexity, Asymptotic notations: Big Oh, Big Theta and Big Omega, Time-Space trade- ae en aU) Agrays: Definition, Single and Multidimensional Arrays, Representation of Arrays: Row Major Order, and Column Major Order, Derivation of Index Formulae for 1-0,2-D,3-D and n-D Array Application of arrays, Sparse Matrices and Pee Le Linked lists: Array Implementation and Pointer Implementation of Singly Linked Lists, Doubly Linked List, Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal, Polynomial Representation and Addition Subtraction & Multiplications of Single variable & Two variables Polynomial. ER UL PER eee Rone od Cee Ce erate ccna It is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed ER eRe ae OC Ree ene ERC re RnR keen rt Pe a nes ee RSC Seem Rea) Pee CRE eee ee sh eR RU a a Basic Terminology: Elementary Data Organization ones eer nea A single value or set of values. Example: 101 Ram 20 Information Acaningful data/processed data Example; Roll No.: 101, Name: Ram, Aj OR CER Cage R Unt een ra ects Cee ERED aca noma OPER OURR TE eer ht eR PLO ROE ane MST ten La Ne A noun that has certainattributes or properties. Example: student, emplc Ne ee et cee na ee a eR] values(numeri¢’6r non-numeric) Avista eT Us LE ON) G ee Cae Cam ted LIEN ed ASS it brat) rs iat PB MeO oreo Pam emery Dyson oa) Represents a column of values in a table. (i.¢.) One attribute information Eee amc SOR ERE ECS) ERO mee cna cee nae ERE ee Sntlby > Collection of records of the entities in a given entity set Pe CRUE Ur Ace m RCU Raa R TE) RST BS CRUE NM ONAL e SOLE BETS} K is called a primary key and the values k1, k2. PR oe Bod CORO Same data item with same memory space for each item and same length for all records. (e.g.) personal details of a student ee RN OR RCO CEU RUE e es cc eet come ca AY ECOSOC eRe ed TCR ROR en en Seo cece RE nea eset col sat een ed Oe ete Re COR ee eR Un cc es nce ec) Ree Te a ees Storing and retrieving user data as quickly as feasible for improved performance of an algorithm SO OR Re Ue eMac ORL LeLee PES UROL oe CCRC oR re Sumo oe 1. Yogical or mathematical description gf the structure fiplementation of the structure on a computer Sad i mala d SO a UTR t SAT ROR RSet is PERS te tee har ROR Osa ete td Doe nee Rte ted Primitive DS > Primitive data structures are the fundamental data types which are supported by a programming These data types consists of characters that cannot be divided and hence they also called simple data types ee ee cee oD Non-Primitive DS: eee ne Ee Rare eS Ce eee SO cone) eee Ne eee eos ala ik Lain EE SEN em eS sr ee ma et de Lyrs OU ers ea Leta i enreta ys DS is said to be linear if its elements are arranged in sequence one after the other in particular Comme CRT Cntr’ aoe CEC EMEC OE UCR amma need not be sequential It can be traversed on a single run. That is, if [Link] from the first element, we can traverse all elements sequentially in a single pass. Example: Arrays, linked lists, stacks and queues are examples of linear data structures. Cee US eR eR eC ROC LL type. Type of elements that can be stored in arrays is determined by programming language BS] T a Gy AWAY Cigvl io a mG ke rama Base asstners, Pe BTC B ess aeRO es RUC Roe Re AO Me RCT RR TUR roe mL ORNS Oa OR eR nets naar easy ee aCe me ee CRC OEM mos on ROT RT PAN OE ROR ec Applications of Linked Lists > Implementing stacks, queues, binary trees and graphs of predefined size. > Polynomial implementation for mathematical operations Orne cn ee ROM en eee Oe aeRO ORC O Re cS Circular linked list is used in a slidé show to go back to the first slide after last slide is displayed Doubly linked list is used to implement forward and backward buttons in a browser to move backwards and forward in the opened pages of a website Circular queue is used to maintain the playing sequence of multiple players in a game. Retr 4. Queue! era cents Oem mens ys > Works in the FIFO principle PEM eas eee Meo aT Pema Cand removed first Ton va Bile Pe ee em Om ECM > dt works like a queue of people in the ticket as Sa eC oe ad Om ee cr nT oem Pos ranacoa ine MeO eee utes Caceres eae Ans Tt Tc a PEO es See een (een M Na SCRE CR NOSUIna ss css eee ett ec Ose ene Cant Matching of parenthesis Siri eara cans} A ER eon Sc Re cra PRR Cubes MRSC EOC Ret or eet aCe St UNDO and REDO functions in an editor. —_ Applications of Queues: PRR Ee ues Ry car tense > Job scheduler operations of OS like a print buffer queue, keyboard buffer queue to store the keys essed by user; Job scheduling, CPU schéduling, Disk Scheduling Pe eee OTe creo cd Data transfer between peripheral devices and CPU eee Mme eS kee ETE mia atiiag reas Oe ae BR eae SUR ce Oe eR RU Pema eS LOE) Q.2 List out the areas in which data structures are applied-éxtensively? (AKTU 2017-18) ORR eee ko ecm ae COP cera miei ay CVT) (ice IES) ata CS IT & CS Allied PR Unit-1 Lecture-2 Today’s Target Types of Data Structure contd.. Peat tween Linear and Non-linear Data Structures Static vs Dynamic Data Structuré By Dr. Nidhi Parashar Ma'am nau oe eaters Ph.D (CSE) OSCR eR Mech Gold Medalist STi Trea Net Qualified rie mO eon SSDs > Data elements are not arranged in sequence. Instead, they are arranged in a hierarchical manner Sree eo Ree ROR ee os eRe RRs ee Mme) > It requires multiple runs. That is, if we start from the first element it might not be possible x aan en ene Co al] fires > Data frequently contain a hierarchical relationship between various elements. The data structure which reflects this relationship is called a tree. It is also a collection of vertices and edges. However cere ura Re ts ea cnn Cat eo For example, an employee personnel record may contain the following data items erro Peet ee ERS ECMus tT acne et Rs en ROM eer ee TCs ego CET Ra een ee ete she ted The data structure which reflects this type of relationship is called a graph Oe ee oR oe eR oes ROR ee Tans Difference between Linear and Non-linear Data Structures errs eS TO eeu REN me eee element is attached to its previous and next adjacent el |Easy implementation in comparison to non-linear DS Sane |Data elements can be traversed ina si OOSmMR Meru eeu RSH a sy |Examples : array, stack, queue, linked list, ete Useful for simple data storage and manipulation Non-linear Data Structure s are attached in hierarchically manner data elem | bet feeKenalcecet daa cminaeal cal multiple leve {Complex implementation |Data elements can't be traversed in a single run only Memory is utilized in an efficient way Examples: trees and graphs Useful for representing complex relationships and data hierarchies, such as in social networks, file systems, or Cancers Static Data Structure ys Dynam Rice Ratios a CM Ce BR ee eer ee en eee eee eee eee TO) Pan oer Eee SOR CRS eRe ee ee eee ere a a tnt a ¢ Sein (acs sage7 eae RIC Cena Sy “FTheir memory size can be changed during program execution. > Memory can be dynamically allocated or deallocated during program ex Se Se Sesto UE eae Oca Nec memory allocation and deallocation ial Ta} va) aaa AT ay Elites) Na Nong Proton) Roy ise tas SCC Pee ated See eee Ee ERS et ied AY UT aE ee cee eee on Rm Cel ecco TELL PSS OE UR Ree MR eRe NR OMm TCE eee ee CTO R MTR Nme erste cu reused Access time may be slower due to indexing Neca aS Se eae IN outs Linked Lists va) TE RU eS ea) ry = ; sw

Vous aimerez peut-être aussi