Lista1EstruturaDeDados

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

DuplamenteEncadeada.c
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
typedef struct listadupla{
	int chave;
	struct listadupla *ant;
	struct listadupla *prox;
}listadupla, *plistadupla;
void inicializar(plistadupla *l);
_Bool consulta(plistadupla *l, int x);
_Bool inserir(plistadupla *l, int x);
void remover(plistadupla *l, int x);
void imprimelista(plistadupla *l);
int main(void) {
	plistadupla L;
	int i;
	//abaixo chamada de funções para testes básicos e mostrar como ocorrem as chamadas das funções
	inicializar(&L);
	for(i=0; i < 11 ; i++)
		inserir(&L,i); //inserindo de 0 a 10 na lista
	imprimelista(&L);
	for(i=0; i < 11; i+=2)
		remover(&L,i);	//removendo numeros pares da lista
	imprimelista(&L);
	for(i=0; i < 11; i++)
		if(consulta(&L,i))
			printf("O numero %d pertence a lista\n",i);
		else
			printf("O numero %d nao pertence a lista\n",i);
	return EXIT_SUCCESS;
}
void inicializar(plistadupla *l){
	*l=NULL;
}
plistadupla consultaendereco(plistadupla *l, int x){
	plistadupla p;
	for(p=*l; (p) && (p->chave != x); p=p->prox);
	return p;
}
_Bool consulta(plistadupla *l, int x){
	return (consultaendereco(l,x));
}
_Bool inserir(plistadupla *l, int x){
	plistadupla novo;
	if(!(novo=(plistadupla)malloc(sizeof(listadupla))))
		return false;
	if(*l)
		(*l)->ant=novo;
	novo->chave=x;
	novo->prox=*l;
	novo->ant=NULL;
	*l=novo;
	return true;
}
void remover(plistadupla *l, int x){
	plistadupla p;
	for(p=*l; (p) && (p->chave != x); p=p->prox);
	if(p){
		if(p->prox)
			p->prox->ant=p->ant;
		if(p->ant)
			p->ant->prox=p->prox;
		else
			*l=p->prox;
		free(p);
	}
}
void imprimelista(plistadupla *l){
	plistadupla p;
	printf("\n");
	for(p=*l; (p) ; p=p->prox)
		printf("%d , ", p->chave);
	printf("\n");
}
filaApontador.c
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
typedef struct listasimples{
	int chave;
	struct listasimples *prox;
}lista;
typedef struct fila{
	lista *inicio;
	lista *fim;
}fila, *pfila;
void inicializar(fila *l);
_Bool enfileira(fila *l, int x);
_Bool desenfileira(fila *l, int *x);
int main(void) {
	fila topo;
	int i,x;
	inicializar(&topo);
	for(i=0; i < 11; i++)
		enfileira(&topo, i);
	for(i=0; i < 11; i++){
		desenfileira(&topo, &x);
		printf("desempilhei %d\n",x);
	}
	return EXIT_SUCCESS;
}
void inicializar(fila *l){
	l->inicio=NULL;
	l->fim=NULL;
}
_Bool enfileira(fila *l, int x){
	lista *novo;
	if(!(novo=(lista*)malloc(sizeof(lista))))
		return false;
	novo->chave=x;
	novo->prox=NULL;
	if(l->fim)
		l->fim->prox=novo;
	else
		l->inicio=novo;
	l->fim=novo;
	return true;
}
_Bool desenfileira(fila *l, int *x){
	lista *p;
	if(!(l->inicio))
		return false;
	p=l->inicio;
	*x=p->chave;
	l->inicio=p->prox;
	free(p);
	return true;
}
FilaVetorial.c
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
#define MAXTAM 11
typedef struct fila{
	int chaves[MAXTAM];
	int final;
}fila;
void inicializar(fila *l);
_Bool enfileira(fila *l, int x);
_Bool desenfileira(fila *l, int *x);
int main(void) {
	fila L;
	int i,d;
	//abaixo chamada de funções para testes básicos e mostrar como ocorrem as chamadas das funções
	inicializar(&L);
	for(i=0; i < 11 ; i++)
		enfileira(&L,i); //inserindo de 0 a 10 na pilha
	for(i=0; i < 11; i++){
		desenfileira(&L,&d);
		printf("desemfileirei %d\n",d);
	}
	return EXIT_SUCCESS;
}
void inicializar(fila *l){
	l->final=0;
}
_Bool enfileira(fila *l, int x){
	if(l->final == MAXTAM)
		return false;
	l->chaves[l->final++]=x;
	return true;
}
_Bool desenfileira(fila *l, int *x){
	if(l->final==0)
		return false;
	*x=l->chaves[0];
	l->chaves[0]=l->chaves[--l->final];
	return true;
}
LISTA1 - Estrutura de dados.pdf
MATA 40 Estrutura de Dados e Algoritimos – Lista 1
Obs: As questões acompanham o protótipo das funções pedidas. Você pode utilizar funções já 
implementadas em questões anteriores. É importante implementar as questões da lista para se pegar 
prática em programar as estruturas de dados. Você deve apresentar os tipos de dados utilizados nas 
questões, a não ser que você já tenha descrito o tipo de dado que deseja utilizar em outra questão, 
lembrando de que se não descrever o tipo de dado lembre-se de verificar que o nome que esta 
utilizando seja o mesmo de alguma estrutura de dados já descrita.
Caso queiram correção da lista favor seguir as observações acima e enviar os arquivos para 
viniciussilva@dcc.ufba.br ou vinicius.cscience@gmail.com
As questões que não especifícam a estrutura de dados a utilizar podem ser feitas com a estrutura que
desejarem(lista simples ou dupla, aconselho lista duplamente encadeada)
Obs.: nas respostas que seguem após a questão todas estão utilizando lista simplesmente encadeada
Estrutura de dados Lista exercícios com resoluções
1 – Implementação de todas as funções ensinadas em sala.
Resposta anexa
2 – Implementação de uma função que imprime todos os elementos de uma lista.
Protótipo – void imprimelista(plistasimples *l);
3 - Implementação de uma função que retorna a soma de todos os elementos de uma lista, caso a 
lista esteja vazia a função retorna 0.
Protótipo – int somaelementos(plistasimples l);
4 – Implementação de uma função que retorna a soma de todos os elementos pares de uma lista, 
caso a lista esteja vazia a função retorna 0.
Protótipo – int somapares(plistasimples l);
5 – Implementação de uma função inserir em que o número a lista mantém uma ordem crescente 
dos elementos. A função retorna true caso seja possível inserir o número e false caso contrário (erro 
na alocação de memória).
Protótipo: _Bool insereemordem(plistasimples *l, int x);
6 – Implementação de uma função que retorna o menor elemento de uma lista através de um de seus
parâmentros, caso a lista esteja vazia a função retorna false e caso contrário retorna true. Se a 
função retornar false, o parâmetro que será utilizado para retornar o menor elemento não precisa ter 
um valor, caso contrário deve guardar o menor elemento da lista.
Protótipo: _Bool menorelem(plistasimples l, int *x);
7 – Análogo a questão 6, porém a função irá retornar o maior elemento através de um de seus 
parâmetros.
Protótipo: _Bool maiorelem(plistasimples l, int *x);
8 – Implementação de uma função que verifica se uma lista possui elementos repetidos, a função 
deve retornar true caso a lista repita elementos e false caso contrário.
Protótipo: _Bool repeteelemento(plistasimples l);
9 – Implementação de uma função que dadas 2 listas ordenadas como entrada retorne uma lista 
ordenada que possua todos os elementos das duas listas (a lista pode possuir elementos repetidos).
Protótipo: plistasimples merge(plistasimples l, plistasimples h);
10 - Escreva uma função que identifique se duas cadeias de caracteres são palindromas, as cadeias 
de caracteres serão dadas como entrada concatenadas com o caracter '#' para separalas, exemplo 
“bola#alob” (é palindroma) ou “casa#borracha” (não é palindroma) . Sua função deve retornar true 
caso as cadeias sejam palindromas e false caso contrário.
 Para escrever este algorítimo você pode utilizar apenas as funções (considere que você já possui 
estas funções implementadas):
_Bool getchar(char *x); //esta função retorna true caso a string de entrada não esteja vazia, na saida 
a variavel referenciada por x possui como valor o primeiro caracter da string, o primeiro caracter da 
string é retirado e o segundo caracter passar a ser o primeiro caracter após a chamada da função. 
Esta função retorna false se a string estiver vazia.
_Bool pop(pilha *l, char *x); //esta função retorna true se existir elemento na pilha, retirando este 
elemento e colocando o valor na variavel referenciada por x. Esta função retorna false se a pilha 
esta vazia.
_Bool top(pilha *l, char *x); //esta função
retorna true se existir elemento na pilha, colocando o 
valor do topo na variavel referenciada por x. Esta função retorna false se a pilha esta vazia. (perceba
que é o mesmo que pop porem o elemento não é retirado da pilha)
_Bool push(pilha *l, char x) // esta função retorna true caso seja possível inserir o elemento x na 
pilha , o inserindo na pilha. Esta função retorna false caso não seja possível inserir o elemento x na 
lista. (considere que sempre será possível inserir elementos em uma pilha)
_Bool pilhavazia(pilha l); //esta função retorna true caso a pilha esteja vazia. Esta função retorna 
false caso a pilha não esteja vazia.
void inicializa(pilha *l); // esta função iniciliza uma pilha
OBS: entenda que as únicas funções que você poderá usar são essas, não se deve considerar funções
de bibliotecas de C.
11 - Represente as expressões abaixo na notação pós-fixada e pré-fixada.
(a) (A + B) * ((C + D) / E)
(b) (A + B) * C + D * (E + F/G/H)
IMPLEMENTAÇÕES 
1 – Código esta separado para que seja possível realizar testes.
Demais questões estão abaixo , estão em ordem e é possível indentificálas através do nome da 
função, visto que foram dados os protótipos das funções.
(os tipos de dados utilizados são os mesmos utilizados em sala de aula, somente mudando a 
nomenclatura, e podem ser encontrados nos códigos da questão 1)
int somaelementos(plistasimples l){
int res;
for(res=0; (l) ; res+=l->chave, l=l->prox);
return res;
}
int somapares(plistasimples l){
int res;
for(res=0; (l) ; l=l->prox)
if(!(l->chave%2))
 res+=l->chave;
return res;
}
_Bool insereemordem(plistasimples *l, int x){
plistasimples p,q,novo;
if(!(novo=(plistasimples)malloc(sizeof(listasimples))))
return false;
for(p=*l,q=NULL; (p) && (p->chave < x); q=p, p=p->prox);
novo->chave=x;
novo->prox=p;
if(q)
q->prox=novo;
else
*l=novo;
return true;
}
_Bool menorelem(plistasimples l, int *x){
int menor;
if(!l)
return false;
menor=l->chave;
for(;(l);l=l->prox)
if(l->chave < menor)
menor=l->chave;
*x=menor;
return true;
}
_Bool maiorelem(plistasimples l, int *x){
int maior;
if(!l)
return false;
maior=l->chave;
for(;(l);l=l->prox)
if(l->chave > maior)
maior=l->chave;
*x=maior;
return true;
}
_Bool repeteelemento(plistasimples l){
plistasimples p;
for(;(l);l=l->prox)
for(p=l->prox;(p);p=p->prox)
if(l->chave==p->chave)
return true;
return false;
}
plistasimples merge(plistasimples l, plistasimples h){
plistasimples res;
inicializar(&res);
while((l) && (h)){
if(l->chave < h->chave){
inserirfinal(&res,l->chave);
l=l->prox;
}
else{
inserirfinal(&res, h->chave);
h=h->prox;
}
}
if(l)
for(;(l);inserirfinal(&res,l->chave),l=l->prox);
else
for(;(h);inserirfinal(&res,h->chave),h=h->prox);
return res;
}
_Bool palindromo(char *string){
pilha *p;
char c,x;
_Bool flag;
inicializa(&p);
getchar(string,&c);
while(c!='#'){
push(&p,c);
getchar(string,&c);
}
while(!pilhavazia(p)){
if(!(flag=getchar(string,&c)))
return false;
pop(&p,&x);
if(c!=x)
return false;
}
return true;
}
ListaVetorial.c
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
#define MAXTAM 11
typedef struct lista{
	int chaves[MAXTAM];
	int nelem;
}lista;
void inicializar(lista *l);
_Bool consulta(lista *l, int x);
_Bool inserir(lista *l, int x);
void remover(lista *l, int x);
void imprimelista(lista *l);
int consultaendereco(lista *l, int x);
int main(void) {
	lista L;
	int i;
	//abaixo chamada de funções para testes básicos e mostrar como ocorrem as chamadas das funções
	inicializar(&L);
	for(i=0; i < 11 ; i++)
		inserir(&L,i); //inserindo de 0 a 10 na lista
	imprimelista(&L);
	for(i=0; i < 11; i+=2)
		remover(&L,i);	//removendo numeros pares da lista
	imprimelista(&L);
	for(i=0; i < 11; i++)
		if(consulta(&L,i))
			printf("O numero %d pertence a lista\n",i);
		else
			printf("O numero %d nao pertence a lista\n",i);
	return EXIT_SUCCESS;
}
void inicializar(lista *l){
	l->nelem=0;
}
int consultaendereco(lista *l, int x){
	int i;
	for(i=0; i < l->nelem && l->chaves[i] != x; i++);
	if(i==l->nelem)
		return -1;
	return i;
}
_Bool consulta(lista *l, int x){
	return (consultaendereco(l,x) != -1);
}
_Bool inserir(lista *l, int x){
	if(l->nelem == MAXTAM)
		return false;
	l->chaves[l->nelem++]=x;
	return true;
}
void remover(lista *l, int x){
	int i=consultaendereco(l,x);
	if(i!=-1)
		l->chaves[i]=l->chaves[--l->nelem];
}
void imprimelista(lista *l){
	int i;
	printf("\n");
	for(i=0; i < l->nelem ; i++)
		printf("%d , ", l->chaves[i]);
	printf("\n");
}
PilhaApontador.c
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
typedef struct pilha{
	int chave;
	struct pilha *prox;
}pilha,*ppilha;
void inicializar(ppilha *l);
_Bool topo(ppilha *l, int *x);
_Bool empilha(ppilha *l, int x);
_Bool desempilha(ppilha *l, int *x);
int main(void) {
	ppilha topo;
	int i,x;
	inicializar(&topo);
	for(i=0; i < 11; i++)
		empilha(&topo, i);
	for(i=0; i < 11; i++){
		desempilha(&topo, &x);
		printf("desempilhei %d\n",x);
	}
	return EXIT_SUCCESS;
}
void inicializar(ppilha *l){
	*l=NULL;
}
_Bool topo(ppilha *l, int *x){
	if(!(*l))
		return false;
	*x=(*l)->chave;
	return true;
}
_Bool empilha(ppilha *l, int x){
	ppilha novo;
	if(!(novo=(ppilha)malloc(sizeof(pilha))))
		return false;
	novo->chave=x;
	novo->prox=*l;
	*l=novo;
	return true;
}
_Bool desempilha(ppilha *l, int *x){
	ppilha p=*l;
	if(!p)
		return false;
	*x=p->chave;
	*l=p->prox;
	free(p);
	return true;
}
PilhaVetorial.c
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
#define MAXTAM 11
typedef struct pilha{
	int chaves[MAXTAM];
	int topo;
}pilha;
void inicializar(pilha *l);
_Bool topo(pilha *l, int *x);
_Bool empilha(pilha *l, int x);
_Bool desempilha(pilha *l, int *x);
void imprimepilha(pilha *l);
int main(void) {
	pilha L;
	int i,d;
	//abaixo chamada de funções para testes básicos e mostrar como ocorrem as chamadas das funções
	inicializar(&L);
	for(i=0; i < 11 ; i++)
		empilha(&L,i); //inserindo de 0 a 10 na pilha
	for(i=0; i < 11; i++){
		desempilha(&L,&d);
		printf("desempilhei %d\n",d);
	}
	return EXIT_SUCCESS;
}
void inicializar(pilha *l){
	l->topo=0;
}
_Bool empilha(pilha *l, int x){
	if(l->topo == MAXTAM)
		return false;
	l->chaves[l->topo++]=x;
	return true;
}
_Bool desempilha(pilha *l, int *x){
	if(l->topo==0)
		return false;
	*x=l->chaves[--l->topo];
	return true;
}
_Bool topo(pilha *l, int *x){
	if(l->topo == 0)
		return false;
	*x=l->chaves[l->topo];
	return true;
}
void imprimepilha(pilha *l){
	int i;
	printf("\n");
	for(i=0; i < l->topo ; i++)
		printf("%d , ", l->chaves[i]);
	printf("\n");
}
SimplesmenteEncadeada.c
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
typedef struct listasimples{
	int chave;
	struct listasimples *prox;
}listasimples, *plistasimples;
void inicializar(plistasimples *l);
_Bool consulta(plistasimples *l, int x);
_Bool inserir(plistasimples *l, int x);
void remover(plistasimples *l, int x);
void imprimelista(plistasimples *l);
int main(void) {
	plistasimples L;
	int i;
	//abaixo chamada de funções para testes básicos e mostrar como ocorrem as chamadas das funções
	inicializar(&L);
	for(i=0; i < 11 ; i++)
		inserir(&L,i); //inserindo de 0 a 10 na lista
	imprimelista(&L);
	for(i=0; i < 11; i+=2)
		remover(&L,i);	//removendo numeros pares da lista
	imprimelista(&L);
	for(i=0; i < 11; i++)
		if(consulta(&L,i))
			printf("O numero %d pertence a lista\n",i);
		else
			printf("O numero %d nao pertence a lista\n",i);
	return EXIT_SUCCESS;
}
void inicializar(plistasimples *l){
	*l=NULL;
}
plistasimples consultaendereco(plistasimples *l, int x){
	plistasimples p;
	for(p=*l; (p) && (p->chave
!= x); p=p->prox);
	return p;
}
_Bool consulta(plistasimples *l, int x){
	return (consultaendereco(l,x));
}
_Bool inserir(plistasimples *l, int x){
	plistasimples novo;
	if(!(novo=(plistasimples)malloc(sizeof(listasimples))))
		return false;
	novo->chave=x;
	novo->prox=*l;
	*l=novo;
	return true;
}
void remover(plistasimples *l, int x){
	plistasimples p,q;
	for(p=*l,q=NULL; (p) && (p->chave != x); q=p, p=p->prox);
	if(p){
		if(q)
			q->prox=p->prox;
		else
			*l=p->prox;
		free(p);
	}
}
void imprimelista(plistasimples *l){
	plistasimples p;
	printf("\n");
	for(p=*l; (p) ; p=p->prox)
		printf("%d , ", p->chave);
	printf("\n");
}