Data Structure Stack and Queue Stack Definition: Lists with the restriction that insertions and deletions can be performed in only one position, namely, the end of the list. Access the list from the top. First in, last out (FILO) lists Or last in, first out (LIFO) lists. Basic Concepts Top: the end of the list, namely, the operation end. Bottom: the head of the list Push: Insert an element into
Data Structure List Definition A list is a finite sequence of N elements $write\ as\newline$ $L = (a_1, a_2, a_3，…a_n)\newline$ $The\ size\ of\ this\ list\ is\ n\newline$ $n=0 \rightarrow empty\ list\newline$ element The first element(No predecessor),called “head” The ith element(has only one predecessor and only one successor) The last element(No successor),called “tail” ADT
Data Structure Algorithms Analysis Algorithm Define: A finite, clearly specified sequence of instructions to be followed to solve a problem.(not a program)
Five features Finiteness Definiteness Effectiveness Input Output Design Requirements Correctness Readability Robustness High efficiency and low memory capacity Algorithm Analysis Computing time and memory space are two important resources.
Running time Analysis The estimation of the running time of algorithms.
The running times of algorithms can be changed because of the platform, the properties of the computer, etc.
Data Structure Introduction Data Define: The set of all the symbols can be processed or stored by a computer Example: A data set in a classroom = { desk 1, desk 2,…chair 1, chair2…,stud 1, stud 2,…}
Data Element Define: The term data element is an atomic unit of data that has:
An identification such as a data element name A clear data element definition Example: desk i; chair j; project n…
Data Structure Tree Definition One natural way to define a tree is recursively.
A tree is a collection of nodes. The collection can be empty;
otherwise, a tree consists of a distinguished node r,called root, and zero or more nonempty (sub)trees $T_1, T_2, … T_k$, each of whose roots are connected by a direct edge from r.
Terminology Parent: Node A is the parent of node B, if B is the root of one subtree of A.
