data structures
seminar surveyer Active In SP Posts: 3,541 Joined: Sep 2010 
29122010, 04:43 PM
PRESENTED BY,
S.JAILANI BEEVI WORST CASE ANALYSIS OF SHELL SHORT Although shell sort is simple to code, the analysis of its running time is quite another story. The running time of shellsort depends on the choice of increment sequence. worst case analysis of shell sort.ppt (Size: 2.1 MB / Downloads: 119) 


project uploader Active In SP Posts: 2,534 Joined: Jan 2012 
09012012, 10:42 AM
Definition
Data may be organized in many different ways. The logical or mathematical model of a particular organization is called a data structure. It can also be defined as the choice of representation of data. The choice of a data model depends on two considerations : It must be rich enough to mirror the actual relationship of data in the real world. It should be simple enough that one can effectively process the data when necessary Classification Data structures can be classified as : Linear Nonlinear A data structure is said to be linear if its elements form a sequence. Examples for linear structure include arrays and linked lists. Trees and graphs are examples of nonlinear structures. Linear Data structures The operations performed on linear structures are : Traversal Search Insertion Deletion Sorting Merging Arrays The simplest type of data structure is a onedimensional array or list or linear array. Linear array is a list of finite number (n) of similar data elements referenced respectively by a set of n consecutive numbers , usually 1,2…..n. If we choose a name A for the array , then the elements of A are denoted by subscript notation a1,a2,a3……,an or by the parenthesis notation A(1),A(2)………. ,A(n) or by the bracket notation A[1],A[2]………. , A[n] The value K in A[K] is called a subscript and A[K] is called a subscripted variable. The elements of an array are stored in consecutive memory locations. Linear Array A linear array LA can be pictured as (LB) 1 2 1 2 3 4 5 3 4 (UB) 5 Notations : LB : Lower Bound UB : Upper Bound Length of an array : UB – LB + 1 LOC(LA[K]) : Address of the element LA[K] of the array LA Base (LA) : Address of the first element of LA. LOC (LA [K]) =Base (LA) + w (Klower bound) ,where w is the number of words per memory cell for the array LA. Traversing Linear Arrays Let LA be a collection of elements stored in memory of the computer. Suppose we want to print the contents of the array or to count the number of elements of LA with a given property. This can be accomplished by traversing LA ,that is by accessing and processing each element of exactly once. Algorithm Here LA is a linear array with lower bound LB and upper bound UB. This algorithm traverses LA applying an operation to each element of LA. [Initialize counter] Set K = LB. Repeat steps 3 and 4 while K<=UB [Visit Element] Apply process to LA[K]. [Increment counter.] K = K+1. End of step 2 loop. Exit. Insertion Suppose LA is an array containing 5 names in alphabetical order Algorithm (Inserting into a Linear Array) INSERT(LA,N,K,ITEM) Here LA is a linear array with N elements and K is a positive integer such that K<=N. this algorithm inserts an element ITEM into the Kth position in LA. [Initialize counter.] Set J=N. Repeat steps 3 and 4 while J>=K. [Move Jth element downward.] Set LA[J+1] = LA[J]. [Decrease Counter.] Set J = J1. [End of step 2 loop.] [Insert element.] set LA[K] = ITEM. [Reset N] Set N= N + 1. Exit Deletion Suppose we want to delete an element “smith” from the array. Deletion (Deleting from a Linear array)DELETE(LA,N,K,ITEM) Here LA is a linear array with N elements and K is a positive integer such that K<=N. This algorithm deletes the Kth element from LA. Set ITEM = LA[K] Repeat for J=K to N1: [Move J+1 th element upward] Set LA[J] = LA[J+1]. [End of loop.] [Reset the number N of elements in LA.] Set N=N1 Exit . Searching Let A be a collection of data elements in memory and suppose a specific ITEM of information is given. Searching refers to the operation of finding the location LOC of ITEM in A or printing some message that ITEM does not appear there. The search is said to be successful if ITEM does appear in A and unsuccessful otherwise. Searching Techniques There are different searching techniques Linear Search Binary Search Binary search is more efficient than linear search. It take lesser time for execution. The complexity of searching algorithms is measured in terms of the number of comparisons required to find ITEM in array . Linear Search Suppose A is an array with N elements. To search for a given item in A , compare ITEM with each element of A one by one. This method , which traverses A sequentially to locate ITEM , is called linear search or sequential search. Algorithm (Linear search) LINEAR(A,N,ITEM,LOC) Here A is a linear array with N elements, and ITEM is a given item of information. This algorithm finds the location LOC of ITEM in DATA , or sets LOC=0 if search is unsuccessful. [Insert ITEM at the end of A]. Set A[N+1]=ITEM. [Initialize Counter] Set LOC=1. [Search for ITEM] Repeat while A[LOC] != ITEM Set LOC=LOC+1 [End of loop] [Successful?] If LOC=N+1 , then Set LOC=0. Exit Binary Search Suppose A is an array which is sorted in increasing numerical order or alphabetically. Then there is an extremely efficient searching algorithm, called binary search. The algorithm compares ITEM with the middle element A[MID] where MID is obtained by MID=((BEG+END)/2) If A[MID]=ITEM , then search is successful and set LOC=MID. Otherwise a new segment of A is obtained as follows: If ITEM<A[MID], then ITEM can appear only in the left half of the segment : A[BEG],A[BEG+1],…….A[MID1] So reset END = MID1 and search again. If ITEM>A[MID], then ITEM can appear only in the right half of the segment : A[MID+1],A[MID+2]……..A[END]. So reset BEG=MID+1 and search again. Algorithm (Binary search) BINARY(A,LB,UB,ITEM,LOC) Here A is a sorted array with a lower bound LB and upper bound UB, and ITEM is a given ITEM of information. The variables BEG,MID and END denote, respectively the beginning, end and middle locations of a segment of elements of A. This algorithm finds the location Loc of ITEM in A or sets LOC=NULL. [Initialize segment variables.] Set BEG=LB,END=UB AND MID = INT((BEG+END)/2) Repeat Steps 3 and 4 while BEG<= END and A[MID]!=ITEM If ITEM<A[MID], then: Set END= MID – 1 Else Set BEG = MID + 1 [End of If.] Set MID = INT((BEG+END)/2) [End of step2 loop.] If A[MID]=ITEM , then Set LOC= MID else Set LOC=NULL [End of If] Exit Example Consider an array with 5 elements : Let ITEM= 76 12 , 15 , 20 , 23 , 32 , 45 , 54 , 76 , 98 beg=1,end=9 ,mid=5 Limitations of Binary Search Even if the binary search algorithm is so efficient it requires two conditions : The list must be sorted and One must have direct access to the middle element in any sub list . This means that one must essentially use a sorted array to hold data. But keeping data in sorted array is normally very expensive when there are many insertions and deletions. Sorting Methods Bubble sort Selection sort Quick sort Insertion sort Merge sort Heap sort Bubble Sort Let A be a list of n numbers. Sorting A refers to the operation of rearranging the elements of A so that they are in increasing order. A[1]<A[2]…..<A[N] Steps Compare A[1] and A[2] and arrange them in desired order, so that A[1]<A[2]. Then compare A[2] and A[3] and arrange them so that A[2]<A[3].Continue until we compare A[N1] with A[N]. This step involve N1 comparisons. Repeat step 1 with one less comparison .That is ,now we stop after we compare and rearrange A[N2] and A[N1] …………………. ……………….. Step N1. Compare A[1] with A[2] and arrange them so that A[1]<A[2] After N1 steps , the list will be in sorted order. Algorithm (Bubble Sort) BUBBLE (A,N) Here A is an array with N elements. This algorithm sorts the elements in A. Repeat steps 2 and 3 for K=1 to N1. Set PTR=1[Initializes a pointer PTR.] Repeat while PTR<=NK [Executes pass] If A[PTR]>A[PTR+1], then : Interchange A[PTR] and A[PTR+1]. [End of If] Set PTR=PTR+1. [End of inner loop] [End of outer loop] Exit Example 32 , 27 , 51 ,66 , 23, 13,85,57 Complexity of Algorithms An algorithm is a welldefined list of steps for solving a particular problem. The time and space it uses are two major measures of the efficiency of the algorithm. The complexity of an algorithm is the function which gives the running time or space in terms of the input size. Complexity of Linear Search In linear search we read each item in the list one at a time and compare it with the item to be searched. The time required to execute this algorithm is proportional to the number of comparisons. The average number of comparisons required in a list of n elements = n/2. => complexity of linear search , C (n)=n/2. MultiDimensional arrays Linear arrays in which each element is referenced by a single subscript is called a one – dimensional array. Arrays in which elements are referenced by more than one subscript is called multidimensional arrays. A twodimensional array A is a collection of m*n elements such that each element is specified by a pair of subscripts A [i][j] Representation of 2D arrays A 2D array is stored in memory by a block of m*n sequential memory locations. The programming language will store the array A either Column by column (columnmajor order) Row by row (rowmajor order) 2D arrays For a onedimensional array computer uses the formula LOC(A[K])=Base (A) +w(K1) to find the address of A[K]. For a 2D array the address of A[J,K] is found out using the formula LOC(A[J,K])=Base(A)+w[M(K1)+(J1)] (Column major order) LOC(A[J,K] = Base (A)+[N(J1)+(K1)] Stacks and Queues The linear lists and arrays allow one to insert and delete elements at any place in the list : at the beginning , at the end or in the middle. But there are certain situations in computer science when one wants to restrict insertions and deletions so that they can take place only at the beginning or the end of the list , not in the middle. Two of the data structures that are useful in such situations are stacks and queues. Stacks A Stack is a linear structure in which items may be added or removed only at one end. A stack is a homogeneous collection of items of any one type, arranged linearly with access at one end only, called the top. Formally this type of stack is called a Last In, First Out (LIFO) stack. Data is added to the stack using the Push operation, and removed using the Pop operation. Stacks Consider the following example : Operations on Stack Two basic operations associated with stack include : Push : term used to indicate insertion. Pop : term used to indicate deletion. Suppose the following 5 elements are to be inserted or pushed on to the stack: a, b ,c ,d ,e Operations on Stack The elements from a stack are poped in the reverse order. Elements are poped in the following order. Array Representation of Stack Stacks may be represented in the computer in various ways ,usually by means of a oneway list or a linear array. Stack can be maintained by a linear array STACK, a variable TOP , which contains the location of the top element of the stack and a variable MAXSTK which gives the maximum number of elements that can be held by the stack. The condition TOP=0 or TOP=NULL will indicate that the stack is empty. Algorithm PUSH(STACK,TOP,MAXSTK,ITEM) This procedure pushes an ITEM onto stack. [Stack already filled?] if TOP=MAXSTK ,then Print : OVERFLOW , and Return set TOP=TOP+1[Increases TOP by 1.] Set STACK[TOP] =ITEM. [Inserts ITEM in new TOP position.] Return. Algorithm POP(STACK,TOP,ITEM) This procedure deletes the top element of the stack and assigns it to the variable ITEM [Stack has an item to be removed?] if TOP=0 , then print UNDERFLOW and Return. Set ITEM = STACK[TOP].[ Assigns TOP element to ITEM] Set TOP= TOP – 1 .[Decrease TOP by 1] Return. Queues How do we use lists? In many cases, we want to use a list, but we only want a limited subset of its operations example: Use a list to store a waiting line of customers for a bookstore. As each customer arrives, place him/her at the end of the line. Serve customers in the order that they arrived. Which list methods do we need here, and which do we not need? Common idiom: "FIFO" Many times, we will use a list in a way where we always add to the end, and always remove from the front (like the previous example) The first element put into the list will be the first element we take out of the list FirstIn, FirstOut ("FIFO") Let's create a new type of collection which is a limited version of List, tailored to this type of usage: a Queue Queues A queue is a linear list in which items may be added at one end and items may be removed only at the other end. Deletions can take place only at one end , called the front , and insertions can take place only at the other end , called the rear. Queues are also called firstinfirstout lists , since the first element in a queue will be the first element out of the queue. In other words , the order in which elements enter a queue is the order in which they leave. Representation of Queues Queues may be represented in various ways , usually by means of oneway lists or linear arrays. Queues will be maintained by an array QUEUE and two pointer variables , FRONT, containing the location of the front element and REAR , containing the location of the rear element of the queue. The condition FRONT=NULL indicates that the queue is empty. offer or enqueue: add an element to the back remove or dequeue: remove and return the element at the front peek: return (but not remove) front element peek on an empty queue returns null Circular arrays We can treat the array holding the queue elements as circular (joined at the ends) Elements were added to this queue in the order 11, 22, 33, 44, 55, and will be removed in the same order Use: front = (front + 1) % Queue.length;and: rear = (rear + 1) % Queue.length; Full and empty queues If the queue were to become completely full, it would look like this: If we were then to remove all eight elements, making the queue completely empty, it would look like this: Algorithm QINSERT(QUEUE,N,FRONT,REAR,ITEM) This procedure inserts an element ITEM into a queue. [ Queue already filled?] If FRONT=1 and REAR=N , or if FRONT=REAR+1, then: Write : OVERFLOW AND Return. [ Find new value of REAR] if FRONT=NULL , then [Queue initially empty] set FRONT=1 and REAR=1. Else if REAR=N then : set REAR=1. Else Set REAR=REAR+1 [ End of if structure.] Set QUEUE[REAR]=ITEM. [This inserts new element] return. More Refer topicideashowtodatastructures?pid=61222#pid61222 topicideashowtodatastructuresinterviewquesans topicideashowtofileorganizationtechniquesrecordaccessmethodsdatastructures 


seminar addict Super Moderator Posts: 6,592 Joined: Jul 2011 
01022012, 12:03 PM
data structures
Data structre.pptx (Size: 46.62 KB / Downloads: 50) Types of data structures 1. According to nature of Size: (i) Static data structure (ii) Dynamic data structure 2. According to occurrence: (i) Linear data structure (ii) Nonlinear data structure 3. Primitive and Nonprimitive data structure According to nature of Size 2. Dynamic data structure: Allow to change its size during program execution(add or delete elements at run time) Example: Link list, tree, graph etc. Primitive and Nonprimitive data structure 1. Primitive Data Structure: Basic data structure and directly operated upon by the machine instructions. Example: integer , float, character. 2.Nonprimitive Data Structure: Derived from primitive data structure. Emphasising on structuring of a group of homogeneous or heterogeneous data items. Example: Array , List , Tree , Graph. 


seminar paper Active In SP Posts: 6,455 Joined: Feb 2012 
03032012, 03:55 PM
data structures
datastruct.doc (Size: 100 KB / Downloads: 23) 1. What is data structure? A data structure is a way of organizing data that considers not only the items stored, but also their relationship to each other. Advance knowledge about the relationship between data items allows designing of efficient algorithms for the manipulation of data. 2. List out the areas in which data structures are applied extensively? Compiler Design, Operating System, Database Management System, Statistical analysis package, Numerical Analysis, Graphics, Artificial Intelligence, Simulation 3. What are the major data structures used in the following areas : RDBMS, Network data model & Hierarchical data model. RDBMS – Array (i.e. Array of structures) Network data model – Graph Hierarchical data model – Trees 4. If you are using C language to implement the heterogeneous linked list, what pointer type will you use? The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type. 5. Minimum number of queues needed to implement the priority queue? Two. One queue is used for actual storing of data and another for storing priorities. 6. What is the data structures used to perform recursion? Stack. Because of its LIFO (Last In First Out) property it remembers its ‘caller’ so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls. Every recursive function has its equivalent iterative (nonrecursive) function. Even when such equivalent iterative procedures are written, explicit stack is to be used. 


seminar ideas Super Moderator Posts: 10,003 Joined: Apr 2012 
04082012, 10:17 AM
to get information about the topic " structures" full report ppt and related topic refer the link bellow
topicideashowtostructures seminar and presentationproject and implimentationsattachment.php?aid=29417 topicideashowtodatastructures topicideashowtodatastructuresinterviewquesans topicideashowtoconnectionsinsteelstructures 


