Your browser does not seem to support CSS. If images appear below, please disregard them.
toggle
May
S M T W T F S
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
Sponsored Links
Latest Postings
Topic Options
Rate This Topic
#17133 - 06/04/04 06:30 AM Anyone could help me change these codes ? URGENT, help!!
Joined: Jun 2004
Posts: 1
tszngau Offline
Junior Member
tszngau Offline
Junior Member

Joined: Jun 2004
Posts: 1
Australia
I have an assignment due soon, is there any one could help me change it looks difference?

this is a copy of work from my friend, i really don't know muuch about coding, it dues in few hours, could anyone help me change it in a different manner??

this assignemnt is about Prim's algorithm, and find the minimum span tree problem, it requires to use an adjacency list to store the values, and out put will be the maximum value of the vertex.


Code:
#include <stdio.h>
#include <stdlib.h>
#include "list.h"



node_ptr create_list()
{
    node_ptr header_node = (node_ptr)malloc(sizeof(struct node));
    header_node->to_vertex = -1;
    header_node->weight = -1;
    header_node->next = NULL;
    return header_node;
}

void destroy_list(node_ptr header_node)
{
    node_ptr current = header_node; /* Dynamically allocated memory to header_node node */
    node_ptr temp;

    while(current){
        temp = current;
        current = current->next;
        free(temp);/* Free the dynamically allocated memory */

    }
}

void insert_at_front(node_ptr header_node, int w, int to_vertec)
{
    node_ptr new_node = (node_ptr)malloc(sizeof(struct node));/* Dynamically allocated memory to new_node */
    new_node->to_vertex = to_vertec;
    new_node->weight = w;
    new_node->next = header_node->next;
    header_node->next = new_node;
}

span_ptr create_span_list()
{
    span_ptr span_header = (span_ptr)malloc(sizeof(struct span_tree));
    span_header->total_weight = -1;
    span_header->next = NULL;
    return span_header;
}

void destroy_span_list(span_ptr min)/* Function to destroy the span_list */
{
    span_ptr current = min;
    span_ptr temp;

    while(current){ /*while it's not the end,keep going*/
        temp = current;
        current = current->next;
        free(temp); /*free it one by one*/
    }
}

void span_insert_at_front(span_ptr min, int weight)
{
    span_ptr new_node = (span_ptr)malloc(sizeof(struct span_tree));
    new_node->total_weight = weight;
    new_node->next = min->next;
    min->next = new_node;
}

/*============functions for table====================*/

table create_table(int max_span)
{
    table t;
    
    t = (table)malloc(max_span * sizeof(struct table_property));
    return t;
}

void destroy_table(table t)
{
    free(t);
}

void start_table(table t, int max_span)
{
    int i;
    
    for(i=0; i<max_span; i++){   /*create the dummy header node*/
        t[i].known = 0;
        t[i].distance = infinity;
        t[i].path = Not_a_Vertex;
    }
}

void set_initial_vertex(table t, int initial_vertex)
{
    t[initial_vertex].distance = 0; /*set the start vertex to be zero*/
}

int nearest_unknown_vertex(table t, int max_span)
{
    int i;
    int v = Not_a_Vertex;
    int dist = infinity;

    for(i=0; i<max_span; i++){
        if(!t[i].known && t[i].distance < dist){
            dist = t[i].distance;
            v = i;
        }
    }
    return v;
}

int find_next(table t, int max_span)
{
    int i, what_next=0;

    for(i=0; i<max_span; i++){
        if(!t[i].known && t[i].distance == infinity){
            what_next = i;
            break;
        }
    }
    return what_next;
}

int find_maximum(span_ptr min)
{
    int maximum = 0;
    span_ptr current;

    for(current=min->next; current; current=current->next){
        if(current->total_weight > maximum){
            maximum = current->total_weight;
        }
    }
    return maximum;
}

/*====================prims algorithm===============================*/

void prims(table t, node_ptr g[], int max_vertex, span_ptr span_tree)
{
    int v;
    int w;
    int number_of_vertex = 0;
    node_ptr current;

    span_insert_at_front(span_tree, 0);    

    while(1){

        v = nearest_unknown_vertex(t, max_vertex);
        printf("Nearest Vertex:%d\n",v);


        if (v == Not_a_Vertex){
            if(number_of_vertex == max_vertex){
                break;
            }else{
                v = find_next(t, max_vertex);
                set_initial_vertex(t,v);
                span_insert_at_front(span_tree, 0);
            }
        }
    
        t[v].known = 1;            
        number_of_vertex++;        
        span_tree->next->total_weight += t[v].distance;    

    
        for(current = g[v]->next; current; current=current->next){
            w = current->to_vertex;
            if(!t[w].known){
                if(current->weight < t[w].distance){
                    /* Update the all t[w] value in the table */
                    t[w].distance =    current->weight;
                    /*printf("the current weight:%d\n",w);*/
                    t[w].path = v;
                }
            }
        }

    }
}
--------------------------------------------------------------------------
#ifndef _LIST_H
#define _LIST_H

