Insert a Link to a Dynamic Linked List

[iclearwater]

Hi,

The following programme is transcribed from a tutorial I am learning. With the programme, the tutor illustrated how to insert a link to the middle of a dynamic linked list.

I have the questions (Q)as below:
Q1: From Line 82 to Line 86.
I think it is necessary to declare "list->next=NULL" since "list" is the last one.

if(num>head->num)
{
head->next=list;
list->next=NULL; //I don't understand the tutor didn't write this.)
}

Because on the other sections about dynamic linked list, he always declared the next to the last one as "NULL". However I don't understand why the tutor didn't do so this time.

Q2: In Line 73, the tutor underlines to add "return". But why is there no such a request about adding "return" to other blocks.

For example, why was "return" not written between Line 82 and Line 86 as below:

if(num>head->num)
{
head->next=list;
return;// why was "return" missing?
}

Could anyone please help me with the questions? Many thanks!

 #include<iostream>

using namespace std;
class book
{
public:
	int num;
	float price;
	book* next;
};
book* head=NULL;

book* Create()
{
	book *p1,*p2;
	p1=new book;
	p2=p1;
	head=p1;
	cout<<"Please enter the book No.. Press 0 to return."<<endl;
    cin>>p1->num;
	if(p1->num!=0)
	{
		cout<<"Please enter the book price"<<endl;
		cin>>p1->price;
	
	}
	else 
	{
		delete p1; p2=NULL; head=NULL; return head;
	}
	while(p1->num!=0)
	{
		p2=p1;
		p1=new book;
        cout<<"Please enter the book No.. Press 0 to return. "<<endl;
		cin>>p1->num;
		
		if(p1->num!=0)
		{
		cout<<"Please enter the book price"<<endl;
		cin>>p1->price;
	
		}
		p2->next=p1;
	}
	delete p1;
	p2->next=NULL;
	return head;
}

void ShowBook(book* head)
{
	cout<<endl;
	cout<<"The books info as below:"<<endl;
	while(head)
	{
		cout<<"book number: "<<head->num<<"\t";
		cout<<"book price:"<<head->price<<endl;
		head=head->next;
	}
}


void InsertMiddle(book* head, int num, float price)
{
	book* list=new book;
	list->num=num;
	list->price=price;
	if(num<=head->num) 
	{
		list->next=head;
		::head=list;
		return;
	}

	book* temp=NULL;
	while((num>head->num)&&(head->next!=NULL))
	{
		temp=head;
		head=head->next;
	}
	if(num>head->num)
	{
	  head->next=list;
	 
	}
	else
	{
		temp->next=list;
		list->next=head;
	}
	return;
}
int main()
{
 
 head=Create();
 ShowBook(head);
 int BookNum;
 float price;
 cout<<"Please enter the book number you want to insert"<<endl;
 cin>>BookNum;
 cout<<"Please enter the book price for the book number: "<<endl;
 cin>>price;
 InsertMiddle(head,BookNum, price);
 ShowBook(head);
 return 0;
}

[gunnerfunner]

I ran your program with book numbers and prices (1, 1.1), (2, 2.2) for Create() and then trying to insert book (4, 4.4) and the program aborted - see here: http://pastie.org/10993004 (if the link doesn't work you can try running the program with these data yourself)

The reason this is happening is because you haven't told the program how to insert numbers at the end - which would happen if the inserted book's number is greater than any in the current list

#include<iostream>
#include<string>
//using namespace std;//AVOID
class book
{
public:
	int num;
	float price;
	book* next;//consider using smart pointers
};
book* head=NULL;//leave space b/w operator symbols and text throughout (easier to read)

