Cursos gratuitos -- Algoritmos -- Coursera + Princeton

O site Coursera oferece muitos cursos gratuitos promovidos por renomadas universidades de todo o mundo:

https://www.coursera.org/

Em destaque, deixo aqui a sugestão para estudo de algoritmos:

Algorithms, Part I - https://www.coursera.org/course/algs4partI
Algorithms, Part II - https://www.coursera.org/course/algs4partII

Robert Sedgewick, Kevin Wayne

Este curso aborda o conteúdo essencial que qualquer programador sério necessite conhecer sobre algoritmos e estruturas de dados, com ênfase em aplicações e análise científica de performance em implementações na linguagem de programação Java.


O livro texto recomendado é:

Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne [ Amazon · Pearson · InformIT ] 


Link para consulta: http://algs4.cs.princeton.edu/home/

Bom estudo.

Tutorial de Ponteiros e Arrays em C

Um excelente tutorial sobre ponteiros, arrays, strings, alocação dinâmica de memória, struct e typedef em C Ansi:


http://cesarakg.freeshell.org/pointers.html


Bom estudo.

Lista genérica para dados estruturados

Continuando com a abordagem de typedef struct, apresento mais alguns exemplos e um em especial que é o da definição de um node em uma lista ligada.

Na estrutura No, são usados ponteiros do tipo void, pois não sabemos que tipo de estrutura será usado na aplicação.

Para testar a lista ligada, foram usados exemplos com estruturas pre-definidas: Paciente e Salario.

No caso de strings, também é apresentado um exemplo de lista com os nomes dos dias da semana sem haver a necessidade de definir previamente uma estrutura.

A seguir o código na linguagem C Ansi:

---

#include &ltstdio.h&gt
#include &ltstdlib.h&gt
#include &ltstring.h&gt


// exemplo de dados estruturados e algumas funções relacionadas

typedef struct{
    int prontuario;
    char nome[40];
    int idade;
    char rg[13];
} Paciente;


Paciente* criaPaciente( int prontuario, char *nome, int idade, char *rg ){

    Paciente *tmp = (Paciente *) calloc( sizeof(Paciente), 1 );

    tmp->prontuario = prontuario;
    strcpy( tmp->nome, nome );
    tmp->idade = idade;
    strcpy( tmp->rg, rg );

    return tmp;

}


void mostraPaciente( Paciente *tmp ){

    printf("\n\nPaciente: \t[%05d] [%-40s]\nIdade: \t\t[%3d]\t\tRG: [%-13s]\n",
           tmp->prontuario,
           tmp->nome,
           tmp->idade,
           tmp->rg
           );

}


// outro exemplo de dados estruturados

typedef struct{
    double salario;
    char *cargo;
} Salario;


Salario* criaSalario( double salario, char *cargo ){

    Salario *tmp = (Salario *) calloc( sizeof( Salario ), 1 );

    tmp->salario = salario;
    tmp->cargo = cargo;

    return tmp;

}


// estruturas e funções de uma lista generica

typedef struct{
    void *dados;
    void *proximo;
    void *anterior;
} No;


typedef struct{
    No *primeiro;
    No *corrente;
    No *ultimo;
    int tamanho;
} Lista;


Lista* criaLista(){

    Lista *tmp = (Lista *) calloc( sizeof(Lista),1);

    tmp->primeiro = NULL;
    tmp->corrente = NULL;
    tmp->ultimo = NULL;
    tmp->tamanho = 0;

    return tmp;

}


void insereElemento( Lista *lst, void *dat ){

    No *no = (No *) calloc( sizeof(No), 1 );

    no->anterior = lst->ultimo;
    no->dados = dat;
    no->proximo = NULL;

    lst->ultimo = no;

    if ( lst->tamanho == 0 ){
        lst->primeiro = no;
    } else {
        //No *tmp = no->anterior;
        //tmp->proximo = no;
        ((No *) no->anterior)->proximo = no;
    }

    lst->tamanho++;

}


void destroiLista( Lista *tmp ){

    tmp->corrente = tmp->primeiro;

    while ( tmp->tamanho > 0 ){

        No *proximo = tmp->corrente->proximo;
        free( tmp->corrente->dados );
        free( tmp->corrente );
        tmp->corrente = proximo;
        tmp->tamanho --;
    }

    free( tmp );

}


// outras funções do programa

void pausa(){
    printf( "\ntecle ENTER" );
    fflush( stdin );
    getchar();
    system( "cls" );
}


