Programação Avançada em C Usando Algoritmos …w3.ualg.pt/~jvo/pacuaedf.pdfProgramação Avançada em C Usando Algoritmos e Estruturas de Dados Fundamentais The Ualg Informatics

Programação Avançada em C

Usando Algoritmos e Estruturas de Dados

Fundamentais

The Ualg Informatics Lab Universidade do Algarve

http://w3.ualg.pt/~jvo

[email protected]

! " # $ % & ' ( ' )' * + , - ( . /

0 $ 1 " 1 # , 2 , 3 4 & " $ 1 5 3 6 7 " - 7 6 , 8 & $ & 2 9 : , ; 6 7 " - < , = # " , 1 6 > " = & : : & - $ ? 1 # 6 2 9 6 < % & @ A $ & B % & @= & : " # 7 6 , 3 @ ! " 8 , 8 , , = # 6 , < % & 8 " C 2 # , $ D " # 6 > , 8 , $ E ( F G & # 1 9 H , 3 ( G , # , > " # 9 : , 7 I J 6 ,8 " $ 1 , 3 6 7 " - < , K > 6 $ 6 1 " 4 1 1 J LM M 7 # " , 1 6 > " 7 & : : & - $ ( & # H M 3 6 7 " - $ " $ M 2 N @ - 7 @ - 8 M E ( F M J 1 M & 9 " - > 6 " 9 : ,7 , # 1 , J , # , = # " , 1 6 > " = & : : & - $ K ' O ' P " 7 & - 8 P 1 # " " 1 K P 9 6 1 " Q . . K P , - R # , - 7 6 $ 7 & K = , 3 6 S & # - 6 ,T U ' . F K A P ? (

Índice

0. Preâmbulo

1. Introdução

! "

#

$ %

&

# ' (

2. Arrays e Ponteiros

) %

*

&

+

,

! % -

!

# ' (

3. Reserva dinâmica de memória

"

# ' (

4. Primeiras noções de complexidade

'

# ' (

' )

'

*

*

) &

# ' (

5. Algoritmos elementares de ordenação &

! &

) &

) * &

) & &

# ' (

6. Mergesort +

+

+

+

# ' (

7. Quicksort ,

,

,

,

,

% ,

, &

! * , +

! , ,

# ' (

8. Introdução às listas ligadas -

-

-

% -

# ' (

9. Primeiras noções de Projecto e de Projecto por

Contrato

# ' IR

!

( &

+

# ' (

10. As listas ligadas revisitadas

!

! %

) &

+

,

# ' (

11. Tipos de dados abstractos

12. O tipo de dados abstracto pilha

$ !

$ ! !

' %

%

$

$

&

' % ! ' ! '

+ # ' (

13. O tipo de dados abstracto fila de espera

$ ! !

!

$

$

# ' (

14. As filas revisitadas

!

!

%

# ' (

15. Implementação em C de ADTs com múltiplas

instâncias &

$ &

$ ! &

! ! % &

# ' (

16. O tipo de dados abstracto polinómio +

! +

+

+

# ' (

17. O ADT matriz esparsa ,

,

! % ! ,

,

,

, *

, & # ' (

18. Primeiras noções sobre árvores -

-

-

-

# ' (

19. Árvores binárias

%

! %

# ' (

20. Acervos e filas com prioridades

!

!

&

# ' (

Referências bibliográficas

Referência rápida sobre C

R1. Preliminares

R2. Algumas características do C

R3. Exemplo de programa

R4. Elementos de sintaxe

!

% !

& !

+ !

,

,

,

,

- )

- )

- )

- )

- )

- & )

- +