book* Create()
{
	book *p1,*p2;
	p1 = new book;
	p2=p1;
	head=p1;
	std::cout<<"Please enter the book No.. Press 0 to return."<<'\n';
    std::cin>>p1->num;
	if(p1->num!=0)
	{
		std::cout<<"Please enter the book price"<<'\n';
		std::cin>>p1->price;

	}
	else
	{
		delete p1; p2=NULL; head=NULL; return head;
	}
	while(p1->num!=0)
	{
		p2=p1;
		p1=new book;
        std::cout<<"Please enter the book No.. Press 0 to return. "<< '\n';
		std::cin>>p1->num;

		if(p1->num!=0)
		{
		std::cout<<"Please enter the book price"<<'\n';
		std::cin>>p1->price;

		}
		p2->next=p1;
	}
	delete p1;
	p2->next=NULL;
	return head;
}

void ShowBook(book* head)
{
	std::cout << '\n';
	std::cout << "The books info as below:" << '\n';
	while(head)
	{
		std::cout << "book number: " << head -> num << '\n';
		std::cout << "book price:" << head -> price << '\n';
		head=head->next;
	}
}
void InsertMiddle(book* head, int num, float price)
{
	book* list = new book;//try not to use names like list that are C++ defined names
	bool inserted = false;//to keep track
	list -> num = num;
	list -> price = price;
	while (!inserted)
    {
        if(num <= head -> num)
        {
            list -> next = head;
            head = list;
            inserted = true;
            break;
        }
    	else
        {
            book* temp = head;//declared and assign in one step, no NULL required
            while((num > temp -> num) && (temp -> next != nullptr))
            {
                if( num <= temp -> next -> num)//insert b/w temp and temp-> next
                {
                    list -> next = temp -> next;
                    temp -> next = list;
                    inserted = true;
                    break;
                }
                else
                {
                    if(temp -> next -> next)//make sure we don't run off the back of the list
                    {
                        temp = temp -> next;
                    }
            }
            if(inserted == false)
            {
                if(num <= temp -> next -> num)//insert as second last element
                {
                    list -> next = temp -> next;
                    temp -> next = list;
                    inserted = true;
                    break;
                }
                else
                {
                    temp -> next -> next = list;//insert as last element
                    list -> next = nullptr;
                    inserted = true;
                    break;
                }
            }
        }
    }
}
}
int main()
{

 head=Create();
 ShowBook(head);
 int BookNum;
 float price;
 std::cout<<"Please enter the book number you want to insert"<<'\n';
 std::cin>>BookNum;
 std::cout<<"Please enter the book price for the book number: "<<'\n';
 std::cin>>price;
 InsertMiddle(head,BookNum, price);
 ShowBook(head);
 return 0;
}

[dhayden]

Q1: From Line 82 to Line 86.
I think it is necessary to declare "list->next=NULL" since "list" is the last one.

I agree. Nice catch.

Q2: In Line 73, the tutor underlines to add "return". But why is there no such a request about adding "return" to other blocks.

For example, why was "return" not written between Line 82 and Line 86 as below:

After executing lines 82-86, control transfers to the return at line 92, so adding an extra one after line 85 is not necessary.

In contrast, without the return at line 73. control would continue at line 76, with bad results.

I'm not impressed with the tutorial's code:
- variable names like p1 and p2 aren't very meaningful, especially in a tutorial
- The code to insert the 2nd through nth items in Create is functionally the same as the code in InsertMiddle. You shouldn't duplicate functionality so Create() should call InsertMiddle()
- The code is buggy, as you've found.
- InsertMiddle() has a local variable named head, which is very confusing.
- InsertMiddle(), which must be called on a non-empty list, has 3 different cases that it deals with, so the program overall has 4 different case for inserting into the list. Yuck! If properly coded, it can be done with a single case.

[iclearwater]

Hi gunnerfunner and dhayden,

It's very kind of you to spend your precious time to help me out, and to fix and comment on the code in detail. Thank you very much!

I started from the scratch. The reason for me to adopt this tutorial is because it has both videos and book. The tutor illustrated each step on the videos, which are easier for me to access. I've realised the tutorial, which I'm learning, doesn't seem very desireable, as dhayden commented here and another forumite commented on another thread of mine.