int main()
{
    Lista *pacientes = criaLista();

    insereElemento( pacientes, criaPaciente( 1200, "Antonio", 89, "123.456.123-1" ) );
    insereElemento( pacientes, criaPaciente( 1300, "Maria", 81, "987.654.432-2" ) );
    insereElemento( pacientes, criaPaciente( 1400, "Joao", 84, "765.234.546-3" ) );
    insereElemento( pacientes, criaPaciente( 1500, "Francisco", 78, "453.765.897-5" ) );

    printf( "\nListagem Normal:\n" );

    pacientes->corrente = pacientes->primeiro;
    while ( pacientes->corrente != NULL ){
        mostraPaciente((Paciente *) pacientes->corrente->dados);
        pacientes->corrente = pacientes->corrente->proximo;
    }

    pausa();

    printf( "\nListagem Invertida:\n" );

    pacientes->corrente = pacientes->ultimo;
    while ( pacientes->corrente != NULL ){
        mostraPaciente((Paciente *) pacientes->corrente->dados);
        pacientes->corrente = pacientes->corrente->anterior;
    }
    pausa();

    destroiLista( pacientes );
    pacientes = NULL;


    // outro exemplo

    Lista *semana = criaLista();

    insereElemento( semana, "Segunda-Feira" );
    insereElemento( semana, "Terca-Feira" );
    insereElemento( semana, "Quarta-Feira" );
    insereElemento( semana, "Quinta-Feira" );
    insereElemento( semana, "Sexta-Feira" );
    insereElemento( semana, "Sabado-Feira" );
    insereElemento( semana, "Domingo" );

    printf( "\nDias da Semana:\n" );

    semana->corrente = semana->primeiro;
    while ( semana->corrente != NULL ){
        printf("\n%-s\n", (char *) semana->corrente->dados);
        semana->corrente = semana->corrente->proximo;
    }
    pausa();

    destroiLista( semana );
    semana = NULL;


    // mais um outro exemplo

    Lista *salarios = criaLista();

    insereElemento( salarios, criaSalario( 1200.00, "Estagiario" ) );
    insereElemento( salarios, criaSalario( 1600.00, "Motorista" ) );
    insereElemento( salarios, criaSalario( 1900.00, "Secretaria" ) );
    insereElemento( salarios, criaSalario( 2300.00, "Vendedor" ) );
    insereElemento( salarios, criaSalario( 3400.00, "Programador" ) );
    insereElemento( salarios, criaSalario( 4500.00, "Analista" ) );
    insereElemento( salarios, criaSalario( 6720.00, "Gerente" ) );

    printf( "\nTabela de Salarios:\n" );

    salarios->corrente = salarios->primeiro;
    while ( salarios->corrente != NULL ){
        Salario *tmp = (Salario *) salarios->corrente->dados;
        printf("\n%-15s - %12.2f\n", tmp->cargo, tmp->salario );
        salarios->corrente = salarios->corrente->proximo;
    }
    pausa();

    destroiLista( salarios );
    salarios = NULL;

    return 0;

}

---

Bom estudo e até a próxima.

Usando typedef, struct, malloc e free

A seguir temos alguns exemplos de fácil compreensão.

---

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct{
    int id;
    char name[30];
} elemento;

typedef struct node{
    struct node *next;      // forma correta
    // node *previous;      // declaração errada
    elemento *dados;
} node;

typedef struct tag{
    int key;
    int value;
} tag;

int main()
{
    elemento *prod = (elemento *) malloc( sizeof( elemento ));

    prod->id = 123;
    strcpy( prod->name, "teste");

    node *n = (node *) malloc( sizeof(node));

    n->next = NULL;
    n->dados = prod;

    free( n->dados );
    free( n );

    tag *a = (tag *) malloc( sizeof( tag ));

    a->key = 12;
    a->value = 14;

    free( a );

    struct tag *b = (struct tag *) malloc( sizeof( struct tag ));

    b->key = 120;
    b->value = 140;

    free( b );

    struct point3d {
        int x;
        int y;
        int z;
    };

    struct point3d *ptr = (struct point3d *) malloc( sizeof( struct point3d ));

    ptr->x = 10;
    ptr->y = 20;
    ptr->z = 30;

    free( ptr );

    typedef struct point{
        int x;
        int y;
    } point;

    point *q = (point *) malloc( sizeof( point ));

    q->x = 39;
    q->y = 67;

    free( q );

    return 0;
}

---

Link relacionado ao assunto:

RE: typedef struct vs struct
http://www.netalive.org/codersguild/posts/1753.shtml

The Most Expensive One-byte Mistake - ACM Queue

