curs10

1Scopul cursului

CAP.10. Recursivitatea

10.1. Funcii recursive

10.2. Transferarea argumentelor ctre funcia main( )

10.3. Structuri dinamice

Programarea calculatoarelor I -Gyorodi Cornelia

2Funcii recursive

Prin recursivitate se nelege proprietateaunei funcii de a se putea apela pe ea nsi.

O funcie se poate apela fie:

direct, n blocul propriu de instruciuni,

indirect , prin apelul n cadrul altor funcii


Funcii recursive

Programarea calculatoarelor I -Gyorodi Cornelia 3

Exemplu

# include < stdio.h >

void suma( int i ) ;

void main( void ) {

suma( 0 ) ;

}

void suma( int i ) {

if ( i < 10 ) {

suma( i+1 );

printf( " %d " , i );

}

}Programarea calculatoarelor I -

Gyorodi Cornelia 4

Acest program afieaz 9 8 7 6 5 4 3 2 1 0.

Funcii recursive

Cnd este apelat o funcie, parametrii i datele locale sunt salvate pe stiv.

Cnd o funcie este apelat recursiv, funcia ncepe execuia cu un nou set de parametri i variabile locale, dar codurile care constituie funcia rmn aceleai.

Orice funcie recursiv va avea o instruciune de decizie (if) care va determina oprirea apelului recursiv a funciei.



Copierea unui ir ntr-un alt ir folosind recursivitatea.


void rcopy( char * s1, char * s2 );

void main( void )

{

char str[ 80 ] ;

copy ( str, " acesta este un test " ) ;

puts ( str ) ;

}

void rcopy( char * s1, char * s2 )

{

if ( *s2 ) { /*daca nu este sfirsitul sirului s2 */

*s1 ++ = *s2++ ;

rcopy ( s1, s2 ) ;

}

else *s1 = ' \0 ' ; /*caracterul null incheie sirul */

}

Funcii recursive

Este posibil s avem programe n care dou sau mai multe funcii sunt recursive mutual.

Recursivitatea mutual apare cnd o funcie o apeleaz pe cealalt, care apoi o apeleaz pe prima.


# include < stadio.h > /* recursivitate mutual*/

void f2 ( int b );

void f1 ( int a );

void main ( void )

{

f1 ( 30 ) ;

}

void f1 ( int a )

{

if ( a )

f2 ( a -1 );

printf ( " %d " , a );

}

void f2 ( int b )

{

printf ( " . " ) ;

if ( b )

f1( b-1 );

}


9Transferarea argumentelor ctre funcia main( )

Un argument command-line este un parametru careurmeaz dup numele programului, pe linia de comanda sistemului de operare.

Programele scrise n limbajul C pot de asemenea utilizaargumente command-line. Acestea sunt transferateprogramului C prin dou argumente ale funciei main.

main(int argc, char * argv[ ] )

Parametrul argc conine numrul argumentelor command-line i este un ntreg. El trebuie s fie totdeauna cel puin 1, deoarece numele programului este considerat ca primul argument.

Parametrul argv este un tablou de pointeri ctre iruri.

char * argv[ ] ;


Transferarea argumentelor ctre funcia main( )

Fiecare argument command-line trebuie separat printr-un spaiu sau printr-un tab.

Virgula i punctul sau virgula sau altele ca acestea nu sunt considerate separatori. Dac trebuie s transferm un argument command-line care n corpul su conine spaii, atunci argumentul trebuie nchis ntre ghilimele, de exemplu " acesta este un test " .

Numele argumentelor argc i argv sunt absolut arbitrare, ns aceste argumente au fost denumite argci argv nc de la originile limbajului C.


11

Transferarea argumentelor ctre funcia main( )

Exemplu de program care afieaz toate argumentele command-line cu care el estelansat n execuie:


void main ( int argc, char * argv[ ] ) {

int i ;

for ( i = 1 ; i < argc ; i+ + )

printf ( " %s " , argv[ i ] ) ;

}


Funcii de conversie

Funcii de conversie :

int atoi ( char * str ); - returneaz ntregul echivalent al irului str.

double atof ( char * str ); - returneaz date de tip double al irului str.

long atof ( char * str ); - returneaz data de tip long echiv. a irului str.



void main ( int argc, char * argv[ ] )

