Linked lists

[XodoX]

I'm trying to do the following using a linked list.

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

It's like a sentence editor. It follows the commands on the left side ( print, delete, insert) etc. so that "This is is an an icorrect sntence." becomes "This is an incorrect sentence."
Using fstream to read the text file this is from and load it into the nodes. Each word in a seperate node. I have no idea how to build this linked list. The book only talks about deleting first node, deleting last node, retrieve data from first node etc. But that is not what I am looking for, I think.

Would this do it?

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

I have been trying forever to figure this out. Help is really appreciated!!

[myk45]

Please see my next post. i posted it twice instead of editing. Sorry about that.

[myk45]

Ok.

First of all, you need a self-reference to the structure/class.

something like this:

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

So there goes the basic class.
Now, lets add some insert and delete methods.

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

delete() {
        // Here, i'm assuming you delete via a number (say node 2 or something like that)

      
      // Now, loop till you get the node.
      // keep a track of the previous node.
      prev->next = cur->next; // You make the previous node's next node as the mext  node of the current node.

     // Now, free() or delete the current node.
}

Hope this helps.

[XodoX]

Thanks. So, I basically do it like this, I implement it...

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

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


delete() {
        // Here, i'm assuming you delete via a number (say node 2 or something like that)

      
      // Now, loop till you get the node.
      // keep a track of the previous node.
      prev->next = cur->next; // You make the previous node's next node as the mext  node of the current node.

     // Now, free() or delete the current node.
}

};

And do the operations right there?

[myk45]

Yeah. Thats basically it. Hmm you might wanna look into a good Data Structures book if you need more help and detailed explanation.

[XodoX]

You can't use delete and insert like this though. It's a reserved word, isn't it? I do have a good book, but it dosen't help me here because it just covers the basics.. like retrieve data from first/last node etc. I don't need all this here.

BTW. The input already includes the commands/reserved words... delete, insert etc. Can I not just load it into the node and it automatically knows what to do?

[myk45]

Hmm i was implying the insert and delete operation in the List. Yeah you are right. delete is a keyword.

Hmm i'm a little confused now. i thought what you wanted was a basic insert/delete operation on a list.

>>BTW. The input already includes the commands/reserved words... delete, insert etc. Can I not just load it into the node and it automatically knows what to do?

Can you please elaborate with an example?

[XodoX]

This input file

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

already has delete, insert, print etc. So I guess the code will already know what to do. Man, I didn't think this was so difficult :( There's also a delete and instert algorithm. Maybe use that?

[myk45]

Ok, i got it.. Well your idea of creating a linked list seems good enough.

But before that, you need to check what your operation is going to be.

Now, alternate lines have commands and sentences.
say :
first line: command
next line: sentence
third line: command
so on...

So,

check for these conditions first:

if (fscanf(file_ptr, "delete(%s)", str) > 0)
		/* set a flag-> say op = 1 */
else if (fscanf(file_ptr, "insert(%s)", str) > 0)
		/* set the flag-> say op = 2 */

Now, str has your operation. (file_ptr is the file pointer).
ie str has "is", 3. So you need to get the word and the number.

Also, check this code for what exactly i meant:

#include <stdio.h>

int main(void)
{
	char str[10];

	if (fscanf(stdin, "delete(%s)", str) > 1)
		printf("hello");
	return 0;
}

So, now you know what operation is to be performed.Half the task is done :)(hopefully).

Now,
Read the second line. Build a linked list of the words(separated by spaces). Then perform operations.

In fact,
print 1:This 2:is 3:an 4:sntence
The numbers wont be necessary. You can loop through the number of spaces and perform the exact operation.

PS: Sorry for mixing up so many functions generally used in C.

[XodoX]

Thank you very much.

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

That creates the list. But I don't know if I can do it that way because I don't know how large the list needs to be. And I'm assuming that the search methods go right there where I put that comment.
The code you gave me earlier is not needed then, is it? And, I wanted to use fstream to get the input from the file. So the fscanf wouldn't be needed.

