array-based list question

[kempofighter]

http://cplusplus.com/reference/stl/list/
http://cplusplus.com/reference/string/getline/
http://cplusplus.com/reference/string/string/

[TheTrace]

Ok, let me explain this all over again. This here in an example of the input.

delete("is",2)
print 1:This 2:is 3:an 4:an 5:icorrect 6:sntence
delete("an",3)
print 1:This 2:is 3:an 4:icorrect 5:sntence
delete("icorrect",4)
print 1:This 2:is 3:an 4:sntence
insert("incorrect",4)
print 1:This 2:is 3:an 4:incorrect 5:sntence
delete("sntence",5)
insert("sentence",5)
print 1:This 2:is 3:an 4:incorrect 5:sentence

The sentence "This is is an an icorrect sntence." becomes "This is a correct sentence."

As you can see, the input file includes the commands. It's delete, insert, ansd print.

I got this:

class List {
private:
Node data;
List *next;

insert_function() {
if (head == NULL) {
// This is the first node.
} else {
// Subsequent nodes
}
}


delete_function() {
prev->next = cur->next;

}

I'm not even sure if that is how I do this. I gotta load the input into the nodes. I need XX nodes. I don't know how large the input will be, I guess it needs to expand/shrink dynamically. I don't think it does right now. Do I even need a delete and insert function in the way I did it here? It needs to execute the commands from the input file to get the right sentence.

There are ”insert”, ”delete”, ”print” and ”neighbor” commands to manipulate the list. ”insert” and ”delete” have the word and position as input parameters. The word positions may change after a word is inserted or deleted. If the position given is invalid then the sentence should be unchanged.

And yes, I already checked several books etc. But I can no where find anything about this. They'll just tell me how to add/delete the heads, tails etc. But that's not what I need to do here. This is so confusing

[monarch_dodra]

You should try to use std::list instead of writing your own container. Learning how to use std::list correctly is much more important than being able to write your own list container.

I recommend you forget the whole file parsing part for now, and just try to create a list, print it, remove and insert elements into it.

That said, this problem begs for vectors rather than lists, but whatever.

Here is an example with vectors which should help get you started:

//helper printer
void print_vector(const std::vector<std::string>& iVector)
{
    std::vector<std::string>::const_iterator it = iVector.begin();
    std::vector<std::string>::const_iterator itEnd = iVector.end();
    for ( ; it != itEnd ; ++it )
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

int main()
{
    //The original container
    std::vector<std::string> myContainer;

    //initial fill
    myContainer.push_back("This");
    myContainer.push_back("is");
    myContainer.push_back("an");
    myContainer.push_back("an");
    myContainer.push_back("icorrect");
    myContainer.push_back("sntence");
    print_vector(myContainer);

    //delete("an",3)
    myContainer.erase(myContainer.begin()+3);
    print_vector(myContainer);

    //delete("icorrect",4)
    myContainer.erase(myContainer.begin()+3);
    print_vector(myContainer);

    //insert("incorrect",3)
    myContainer.insert(myContainer.begin()+3, "incorrect");
    print_vector(myContainer);

    //change "sntence","sentence",4)
    myContainer[4] = "sentence";
    print_vector(myContainer);
}

Doing the same thing with a list would be much harder because list are not random access.

[TheTrace]

I have to use linked lists. Probably a doubly linked list here. The input files will vary. It can be any sentence. I don't think it's difficult to use them here. I just odn't know how.

[monarch_dodra]

#include <iostream>
#include <string>
#include <list>

//helper printer
void print_vector(const std::list<std::string>& iVector)
{
    std::list<std::string>::const_iterator it = iVector.begin();
    std::list<std::string>::const_iterator itEnd = iVector.end();
    for ( ; it != itEnd ; ++it )
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

int main()
{
    //The original container
    std::list<std::string> myContainer;

    //initial fill
    myContainer.push_back("This");
    myContainer.push_back("is");
    myContainer.push_back("an");
    myContainer.push_back("an");
    myContainer.push_back("icorrect");
    myContainer.push_back("sntence");
    print_vector(myContainer);

    //delete("an",3)
    std::list<std::string>::iterator it = myContainer.begin();
    std::advance(it,3);
    myContainer.erase(it);
    print_vector(myContainer);
}

Use std::list. Don't write your own.

[TheTrace]

I can't use those. It msut be linked lists. And it would have to accept any input. Yours seems be be pre-defined.

[Xupicor]

It msut be linked lists.

List containers are implemented as doubly-linked lists

And what do you mean this seems to be predefined? Lists grow as you feed them (like vectors and others), you can feed it any number of strings (in this case) and it will hold them. You can then efficiently remove them, it doesn't matter where the element is (in vector, it is efficient to pop_back elements, but to remove them from the middle of a vector triggers costly memory reallocations).

Why are you so inclined to write your own container? Is the point of this task to write one and use it?

[TheTrace]

Under "initial fill". It would have to put whatever word in there. Looks to me like it dosen't do it. I don't have any experience with writing my own container though. I have never done this before. I'm supposed to use linked lists. So I can't say if you can use those. But I would use those if that sloves my problem.

public class SLinkedList { 
	protected Node head; // head node of the list 
	/** Default constructor that creates an empty list */ 
	public SLinkedList() { 
		head = null; 
	}
	// ... update and search methods would go here ... 
}

This would create the list. I guess I could use loops then to loop through it.

I can't use STL either.

[Paul McKenzie]

Under "initial fill". It would have to put whatever word in there. Looks to me like it dosen't do it. I don't have any experience with writing my own container though. I have never done this before. I'm supposed to use linked lists.

So why were you given this assignment? It isn't a trivial matter to write a container class in C++ correctly. Did you do any programming that would serve as a proper prerequisite to writing your own linked list?

You must know what you're doing in terms of usage of pointers and dynamically allocated memory (not just book knowledge, but know exactly how to achieve what you want using these concepts).

Regards,

Paul McKenzie

[monarch_dodra]

Under "initial fill". It would have to put whatever word in there. Looks to me like it dosen't do it.

That's because I just gave you an example to get started. It's up to you to fill it with the correct words.

I don't have any experience with writing my own container though. I have never done this before. I'm supposed to use linked lists. So I can't say if you can use those. But I would use those if that sloves my problem. ... I can't use STL either.

Any chance we could get an accurate problem description? First, you use arrays, then, you say it has to be a list, then you say you can't use stl, but you don't know if you can use it... This is all terribly confused.

I've given you all the generic help I could give you. I can still help if you need some specific advice on something precise though.