In order not to mix up my previous questions(Q1, Q2) which have been sovled, I start the new question number from Q3...

Q3: Do you think "C++ Primer Plus" is a good book for beginners? I want a better book after I finish learning this tutorial.

The tutor commented on his video that "C++ Primer" is regarded as the Holy Bible of C++, but it is too difficult to access for a beginner. I searched from the Internet, and found some people recommended "C++ Primer Plus". I knew it is a well-known book.


Q4: Line 3, Post 2 by gunneerfunner:

//using namespace std;//AVOID

Do you mean I should use "std::cout/cin" all the time?

In page 43, C++Primer Plus (Edition 6), the author wrote the following code. I mean he used "using namespace std;".

#include <iostream>
int main()
{
using namespace std;
cout<< " Come up, C++ me some time." ;
cout << endl;
cout<<"You won't regret it."<<endl;
}

Q5: Line 11, Post 2 by gunneerfunner:

book* head=NULL;//leave space b/w operator symbols and text throughout (easier to read)

What does "b/w" mean?

Could any of you answer again?

Many thanks!

[gunnerfunner]

Q3: Do you think "C++ Primer Plus" is a good book for beginners?

If you mean the one by Stephen Prata, 5th edition, then I'd recommend it though it's a bit out of data specially since C++ has changed so much since C++11 that this book doesn't cover

//using namespace std;//AVOID

http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice

What does "b/w" mean?

b/w == "between"

[iclearwater]

Thank you very much for your help again, gunnerfunner.

I don't understand some suggestions you made in the programme, i.e. smart pointer, because the tutor doesn't introduce it /I haven't learnt it in his tutorial.

I searched "smart pointer" from the Internet, but I don't understand those articles either, as my knowledge of C++ is so little. I think I will learn it and more when I adopt a better book. I don't want you to spend your precious time on teaching me how to use smart pointer.

For the first stage I just try to understand the tutorial, and imitate; and then I'm able to improve them in the future.

Currently I'll have to limp along with the code the tutor wrote.

Have great day! :)

[iclearwater]

Hi gunnerfunner,

Q6: I tried to follow the suggestion of yours and removed "using namespace std" from the code and replaced with "std :: cin / cout", but my compiler Visual C++6.0 reminded there are errors as error C2065: 'endl' : undeclared identifier.

Because the original code here is a bit long and there are several "endl", I wrote two simple codes as below to test, but neither of them works. When I added "using namespace std", the problem was solved.

#include <iostream>
//using namespace std;
int main()
{
	std :: cout  << "Hello World";
	std :: cout  << endl;
	return 0;
}

#include <iostream>
//using namespace std;
int main()
{
	std :: cout  << "Hello World"  << endl;
	return 0;
}

Could you please suggest how to fix it? Thank you!

[gunnerfunner]

You'd need the std namespace also to use the endl manipulator: http://en.cppreference.com/w/cpp/io/manip/endl
In this case you have 3 options:
(a) using namespace std directive: http://stackoverflow.com/questions/16152750/using-directive-vs-using-declaration-swap-in-c - but we alread know that is not good practice, and so ...
(b) using namespace std declaration for endl and, perhaps, cout, cin - i.e. declaring use of some of the std namespace components in the global namespace (in your case just before int main()) and then using them in your program without the std:: qualifier - above link also
explains the directive/declaration differences
(c) or not using endl at all if you just want to insert a newline character and replacing it with "\n", so:

std::cout << "Hello World" << std::endl
//becomes 
std::cout << "Hello World \n";

std::endl places a newline chararcter and flushes the output buffer: http://en.cppreference.com/w/cpp/io/manip/flush whereas "\n" just places the newline character

[iclearwater]

Thank you very much again, gunnerfunner.

