The C++ class is used to implement the operation methods of adding deleting and reversing the one way linked list
- 2020-05-17 06:04:24
- OfStack
Data structure is not difficult to understand, but it is difficult to implement, although the idea is very clear, but do not know where to start and the details of the language problem 1 is the main obstacle for beginners (such as me). It took me 1 afternoon to finish the linked list operation independently.
Looking for the code on the Internet, most of them use structure, and some of them are not suitable for those who just learn c++ or data structure. Therefore, I wrote the code with class, which is more in line with students' habits and levels.
Let's look at the class definition first
class node
{
public:
int data;
node *next;
};
class linklist
{
node *h;
... //1 Some function
}
The two classes, node for nodes, node *next, next for Pointers to node, linklist for head Pointers and definition of operation functions.
1. Create the whole table
There are two ways to create a whole table, the head insert (flashback) and the tail insert (order).
void head(linklist &l,int n)
{
node *p;
p=new node;
l.h=p;// Defines the header and the pointer
p->data=n;// The data field of the header pointer is the number of nodes
p->next=NULL;// The successor of the last node must be empty
for(int i=0;i<n;i++)// create n A new node
{
node *q=new node;
cin>>q->data;
q->next=p->next;
p->next=q;// Each new node is placed after the head node
}
}
2. Single node insertion
void insert(linklist &l,int n,int num)
{
node *p=l.h;
for(int i=0;i<n;i++)
{
p=p->next;
}// Find the insertion location
node *q=new node;
q->next=p->next;
p->next=q;
q->data=num;
}
3. Single node deletion
void del(linklist &l,int n)
{
node *p=l.h;
for(int i=0;i<n-1;i++)
{
p=p->next;
}// Find the deleted location
node *q=p;
q=q->next;
p->next=q->next;
delete q;// Release the space
}
4. Find nodes
void search(linklist &l,int n)
{
node *p=l.h;
for(int i=0;i<n;i++)
{
p=p->next;
}
cout<<p->data<<endl;
}
5. The horse
Because the head insert is a flashback output, you want to reverse, a lot of online code is to create a linked list, or use the tail pointer two-way linked list, I think it will not be so troublesome, so I thought of such an algorithm
void reverse(linklist l)
{
node *p=l.h;
node *q;
p=p->next;
while(p->next)
{
q=p->next;
p->next=q->next;
// q->next=p; // It would be tragic to replace the following two sentences with this one.
q->next=l.h->next;
l.h->next=q;
}
}
I began to write the comment sentence, and then I always output the data of the header node. After careful observation, I found that the header pointer followed the header node to the end. Then this problem was solved through the following two sentences to ensure that the header pointer was always at the top of the table.
6. Conclusion
Write here, finally understand why online including wrote a lot of the code is read easily, because books or bloggers will not make the mistakes that he posted, 1 some simple code also does not have a lot of comments, write their own also understand, they want to specify reason for each step 1 or too difficult, can't express what is too much, so want to master one thing or the hands-on, to progress more errors, because it is difficult to find details of the book or online pitfalls, thought he would when writing paper, will find that in the end or not... Loop it a few times, and you're done.