Previous Thread
Next Thread
Print Thread
Rate Thread
Joined: Jun 2004
Posts: 1
T
tszngau Offline OP
Junior Member
OP Offline
Junior Member
T
Joined: Jun 2004
Posts: 1
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;

}

Joined: Mar 2002
Posts: 524
D
Member
Offline
Member
D
Joined: Mar 2002
Posts: 524
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.

Joined: Mar 2002
Posts: 93
Junior Member
Offline
Junior Member
Joined: Mar 2002
Posts: 93
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

Link Copied to Clipboard
Member Spotlight
Phatal
Phatal
Houston, TX
Posts: 298
Joined: April 2004
Forum Statistics
Forums41
Topics33,840
Posts68,858
Average Daily Posts1
Members2,176
Most Online3,253
Jan 13th, 2020
Latest Postings
Where and how do you torrent?
by danni75 - 03/01/24 05:58 AM
Animation,
by JohanKaariainen - 08/15/19 01:18 AM
Blackbeard.....
by Gremelin - 10/03/18 07:02 PM
my old account still exists!
by Crime - 08/10/18 02:47 PM
Okay WTF?
by HenryMiring - 09/27/17 01:45 AM
The History Thread...
by Gremelin - 08/11/17 12:11 PM
My friend NEEDS your HELP!
by Lena01 - 07/21/17 12:06 AM
I'm having fun with this guy.
by gabithompson730 - 07/20/17 01:50 AM
I want to upgrade my phone
by gabithompson730 - 07/20/17 01:49 AM
Doom 3
by Cyrez - 09/11/14 08:58 PM
Amazon Gift Card Generator/KeyGen?te
by Gecko666 - 08/22/14 09:21 AM
AIM scene 99-03
by lavos - 09/02/13 08:06 AM
Planetside 2
by Crime - 03/04/13 07:10 AM
Beta Testers Wanted
by Crime - 03/04/13 06:55 AM
Hello Everyone
by Gremelin - 02/12/12 06:01 PM
Tracfone ESN Generator
by Zanvin Green - 01/18/12 01:31 PM
Python 3 issue
by Testing - 12/17/11 09:28 PM
tracfone airtime
by Drache86 - 07/30/11 03:37 AM
Backdoors and the Infinite
by ZeroCoolStar - 07/10/11 03:52 AM
HackThisZIne #12 Releaseed!
by Pipat2 - 04/28/11 09:20 PM
gang wars? l33t-wars?
by Gremelin - 04/28/11 05:56 AM
Consolidate Forums
by diggin2deep - 04/21/11 10:02 AM
LAN Hacking Noob
by Gremelin - 03/12/11 12:42 AM
Top Posters
UGN Security 41,392
Gremelin 7,203
§intå× 3,255
SilentRage 1,273
Ice 1,146
pergesu 1,136
Infinite 1,041
jonconley 955
Girlie 908
unreal 860
Top Likes Received
Ghost 2
Cyrez 1
Girlie 1
unreal 1
Crime 1
Powered by UBB.threads™ PHP Forum Software 7.7.5