1 reply to this topic

[cleytow]

Pessoal, estou precisando com urgência de dois programas em C++ a respeito de listas seqüenciais, encadeadas e circulares. Eu já tentei várias vezes, mas não consegui. Se alguém puder me ajudar fico grato, pois vale a metade da minha prova.
1. O primeiro programa o usuário poderá escolher entre uma lista contígua (seqüencial)e uma lista simplesmente encadeada, depois ele poderá:
• Inserir um nó;
• Excluir um nó;
• Pesquisar um valor “K” (passado pelo usuário).
A estrutura deverá estar carregada com valores aleatórios, ela deverá ter no mínimo 5.000 posições e tem que estar organizada.
2. O segundo programa, nas mesmas condições do primeiro, mas as opções de listas serão: Lista duplamente encadeada e Lista singularmente circular.
Operações:
• Inserir um nó;
• Excluir um nó;
• Pesquisar um valor “K” (passado pelo usuário).
Ambos os programas deverão apresentar ao usuário o tempo de cada operação para que seja possível verificar qual das listas é a mais rápida ou mais lenta.

Quem puder me ajudar, eu fico muito grato,
Cleytow
E-mail: cleytow@yahoo.com.br

[cleytow]

Eu fiz um para lista simplemente encadeada e um para Lista sequencial. Daí então eu tiraria o tempo de operação cada uma e faria uma comparação. Mas tanto um quanto o outro está dando pau.
Se alguém descobrir a bronca eu agradeço.

Já o programa de lista duplamente encadeada e singularmente circular eu ainda não comecei.


// Codigo Programa da Lista Sequencial

#include<stdio.h>
#include<stdlib.h>
#include <dos.h>
#include <time.h>

int valor[200000];//lista
int k;
int fim;//fim da lista
int sinal;//variavel logica
int i, cont, cont2, val, aux;
int Rand[40];
int no[40];
clock_t iniciar, parar;
double Clock[100];

FILE *fp;


main(){
//declarar os valores para a lista
sinal = 1;
srand(time(NULL));
fp=fopen ("graficoSeq.txt","w");
if (!fp)
printf ("Erro na abertura do arquivo.");

for (k=1,Rand[0]=0;k<=30; k++){
Rand[k] = rand() % 1000000;
}

iniciar = clock();
for (k=0;k<=100000; k++){
valor[k] = rand() % 1000000;
fim = k;
}
parar = clock();
k=0;
Clock[99] = ((parar - iniciar) / CLK_TCK);

iniciar = clock();
ordenar(fim);
parar = clock();
Clock[98] = ((parar - iniciar) / CLK_TCK);

// eu tirei a pra acessar pois no comando da questao o sr pede so: inserir, pesquisar e deletar
//Acessar
//for (cont=1;cont<=10; cont++){
//iniciar = clock();
//acc(pesquisa(Rand[cont]));
//parar = clock();
//Clock[cont] = ((parar - iniciar) / CLK_TCK);
//}
for (cont = 1; cont<=30; cont++){

no[cont]= pesquisa2(Rand[cont]);
iniciar = clock();
val = Rand[cont];
inc(no[cont]);
parar = clock();
Clock[cont] = ((parar - iniciar) / CLK_TCK);
}

for (cont = 11; cont<=20; cont++){
no[cont]= pesquisa(Rand[cont]);
iniciar = clock(); // pego o tempo antes de iniciar a tarefa
del(no[cont]);
parar = clock();

Clock[cont] = ((parar - iniciar) / CLK_TCK);
}


for (cont = 21; cont<=30; cont++){
iniciar = clock(); // pego o tempo antes de iniciar a tarefa
no[cont]= pesquisa(Rand[cont]);
parar = clock();
Clock[cont] = ((parar - iniciar) / CLK_TCK);
}


for (i=0;i<=79;i++)
fprintf(fp,"#");

fprintf(fp,"\n""\t""\t""\t""Tabela de Tempo (s) - Lista Sequencial""\n""\n");
fprintf(fp,"Carregar: ""%f""\t""Ordenar: ""%f""\n",Clock[99], Clock[98]);
fprintf(fp,"\n""Inserir""\tNO""\t""\t""Excluir""\tNO""\t""\t""Pesquisar""\tNO""\n");

for (cont=1;cont<=10;cont++)
fprintf(fp,"%f""\t""%d\t""%f""\t""%d\t""%f""\t%d""\n", Clock[cont],no[cont], Clock[cont+10],no[cont+10], Clock[cont+20], no[cont+20]);

fprintf(fp,"\n");
for (i=0;i<=79;i++)
fprintf(fp,"#");

//Escrever na tela
for (i=0;i<=79;i++)
printf("#");

printf("\n""\t""\t""\t""Tabela de Tempo (s) - Lista Sequencial""\n""\n");
printf("Carregar: ""%f""\t""Ordenar: ""%f""\n",Clock[99], Clock[98]);
printf("\n""Inserir""\tNO""\t""\t""Excluir""\tNO""\t""\t""Pesquisar""\tNO""\n");

for (cont=1;cont<=10;cont++)
printf("%.9f""\t""%d\t""%.9f""\t""%d\t""%.9f""\t%d""\n", Clock[cont],no[cont], Clock[cont+10],no[cont+10], Clock[cont+20], no[cont+20]);

printf("\n");
for (i=0;i<=79;i++)
printf("#");

printf("\nDigite Qualquer tecla pra sair...");
fclose(fp);
getch();
exit(0);
}