I am sorry keep asking you questions. Before closing this thread, would you please help me out with the following question about how postfix increment works in the same programme of Post 1, at your convenience?

Q7: On another section, the tutor taught how to cout the quanity of the books. The code is mostly from the same tutorial, except I changed a little bit, i.e. I adopt "std::cout", etc as you've advised above. I removed "void InsertMiddle(book* head, int num, float price), because it is irrevant to my question now.

The programme is correct, but I don't understand how it works, when it comes postfix increatment from Line 51 to Line 60.

If there are a total of 4 books, and the book numbers are 1, 2, 3, 4.

And it goes to while ( head)

when num==0, 1=2; //1 is the head, and 2 is head -> next
when num==1, 2=3;
when num==2, 3=4;

I think there are just three loops totally, but how does the programme calculate there're 4 loops. I know I am wrong about this. Would you please correct me ?

#include <iostream>

class book
{
public:
    int num;
    float price;
    book* next;
};
book* head = NULL;
book* create()
{
    book *p1, *p2;
    p1 = new book;
    head = p1;
    p2 = p1;
	std::cout << "Please enter a book number. Press 0 to return. \n";
	std::cin >> p1 -> num;
    if (p1->num != 0)
    {
		std::cout << "Please enter the book price.\n";
		std::cin >> p1 -> price;
    }
    else
    { delete p1; p2 = NULL; head = NULL; return head;}
    while(p1->num != 0)
    {
        p2 = p1;
        p1 = new book;
		std::cout << "Please enter a book number. Press 0 to return. \n";
		std::cin >> p1 -> num;
        if (p1->num != 0)
        {
			std::cout << "Please enter the book price.\n";
			std::cin >> p1->price;
        }
        p2->next = p1;
    }
    delete p1;
    p2 -> next = NULL;
    return head;
}
void showbook(book* head)
{
  while(head != 0)
  {
	  std::cout<<"Book No:  "<< head->num << "\t" << "Book Price:  " << head->price << "\n";
      head = head -> next;
  }
}
int GetBookNum(book* head)
{
    int num = 0;
    while(head)
    {
        num++;
        head = head -> next;
    }
    return num++;
}
 
int main()
 
{
 head = create();
 showbook(head);
 std::cout << "The Quantity of total books: " << GetBookNum(head) << "\n";
 return 0;
}

[gunnerfunner]

post vs pre fix increment:
http://stackoverflow.com/questions/17366847/what-is-the-difference-between-pre-increment-and-post-increment-in-the-cycle-fo

I think there are just three loops totally

as there are four books why do you think so? don't forget there's one book corresponding to head as well and then 1, 2, 3. another way of writing the function would be:

int GetBookNum(const book* head)
{
    int num = 0;
    while(head)
    {
       num++;
        head = head -> next;
    }
    return num;
}

I'd prefer this as I think your version is unnecessarily indirect

[iclearwater]

My bad! I didn't transcribe the code correctly from the tutorial. What the tutor wrote was exactly same as yours. He made GetBookNum to return to an int, and made "return" as "num".

Let's say if I input 4 books with the programme sequently, then there are four nodes: node 1 (head), node 2, node 3, node 4.

I try to simulate how the programme works as below:

When num == 0, node 1 (head) = node 2;
when num == 1, node 2 (head) = node 3;
when num == 2, node 3 (head) = node 4;
when num == 3, node 4 (head) = ??? //The programme will execuate num==3, because node 4 is not "0". correct? The loops of while quits only if "head ==0".

The programme will make 4 loops, as when num is 3, though node 4 becomes head, and the last one.

Can I understand the function of "while" runs in this way?

[gunnerfunner]

head = head -> next;

so by the end of the fourth loop head has gone beyond the end of the list and that's why the while() loop stops

[iclearwater]

gunnerfunner, I greatly appreciate that you spent your precious time patiently helping me out time and again. You're very very kind!

Have a great day! :)