Para quem ainda não entendeu o uso do terminador NUL nas strings em C ( "demo\0' ):


The Most Expensive One-byte Mistake - ACM Queue


e outras escolhas.


Saudações.


Josimar

Uma mensagem de encerramento de mais um ano

Rodem o código e vejam a mensagem.

#include <stdio.h> void PrintBitMap( unsigned long long int bitmap ){     if ( bitmap > 1ULL ) PrintBitMap( bitmap / 2ULL );     printf("%c", ( bitmap % 2ULL ) ? '*' : ' '); } unsigned long long int bitmap[13] = {       0x1000000000000000LL, 0x10000000114447CELL,     0x100000001B444111LL, 0x1000000015444111LL,     0x1000000011444111LL, 0x100000001138410ELL,     0x1000000000000000LL, 0x100039E78438E78ELL,     0x1000451444411451LL, 0x100045E7847DF451LL,     0x1000451504451451LL, 0x100039E48439178ELL,     0x1000000000000000LL  }; void main(){     for (int i=0; i<13; i++) {         PrintBitMap( bitmap[i] );         printf("\n");     }     fflush(stdin);     getchar(); }

Até a próxima.

Matrizes e Vetores Equivalentes

O código a seguir apresenta a técnica de alocação dinâmica de vetor (matriz linha ou matriz coluna) na linguagem de programação C. Foi usado o Borland C-Builder 6.

O usuário poderá definir o tamanho de uma matriz bi-dimensional e em seguida fornecer os valores para cada elemento, que neste estudo de caso é do tipo inteiro.

A função "sizeof(int)" retorna o tamanho em bytes para cada elemento da matriz[m][n].

Com a função "malloc( m * n * sizeof( int ) )" são alocados bytes na memória RAM suficientes para armazenar a quantidade de elementos ( int ) que compõem a matriz[m][n]. Esta função retorna um ponteiro do tipo (void*) sendo necessária a conversão para ponteiro do tipo (int*).

Para a entrada de dados, o algoritmo percorre de maneira bi-dimensional a matriz[m][n], sendo necessária a conversão dos índices m e n para a posição efetiva no vetor:

posição no vetor = t * n + u

onde:

t : linha corrente na matriz[m][n]

u: coluna corrente na matriz[m][n]

n : quantidade de colunas por lina na matriz[m][n]

Na segunda parte do código, o algoritmo percorre linearmente o vetor de dados que armazena a matriz[m][n] desejada, e para informação é calculada de maneira inversa os índices correntemente sendo impressos:

v = t / n (divisão inteira)

w = t % n (resto de divisão inteira)

onde:

t : posição corrente no vetor

n : quantidade de colunas por linha na matriz[m][n]

v : linha corrente da matriz[m][n]

w : coluna corrente da matriz[m][n]

Antes de analisar o código, acompanhe o diagrama de blocos a seguir:

Agora temos o código na linguagem C:

//--------------------------------------------------------------------- #pragma hdrstop //--------------------------------------------------------------------- /*     Alocação dinâmica de memória     Estudo de caso: matrizes e vetores equivalentes     malloc, free, fflush, printf, scanf */ #include <stdio.h> #include <stdlib.h> #pragma argsused int main(int argc, char* argv[]) {     int *A;     int m, n, c, t, u, valor;     printf("Matriz A[m][n]:\n");     fflush(stdin);     printf("Digite valor de m:");     scanf("%d",&m);     printf("Digite valor de n:");     scanf("%d",&n);     // Alocar recurso de memória RAM ----------     c = m * n;     A = (int*) malloc( c * sizeof( int ) );     // ----------------------------------------     if ( A == NULL )     {         printf("\n\nErro ao alocar memoria RAM!!!\n");         printf("\n\nTecle ENTER para encerrar");         fflush(stdin);         getchar();         return 1;     }     printf("\nDigite os elementos da matriz A[%d][%d]\n", m, n);     for ( t=0; t<m; t++ )     {         for ( u=0; u<n; u++ )         {             printf("Digite elemento[%d][%d]:", t, u);             scanf("%d", &valor);             A[ t * n + u ] = valor;         }     }     printf("\n\nMatriz A[%d][%d]:\n", m, n);     for ( t=0; t<c; t++ )     {         printf("\nA[%d][%d]=%d", (t / n), (t % n), A[t]);     }     printf("\n\nTecle ENTER para encerrar");     fflush(stdin);     getchar();     // Liberar recurso de memória RAM -----     free(A);     // ------------------------------------     return 0; } //---------------------------------------------------------------------

 

Links sugeridos para outros esclarecimentos:

http://www.ime.usp.br/~pf/algoritmos/aulas/aloca.html

http://en.wikipedia.org/wiki/Malloc

http://cplus.about.com/od/learningc/ss/pointers_7.htm

http://informatica.hsw.uol.com.br/programacao-em-c29.htm

 

Cópias de tela da execução do código aqui apresentado:

Para estudo, desenvolver uma aplicação para multiplicar duas matrizes bi-dimensionais:

C[m][j] = A[m][n] . B[i][j]

restrições:

• n igual a i
• m, n, i, j maiores que zero

Links com fundamentos matemáticos para multiplicação de matrizes:

• http://www.eng.uerj.br/~marcelo/matriz.html
• http://pt.wikipedia.org/wiki/Matriz_(matem%C3%A1tica)
• http://pessoal.sercomtel.com.br/matematica/medio/matrizes/matrizes.htm
• http://msdn.microsoft.com/pt-br/library/8667dchf.aspx

 

Bom estudo e até a próxima.