I have the following array structure (linked list):
struct str_pair
{
char ip [50] ;
char uri [50] ;
str_pair *next ;
} ;
str_pair *item;
I know to create a new item, I need to use
item = new str_pair;
However, I need to be able to loop through the array and delete a particular item. I have the looping part sorted. But how do I delete an item from an array of structures?
You can delete it using the ordinary delete keyword, but that will not shift all other members of the array. If you want this kind of behaviour take a look at std::vector or something like that.
What you've shown is not an array of struct, but a linked list of struct containing arrays (of type char).
An array of struct would look like this:
str_pair array_of_structs[10];
// or:
str_pair* dynamically_allocated_array_of_structs = new str_pair[10];
If you actually have something like this, you don't need to delete single items from an array. Let's say you've initialized your array as follows:
str_pair* array_of_structs = new str_pair[10];
Then you delete the whole array (including all of its items) using:
delete[] array_of_structs;
Again, you can't delete single items in an array allocated with new[]; you perform a delete[] on the whole array.
If, on the other hand, you intended to say "linked list of struct", then you'd generally delete an item similarly to the following:
str_pair* previous_item = ...;
str_pair* item_to_delete = previous_item->next;
if (item_to_delete != 0)
{
previous_item->next = item_to_delete->next; // make the list "skip" one item
delete item_to_delete; // and delete the skipped item
}
Or, in English: Find the item (A) preceding the item which you want to delete (B), then adjust A's "next" pointer so that B will be skipped in the list, then delete B.
You need to be careful with special cases, i.e. when the item to be removed from the list is the first item or the last one. The above code is not sufficient when you want to delete the first item in the list, because there will be no previous_item. In this case, you'd need to change the pointer to the list's first element to the second element.
void deleteitem(char *uri) { str_pair *itemtodelete; curr = head; while (curr->next != NULL) { if ((strcmp(curr->uri, uri)) == 0) { itemtodelete = curr; curr = itemtodelete->next; delete itemtodelete; curr = head; return; } curr = curr->next; } }
Some things are wrong here:
If head is null, the test curr->next != NULL will cause a segfault. (You must never dereference a null pointer!)
Your code for removing an item from the list is completely incorrect. Worst of all, you delete a node without changing the previous item's next pointer. The previous item will thus reference an item that's no longer there.
A detail: curr = head; before the return statement doesn't do anything useful at all.
Do it in two steps: One function to find the node to be deleted via its attached uri, and one function to remove the node. You could separate it even better than the code below does, but it should be a starting point:
str_pair* finditemwithuri(char* uri)
{
str_pair* current = head;
while (current)
{
if (strcmp(current->uri, uri) == 0) return current;
current = current->next;
}
return 0;
}
void deleteitem(char* uri)
{
// find linked list node with that uri; abort if uri not in list
str_pair* itemtodelete = finditemwithuri(uri);
if (!itemtodelete) return;
// special case: node to be deleted is the list's head
if (itemtodelete == head)
{
head = itemtodelete->next;
delete itemtodelete;
return;
}
// else, iterate over list nodes
// up to the one preceding the node to be deleted
str_pair* current = head;
while (current)
{
if (itemtodelete == current->next)
{
current->next = itemtodelete->next;
delete itemtodelete;
return;
}
current = current->next;
}
}
As others have pointed out, this is a Linked List, not an array. To answer your question for linked lists:
To insert an item:
str_pair* p = // iterate over the linked list to your insertion point
str_pair* item = new str_pair;
item->next = p->next;
p->next = item;
That inserts a new str_pair after p.
To remove an item:
str_pair* p = // iterate to just before your deletion point
str_pair* item = p->next;
p->next = p->next->next;
delete item;
This will remove the element after p
To do this with your code:
void deleteitem(char *uri)
{
str_pair *previous = NULL;
curr = head;
while (curr != NULL) {
if ((strcmp(curr->uri, uri)) == 0) {
// modify the previous element to skip over our deleted one
if (previous)
previous->next = curr->next;
else
head = curr->next;
// safely delete the element, now that no one points to it
delete curr;
curr = head;
return;
}
// always remember our previous element, so we can fix its 'next' pointer
previous = curr;
curr = curr->next;
}
}
You need a better add method too:
void additem(char *uri, char *ip)
{
curr = head;
// traverse the list until we're at the last item
while (curr->next != NULL) {
curr = curr->next;
}
// attach a new element to the list
curr->next = new str_pair;
// go to that new element
curr = curr->next;
// set the values of the new element
strcpy(curr->ip, ip);
strcpy(curr->uri, uri);
curr->next = NULL;
curr = head;
}
Thanks for the replies guys! Sorry, yeah, it's a linked list. However, I still couldn't get the delete function to work. I'm pasting the whole code. I just need to get the deleteitem() function to work.
#include <iostream>
#include <cstdlib>
using namespace std;
//--- You must use this struct to save data and search for the desired output.
// Do not change anything about the structure or the pointer below it.
struct str_pair {
char ip[50];
char uri[50];
str_pair *next;
};
str_pair *head;
str_pair *curr;
void additem(char *uri, char *ip)
{
curr = head;
while (curr->next != NULL) {
curr = curr->next;
}
strcpy(curr->ip, ip);
curr->next = new str_pair;
strcpy(curr->uri, uri);
curr->next = new str_pair;
curr = curr->next;
curr = head;
}
int totalitems()
{
int i = 0;
curr = head;
while (curr->next != NULL) {
i += 1;
curr = curr->next;
}
curr = head;
return i;
}
void findbyuri(char *uri)
{
curr = head;
while (curr->next != NULL) {
if ((strcmp(uri, curr->uri)) == 0) {
cout << curr->ip << endl;
return;
}
curr = curr->next;
}
cout << "nil" << endl;
}
void findbyip(char *ip)
{
curr = head;
while (curr->next != NULL) {
if ((strcmp(ip, curr->ip)) == 0) {
cout << curr->uri << endl;
return;
}
curr = curr->next;
}
cout << "nil" << endl;
}
void deleteitem(char *uri)
{
str_pair *itemtodelete;
curr = head;
while (curr->next != NULL) {
if ((strcmp(curr->uri, uri)) == 0) {
itemtodelete = curr;
curr = itemtodelete->next;
delete itemtodelete;
curr = head;
return;
}
curr = curr->next;
}
}
int main(int argc, char *argv[]) //-------------------------------------------
{ //--- When no command line parameters MUST print id string in CSV format.
if (argc == 1) // no parameters.
{
cout << "159753, [email protected], Alex Nybolm" << endl;
return (0);
}
it = new str_pair;
head = new str_pair;
int i;
for (i = 1; i < argc; i++) {
if (argv[i][0] == 'A') //add item
{
additem(argv[i + 1], argv[i + 2]);
i += 2;
}
else if (argv[i][0] == 'U') //find by uri
{
findbyuri(argv[i + 1]);
i += 1;
}
else if (argv[i][0] == 'I') //find by ip
{
findbyip(argv[i + 1]);
i += 1;
}
else if (argv[i][0] == 'N') //print total tiems
{
cout << totalitems() << endl;
}
else if (argv[i][0] == 'D') //delete item
{
deleteitem(argv[i + 1]);
i += 1;
}
}
return (0);
}
The command-line input would be something like this (Linux):
./x A google.com 1234 A cnn.com 5678 A microsoft.com 7415 D cnn.com N
This would add the 3 URLs and IPs, delete the cnn.com record, and finally report the number of items at the end (here should be 2).
Just use std::list. There's no reason to manually write such a construct.
http://msdn.microsoft.com/en-us/library/802d66bt(VS.80).aspx
std::list offers remove.