can anyone help me with this problem, Designing Bag data Structure Using C++? i

Question

can anyone help me with this problem, Designing Bag data Structure Using C++? i have attached the problem below. Thanks

The bag data structure is a data structure for storing the data in an unordered list. For the bag data structure, the insert function takes O (1) and the remove function takes O(1). However the search function for a large bag a lot of different values is O(n) Design a second bag data structure with the same specification of the first bag data structure that has a search time of O(g n) but the insert and remove time of O(n). This special bag data structure might be very useful in the real life. Suppose there is a list of items for sale. The users may search for specific items again and again (For multiple times). However removal and insertion to the item list may happen very infrequency

Explanation / Answer

//for bag1

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<iostream>

using namespace std;

struct Bag1
{
int data;
struct Bag1* next;
};

void addinBag1(struct Bag1** head_ref, int item)
{
  
struct Bag1* new_node =
(struct Bag1*) malloc(sizeof(struct Bag1));

  
new_node->data = item;

  
new_node->next = (*head_ref);


(*head_ref) = new_node;
}

void removefromBag1(struct Bag1** head_ref)
{
  
struct Bag1* node=*head_ref;


(*head_ref) = (*head_ref)->next;
delete(node);
}

bool search(struct Bag1* head, int x)
{
struct Bag1* current = head;  
while (current != NULL)
{
if (current->data == x)
return true;
current = current->next;
}
return false;
}

void printbagItems(struct Bag1* head)
{
struct Bag1* current = head;  
while (current != NULL)
{
cout<<current->data<<" ";
current = current->next;
}
  
}

int main()
{
  
struct Bag1* head = NULL;
int x = 21;

  
addinBag1(&head, 10);
addinBag1(&head, 30);
addinBag1(&head, 11);
addinBag1(&head, 21);
addinBag1(&head, 14);
  
removefromBag1(&head);
printbagItems(head);

search(head, 21)? printf("Yes") : printf("No");
return 0;
}

//for bag2

use skip list

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.