- , ) (

- -

R5. Controlo de fluxo do programa

& % !

& %

& %

& %

& & % !

& + % '

R6. Funções

+

+ ! %

+ *

R7. Arrays e Matrizes

, *

, "

R8. Ponteiros

-

-

-

-

- & ! %

R9. Sinónimos de tipo

R10. Estruturas

R11. Uniões

R12. Campos de bits

R13. Enumerações

R14. Directivas de Pré-processador

R15. Biblioteca de funções

&

&

& ! % ( !

& ! % !

Índice Remissivo

0. Preâmbulo ? $ " $ 1 # 9 1 9 # , $ 8 " 8 , 8 & $ S , " : J , # 1 " 8 & 7 & - 9 - 1 & 8 " 7 & : J " 1 - 7 6 , $ 7 " - 1 # , 6 $ 9 " 9 :" $ 1 9 8 6 & $ & 8 " - S & # : 5 1 6 7 , 8 " > " # 5 , 8 9 6 # 6 # (

B , H , 3 " # 6 , 8 , $ 3 6 - H 9 , H " - $ 8 " J # & H # , : , < % & K , 3 6 - H 9 , H " : = & 7 9 J , 9 : 3 9 H , # 8 " 8 " $ 1 , 9 " ( $ " H 9 # , : " - 1 " 9 : , 8 , $ 3 6 - H 9 , H " - $ 9 $ , 8 , $ , 7 1 9 , 3 : " - 1 " 7 & : : , 6 $ 1 " : J & 8 " J # & > , $8 , 8 , $ ( ? 3 6 - H 9 , H " : = 9 : , 3 6 - H 9 , H " : J " 9 " - , K 8 " " $ 7 # 6 1 , 7 & - 8 " - $ , 8 , K " 1 # " : , : " - 1 "" S 6 7 6 " - 1 " K 9 " J " # : 6 1 " 9 : " 3 " > , 8 & - > " 3 8 " 6 - 1 6 : 6 8 , 8 " 7 & : & 7 & : J 9 1 , 8 & # ( B % & " 6 $ 1 "& 9 1 # , 3 6 - H 9 , H " : 8 " , 3 1 & - > " 3 , 7 1 9 , 3 9 " J " # : 6 1 , : , 6 & # - > " 3 8 " J # & 6 : 6 8 , 8 " 7 & : ,: 5 9 6 - , K " $ J " 7 6 , 3 : " - 1 " - & 9 " $ " # " S " # " $ $ 9 , $ 7 , J , 7 6 8 , 8 " $ 8 " , # 6 1 : 1 6 7 , 7 & :J & - 1 " 6 # & $ ( ? 9 - 1 , # , 6 $ 1 & K , 3 6 - H 9 , H " : = 1 " : : " 7 , - 6 $ : & $ 8 " , 2 $ 1 # , 7 < % & $ 9 S 6 7 6 " - 1 " $J , # , J " # : 6 1 6 # 9 : , 6 : J 3 " : " - 1 , < % & , 8 " 9 , 8 , 8 " " $ 1 # 9 1 9 # , $ 8 " 8 , 8 & $ K , 3 H & # 6 1 : & $ KJ # & H # , : , $ " : " $ : & $ 6 $ 1 " : , $ (

? & 7 , $ , # : & $ " $ 1 # 9 1 9 # , $ 8 " 8 , 8 & $ 7 & : = - % & " $ 1 , # " : & $ , $ " # : 9 6 1 & & # 6 H 6 - , 6 $ ( 0 $ 1 ," $ 7 & 3 4 , $ " H 9 6 8 , - , $ 8 6 $ 7 6 J 3 6 - , $ 8 " ? 3 H & # 6 1 : & $ " 0 $ 1 # 9 1 9 # , $ 8 " D , 8 & $ " : : 9 6 1 & 7 9 # $ & $8 " - S & # : 5 1 6 7 , J & # " $ 1 " : 9 - 8 & S & # , K 6 - 7 3 9 6 - 8 & , 3 H 9 - $ 8 & $ - & $ $ & $ J # I J # 6 & $ 7 9 # $ & $ 8 "0 - H " - 4 , # 6 , (

0 $ $ " - 7 6 , 3 : " - 1 " , & # 6 H 6 - , 3 6 8 , 8 " 8 & 3 6 > # & " $ 1 5 # " 3 , 7 6 & - , 8 , 7 & : , , 2 & # 8 , H " : J # , H : 5 1 6 7 ,$ " H 9 6 8 , - , , J # " $ " - 1 , < % & 8 , $ : , 1 # 6 , $ ( ? - & $ $ , " J " # 6 - 7 6 , " : $ , 3 , 8 " , 9 3 , K : & $ 1 # , @ - & $ 9 " & , $ $ 9 - 1 & K - % & $ " - 8 & 8 6 S 7 6 3 K : 9 6 1 , $ > " " $ 6 - 1 6 : 6 8 , 1 6 > & J , # , & # " 7 : @ 7 4 " H , 8 & (

? & 3 & - H & 8 & 3 6 > # & 9 1 6 3 6 , : & $ 9 : , 3 6 - H 9 , H " : 7 3 , # , K 8 " 3 " 6 1 9 # , S 5 7 6 3 K $ " : & S # " 9 " - 1 " "8 " $ - " 7 " $ $ 5 # 6 & 1 7 - 6 7 & @ 7 6 " - 1 S 6 7 & , $ $ & 7 6 , 8 & , " $ 1 , $ : , 1 # 6 , $ ( ? J " $ , # 8 " $ 1 " " $ 1 6 3 &- % & $ " J # " $ 7 6 - 8 " 8 & # 6 H & # 9 " 3 " > , & 8 " $ " - > & 3 > 6 : " - 1 & 8 " J # & H # , : , $ 8 " K8 " $ 6 H - , 8 , : " - 1 " - & 9 " $ " # " S " # " $ 9 , 7 & # # " 7 < % & ( G , # , J # & $ $ " H 9 6 # " $ 1 " & 2 " 7 1 6 > & K 7 " 8 &, J # " $ " - 1 , : & $ - & < " $ 8 " J # & " 7 1 & " 8 " J # & " 7 1 & J & # 7 & - 1 # , 1 & 9 " - & $ , 9 8 , : - &8 " $ " - > & 3 > 6 : " - 1 & $ 6 $ 1 " : 5 1 6 7 & 8 & $ J # & H # , : , $ $ 9 2 $ " 9 " - 1 " $ (

B % & J # " 1 " - 8 " : & $ $ " # " , 9 $ 1 6 > & $ - , , J # " $ " - 1 , < % & 8 , $ " $ 1 # 9 1 9 # , $ 8 " 8 , 8 & $ ( = & - 7 " - 1 # , : & @- & $ - , $ " $ 1 # 9 1 9 # , $ 8 " 8 , 8 & $ S 9 - 8 , : " - 1 , 6 $ K J , # , 8 6 $ 7 9 1 6 # : & $ " 6 3 9 $ 1 # , # : & $ , $ > 5 # 6 , $, 3 1 " # - , 1 6 > , $ $ 9 , 6 : J 3 " : " - 1 , < % & " : = ( C > & 3 9 : " , 9 1 & @ 7 & - 1 6 8 & K 6 - 7 3 9 6 - 8 &6 - 7 3 9 $ 6 > , : " - 1 " - & S 6 - , 3 9 : , # " S " # - 7 6 , # 5 J 6 8 , K : , $ 7 & : J 3 " 1 , K $ & 2 # " = (

& 8 & $ & $ 7 & - 7 " 6 1 & $ $ % & 8 " > 6 8 , : " - 1 " 6 3 9 $ 1 # , 8 & $ ( A 1 6 3 6 , : & $ " " : J 3 & $ 6 - 1 " - $ 6 > , "" 1 " - $ 6 > , : " - 1 " ( R , " : & @ 3 & , & - > " 3 8 , 6 - 1 # & 8 9 < % & 8 " 9 : 7 & - 7 " 6 1 & : , $ 1 , : 2 : 8 " J & 6 $, & - > " 3 8 , 6 : J 3 " : " - 1 , < % & " : = ( R , " : & @ 3 & , 6 - 8 , 8 " 9 : , S & # : , $ 6 $ 1 " : 5 1 6 7 , 8 " $ 8 " ,6 - 1 # & 8 9 < % & 8 & $ " 3 " : " - 1 & $ S 9 - 8 , : " - 1 , 6 $ 8 , J # & H # , : , < % & K 7 & : & , - & < % & 8 " 1 6 J & $ & 9 8 "1 6 J & $ 8 " 8 , 8 & $ , 2 $ 1 # , 7 1 & $ K , 1 , & $ 1 I J 6 7 & $ : , 6 $ , > , - < , 8 & $ K 7 & : & & 8 , $ : , 1 # 6 " $" $ J , # $ , $ ( ? , 2 & # 8 , H " : K J & # 1 , - 1 & K " : 6 - " - 1 " : " - 1 " J # 5 1 6 7 , ( G , # , 9 " & 3 " 6 1 & # J & $ $ , 6 #S , " - 8 & , $ 9 , J # I J # 6 , , 9 1 & @ , > , 3 6 , < % & K 7 , 8 , 7 , J 1 9 3 & 1 " # : 6 - , 7 & : 9 : 7 & - 9 - 1 & 8 "" " # 7 7 6 & $ K 1 " - 1 , 1 6 > , : " - 1 " & # 8 " - , 8 & $ J & # & # 8 " : 7 # " $ 7 " - 1 " 8 " 8 6 S 6 7 9 3 8 , 8 " (

8 " - 1 6 S 6 7 , # " # " J # & 8 9 6 # 2 & , $ J # 5 1 6 7 , $ 8 " J # & H # , : , < % & 1 " : > 6 - 8 & , $ " # # " 7 & - 4 " 7 6 8 &7 & : & 8 , $ , 7 1 6 > 6 8 , 8 " $ : , 6 $ " S 6 7 , " $ - & J # & 7 " $ $ & 8 " " - $ 6 - & M , J # " - 8 6 , H " : 8 ,J # & H # , : , < % & ( D " S , 7 1 & K J # & H # , : , # 8 , & # 8 " : 8 " 7 & : 9 - 6 7 , # ( = & : 9 - 6 7 , # 7 & : ,: 5 9 6 - , K : , $ S 9 - 8 , : " - 1 , 3 : " - 1 " 7 & : 9 - 6 7 , # " - 1 # " J # & H # , : , 8 & # " $ ( P , 2 " # 3 " # 7 I 8 6 H & "6 8 " - 1 6 S 6 7 , # 7 I 8 6 H & 8 " 9 " J & $ $ , $ " # # " @ 9 1 6 3 6 , 8 & 9 , - 8 & - " 7 " $ $ 5 # 6 & K 1 & # - , @ $ ", $ $ 6 : 1 % & 6 : J & # 1 , - 1 " 7 & : & $ , 2 " # " $ 7 # " > " # 7 I 8 6 H & (

? & $ " H 9 6 # : & $ 9 : , , 2 & # 8 , H " : J # , H : 5 1 6 7 , 9 $ , - 8 & 6 - 1 " - $ 6 > , " " 1 " - $ 6 > , : " - 1 " " " : J 3 & $8 " 2 & , $ J # 5 1 6 7 , $ 8 " J # & H # , : , < % & " : = " $ J " # , : & $ " $ 1 , # 7 & - 1 # 6 2 9 6 # J , # , & $ 9 7 " $ $ & 8 " $ 1 "J # & 7 " $ $ & 8 " " - $ 6 - & M , J # " - 8 6 , H " : (

? J # & H # , : , < % & " " $ 1 # 9 1 9 # , 8 " 8 , 8 & $ " : = 9 : 1 " : , # " 3 , 1 6 > , : " - 1 " : , 8 9 # & 7 & :, J 3 6 7 , < " $ " : > , # 6 , 8 $ $ 6 : , $ 5 # " , $ 8 , " - H " - 4 , # 6 , 6 - S & # : 5 1 6 7 , K 8 , 6 - S & # : 5 1 6 7 , 8 " H " $ 1 % &" 8 & $ 7 & : J 9 1 , 8 & # " $ " : H " # , 3 ( 0 - 7 & - 1 # , : & $ , J 3 6 7 , < " $ 8 , $ " $ 1 # 9 1 9 # , $ 8 " 8 , 8 & $ " : 5 # " , $ 9 " > % & 8 " $ 8 " & $ $ 6 $ 1 " : , $ & J " # , 1 6 > & $ K , & $ 7 & : J 6 3 , 8 & # " $ K " 6 - 1 " 3 6 H - 7 6 , , # 1 6 S 6 7 6 , 3 ( D " $ 1 "

J & - 1 & 8 " > 6 $ 1 , K " 8 , 8 & & 7 & - 1 " 8 & " , , 2 & # 8 , H " : J # , H : 5 1 6 7 , $ " H 9 6 8 , K & 3 6 > # &

6 - 1 " # " $ $ , - 1 " J , # , 9 : , , : J 3 , , 9 8 6 - 7 6 , L " - H " - 4 " 6 # & $ K 6 - S & # : 5 1 6 7 & $ K " $ 1 9 8 , - 1 " $ "8 & 7 " - 1 " $ 9 - 6 > " # $ 6 1 5 # 6 & $ K : , $ 1 , : 2 : , & 9 1 # & $ J # & S 6 $ $ 6 & - , 6 $ 9 " 9 " # " : , 7 1 9 , 3 6 , # & $$ " 9 $ 7 & - 4 " 7 6 : " - 1 & $ - & : 2 6 1 & 8 " 9 : J # & H # , : , 8 " , J # " - 8 6 , H " : , & 3 & - H & 8 , > 6 8 , K " , &, 9 1 & @ 8 6 8 , 7 1 , 9 " 9 " # , J # " - 8 " # , 8 " $ " - > & 3 > " # & $ $ " 9 $ J # & H # , : , $ 8 " 9 : , S & # : , $ 6 : J 3 " $: , $ $ 6 $ 1 " : 5 1 6 7 , ( ? & # H , - 6 , < % & 8 & 7 & - 1 " 8 & 1 & # - , & 3 6 > # & , 7 " $ $ > " 3 , & - & > 6 < & " :J # & H # , : , < % & : , $ 1 , : 2 : , & 3 " 6 1 & # " - > & 3 > 6 8 & 4 5 : 9 6 1 & - & 8 " $ " - > & 3 > 6 : " - 1 & 8 "J # & H # , : , $ (

C 1 " 1 & 8 & 3 6 > # & " $ 7 # 6 1 & " : 6 : " $ B " & : , - ( C 7 I 8 6 H & = " $ 7 # 6 1 & " :

Arial NarrowK

7 & : & " :

#include <stdio.h>

/* Primeiro programa. */

int main()

printf(“Olá mundo!”);

return 0;

C $ 7 & : " - 1 5 # 6 & $ , & 7 I 8 6 H & $ % & " $ 7 # 6 1 & " : G & # 1 9 H 9 $ ( G & # 9 : , 9 " $ 1 % & 8 " 9 - 6 S & # : 6 8 , 8 " K1 & 8 & $ & $ 6 8 " - 1 6 S 6 7 , 8 & # " $ - & : " $ 8 " > , # 6 5 > " 6 $ K S 9 - < " $ K " 1 7 ( $ % & " $ 7 # 6 1 & $ " : - H 3 $ (

G , # , , 3 : 8 & $ " 3 " : " - 1 & $ H # 5 S 6 7 & $ 8 " : & 8 " 3 , < % & 7 & : & & $ 8 6 , H # , : , $ 8 " " $ 1 # 9 1 9 # , & 9S 3 9 & H # , : , $ K 9 1 6 3 6 , @ $ " , 7 , 6 , 8 " 1 " 1 & 7 & : 3 6 : 6 1 " $ , J # " 1 & J , # , 6 8 " - 1 6 S 6 7 , # & $" 3 " : " - 1 & $ 8 " $ 6 - 1 , " 8 , 3 6 - H 9 , H " : (

? & $ : " 9 $ , 3 9 - & $ J " 3 & $ " 9 " $ 1 : 9 3 & J " # : , - " - 1 " (

? & $ 7 & 3 " H , $ 8 & D " J , # 1 , : " - 1 & 8 " 0 - H " - 4 , # 6 , 0 3 " 7 1 # I - 6 7 , " - S & # : 5 1 6 7 , 8 , R , 7 9 3 8 , 8 " 8 "= 6 - 7 6 , $ " " 7 - & 3 & H 6 , 8 , A - 6 > " # $ 6 8 , 8 " 8 & ? 3 H , # > " 9 " 7 & : 6 H & 1 : 3 " 7 7 6 & - , 8 &8 6 $ 7 6 J 3 6 - , $ K & - 8 " , $ : , 1 # 6 , $ , H & # , , J # " $ " - 1 , 8 , $ 1 : > 6 - 8 & , $ " # 3 " 7 7 6 & - , 8 , $ ( 0 :J , # 1 6 7 9 3 , # H & $ 1 , # 6 , 8 " , H # , 8 " 7 " # G , 9 3 , ! " - 1 9 # , J " 3 & $ " 9 , J & 6 & - , " 3 , 2 & # , < % & 8 ,J # 6 : " 6 # , > " # $ % & " 3 " 7 1 # I - 6 7 , 8 & $ , J & - 1 , : " - 1 & $ 8 , 8 6 $ 7 6 J 3 6 - , G # & H # , : , < % & (

" 7 & - 4 " < & 6 H 9 , 3 : " - 1 " & $ : " 6 & $ " & , : 2 6 " - 1 " J # & J 7 6 & # " S 3 " , < % & J # & J & # 7 6 & - , 8 & $J " 3 , A - 6 > " # $ 6 8 , 8 " 8 & ? 3 H , # > " " J " 3 & 9 , 3 H @ 6 3 , 2 L 4 " A , 3 H - S & # : , 1 6 7 $ ; , 2 (

1. Introdução

A : , 3 H & # 6 1 : & 7 & # # " $ J & - 8 " , 9 : , S & # : , 8 " # " $ & 3 > " # 9 : J # & 2 3 " : , ( , 6 $ 7 & - 7 # " 1 , : " - 1 " K9 : , 3 H & # 6 1 : & 9 : 7 & - 9 - 1 & S 6 - 6 1 & $ 8 " 6 - $ 1 # 9 < " $ J # " 7 6 $ , $ " & # 8 " - , 8 , $ 9 " # " $ & 3 > " 9 :8 " 1 " # : 6 - , 8 & J # & 2 3 " : , ( A : , 3 H & # 6 1 : & 8 " > " $ , 1 6 $ S , " # 9 : 7 & - 9 - 1 & 8 " J # & J # 6 " 8 , 8 " $7 & : & L

' (

D " > " 1 " # : 6 - , # - 9 : 7 & - 9 - 1 & S 6 - 6 1 & 8 " J , $ $ & $ S 6 - 6 1 9 8 "

E (

= , 8 , J , $ $ & 1 " : 9 " $ " # J # " 7 6 $ , : " - 1 " 8 " S 6 - 6 8 & 8 " S 6 - 6 1 9 8 "

Q (

= , 8 , J , $ $ & 8 " > " $ " # $ 9 S 6 7 6 " - 1 " : " - 1 " $ 6 : J 3 " $ " S 6 7 5 7 6 ,

U (

D " > " # " $ & 3 > " # & J # & 2 3 " : , " : 1 " : J & 1 6 3 J , # , 9 " , $ & 3 9 < % & J # & 8 9 6 8 , 1 " - 4 ,6 - 1 " # " $ $ " " S 6 7 6 - 7 6 ,

F (

" : . & 9 : , 6 $ " - 1 # , 8 , $ "/ (

" : ' & 9 : , 6 $ $ , 8 , $ (

B , # " $ & 3 9 < % & 8 " J # & 2 3 " : , $ 9 $ , : & $ , 3 H & # 6 1 : & $ 7 9 & 8 " $ " : J " - 4 & J & 8 " 8 " J " - 8 " # ": 9 6 1 & 8 , $ " $ 1 # 9 1 9 # , $ 8 " 8 , 8 & $ 9 " 9 1 6 3 6 , : ( 8 & - & $ $ & 6 - 1 " # " $ $ " 8 " $ " - > & 3 > " #, 3 H & # 6 1 : & $ " S 6 7 6 " - 1 " $ ( 9 6 1 , $ > " " $ K , - 6 7 , 4 6 J I 1 " $ " 9 " 1 " # " : & $ 8 " " - 7 & - 1 # , # 9 : ,$ & 3 9 < % & J , # , 9 : 7 " # 1 & J # & 2 3 " : , " $ 1 5 - , 9 1 6 3 6 , < % & 8 " , 3 H & # 6 1 : & $ " S 6 7 6 " - 1 " $ (

A : , " $ 1 # 9 1 9 # , 8 " 8 , 8 & $ - % & : , 6 $ 8 & 9 " 9 : , S & # : , 8 " & # H , - 6 , # > , 3 & # " $ # " 3 , 7 6 & - , 8 & $" " : 7 9 & $ " " : J 3 & $ $ " 6 - 7 3 9 " : , $ : , 1 # 6 " $ K , $ 3 6 $ 1 , $ K , $ 5 # > & # " $ " & $ H # , S & $ (

B & " $ 1 9 8 & 8 , $ " $ 1 # 9 1 9 # , $ 8 " 8 , 8 & $ , - & < % & 8 " 1 6 J & $ 8 " 8 , 8 & $ 9 : , - & < % & 7 " - 1 # , 3 (

? : , 6 & # J , # 1 " 8 , $ 3 6 - H 9 , H " - $ 8 " J # & H # , : , < % & J # & J & # 7 6 & - , : J " 3 & : " - & $ 9 : 7 & - 9 - 1 &: - 6 : & 8 " 1 6 J & $ 8 " 8 , 8 & $ J # 6 : 6 1 6 > & $ & 9 J # @ 8 " S 6 - 6 8 & $ K , $ $ 6 : 7 & : & , 7 , J , 7 6 8 , 8 " 8 "7 & - $ 1 # 9 6 # - & > & $ 1 6 J & $ K & 9 1 6 J & $ 8 " S 6 - 6 8 & $ J " 3 & 9 1 6 3 6 , 8 & # ( , $ , S 6 - , 3 & 9 " 9 : 1 6 J & 8 "8 , 8 & $

A : 1 6 J & 8 " 8 , 8 & $ 9 : 7 & - 9 - 1 & 8 " > , 3 & # " $ " 9 : , 7 & 3 " 7 < % & 8 " & J " # , < " $ $ & 2 # " " $ $ " $> , 3 & # " $ ( 0 " : J 3 & L C 1 6 J & 8 " 8 , 8 & $

int7 & - $ 6 $ 1 " 8 & $ " H 9 6 - 1 " 7 & - 9 - 1 & 8 " > , 3 & # " $

. K ' K @ ' K E K @ E K ( ( ( KINT_MAX

KINT

B

& - 8 "INT MAX

"INT MIN

# " J # " $ " - 1 , : & $ > , 3 & # " $ : 5 6 : & $ " : - 6 : & $ 8 & $ 6 - 1 " 6 # & $ ( ? $& J " # , < " $ $ & 2 # " & $

int$ % & : 9 6 1 , $ " 6 - 7 3 9 " : & $ & J " # , 8 & # " $ , # 6 1 : 1 6 7 & $

+, -, *, /"

%K 1 " $ 1 "

8 " 6 H 9 , 3 8 , 8 " " 8 " $ 6 H 9 , 3 8 , 8 " K & J " # , < " $ 8 " , 1 # 6 2 9 6 < % & K " 1 7 (

G & # 9 " # , % & , - & < % & 8 " 1 6 J & 8 " 8 , 8 & $ 1 % & 6 : J & # 1 , - 1 " 0 $ $ " - 7 6 , 3 : " - 1 " J & # 1 # $& # 8 " - $ 8 " # , " $ (

' (

A : 1 6 J & 8 " 8 , 8 & $ J # & J & # 7 6 & - , 9 : , 6 - 1 " # J # " 1 , < % & J , # , & $ > , 3 & # " $ H 9 , # 8 , 8 & $ " :: " : I # 6 ,

E (

? 9 8 , : , & # H , - 6 , # " , 8 & 7 9 : " - 1 , # 7 & - 7 " 6 1 & $ Q (

G & $ $ 6 2 6 3 6 1 , : 9 " & 7 & : J 6 3 , 8 & # , 9 8 " & J # & H # , : , 8 & # - , > " # 6 S 6 7 , < % & 8 , 7 & # # " 7 < % &8 & $ " 9 7 I 8 6 H & (

0 $ 1 " $ , $ J " 7 1 & $ $ " # % & 6 3 9 $ 1 # , 8 & $ 8 " $ " H 9 6 8 , (

! , : & $ 7 & : " < , # J & # > " # & 9 " , 3 6 - H 9 , H " : ? B P = S # " 9 " - 1 " : " - 1 " # " S " # 6 8 , 8 , 9 6J , # , , S # " - 1 " $ 6 : J 3 " $ : " - 1 " J & # = @ - & $ & S " # " 7 " J , # , & # H , - 6 , # " J # & 7 " $ $ , # 6 - S & # : , < % & (0 : = K , $ , 2 $ 1 # , 7 < " $ 8 & : 9 - 8 & # " , 3 $ % & K " : 3 1 6 : , , - 5 3 6 $ " K # " J # " $ " - 1 , 8 & $ J " 3 & $ 1 6 J & $J # 6 : 6 1 6 > & $ 8 " 8 , 8 & $ L

charKint, float, double

(

0 : = K 9 $ , : & $ 9 : - : " # & S 6 & 8 " 2 6 1 $ J , # , # " J # " $ " - 1 , # - : " # & $ ( ? $ $ 6 : K & $int

$ % & J & #- " 7 " $ $ 6 8 , 8 " 6 - 1 " 6 # & $ 9 " > 6 > " : 8 " - 1 # & 8 " 3 6 : 6 1 " $ " $ J " 7 S 6 7 & $ 9 " 8 " J " - 8 " : 8 & - : " # &8 " 2 6 1 $ 9 " 9 $ , : & $ J , # , & $ # " J # " $ " - 1 , # (

G , # , S , 7 6 3 6 1 , # , , J # " $ " - 1 , < % & K > , : & $ 7 & - $ 6 8 " # , # 9 : 7 & : J 6 3 , 8 & # 8 " = & - 8 " & $ 6 - 1 " 6 # & $$ % & # " J # " $ " - 1 , 8 & $ 9 $ , - 8 & , J " - , $ Q 2 6 1 $ ( C $ > , 3 & # " $ J & $ $ > " 6 $ J , # , " $ $ " $ Q 2 6 1 $ $ % & L

. . . K . . ' K . ' . K . ' ' K ' . . K ' . ' K ' ' . " ' ' '

C $ 7 & : J 6 3 , 8 & # " $ 8 " = 9 $ , : & $ 6 $ 1 " : , 8 " - 9 : " # , < % & 2 6 - 5 # 6 & - , 1 9 # , 3 J , # , # " J # " $ " - 1 , #6 - 1 " 6 # & $ $ " : $ 6 - , 3 K J " 3 & 9 " L

. . . .. . ' '. ' . E. ' ' Q' . . U' . ' F' ' . /' ' ' O

G & # 1 , - 1 & K & - : " # & 8 " 6 - 1 " 6 # & $ 8 6 S " # " - 1 " $ 9 " J & 8 " # " : & $ # " J # " $ " - 1 , # 9 $ , - 8 & Q 2 6 1 $

8 , 8 & J & # E * ( 0 $ $ " $ 6 - 1 " 6 # & $ 7 & : " < , : " : . " > % & , 1 E @ ' O ( 0 $ 1 " $ $ % & & $ 3 6 : 6 1 " $ 8 "> , # 6 , < % & K & 9 , H , : , 8 " > , 3 & # " $ J & $ $ > " 6 $ K J , # , 6 - 1 " 6 # & $ $ " : $ 6 - , 3 8 " Q 2 6 1 $ (

P " " : > " 8 " Q 2 6 1 $ 1 6 > " $ $ " : & $ * K " - 1 % & J & 8 " # 6 , : & $ # " J # " $ " - 1 , # E E F / > , 3 & # " $8 6 S " # " - 1 " $ " , H , : , 8 " > , 3 & # " $ $ " # 6 , 8 " . , E @ ' E F F (

B & 7 , $ & H " # , 3 K J , # , 9 : 7 & : J 6 3 , 8 & # 8 "n

2 6 1 $ K ( K J , # , 9 : 7 & : J 6 3 , 8 & # 9 " # " J # " $ " - 1 "6 - 1 " 6 # & $ 9 $ , - 8 &

n2 6 1 $ K " 6 $ 1 6 # % & E

n6 - 1 " 6 # & $ 8 6 S " # " - 1 " $ K $ " - 8 & & $ 3 6 : 6 1 " $ 8 " > , # 6 , < % & . "

En@ ' (

C 9 " > 6 : & $ > 5 3 6 8 & J , # , 6 - 1 " 6 # & $ $ " : $ 6 - , 3 ( ? # " J # " $ " - 1 , < % & 8 " 6 - 1 " 6 # & $ 7 & : $ 6 - , 3

S " 6 1 , 9 $ , - 8 & , 9 6 3 & , 9 " $ " 7 4 , : , # " J # " $ " - 1 , < % & " : 7 & : J 3 " : " - 1 & J , # , E (

! & 3 1 " : & $ , & - & $ $ & 7 & : J 6 3 , 8 & # 8 " Q 2 6 1 $ ( C $ > , 3 & # " $ J & $ $ > " 6 $ J , # , " $ $ " $ 1 # $ 2 6 1 $7 & - 1 6 - 9 , : , $ " # & $ : " $ : & $ L . . . K . . ' K . ' . K . ' ' K ' . . K ' . ' K ' ' . " ' ' ' ( 0 : 7 & : J 3 " : " - 1 &J , # , E K & 2 6 1 : , 6 $ " $ 9 " # 8 , - & - : " # & & 9 & 2 6 1 : , 6 $ $ 6 H - 6 S 6 7 , 1 6 > & 9 $ , 8 & J , # ,6 - 8 6 7 , # & $ 6 - , 3 8 & - : " # & ( P " " $ $ " 2 6 1 S & # . " $ 1 , : & $ - , J # " $ " - < , 8 " 9 : - : " # & J & $ 6 1 6 > &

$ " " $ $ " 2 6 1 S & # ' 1 " # " : & $ 9 : - : " # & - " H , 1 6 > & (

B : " # & $ J & $ 6 1 6 > & $ 7 & : " < , : J & # . " & $ # " $ 1 , - 1 " $ 2 6 1 $ # " J # " $ " - 1 , : & > , 3 & # , 2 $ & 3 9 1 & 8 &- : " # & ( B : " # & $ - " H , 1 6 > & $ 7 & : " < , : J & # ' K $ " - 8 & & $ " 9 > , 3 & # , 2 $ & 3 9 1 & 8 , 8 & J " 3 ,8 6 S " # " - < , " - 1 # " , 9 , - 1 6 8 , 8 " 8 " - : " # & $ 9 " $ " 7 & - $ " H 9 " : # " J # " $ " - 1 , # 7 & : & - : " # &8 " 2 6 1 $ # " $ 1 , - 1 " $ " & > , 3 & # " : 2 6 - 5 # 6 & - , 1 9 # , 3 # " J # " $ " - 1 , 8 & J & # " $ $ " $ : " $ : & $ 2 6 1 $ (

. . . .. . ' '. ' . E. ' ' Q' . . @ U @ . U' . ' @ U @ ' Q' ' . @ U @ E E' ' ' @ U @ Q '

? $ $ 6 : K " : 2 & # , 9 : 6 - 1 " 6 # & 7 & : $ 6 - , 3 K # " J # " $ " - 1 , 8 & 9 $ , - 8 & Q 2 6 1 $ K 1 " - 4 , , 6 - 8 , E *> , 3 & # " $ J & $ $ > " 6 $ K & $ $ " 9 $ 3 6 : 6 1 " $ 8 " > , # 6 , < % & $ % & L @ E @ U " E @ ' Q (

P " 1 6 > " # : & $ * 2 6 1 $ " - 1 % & , H , : , 8 " > , # 6 , < % & > , 6 8 " E @ ' E * , E @ ' ' E O (

B & 7 , $ & H " # , 3 K 9 : 6 - 1 " 6 # & 7 & : $ 6 - , 3 # " J # " $ " - 1 , 8 & 9 $ , - 8 &n

2 6 1 $ 1 " # 5 En

> , 3 & # " $ 8 6 S " # " - 1 " $" 9 : , H , : , 8 " > , # 6 , < % & 9 " > , 6 8 " E , E @ ' (A : , : , - " 6 # , 8 " $ , 2 " # : & $ 9 , 6 $ $ % & & $ 3 6 : 6 1 " $ 8 " > , # 6 , < % & J , # , & $ 6 - 1 " 6 # & $ - &7 & : J 6 3 , 8 & # 8 " = 9 " " $ 1 , : & $ , 9 $ , # # " 7 & # # " # $ : , 7 # & $ 8 " S 6 - 6 8 , $ - & S 6 7 4 " 6 # & 8 "7 , 2 " < , 3 4 &

limits.h. G , # , & $ 6 - 1 " 6 # & $ K " $ $ " $ 3 6 : 6 1 " $ $ % & 8 , 8 & $ J & # L

INT MIN"

INT MAX(

0 : = - " H & 7 6 , : & $ " $ J , < & " J # " 7 6 $ % & " $ 7 & 3 4 " - 8 & " - 1 # "char, int, long int

" " - 1 # "float,

double ou long double (

! , 3 & # " $ 1 J 6 7 & $ J , # , , 3 H 9 - $ 1 6 J & $ " : 7 & : J 6 3 , 8 & # " $ 8 " ' / 2 6 1 $

#

7 4 , # * 2 6 1 $ . , E F F$ 4 & # 1 " 6 - 1 ' / 2 6 1 $ @ Q E O / * , Q E O / O9 - $ 6 H - " 8 $ 4 & # 1 " 9 - $ 6 H - " 8 6 - 1 ' / 2 6 1 $ . , / F F Q F3 & - H Q E 2 6 1 $ @ E ' U O U * Q / U * , E ' U O U * Q / U O9 - $ 6 H - " 8 3 & - H Q E 2 6 1 $ . , U E T U T / O E T FS 3 & , 1 Q E 2 6 1 $ J # " 7 6 $ % & O 8 H 6 1 & $

S & 9 2 3 " / U 2 6 1 $ J # " 7 6 $ % & ' F 8 H 6 1 & $

3 & - H 8 & 9 2 3 " * . 2 6 1 $ J # " 7 6 $ % & ' T 8 H 6 1 & $

! 6 : & $ J & # 1 , - 1 & 9 " # " J # " $ " - 1 , < " $ 6 H 9 , 6 $ $ 6 H - 6 S 6 7 , : K " : H " # , 3 K 7 & 6 $ , $ 8 6 S " # " - 1 " $ J , # ,1 6 J & $ 8 6 S " # " - 1 " $ ( ! " , : & $ , H & # , 7 & : & & $ 1 6 J & $ 8 " 8 , 8 & $ - & $ , 9 8 , : , & # H , - 6 , # " ,8 & 7 9 : " - 1 , # 7 & - 7 " 6 1 & $ (

A : J # & H # , : , & # H , - 6 , & $ 8 , 8 & $ # " 3 , 7 6 & - , - 8 & @ & $ 7 & : & $ 7 & - 7 " 6 1 & $ 8 & J # & 2 3 " : ," : # " $ & 3 9 < % & ( G & # " " : J 3 & K 9 : " 8 6 1 & # H # 5 S 6 7 & & # H , - 6 , & $ $ " 9 $ 8 , 8 & $ 8 " S & # : , , 9 "# " J # " $ " - 1 " : J & - 1 & $ K 3 6 - 4 , $ " S 6 H 9 # , $ H " & : 1 # 6 7 , $ ( A : , & # H , - 6 , < % & 8 " 8 , 8 & $ 8 " $ 1 " 1 6 J &1 & # - , & J # & H # , : , : , 6 $ 3 " H > " 3 K K : , 6 $ S 5 7 6 3 8 " 7 & : J # " " - 8 " # " : , 6 $ S 5 7 6 3 8 " : , - 1 " # K K 8 " " $ 1 " - 8 " # & 9 : " 3 4 & # , # (

G & # " " : J 3 & K 7 & - $ 6 8 " # " : & $ 9 " " : > " 8 " 6 : J 3 " : " - 1 , # : & $ & " 8 6 1 & # H # 5 S 6 7 & 7 & : J 3 " 1 &

, J " - , $ - " 7 " $ $ 5 # 6 & 7 , 3 7 9 3 , # 8 6 $ 1 - 7 6 , $ " 9 7 3 6 8 " , - , $ " - 1 # " J & - 1 & $ 8 & J 3 , - & (

! " # $ "% & ! ' # $ '% ( )

**+**+ ,-,- ..//0−+−=

1 2 2 3 4 2 5 2 3 5 2 6 6 4 4 2 )

int main()

float a, b, c, d;

printf("Abssissa do ponto A:");

scanf("%f", &a);

/* ... */

printf("dist: %f \n", dist(a, b, c, d));

return 0;

7 8

dist 2 2 4 7 2 )

double dist(float x, float y, float z, float t)

float dx = x - y;

float dy = z - t;

return sqrt(dx * dx + dy * dy);

2

sqrt( 7 8 9 7 6

math.h

2 2 3 6 8 ( 2 2 2 7 2 2 2 2 7 8

dist5 2 6 6

7 5 2 x

y

3 z

t

2 ( 6 4 2 4 3 4 2

2 4 2 7 2 2 7 2 6 6 9 2 2 6 3 6 8 6 7 8 6

! " # $ " $ # % % & # ! & % ' ( ) $ % & # $ * % ' + , % , ) - ! . ! / " $ % 0 ' ! / " ! , ! " 1 * ) , 1 2 ! # ! / " ! - 3 $ !* ) , ! ' ! # ' % / 1 * $ 0 % , ) 4 ) ' ) $ ' % $ / 1 , % , ! - 5 6 7 6 - 4 ) ' $ ' / ) ' ! 4 ) ' $ ' - ' % 3 $ !* ) , ! ' ) % 1 / , % # ! 2 ! # 1 # % 4 % , % 4 ) ' * ) / ! / " ! 1 / , 1 . 1 , $ % 0 , ! $ ' 4 ! # " ) , % , ) * ! 0 ) / ) ' ! 8 4 % , % 4 ) ' * ) / ! / " ! 1 / , 1 . 1 , $ % 0 4 9 % ' % # ! ' ) ' ! ' : # ) , ! , % , ) 8

; / 1 4 % ) * ! # % < = ! 3 $ ! ! " > ) , ! 2 1 / 1 , % * % # % % ! " # $ " $ # % > ) ) % 4 ! ) % ' ! ' : # ) - %4 ? * 1 % ! % % " # 1 : $ 1 < > ) 8

@ ) , ! ' ) $ % # % ! " # $ " $ # % * % # % , ! 2 1 / 1 # $ ' " 1 * ) , ! , % , ) 3 $ ! # ! * # ! ! / " ! * ) / " ) A

struct point

float x;

float y;

;

! ! 4 # ! . ! # A

struct point A, B;

A.x=1.0; A.y=1.0;

B.x=4.0; B.y=2.0;

) ' ) % ) * ! # % < > ) , ! 4 ? * 1 % ! " , ! 2 1 / 1 , % * % # % % ! " # $ " $ # % - * ) , ! ' ) * % % #, 1 # ! 4 " % ' ! / " ! ! " # $ " $ # % 4 ) ' ) % # & $ ' ! / " ) , ! 2 $ / < = ! 8 @ ) # ! ! ' * 0 ) A

double dist(struct point p, struct point q)

float dx = p.x - q.x;

float dy = p.y - q.y;


;

0 " ! # / % " 1 . % ' ! / " ! * ) , ! # % ' ) " ! # $ % , ) % * % 0 % . # % 4 9 % . !typedef

* % # % 1 / 2 ) # ' % # )4 ) ' * 1 0 % , ) # , ! 3 $ ! 3 $ ! # % ' ) 4 # 1 % # $ ' / ) ' ! * % # % ) / ) . ) " 1 * ) ! % 1 ' 2 % 4 1 0 1 " % # % ! 4 # 1 " % 8

typedef" ! ' % ! & $ 1 / " ! 1 / " % ! A

typedef <tipo elementar ou estruturado> <novo identificador>

! ' * 0 ) Atypedef int Number;

) 4 % ) , % ! " # $ " $ # %point

" ! # 1 % ' ) -

typedef struct float x, y; point;

! * ) # " % / " ) * ) , ! # % ' ) " ! # ! 4 # 1 " ) % 2 $ / < > ) % / " ! # 1 ) # , % ! & $ 1 / " ! 2 ) # ' % A

double dist( point p, point q)

/* … como antes … */

;

) " ! ! 3 $ ! )typedef

/ > ) 1 / " # ) , $ $ ' / ) . ) " 1 * ) % * ! / % $ ' 1 / ? / 1 ' ) ( ) $ $ ' %% : # ! . 1 % " $ # % + , ! $ ' " 1 * ) 3 $ ! * ) , 1 % ! # ! * ! 4 1 2 1 4 % , ) , ! ) $ " # % 2 ) # ' % 8 * # ) & # % ' %4 ) ' * 0 ! " ) ! # 1 %

#include <stdio.h>

#include <math.h>


double dist( point, point);

int main()

point a,b;

printf("Primeiro ponto:");

scanf("%f", &a.x);

/* ... */

printf("dist: %f \n", dist(a,b));

return 0;

double dist(point p, point q)

float dx= p.x - q.x;

float dy=p.y - q.y;


;

% " $ # % 0 ' ! / " ! 3 $ ! / % , % / ) 1 ' * ! , ! , ! % & # $ * % # ' ! ' : # ) , ! , % , ) 3 $ ! ! % ' ! 0 ! * # ? * # 1 ) ! " # $ " $ # % 8 ! ' * 0 ) A

typedef struct circle

point center;

float radius;

/* ou o que é a mesma coisa: */

typedef struct

point center;

float radius;

point.

! " #

$ % # $ & ' "

circle;

! " # " " $ " % ! & % # " & ' " (

circle aCircle, bCircle;

aCircle.center.x = 0.0;

aCircle.center.y = 0.0;

aCircle.radius = 1.0;

bCircle = aCircle; /* OK*/

) * ! " ! " % ! & #

+ (

• , $ " $ & & % - " " . ! " /

• + $ ! " & " & * * 0 & # 1 ) 2 $ " $ & #

• ! " " ' # % 3 ) ! " % & ' #

4 5 6 5 7 5 8 9 : ; < =

> ! ! " " & " 2 " # ? * ! * & ! " " " % & 3 * % " ' #

? ! " % & " * & & $ 3 $ & " *

char & - .

int &

#

" ! "

struct s

int i,j;

;

& " i

" & " j#

> " & & " & & % #

? 2 $ * $ $ 0 ' # ? & $ " # & % " % 3 " # + (

union u

char lowbyte;

int word;

;

$ * char lowbyte

$ * " word

& 2 " % ' #

" * $ " & $ lowbyte

word

word

$ lowbyte

# (

union u aUnion;

aUnion.word=0x105; /* 105H = 261D */

printf("%d", aUnion.lowbyte);

> (

0 * '

+ * 3 & " " " " * lowbyte

$ * highbyte ,

" (

typedef struct

unsigned char low, high;

lhbytes;

typedef union

lhbytes byte;

int word;

bytesword;

+ " (

bytesword bw;

bw.word =261;

printf("%d %d \n", bw.byte.low, bw.byte.high);

# + " * " * (

bytesword bw;

bw.byte.low =5;

bw.byte.high =1;

printf("%x \n", bw.word);

2 (

+ (

• , " % & * 2 $ " " $ # # $ & " " & #

• " % 0 ! & " " " & " - " & " " " . #

> " * & 2 % $ * ! 3 * ! * ! " & " ! % & & & " & $ & " ! & % & & % & ' # 0 ! & $ & ! &

" & " & & % & & " & ! 3 & ! & " % " $ & " #

4 5 5 < : =

#

" * & " " & % # #

" * " & &

" & " & % # #

+ & * " " * " " " % * 0 $ & " ( . " . " " & . " " . ! & . " ! .

#

+ & * " " * & #

#

" " #

#include <stdio.h> #include <string.h> #include <ctype.h> #define COMPMAX 128 typedef struct int letras, espacos, palavras; contador; int main() char dentro=0, texto[COMPMAX]; int i; fgets(texto,COMPMAX,stdin); for (i=0; i<strlen(texto); i++) if (!dentro && !isspace(texto[i])) dentro=1; printf("%c",texto[i]);

else if (dentro && isspace(texto[i])) dentro=0; /* printf("\n%d %d %d \n", c.letras, c.espacos, c.palavras); */ return 0;

.

+ * * ! 2 # .

! & " " $ #

& .

! & " ! * " & - & " . & #

! * " ! 3 ! &

2. Arrays e Ponteiros

& ) " " & & " & "

" " -ℜ

. # 2 ℜ

" " " & ℜ & "

" n

& " #

* " & - & " . $d

$ " " X

Y

$ " X

" & " (x1, x2, ..., xn)

Y

(y1, y2, ..., yn)

$ * " % (

d =

=−=−++−+−

? & " $ & * 3 & % * 0 2 " ! % & " #

+ " * " * & ℜ

$ " " $

& & & $ &

ℜ $ " % 3 & " 0 # * & 2 * * 3 " %

n$ ) * " % "

$ 3 ' ! " % * & & " & #

" % " 2 " * " " % 0 & & ( # % 0 " " * 2 % #

, 3 & & % $ $ * % & ) " & " # + $ ) " & 3 #

? $ 3 & " # " " * & & " & " "

ℜ #

& "

ai& " " ! (

int ai[10];

& " ai

" ! (ai[0]

" & 2 % " #

/* 1ª Versão */

#define N 10

int i;

int ai[N];

ai[0]=1;

for( i=1; i<N; i++) ai[i]=0;

%

#define N 10

int i;

for( ai[0]=1, i=1; i<N; ai[i++]=0);

> " % % " & " # 3 $

int ai[]=1,2,3;

int bi[3];

bi=ai; + >

* ! 2 % (

for( i=0; i<3; i++) b[i]=ai[i];

"

for( i=0; i<3; bi[i]=ai[i++]);

? * * # + & $ (

#define N 10


point apoints[N];

apoints[0].x=0.0;

apoints[0].y=0.0;

/* Programa que calcula a distância entre dois pontos de ℜℜℜℜn */

#include <stdio.h>

#include <math.h>

#define N 10

double distn(float[], float[], int);

void read(float[], int);

int main()

float x[N], y[N];

printf(“Ponto X: “);

read(x, N);

printf(“Ponto Y: “);

read(y, N);

printf(“d= %f”, distn(x, y, N));

return 0;

double distn(float p[], float q[], int n)

int i;

float sum = 0.0;

for (i=0; i<n; i++)

sum += (p[i]-q[i])* (p[i]-q[i]);

return sqrt(sum);

void read(float a[], int n)

int i;

for(i=0; i<n; i++)

printf(“Coordenada %d”, i+1);

scanf(“%f”, &a[i]);

printf(“\n”);

> 3 " ! & " " & " # ! & " & ! & & " ) " & " % " " * " # ? $ ! & " % ! 2 ! & % ) " & # ? 3 $ 3 " & " % - " . " % #

+ & " " & & " " & & " & ' $ * " & " #

! " " & " ai

$ &

" # " * - . & % ' * & & #

int ai[10];

" 3 * & ' > & " " & " " #

, 2 * " & * & & " " % $ " 0

sizeof(<tipo>)

" ! % # + sizeof

" - " " . size_t

#

7 5 4 5 9 < : =

, " - " . & 0 * " 0 #

" 0 * " & " " " (

char c=3;

char *ptr_c; /*declaração de ponteiro para um char */

* " ! 2 %

ptr_c=&c; /*endereço do char c */

" % ptr_c

! & & !

? * 3 $ 0 & " ! & - " . $ $ -

. & 2 % - . #

? & " # + " " " 3 & void*

# * " 0 & " void*

#

* & " 0 " ptr_c

$ & *ptr_c

$& (

printf("%c", *ptr_c);

, & 3 * & - * . " " " & " # + " (

#define N 10

int ai[N];

ai[2]== *(a+2); /* É sempre verdade */

* ! & & & * " 3 &

" 0 &

$ " " ++

--

$sizeof

* " " 3 " * % #

) *

int ai[3];

int bi[3];

/* ... */

bi=ai; /*ERRO*/

* " " & " ! " % $ & 0 " " " # ? " & * & $ & % " * & % $ * " ! " % ! " # $ & " ! " % * & & (

int soma( int *, int);

int main()

int a[]=1,2,3;

int n = sizeof(a) / sizeof (int);

pritnf("%d", soma(a, n));

return 0;

;

int soma( int *x, int n)

int i, s=0;

for(i=0; i<n; s+=x[i++]);

return s;

& " " & 3 ) * 3 " "

sizeof#

7 5 7 5 < ; < = 9 < : =

#

? - . " n

" # > 3 " " 3 " ! " - 0 . " " " & " #

int a[3];

int *ptr=&a[1];

ptr+1;

ptr-1;

* " & $ & " & $ " ptr

3 " & " - & " . ' * ! * " " " & - . " " #+ 3 " & 2 & % " 0 " # + "

char

float

" $ * " ' & 3 & 3 ! " #

#

? " * " & " 2 # + (

int a[5], *ptr1, *ptr2, i;

ptr1=&a[1];

ptr2=&a[2];

i = (int) (ptr2-ptr1); " & %

(ptr2-ptr1) "

ptr_diff_t* 0 ! "

stddef.h#

#

? & - " & " $>, >=, <, <=, ==, !=

. " * " & " 2 #

#

? ! & " " * ( # #

> " /

# #

2 " /(void *)

"

0 /* ou */ NULL " "

< = < : :

.int x, *ptr_x, y;

ptr_x=&x;

*ptr_x=0;

y=*ptr_x+3;

.void swap( int *, int *);

int main()

int i=1, j=2;

printf("i:%d, j:%d \n",i,j);

swap(&i,&j);

printf("i:%d, j:%d \n",i,j);

return 0;

;

void swap( int *x, int *y)

int tmp;

tmp=*x;

*x=*y;

*y=tmp;

7 5 6 5 : 9 =

+ " 3 & & $ & % 0 & & "

'\0'$ & & ' " 3 & 3 2 # ? & " & "

:

char str[]='a','b','c','\0';

> & $ 3 & " (

char str[]="abc";

3 " & & " & " " & * ! 2 " $ " " # 1 " & 0 ! " &

<string.h> "

" #

? $ ! " % " string, strlen

$ * " & " " $ # # $ " " & & & " & & " # + ! " % 0 " ! " (

/* 1ª Versão: usando arrays */

int strlen1( char s[])

int len=0;

while (s[len]) len++;

return len;

;

/* 2ª Versão : usando ponteiros */

int strlen2( char *s)

char *p=s;

while (*p) p++; *

a while (*p !='\0') p++;

return p-s;

;

/*Programa de teste */

int main()

char str[]="abc";

printf(%d",strlen2(str));

return 0;

" % 0 % " " "

char str[]="abc"; /* array */

char *ptr="abc"; /* ponteiro */

? & ! " " " $ ! " " & (

#

" ! & & 0 * " $ # $ &

ptr++# > " 3 & & " " # $ 3

& str++

#

#

" ! 2

ptr="zybaz";

& " 3 ) % " " /

#

" " 3 & " " #

#

3 " & 0 & & #

7 5 5 9 < : = 9 = 9 < =

> " 3 * &

#define N 10

) &

const int n=10;

3 $ & n

& & " " " #

& " " ' " " & " " / * & " & #

const int *ppci=&n; /* ppci: ponteiro para constante inteira */

> " & " " " & " " 0 & " & " # > " " & " " " % #

int i=3;

ppci=& >

+ i

" % & " " $ " % 0 3 ppci

#

7 5 5 9 < : = 9 = 9 < =

& * * & " " $ " & " " " % # & " & " " " ! (

int i =4;

int * const pcpi =&i;

pcpi = &i; /* ERRO */

% 3 ) " & " " # " " $ 3 ) " " & " " #

7 5 5 9 < : = 9 = 9 < = 9 = 9 < =

$ " " & " " & " " $ " % 3 ) " " " " ' " # & % " 3 ! & (

const int ci=1;

const int * const pcpci=&ci;

0 " "

7 5 5 9 < : = 9 ; < =

> " ' " & & ' ! " % 3 " 0 # 3 ! " " ! " #

& " $ " ! " 3 ) $ ! " " ! " #

& % " ! " % * & ! * " " ! " % # $ & " ! "

min

max ! " & (

int min(int a, int b)

return (a<b ? a : b);

int max(int a, int b)

return (a > b ? a : b) ;

, " ! " $ # # $ " ! "

" int

* " int

3 & - " & 2 2 . & (

int (*pf)(int, int)=0/

*

int *pf(int, int) 3 & % ! " % * " "

int.

& " & & " pf

" ! " % & ) " " &

pf# + & ! 2

" (

pf = max; /* equivalente a pf=&max; */

pf = min;

" & % & ! " % 3 " 3 ! " ! (

f()

int a, b;

a=min(10,20); /* Chamada directa à função */

b=pf(10,20); /* Chamada à função através do seu ponteiro, */

/* e a abreviação de (*pf) (10,20); */

;

" % " ! " % " ) & " 3 ( 0 & " ! " + & $ * " & " # & %

& & " * $ $ " " * & $ $ & " ! " % & # " & ! " * " 3 ! " % * & # > * " 0 $ ) " $ $ " % " " * & & # + 2 & & ' & " ! " % " ) " $ & & 0 $ & & " & & $ & " & ! " % * & & " " - " .! " % & " # + " 3 " & 0 ) " #

include <stdio.h>

int min(int, int);

int max(int, int);

int calcula(int (*) (int, int), int*, const int);

int main()

int a[]=1, 2, 3;

const int n = sizeof(a) / sizeof(int);

int maximo, minimo;

maximo = calcula(max, a, n);

minimo = calcula(min, a, n);

printf("min: %d - max: %d \n", minimo, maximo);

return 0;

;

int calcula(int (*pf) (int, int), int *a, const int n)

int i, res=a[0];

for (i=1; i<n; i++) res = pf(res, a[i]);

return res;

;

? 3 2 % " & ' $ " ! & " " % & ' # 1 - . ! 0 & " & ! " % " & ! " %

calcula * ! " % ) " $

0 $ & #

7 5 5 9 < : = < = =

? & 3 " 2

->$ & " #


point p, *pp;

p.x=0.0;

pp=&p;

pp->y=0.0;

" % ! * (

(*pp).y=0.0;

7 5 5 = < 9 < : =

! * " 3 & (

int ai[5];

3 * " " 3 & & (

int*api[5];

+ " % & 0 & % ! + "

* api

" " / " % ' " #

2 % " $ ! " % * " & " "

“false”

n! " & " "

“true”&

& " 0 #

const char* bool (int n)

static const char * names[]="false", "true";

return (n? names[1]: names[0]);

;

> " " ) # " " $ " % & ! & " ! & 0 & " # " % ( ! " % & ! * " " & " ) " & " " # " $ " "

" 2 #

& static

0 names

# static

$ 0 & " " ) & & - & % " " & . " " ! & #

static$ 0 &

! " % " & * " ! " % 3 & 2 " " ! & % $ " & " " & ! " % # " " $ 0 & " ) " & $ $ " % 0 & ) ! ! " % " 3 ! " #

7 5 4 5 < 9 = 9 : 9

* " " * & & " ! " " " # , & * 3 " (

& * & & ! & & " ! " " " * * ! & $ & (

> fact 3

6

+ & " 3 & " & " " ! " % main

# " ! " %

main3 & $ 3 & & " (

# argc

* & " 3 " " & * 3 &

- * 3 " ' . # $ " & argc

#

# argv

* 3 " $ " " " & 0 " " & " & " " " & * ! & # & $

argv[0] "

"fact"

argv[1] "

"3"- $ " / " % " . #

$ * & * & " & % - " stdout

& . ' " " & * ! & $ & (

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

int i;

printf(“O meu nome e os argumentos com que foi chamado são: \n”);

for(int i=0; i < argc; i++) printf(" %s \n",argv[i]);

return 0;

;

* ! " " & " ! 2 " " * " #

7 5 4 4 5 < : =

#

& " & " " $ & " ! " % * ! * ( .

+ " & #

.

* " & " 3 " " ' " $ $ " & & " " & & " #

#

+ & " % printf

* 2 % & " * # 0 2 ! * & " " #

2.1. int *pi=0, i=1; 2.2. int a[]=1, 2, 3;

int pi=&i; int *pi = a; *pi += i; pi++; ++i; *pi; i

# , 2 $ ! " " $ & "

! " % * " & " & & & " 3 & # ? $ & ' " 0 & ( # + & & ' ! & " #

# " ! " % & " * % " $ " ! " % "

# + ! " % " & " & & & * " % " ! " % & " " ! " % #

* ! " % & " " " " # ? $ & ' " 0 (

# , 2 $ ! " " $ "

! " * & " " & & " " # ? $ ! " " ! " $ & ' " 0 ) #

3. Reserva dinâmica de memória

0 * " " " & # ? 3 $ 0 3 ! " * " % # ? $

− 0 - $ 0 & ! * * ! " % * & * * ! " % . * % & 3 ! # ! " * 3 * " % 0 /

− 0 & - # # $ * % ! " " " ) & & " . " * " & & % /

− 0 0 & % & " * ! " % ! " 3 ! #

? & 0 * " & " " * " # % " " 0 * & " 0 * " 3 " 0 $ 3 2 3 " # & % 0 " 3 ! " - & % . " & ' # " & ' 3 ! & 0 & % & & " ' # ? 2 0 % & 0 " & #

> & ' " ! 2 " & ' " & " #

int *pi;

pi = (int *) malloc(sizeof(int)); /* (int *) é uma coerção ou conversão explícita */

$ " " (pi = (int *) malloc(sizeof * pi);

* sizeof

* " " & 0 ' " " & ' " " " " % #

> " 2 " & stdlib

! " " & ' $& ' " # > ' ! " % 3 & " " $ " * " 3 & " ) " " #

void *malloc( size_t n);

void *calloc( size_t , size_t);

! " % malloc

" " & ' " % " & 2 " %

n$

NULL ! #

& $ " pi

* & " $ 0 * malloc

" void*

# " " ) & (

int *pi;

pi = (int *) calloc(1, sizeof * pi);

! " %

calloc & " & 2 ' * # &

malloc 3 " 0

NULL ! #

' " ) $ * $ 3 ! " # ? $ ' % ! # ' & " ' ! & & " $ ! & $ ' " $& (

if( pi == 0)

fprintf(stderr, “Memória insuficiente”);

exit(1);

" " & " & ' $ * ! 2 " & " 0 & ' & (

% " ) $ & ! & & 3stdio.h

$ " & ! & (

# stdout

$ % $ " ) % * $ % $ 3 & % #

# stdin

$ % $ " " % * $ % $ 3 & #

# stderr

$ % $ 3 & % / $ " % & & " #

) * & printf("abc");

* "

fprintf(stdout,"abc");

int i;

scanf("%d", &i);

* "

fscanf(stdin,"%d", &i);

printf" " " $ & & " %

" ! " ) ! & & " ! & $ # , "

fprintf(stderr, <mensagem>) 0 " % & " & 2

* $ * ) & & " $ stderr

& " " 0 & % #

* " & 0 ' " & " 0 # ! " %

free ' ! "

malloc

calloc# +

! " % " ' (

void free(void *);

$ & ' * & " " pi

$ & "

free(pi);

" ' " & " * & $ " " (

#

" 0 * " & ! & * $ # # $ * " & #

#

" & " & " / #

1 & ! " %

free 0 & " % ! &

malloc

calloc/

#

1 " 0 * 0 ! #

6 5 4 5 < = < : 9 : < < : =

" & ' 3 & " - " & $ 2 " . # + $ "

" % & " " / + $ " % & % * " " & 0 # * " " $ * " 3 & ! & ! & " " & % #

? $ " % * & & " & " " * " " ) " " 0 " & "

& " # " ! " " & " ! & " ! * " ' # " & " " & 0 ! * 3 ! " * $ & " " " # ? $ " % * 2 " & " & " " " & 0 & " # ! & " ! " %

callocf.

> " (

double distn(float*, float*, int);

void ler(float*, int);

float *callocf(unsigned);

int main()

int n;

float *A=0, *B=0;

printf("Nº coordenadas: ");

scanf("%d", &n);

/* verificar n aqui */

A = callocf(n);

B = callocf(n);

printf("Ponto A\n");

ler(A, n);

printf("Ponto B\n");

ler(B, n);

printf("d: %f", distn(A, B, n));

free(A); free(B);

return 0;

"

float *callocf(unsigned n)

float *data;

data = ( float *) calloc(n,sizeof(float));

if (!data)


exit(1);

return data;

;

" * " double distn(float*, float*, int);

void ler(float*, int);

" % ! # , 2 * " & % & " &

" $ " % ! " & 0 " " ! " * " #+ & " & $ &

A[i] * " &

*(A+i)#

6 5 7 5 < = < : 9 : < < : : < =

? " " & & 2 " " ! " % * " & " 2 " $ & & " " $ & " " " 2 & 2 " $ & " " 2 & " & " $ & " (

? & " $ # " $ % * ! 2 3 (

int *ptrelem = (int *) calloc(l*c, sizeof(int));

+ " 2 % ' ) (

" ! " % 0 & calloc2d

0 " % & " (

m = calloc2d(l, c);

? 3 $ * & & " (

m[i][j] = 3;

ptrelem[i]

3 *(ptrelem + i)

$ " % m[i][j]

3 *(*(m+i) + j).

" " $ " & ! " %

calloc2d ! " & " & " "

" " & " 2 # * & & " ! $ * ! 0 & ! & (

> & ' * " 3 " (

pplinha = (int **) calloc(l , sizeof(int*));

for (i=0; i < l; i++) pplinha[i] = &ptrelem[i*c];

" % & ! " % * 2 l

"

c& " $ " 3 & $ 3 " (

int **calloc2d( unsigned r, unsigned c)

int i;

int *pe, **pr;

pe = (int *) calloc(r*c, sizeof(int));

if (pe == NULL)

fprintf(stderr, "Erro na alocação de memória. \n");

exit(1);

;

pr =(int **) calloc(r, sizeof (int *));

if (!pr)

fprintf(stderr, "Erro na alocação de memória. \n");

free(pe);

exit(1);

;

for(i=0; i<r; i++) pr[i]=&pe[i*c];

return pr;

;

+ 2 % ( int main()

int i,j;

int **matriz;

matriz=calloc2d(2,3);

for(i=0; i<2; i++)

for(j=0; j<3; j++)

printf(“%d \n”, matriz[i][j]);

/* ... */

free2d(matriz);

return 0;

;

" * ! " % * ' ! " % 3 " (

void free2d(int **pp)

free(pp[0]); /* liberta toda a memória reservada para guardar os elementos da matriz */

free(pp); /* liberta a memória reservada para os endereços das linhas da matriz. */

;

6 5 6 5 < : =

#

! * * & " " & ' & 2 $ ! " " " ! " (

#

> " # " ! * & #int main()

int *pi;

printf(“No. inteiro: “);

scanf(“%d”, pi);

printf(“%d \n”, *pi);

return 0;

#

" " (

#include <stdio.h>

#include <stdlib.h>

int main()

int i, n, m;

int *a, *p, *e;

printf("N: "); scanf("%d", &n);

printf("M: "); scanf("%d", &m);

a = (int *) malloc (n * sizeof (int));

p = a;

e = a+n-1;

while (p<=e) *(p++) = p-a+1;

do

for (i=0; i < m; i++)

do

p++;

if (p>e) p = a;

while (!*p);

printf("%d ", *p);

*p = 0;

n--;

while (n>0);

free(a);

return 0;

#

) $ $ #? & " #

#

+ * * ! 2 & " #& #

& " # " % $ * " " " " %

#

+ & & " " " " ! " % * & & " " 2 # % ( & & " " & % " " " & $ ' & " " % #

#

" " & ' (

int ***new3i(unsigned, unsigned, unsigned);

void free3i(int***);

int main()

int i, j, k, ***tensor;

unsigned pag = 2, lin=3, col=4;

tensor = new3i(pag, lin, col);

for(i=0; i<pag; i++) for(j=0; j<lin; j++) for(k=0; k <col; k++)

tensor[i][j][k] = i+j+k;

/* mais processamento sobre o tensor */

free3i(tensor);

return 0;

+ & ! " & ' " & & $ & ! % $ & " $ ' " * & " & ! " %

main#

#

" " % " $ " 2 " # 2 " % ( " & & " # " * & & " 2 & * " 2 # " 2 " & 2 " # ) " 2 # > 0& - ' 2 . 0 & & " " $ & # ? $ &

$> sam 4 3 2

! 0 & * & " 2 " & " $ & / 2 & * " 2 #

4. Primeiras Noções de Complexidade

& % & " & " & ( & ' #

% * 2 ! 0 " " 0 & # & & ! * " ' * * # " ! " & ! " & #

+ & * " " # 3 " $ % ! & " * $ & $ " " " & & " ! & " % #

& ) $ " & 0 " & " * & ( #

& " & 0

#

& " " * 2 !

? " * " # ) & " " ) & #

& " & 0 " & # * & ! & " & * 2 ! - ! & . & ! &

" " * 3 * ' # ? 2 $ $ # + " 0 3 * " # " " $ ! " $ " & " % & ! & #

" & # > & & % " & " " ! & * " & & " ! % & $ " % # ? 3 $ ) & " 2 ! ! " " % % & 0 # 3 " % " " * " % " & ! & $ * ! " & 0 " & " " % # " * 2 3 ! & $& " 0 & ! " $ " % & #

> & " 0 0 & " " & ) & - . " " #

, " " 0 & & " " " ! & % & " 2 " & & % & # * * " & & * & & % 3& " & " * & & #

> & " & " 3 " % * " & & - . " " # " & & 2 # + " " " & " " $ " " $ " ' " " 2 " # " % & & 2 - $ " & " 2 . 3 2 " " & - $ " " " 2 . # > " & 3 " " " & & #

$ * & " " & & 2 " $ " 3 ' & " * & #

$ & " " ! " % * " & " 0 " #

int getmax(int *a, int N) int i, mx = a[0];

for (i=1; i<N; i++) if (a[i] > mx) mx = a[i]; −

=

return mx;

++−++= −

=

(

− & " " 0 " " " ! " ! " % & #

− > & " & " % $ %

mx=a[i]! " % & #

! & $ " " % " ' " # & " " & (

# & # $ & & * " 0 " & & " " & " 0 " # & $ −

=

*

+=++−+=

" % & " " * " & #

#

+ 3 # $ & " % ' " " #

#

? & # $ & & * " 0 " & & " # & $

+=+−++−+=++−++=

−

=

" $ 2 $ % & " " * " & #

& " " " " " 0 & $ # # $ " & * 3 & % " " # " " & * & " & % * * " # " $ " " & " & " ( " " % & " 0 * " & " " 0 & #

5 4 5 < : < = = : :

? 3 " 0 & $ " " * &

$ # # $ " & " & & & " " " # % " $ " & & " 3 " & # * & ! & " & - . * " ! & * " & & & * ' " & " $ * " 3 ! & " " # " 0 & # > & ' & & " & % ! & " 0 #

? * 2 * & - . ' & 3 " $ " " (

3 >

" * * & " % > " #

+ " 0 ! * 3 ! & " * $* ! 2 & $ & ' & " * # + $ " 0 " % 3 0 * " #

3 " & # > & & ! ! " $ & " 2 " ' & & % " 2 #

5 7 5 < : =

#

3 & & " " % > "

−

+++

#

" & ' & 3 * * " & $ * & 3 " & " " - " " " & . 3 & ! - " " . #

#

.

" ! " % " & " 0 2 " & " /

.

" & & ! " % * " #

#

? & & " ' $ " "

. " & " % (? - .

. , " (? - . - # # # -

. . .

" " & & #

#

.

? " ! " % " & & " " # .

" & " " & # & & " "

5 6 5 = = < = < < : < <

" % > 3 " " ! 0 & # + " % ! 0 & & " " " 3 & " & " " # ? & ! & " ! & " % > & " ! 2 % # ! " %

" > " & " " ! "

≤≤∀∃∃= >>>

1 & * " % > " ! " % & " " # 2 * 3 > - . $

∈ $ &

" > $ 3 2 * 3 & " " > $ * 3 & $ & & > # ! " & #

+ * $ $ #

1 " " * > 3 $ " % " & " " # 3 > " % 3 3 > $ &

& & ' & ) & " &

− & " " $ # # $ & % " % " " " $ " > >

− ) & $ > /

− " $ >

− ? " >

− * 0 & $ >

− & & $ >

− " " & $ > $

− ! & $ >

& % " & & " & $ # # $ & ! & " & # ? & & "

$ & & " " $ & & " " # & " % " & ) & & " " " & ! & #

! " & & " & " ! " % " " $ # 2 % & ) & # ! * & & - . * #

101

102

103

104

105

106

100

105

1010

1015

1020

N

Cre

scim

ento

Logarítmico, Log(N)

Linear, N

Pseudo-logarítmico, N Log(N)

Quadrático, N2

Cúbico, N3

? & % $ " ! " " " " & & " & & $ " & & " " " & ! & #

101

102

103

100

1050

10100

10150

10200

10250

10300

N

Cre

scim

ento

Cúbico, N3

Exponencial, 2N

Factorial, N!

+ & & " " 3 #

" & " " 3 & 2 " ! ! ! " # " " * " & # > 3 ! % $ $ $ * " % 3 " " 0 & & #

" " & % & # & " " ! " % " " #

& " " " & & ! " $ # # $ - . - ) ! " . " # > & & 0 3 & 2 ! " $ ! # ? & % $ & *

" $ & 0 $ 0 & 2 "

! - " " . #

2

! - ! .

# # 3 & ! - .

!

# ? ! - ! .

# "

* " & ) 3 " " " & ! & $ " ! # * & & & " $ " & " " & - . "

!

3 " " & ? ! - ! .

3 & 3 " $ $" " &

? 2 * & % " " & ! & " % $ $ " " & " #

& " % & * " " & ' % 0 & 2 " # 2 * 3 ! & " & ' & ! $ * " $ " $&

1 & % " * * & " * "

& " & & " 3 " % " # + 2 #

1 " " * " % % " 0 # > " & " & " & " & " * * & " " ! % " ) " $ " 2 0 " & 0 & & & " " ! 3 & $ * 0 & & " " & & & ' " & #

5 5 < : < < < = : : <

5 5 4 5 < < = : <

& 0 & $ 3 & % " % & % 3 " % & " # & " " " $ & & ! & " #

" 0 & $ ! " % 2 & & " ! ! " ' #

$ ! " % 3 & & ' #

, 2 & * " " & " % " " " & " #

> & % " ! " & ! " & & " ! " & ! " 0 & #

2 ! " % & $ 2 & & ! " %

factorial# >

factorial "

n$ "

n!$ 3

(

=≥−

=

, " % ! " % 3 " (

int factorial (int n)

int i, t=1;

for (i=2; i<=n; i++) t*=i;

return t;

, " % $ & $ " % * factorial

! " & (

=≥−

=

3 " (

int factorial (int n)

if (n==0) return 1;

return n*factorial(n-1);

;

" ! % % & % 3 ) # ! $ & & * * & % * " & & $ " & % #

+ & % " " & " & ! " % ! & $ & & (

factorial(3)

3 * factorial(2)

2* factorial(1)

1 * factorial(0)

& " ! * " " & ! & & & ! & ! & " & # "

factorial$

2 % & " " 0 & $ ! & " " % #

" " $ 3 " & 0 & " * $ * " ! " % & $ & * 0 " & " ! " & % # ! " & % & " " 0 & & ! " % " & % - * & " " " . # ? " $ " & 0 " % & #

! " & & % " ! " & $ % 0 & (

• & - & & 2 & " % " % " 3 & & & " " &

factorial& "

" if (n==0) return 1

/

• & & " " & 2 * " #

5 5 7 5 < < 9 : =

> & % $ ! " % & 3 & * % & " $ & " & # * % * & & % % & ! & " & 3 (

>Θ+=Θ

=

& & & * " " " % #

! " % " " & " " ! "

≤≤≤∀∃∃∃=Θ >>>>

2 * 3 - . $ $ 3 2 * 3 & " "

# ! " & #

+ * $ $ 0 " #

& ! " > * 3 " % 3 3 > #

" % ! " % & ! & & " & * " & % #

" ! " % ! 2 % & & " $ if

return

/ & & " " / & & " 0 $ ! " % " 0 " " & ' ! " % & " * 3 " " & " # & $ " " & " " * & % 3 & #

? " " & " & % ! " & ! & & " & & # + & $ * " % " $ * " & " $ & " & * & & 2 ! " % & ! & 3 " (

, ! 2 " & " & " & " & # ? & " & & ) $

+=+=

=>+−=

=++−=

+−=

? * " % > $ ! * 3 #

" & ! " % & * & " * & " " $ " " * ! " % & " & " & 2 # > & % ! " % 3 (

>Θ+=Θ

=

" " & " & (

+=

+−+−+++=+−+−++++−++−=

=+−+−+−=

+−+−=+−=

? * 3 >

" * " & 3 % 3 & & " #? " % 0 & * % 3 & & " 3 (

+

=

=

(

−+=+= −

5 5 6 5 < < < = <

+ & " " ! " & & & % & " & ! &

+ ! " - . $ & * & " " - . # > & % " % 0 3 #

& " $ 2 " " " $ " $ $ " " $ (

#

Θ=

& εε

−> =∃

#

Θ=

& Θ=

#

Θ=

& ≤∀∃∧Ω=∃ ≥

+>

εε

" (

≤≤∀∃∃=Ω >>>

2 * 3 - . $ $ 3 2 * 3 & " " # ! " & #

? $ 0 #

! " > $ * ' > ∧

? $ & % # " & " & (

& $ # ? 3 $ Θ===

$ * & & $ "

> # " & " & (

& $ # ? 3 $

Θ===#

, 2 *

−− ===

ε

# # $ " % & & (

5 5 < : =

#

.

" % & 3 * * " & $ * & 3 " & " " - " " " & . 3 & ! - " " . #

.

+ & ' & ! " % " " ) " " & " & % & ) & # #

# " & ' & & " &

.

>Θ+=Θ

=

.

≥Θ+<Θ

=

#

" & % " & " &

5. Algoritmos elementares de ordenação

+ % & & * " % " % # > " % % 2 & $ & $ " $ 3 & $ ! & 0 & / " " #

? & " % " % * " " " " " " " " & " ! % " & # " * % 0 " " " * & " 3 ! ) #

& ) & " 2 " % * 0 " % " " % # + " % ! & " $ 2 % & & * " % & " ! 0 & & " # & ) " " % & ! & " * * " * #

5 4 5 < : 9 : < < : 9 : < < < < 9

" * & & % " # - " . " & & % 3& & " " & * " & % # - & . * & & 2 ! " % & # & % & " & % # " " $

& & 2 " $ " $ & 0 * * & $ " " * " % " $ " #

" & & % " - $ $ # # # $

. " & & # ? 3 $ " * % & - . * * * & $ $ # % 3 " $ $ * * & $ $ 2 2 " % 2 #

> " % ! " & " & " % σ

$ *

σ

σ / $ " * " % 3 (

σ

$ σ $ # # # $

σ

, 2 * & & % & $ % " % 3 " & #

? 2 " " & " % " & $σ

$ & " (

#

"

σ

σ $

#

0 " % & 0 " * $ " & & % " # ? $ " % 3 0 " & & #

? $ & & % " & " ! % " $ " " $ ! & * " & & % " " " " , " $ " % 0 2 0 & & % * " 0 " ! & " " * " " " #

" % * " " & " % # 3 " & 3 & & 2 " % # > & 3 " & (

#

> & " # 1 & 3 " " & & 2 % " % # & " " & * " " & - * " & . $ " & 3 /

#

' " & 0 # & 3 " . * & " % " 3 ! " ' & & % * $ " $ " % " & ' $ & . * " & & ' & & % " ! " & - $ " .

n " /

& & * " ' " % 2 0 3 0 & ! & * * & " % " & $ $ " " % " & & % ! " & ! * ! " & " " & $ " & " " & " # & $ " % 2 " & #

#

& 2 % # , " % " % " " " # " % " " & & % " 3 ! & " " * " " ) " ' " & # " % " $ & & % 3 " & " ' " & " ) " * & ' $ & & ) # " & ! " " " % 3 * " " % " " $ & & % 0 " ) * * " " $ " * " * " % " $ " % * & * " & " $ & #

#

# , " % 2 & " % ! " ) " % & & % " $ $ ! & & & % 0 " " ? % $ " " ) " % " & " 2 " % #

#

> " # , 0 . & - & 0 & . . " & $ " " & " % " % " "

" ' - ) & . # + " ' 3 " 2 " & " " ' #

> * " & ) % 0 $ " " $ & $ " ) & " % " & ' $ 3 0 $ & " & & #

5 7 5 < 9 = < <

> " % & % ! " & " & # ? & & " & & % & " & $ & & * 0 " % & & % # $ & & " & " " & & & * 0 " " % $ & " 3 * & & % " #

! " & % " & & %

- " . " #

= = < : = - " ) & .

* & & & " " " % ! " $ * " % 3" & 0 & #

! " % " " " & & %

N " #

void selection( type *a, int N)

int i, j, n=N-1, im; /* im - indice do min*/

for(i=0; i< n; i++)

im=i;

for(j=i+1; j<N; j++)

if (less(a[j], a[im]))

im=j;

swap(a[i], a[im]);

? & ' $ 3 " & 0 ! " " ! & " " (

type, " " /

less

$ * & & " % / swap,

* & "

, 2 * $ & $ " " " & " " & $ " " ! & " ) # $ 2 ! " " & & #

, & & & & #

0 ) 3 & $ & ' & " " $ " & % # ? $ * " & " " ) &

#include <stdio.h>

" & % $ 3 & 0 " & " " ! &

stdio.h#

& 2 ! " ! & " & " & ' * & 3 & & % & & ! " #

$ & " & & ' ) ! ) $ " " * 3! & " 0 0 " #

? & & % " ) (

/* file: type.h */

typedef int type;

#define printfstring "%d "

#define Key(A) (A)

#define less(A,B) (Key(A) < Key(B))

#define swap(A,B) type t=A; A=B; B=t;

" * " &

ssort * $ $ "

! (

> ssort 0 8 1 5 4 <Enter>

0 1 4 5 8

" % & ' & " ! " % selection

(

#include <stdio.h>

#include <stdlib.h>

#include “type.h”

#include “sort.h”

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

int i, N=argc-1;

if (argc ==1)

printf(“Utilização: ssort <sequência de números separados por espaços>”);

exit(1);

type *ai= (type *) malloc (N*sizeof *ai);

if (!ai)


exit(1);

for(i=0; i<N; i++) ai[i]=(type) atof(argv[i+1]);

selection(ai,N);

for(i=0; i<N; i++) printf(printfstring, ai[i]);

free(ai);

return 0;

? " ! " % selection

& " * " & ) " #

void selection( type *a, int N)

int i, j, n=N-1, im;

for(i=0; i<n; i++) im=I;

for(j=i+1; j<N; j++) −

=

if (less(a[j], a[im])) −

=−

Im=j; −

=−

swap(a[i], a[im]);

" & " 0 & 0 & " # " % $ ' & & & % * 0

i & &

for# > & " " 2 *

& & " 3 & #

" % " 0 & * ! & 0 * " & & % " & & " - " " . # & $ % & & & 3 ! & " 2 * " & % & & $ $" & $ # & " $ & % (

−+−+−++−++= −

=

−

=

−

=

" *

−+=++−+= −

=

* " & 3 (

−=+=−

−

=

−

=

* (

=++=

−+−++−++−++=

" $ % & " " * " & # 3 * & * " . & & % 0 " $ . & & % & & . & & % & " % ) " $ & & # ? ! & & # ? $ " " & & " " % & $ $

- & & &

swap ! " & 3 " 2 * .

*

! 2 " % ! 2 3 & " " * " * ! & & & & # " & * " % 3 #

5 6 5

< 9 <

+ " " % & % " " " % & $ " & 2 * ! 2 & % ! & " & $ " & 0 # , " & " & " " * 3

bubble sort# + & "

& & % & " " & " * " & " ! # , " % " 3 " (

void bubble( type *a, int N)

int i, j;

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

for(j=N-1; j>=i; j--)

if (less(a[j], a[j-1]))

swap(a[j],a[j -1]);

? * " " $ & ' 2 " (

= <

- " 3 .

$ & & - 0 . $ & & - 0 " % & & . #

+ $ & " & bubble sort

" " ! & % # " % 0 ) & " " " % & " " & " ! & " * & % 3 #

& * " ! 2 3 " " " * & * " % & & # % " & 3 * 0 " # " % " % 0 & & # ? " 0 & " % " " & &

for#

3 * * " & & % 0 " " % 3 - . " $ 3 3 * 3 % & * % " # ? *

> & " % ! & " " " % & 0 " & % " #

5 5

< 9 : 9 = < > & & " ! " %

bubble " * # & &

" " " & " 0 & " " $ * & & % " " # & $ " % ' " " % # + 3 3 & " & & " % " % #

" % " % 3 3 " % * " ' 2 * " & # " & & 3 " ! " $ " " & & & 3 & " % " % & & & #

" % & $ " " " " * " " & " ! % (

3 $ * ) " & & " % i

" % " $ " % " % ! " $ 0 * % * & " - & & . " " & " " # ? & " $ & & & % * & " & & " * % * $ " & 0 #

" " " " i

? & & % " " & $ " % & (

= <

- " 3 .

, % " $ & ! & " $ 3 " (

void insertion( type *a, int N)

int i, j;

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

for(j=i; j>0; j--)

if (less(a[j], a[j-1]))

swap(a[j], a[j-1]);

+ % 0 & " " (

#

? " & & " * " " & " & * " * & & $ * & & % * & & 0 " # + " % ! 2 % % " % #

# * & & " * & & " $

& " ' " ! & " & % #

+ % " (

void ainsertion( type *a, int N)

int i, j;

type t;

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

t=a[i];

for(j=i; j>0 && less(t, a[j -1]); j--)

a[j]=a[j -1];

a[j]=t;

" % * 3 " $ 3 * " " " & 3 # + " $ & " & ) & ! & * $ & & ' $ ! " %

ainsertion3 & & 2 0 * ! " %

bubble & & $

0 * ! " % selection

#

" " % " % $& " " $ * " " " ! & " %

ainsertion * " #

5 5

< : = #

& & % & & + + > $ " & & " ! * & & % * " 2 " % (

.

& % .

& - .

& .

" %

#

+ & ' & $ " & $ ! " " %

a) insertion .

ainsertion& .

bubblesort

#

? " " & ! " selection

ainsertion

#

3. + & * " " " " & " " ! " " % # > 0 & " & & " & " % # % ( " ! " # $ & " " ! "

selection, insertion, bubble

ainsertion " '

! " #

#

" * 3

a$ &

N " "

" i$ & ) " & " # " ! " %

" % $ " ! " % ainsertion

* (

i[0] ) " & " "

a$

i[1] ) " & " " "

a$

# # #i[N-1]

) " & " a

#

#

+ 2 " " " " " " & " 0 ! & # ? 3 " $ " 3 & & 2 " $ $ " " $ " & " " $ " " % # " " ! " % " & ! " %

ainsertion$ & & % " &

' " #i.

ii.

iii.

" #

6. Mergesort " & " " & ! ) & " & & & " " # ? " " & " " " # > " " 3 ! # $ * " " " " & " " & " & $ " " #+ " 3 & " & & $ " & 3 " 2 " " * " # % " % & " ! % " #

> 0 & " * & ! & 0 ! " & # 1 & 0 & # > ! " & " " " " " #

5 4 5 < = : :

> 3 & (

# & & % " & " & &

- " . " / #

> " & & & % & " ' /

#

" " ! % " #

# & & %

0 " & " % (

+ & ! & " ! (

#include "type.h"

void mergesort(type *a, int n)

int m=n/2;

if (n < 2) return;

mergesort(a, m);

mergesort(a+m, n-m);

merge(a, n, m);

> & " % 3 & " & " # ? & # & " " & $ & 0 " & & & $ & & * " & # ? " & " " & " ) " & & " "

& & # 3 * " " & " " " " & # ! " & * & " " $ " #

? " & " % $ " & " ' - & & % . & " & " & " & & % " $ # " " % ! & & % 2 * " % " % 3 ! " $ " % & " ' & & % " $ & & " & & * 3 * # " & & % & 2 " ! " ! & " & " (

void merge(type *a, int n, int m)

int i;

int l2r=0; /*left to right index */

int r2l=n-1; /*right to left index */

static type aux[MAXN];

for(i=0; i<m; i++) aux[i] = a[i];

for(i=m; i<n; i++) aux[i] = a[n-1+m-i];

for(i=0; i<n; i++)

a[i] = less(aux[r2l], aux[l2r]) ? aux[r2l--] : aux[l2r++] ;

! " % &

a "

n " * * - m=n/2

" . * " a

% " " " $ & " #

> & & & " # > " & & & $ " $ "

a

" # ? & $ & & " & " ! % (

- ) " & . "

a

> % & " " & 0 & # * * ! 2 3 & & " " " & 2 0 & " " " #

, * " & $ & aux

& $ * & & - & & . " " " 3 & & - & & . " " " $ 2 * " & ' " & #

5 7 5 < = < < 9

> & % mergesort

3 " " " % " $ ! " % 3 " & " & (

Θ+<Θ

=

" & " 2 & & " & & " 0 & " * & " % $ # # $ ! " %

merge," & & "

? $ & % # # $ & " & * & ' &

mergesort3 & &

" % * $ 3 * & " 3 " #

? $ ! " % merge

" & & " % & & % " $ * 3 " #

- ) " & . "

aux

5 6 5 9 9

1 " " ! " % merge

* " % " & & & % # " & " & - . & " # ? $ " ! " %

ainsertion % ! " %

merge, o * ! 2 " % " #

0 * " " % ! " & ! " % " % & & " " " $ 3 & & & " &

ainsertion"

& & % $ # # $ & & % " 2 & " " & ) $ & ! 2 "

ainsertion# " & " & ) &

$ ! & " ! & * " % " " & 3 & % $ & " * 0 " & " &

ainsertion#

" ! " % * " " & & " " $ " ) $ & " % ! ! 0 & #

5 5 < : =

# & & % & & + + > " & & &

* " 2 #

# , & " * " ! " % *

" & " " ) # + & ' & ! " % " #

#

+ #

#

+ & ' & ! " % mergesort

* 2 " & ! " % " % " (

/* Função de junção no lugar baseada em ainsertion.

Args:

a – colecção a ordenar, constituída por 2 subcolecções garantidamente ordenadas.

A subcolecção direita começa em m.

n – número de elementos em a

m = n/2 */

void poor_merge_in_place(type* a, int n, int m)

int i, j;

type t;

for(i=m; i<n; i++)

t=a[i];

for(j=i; j>0 && less(t, a[j-1]); j--) a[j]=a[j-1];

a[j]=t;

#

" " " ! " " % ainsertion

mergesort

" ! " % merge_in_place

& # , & & " # " ! "

n#

7. Quicksort

> quicksort

! # # # " % 3 " % # >

quicksort3 & 3

" % 0 & " " ) $ & ! " % $ " " % & #

quicksort ! & ! 0 & " $ " " " " " # , " 0 & 3 *

quicksort, &

, 3 " & & %

" " > - # " " $ " 0 & * & & " ! & " * # , " & " " * & 3 * " % 3 0 #

5 4 5 : = :

+ " $ quicksort

" & (

#

+ & " * & # #

" " " (

#

> " & & % " * & /

#

> " & & % & /

# , & " " & #

" & " " $ 0 " & " " * & 2 $ " $ 3 & & " % ! " #

* ! $ " " "

* " " ! " # % * $ 3 " " #

5 7 5 < = : : = :

& & & 3 * 0 & " & 2 # ? % & & & " $ $ $ #

" & " & $ ! ' $p

#

- ) " & .- " .

& & " * 0 " % - " % . #

" $ & $ & & " p

$ " * " * # ' & & " 0 " (

/ " " * & & / " * #

- .

! & & $ & & " # > " ! & (

" % * * $p

$ " % " " *

p# " %

* * & " $ " ) " & $ " % (

? " & " & * p

! & & & " % ! " $ " #

> & " * & & 3 & "

* p

#

& % 0 * " & " " # " & " $ 0 " " " # , 2 * & % - % . & " $ " $ " " % ! " $ " ! & " & & % #

> & ' & " " & % 3 (

#include “type.h”

void quicksort(type *a, int n)

int i;

if (n < 2) return;

i = partition(a, n);

quicksort(a, i);

quicksort(a+i+1, n-i-1);

;

int partition(type *a, int n)

int i, last=0;

swap(a[0], a[rand() % n]);

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

if (less(a[i], a[0]))

swap(a[i],a[++last]);

swap(a[0], a[last]);

return last;

+ % 3 ) & - & 0 & . # 3 " " " " ) * " & " $ 2 " & * " & " $ $ & #

! " " #

5 6 5 < = = = :

% & " & " " $ 0 " " * " - . ' # , 3 % $ " " " ' $ 3 " (

#

+ & p

a[n-1]

- 3 ) a[0]

. # #

? & * 3 " & " " $ "

a[l2r],* *

p#

#

? & * 3 " & " " $ "

a[r2l]* " *

p#

# , 2 * " % ! $ % & #

! $ " " " & % ' & $

" " 2 % (

> & " * " ) " & l2r

r2l

& 2 # " $p

3 & & " * " % - % . $ $ & " " &

l2r#

+ (

+ & " ! " " " " ! (

int partition(type *a, int n)

int l2r=-1; /*left to right index */

int pp=n-1; /* pivot position */

int r2l=pp; /* right to left index */

for(;;)

do ++l2r;

while(less(a[l2r], a[pp])) ;

a[l2r] == a[pp] " % & & 0 *

l2r" % & 0 *

do if(--r2l < 0) break;

while(less(a[pp], a[r2l]));

if(l2r >= r2l) break;

swap(a[l2r], a[r2l]);

swap(a[pp], a[l2r]);

return l2r;

5 5 < = < < 9

! " " quicksort

3 & % # + & " ! * & " " ! * (

. a[i]

0 " % ! " $ i

" n-1

# .

" "

a[0]$a[1]

$ # # # $a[i-1]

% * a[i]

# .

" "

a[i+1]$a[i+2]

$ # # # $a[n-1]

% " * a[i]

#

! & " & " ! & & & % " #

& $ " " ) & % & - & . n

" " n/2

" # " " ) &

2*n/2 "

n/2 "

" n/4

" & # + & & & n " ) & % # $ & " 3 & "

=+++

! & $ & " ) & % & & % " ! & " & &

n " $ " & %

& " & (

Θ+<Θ

=

" n ! & & " & & n & " " % # ? & % # # $ n n n

> & 3 & & 2 n-1

" 1

" & " ) & % # ! " %

quicksort& '

n 2 $ $ & % 0

n" ) # + & " ) " & " " & " # % $ & " & * " & % 3 (

Θ+<Θ

=

* $ * * " & $ " " " & % # # $ n 3 n #

? * " 3 * & 3 " & # ? " " $ " ) " & & % # & " $

n " #

% " % ! - $ $n

. $ % 2 0 & & & "

n $ & " # $ * & %

3 & " & (

Θ+

<Θ= −

=

" 3 * ∈

#

? " & " " " " * 3 0 ! 0 ! 0 - " " * " " . & ' & * " % ! 0 # ? 3 $ " % '

n " $ & " &

& " " " & " & n

# & " 0

1/n!. % & * $ & "

$ " " & " " % " #

< < 9 = < ; < = < < 9 =

, " ) * & % * " & & ' 2 " " & * " #

) * ! & " $ & 0 3 % ! & " * " ) & " " & * " #

, ! 3 " * & 3 " % & " & " ! & " " & & * " # , " ! " %

quicksort(

if ( n< 2 ) return;

"

if ( n < C) ainsertion(a,n);

" * & &

C" % 3 & ) & $ " #

" $ * % ! * " " & ) & #

> ! & & & * " 3 " * & & $ & (

void quicksort(type *a, int n)

if (n < C) return;

/*…*/

;

& $ & & % " & $ & quicksort

$ ! &

" # + 3 * ! & " & $&

ainsertion# + & % & " & 2 " " ! " % (

void hsort(type *a, int n)

quicksort(a,n);

ainsertion(a,n);

;

# # #

< < 9 : < < : 9 < 6 = = " & " & " 0 & & # > " " & $ " ! & " " " - * . " ' $ 3 " & & % " # ! " $ " " " & & % $ " % 3 p=medianaa[0], a[n/2],a[n-1]

# + (mediana1, 8, 4=4; mediana1, 1, 8=1

# 3 $ " " & #

! & & ) & $ * " & " " & " " & " #

5 5 9 =

<stdlib>

" " " " % quicksort

# + % 0 " " ! " % qsort

#

! " % qsort

" & * 2 ! " ! " % & % "

" # " * * $ " ! " % & % % *

void*#

* " * " ! " % qsort

& ) " (

#include <stdlib.h>

#include <stdio.h>

int intcmp( const void *p1, const void *p2)

int i = * (int *)p1;

int j = * (int *)p2;

if (i <j) return –1 ;

else if (i==j) return 0;

else return 1;

int main()

int i;

int a[] = 0, 1, 8, 5, 4;

qsort(a, sizeof(a)/sizeof(int), sizeof(int), intcmp);

for(i=0; i <n; i++) printf(“%d “, a[i]);

return 0;

;

5 5

< 9 : = : 9 : =

" " " % $ ! & & * * #

" % * 3 & #? * * * * & 0 $ " $ " " $ " & # ? " $ " & $ * & % & " ' # ' " " " % & 3 * & " " ' & #

5 5

< : = #

" " (

- " .- % .

" & * * " & % & 0 & * &

#

? " % & 0 & * & & & " ( # #

& & " /

# #

& & " #

#

" " ) & % " % ) & * & $ & & % 0 " ! * #

#

> " & " 3 % ) & * & % " % " % $ ! " % " " " & & % # , & & " # " #

#

" " " % & % & 0 & * & $ ! " % " " " & & % # , & & " # > * & " &

#

" " " " % & 0 & * & & " % & $ $ & & * " $ ! " % #

#

" " " " % & 0 & * & & 2 % " #

#

" " " " % & 0 & * & & 2 % & " " & & & * " " #

#

" * 3 a

$ & N

" " "

p$ & " " # " ! " %

" % $ " ! " % quicksort

* (

p[0] " " "

a$

p[1] " " " "

a$

# # #p[N-1]

" " a

#

#

" " " * & $ ! " % " " " & & % # , & & " #

8. Introdução às listas ligadas

> % & " & & % * " * " % & % # " " " " ! & " " - . " ! & " $ # # $ & # ? " $ $ " " " ! & 0 & # & " % " " 2 0 # > * 3 * ! 0 - " " . & " " ! " ! & " & 0 $ & 0 " " " " " " 0 " % & % #

? & $ & " " " # & " 0 * & " & " $ & " " % & ! " # " - " " " " . " # " % % " ! & " " # " " $ & " " $ " " " & 0 # * ! " & 0 2 " " " ' " & " " ! 2 " % " # * " " & 0 ' #

$ % & # 3 0 # & ) ! $ " # + & ) " * " / - " % .& & / - " % . " " $ " " " 0 *

& ! & % " " # 3 $ 3 " $ & & & " " $ " ! " #

5 4 5 : = = = : < = < 9 < : =

, " $ & $ 3 & & % " ' * & " '& " 3 - . % " ' #

1 " " " ! (

+ " % $ 2 3 & " " % # ? $ 2 3 * " ' " $ & " & & #

# # < : 9 :

" " & " (

2 $ $ " ' / & " $ $ " " ' / & $ $ " ' / & $ * 3 " " " ' #

! " " (

& /

& $ & " / ! & 0 2 / " " " ' / " ' / / & / & & / & " & " #

! " " * & " " % " " ' " "

$ ! " " * & " % " '

5 6 5 : < : = : < < 9 ; < =

? " " ! " $ & " $ & ! " * & & 2 & " ' #, % (

struct node

int item;

struct node *next;

;

+ & % & " 3 * * & ! " & # * ! "

next$ & "

node

$ " & ! " ' node

# > & " * " " % * " & #

" " $ " % 3 ) & s

$ * '

s# ? $ " % 3 ) (

struct s + >

int i;

struct s ss; + >

;

%

node & "

" (

#

? * 2 & ' * & " ! " - " . # 0 ! &

typedef int type/

type" & %

struct node#

# , 2 * " & ! * " "

struct node *$ & " & 2

* ! & 0 & ' * & " 0 ! " " $ & & $ $ & list_pointer

$node_pointer

link

#

$ " % (

typedef int type;

typedef struct node* link;

struct node type item; link next; ;

, ! " % * & " ' $ " " 3 #

" % * 0 & * * & 3 " (

& ' 3 (

#include <stdio.h>

#include <sdtlib.h>

typedef int type;


struct node type item; link next; ;

void f()

link first, second, ptr;

first= (link) malloc(sizeof *first);

if ( ! first)

fprintf(stderr, "Memória insuficiente");

exit(1);

;

second= (link) malloc(sizeof *second);

if ( ! second)

fprintf(stderr, "Memória insuficiente");

exit(1);

;

first->item=3;

first->next=second;

second->item=1;

second->next=NULL;

printf("Neste momento a lista contém:");

for( ptr=first; ptr; ptr=ptr->next) printf("%d \n", ptr->item);

free(second); free(first); /* equivalente a free(first->next); free(first); */

;

+ ! " % - . 3 & " 0 & " ) $ & " #

5 5 < : =

#

! " % f

& ! " " " ' $ # # $ ! *

second "

first

NULL#

#

! " % f

& ! & " & " ' /

#

" " % % " ' & " & % #

9. Primeiras noções de Projecto e de Projecto por

Contrato

& & " % & * ) " ! & " ! " %

f() & ) "

,* & " ' " # + " %

" 0 * & " & & ' * & $ " & " (

#

#

" & '

* $ " * #

5 4 5 < <

, " & " " & + " " 3 % ! 0 & & " # & 0 " " 3 & " 0 # ' " $ & & " % & # & 0 " " 3 & ) " #

" ! & & $ ! & 3 & ! " % * 0 " ! " " ! 0 & " # + ! & 3 ! & & # > & $ " 2 % " ! " " " " ) $ " 2

* & " $ & # 0 & % - * * " " " % & . 3 $ $ ! & ! & ! & # 3 $ & " $ " & $ " ! 0 & " " 2 % * " & ' 0 #

> " ! ) & & % " & & * & " ! " % ! " $ " " " $ & " ! & ! " $ & ! " " & ! " #

" " & " " ) & % (

& " % " " % - # # $ & & " . /

? " % 0 ! " /

2 & " & % /

" ! - * " . /

" 2 ! 0 /

& & /

1 & % 2 % /

& 2 %

" " & % $ & " ! " (

3 " " & /

& & 2 % & " & ! " % * " 0 /

% & " " 2 /

& % ! " " % 3 " & ! & % ) # , " " ! & % & & & " " #

+ $ & " ! " * " $ " * " % % & " & ) & #

> " " 0 & * " & & " % & " & $ " % $ ! 2 + " " ! & " & " " 0 % #

+ $ ! & % $ * ' 0 ! " % & # & & $ & % ' $ 2 % $ ! " " " " " $ " * " & 2 " " #

? & & * 2 % 2 & 3 # & % ! & $ ) & 3 & #

5 7 5 : < < =

? " " ! & & ! * " " & # , $ * " ! & & " " ' ! " # > & " " & # ? $ " " " % # & " ' ! & " " ) # ? $ 2 * * % ) * " ) & 2 " " $ " % ' ! " " % & & " & " * ! " % & " & ' #

5 7 5 4 5

9 < 9 < = : < =

! " % & 3 " & " & " " # ? ! " " " & $ & & $ & " & #

" & $ # # $ 3 ! " % " (

& " ! " 3 " " # ! " $ ! " % & ! " % #

> ! " ! " $ # $ " ! " 3 " & " & # ! ! " 2 $ & " ! % & " $ # # $ " $ " & # > " " " ! #

! " % &

& 3 ! "

! " % 3 ! "

" $ ! " % & ! " % # + $ & " (

, " & " " & " (

A() /* … */ y = B(x); /* … */

> " " & & " & "

! " " & % * & "

)

5 6 5 < : = 9 : = < IR

* & & " & " " ℜ * &

" & ) " & % # " " #

" - . * " " & " " & % ! " 2 # " " ) # " * & ! " $ " "

% ' & B

# $ & & " ! " % " & #

? * & " & * " & " % #

! " % & ! " % " & 2 #

callocf

ler distn printf

sqrt

free

calloc

d

d

d A, B, n

A n A n A

main

5 5 9 = < = < : <

> ! & ! & " ! & " " " " $ " % $ 0 2 #

! & " % " & ) ! & & & & % $ 2 ! & 2 % $ " #

& & % & & ! & ! * & ! & # ! & $ & & % 3 $ " $ " # & & % $ ! & % & " & # % 3 " " * & " & % $ " & " " ) " " & " " % - 0 & . ! & #

2 3 & & ! " & " & " " & & " # & & & 2 $ & " ! 0 #

! & 2 % 0 & " & ! & & * " & $ " " " " " " #

! & * " " ! * " " & (

− + ! & " & ( , 2 % & & " )

− ( & & * & " & /

− ? ( & & * " ! ! /

− + " - & & . ( & & * & ! & % /

! & * " " $ $ ! & * % 0 "

$ & ( & " & % #

5 5 4 5 < 9

! " & " & " $ $ & " $ 2 & # > & " & " & " & % " & 0 " ! " * * & " & #

! " & - & " * % & ) * * ' . 2 * & " & # > & " & 2 " & " # " & " % (

> & /

+ " & ) $ % & 0 % ! " /

+ " ! " % * ! & ! " * 3 #

" & & " & ' ! & " % 2 #

, & " ! $ * $ 3 & " #+ & " & * " " ! " % " % " " & 0 * ! " % " $ * % " # ? (

& ! $ " & $ 3 " ! " $ & " $ $ & # " * ! " % 3 % * " " ! " #

$

" ! " 3 " & 0 ! & " " ! " / ? $ 0 $ " " & " ! " % #

> & " $ " $ " ! " & " ! % - " " & . " ! " * & " & " # + " & " ( $ $ & " & " # + ! " & & " " " & $ " $ & & " #

" & ! " # 3 $ ! " * & " & & " " " ! % ) #

5 5 7 5

< =

& % " 2 " " & " " " ! " % ( " ! " & " 2 " & ! ! " # & % 0 " & % ! " & " #

> & % $ " & & " $ % ( ! " & " $ * " & $ & " & & " $ & " $ $ ' & & " & " # & % & " & " & " $ " $ " ) ! & & % & & 2 ! & " % " & " " ! " %

" ! "

& # " * ! " % & & % & " & " " % & & " - " . " 2 #

? " " * ! " ! " & # " ! ! & % " 0 & " #

5 5 < = : = < <

) & & & 0 & * & " " " $ $ #

" & ) & & $ * & * $ " & (

& /

" " " &

? 3 ) & 2 " " " " " " #

9 : : : : 9 : " & 2 '

) ' * " ! " " & 0 ! " 2 & ) * 0 " & 0 #

9 : 9 9 ! " " ! " % " & "

! " % # & " $ ! " " ! " " # ! " ! " % " ! " & & " ! " % # & " $" $ ! " 3 #

< = : : : < < : : : < ! " % " %

! " % * " ! $ " & " * " ! " % $ " & 0 #

5 5 <

9

" 3 & 3 & " & " & & " #

3 & " & ? & " - . ! " & " " $ " " ) & " $ & ! # $ #

+ 3 & " & " " % % # , % 3 ! % * " " & 0 ! # & " $ " % " ! & " ! # " & % & ' & ! 3& " # $ " % 0 * % #

3 & " & ? & " $ * 2 " 3 ' & " #

, 3 & " % 3 & % & * " & % # " & $ " $ & " * % ! & * " ! " % 3 & # ? $ & " ! " % " $

y = log(x)# 3 & " % * 0 " & " !

3x>0

# 3 & " % " ) & * 0 " 0 ! 2 ( & " ! " %

log# & % ) &

" & " ( " & - * & " * ! " % * " 3 . $ & - * & " * ! & . # % # 2 ' # " * & " & ' ) ! & " #

, ' & " % 3 & % & ! & ' & % # " & $ " $ & " * ! " % " ! 2 ' " # & ' & " %

ey==x, "

e

3 & " " & " " " # * " 3 " ' & " %

& & #

! " % 3 ' & " ! " % & ! " % " ! " % & " - ! " * 2 . # > & " " (

"Eu, função fulana de tal, comprometo-me a fornecer um

estado final em que a pós-condição está satisfeita, se

e só se for chamada com a pré-condição satisfeita"

& " & " " % ! ! $ " % ! " % ! & 0 & " * * ( " & % #

1 & " & & " " & ' * 2 #? 3 & " ! * ! " % & * " ! & & " $ 3 ! " " & ! & 3 ' & " #? 3 $ 2 $ 3 " & & " 0 " & ' * " & & " # ? (

x = a*a + 1; /* x > 0 já que é a soma de 1 com uma quantidade positiva ou nula */

y = log(x);

, " & & " 3 " ! & ! & % & ' ! " $ & " * " & $ # , 2 * ! " % * 3 & " % 0 ! $ " % 0 " & " & ! " % #

* & 3 & ! " " " " " * $ $ & 3 " #

> " " (

? & & & - & * ! " % 0 " & & " " % & ! & " * ! " % 0 * ! 2 . /

& & " % /

% #

* & " & 3 & " ! " - ! " & & " . $ $ ! " & " & % ! ! # " * " % 0 2 0 * " 2 ! # ? $ " " ! % 2 0 * " #

% % ! " * " ) $ " " #

+ (

> & ! " % 0 * 3 & " % 0 ! /

% & % % 3 " " /

% 3 & " % 3 " " & " - ! " % * ! 2 & . /

, % ' & " % 3 " " ' ! " % /

* & $ & " & ! " % ' & * & # > & ' ! " % $ " & " & " 0 $ 3 " (

/* Retorna o item do primeiro nó do argumento, list.

Pré-condição: list != NULL */

type lsthead(link list)

return list -> item;

* $ ! * " ! " * " " &

str$ & " " & " $ * % " ! $ * " ! "

* " " & lst

#

> " 2 & " ! & % " $ " " & % # + & " 0 ! " "

assert.? & " " ! " % " $

& (

#include <assert.h>

type lsthead(link list)

assert(list != NULL); /* ou simplesmente assert(list); */

return list -> item;

% " & assert

! $ 0 0 " & " & % ! & " * ! & % # ' $ ! & % % 0 & & &

#define NDEBUG

" #include <assert.h>.

5 5 < : =

# " * % * " & & '

# .

" 2 % ! " % & " % & # ? *

.

? " % "

# " # ! * & " " *

10. As listas ligadas revisitadas

! " * " ! & & " " & $ $ " $ & " ' 3 , "

NULL#

" ! " " 3 0 - 0 . * 2 0 # ? * ) & " & " " 2 " & ' #

$ " ! " ! & " # , " % # $" &

sllist.h$ " % # & $ " &

sllist.c#

! & sllist.h

& " ! & ! " " # ? $ " ! & 0 " & ) * & " ! " " & # + " ! % " & $ ! " % $ & " 0 & (

• & % ! " ! " % /

• " " ! & /

• ? 3 ' & "

• + &

+ & ' & (

• > ' - " $ " " . ! " % #

! & sllist.c

0 $ ! " % $ 3 ! " % $ & & " 0 & " ! # + " ! % " & " $ & 0 (

• & % ! " ! " % /

• " " ! & /

• ? 3 ' & " /

• + &

• " " " % $ & " * " % " /

• + " " % /

•

o ? & % $ 0 " % $ " /

o ? 0 3 ! & #

4 5 4 5 9 < < < : =

! & (sllist.h

" ! & " " / " & 0 " ) sllist.c

typedef int type;


struct node type item; link next;;

/* PRE: plst != NULL

POS: Retorna o item do primeiro nó da lista argumento, apontada por plst. */

type lsthead(link plst);

/* Altera o valor do item do primeiro nó da lista identificada

pelo argumento plst, com o valor do segundo argumento t.

PRE: plst != NULL

POS: plst->item == t */

void lstsethead(link plst, type t);

/* PRE: plst != NULL

POS: Retorna a cauda da lista referida por plst. */

link lsttail(link plst);

/* Verifica se uma lista está vazia.

POS: Retorna 0 se plst != NULL, retorna 1 caso contrário */

int lstempty(link plst);

/* Retorna o comprimento de uma lista identificada por plst,

i.e., retorna o nº de nós da lista. */

int lstlen(link plst);

/* Insere um nó à cabeça dada lista identificada por ptr_link. O item do nó

inserido tem o valor t.

PRE: ptr_link != NULL

POS-CONDIÇÃO fraca: *ptr_link != NULL

POS-CONDIÇÃO forte: *ptr_link == newnode, onde newnode é o nó criado para

guardar o valor t.

Excepção: Se não houver memória suficiente para criar um novo nó, a função

escreve uma mensagem de erro e aborta o programa.

void lstinsert(link *ptr_link, type t);

/* Retorna um link para um novo nó. O novo nó tem como item o valor do argumento

t e como next o valor NULL.

POS (fraca): o valor retornado é != NULL.

Excepção: Se não houver memória suficiente para criar um novo nó, a função escreve uma

mensagem de erro no stderr e aborta o programa. */

link lstnnode(type t);

/*Troca as caudas das duas listas argumento pl1 e pl2

PRE: (pl1!=NULL) && (pl2!=NULL)

POS: pl1->next = lsttail(old pl2);

pl2->next = lsttail(old pl1); */

void lstswaptail(link pl1, link pl2);

/* Remove o 1º nó da lista identificada pelo argumento plink,

libertando o bloco de memória respectivo.

PRE: (plink != NULL) && (*plink != NULL)

POS: *plink = (old *plink)->next */

void lstremovehead(link *plink);

/* Remove todos os nós da lista; liberta toda a memória que a lista utilizava.

A lista é identificada por p_link, um ponteiro para link.

PRE: plink != NULL

POS: *plink== NULL */

void lstremove(link* plink);

+ & & " " & " 0 #

, 3 " - ) " & " . * & & % $ * " ! " % * & " & 2 * % " $ $ * " ! " % 3 & & 3 & " % ! $ 2 * 3 $ " % 3 & 2 " & ' & " % ! # , 2

& " & & % 3 " ! & " & ' " ) ! & % #

! " 2 <nome>

# + 3 " ! & 0

<nome> " ! " % & # >

" % ! 2 " " " $ 3 & " " % * #

4 5 7 5 < < 9 < 9 ; < = : =

#include "sllist.h"

#include <stdlib.h>

#include <stdio.h>

/* Descrição: Retorna o item do primeiro nó da lista argumento, referida por plst.

Estrutura de dados usadas: Não se aplica

Algoritmos usados: Não se aplica

Argumentos: plst – ponteiro para o primeiro nó da lista;

PRÉ-CONDIÇÃO: plst != NULL

Primeira versão: <nome e email do programador> - <data>

Alterações:

<Descrição> - <nome e email do programador> - <data> */

type lsthead(link plst)

return plst -> item;

/* Altera o valor do item do primeiro nó da lista argumento plst,

com o valor do segundo argumento t.

PRE: plst != NULL

POS: plst->item == t */

void lstsethead(link plst, type t)

plst -> item = t;

/* POS: Retorna a cauda da lista referida por lst.

PRE: plst != NULL */

link lsttail(link plst)

return plst -> next;

/* POS: Verifica se uma lista está vazia.

Retorna 0 se plst != NULL, retorna 1 caso contrário */

int lstempty(link plst)

return !plst;

/* Insere um nó à cabeça da lista identificada por ptr_link. O item do nó

inserido tem o valor t.


POS-CONDIÇÃO fraca: *ptr_link != NULL

POS-CONDIÇÃO forte: *ptr_link == newnode, onde newnode é o nó criado para

guardar o valor t.

Excepção: Se não houver memória suficiente para criar um novo nó, a função

escreve uma mensagem de erro e aborta o programa. */

void lstinsert(link *ptr_link, type t)

link tmp = lstnnode(t);

tmp->next = *ptr_link;

*ptr_link = tmp;

* $ & " 0 * & " & " ! " " ! " % lstinsert

& & " " % 0 link

$ link*

# & " & * 3 " & 0 " " ' & #

link lstnnode(type t)

link tmp = (link) malloc (sizeof *tmp);

if(!tmp)

fprintf(stderr,"lstnnode: Mem. insuf. \n");

exit(1);

tmp -> item = t;

tmp -> next = NULL;

return tmp;

/* Remove o 1º nó da lista identificada pelo argumento plink, libertando o bloco de memória

respectivo.


POS: *plink = (old *plink)->next && o 1º nó da lista foi libertado */

void lstremovehead(link* plink)

link tmp = *plink;

*plink = (*plink) -> next;

free(tmp);

/* Remove todos os nós da lista; liberta toda a memória que a

lista utilizava. A lista é identificada por ptr_link, um ponteiro para link


POS: *ptr_link == NULL */

void lstremove(link *ptr_link)

while(*ptr_link) lstremovehead(ptr_link);

/*Troca as caudas das duas listas argumento pl1 e pl2.

PRE: pl1 != NULL; pl2 !=NULL

POS: pl1->next = lsttail(old pl2);

pl2->next = lsttail(old pl1); */

void lstswaptail(link pl1, link pl2)

link tmp = pl1 -> next;

pl1 -> next = pl2 -> next;

pl2 -> next = tmp;

! " # $ % $ & ' ( )

% # * #

+ " $ " # % $ & ' lstswaptail

,

/* Retorna o comprimento de uma lista identificada por plst,

i.e., retorna o nº de nós da lista. */

int lstlen(link plst)

int n=0;

for( ; plst; plst=plst->next) n++;

return n;

# ' ! " # $ $ $ $ $ " % % *

" % # ( + " $ $ #

" # # $ $ % * ,

Uma lista simplesmente ligada é uma ligação nula ou

uma ligação para um nó que contém um item e uma

ligação a uma lista simplesmente ligada.

$ & " % # $ # " $

" # $ $ % * ( " % # & ' % %

$ $ # " $ " # $ $ % * ( (

# * % " ( # ' * " # % & % " $ % $ ( & ' " #

% % (

/* Versão recursiva */

int lstlenr(link plst)

if (lstempty(plst)) return 0;

else return 1+ lstlenr(lsttail(plst));

/* Liberta a memória de todos os nós da lista – versão recursiva */

void lstremove( link l)

if (!l) return;

lstremove(l->next);

free(l);

;

/* Percorre a lista do princípio para o fim aplicando em cada nó a função passada como

segundo arguemento */

void lsttraverse( link l, void (*visit) (link))

if (!l) return;

visit(l); ou (*visit)(l);

lsttraverse(l->next, visit);

;

$ $ & ' " % ' $ $ #

% % & " $ ,

void f( link l )

printf(printstring, l->item);

printf(“\n”);

;

% * $ $ " ,

int main()

link l=NULL;

/* … */

lsttraverse(l,f);

return 0 ;

;

& # $ * # * $ " $ % * & '

f " $ % " ! " # % " # ( + * %

g & ' (

#include “sllist.h”

void g()

link list=NULL;

lstinsert(&list,1); /* */

lstinsert(&list,3); /* */

lstprint(list);

lstremove(&list);

" % " $ & ' g

% % " $ & ' f

" $ (

* " $ " g

# * f

# % # % $ % & $ # $ % $

" % ! $ $ " $ * $ $ # ( * # $ $ " $ ( # # $ * " # ( * # & ' $ # % #

" # & ' $ " & # # $ & '

& ' $ % & * " " % & $ # $ (

* " # % #

& ' % & # " #

# $ # ,

+ "

# & ' ,

lstinsert(&plst,2);

# $ $ & ' * " $ " # % # # $ (

# % * # # & $ #

" & $ $ $ $ " % # $

% & " % $ (

! " # * " # % # $ $ & ' " # % & ' # (

" # & ' $ $ " # , # l

% % # out

$ ' $ $ $ $ (

* % # & % & $ # $ " % l

" % $ " # # max

% % * * # ! ( $ *

max$ #

l $ $ $ $

max % &

$ out

(

& ' % & # " #

# $ % # ,

+ "

# & ' ,

lstinsert(plst,2);

! " # $ % ,

* max

$ # # & ' $

% $ * # * " " $ $ max

(

& ' % $ (

: l!=NULL

) max

* % & $ # ' & ' NULL

link lstfindprevmax( link l)

link prev=NULL, max=l;

while (l->next)

if (less(max->item, l->next->item))

prev=l;

max=l->next;

l=l->next;

return prev;

# % $ & ' ,

% $ % " $ # $ $ & ' ,

link lstselection( link l)

link prev, max, out=NULL;

while (l)

/* Aqui a pré-condição de lstfindprevmax é garantidamente satisfeita */

prev=lstfindprevmax(l);

/* Move o nó max da lista de entrada … */

if (prev)

max=prev->next;

prev->next=max->next;

else /* o max é o primeiro da lista */

max=l;

l = l -> next;

/* … para a lista de saída, out */

max->next=out;

out=max;

return out;

" ! " # $ # % % # " # # $ ( "

$ # $ " " % ( " " NULL

(

& ' $ * % & $ # " $ " $

% $ ,

* % " " * ' % % & ' $ " % $ # %

( # % * % " $ % # plist

" ' " " " # (

# % * & ' ,

! % " # " %

" " # % % # # " $ % $ $ "

# ( % $ # $ $ " $ * '

$ * (

" # & ' " * # " & ' $ * # % % #

" # # $ ,

/* Insere um novo nó identificado por pnode numa lista circular simplesmente ligada,

imediatamente a seguir ao nó identificado por plink_last. plink_last é um ponteiro para link,

que aponta para o “último” nó da lista.

PRÉ: (pnode!=NULL) && (plink_last !=NULL) */

void clstinsert( link *plink_last, link pnode)

if (! *plink_last) /* lista vazia */

*plink_last=pnode;

pnode->next=pnode;

else

pnode->next=( *plink_last)->next;

(*plink_last)->next=pnode;

# * $ " $ $ " & ' $

% $ % $ * $ " & " * $ $ & '

clstinsert(

void clstinsert( link *plink_last, type t)

link pnode = lstnnode(t);

if (! *plink_last) # *

*plink_last = pnode;

pnode->next = pnode;

else

pnode->next=( *plink_last)->next;

(*plink_last)->next=pnode;

/* Retorna o comprimento de uma lista circular simplesmente ligada */

int clstlen(link plist)

int n=0;

link tmp=plist;

if (! plist) return n; # *

do

tmp = tmp-> next;

n ++;

while(tmp != plist);

return n;

& # # % % # ' $ ! $ % ! % % (

) $ % # & " " % %

# $ $ $ $ # % # ( ! " #

" & $ " # ! * & ' % $ $ $

" % " % " $ # # %

# $ " # # $ (

" % # % % # $ " # # $ (

" " $ # " $ " # $ $ ,

typedef int type;

type struct node *link;

struct node

link prev;

type item;

link next;

;

/* ou

struct node

link prev, next;

type item;

; */

# $ " # # $ ' % $ % % # (

% % # ' * % " # $ # pn

,

pn == pn->prev->next == pn->next->prev.

$ * $ " $ $ # % " " $ $ $ % # % # $ $ ( # $ # $ " # # $ " * # $ # "

% $ " " " (

# $ " # # $ $ " # % " & % " $

# " " $ " # % $ " # & $ # " % $

" & ' % (

$ % " $ & & #

$ " # # $ ( $ & # $ " # # $

% & " % * & ' " dllst

(

/*Remove de uma lista duplamente ligada o nó referido por pnode;

PRE: pnode != NULL */

void dllstremove(link pnode)

pnode->prev->next = pnode->next;

pnode->next->prev = pnode->prev;

free(pnode);

/*Insere o nó referido por pnode à direita do nó referido por *ptr_link

de uma lista circular duplamente ligada

PRE: (ptr_link != NULL) && (pnode !=NULL) */

void dllstinsertright(link *ptr_link, link pnode)

if(! *ptr_link) /* lista vazia. Depois da inserção temos a configuração da figura*/

*ptr_link=pnode;

pnode->next = pnode;

pnode->prev = pnode;

else /* lista tem pelo menos um nó.Ver figura abaixo. */

pnode->next = (*ptr_link)->next;

(*ptr_link)->next = pnode;

pnode->prev = *ptr_link;

pnode->next->prev=pnode;

(

# & $ $ # " # # $ $

% $ $ & ' # * # ( $ $ * % " " % " $ $ $

(

(

% * & ' % $ # " #

# $ % # # " " " " ( & ' % %

" % $ & $ " $ % $ ( "

% " " % $ & (

% * & ' % $ ! #

" # # $ % # # " " " " (

(

" # * ' % * $ & ' * $ $ % $ (

& '

/* Remove o 1º nó da lista identificada pelo argumento plink,

libertando o bloco de memória respectivo.


POS: *plink = (old *plink)->next && o 1º nó da lista foi libertado */

void lstremovehead(link* plink)

(

% * & ' " % % " " $ % $ $ * # * " " %

" # $ ( * $ % $ ( % # %

" " % $ & $ & ' (

(

$ % $ $ (

" # * * % * $ & ' ,

/* PRE: plist != NULL

POS: mostra no ecrã todos os valores dos nós da lista plist. */

void lstprint(link plist)

% * & $ # $ & '

lstapply

" % # % $ " & ' % $ % " " ,

void lstapply (link plist, void (*fn) (link, void*), void *arg)

$ plist

" " % & $ # fn

" " & '

" # % % $ & ' % $ % "

plist

$ arg

(

%

# & ' lstapply

$ # " " # & ' ,

int lstlen(link plist) $ $ # " $ "

plist(

$

% * & ' * $ * # $ # " #

$ (

(

" # & ' $ $ & ' " # # $ $ # ,

%

(

% * & ' % * % $ # % % # " #

# $ ( % # % " " % $ & $ & ' (

(

" # & ' % ' $ $ $ " $

# % % # (

(

% * & ' $ $ " " $ # % % #

" # # $ * (

( " # & ' * & ' % * % $

# % % # $ " # # $ $ " # * % #

$ $ " # * (

( " # & ' $ $ % $ " "

# % % # $ " # # $ (

( $ # % % # $ " # # $ ( % $ $ # !

" " $ & * % * ( + $

$ % $ # ( % # % " " % $ & $

& ,

+ $ " " * $ $ # (

+ $ " " $ # " " *

# % " ! % $ " (

%

+ $ " " $ # " " & ' pf

int % % " " *

$ $ # " & ' " $ " pf

* # $ $ (

$

+ * # * " " # # $ % % & ' $ $

# $ $ % (

( $ # " # # $ %

n $ % $ $

" $ " $ ( $ $ ' ,

l# "

c% # ( + * # * " % # % # $

" n-1

% # % # $ # n

( "

1 $ * % # $ # % * # (

$ $ * $ % $ $ $ ( " $ * % # $ $ * % % " $

$ * # $ n

l

c( ! " # % $

% " % # " # # $ % $

" $ " $ # " % # % $ "

% # # $ $ (

( * $ % $ # * " % * % % $ " # ( " $

% " $ $ % $ % # % % % # # % $ % $

% ( " % # " % " % * $

% " % # " & ' $ % % # # $ (

% " & ' $ * * # # $ % $ &

% " # $ " (

+ * # * " # # & ' $ % $

# & ' $ " # $ " ( # & ' ! "

$ " % % # $ # $ " * " & ' $

% ( % % & $ * $ $

# $ ( " % $ " % " (

% $ " " $ " % % %

$ ( " # $ $ $

" % (

" $ * % " % " " * ( " $ * # # % % # $ % $ " $ % $ " ( " # $ % $ * $

% $ & # " " # & ' $ " $ # (

+ ! % & ' " $ * $ $ "

* ' $ # $ ( " $ * $ % * * (

! " # ,

"

* * ,

" " $ ,

" % $ $ " % % $ $ ! % % ( ( ! % % ( % % #

11. Tipos de dados abstractos

$ $ " % $ % % # $ * # * $

" % % $ $ % # # $ $ " $ $ $

" & ' $ * # $ " (

+ % # * $ " # * # $ " * $

" & & " $ " # ( ) " # *

" & $ * # * # $ % # ' % $

# % $ $ $ % $ " $ $ $ $ % # & ' $

& ' # $ (

" $ $ $ % $ # " # + " $ $ $ % $ * # % # % & ' $ " &

* # % * # " % # " * $ " &

$ " * % (

+ " & ' $ $ $ & " # " & '

% " # " $ $ % # " # % ( + % " % % # ' " $ * " # & ' * $ # (

# # $ " & ' $ " # % "

" ! " # % % $ " # & ' % #

" # & ' $ " $ $ $ % (

# $ " & ' ' $ " # %

! " # % " " # $ % + " * # $ * # $ * # *

" $ % $ % % % (

" # & ' $ # # $ $ $

" # % % $ $ $ " * $ & %

$ * # * ( " # % " * & $ % & ' $ % % + * % # ( $ # " & ' $ # " $ $

% $ # % % # $ # " # # $ " # $ " #

# $ ' # " " $ & ' % $ #

% $ % # (

% * & ' " # % $ # % $ # ' "

+ ( $ " # # $ & % '

$ (

% % % * # * " $ ' $ ( ! " # # *

<string.h> ' $ + * "

' " $ % % $ $ % % ( # $

" " $ % $ $ % " & ' $ $ " ( # $ ' " * # $ " & ' $ $

" # # $ # " % # (

" & ' $ $ $ * $ " * # % #

* # * $ " $ ( $ " $ #

" % # # " & ' $ $ $ $ % $ #

" " $ ( ! " # " $ " % % $ $

" % % # ( ) % % ' & $

" # & ' $ $ ! ' $ % % % " " $ * " $ ! % & ' (

+ ' % $ & ' % # " & ' $ $ $ (

% % % # ' ' % # " & ' (

* # ! " # $ + (

12. O tipo de dados abstracto pilha

" # # # ! % ! " #

# $ $ $ " $ $ $ % ( ) # " #

$ $ $ # " & ' % " & ' ( ! " #

* # & ' $ ! " % % $ " # ! " #

" ! % & ' # " # " " % $ & (

" # " $ * % % " % # $ # $ $ ( #

$ $ $ n

# n∈ IN0

" " L=(l0,l1, ..., ln-1)

$ li

0<= i<n

# ( ) # * *

n=0 " $ "

L=()(

% # $ $ & & # $

% ' $ # % # $ # " $ % " (

% " & ' * # " $ % % $ push

" & ' $ & ' # " $ % % $

pop(

$ $ % % # % ! " # $

% % % (

, " # $ " " $ ! # $ " $

% $ $ # % # % $ " # " $ ( )

% $ " * $ % $ % # ' % " ,

$ % #

" " " $ %

"

"

" " " $ " %

" +

" "

" "

" "

, % $ % % & ' " $

% % % (

+ $ % S=(s0,s1, ..., sn-1)

$ s0

# $ ! sn-1

# $ " $ $ si

% $ si-1

0<i<n

( *

# # " * $ % $ $

" # (

% * " + " % $ $ % & ' $

+ ( $ % & ' $ # % % % " &

" $ " # + " % $ & ! ( $ % & ' # $ $ ( # $ ! " # " % & '

" % % & ' " + " # ( % $ % & !

" " & " $ " % $ " * $ % " " % $ & (

" * ' $ % $ + " # $ $ % stack.h

" $

" $ % ( ) $ % * & ' # # # $

" $ & $ # * $ & $ " # & ' $ + " # % & "

STACK( # & ' $ % # $ % $ + (

/* ficheiro: stack.h */

/* Verifica se o stack está vazio; retorna 1 se o stack estiver vazio; retorna 0 caso contrário. */

int STACKempty(void);

/* Verifica se o stack está cheio; retorna 1 se o stack estiver cheio; retorna 0 caso contrário */

int STACKfull(void);

/*Cria um stack vazio com a capacidade máxima de n elementos.

PRÉ: n>0

POS: (STACKempty()==1) && (STACKfull()==0) */

void STACKinit(int n);

" % % * # ' % ( $

$ % $ $ " # " % $ & ' $ & ' % (

) * # * # $ % $ * % % " $ %

' * ( * " & ' " " " & ' $ # $ * " % $ " & ' % ' " $ % ( * & '

% " $ " # " " % $ & $ & ' (

/*Retira e retorna o último item carregado no topo do stack.

PRÉ: STACKempty()==0

POS: STACKfull()==0 */

type STACKpop();

/* Devolve o elemento no topo do stack; Não altera o conteúdo do stack.

PRÉ: STACKempty()==0

POS: STACK == old STACK; em que STACK representa o estado do stack. */

type STACKtop();

) * $ * # % % % % %

" & " * * # ( ( ' % ( " $ * # %

% $ % ' * * # " $ % (

* & ' % " $ " # " " % $ & $ & ' (

/*Carrega o item t no topo do stack.

PRÉ: STACKfull()==0

POS: (STACKempty() == 0) && (t==STACKtop()) && (STACKpop() == old STACK),

em que STACK representa o estado do stack. */

void STACKpush(type t);

% * " + " % " $ % %

$ % & ' ( $ $ % * + * $ " % % & ' ( ( * $ $ % & ' # % " # ( + " $ * #

" % % & ' $ + $ " # % # ,

( $ * $ $ % ( $ % * " $

" % % (

(

" & $ % * $ % $ $ " & $

+

(

! $ % * " " $ $ # $ " &

(

% $ & $ % * % $ & $ " # % & ' $ % $ " & ' (

% $ % ,

( ,

Stack[G] - + % $ % " $ " % % % $

% " * # $ " % G

(

( " & ,

( ( init

,IN stack[G]

( ( empty

,stack[G] 0, 1

( ( full: stack[G] 0, 1

( ( push

,stack[G] x G stack[G

( ( pop

,stack[G] stack[G]

( ( top

,stack[G] G

$ 0

" # 1

" * $ $ ( % $ $ & '

" % # & ' ' $ $ " $ # $ % $

" $ ( " # * & ' " % $ & ' % $ (

! " # " & ' push

$ % % " # % & ' $ $

$ % $ $ $ " $ % $ stack[G]

$

# % G

stack[G].

" & % $ $ % # ' ' % % $ % # & ' ,

f: IR IR

& ' f

& ' # $ * * # # " % % $ $

& ' ( + % % % " & $

! " % $ & (

( ! , $ n∈ IN, x∈G

s∈stack[G]

( (

top(push(s,x))=x

( (

" " " !

( (

"

( (

# #

3.5. empty(push(s,x)) = 0;

3.6. full(pop(s)) = 0;

! ( ( ! " " " $ $ $ # $ %

" # % $ & ' # " (

( % $ % , $ s∈stack[G]

x∈G

( (

pop(s)

empty(s)=0; ( (

top(s)

empty(s)=0; ( (

push(s, x)

full(s)=0;

% " % $ & ' $ & ' f

" $ * % & '

% % % $ $ $ f( & ' % % % $ %

A $

% X,

A,

& ' # A: X 0, 1

# A (x)

1

x∈A

0

% % (

# & ' ! " " ! " % (

& ' ! " $ % # % $ $ " $ % (

# * & ' ! & ' ! ( & ' % $ " $ % # % $ " " $ % ( & ' ' $ $

% & $ $ % $ " $ (

# ! # ! " * # % $

& ,

% %

% % % $ % $

" % % " # $ % * & ' ! & '

! % " ,

(

# % " $ " &

(

* " $ " $ $ "

(

* $ " (

" # # " % * # % $ ! " $ $ #

(

* # & ' $ ! " ' & ' ! " % ! " '

$ $ " $ % # % $ " $ % % $

" $ ( $ " $ % $ % " $ %

% " $ $ " $ % " & ' * # % # % # $

% ( # " % " ! " '

$ $ * # * % # % # $ % $ % $ % & '

! " $ " " & % ( % ! " ' % % # % # $ $ * "

% " ,

! " # $ % " " $ $ " % # % # $ $ * # * (

,

,

,

,

,

,

,

,

,

& # " + % " " # % # % # $

% $ % % # $ % $ & ' # $ * # $

# $ % $ ( ) % * " $ " # % # % $ % % * % % % " $

$ " & " $ ' ' $ " $ $ %

" & ' # $ # $ % # % $ % (

$ % & ' $ % $ " " $ $ % " $ $

( # " $ % * ( # $ * ! " # $ # & ' $ " $ $ ( # $ " " & ' $ % $ $ % &

" (

$ $ % # " " " $ ,

$ % % $ % & ' " % " #calc

%

" $ & le

avalia

escreve

( # $ % & ' avalia

% % $ % # $ " $ $ $ * % & ' $ % $ & '

& procNo

procOp

(

! " ! " $ & '

$ % $ ( " # % % " $ & ' escreve

" $ ' " # printf

( ) printf

" $ "

$ & ' # ( % (

+ % $ % $ * # printf

$ * % * * # res

( * #

" $ $ & ' procOp

$ " & ' avalia

c # %

" * * printf

( ) % # printf

procOp

'

% " " * # $ res

" # % % $ &

$ ( " # % & ' " $ $ $ $ (

avalia

procNo procOp

calc

le

escreve

str

no

str

op

res

res res

" $ " $ % & % *

% $ ( $ * # * " $ * % $ $ $ % " #

" # % $ % $ " $ % $ $ & '

% $ " " # $ " * % # (

" " * # ,

#include "type.h"

#include "stack.h"

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

#define MAXLEN 20

#define MAX_STACK_SIZE 10

#define ENDCHAR 'q'

void le(char *, int);

void avalia(char *);

avalia

procNo procOp

calc

le

str

no

str

op

void procNo(type);

void procOp(char );

int main()

char str[MAXLEN];

printf("Calculadora para expressões aritméticas em notação sufixa.\n");

printf("Características: \n");

printf(" - Operandos: inteiros \n");

printf(" - Operadores: +, - *, / \n\n");

STACKinit(MAX_STACK_SIZE);

for (;;)

le(str, MAXLEN);

if(str[0] == ENDCHAR) break;

avalia(str);

return 0;

void le(char *str, int n)

printf(": ");

fgets(str, n, stdin);

/* Verificar aqui se str está num formato válido */

void avalia(char *s)

if(isdigit(s[0]))

type t = (type) atof(s);

procNo(t);

else procOp(s[0]);

void procNo(type no)

if (STACKfull())

fprintf(stderr, "Error: STACK overflow. \n");

exit(1);

else STACKpush(no);

void procOp(char op)

type res, o1, o2;

if(STACKempty())

fprintf(stderr, "Error: STACK empty. \n");

exit(1);

else o2 =STACKpop();

if(STACKempty())

fprintf(stderr, "Error: STACK empty. \n");

exit(1);

else o1 =STACKpop();

switch (op)

case '+': res = o1 + o2; break;

case '-': res = o1 - o2; break;

case '*': res = o1 * o2; break;

case '/': if(o2) res = o1/o2;

else

fprintf(stderr, "Error: divide by zero; finished. \n");

exit(1);

break;

default: fprintf(stderr, "Error: unknown command. \n"); exit(1);

/* Aqui existem pelo menos dois lugares vazios no stack */

STACKpush(res);

printf(printfstring, res);

printf("\n");

printfstring

$ % # & ' $ printf

( % $ "

type ' $ $ %

type.h( *

% $ $ % " $ ,

typedef int type;

#define printfstring "%d"

# type.h

% # $ % $ $

" % # % $ $ " # & ' $ % $ * " *

% # # " # ( " % $ * $ % # & # " # ,

#ifndef _TYPE_

#define _TYPE_

typedef int type;

#define printfstring "%d"

#endif

$

#ifndef

#define

#endif

' % $ $ % * $ " " % $ ( " " % $ "

$ " $ $ % " # $ ( " " % $ " # # $ # % " % %

# $ % * (

) <identificador>

' * $ $ $ % * #ifndef <identificador>

% $

% $ % $ $ $ % * ,#else

#elif

#endif(

% % # ' " $ $ " $ * # * $ $ " % $ + % ( + $ * # * '

* $ % % $ # $ " # & ' $ %

% % " % & ' $ % # % # $ (

! * " & " # & " * " + %

" " ( * # $ %

" * (

" & ' " * # % $ % $ ,

* % % % " & & $ # $

$ # % " ( " " # $ % # # $ "

" $ % , % & % $ $ % $ * &

& % & $ % $ " $ " %

" $ " $ $ % " $ % $ ( ) $ $

& $ & ' & ' % & $ * # * $ % # % & $

% $ % " $ % (

) % & & " % % $

$ % $

" " # & ' % $ ! ' .c

% stack.c,

% $ & $ $ % " $ % $ ,

#include <stdlib.h>

#include "type.h"

#include "sllist.h" /* Funções que definimos sobre as listas*/

static link pstack = NULL;

static int capacity; /* capacidade do stack */

static int actsize; /* tamanho actual do stack */

/* Inicializa um stack, com capacidade para n elementos.

PRE: n > = 0

POST: (STACKempty() == 1) && (STACKfull() == 0) */

void STACKinit(int n)

pstack = NULL;

capacity = n;

actsize = 0;

;

/* Retorna 1 se o stack está vazio; retorna 0 caso contrário. */

int STACKempty(void)

return !actsize;

/* ou return pstack ==NULL */

;

/* Retorna 1 se o stack estiver cheio; retorna 0, caso contrário. */

int STACKfull(void)

return (actsize == capacity);

;

/* Retorna e retira o último elemento inserido no stack. */

/* PRE: STACKempty()==0 */

/* POS: STACKfull()== 0 */

type STACKpop(void)

type item = lsthead(pstack);

lstremovehead(&pstack);

actsize--;

return item;

;

/* Retorna o último elemento inserido no stack; Não altera o estado do stack.

PRE: STACKempty()==0

POS: STACK = old STACK; onde STACK representa o estado do stack. */

type STACKtop(void)

return lsthead(pstack);

;

/* Carrega um elemento do tipo t, no stack

PRE: STACKfull() == 0



void STACKpush(type t)

lstinsert(&pstack, t);

actsize++;

;

* " # * static

* * # # % # & '

" " * % $ $ * * # % $ % * & ' (

$ " # % $ * * ! * * $ $ $ #

& ' " # * % * static

# # % % $ * * # $ % $

% $ $ $ % # $ ( " # % $ & $ $ %

static(

" # * % * static

" " % $ % $ !

$ % $ ' $ $ (

" & ' " % $ % (

" ) % % % " % $ $ " # $ $ " & '

# $ (

" # & ' $ " & ' % " $ $ $ " ,

#include <stdlib.h>

#include <stdio.h>

#include "type.h"

static type *pstack = NULL;

static int capacity;

static int actsize;

/* Inicializa um stack, com capacidade para n elementos.

PRE: n > = 0

POST: (STACKempty() == 1) && (STACKfull() == 0) */

void STACKinit(int n)

pstack = (type *) malloc (n*sizeof *pstack);

if(!pstack)

fprintf(stderr, "Error in STACKinit: not enough memory\n");

exit(1);

capacity = n;

actsize = 0;

;

/* Retorna 1 se o stack está vazio; retorna 0 caso contrário. */

int STACKempty(void)

return !actsize;

;

/* Retorna 1 se o stack estiver cheio; retorna 0, caso contrário. */

int STACKfull(void)


;

/* Retorna e retira o último elemento inserido no stack. */

/* PRE: STACKempty()==0 */

/* POS: STACKfull()== 0 */

type STACKpop(void)

return pstack[--actsize];

;

/* Retorna o último elemento inserido no stack; Não altera o estado do stack. ,

STACKempty()==0

) ,

STACK = old STACK; $

STACK " $ $ (

type STACKtop(void)

return pstack[actsize-1];

/* Carrega um elemento do tipo t, no stack

PRE: STACKfull() == 0



void STACKpush(type t)

pstack[actsize++] = t;

$ $ " # % $ % $

% & " % $ $ $ & " (

" ) % % % " % $ $ " # $ $

" & ' # $ (

* " $ " & ' $ % # & ,

static type *pstack = NULL;


static int freespace; /* Número actual de posições desocupadas no STACK */

! " # freespace=3

( + ! % ! % % " # & ' $ &

" " # & ' $ % " & ' (

$ " # & " % $ % ( $

" # & ' " % " # " % # %

stack1.c

stack2.c % $ # # & ' "

% # ( * % " % # " $ " # + % ' " # & $ % (

$ & " # & * # $ $ " (

) * " # % & ' % push

pops

" $

% % * ' " # & ' % " * # * ' % * # " % $ $ # " & (

# $ * # % " & $ $ $ % (

+ " " % $ $ % % $ $ $ $ #

! $ " * # " # & ' $

# # $ (

" # & ' $ " # & '

$ # " " # " & pop

push

" % (

" # & ' $ # " $ $ # ' $ % " $ % %

$ $ ( " % ' " * # malloc

% "

NULL $ ' * $ " * # (

# % # $ $ $ # & ' $ % # % # $ % *

# % & ' ! & ' # (

$ * # * % * $ & ' ! " & '

! (

) " % in2post

' $ * " % " ,

> in2post 1 + 2 * 3 <enter>

1 2 3 * +

> in2post 1 * 2 + 3 <enter>

1 2 * 3 +

# $ % * ' & ' ! ! * " % % * ! ! " ' " % $ * (

# % $ * & ' $ " $ '

" $ # $ " # $ % " % ! " ' # % $

$ ( # $ " % $ " $ # $ $ " $ $

" % $ % ( ! " # % * ' $ ! " ' 1+2*3

" % " # $ ( % " # & % # %

" $ % (

% ! " # " # " % " # $ % $ " (

! " # ,

$ $ # ,

$ ) % ,

$ $ % $ " $ " " $ " ) $

% $ ! " ' # % $ $ ( ) $ $ # $ ! " '

" $ $ ' " $ $ % # % $ $ ( $

% " $ % # % $ % ( $ $ " " $

$ # " % $ " $ ( $ %

" $ % " " % $ % % " % $ % $

" $ % ( ! " # % +

" % $ % $

* % " & ' " $ # $ " $ (

+ *

$ $ % " $ +

% # % $ % "

$ " $ (

! " # ,

$ ) % , ) $

+

% # % $ % # % ( $ % % # $ *

% # % $ % ( *

" % $ % # *

$ $ % " $ (

$ % $ $ ! " ' # % $ $ % # % $

$ " $ * # $ ! % (

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#include "type.h"

#include "stack.h"

#define N 10

void procOp(char);

int precedence(char );

int main( int n, char **argv)

int i;

STACKinit(N);

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

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

else procOp(*argv[i]);

while (!STACKempty()) printf("%c", STACKpop());

return 0;

void procOp(char opt)

if (STACKempty())

STACKpush(opt);

return;

if (precedence(opt) > precedence(STACKtop()))

if (!STACKfull()) STACKpush(opt);

else

fprintf(stderr, "ERROR: stack overflow.");

exit(1);

else

while(!STACKempty() &&

(precedence(opt) <= precedence (STACKtop())))

printf("%c", STACKpop());

STACKpush(opt);

int precedence(char c)

static enum precs addsub = 1, mux = 10;

switch(c)

case '+':

case '-': return addsub;

case '*':

case '/':

case '%': return mux;

default: fprintf(stderr, “invalid operator”);

exit(1);

& ' ! " # $ % $ % $ # ! * # , * #

% % " $ & ' ! $ (

& ' # # ! # $ $ $ " # ' $ " # & ' $

$ " & " * $ % # $

# * " " # " & * % (

+ $ " % $ % $ $ $

! " # , ! " ' & ' ! a*b-c+d*e-f/g é equivalente à expressão em

notação sufixa ab*c-de*+fg/-

$ $ # ,1 2 3 4 5 6 7 8 9 10 11 12 13

$ ,a * b - c + d * e - f / g

) % * * (cada linha corresponde a um estado do stack)

estados do -

stack: +

+ *

-

- / $ ,

a b * c - d e * + f g / -

# & ' % " " % ' " %

" $ % % " $ # %

! ' $ % $ " ! " % " $ ! $ % ! % % (

! " # % $ * $ % & ' " " % # * ,

" % " * # ! " & ' ! (

" % % $ " ! " ' " & ' !

$ " * # " & ' $ $ # $

% # % # $ $ * # * (

$ % # $ # & $ " $ " # & '

$ + , in2post

% calc

% $ %

$ " " $ % " " $ char

(

" # & ' $ + % ' " $

% ( % " $ " " # & ' $

+

(

% # % " & '

% % ( " % $ # $ " #

" & (

(

$ % & ! + " # " $ ( $

" # & ' $ # # $ % # " " % $ & (

STACKcount(void); /* retorna o nº de elementos no stack; */

STACKchangetop(type t); /* substitui o topo do stack por t; */

STACKwipeout(void); /* remove todos os elementos do stack; */

(

" # + % $ " % $

# # $ " " (

(

+ * # * + # % & $ % * (

(

" # % # % # $ " & ' ! "

" & +

-*/!

% # %

$ $ * ' ( $ $ $ $

$ * $ $ " ( # % $ " $ (

! " # $ # & ' ,

>calc 5 ! 2 3 * 4 % +

122

(

% * & ' * " % * % % *

! ! " ' % ' % % ( & ' "

! " ,

( (

( (

!

(

$ " in2post

" " % ! " % " (

13. O tipo de dados abstracto fila de espera

$ ! " % $ " # ( " # "

# % $ $ ( % " $ $ " (

% $ $ $ # % $ $ $ $ &

% # ' " $ * $ % $

% " # " % ( * $ " ' #

$ % $ % # ! ' % # % * $ % " $

' & $ $ " # * (

) & % $ % % ' % % ( ( " * $ $ % " $ " # + # $ "

" " "

$ $ $ % $ # ( % $ " # # * "

# $ " (

# # $ $ $ & ' $ # $ $ #

$ & ' $ # $ % ( + $ # F=(f0, f1, ..., fn-1)

f0

# $ fn-1

# $ fi+1

fi 0<= i < n-1

( #

& ' " put

enqueue

& " get (

dequeue)

(

"

"

"

% % " # " $ $ $ % ,

/* Ficheiro: queue.h */

#include "type.h"

/* Inicializa uma fila FIFO, com capacidade para n elementos.

PRE: n > = 0

POST: (QUEUEempty() == 1) && (QUEUEfull() == 0) */

void QUEUEinit(int n);

/* Retorna 1 se a fila está vazia; retorna 0 caso contrário. */

int QUEUEempty(void);

/* Retorna 1 se a fila está cheia; retorna 0, caso contrário.*/

int QUEUEfull(void);

/* Retorna e retira o primeiro elemento inserido na fila. */

/* PRE: QUEUEempty()==0 */

/* POS: QUEUEfull()== 0 */

type QUEUEget(void);

/* Insere um elemento do tipo type, na fila

PRE: QUEUEfull() == 0

POS: QUEUEempty() == 0 */

void QUEUEput(type t);

" # $ " $ # # $ $

$ # " $ (

" & put

get

" " %

& $ * # $ # & % & *

" plast

" # $ # (

/* ficheiro: queue1.c */

#include "sllist.h"

#include "type.h"

#include <stdlib.h>

#include <stdio.h>

static link pqueue;

static link plast;


static int actsize;

/* Descrição: Inicializa uma fila FIFO, com capacidade para n elementos

Parâmetros: n - inteiro positivo; indica o número max de elementos da fila.

Pré-condição: n > 0;

Pós-condição: (QUEUEempty() == 1) && (QUEUEfull() == 0); */

void QUEUEinit(int n)

capacity = n;

actsize = 0;

plast=pqueue = NULL;


int QUEUEempty(void)

return !actsize;

/* Retorna 1 se a fila está cheia; retorna 0, caso contrário.*/

int QUEUEfull(void)

return actsize==capacity;




type QUEUEget(void)

type tmp = lsthead(pqueue);

lstremovehead(&pqueue);

actsize--;

return tmp;




void QUEUEput(type t)

link nn = lstnnode(t);

actsize++;

if(QUEUEempty())

pqueue = plast = nn;

else

plast -> next = nn;

plast = nn;

lstremovefirst% # %

pqueue

NULL ' * #

# (

# " * # " # # $ (

" & $ get

put

" " % $ % , " % $ #

out " " & ' $ " * #

$ # in

(

# % % " & % $ # % % " % $ $

" # (

% * # # # $ % in

% $ % ( # # $ ! $ "

out

% out

( ) $ % ! % $ # $ ' % # $

( % % % # (

* % # * % " $ % * * #

% actsize

$ ,

% $ % # $ # (

" $ " " $ % in

out

"

* % & ( # $ " # # $ " % $

* & " % % " ! " # ' $ $ % # $ $

" # (

$ % in

out

" * % # *

% ( % $ & ' $ # * * % " in==out

! " # (

$ # * # % * " & ' " n

" n+1

# ( # % " #

# ' $ # * in==out

( ! " # ,

% # # *

"

"

"

"

/* Ficheiro: queue2.c */

#include <stdio.h>

#include <stdlib.h>

#include "type.h"

static type* queuep;

static int capacity; /* capacidade máxima da fila */

static int capp1; /* capp1 = capacity + 1 */

static int in; /* índice da posição disponível para inserção, no fim da fila */

static int out; /* índice do próximo elemento a sair da fila */

/* Função auxiliar; visível apenas neste ficheiro.

Dado um índice, calcula o índice seguinte.

Esta função só deverá ser chamada após QUEUEinit */

static int nextindex(int i) return (i+1) % capp1;

/* Inicializa uma fila FIFO, com capacidade para n elementos.

PRE: n > 0

POST: (QUEUEempty() == 1) && (QUEUEfull() == 0) */

void QUEUEinit(int n)

capacity = n;

capp1 = capacity + 1;

in = out = 0;

queuep = (type *) malloc (capp1 * sizeof *queuep);

if(!queuep)

fprintf(stderr, "Error in QUEUEinit: not enough mem for queue allocation");

exit(1);


int QUEUEempty(void)

return in==out;

/* Retorna 1 se a fila está cheia; retorna 0, caso contrário.

Quando a fila está cheia, se inseríssemos outro elemento

ficaríamos com a ilusão de que a fila estaria vazia */

int QUEUEfull(void)

return nextindex(in) == out;




type QUEUEget(void)

type tmp = queuep[out] ;

out = nextindex(out);

return tmp;




void QUEUEput(type t)

queuep[in]=t ;

in = nextindex(in);

(

% # % " & '

# $ " % ( " % $ #

$ " # " & (

(

" # + # $ " $ ( $ "

" & % % ! % " % (

$ * % & ' # % * ,

(

% $ $ #

(

ptr

prt out

14. As filas revisitadas

" $ $ $ % " # % % " " # %

# " ( #

" # % , " " (

+ " $ $ % $ " # " # % " *

# , " # * # # %

# * " (

# ' ' % " # % $ & ' " * (

! " # " # % # * , * $ # !

# % " # $ $ ( $ #

" # $ $ $ $ " ( + % # # (

$ % % # ' $ " # % $ $ " # +

' $ " $ $ % # # (

* $ # # ! " # $ " $ # $ $ # # # % " $ $ (

# # $ $ # $ $ " % " " % $

# " & ' ( " # & ! % " & %

" % (

# & ' $ $ % $ " $ % $ + ( % $

# & ' $ % # $ % $ $ $ # * # % (

# $ " # % & % # # $ " % " & $

$ # & ' $ % & (

) $ " % $ & # " % $

+ (

/* Ficheiro: rq.h – interface fila aleatória (Random queue) */

#include "type.h"

/* Inicializa uma fila aleatória, com capacidade para n elementos.

PRE: n > 0

POS: (RQempty() == 1) && (RQfull() == 0) */

void RQinit(int n);


int RQempty(void);

/* Retorna 1 se a fila está cheia; retorna 0, caso contrário. */

int RQfull(void);

/* Retorna e retira aleatoriamente um elemento da fila.

Todos os elementos têm probabilidades iguais de saírem.

PRE: RQempty()==0

POS: RQfull()== 0 */

type RQget(void);


PRE: RQfull() == 0

POS: (RQempty() == 0) */

void RQput(type t);

+ * " # & " * " # & ' $

" # $ " & $ # % " " % (

% # $ " # & ' ! ( " & ' $ %

RQput(type t) $ % * #

t $ # ( # $ $ % $ *

" & ' $ # % & ' $ RQget()

% #

# $ # % # $ " $ $ $

$ # $ $ $ (

/* Ficheiro: rq.c – fila aleatória (Random queue) */

#include <stdlib.h>

#include <stdio.h>

#include "rq.h"

static type *rq = NULL;


static int actsize;

/* Inicializa uma fila aleatória, com capacidade para n elementos.

PRE: n > 0

POS: (RQempty() == 1) && (RQfull() == 0) */

void RQinit(int n)

rq = (type *) malloc (n*sizeof *rq);

if(!rq)

fprintf(stderr, "Error in RQinit: not enough memory\n");

exit(1);

capacity = n;

actsize = 0;

;


int RQempty(void)

return !actsize;

;


int RQfull(void)


;

/* Retorna e retira aleatoriamente um elemento da fila.

Todos os elementos têm probabilidades iguais de saírem.

PRE: RQempty()==0

POS: RQfull()== 0 */

type RQget(void)

int r = rand() % actsize; /* Número aleatório entre 0 e actsize -1 */

type tmp = rq[r];

rq[r] = rq[--actsize];

return tmp;


PRE: RQfull() == 0

POS: (RQempty() == 0) */

void RQput(type t)

rq[actsize++] = t;

! & " $ % $ # % " # %

$ & ' , * # ! ( $

$ $ " " # % $ & ' $ $ (

# % " $ $ ' $ # & * # * #

" % # % # ' $

" % " $ " * ' $ # #

$ $ & ' $ " % " & $ $ $ % " ' $

$ $ (

# " # " # # $ " $

# " " $ $ " # # $ " % #

% * " $ $ $ # (

) % & ' $ # % " $ $ " & ' $ $ # '

% % $ " % $ % " $ % % "

$ & ( % " % % * ( # # % & ' $

% " " % * $ " $ $ " # % & ' ( ! " # % # % & ' $ %

& ' # % " " * % # $ $

( + " $ $ $ % * $ " # % & ' % * " $ # $

% " (

$ $ ! # & ' $ $ % * # "

# * # $ % * ! ! ! ! ( # & ' $ $ * " # * # $ % * ! ! ' ! (

% $ # % " $ $ " % $ $ % $

# ( ,

/* Ficheiro: pqueue.h */

#include "type.h"

typedef struct priority_queue *PQ;

/* Inicializa uma fila com prioridades, com capacidade para n elementos.

PRE: n > 0

POS: (PQempty() == 1) && (PQfull() == 0) */

PQinit(int n);


int PQempty(void);


int PQfull(void);

/* Insere um elemento do tipo type, na fila pq

PRE: PQfull() == 0

POS: PQempty() == 0 */

void PQput(type t);

/* Retorna e retira o elemento da fila com a maior chave

PRE: PQempty() ==0

POS: PQfull()== 0 */

type PQdeletemax(void);

# $ " & " & " % # ' ,

/* Altera a prioridade do elemento t da fila; se t existir,

deixa a fila inalterada caso contrário.

PRE: PQempty() ==0 */

void PQchangePriority(type t);

/* Remove o elemento t da fila; se t existir,

deixa a fila inalterada caso contrário.

PRE: PQempty() ==0 */

type PQdelete(type t);

/* Devolve o elemento com maior chave sem o remover.

PRE: PQempty() == 0

POS: não altera o estado da fila */

type PQmax(void);

/* Troca o elemento com maior chave com o argumento t.

PRE: PQempty() == 0 */

PQswapmax(type t);

" % ' " " % # " # & ' ( * " # & $ !

$ " $ (

+ " $ * % " # # # $

" " % " " # # % " $ $ $

% $ $ $ % ( & ' % % $

" # * # & % $ %

# ! % % # % # # $

$ # $ $ $ ( " " # & ' " $ # $ $

,

/* Ficheiro: pqueue.c */

#include “pqueue.c"

#define less(A,B) (Key(A) < Key(B))

static int ta; /* tamanho actual */

static int cap; /* capacidade */

static type *elems; /* array de elementos */

/* Retira e retorna o elemento da fila com a maior chave

PRE: PQempty() ==0

POS: PQfull()== 0 */

type PQdeletemax(void)

int I, mx = 0;

type t;

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

if (less(elems[mx], elems[i]) mx = i;

t = elems[mx];

elems[mx] = elems[--ta];

return t;

" # & ' $ & $ ! $ % ! % % (

" # & ' $ " # % # $ % " $ # "

# " ( " # $ " % * # "

% ! " " " % # $ # (

' $ % # % " # & " & $ & '

" & $ & ' % " % ( % " # &

" & % $ % " $

! % % ( # $

# $ % * (

" # # " $ * % % " % # $ # $ $ (

$ $ # $ $ " $ " # + $ *

( " # " $ " # $ $ $ $ ,

(

& ' & ' $ # $ $ $ " # & '

$ * (

(

& ' & ' % $ # $ " # & ' *

$ # # $ (

# $ # $ " " $ " # $ % $ $ $

,

(

& ' & ' " % " $ " # & ' *

$ # # $ (

(

" % " * ' % " $ % %

" # & ' * (

+ " $ * " $ " + " & &

" % " $ # $ $ ( + % $

(

$ & ' $ % " # & ' $ + $ ! $ % ! % % (

(

% # % " & '

# $ " % " $ $ % & ' $ !

( " % $ # $ " # " & (

(

+ " # + $ ( " # & ' (

% # % " " % $ & $ % $ & ' (

(

$ + $ " # + % (

(

" # & $ % $ + # # $ # # $ (

% # % " " % $ & $ % $ & ' (

(

% * % # $ + # # # ,

$ #

$ & ' $ # $ % " $

% & ' # $ $ # * #

(

" # & $ % $ + # % " $ $ $ $ " & ' $ & ' # $ " % ( #

% " # ! $ $ " % " % $ & ' $ & ' " " (

(

" # & $ % $ + # % " $ $ $ #

# $ ( % * % $ % " * # ( % # % "

" % $ & $ % $ & ' (

(

" $ $ # $ # % " $ $ "

+ % %

# $ " " $ $

% " #

% # #

(

# % % # $ $ $ " # $ # $ "

% * ( $ " # #

# $ " & $ % ! % " % (

$ " # & $ % ,

/* Inicializa uma fila generalizada (GC – generalized queue),

com capacidade para n elementos.

PRE: n > 0

POS: (GQempty() == 1) && (GQfull() == 0) */

void GQinit(int n);


int GQempty(void);


int GQfull(void);


PRE: GQfull() == 0

POS: (GQempty() == 0) */

void GQenqueue(type t);

/* Retira o elemento da fila inserido mais recentemente (o último da fila) e retorna-o.

PRE: GQempty()==0

POS: GQfull()== 0 */

type GQlast(void);

/* Retira o elemento mais antigo na fila (o primeiro da fila) e retorna-o.

PRE: GQempty()==0

POS: GQfull()== 0 */

type GQfirst(void);

15. Implementação em C de ADTs com múltiplas

instâncias

" # & $ $ " $ $

* $ $ $ " ( % % % # $ ! " #

$ * # * " " * # ! " " # & " % "

' " ! % $ % % % $ + (

% " $ # " # & ' % $ ! " #

% % $ (

# $ " ! " # * $ * # *

" % # % # $ % % # $ $ " $ " # " $

% & " $ " " " #

& ' % # % # $ % $ " ( % $ $ * # *

# ,

/* interface */


double dist(point, point);

/* código cliente */

int main()

point A, B;

A.x=1.0; A.y=1.0;

B.x=4.0; B.y=2.0;

printf("Distância: %f \n", dist(A,B));

return 0;

;

/*implementação */

double dist(point p1, point p2)

float dx= p2.x-p1.x;

float dy= p2.y-p1.y;

return sqrt(dx*dx+dy*dy);

;

) $ " # + " # & $ "

" ' " $ $ " # " # & ' "

% # % " ' " $ $ % $ + " (

" # " # & ' $ # $

" & ' $ " # " " * # $ + $

% $ $ " & ' (

% $ + " " $ % $ % $ $ ,

/* ficheiro: point.h */

#ifndef _POINT_

#define _POINT_

typedef struct point *Point;

Point POINTinit(float, float);

float POINTx(Point);

float POINTy(Point);

double POINTdistance(Point, Point);

#endif

$ % * # " & ' $ + " ( # $ "

" % ' " * # $ " $ " # ' " $

% $ $ % % $ $ " # ( # $ $

" & " " * # ( % # ' % $ % " $

" # " ' % $ $ * #

% " $ (

" " " $ % $ $ %

" # (

" # & ' " $ $ $ " ,

/* ficheiro: point.c */

#include <stdio.h>

#include <math.h>

#include "point.h"

struct point float x, y; ;

Point POINTinit(float x, float y)

Point p=(Point) malloc(sizeof *p);

if (!p)

fprintf(stderr, "No more memory.");

exit(1);

p->x=x;

p->y=y;

return p;

;

float POINTx(Point p) return p->x; ;

float POINTy(Point p) return p->y; ;

double POINTdistance(Point p1, Point p2)

float dx= (p1->x)-(p2->x);

float dy= (p1->y)-(p2->y);

return sqrt(dx*dx+dy*dy);

" % # % % ,

#include <stdio.h>

#include "point.h"

/* código cliente */

int main()

Point A, B;

A=POINTinit(1.0,1.0);

B=POINTinit(4.0,3.0);

printf("Distância: %f \n", POINTdistance(A,B));

return 0;

" $ " # & " % # # #

* $ $ % " # malloc

( # +

$ " # " & ' " # & ' $ ( ! " #

" & ' " $ " # $ " # % ,

void POINTfree( Point p)

free(p);

' # & ' $ " # " % # % " $ % " * $

# % $ ( ! " # & $ " ,

Point A=POINTinit(1.0,1.0);

Point B=POINTinit(4.0,3.0);

B=A;

" $ $ & $ * $ % # " $ " B

"

& ' B=A

( $ * # $ % # * $

" B

% ,

Point A=POINTinit(1.0,1.0);

Point B=POINTinit(4.0,3.0);

Pointfree(B);

B=A;

# & ' $ + * % % " + % # " #

% " % $ $ % * % & ' (

# * * ' $ % % & $ + % # " #

% * $ % " $ % # $ % % $

+ " # ( ! " # " % $ + #

$ " " # " # % $ ! $ * " # & " *

% ! % % (

/* ficheiro: queue.h */

#ifndef _QUEUE_

#define _QUEUE_

#include "qtype.h"

typedef struct point *Q;

/* Inicializa uma fila FIFO q, com capacidade para n elementos.

PRE: n > = 0

POS: (Qempty(q) == 1) && (Qfull(a) == 0)

*/

Q Qinit(int n);

/* Liberta o espaço de memória reservado para q */

void Qfree(Q q)

/* Retorna 1 se a fila q está vazia; retorna 0 caso contrário. */

int Qempty(Q q);

/* Retorna 1 se a fila q está cheia; retorna 0, caso contrário.*/

int Qfull(Q q);

/* Retorna e retira o primeiro elemento inserido na fila q. */

/* PRE: Qempty(q)==0 */

/* POS: Qfull(q)== 0 */

qtype Qget(Q q);

/* Retorna, sem retirar o elemento inserido na fila q à mais tempo. */

/* PRE: Qempty(q)==0 */

/* POS: q = old q */

qtype Qfront(Q q);

/* Insere um elemento t do tipo qtype, na fila q

PRE: Qfull(q) == 0

POS: (Qempty(q) == 0)

*/

void Qput(Q q, qtype t);

#endif

% & ' * # # $ " " % $ % & ' % $ &

$ & ( & $ & " $ % $ % (

$ % $ $ $ " $ ' " $ $ % $ $ ( # $ $ $ %

$ # $ $ $ " " % $ %

( & ' $ & " $ $

$ $ $ % # " $ $ (

! " # $ " $ & $ & " #

$ " % * ' $ % & ( $ * & % # % $ $ ( $ & ' % # ' " $

" $ " % & ' n/d

$ n

d 0

' ( %

% " & ' $ % # ' " $ % (

% $ % % $ % * ' (

# " $ " ! $ " # % % ,

=

++

++=

$ % % ' ( ! " # #

(

( ( $ " & ' $ % #

" $ % % " " $ " $

! % " ,

=

++=

% % === " $ % # % # $ $ ,

% # " $ $

+ $ ! " ' $ % & ' % $ " $ % % %

" $ % # % # $ " ! & ' % & ' # $ (

" ! & ' $ "

$ $ " # &

$ & ,

−− +=

−− +=

% % $ & % ,

& $ & * # % # % # $ " $ "

% # % # * # % " * ' $ " % # % # * # (

# $ " " " # % " $ % (

# # * $ $ &

$ & $ " $ (

" % # " " # " % $ % % ,

#include <stdio.h>

#include <stdlib.h>

#include "queue.h"

#define ORD 10

int main(int c, char**args)

int signal=1;

double r, y, ratio, error;

long num, den, a;

double x, epsilon=0;

Q nk, dk;

if (c < 2)

fprintf(stderr, “USAGE: f2f <float> [<epsilon>]”);

exit(0);

nk = Qinit(ORD);

dk = Qinit(ORD) ;

Qput(nk, 1);

Qput(dk, 0);

x = atof(args[1]);

epsilon = atof(args[2]);

if (x <0)

x = -x;

signal = -1;

a = (long) x;

Qput(nk, a)

Qput(dk, 1);

r = x - a;

if (r) y = 1.0 / r;

else

printf(“%ld\n”, a*signal);

Qfree(nk);

Qfree(dk);

return 1;

for(;;)

a = (long) y;

num = Qget(nk) + a * Qfront(nk); /* n[k] = n[k-2] + a * n[k-1] */

den = Qget(dk) + a * Qfront(dk); /* d[k] = d[k-2] + a * d[k-1] */

ratio = (double) num / double (den);

error = fabs(x - ratio);

if (error <= epsilon)

printf(“%ld/%ld \n”, num*signal, den);

break;

Qput(nk, num);

Qput(dk, den);

r = y - a;

/* Aqui r != 0; caso contrário o ciclo teria sido interrompido no break anterior. */

y = 1.0 / r;

Qfree(nk);

Qfree(dk);

return 0;

! " # " # $ # & ' $ " (

> f2f 0.333333333 <return>

1/3

' # $ $ % * ' " $ # $

( " $ * # ! % * " $ % * ' (

(

(

$ " # & ' $ + % & ' "

% " # " # % (

( ( + % # & $ + ,

( ( (

& ' " " * % & ' %

$ $

( ( (

& ' % * % ' $ " & '

$ $ $

( ( (

& ' # " & * $ " $

( ( (

& ' % # % & ' " " % & '

% # $ (

( ( " # & $ % # $ (

( ( % * " # & $ % # $ % "

% & ' # $ (

(

+ % " # & ' " * # " +

% " # ! " # " # % ( $ " " & ,

% $ # " # % & ' (

(

# % $ " # & $ $ " + % $

% $ % ( $ % % # ' #

" " % (

16. O tipo de dados abstracto polinómio

# & ' $ + % " " # " # % " % #

$ $ " # % # % % %

# ( ! " # " % # $ $ " # %

% " # ! % & " " # % ( # & ' $ +

! % " # $ $ % % $ " # " # *

" & ' " ( # % *

% " # $ $ % % % $ " (

% " # + " " (

* # " % # * $ " # & ' $ + "

" & ' $ " # (

+ " $ * % " # $ % $

$ $ ,

* * #

% %

! " (

! " # $ " # , ( ) −=

( ) ++=

$ " # # ! " $ $ (

+ $ " # ( )

=

= ( )

==

' ( )

=

+=+

( ) = =

=

" " # % % $ # ! " %

,

( ) −=

( ) +−=

( ) +−=+

# " # % " # " $ # # $

" " $ $ $ * ,

( ) ( )( )

−++−

−+−+−=

+−−=

$ * % $ * # * # % $ "

# " # % & ' $ " # (

$ $ * # * + " # " % # % # * # $

" # P(x)

" $ $ x

% " & # % % $ & '

# " # % & ' $ " # ( " # * " $ % $

+ " # % " ! % $ $ % & '

% " # (

# & $ % " + " # ,

% , " # (

typedef struct poly *POLY;

float POLYeval(POLY, float);

POLY POLYadd(POLY, POLY);

POLY POLYmult(POLY, POLY);

void POLYprint(POLY);

void POLYfree(POLY);

& % " $ % * " % ,

#include "poly.h"

void f(POLY a, POLY b, POLY c)

POLY tmp, e;

tmp = POLYmult(a, b);

e = POLYadd(tmp, c);

POLYfree(tmp);

POLYprint(e);

POLYfree(e);

$ % $ % % $ $ $ " # & $ % $

+ " # " & ' $ # ( + % " $ # % % " $ % $ % # $

% % $ " # " # & ' $ & " % #

" # (

" # & ' $ + " # $ % $ % $

" # $ $ " % $ " $

" # " % % % $ " # (

% % $ " # ' $ $ " $ % % $ ! " (

! " # % $ " # ( ) −=

' $ $ %

" & % # ' $ % ,

$ % $ , # $ ,

% %

! " ,

% $ % & ' $ % $ $ % * " $ $ ,

/* ficheiro: poly1.c */

#include "poly.h"

struct poly

int degree;

float *coefs;

;

" # & ' # POLYeval(POLY p, float x)

% # % # * # $

" # p

" x $ ( # $

# % # % " # % # % # " $ $ $

" * # $ " & ( * & ' ,

!

!

!

! ( ( (

!

!

!

! " # ,

+++=+++

+ ,

float POLYeval(POLY p, float x)

int i;

float re = p->coefs[p->degree];

for(i=(p->degree)-1; i >= 0; i--)

re = re*x + p->coefs[i];

return re;

! % & ' $ & ' * $ # $ " % ,

+

++

+++

/* PRE: n >=0 */

/* POS: Instância de polinómio cujo grau é n e todos os coeficientes são zero */

static POLY POLYnew(int n)

POLY re = (POLY) malloc(sizeof *re);

if(!re)

fprintf(stderr, "Insuficient mem in POLY new \n");

exit(1);

re->degree = n;

re->coefs = (float *) calloc(n+1, sizeof(float));

if(!re->coefs)


exit(1);

return re;

/* Liberta a memória usada pelo polinómio p */

void POLYfree(POLY p)

free(p->coefs);

free(p);

/* Multiplicação dos polinómios p e q */

POLY POLYmult(POLY p, POLY q)

int i, j;

POLY re = POLYnew(p->degree + q->degree);

for(i=0; i<=p->degree; i++)

for(j=0; j<=q->degree; j++)

re->coefs[i+j] += p->coefs[i]*q->coefs[j];

return re;

;

/* Adição dos polinómios p e q. */

POLY POLYadd(POLY p, POLY q)

int i;

POLY re= POLYnew(max(p->degree, q->degree));

for(i=0; i <= p->degree; i++) re -> coefs[i] = p->coefs[i];

for(i=0; i <= q->degree; i++) re -> coefs[i] += q->coefs[i];

return re;

" # & ' $ & ' POLYprint

$ ! $ % ! % % (

" # & ' $ + " # $ * " $ $ " $ &

$ $ % # $ $ % % % #

# * $ ( ( $ $ $ $ " # ( " #

( ) +=

( ) +++=

' ! " # $ % ( $ $ " # # * $ ! " %

" # & ' $ # # $ $ # *

" " $ (

" # & ' $ # " $ " % " $ % $ $ #

" $ " # (

! " # " # A(x)

% " $ " $ % "

% $ $ # % $ " # % % ! " $ % # & ' " ! (

$ $ ! " # * $ % & $ # $

$ $ " $ $ % % $ ! " ( #

% % % # ' ' % $ $ (

" % " & * % $ ' ! * # # * #

" * # * ' % " ( " $ " #

+ " # % $ & $ " * " #

# $ % # # & ' % $ (

# % $ $ * # * " # # $ $

$ $ % "type.h"

$ $ % # $ % $ type

(

% * ,

/* ficheiro type.h */

typedef struct int expo; float coef; type;

% $ " # & ' poly2.c

" $ % $ ,

#include "poly.h"

#include "sllist.h"

#include "type.h"

struct poly

int degree; /* Não é absolutamente necessário */

link head, last;

;

/* PRE: n >=0 */

/* POS: Instância de polinómio */

static POLY POLYnew(int n)

POLY re = (POLY) malloc(sizeof *re);

if(!re)


exit(1);

re->degree = n;

re->head=NULL;

re->last=NULL;

return re;

/* PRE: !p */

void POLYfree(POLY p)

lstremove(&(p->head));

free(p);

/* PRE: p != NULL */


int i;

link l = p->head;

float re = l->item.coef;

l = l -> next;

for(i=(p->degree)-1; i >= 0; i--)

if(l->item.expo == i)

re = re*x + l->item.coef;

l = l -> next;

else re *= x;

return re;

$ " # " $ " # $ $ % $ % ,

& " % " # " % $ $ $ " #

( " % % $ " # % & $ " # ' % & $ " % * # (

( ) −=

( ) +−=

( ) ( ) ( )+=

) ! " % % * " # # $

% $ % % ' # ( * & " " ! " # ( ! " # ,

) % # $ " # p

* ! " $ % # $

" # q

' " $ % % % # $ p

" # # $

* & " " ! $ p

( % # $ q

' # $ (

! " # ,

$ " # $ " # $

" $ ' % % $ " # # $ (

" % $ " $ " # $ % ,

,!p && !q

POLY POLYadd(POLY p, POLY q)

float sum;

POLY re;

link ph = p->head;

link qh = q->head;

re = POLYnew(max(p->degree, q->degree));

while (ph && qh)

if(ph->item.expo == qh->item.expo)

sum = ph->item.coef + qh->item.coef;

if(sum) POLYappend(re, ph->item.expo, sum);

ph = ph -> next; qh = qh -> next;

else if(ph->item.expo < qh->item.expo)

POLYappend(re, qh->item.expo, qh->item.coef);

qh = qh -> next;

else

POLYappend(re, ph->item.expo, ph->item.coef);

ph = ph -> next;

for(; ph; ph=ph->next) POLYappend(re, ph->item.expo, ph->item.coef);

for(; qh; qh=qh->next) POLYappend(re, qh->item.expo, qh->item.coef);

return re;

/* Acrescenta um novo termo à representação do polinómio p; */

/* PRE: (c!=0) && (p != NULL ) &&

( p->last==NULL || ( p->last !=NULL && e < p->last->item.expo ))*/

static void POLYappend(POLY p, int e, float c)

type t;

link nn;

t.coef = c;

t.expo = e;

nn = lstnnode(t);

if(p->head==NULL) p->head = nn;

else p->last->next = nn;

p->last = nn;

" # & ' $ & $ ! $ % ! % % (

(

$ + " # " # & ' $ # # $ (

" % " # ,

(a) A(x)=1

(b) B(x)=1-x2

(c) C(x)=x20

(d) D(x)=x16+8x2+1

(e) A(x)+B(x)

(f) A(x)+B(x)+C(x)+D(x)

(

$ + " # " # & ' $ # # $ (

" # & ,


% # % # * # $ " # "

" ! ( ' % " & $ % (

POLY POLYfromUser(void)

# $ % # $ " #

" $ " " # # $ (

% void POLYshow(POLY p)

" # $ " # " (

$ & " ! " # $ " # (

(

$ $ $ " # & ' $ # # $ "

* ' $ & '

POLY POLYmult(POLY,POLY)

# $ $ # " # % & ' $ " # (

$ $ % " # ! $ $ " % $ & ' $ * # * $

17. O ADT matriz esparsa

$ $ $ % " # % & (

* $ " ,

% " $ " & ' # $ % ,

int mi[Linhas][Colunas];

* $ % $ " % ,

int **ppi;

ppi=malloc2d(Linhas, Colunas);

% % # $ # i % #

j % * $

mi[i][j]

ppi[i][j](

* % " $ $ $ ! $ " # # ' ' # $ # " ' $ $ ( " $ % " (

$ $ $ % % " " "

$ " $ & $ $ % $ * # $ (

" ! % & $ + " * #

$ " # & ' " % # * " # (

$ % $ % * $ " # $ &

" $ % $ + " ( $ $ #

" " " # & ' " # " # % (

/* ficheiro matrix.h */

typedef struct matrix* M;

/* Liberta o espaço ocupado pela matriz */

void Mfree(M);

/* Calcula a transposta da matriz */

M Mtranspose(M);

/* Calcula a soma das matrizes a e b */

M Madd(M a, M b);

/* Calcula a multiplicação das matrizes a e b. */

M Mmult(M a, M b);

$ # $ " $ % % $ " " # <linha, coluna, valor>

(

" " $ " $ " $ " # (

! " # "

( ! $ # , ! ( $ # ,

" $ " $ " # " #

" # & ' $ $ + " " $ $ $

" ,

/* ficheiro matrix1.c */

#include "matrix.h"

#include "type.h"

typedef struct

int row, col;

type value;

triple;

struct matrix

int norows, nocols, actsize;

triple *triples;

;

/* inicializa uma matriz

PRE: r >0 && c >0 && s > 0 */

static M Minit(int r, int c, int s)

M m = (M) malloc (sizeof *m);

if (!m)

fprintf(stderr, "Minit exception: Not enough mem. for another matrix.\n");

exit(1);

m -> triples = (triple *) malloc(s*sizeof(triple));

if (! m->triples)

fprintf(stderr, "Minit exception: Not enough mem. for triples. \n");

exit(1);

m->actsize = s;

m->norows = r;

m->nocols = c;

return m;

void Mfree(M m)

free(m->triples);

free(m);

! A

nxm

" # $ % AT

&

mxn ' ( " at[i][j]

) a[j][i]

# a[j][i]

" " *

j + " !

i

A ' , - " .

///

0

1

2223

4=//

/0

1

2223

4

5667 6666 6686 966:

56696666 6686 766: ;

! ! " ! ) + + " A

# + $ ! ! " .

for(i=0; i<m; i++) m == ' + " !

A for(j=0; j<n; j++) n ==

' " * A

at[i][j]=a[j][i];

! ! " ) ! # + $ ! ) ! + " + .

/* Versão 1: Sem preocupações de ordenação dos elementos da matriz transposta */

/* PRE: m->actsize > 0 */ Mtranspose(M m)

int i;

M t = Minit(m->nocols, m->norows, m->actsize);

for (i=0; i < m->actsize; i++)

t -> triples[i].row = m -> triples[i].col;

t -> triples[i].col = m -> triples[i].row;

t -> triples[i].value = m -> triples[i].value;

;

return t;

;

" - " .

=

# #

# # # #

# #

# #

) # #

# # # #

# #

# #

" * + " ! # #

# #

# #

# # # #

+ ) " + + " * + " * + + + " ! ' ) + " " ) " $ ! & ! " # + '

, ) ! + " + ! " ! + + ) ) + " + " $ " ' + + + $ !

+ $ ! . ! " * ) + " ! $ " # + + " ! - + + " ! $ " ' ! % + $ !

elcol ' - " .elcol[0]=2

elcol[1]=1

elcol[2]=0

elcol[3]=2

" ! + ! " " * # " * " * '

" " * #t# +

t->triples[0]# " " * # +

elcol[0]#

t->triples[2] '

$ ! + + # " " * + elcol[0]+elcol[1]

#

t->triples[3] '

& $ ! + spos '

( + $ ! " ! ) Mtranspose

! + + .

/* Versão 2: A matriz transposta retornada pela função tem os seus elementos ordenados por

valores crescentes de linhas e dentro das linhas por valores crescentes de colunas */

/* PRE: m->actsize > 0 */

M Mtranspose(M m)

int i, j;

M t = Minit(m->nocols, m->norows, m->actsize);

int *elscol = callocd (m->nocols, sizeof(int));

int *spos = callocd (m->nocols, sizeof(int));

for(i=0; i < m->actsize; i++) elscol[m->triples[i].col]++;

for (i=1; i < m->nocols; i++) spos[i] = spos[i-1] + elscol[i-1];

for (i=0; i < m->actsize; i++)

j = spos[ m->triples[i].col]++;

t -> triples[j].row = m -> triples[i].col;

t -> triples[j].col = m -> triples[i].row;

t -> triples[j].value = m -> triples[i].value;

;

free(elscol); free(spos);

return t;

;

! ) callocd

! ) ! ! " " + ) ' ! ) ! "

calloc

<stdlib> # " !

+ " '

/* Calcula a matriz a+b */

/* PRE: (a->nocols == b->nocols) && (b->norows == b->norows) */

M Madd(M a, M b)

int i=0, j=0, n=0, sum=0;

int maxsize = max(a->actsize+ b->actsize, a->norows*a->nocols);

M c = Minit(a->norows, a->nocols, maxsize);

/* Neste momento, podemos dizer que no max, a matriz c = a+b, tera' um

no de elementos igual a max( a->actsize + b->actsize, a->linhas*a->colunas);

Posteriormente actualizaremos o actsize de c */

while( (i < a->actsize) && (j < b->actsize))

if (a->triples[i].row < b->triples[j].row)

c->triples[n++] = a->triples[i++];

else if (a->triples[i].row > b->triples[j].row)

c->triples[n++] = b->triples[j++];

else /* a->triple[i].row == b->triples[j].row */

if (a->triples[i].col < b->triples[j].col)

c->triples[n++] = a->triples[i++];

else if (a->triples[i].col > b->triples[j].col)

c->triples[n++] = b->triples[j++];

else

sum = a->triples[i].value + b->triples[j].value;

if (sum)

c->triples[n].value = sum;

c->triples[n].row = a->triples[i].row;

c->triples[n].col = a->triples[i].col;

n++;

i++; j++;

for( ; i < a->actsize; i++) c->triples[n++] = a->triples[i];

for( ; j < b->actsize; j++) c->triples[n++] = b->triples[j];

c->actsize = n;

return c;

- " ! " ' " $ ! .

" * ! " # ! " " ) + ! ! " ! + $ ! ! " + " * # + " ! " " + ' )

" ) & ! ) ! " ! & ! " + " ' , " # ! $ ! ! " & ! ! # ) ! ' ! " ) '

" - " + " # ! " ! ! ! ! ! + + " '

- " .

! + ! ! $ ! ) " ) ! " # ! + ! + ! " ! + " + '

$ ! + " ) + ) + +

s0, s1, s2,

s3 ' # + ! " + ! + " ) ! ! '

( " + - " * + " ! '

( " s0, s1, s2 e s3

! " + + ! " " " $ ' , " # + " + " + + ! " ' ! + ! " * ! ! + ! + " ! ' ( " " *

i " + " !

i '

) # ! $ ! ! + l

" * #c

+ " ! n " ) ! " +

max(l,c)+n '

! " # ! " $ ! + $ ! ) ! + .

( ! $ ! $ + .

next - "

rigth " *

i

down + " !

i '

, ! ! # ! $ ! + $ ! ) ! + .

( .% row

" * " ) ! "

% col

+ " ! " ) ! "

% value

" " ) ! " "

% rigth

! - " * row

% down

! - + " ! col '

( down

right

! " '

" + + ! " + ! + ! ! + ' ! ! + # + ! ' , " ! # ! ! ! " ! ) ! ! )

union) ! + " !

+ + + '

# " # + + " + * matrix2.c

# " $ ! ) # $ ! .

/* ficheiro matrix2.c */

#include "matrix.h"

#include "type.h"


typedef struct

int row, col;

type value;

triple;

struct node

link down, right;

union

triple data; /* Para os nós de dados */

link next; /* Para os nós sentinela */

u;

;

struct matrix

int norows, nocols;

int actsize;

link head;

;

$ ! " ! ) MfromUser

# ! ! ! " % + + ! ! ! '

) ! ! " ! " ! ! ! ! & ' ! ) + ! ! " " * + " ! " # " $ ! ) ! " '

" ! & # ) + " " + " + + ! " ! " $ '

! ) " ! + - " $ ! ! ! + ! '

! ) + ! # " " " * " * ' ! + " ) ! " " + ! $ ! ' ( " $ - '

$ ! - % ! ! + $ ! " " * # + " ! '

, + ! " $ & ! - # + # ! $ ! " + " ) " " + " * + + " ! ' ) $ ! " ' - $ $ ! " & + $ ! .

typedef struct

link next;

link lastdown;

link lastright;

links ;

struct node

link down, right;

union

triple data;

links connection;

u;

;

( + $ ! ) MfromUser

! + + ! " $ & $ ! .

M MfromUser(void)

/* … */

m = Minit(l,c);

row = m->head;

for(i=0; i < l; i ++)

col = m->head;

for(j=0; j< c; j++)

printf("(%d, %d): ", i, j);

scanf(printfstring, &t);

if(t)

pn = Mnnode();

pn->u.data.value = t;

pn->u.data.row = i;

pn->u.data.col = j;

row->u.connection.lastright -> right = pn;

row->u.connection.lastright = pn;

col->u.connection.lastdown -> down = pn;

col->u.connection.lastdown = pn;

/* ... */

+ * " * # ! ! - " ! $ ! '

( + $ " - + - + + ' " % # # ! + + " ! ! " * + * % " + + ! " " " * ' ( ! + + " ! '

Mprint $ ! " ) " ! ) Mprint

! " ) ! " ! ' ( " ) " * " * '

void Mprint(M m)

link row = m ->head;

link i = row;

do

i = i->right;

if (i == row) i=i->u.connection.next; row=i;

else

printf("(%d, %d ): ", i->u.data.row, i->u.data.col);

printf(printfstring, i->u.data.value);

printf("\n");

while( i != m->head );

;

, ! & " " # + " ! ! ) '

' $ !

! + ) ! ! + ! " '

+ + $ ! " ' ! ! ! + & ! '

' ! " ) $ " ! ! ! + " - $ " + " '

+ " $ ! ! & .

' ! ) ! + " ! !

+ "

' ! ) ! ! ! +

$ !

' ! ) ! " $ !

$ !

' ! ) ! + ) $ !

" ! ) " ! ) ' '+

+ ! $ + " ! ! " ! & + " +

+ ) .

' " ) ! " ' " $ ! ! & .

M MfromUser(void) ! ! " " !

% ! + ' void Mprint(M m)

! + ) " '+

type Mvalue(int i,int j) ! " " "

+ # '

' + ! ) M Mtranspose (M m)

# + # ! " ! + ! - " ! " ) '

' " ! " * + " + ! " ! " + # + ' ) - " * + " + ! " " * + " ! ' ( ! $ + $ ! + .

−+

+

load <nome de ficheiro> $ ! " * + " + ! " $ + * + + 'save <nome de ficheiro> + * + + " * + " + ! " - '<l> <c> <v> " + "

<v># " *

<l> + " !

<c> " * + " + ! " '

l <i> + " ! " - " * <i>

c <j> + " ! " - + " ! <j>

clear + + ! " " ! " * +

quit - + ! ) $ ! - + ! ! + $ " * + " + ! " '

18. Primeiras noções sobre árvores

) ! + ) ! * ! " ! " ' " - " ! " " ! + + " ! $ " $ + ! # # # + ' ! ' ( + ! ! + ) " + + ! " ! $ ! ' $ " # $ + # + $ $ ! ! ) # ) ' ! + ) ! ! $ ! ! " + ! . ! # # + " + # + ' + ! # + * ) $ + ! . $ ! % + * + ! ! ) # ! # '

+ ! ) + " $ $ ) + * ' - & " $ + # ! $ " - & ! " $ ! $ " # ) + ! ' , - " # - ) "

+ " ! ! " " + ) + + " '

, " # ! + + " $ ' , - " # - + ! ) ! + $ ! ' ! ! - " + ! + + + ) + ) ' + ! " " ! " ! & ) '

! + + ! " $ ! # " # ! $ ! + " + ) ) ! + + ! " $ ' " ! + + ! # # ! + ! ) +

⊆ ! + ! ) + # !

+ ! ' ( + ! $ ! ) '

! # ! + * ! " + + ! ) " $ + ' + . - - + ! + * ! " ! '

+ ! - "

# # # # # # # # '

- ' ! $ ! $ ! .•

"

• +

•

• '

! % + ' + ! ! + " * ! '

! + # ! " ! ! ! % + " - " '

! " $ + ! + + ' ! + + ! " # ! " + ! " # !+ ! ! + + ! " ' - " .

# - + # - + ! + # ! '

! n

- i

! i

+ n

i

+ *

n '

( + - n

# ) + * " * ! ! + n '

" * n

) ) '

( " * ! + * $ ! ' ( $ ! ! " - $ ! '

" * % " * ! " + " ! " * ) + * ) " '

! + ! + + ) ' ! + ! + ) ) $ + ! ! + * ! + " ! " ' ( ! $ + ! ) * ! " " * ! # ! " $ ! '

+ ! ! ! + # ) # ) !

M ' ! - # " * '

$ ! $ ! ! ' ' # ! - ) + + ! " + '

! # ! + . - # # " * # + - + " * '

! " * + ) # + * % " * " * ! " * ' % ! ! " * ! ! " * ' # ! ! " * ) - '

! M

# ! " * + ! ! ! " * ) - '

( ! + ! " $ ! + % ' ! - " + + ! ! # ! ! + # " ! & + ! ' , ! " # ! ! & + ! + ! ! " '

) + ! . ! - ! ! " $ ! # ! ) + * ! % ! ! % '

$ ! + + ! " ) ' - " + ) # + " ! " & ! ! ' ) + - '

"

"

)

! ! + " # + ! ) $ ! ! + " ! " + " + ) # " * ! " * # + - ' ) - & - + - + + '

, ) + " ) ! ! + " '

% + * ! ! + * # - + ! " " '

+ " ! + * ! " " + ! - " '

" ! " ! + " $ & ! + + ' ! ) " '

, - " # $ ! ) + * # " $ ) + " ' + ! ) # + - " '

" & ! + " + ! ! ! + " $ & !

links) ' ( links

! " + - '

+ ! ) + + ! " .

! " ) .

( + + $ ! " ! + $ ! ! ! .

typedef struct node *link;

struct node

type item;

link left, right;

;

) ! " ) + & ! + + + - ' , " $ ! + + - + + ! +

link

! ! node

# ! ! '

) + ! M

. M

! - ! ! " $ ! ! + ! ) "

M ' ! + + * % " ' " ! + ! ! '

! + * " $ ! ! + ! '

) + ! ! ! " ! " * !

M +

M " * '

! + ! ! " ! links

# ! ! " " $ ! $ !

links

" * '

$ # ! + - " " + $ ! .

) " ) + " ! + + " $ & ! ' ! " " $ ! ! + # ! ! - ! ) '

, ! ! ! # + !

link ! !

n # " *

! $ " # ! link

n

! ) # $ " '

, ! $ ! - # " # $ ! '

) " * % ! % ) !

% %

) " ) + ) '

+ ! ) ! " $ ! + ! ) ' + ! + * % " ) '

, ! ) ! ! # # ! ! ) '

' $ ! ) ! '

! " * # - '

" ) + " " $ '

+ ! ! ' " ! ) " * !

) '

' * ! " $ ! + ! + # % # % # % # % %

# ! + "

! '

19. Árvores binárias

! ! & ! " ) # + " ! & " # # " ! & # ! + ! '

+ " ! ! + " + % $ ! . ! ! # ! + ! + '

" " " $ ! " . + ! $ ! !

link# + .

void lsttraverse(link l, void (*visit) (link))

if (!l) return;

visit(l);

lsttraverse(l -> next, visit);

visit

! ! ) ! + ' + ! ) lsttraverse + # + + ! ' " $ !

link

+ ! ' + + ! + '

, " # " ! # " # " ! .

' ! % ! ! % # ' # + ! - ) $ " % - + .

preorder traversal

' ! % ! # ! % # ' ' # + ! - '

inorder traversal

' ! % ! # ' ' # + ! ! -

postorder traversal

+ ) " # + $ ! .

void ttraverse( link l, void (*visit) (link))

if (!l) return;

visit(l);

ttraverse(t->left, visit);

visit(l);

ttraverse(t->right, visit);

visit(l);

;

# + .

typedef struct node *link;

struct node

type item;

link left, right;

;

( + ! - ! - ) visit(l)

" * $ - &

visit(l) + ' $ ! " # + !

infixo %

+ - ) $ ' + ! ! -

% .

+ + ! prefixo

! + + * ! & $ ! .

ttraverse(R)

visit(R)

ttraverse(A)

visit(A)

ttraverse(C)

visit(C)

ttraverse(E)

visit(E)

ttraverse(NULL)

ttraverse(NULL)

ttraverse(F)

visit(F)

ttraverse(NULL)

ttraverse(NULL)

ttraverse(NULL)

ttraverse(B)

visit(B)

ttraverse(D)

visit(D)

ttraverse(NULL)

ttraverse(G)

visit(G)

ttraverse(NULL)

ttraverse(NULL)

ttraverse(NULL)

! " * ! " ! " ) ! ! + !

prefixo ' # + ! " % + ! infixo

+

sufixo '

# !

! + $ ! ! + ! - ) + + ! + ! + $ ! + ! ! - ! +

. ! ) - ) ) ! - ' ! " ! + + $ ! + ! -

! $ + ! ! + - ' - " ! " + " $ ! .

$ + * + ! "

+ * + ! " $ ! '

! ) ! " $ $ ! .

* PRE: l!=NULL void tlorder(link l, void (*visit) (link))

static int MAXN=10;

QUEUEinit(MAXN);

QUEUEput(l);

while (!QUEUEempty())

l=QUEUEget();

visit(l);

if (l->left) QUEUEput(l->left);

if (l->right) QUEUEput(l->right);

( ! + ! ! ) ! ! ! ! ! + ! " +

( # + " # ! ! " + ( # + # ! ! ) ) + ! + $ ! ! + !

prefixo ! # + # ! '

( ! + " + ! " ! ) $ !

int tcount (link l)

if (!l) return 0;

return 1+ tcount(l->left)+ tcount(l->right);

;

) + " + ! ! ) + ' ! ) + # + ! ) ! + " + ! " - ! ) " $ ! '

+ - '

, ! ! ) ' ! ) ! ! - # " ! + ' ( ! ) $ ! . , # ! " !

! ! ! % ! ! ' , " * ! ) # ! ! - ! - # ! " - '

( ! " . + + ! " $ & '

( " ! ! ! " ! ! ! ' - " .

" $ ! ! # ! + ! ' # ) ! + + ) " ! + + # " $ & ! + + # ! + '

" ! ! " - ! '

" ! ! + + ! " * ' " ! ! " ! ! '

! ) ! + " + ! " " ! ! .

/*PRE: t != NULL */

int theight (link t)

if (!t) return -1;

return 1+ max(theight(l->left),theight (l->right));

;

max

! ) ! + " + ! " - '

( - ! ! ! " ' ! ) '

( - ! " ! h

1 + 2 + ... + 2h =

2(h+1)-1.

! ! $ ) $ + ) # ' , ! .

−−=

+

=

$ ! ! ) ! + ! ' - " + ! ! + " # " !

h# + " "

'

link trand( int h )

if (h < 0 ) return NULL;

link tmp=tnnode(rand()%10);

tmp->left=trand(h-1);

tmp->right= trand(h-1);

return tmp;

;

! ! ) ! + ! ! .

link tnnode( type t)

link tmp=(link) malloc (sizeof *tmp);

if (!tmp) fprintf(stderr, “Erro na alocação de memória”); exit(1);

tmp->value=t;

tmp->left=NULL; tmp->right=NULL;

return tmp;

;

' + ! ! ) ! + " * ! '

' + ! ! ) ! + ! ! ! " * ! - '

' + ! ! ) ! ! " * '

' + ! ! ) ! " + ! ! '

' + ! ! ) # ) + ! # ! + ) ! ! ! + !

-

-

+

! -

' + ! ! ) ! + ! ! " !

! " ' $ ! ! '

' + ! ! ) ! + ! ! + ! # + " ! " '

'

" ! '

+ ! ! ) ! + ! '+

+ ! ! ) ! " ! '

' ! '

+ ! ! ) ! + ! + + " ! " '

+ ! ! ) ! + ! '+

+ ! ! ) ! " ! '

20. Acervos e filas com prioridades

( ! + % # ! + # " " + ! ! & ) ) * + ' " $ ! + " - " + & ) ) " & ! " + " '

PQput PQdeletemax ) + " $ " $

" # ! +

! + ! " ) $ ! # ! ) ! + * '

! + " # ! + ! ! + " ! $ ! + . + * + + ! ! $ ! " + * ! + # +

- ! ! " # + * ! ! $ ! " + * ! '

! - " ' ( $ ! ! + ' (

$ !

! + # ! ) ! " ! # ! ! ! ! # + ! ! " ) + ) + + ! ! ' , + + ) + + + ! ' # " # ! + ! + + + * $ ' ! + ! ! " ) + + + + ) '

% ! ! + ! ! + * ! $ ! " + * ! " * ' # ! " ! ) # ! ! " * ! # ) % ! ) '

( + ! + " ! + * % + ) + " $ ! .

void fixUp(type *t, int position)

int father;

while ( k && less( t [father = (position-1) /2 ], t [position] ))

swap(t[father], t[position]);

position = father;

% ! ! ! + " # "father

+ $ ! ) p

# + % ) father = (int)

(p-1)/2 , - " # - " # ! )

# + + * # ! + ) (int) (4-1)/2 ,

, 1

! + # + " ! ! $ ! ! + ! + * ! ! + * ! # ! # " * # ) + " ) + + " * ' + ! " ) # " ! + ! + * $ " * ' ! + ! ! " ) + + + + ) '

( + ! + " ! + * % + ) - " $ ! .

void fixDown (type *t, int position, int N)

int child;

while ((child = 2*position+1) < N )

if (child < N-1 && less (t[child], t[child+1)) child++;

if (!less (t[position], t[child])) break;

swap(t[position], t[child]);

position = child;

+ " ! ! ! + " # " * ) # + % &

2*p+1 e 2*p+2 , - " #

- " # " * ! ) # ) + + * # ! + &

2*2+1 e 2*2+2 '

+ ! " ) + ) + # " ) " + % ) + '

! " ) ! " " + # + .

/* Ficheiro: PQ.h */

#include "type.h"

typedef struct priority_queue *PQ;

/* Inicializa uma fila com prioridades, com capacidade para n elementos.

PRE: n >= 0

POS: (PQempty() == 1) && (PQfull() == 0) */

PQ PQinit(PQ q, int n);

/* Liberta a memória usada pela fila pq

PRE: pq != NULL */

void PQfree(PQ pq);

/* Retorna 1 se a fila está vazia; retorna 0 caso contrário.

PRE: pq != NULL */

int PQempty(PQ pq);

/* Retorna 1 se a fila está cheia; retorna 0, caso contrário.

PRE: pq !=NULL */

int PQfull(PQ pq);


PRE: pq != NULL && PQfull(pq) == 0

POS: pq!= NULL && PQempty(pq) == 0 */

void PQput(PQ pq, type t);


PRE: pq !=NULL && PQempty(pq) ==0

POS: pq != NULL && PQfull(pq)== 0 */

type PQdeletemax(PQ pq);

" " ) " ! # ! ) # + ! & ! " & $ ) ! & ) ) ' ) # " + " + + $ % ! " & + ) + ! + + + ) + ' ) # + % " " + # ! % ) ! ! " % ! " ! $ " " ' " + $ ! .

/* Ficheiro: PQ.c */

struct priority_queue

int ta; /* tamanho actual */

int cap; /* capacidade */

type *elems; /* array de elementos */


PRE: pq != NULL && PQfull(pq) == 0

POS: pq!= NULL && PQempty(pq) == 0 */

void PQput(PQ pq, type t)

pq-> elems[pq->ta] = t;

fixUp(pq->elemes, ta++);


PRE: pq !=NULL && PQempty(pq) ==0

POS: pq != NULL && PQfull(pq)== 0 */

type PQdeletemax(PQ pq)

swap( pq->elems[0], pq->elems[--(pq->ta)]);

fixDown(pq->elems, 0, pq->ta);

return pq->elems[pq->ta];

" ) ! & - + - + + '

" ) ! " + + % + ! " $ ) " ! + + "

n log n#

n * + " + ) '

void PQsort(type *a, int n)

int i;

PQ pq = PQinit(n);

for (i=0; i<n; i++) PQput(pq, a[i]);

for(i=n-1; i >= 0; i--) a[i] = PQdeletemax(pq);

PQfree(pq);

# " $ " ! " ! - + "

n ' " - ' ( " " " $ ) - + - + + '

' ! ! + $ ! # ! ) # ! + 'int *a=16, 12, 9, 8, 7, 7, 3, 2 ,4 , 1, 0;

' + char *a=‘x’, ‘m’, ‘n’, ‘a’, ‘b’, ‘e’, ‘c’; ! ! + ! + " ! + # ! .

" " + + ) - " ) +

" ! " ) + + ) + '

' (

int *a=1, 2, 3, 4, 5, 6, 5, 4 ,3, 2, 1; ) ! + ' " a

! + +

) !

' + ! ! ) ! ! ! ! ) ! + ' ' " " ) ! & + " +

+ '

' , " $ ) + ! " $ ! ) + - ! ! " " $ + '

Referências bibliográficas

# # # # # ' # ' # ' # ' # # # * , # '

Referência completa e formal aos algoritmos e estruturas de dados; Não usa

nenhuma linguagem de programação. É uma das referências pedagógicas

mais usadas em todo mundo para estas matérias.

$ * + * # ' $ * # ' + * #

# , + % " " # '

Escrito por um dos criadores da linguagem C é uma referência obrigatória para

o estudioso do C.

! * # ' ' ! * # #

# % " # $ # # '

Este volume, juntamento com o Vol 1, Fundamental Algorithms e o Vol 2,

Seminumerical Algorithms, formam a biblia dos Algoritmos e das Estruturas de

Dados. No Vol. 3, Knuth apresenta e analisa detalhadamente um vasto

conjunto de algoritmos ordenação e procura.

# # # , + " " #

'

Referência fundamental sobre factores de Qualidade em software e referência

obrigatória para o estudo de Projecto por Contrato, especialmente quando

aplicado à abordagem orientada por objectos.

$ + # $ + #

# % " # '

Apresenta um conjunto muito interessante de algoritmos e estruturas de dados

em C.

Referência rápida sobre C

R1. Preliminares

• " $ ! $ ! $ " " + + '

• $ + $ '

• " $ ! $ " ! & # ! " $ ! " ! + " " '

R2. Algumas características do C

• ( " + " ! ! " +

• , + ! ! + " + " $ ! $ ! !

%

! ) " + ) + $

%

+ " ! + " $ +

%

" + & " # " " "

• $ ! $ + + %

+ " $ + # + + ! % ! )

%

) ! + " + & ' , $ .

, & * + # ! & ) * ! " #+

strcpy#

strcmp ! ) ! & ! +

+ $ # + '

( ! " + & .

if (x>=0)

abs = x;

else

abs = -x; + " .

abs = (x>=0) ? x : -x;

" ! ?:

+ * + + + '

• ( ! + + + .% , ! ! & ' , - " # ! &

) ) ! & ) ! & " ' $ ) ) ! '%

+

%

! " ) " "

R3. Exemplo de programa

, % + ! $ + " + ! " ! & # # ! + ! " $ ! ' ( $ + '( $ " ! + + ' ( ! & .

−=

#include <stdio.h> #define MFA 9 /* MAX factorial Arg. */ unsigned int factorial(unsigned int); int main() int m, n, d; unsigned int p; printf("m | m > 0 e m < %d: ", MFA); scanf("%d", &m); printf("n | n > 0 e n < m: "); scanf("%d", &n); if ((m>0) && (m < MFA) && (n >0) && (n< m) && ((d=m-n)>0)) p = factorial (m) / factorial(d); printf("Permutacoes de %d, %d a %d: %u \n", m, n, n, p); else printf("Dados inválidos ou inconsistentes. \n"); return 0; /* Versão básica iterativa do factorial. Argumento: n, inteiro sem sinal. Retorna : inteiro sem sinal dado por: n*(n-1)* ...1 se n>0 1 se n==0 Obs: A função não verifica se o seu valor de retorno excede a gama dos inteiros sem sinal. */ unsigned int factorial (unsigned int n) unsigned tmp = 1; register int i; for(i=1; i<= n; i=i+1) tmp = tmp * i; return tmp;

• ( % + + ! $ ! " & + $ .%

! ! +

%

+ #include<stdio.h>

! ! " + + * stdio.h ' %

( " ! ! + '

• + " & . + " - + ! & ! " ! $ .

unsigned int factorial(unsigned int);

• ! )

main ! ! ) + " # ! ) + " $ '

! ) ! - + ! ) $ + '

• .

/* */

• + " ) .

int m, n, d;

• + ) ! & .

factorial (m);

• ) ! & .

unsigned int factorial(unsigned int) /* ... */

• + " .

if ( /* condição */)

p = factorial (m) / factorial(d);

printf("Permutacoes de %d, %d a %d: %u \n", m, n, n, p);

else printf("Dados inválidos ou inconsistentes. \n");

• + " + .

for(i=1; i<=n; i++) tmp = tmp * i;

R4. Elementos de sintaxe

( ! " $ ! $ " # # % ! # ! " " * ! " ! " + " + $ # - + ! $ ! + .

' + ' " + * ' + % +

( + * + + $ " + . ' +

' " % + *

' +

' + + +

'

' ! )

- " " " - + .if (n<0) return(0);

if " % + *

( " ! )

n +

< " + "

0 +

) " ! )

return " % + *

( " ! )

0 +

) " ! )

; " ! )

• ( + ) ! # ! & # +

• ( + ) ! + " $ ! + ! " !

• ( " ! + ! " + ! " ' , - " #

tmp

Tmp )

+ '

• + + " + ! "

• + ! + '

•

" % + * ) + + ! ! ) '

auto double int struct

break else long switch

case enum register typedef

char extern return union

const float short unsigned

continue for signed void

default goto sizeof volatile

do If static while

• - ! + .

char ! ) ! + +

int

)

float # $ ! " " ! ! # + )

" 'double

# $ ! " " ! ! # + ) ! " '

void ! + "

• ( ! " + " + + + + .

! " +

" + % short int , ) ! $

long int

double , ) ! $

signed

unsigned char

#int,

short long int

+ + " + ! " '

• $ + + " '

• ( unsigned

! " ! " '

• ( signed

! " + " '

• + " ) ! " + " " # '

+ " ) ! " + " ! .% classe

. + ! # $ # + ! -

% qualificador:

+ + + + +

% tipo:

+ " ! " $ !

% nome

$ . + " '

- " .static unsigned i, j;

• ) ! " + ! + ! ) + " ! '

•

+ + " ) " - + ! ) ' - " . '

+ + +

• - + " + ! + '

•

$ " # + ! # + " ) # + + ! + ! " '

• ! - " + .

u !

U

l !

L

• + .%

+ . % %

+ . %

* - + . - -

• + + + + " " + # + '

• ( + + + ) + " ! + + # + + + " ' ) + ! + + # + $ ! .

\n " *

\t ! " * "

\v ! " + "

\b +

\r

\f ! $

\a "

• $ + ) .

\ooo !

\xhh !

ooo

hh )

+ + $ + " * - + " + + ' - " . + + ! " '

•

+ ) " ! + ! + " ! + " ' #

! '

• ( ! - " + ) !

" ! ' - " . "

' ' double ' ' double

' ' double ' % '

double

' ' Float ' ' long double

• # ) ! ! ' ( ! ! '

• " $ ! . + " $ + " + ! )

• ! + + '

• + - # ! ! ! $ + '

• ( + ) .+

-

! + ) ! + *

! " " + ) /

) ! )

% ) ( ) $

int.

• ( - " + + + '

& ) + * ! $ ! ' , - " # ! ' # ! " & % ' ! ! # + " + ! - + ) ! '

• - " + & ! + .% + .

1 + 3.14 % ! & .int i; float x=3.14; i = x;

• - " + ) .

int i; float f=13.0; i= (int) f % 4;

< <= > >= == != && || !

• ( ) " '

• ( " $ + " + ) + " " $ + # + $ ! .

% ( " #

%

! " ! ! " '

• " ! ! - ) + " + ' - " .

a = -1 + (b==c) * 2

+ " ) + " + " ' , + ! + ) ' - " + + " ! ! + - + ! .

while(x=0) /* ... */

• - &

i==0

!i ) ! " '

• ! )

a=b + ! - ) + ! " "

a ' + ! # " "

a+ " ! "

" ) b '

i = i + 2; ! ) "

a = b = 1;

a = (b= 1)+ 2;

! ) " "

i += 2;

x *= 10;

! % ! ) .x <op>= y

! ! - &

x = x <op> y#

<op> +,-, *, /,%, &, |, ^, >>, <<.

a = c++; + ) ! - ' ! "

a = c; c = c+1;

c-- + ) ! - '

a = ++c; + ) - ' ! "

c=c + 1; a=c;

--c + ) -

abs = x >=0 ? x : -x; ! ) + + " ' ! " if(x>=0) abs = x; else abs = -x;

• - " ! " ) % ! ) ! ) + " .

unsigned int factorial(int n)

int i;

unsigned tmp=1;

for(i=1; i<=n; tmp *= i++);

return(tmp);

• ( ! " ! " ' ( ) .

& ! )

| ! )

^ ! % - + " !

<< " + !

>> " +

~ $ )

• " $ + &&

#||

- + ! ) ! " $ ! + * + " ! " - ) ' - " .

a && (c = n / a); /* Se a=0 então (c=n/a) não é executado ! */

i || i++; /* Só incrementa i, se i = 0 */

• + - # + +

# ! " ! )

$ ! ! ! '

• + # ) + " + ! " ! # " ! " " $ !

' - .printf(“%d \n”, (“nada”, “zero”, 0, ‘0’, 1));

• " $ ! # " * + +

" * ) $ + + + + '

( ) [ ] -> .

! ~ ++ -- +φ -φ *φ &φ sizeof

* / %

+ -

<< >>

< <= > >=

== !=

&

^

|

&&

||

?:

= <op>=

- ,

φ

R5. Controlo de fluxo de programa

• ( " ! ! + " + " $ ! $ ! ! .

%

) ! ) " + ) + $

%

! & " + ) . " # " " " %

! & . + + " ! + " $ +

- ! ) )

) ! # " |

" # " [ ]

+ + " # - &

) + ! "

" "

" " $ ! $ '

<instrução> ::= “;” | <expressão> “;” | ““ <instrução> “” | if “(“ <expressão> “)” <instrução> | if “(“ <expressão> ”)” <instrução> else <instrução> | switch “(“ <expressão> “)” <instrução> | case <constante> “:” <instrução> | default “:” <instrução> | break “;”

| while “(“ <expressão “)” <instrução> | do <instrução> while “(“ <expressão> “)” “;”

| for “(“ [ <expressão> ] “;” [ <expressão> ] “;” [ <expressão> ] “)” <instrução> | continue “;” | return [ <expressão> ] “;” | goto <identificador> “;” | <identificador> “:” <instrução>

if

" + ) " '

<expressão> ) - + !

<instrução>

" + ) " '

<expressão> ) - + ! %

<instrução1>, senão executa <instrução2>

if(a)

if(b)

printf(“a e b são ambos diferentes de zero”);

if(a)

if (b)

printf(“a e b são ambos diferentes de zero”);

else

printf(“a é diferente de zero, mas b é igual a zero”);

$ " ) $ ! . ( else +

if -

! ) * else

+ + #if

#else

" + + # " * # ! + $ + ! + $ $ ' - " .

#if _PT_

# include "elapc.pt"

#else

(1) if “(“ <expressão> ”)” <instrução> | (2) if “(“ <expressão> ”)” <instrução1> else <instrução2>

# include "elapc.usa"

#endif

switch

' ( "

<expressão> + " + ! " + + + !

+ ' ' + $ ! " # - + ! ! & + ' '

default - expressão>

) $ ! " * ! + ) ! & instrução>

) - + ! '

switch(n)

case 1: printf(“Um \n”); break;

case 2: printf(“Dois \n”);

break;

case 3:

case 4: printf(“Três ou quatro: ”);

printf(“Nem mais nem menos. \n”); break;

default: printf(“Ou negativo, ou zero, ou muitos \n”);

switch “(” <expressão> “)” ““ case <constante1> “:” <instrução1> [break”;”]

... case <constanteN> “:” <instrução N> [break “;” ]

[default “:” <instrução> ] “”

while

( + ! ! &

<instrução> - + ! !

" <expressão>

'

( - + ! <instrução> ' , #

<expressão>

+ " # + + " ) - + ! '

while (c=0) printf(“ %d \n”, c++); /* Ciclo nunca executado */

do

! & <instrução>

) - + ! ! <expressão>

' <expressão>

- + ! ) <instrução>.

! # + + " - + ! " ! '

do

printf (" Escreva um número positivo: "); scanf("%d", &n);

while (n <=0);

while “(“ <expressão> “)” <instrução>

do <instrução> while ( <expressão> )

for

! " .

' + #

<expressão1> + "

' <instrução> - + ! !

<expressão2>

' + ) #<expressão3>

+ ! " ' ' - & ) + '

<expressão2>

! + ) % # + + " '

for(i=0; i < 2; i++) printf("%d \n", i);

for(i=0; i > 2; i++) printf(“%d \n”, i); /* Nenhuma iteração será executada */

for(;;) /* Ciclo infinito */

for “(“ [<expressão1>] “;” [<expressão2>] “;” [<expressão3>] “)” <instrução>

<expressão1> while “(“ <expressão2> “)” ““

<instrução> <expressão3> “;”

“”

break

switch#

do#

while

for + "

! ) $ ! + ! ) ! + * '

continue + ! &

do#

while !

for '

) + ! " # ) $ ! '

goto <identificador> " ! ) + + ' ! - $ + " + + $ - ! ! " ) "

R6. Funções

+ ) ! ! # ' + " ) + ' #

!

+ " ) ! ) + ! " + ! ) +

) ! ) ! ) ' + " ) + " ! ! ) + + ) - " +

' " + " ! ) ' " ! ) + * '

• ! " ! ! ) ! + " ! " '

• ! ) ) " ! " ! " # + " +

void ' ! ! ) ) + " + '

! ) ) + " ! + " int '

! ) + " ! + !

int '

• # + " ) ! ! ) + ! ! ! + + '

int printf(const char *format, ...);

return [ <instrução> ] “;” ! ) ! # " ! # ! & + - + ) ! "

void ' ! ) - + ! ! ' ( - ) + " ! ! ) " '

• , " $ ! ) + " + ! " " + ) + ! ) $ $ ! " '

" ) " ) " + $ ! '

" + + # ! " " + + ! "

$ ! " ! " ' - $ ! " + + .

' " + + " + " . " + + + " + ! " + " + # " ! " + + ! ! ) + ! ) '

' " + + + * . " + + + " ! " ! ! ) # + + " ) + + * ) + " '

R7. Arrays e Matrizes

• $ ! # # ! + " + ) " $ ! - ! '

int a[3]; a[0] a[1] a[2]

• ( ) & + .%

&

%

! )

%

" ) + ! '

• # ! + + + ! ! $ ! + + " + + ' - " .

char str[5] = “olá”;

) ! " . # + # + # # ) .

<tipo> <nome>“[“<expressão constante>”]”; .

% <tipo> é o tipo dos elementos individuais do vector; % <nome> é o nome do vector;

<expressão constante> indica o número de elementos que constituem o vector.

- " .

int multi[2][3]; /* ou alternativamente */ int (multi[2])[3];

! " ! + " # ! " ! " # + ! ! ! + "

R8. Ponteiros

( + ! + ) - " ' ( ) + + + ' ) - # - $ ! ! " ) + ! '

• ! ! " ! $ !

! " ! '

• + " ' + " ) ! # + ! " ) " # # + " $ '

• + " ) ! ! !

& '

<tipo> <nome> “[“<dim1>“]” “[“<dim2>“]” ... “[“<dimn>“]”

<tipo> “*”<nome do ponteiro>;

•

ptr

x# )

*ptr "

x.*&x

x).

• ( + " ! ! ! ! " # - + + " !

&# ++

# --

#sizeof

! ! ! ! ) '

int x, *ptr_x, y;

ptr_x = &x;

*ptr_x = 0; /*coloca x a 0*/

y = *ptr_x + 3; /* igual a y = x + 3 */

*ptr_x += 2; /* igual a x += 2; */

y = (*ptr_x)++; /* igual a x++ */

• ( & + . ' ! ! ! ! '

( ! " ! % " !

" $ " ! $ " '

int a[3], *ptr_a; ptr_a = &a[0];

a[0] a[1] a[2]

ptr_a == a

) # ) ! + " ! + " * + ! ' - " .

char *c ! + * + ! # " !

c += 2 + " c

# ' + int *i

! int

+ !

, )

i +=2 + "

i & '

! + & ! + " ) ! " ' !

char $ !

# * " + '

' ! ' ( ! " " " ' , $ .

( ! " ptrdiff

stddef ' *

• ( ! & ' # !

>, >=, <, <=, ==

!=# ! + " '

' + ! ! & ! .

(

! " ! $ ! + .% (void *)

% 0

, ! " $ +

int a[5], *a1, *a2, i; a1 = &a[1]; a2 = &a[2]; i = (int) (a2 – a1); printf(“%d \n”, i);

• ( " ! + ) " '

• + ' ( ! + + '

• , + " ! + ! " $ ! " + " + " '

• ) " " " ! + '

• " " " " + '

const int ci = 1; const int *pi = &ci; int *pi2 = &ci; /* Erro ! */ int i; pi = &ci;

pi = &i; /* OK: Embora i não seja constante o seu valor não será alterado através de pi. */

int i, ii; int *const icp = &i; icp = &ii; /* Erro */

• ) " " " " "

'

R9. Sinónimos de tipo

• " % + *

typedef ! + !

" ! ! ! '

• ( typedef ) ! ! # ! ! !

! + + ! '

const int ci = 1; const int * const cp2ic = &ci;

int (*ptrf) (int, int)=0; /* Declaração de ponteiro para funções com 2 argumentos inteiros, e retorno de um inteiro. */ int min(int, int); ptrf = min;

typedef <tipo elementar ou estruturado> <identificador>

typedef unsigned char byte; unsigned char byte1; byte byte2;

typedef int (*pf) (int, int); pf p2f, ap2f[10];

R10. Estruturas

• ! ! $ ! # # ! + " + ) " * $ '

• ! ! ! + + ! " ! + . " ! ! # ! ! # + '

• ! ! ! ' ) " ! " ) ! ! ! + '

• # ! ! .%

+ "

%

!

%

+ $ ! ! &

%

" ! & '

• ( + ! ! ! ! ' '

( + ! ! ! ! !

% '

struct student char *name; int number; ; main() struct student a_student; a_student.name= “José”; a_student.number = 27267; /* ... */

• ( ! ! ! + + + ! + " ) '

R11. Uniões

• ! & + ! ! ! + '

• " * ! # " ) ! " ! '

R12. Campos de bits

• ( + + + + ! ! '

• ( + + " ! ! ! ! & '•

) ! " ) ! ! " ) '

struct student *ps, student = “Ana”, 12312; ps = &student;

ps -> name; /*é igual a (*ps).name */

struct x_tremly_low_mem unsigned int age: 6;

unsigned int sex: 1; unsigned : ; /* não usado */

....

R13. Enumerações

• ! & ) ! " + + '

• ( ! ! ) # + * ! # ) const int '

• , # ! ! ) ! " + + + ! ! ' ! " '

• , % ! ! ! ) '

enum key special, home=71, xx ; /* é equivalente a const int special =0; const int home=71; const int xx = 80; */

R14. Directivas de Pré-processador

• ( % + # " * " * # " * + ! + + ' ( % + + " '

• + + !

#define identificador texto +

#define MAX 100

#define SQUARED(a) ((a)*(a))

#else, #elif e #endif

#if expressão + $ $ ! +

#else, #elif

ou #endif#

expressão ) ! " '

#ifdef identificador + $ $ ! +

#else, #elif !#endif

# - identificador '

#ifndef identificador + $ $ ! +

#else, #elif !#endif

# ) - + identificador '

#include “nome_ficheiro” + !

+

+ ! " # ) + + ! + #include

<nome_ficheiro>.

#include <nome_ficheiro> , + ! + + $ !

'#undef identificador

+ % + $ + identificador

# '

R15. Biblioteca de funções

• ( " ! + ! ! & % + " # + * ! & " + '

• " + + ! + * + " * + + " & ! & # + ! '

• , ! ! ! ) " + ! $ # + + " ! # $ # + * + " * + '

assert.h + $ + '

ctype.h ! & + ) + + - . " * #

" 'errno.h

+ + $ 'float.h , " + + & $ ! "

" ! ! + ) # $ # + 'limits.h

" + + #$ # + '

locale.h ! & & " $ ! $ '

math.h ! & + '

setjmp.h " + * " ! &

signal.h + & - + + '

stdarg.h ! & + $ ! + * + '

stddef.h + ! ! + * + " * '

stdio.h ! & + '

stdlib.h " $ 'string.h

! " ) + + + 'time.h , + * '

! & + ) + +

int isalnum(int c)

" * + $ +

int isalpha(int c) ! + " +

int iscntrl(int c) + + + " # ' ' # c

-

c -

int isdigit(int) " $

int isgraph(int) + + " - +

int islower(int) " ! + ! "

int isprint(int) + + " + " !

int ispunct(int) + + ! ) # ' ' # + + " - + #" # " $

int isspace(int) # # " # + $ ! # # ! + "

int isupper(int) " + ! "

int isxdigit(int) $ * - + "

int tolower(int c)

c + ! " " + ! " +

" c

# + + 'int toupper(int c)

c

+ ! " " + ! " +

" c

# + + '

! & + '

int fprintf(FILE *, const char *format, ...) int printf(const char *format, ...)

int sprintf(char *, const char *format, ...)

format.

% [flags] [width] [.prec] [ h | l ] <type_char>

" $ $ +

- " * !

+ + "

(espaço) ) - # + !

0 + * + !

# + ! " + + "

<type_char> $ !

c char

short !

int

d, i int

short !

char

u

unsigned int

unsigned char !

unsigned short

o + "

f

double !

float - - - '

e double !

float ) $ * # ' ' # % - - - ' %

E + # !

g double - !

! !

+ ) ) $ ! " ) + 'G

$ ! " # ! # + 's

! + + + x

int

* - + " # ! # # + # # # # + # # # # # + '

X $ ! " ! # # # # #

P # + + '

N ) + ' ( + + + !

" '% ( + +

int sscanf(char *, const char *format, ...)

int fscanf(FILE*, char *, const char *format, ...) int scanf(const char *format, ...)

format.

% [*] [width] [h|l|L] <type_char>

<type_char> $ !

c char * - width + + ) " + +

d int * - + "

i int* - + " + ! * - + " +

- ' u unsigned int *

E, f, g float * % ) + " *

s char * - + + + + + +

x int* - * - + " # + ! - !

o int* - + " # + ! )

p void* - " + +

printf(“%p”)

n ) " + $ ! "

[ <cp> ] ! + ! + . " ! + # ' $ ' %[0123456789]

[^ <cp> ] ! + ! + . " ! ) + # ' $ ' %[^abc]

% %; ) ! )

Índice remissívo

A

+ # + # + " # # " + + # " # " + # " " ) # " " - + # # $ ! #

#

# # # # # + * #

+ " # # + # #

M# #

) # # # # ) # #

assert#

! #

B

# ! " # " + #

C

+ # # + * # #

+ ) # + ) # # + # + " #

+ " - #

+ " - + # # #

+ " - + " # # + " - " #

+ ) + # + #

+ + ) # # # # #

+ + " " # + + ! % " " #

D

+ " ) #

) #

! #

$ ! ! #

+ + # + # #

E

! ) #

+ + ) # $ + # # ! ! # ! ! # - + ) # - + ) #

F

+ ! " #

( # # # " #

" " # " # # " + # " $ " # ! #

! ) + ! # #

H

#

I

+ # ! ) + # + #

L

" $ ! #

( # # # " + + ! " " " $ # " ! " " $ # " " " $ #

M

! ) # # # # # $ ' #

N

" ! # # " # ) - # ) ! - # ) % ( # ) % #

O

( & + # # # + + # ) - # ) + # ) #

) " + ) #

P

" % + * #

, #

+ ! # ! ) #

" * # # #

# # # " + + #

" # # # + + # + # + #

, ! ! # ! & #

pop#

% + ) # % + ) # # ! + ! ) # ! ! # ! # + # + ! ! # + + # #

, #

push#

Q

! " # ! " + # ! ! #

quicksort#

R

+ + # ! #

S

! + + # # ! ) #

static# #

$ # #

T

# # # " #

# + # #

typedef#

U

! ) # # #

V

+ #

" #

Documents

Programação Avançada em C Usando Algoritmos …w3.ualg.pt/~jvo/pacuaedf.pdfProgramação Avançada em C Usando Algoritmos e Estruturas de Dados Fundamentais The Ualg Informatics