array-based list question

Hello,

I'm trying to do the following. It's a code that corrects a sentence. That's one of the input files:

Code:

---

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
neighbors("is") 2:is previous:This next:an

---

So, first it's "This is is an an icorrect sntence", and after the code has sorted everything, it's gonna be "This is a correct sentence".

Because I don't know how large the input, I thought I would use this to get the input:

Code:

---

#include <iostream>
#include <fstream>
using namespace std;

int main () {
ofstream myfile;
myfile.open ("example.txt");
myfile << "Writing this to a file.\n";
myfile.close();
return 0;
}

---

Now I don't know how to create the array and populate it. Will this work?

Code:

---

template <class elemType>
bool arrayListType<elemType>::isempty() const
{
return (length == 0);
}
template <class elemType>
bool arrayListType::isFull() const
{
return (length == maxSize);
}

template <class elemType>
int arrayListType<elemType>::listSize() const
{
return lenght;
}
template <class elemType>
int arrayListType<elemType>::maxListSize() const
{
return maxSize;
}

Any help/input is appreciated! Thank you

---

Hm, nobody knows? Maybe my question wasn't clear. If so, just let me know :)

Not really clear, no. What is arrayListType and why can't you just use a std::vector or std::list?

That's just the name, and I'm not sure if I can. I think I have to do it this way. I'm just having troubles populating the array.
I guess I would have to make dynamic memory allocation. Any idea how?

Can't edit it anymore. Anyway, it's supposed to be array-based lists/linked lists. Wanted to add that.

"Array-based linked list" is a contradiction in terms. Arrays and linked lists are fundamentally different.

I suppose you could implement a linked list using an array to "allocate" the memory, but that's overly complicated for a school assignment.

I don't see how an array or linked list fits into this at all except that you might have a string which is an array of characters. The STL provides all sorts of containers such as std::list, std::deque, std::string, and so forth. I would be more concerned about your correction algorithm. I don't really understand your basic requirements at all. How does the program know what a correct sentence is?

The commands are in the input file, as you can see in my 1st post.

I guess I could load the string, read each line command by command and perform the actions accordingly?

Quote:

---

Originally Posted by TheTrace

The commands are in the input file, as you can see in my 1st post.

I guess I could load the string, read each line command by command and perform the actions accordingly?

---

Sure, you could. What does that have to do with an array based list? It is a really strange looking input file. The last line doesn't make any sense at all based on what you indicated that the final answer is supposed to be.

It needs to sort it. And I thought I could use an array-based list to solve it. But I now think linked lists are the way to go.

So just load the elements into a std::vector and call std::sort....

I'm just curious to what an array based list is? Is that some sort of variation of the classic deque implementation? Or a fancy way of saying vector?

Quote:

---

Originally Posted by monarch_dodra

I'm just curious to what an array based list is? Is that some sort of variation of the classic deque implementation? Or a fancy way of saying vector?

---

There are benefits for having an array in a linked-list. For starters, it is much easier to manage pointers, implementing reference count such as weak reference that would be difficult without it, and the allocation strategy is more flexible and easier to maintain. I use this approach frequently in a client-policy based design.

Ok, nevermind. Sorry. It's a linked lsit that has to be used. I think fstream would be the best option. I don't know how to load the input into the linked list though. Would be nice if someone could show me how to do this.

Thank you

Now what do you mean, how to put things into std::list or how to write your own implementation of singly/doubly linked list?

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

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

Code:

---

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:

Code:

---

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 :(

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:

Code:

---

//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.

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.

Code:

---

#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.

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

Quote:

---

It msut be linked lists.

---

Quote:

---

Originally Posted by http://www.cplusplus.com/reference/stl/list/

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?

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.

Code:

---

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.

Quote:

---

Originally Posted by 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 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

Quote:

---

Originally Posted by TheTrace

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.

Quote:

---

Originally Posted by TheTrace

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.