Which is the diff between the two fol.decalration?
.the first declaration is a structure .A structure is a group of members of diff types. A structure stres its members at unique memory locations. The size of the structure is the sum of the size of all the members of the structure.
The second declaration is an union .A union is a collection of types from which a variable can have diff types at diff times.
A union stres its members in the same memory location The size of the union is equal to the size of the largest element of the union.We can use only one member of the union at a time
struct A contain all x,y,p (each element is separateand distinct)
unionB contains only one of the elements x,y,p at a given time
Using the declaration A*pa then:
pa->y: refers the the second member of the structure A,which is a value of foalt type ;pa -> y refer a float member
pa-> p refers the third members of the structure A ,which is a pointer to a char type ;pa-> p refers a printer
2. explain the fol signatures
int f put c(int ch,FILE*in)
writes "ch" to the current position in the specified file "in"and increases the file position to the next character
the function returns a char and has 2 param:the first param is a char and the second is a printer to a FILE type;i.e a printer to an opened file
char * fgets(char *dest,int n ,FILE * in); reads characters from the fine "in" and stors yhem in "dest".The function returns a pointer to a char and has 3 parameters.
The firs param. Is a pointer to a char representing the first type of the buffer to store the road data
The second param.is an integer representing the max.number of bytes to be read
The third param. Is a pointer to a FILE type,i.e a pointer to an opened file
Both are functions in the input/output liberary , so in order to use them wee need to use in the C file the declaration : #include<stdio.h> which specifies the file containing the prototypes for the functions in i/o library
3. define the loop
A loop invariation is a statement S that is true each time we reach a particular point in the loop
Ex: Factorial computation
Scanf("% d",& u);
I=2;
Fact =1;
While (i<== n)
(e)->
printf ("%d\n",fact);
Statement : S(j) If we reach the loop test with the var. i(i<=n) having the value j , then the value of the var. fact is (j-1)!
Basis: S(2): i=2;
Fact 2-1)!=1!
Induction: we supp.S(j) to be true => S(j+1) is true
a). j>n:loop breacks before i=j+1=>S(j+1) is trivialy true
b). j<=n: before line (l) we have the state
example of a data structure recursively defined:
Linked list
6. build the structure tree and estimate the running time
for (i=0;i<n-1;i++)
for (j=i+1;j<n;j++)
}
for (1)-(6)
for(2)-(6)
for(3)-(6)
(3) 6) (5)Q1 (6)Q1
(4)Q1
Simple statements are represented by elipses A component statement is analised after all the statements that are its constituent parts are analized
Q1
If (3)-(4) Q1
Q1
Q1
Block (3)-(6) Q1+Q1+Q1=>Q1
for(2)-(6) Q(n-i-1)
for (1)-(6) i=0..n-2,so we can use Qn which is an upper loud to Q(n-i-1)
and also we go around the loops (n-1) times=> T(n)=(n-1)*O(n)=
=O(n la patrat -n ) so O(n) is an upper load and the result is T(n)=O(n)
the relation between data model and data structure
A data model is an abstraction used to describe problems .Can be find in two contexts
a). abstractions fregnently used in the description of the solution of a problem
b). associated with programming languages and computers .The data model of a language is the solution of all predefined types offered by that language(expl: C data mdel contains char , integers, other types of numbers , structures , points and functions).Data models have 2 aspects for programming: staticLtype System ) defines the values that a data can have and dynamic : operations that can be executed with data
A data structure is a programming language used to represent data models which do not have built -in representations in that programming language .The main data statements used to represent the true data model in C language are :
+ Array of points :node -structures:label;array of points
type def struct NODE *pNODE;
struct NODE
+Left -Chold Right liling representation :north-structure:label;leftmost child(P1);right sibeling (P2)
type def struct NODE*pNODE;
struct NODE
what kind of tree is represented in the fol.fig.
The given tree is a balanced partially ordered tree
Def: Partially order tree (POT) is a labeled linary tree with the following properties:
a). the labels of the models are elements with "priority"
b). the element stored at a node has at least as large a priority as the elements stored at the children of the nodes
Obs:The element at the root of any subtree is always the largest element of the subtree , but its priority is not necesarly unique because equals elements can appear on different labels on the tree as large as the conditions in the definition are fullfield
Def: A Balanced POT-POT in which all possible models exists at each level , except the button mast. The level are as far to the left as possible.
In the C programming language , a balanced POT is represented by a heap data structure
Kind of an array (A[i]) with a special interpretation of indices
A[0]-not used
A[1]- contains the root
A[2]- contains the leftchild of the root( A[1])
A[3]-contains the rightchild of the root ( A[1])
...
A[2i]-contains the left child of the node in A[i]
A[2iN]-contains the rightchild of the node in A[i]
And A[i]>=max(A[1i];A[2i+1])
In order to implement the insert operation in C , we use:
x-element to be inserted
pn-point to the current size of the POT
void insert(intA[]; int x;int*pn)
using bubbleUp (int A[ ];int i)
//tests if the elem in the indicated position is greater then its parent and is so, swaps yhe two elements
}
void swap (int A[ ],int I , int j )
9. compare the list data model with the set data model
A LIST is a finite segment of 0 śn elements , usually of the same type
A SET is a collection of members having the same property
The main differences between them are:
-the attributes of a list element describe its type or its position in the list (first, last, i) so , an order of elements is achived .In a set the order of elements is arbitrary so ==
-In a list one element can have more occurrences : (a;h;a).In a set all the members are different so, they cannot repair themselves
The similarities between the list data model and the set data model regard the notions of length /size ; sublist/subset and equality of list/sets
The length of a list is the nr. Of ocurances of elements in a list .The size of a set represents the nr. Of members of that set ..Regarding the size , a set can be finite or infinite
With the notion of sublist (For a list L a1,a2,.,a n)
Any i,j s.t 1≤i≤j≤n →(ai , .. , aj) is a sublist of L) we can define the notions of prefix of a list and suffix of a list
For any S,T sets , if S in T then S is called subset of T . A proper subset is : S<T and it exists tapartine T,t nu apartine S.T is called a super set for S.
The Power Set of the set S is the set of all subsetsof S .So, for S=→P(S)=,{b.} which has the size =2(la)n
The operation with Lists are:
Insert ,delete,LookUp ,concatenation ,first(L) ,last(L) , retrieve,(I,L), Length(L), is empty (L).
The operation with sets are :
The data structures for implementation of the list data model are :linked list , sorted list ,double linked list and array based structures
The data structures for implementation of the set data model are:linked list , characteristic vector and based table.
10.consider the fol.label undirected graph
A connected component of an undirect graph is a subset of nodes and edges s.t. all nodes are connected by a path and no problem exists outside the component.In our given graph there are 2 connected component:desenu unu (unu roman ),desenul doi 7 doi roman
b).adjuncy list for the connected comp.with 6 noded(unu roman )
|
