Inconsistent output while creating an adjacency list

Question

I have an undirected graph and need to represent it usind an adjacency list. I'm using an array of single linked lists. The input is:

11 18 3
1 8 4 7 7 10 11 10 2 1 2 3 8 9 8 3 9 3 9 2 5 6 5 11 1 4 10 6 7 6 2 8 11 7 11 6

First, I'm creating the array of lists. Then, to add the nodes into it, I read from the input and create 2 pointers. The first one holds as information the value that must be added into the list, while the second one is the current last element of the list. Then I bind the first one with the second, the fist one now becoming the last element of the list. I delete the pointers and create new ones to add in the inversed pair now, as the graph is undirected.

The output is inconsistent and never matches the expected output.

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("info.in");
struct LLSI {
    int info;
    LLSI* urm;
} * c, *d, *cap, *v[100], *e;
int main()
{
    int n, m, k, i, x, y;
    f >> n >> m >> k;
  //creating the array of lists
  for (i = 1; i <= n; i++) {
        v[i] = new LLSI;
        v[i]->urm = 0;
        v[i]->info = 0;
    }
    //adding the nodes into the adjacency list
    for (i = 1; i <= m; i++) {
        f >> x >> y;
        c = new LLSI;
        c->info = y;
        c->urm = 0;
        d = new LLSI;
        d = v[x];
        while (d->urm)
            d = d->urm;
        d->urm = c;
        v[x]->info++;
        d = c;
        delete c;
        delete d;
        d = new LLSI;
        d = v[y];
        while (d->urm)
            d = d->urm;
        c = new LLSI;
        c->info = x;
        c->urm = 0;
        d->urm = c;
        v[y]->info++;
        delete c;
        delete d;
    }
    //outputting the adjancecy list
    for (i = 1; i <= n; i++) {
        c = new LLSI;
        c = v[i];
        while (c) {
            cout << c->info << " ";
            c = c->urm;
        }
        cout << "\n";
        delete c;
    }
    return 0;
}

1) You state that the output you receive does not match the expected output, but you don't say what the expected output is. 2) Did you try stepping through your code with a debugger? — Algirdas Preidžius, Jan 15 '19 at 14:31
Are you coming from Java or C#? You are seriously misusing operators `new` and `delete`. You may want to read [a good C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) to learn the basics before jumping head first into coding. — Yksisarvinen, Jan 15 '19 at 14:32
Using one letter variable names make your code hard to understand. It's difficult to help with hard to understand code. You really should get out of the habit if using one letter variable names. — john, Jan 15 '19 at 14:58

john · Answer 1 · 2019-01-15T15:06:12.233

This

//outputting the adjancecy list
for (i = 1; i <= n; i++) {
    c = new LLSI;
    c = v[i];
    while (c) {
        cout << c->info << " ";
        c = c->urm;
    }
    cout << "\n";
    delete c;
}

should be this

//outputting the adjancecy list
for (i = 1; i <= n; i++) {
    c = v[i];
    while (c) {
        cout << c->info << " ";
        c = c->urm;
    }
    cout << "\n";
}

I removed the new and delete. Not sure why you think you need to create a new list just to iterate through a list.

You have the same error in the earlier loop. This

//adding the nodes into the adjacency list
for (i = 1; i <= m; i++) {
    f >> x >> y;
    c = new LLSI;
    c->info = y;
    c->urm = 0;
    d = new LLSI;
    d = v[x];
    while (d->urm)
        d = d->urm;
    d->urm = c;
    v[x]->info++;
    d = c;
    delete c;
    delete d;
    d = new LLSI;
    d = v[y];
    while (d->urm)
        d = d->urm;
    c = new LLSI;
    c->info = x;
    c->urm = 0;
    d->urm = c;
    v[y]->info++;
    delete c;
    delete d;
}

should be this

//adding the nodes into the adjacency list
for (i = 1; i <= m; i++) {
    f >> x >> y;
    c = new LLSI;
    c->info = y;
    c->urm = 0;
    d = v[x];
    while (d->urm)
        d = d->urm;
    d->urm = c;
    v[x]->info++;
    delete c;
    d = v[y];
    while (d->urm)
        d = d->urm;
    c = new LLSI;
    c->info = x;
    c->urm = 0;
    d->urm = c;
    v[y]->info++;
    delete c;
}

I removed d = new LLSI; and delete d;. Use new to create a new object. If all you want is to point to an existing object you don't need new or delete.

The other obvious improvement is that you have a lot of repeated code that differs only on whether you are operating on list x or list y. That repeated code should be placed in a seperate function.

score 0 · Answer 2 · answered Jan 15 '19 at 15:31

Thank you for the advice, for some reason my teacher taught me I should use new and delete, although this makes more sense. The code shows no output now, but this is how the new code looks like:

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("info.in");
struct LLSI {
    int info;
    LLSI* urm;
} * c, *d, *cap, *v[100], *e;
int main()
{
    int n, m, k, i, x, y;
    f >> n >> m >> k;
    for (i = 1; i <= n; i++) {
        v[i] = new LLSI;
        v[i]->urm = 0;
        v[i]->info = 0;
    }
    for (i = 1; i <= m; i++) {
        f >> x >> y;
        c = new LLSI;
        c->info = y;
        c->urm = 0;
        d = v[x];
        while (d->urm)
            d = d->urm;
        d->urm = c;
        v[x]->info++;
        delete c;
        d = v[y];
        while (d->urm)
            d = d->urm;
        c = new LLSI;
        c->info = x;
        c->urm = 0;
        d->urm = c;
        v[y]->info++;
        delete c;
    }
    for (i = 1; i <= n; i++) {
        c = v[i];
        while (c) {
            cout << c->info << " ";
            c = c->urm;
        }
        cout << "\n";
    }
    return 0;
}

Well now I look at it again, you should remove the `delete c;`. If you create an object whith `new` and add it to a list you shouldn't delete it until you remove it from the list. Since no part of your code is about removing items from lists you shouldn't be deleteing anything. — john, Jan 15 '19 at 19:04
I'm not saying that change will fix your program. I'm just pointing out the obvious stuff, there could be many other errors. — john, Jan 15 '19 at 19:05
Thank you, removing the `delete c;` did the job, it outputs the expected result. — Jake Wright, Jan 16 '19 at 07:15

Inconsistent output while creating an adjacency list

2 Answers2