int acc(int k){ //acessar o k-esimo valor passado
if (k< 0 || k > fim){
sinal = -1;
}
else{
sinal = 1;
val = valor[k];
}
}

int alt(int k){ //alterar o k-esimo valor passado
if (k<0 || k>fim){
sinal = -1;
}
else{
sinal = 1;
valor[k] = val;
}
}


int inc(int k){ //Incluir um elemento na lista
i = fim;
if (k<0 || k>fim){
sinal = -1;
}
else{
while (i>=k) {
valor[i+1] = valor[i];
i--;
}
valor[k] = val;
}
fim++;
}


int del(int k){ //deletar um elemento na lista

if (k<0 || k>fim){
sinal = -1;
}
else{
for (k; k<=(fim-1); k++) {
valor[k] = valor[k+1];
}
}
valor[fim]= 0;
fim--;
}


void ordenar(int fim2){
for (k=0;k<=fim2; k++){
for (cont2 = k+1;cont2<=fim2; cont2++)
{
if ((valor[k]>valor[cont2]))
{
aux = valor[k];
valor[k] = valor[cont2];
valor[cont] = aux;
}
}
}
}
int pesquisa(int pesq){
int q = 0;
while ((pesq != valor[q]) && (q<=fim)){
++q;
}
return q;
}

int pesquisa2(int pesq){
int q;
for (q = 0;(pesq > valor[q]) && (q<=fim);q++){
}
return q;
}


//Codigo do programa Lista Encadeada


#include <stdlib.h>
#include <stdio.h>
#include <dos.h>
#include <time.h>

float Clock[100];
clock_t iniciar, parar;
int k, i, cont;
int Rand[101];
int no;
int No[101];
FILE *fp;

struct lista{
int conteudo;
struct lista *prox;
};

typedef struct lista encadeada;

encadeada c;
encadeada *p;
encadeada *ini;