{

int i ;

double d ;

long l ;

if ( argc != 4 ) {

printf(" Numar de parametri incorect \n");

exit(1);

}

else

{

i = atoi (argv[ 1 ]);

d = atol (argv [ 2 ]);

l = atol (argv [ 3 ]) ;

printf ( " %d %f %lf " , i, d, l );

}


Structuri dinamice

Structurile de date dinamice

Sunt structurile de date care i mresc respectiv ii micoreaz dimensiune pe durata execuiei programului

Stive

Permite inserarea i tergere elementelor numai din vrful stivei

Cozi

Permite inserarea n spatele cozi i tergerea din faa cozi

Arbori binari

Crete viteza de cutare i adaug elemnetelor ordonat


Structuri cu autoreferire (Self-referential structures)



Structuri care conin un pointer la o structur de acelei tip

Pot fi legate impreun pentru a forma structuri de date cum ar fi liste, cozi, stive, arbori.

Se termin cu un pointer NULL (0)

Diagrama a dou structuri cu autoreferire legate mpreun

1015

NULL pointer (points to nothing)Membru data

i pointerul



struct node {

int data;

struct node *nextPtr;

}

nextPtr

Indic la un obiect de tipul node

Este cunoscut cu denumirea de legtur Leag un nod de un alt nod

Alocarea dinamic a memoriei


Alocarea dinamic a memoriei Permite alocarea respectiv dezalocarea memoriei n timpul

execuiei programului

Malloc funcie care permite alocarea memoriei

Takes number of bytes to allocate Utilizaz sizeof pentru a determina mrimea unui obiect

Returneaz un pointer de tip void * Un pointer void * poate fi asignat la orice pointer

Dac nu exist memorie disponibil returneaz NULL

ExemplenewPtr = malloc( sizeof( struct node ) );

Free funcie care dezaloc memorie

Dezaloc memorie alocat prin funcia malloc

free ( newPtr );

Exemplu


/**

* Operaia de inserare i tergere intr-o list

*/

#include

#include

struct listNode { /* structur cu autoreferire */

char data;

struct listNode *nextPtr;

};

typedef struct listNode ListNode;

typedef ListNode *ListNodePtr;

void insert( ListNodePtr *, char );

char delete( ListNodePtr *, char );

int isEmpty( ListNodePtr );

void printList( ListNodePtr );

void instructions( void );


int main()

{

ListNodePtr startPtr = NULL;

int choice;

char item;

instructions(); /* display the menu */

printf( "? " );

scanf( "%d", &choice );

while ( choice != 3 ) {

switch ( choice ) {

case 1:

printf( "Enter a character: " );

scanf( "\n%c", &item );

insert( &startPtr, item );

printList( startPtr );

break;

case 2:

if ( !isEmpty( startPtr ) ) {

printf( "Enter character to be

deleted: " );

scanf( "\n%c", &item );


if ( delete( &startPtr, item ) ) {

printf( "%c deleted.\n", item );

printList( startPtr );

}

else

printf("%c not found.\n\n", item);

}

else

printf( "List is empty.\n\n" );

break;

default:

printf( "Invalid choice.\n\n" );

instructions();

break;

}

printf( "? " );

scanf( "%d", &choice );

}

printf( "End of run.\n" );

return EXIT_SUCCESS;

}


/* Print the instructions */

void instructions( void )

{

printf( "Enter your choice:\n

" 1 to insert an element into the list.\n

" 2 to delete an element from the list.\n

" 3 to end.\n" );

}

/* Insert a new value into the list in sorted order */

void insert( ListNodePtr *sPtr, char value )

{

ListNodePtr newPtr, previousPtr, currentPtr;

newPtr = malloc( sizeof( ListNode ) );

if ( newPtr != NULL ) { /* is space available */

newPtr->data = value;

newPtr->nextPtr = NULL;

previousPtr = NULL;

currentPtr = *sPtr;


while ( currentPtr != NULL && value > currentPtr->data ) {

previousPtr = currentPtr; /* walk to ... */

currentPtr = currentPtr->nextPtr; /* ... next node */

}

if ( previousPtr == NULL ) {

newPtr->nextPtr = *sPtr;

*sPtr = newPtr;

}

else {

previousPtr->nextPtr = newPtr;

newPtr->nextPtr = currentPtr;

}

}

else

printf( "%c not inserted. No memory available.\n", value );

}


/* Delete a list element */

char delete( ListNodePtr *sPtr, char value )

{

ListNodePtr previousPtr, currentPtr, tempPtr;

if ( value == ( *sPtr )->data ) {

tempPtr = *sPtr;

*sPtr = ( *sPtr )->nextPtr; /* de-thread the node */

free( tempPtr ); /* free the de-threaded node */

return value;

}

else {

previousPtr = *sPtr;

currentPtr = ( *sPtr )->nextPtr;

while ( currentPtr != NULL && currentPtr->data != value ) {

previousPtr = currentPtr; /* walk to ... */

currentPtr = currentPtr->nextPtr; /* ... next node */

}

if ( currentPtr != NULL ) {

tempPtr = currentPtr;

previousPtr->nextPtr = currentPtr->nextPtr;

free( tempPtr );

return value;

}

}

return '\0';

}


/* Return 1 if the list is empty, 0 otherwise */

int isEmpty( ListNodePtr sPtr ) {

return sPtr == NULL;

}

/* Print the list */

void printList( ListNodePtr currentPtr ) {

if ( currentPtr == NULL )

printf( "List is empty.\n\n" );

else {

printf( "The list is:\n" );

while ( currentPtr != NULL ) {

printf( "%c --> ", currentPtr->data );

currentPtr = currentPtr->nextPtr;

}

printf( "NULL\n\n" );

}

}

Date post:	19-Dec-2015
Category:	Documents
Upload:	micula-aurel
View:	216 times
Download:	3 times

curs10

Documents