#define Not_a_Vertex (-1)
#define infinity (9999)

typedef struct node *node_ptr;
typedef struct table_property *table;
typedef struct span_tree *span_ptr;

struct node
{
    int to_vertex;
    int weight;
    node_ptr next;
};

struct table_property
{
    int known; /*to store the know vertex*/
    int distance;/*how far are they*/
    int path;
};

struct span_tree
{
    int total_weight; /*this is to store some disconnected graphs weight*/
    span_ptr next;
};

node_ptr create_list();

void destroy_list(node_ptr header_node);

void insert_at_front(node_ptr header_node, int w, int to_vertec);

span_ptr create_span_list();

void destroy_span_list(span_ptr min);

void span_insert_at_front(span_ptr min, int weight);

table create_table(int max);

void destroy_table(table t);

void start_table(table t, int max);

void set_initial_vertex(table t, int initial_vertex);

int nearest_unknown_vertex(table t, int max);

int find_next(table t, int max);

void prims(table t, node_ptr g[], int max_vertex, span_ptr span_tree);

int find_maximum(span_ptr min);


#endif
----------------------------------------------------------
#include <stdio.h>
#include "list.h"

int main(){
    int i;
    int number_of_vertex, number_of_edges;
    int weight, smallest, biggest, maximum;
    table t;
    node_ptr g[10000];
    span_ptr span_list;    

    scanf("%d %d", &number_of_vertex, &number_of_edges);

    /* Create list and initialise g[i] */
    for(i=0; i<number_of_vertex; i++){
        g[i] = create_list();
    }

    /* Read graph */    
    for(i=0; i<number_of_edges; i++){
        scanf("%d %d %d", &weight, &smallest, &biggest);
        insert_at_front(g[smallest], weight, biggest);
        insert_at_front(g[biggest], weight, smallest);
    }

    /* Table is created and initialised */
    t = create_table(number_of_vertex);

    start_table(t, number_of_vertex);

    /* Set the starting vertex as vertex 0 */
    set_initial_vertex(t, 0);

    /* span_list is created */
    span_list = create_span_list();

    /* Prims algorithm process and record them into the table */
    prims(t, g, number_of_vertex, span_list);

    /* Get and printf the maximum value from span_list */
    maximum = find_maximum(span_list);
    printf("%d\n", maximum);

    /* Destroy the adjacency list, table and span_list */
    for(i=0; i<number_of_vertex; i++){
        destroy_list(g[i]);
    }

    destroy_table(t);/*destroy the table after successfully get the minimum tree*/

    destroy_span_list(span_list);/*destroy the span_list after successfully get the minimum tree*/

    return 0;

}

Top
Sponsored Links
#17134 - 06/05/04 06:52 AM Re: Anyone could help me change these codes ? URGENT, help!!
Joined: Mar 2002
Posts: 524
dashocker Offline
Member
dashocker Offline
Member

Joined: Mar 2002
Posts: 524
Cornfields everywhere...
Um, question...does your friend have or did he have this same teacher? Otherwise, it's not likely anyone is going to notice the cheating. And if you don't know much about coding, why are you in a class that seems to require such complex mathematically-related programming? Just curious.

Top
#17135 - 09/29/04 12:29 AM Re: Anyone could help me change these codes ? URGENT, help!!
Joined: Mar 2002
Posts: 93
zenon Offline
Junior Member
zenon Offline
Junior Member

Joined: Mar 2002
Posts: 93
Sweden
Agree.
I usually give a lot of constructive criticism
but this is just 2 much on 2 short time.
And honestly, I don´t think annyone would code such a thing for you because you want it.


- "It's not my code that's useless
it's you loosers being unable to
apprecitate it because of your
lack of skills!"
/zenon - C++ master Apprentice
Top

Member Spotlight
Gremelin

Gremelin
Portland, OR; USA
Posts: 7,194
Joined: February 2002
Show All Member Profiles 
Forum Statistics
Forums46
Topics45,724
Posts80,892
Members2,157
Most Online1,567
Apr 25th, 2010
Top Posters(All Time)
UGN Security 38,888
Gremelin 7,194
SilentRage 1,273
Ice 1,146
pergesu 1,136
Infinite 1,041
jonconley 955
Girlie 908
unreal 860
Newest Members
Herbert_Sherbert, codemauve, Lillysdragon1984, Brewwit, boa
2157 Registered Users
Who's Online Now
0 registered members (), 4 guests and 2 spiders.
Latest News