main(){

fp=fopen ("graficoEnc.txt","w");
if (!fp)
printf ("Erro na abertura do arquivo.");

ini = malloc (sizeof (encadeada));
ini->prox = NULL;
p = NULL;
srand(time(NULL));

for (Rand[0]=0,k=0;k<=100; k++)
Rand[k] = rand() % 1000000;

//Carrega e ordena ao mesmo tempo
iniciar = clock();
for (k=0;k<=100000; k++){
insere((rand() % 1000000), ini);
}
parar = clock();
Clock[0] = (((parar - iniciar) / (CLK_TCK)));
k=0;

//inserir 30 valores aleatorios e ordenar
for (cont=1;cont<=30; cont++){
iniciar = clock();
insere(Rand[cont],ini );
parar = clock();
busca(Rand[cont],ini);
No[cont] = no;
Clock[cont] = ((parar - iniciar) /(CLK_TCK));
}

//
for (cont = 11; cont<=20; cont++){
iniciar = clock();
if (busca(Rand[cont],ini)!= NULL)
Remove((busca(Rand[cont],ini))); //faz a busca e remove
else
if (busca(Rand[cont+10],ini)!= NULL)
Remove((busca(Rand[cont+10],ini))); //so pra diminuir a probabilidade de
else //nao inserir nenhum no
if (busca(Rand[cont+20],ini)!= NULL)
Remove((busca(Rand[cont+20],ini))); //Idem
parar = clock();
No[cont] = no;
Clock[cont] = ((parar - iniciar) / (CLK_TCK));
}
for (cont=21;cont<=30; cont++){
iniciar = clock();
busca(Rand[cont],ini);
parar = clock();
No[cont] = no;
Clock[cont] = ((parar - iniciar) / (CLK_TCK));
}
for (i=0;i<=79;i++)
fprintf(fp,"#");

fprintf(fp,"\n""\t""\t""\t""Tabela de Tempo (s) - Lista Encadeada""\n""\n""Carregar E Ordenar ao Mesmo Tempo: %f""\n",Clock[0]);
fprintf(fp,"Inserir""\t""\t""NO""\t""Remover""\t""\t""NO""\t""Buscar""\t""\t""NO""\n");

for (cont=1;cont<=10;cont++)
fprintf(fp,"%f""\t""%d\t""%f""\t""%d\t""%f""\t%d""\n", Clock[cont], No[cont], Clock[cont+10],No[cont+10], Clock[cont+20],No[cont+20]);

fprintf(fp,"\n");
for (i=0;i<=79;i++)
fprintf(fp,"#");


for (i=0;i<=79;i++)
printf("#");

printf("\n""\t""\t""\t""Tabela de Tempo (s) - Lista Encadeada""\n""\n""Carregar E Ordenar ao Mesmo Tempo: %f""\n",Clock[0]);
printf("Inserir""\t""\t""NO""\t""Remover""\t""\t""NO""\t""Buscar""\t""\t""NO""\n");

for (cont=1;cont<=10;cont++)
printf("%f""\t""%d\t""%f""\t""%d\t""%f""\t%d""\n", Clock[cont], No[cont], Clock[cont+10],No[cont+10], Clock[cont+20],No[cont+20]);

printf("\n");
for (i=0;i<=79;i++)
printf("#");
printf("\nDigite Qualquer tecla pra sair...");
fclose(fp);
getch();
exit(0);

}


encadeada * busca (int x, encadeada * ini)

{
encadeada *p;
no = 0;
p = ini -> prox;
while (p != NULL && p->conteudo != x){
p = p->prox;
no++;
}

return p;
}

void insere (int x, encadeada * q)
{
encadeada *nova;
encadeada *p;
nova = malloc (sizeof (encadeada));
nova->conteudo = x;
nova->prox = q->prox;
q->prox = nova;
for (p = ini->prox; (p != NULL)&& (p->prox!=NULL); p = p->prox){
if ( (p->conteudo)>(p->prox->conteudo)){
x = p->conteudo;
p->conteudo = p->prox->conteudo;
p->prox->conteudo = x;
}
}
}

void Remove (encadeada *p)
{
encadeada *morta;
if ( p->prox != NULL){
morta = p->prox;
p->prox = morta->prox;
}
else p->prox = NULL;
free (morta);
}

void imprimir (encadeada *ini)
{
encadeada *p;
for (p = ini->prox; (p != NULL); p = p->prox)
printf ("%d""\n", p->conteudo);
}