[myk45]

Here is some more code: i found the problem interesting.

Create a file called "new.txt" and put the following:

delete("is",3)
This is is a sentence.

#include <stdio.h>

int main(void)
{
	char str[10], c;
	int flag = 1;
	FILE *fp = fopen("new.txt", "r");

	/* Check what the command is and set the respective flag */
	if (fscanf(fp, "delete%s", str) > 0)
		flag = 1;
	else if (fscanf(fp, "insert%s", str) > 0)
		flag = 2;
	
	if (flag == 1)
		printf("Delete is the command and %s is to be performed", str);
	else if (flag == 2)
		printf("Insert is the command and %s is to be performed", str);

	/* Now, go to the next line */
	while ( (c = fgetc(fp)) != '\n')
		   ;

	fscanf(fp, "%[^\n]", str);
	printf("\n%s", str);

	getchar();

	return 0;
}

Please test the above code: You basically need to put it in a loop.

So, now, you have the command(ie operation to be performed)
You have the string to be inserted/deleted.

It will be of the form:
("xxxxx",pos)

where
xxxxx is the word
pos is the position.

Now, you need to scan through that and find the word.(will do that later)

Now,
you have the sentence:
ie
This is is a sentence.

Now, build a linked list out of this.

The only part left is scanning the word to be inserted and the position. can be done by sscanf() i suppsose.

Again, sorry for using so many C functions. But im not sure if they are available in C++.

[myk45]

>>That creates the list. But I don't know if I can do it that way because I don't know how large the list needs to be. And I'm assuming that the search methods go right there where I put that comment.
The code you gave me earlier is not needed then, is it? And, I wanted to use fstream to get the input from the file. So the fscanf wouldn't be needed.

Well, im not sure if there are such functions in C++. Is it mandatory that you use fstream? If yes, i have not used it much myself.

You generally use lists when you cannot predict how big it may grow, isn't it?

Also, creating a list will not be a problem. You can loop through till you get a newline.

[XodoX]

Yes, that code works. I tested it. Fstream isn't mandatory, but I found it to be the most suitable for this kind of input.

I understand your code there.I have no experience with C though. I don't know how I would implement this.

The list is created I think. That code I posted should be ok. And that code would come right after it.

[XodoX]

P.S. I think your code there would go through the entire list too, right? Because it looks for insert/delete. The input I have there is just an example. It can be any other sentence/order as well.

[myk45]

>>I understand your code there.I have no experience with C though. I don't know how I would implement this.

Well, i don't know how that can be done in C++.

Anyways, is the list creation over? i mean did you extract single words from the sentence?

The struct you had mentioned can be like this ( i mean the node)

struct Node {
     char str[10];
     struct Node *next;
};

So, that would be the Node you had mentioned in your first post. Extract each word from the sentence and build a list.

sscanf() can be used for that purpose. im not sure of a C++ solution for that.

So,

the list is built like this:

while (not_end_of_sentence) {
// extract next word
// insert word into the list
}

[myk45]

>>I think your code there would go through the entire list too, right? Because it looks for insert/delete. The input I have there is just an example. It can be any other sentence/order as well.

i did not quite follow you. Arent the commands and sentences in alternate lines?
And arent the commands limited? like insert, delete, etc? So, what is the problem?

[XodoX]

You used fscanf. This would not put it into the node, would it? Wouldn't that pull it directly from the file?

So I basically have to create the node and go through the sentence like you did in your first post on this page.

[XodoX]

i did not quite follow you. Arent the commands and sentences in alternate lines?
And arent the commands limited? like insert, delete, etc? So, what is the problem?

No, nvm. Just what I posted in my first post is in there. I thought you could work with the delete, print, insert that's in there because those are reserved words but you can't. Just got to loop through it and look for delete, print, insert to have it execute it.

[myk45]

>>You used fscanf. This would not put it into the node, would it? Wouldn't that pull it directly from the file?

Precisely. You need to get the words from the sentence and build a list. Please get back with the progress. i found the problem really interesting.