Please read the instructions...I only need help with the emboldened methods in t

Question

Please read the instructions...I only need help with the emboldened methods in the code i displayed

The web crawler will start at some web page, follow a random link on that page, then follow a random link on that new page, and so on, keeping a list of the pages that it has visited. Your part of this project will be to complete the linked list data structure that stores the web addresses that the crawler visits. Note that this project deals with a singly-linked list (unlike the doubly-linked list we discussed in class). Singlylinked lists are simpler, because each node just points to the next node (i.e., no “previous” pointers). The last node in the list has a NULL next pointer to indicate the end. (FYI, the disadvantage with singly-linked lists is that you can’t traverse them backwards, while doubly-linked lists let you go forward and backward.)

The file crawler.c contains some code already written. You should only modify that file in the places that are marked "TODO: complete this". There are comments to help guide you through the code. Note that there are four functions that operate on the linked list that you need to complete: contains, insertBack, printAddresses, and destroyList. Each of these functions must be recursive. The comments indicate how those functions should behave. Only "printAddresses" should print any output to the terminal.  

Explanation / Answer

Here is the code for you:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX_ADDR_LENGTH 1000

/*
* a node in our linked-list of web addresses
*/
struct listNode{
char addr[MAX_ADDR_LENGTH];

struct listNode *next;
};

/*
* returns 1 if the list starting at pNode contains the address addr,
* and returns 0 otherwise
*/
int contains(const struct listNode *pNode, const char *addr);

/*
* inserts the address addr as a new listNode at the end of
* the list
*/
void insertBack(struct listNode *pNode, const char *addr);

/*
* prints the addresses from pNode to the end of the list,
* one on each line
*/
void printAddresses(const struct listNode *pNode);

/*
* frees the memory associated with this node and all subsequent nodes
*/
void destroyList(struct listNode *pNode);
  

/*
* srcAddr should be a web address (e.g., http://www.yahoo.com).
* link should point to an array of maxLinkLength characters.
* getLink returns 1 if a link was found and 0 otherwise.
* If a link was found, "link" will be filled in with the web address.
*/
int getLink(const char* srcAddr, char* link, const int maxLinkLength);

int main(int argc, char** argv){
  
long seed;

char startAddr[MAX_ADDR_LENGTH];
char destAddr[MAX_ADDR_LENGTH];
  
int hopNum, numHops;
  
struct listNode *pListStart;

if(argc < 3 || argc > 4){
fprintf(stderr, "USAGE: %s startAddr numHops [rand seed]", argv[0]);
return -1;
}
  
/* initialization */
if(argc >= 4){
seed = atol(argv[3]);
}
else{
seed = time(NULL);
}

printf("seed = %ld ", seed);
srand(seed);

strncpy(startAddr, argv[1], MAX_ADDR_LENGTH);
startAddr[MAX_ADDR_LENGTH - 1] = '';

numHops = atoi(argv[2]);

pListStart = malloc(sizeof(struct listNode));
if(pListStart == NULL){
fprintf(stderr, "ERROR: could not allocate memory ");
return -2;
}
strncpy(pListStart->addr, startAddr, MAX_ADDR_LENGTH);
pListStart->next = NULL;

/* start the crawling */
for(hopNum=1; hopNum <= numHops; hopNum++){
int res = getLink(startAddr, destAddr, MAX_ADDR_LENGTH);

if(!res){
printf("Dead end on hop %d: no outgoing links ", hopNum);
break;
}

if(contains(pListStart, destAddr)){
printf("Cycle detected on hop %d: address %s ", hopNum,
destAddr);
hopNum--; // try again for this hop in the next iteration
}
else{
insertBack(pListStart, destAddr);
strncpy(startAddr, destAddr, MAX_ADDR_LENGTH);
}
}

printAddresses(pListStart);

destroyList(pListStart);

return 0;
}

/*
* returns 1 if the list starting at pNode contains the address addr,
* and returns 0 otherwise
*/
int contains(const struct listNode *pNode, const char *addr){
    //TODO: complete this
    while(pNode != NULL)   //Keep moving till the end of the list.
    {
       if(strcmp(pNode->addr, addr) == 0)   //If the address at some node equals the passed addr.
            return 1;       //Conclude the addr is found, and stop search.
        pNode = pNode->next;   //If the list is exhausted, conclude the addr is not found, and report back.
    }      
    return 0;      
}
  

/*
* inserts the address addr as a new listNode at the end of
* the list
*/
void insertBack(struct listNode *pNode, const char *addr){
    //TODO: complete this
    struct listNode *newNode = malloc(sizeof(struct listNode));   //Creates a new node.
    strcpy(newNode->addr, addr);   //Copies addr to the node.
    newNode->next = NULL;   //Assigns newNode->next to NULL.
    if(pNode == NULL)   //If the list is empty.
        pNode = newNode;   //Make this the first node.
    struct listNode *temp = pNode;   //Creates a traversal pointer.
    while(temp->next != NULL)   //Till the pointer reaches the last node.
        temp = temp->next;       //Keep moving to the next node.
    temp->next = newNode;       //Once the last node is reached, add this new node there.      
}

/*
* prints the addresses from pNode to the end of the list,
* one on each line
*/
void printAddresses(const struct listNode *pNode){
    //TODO: complete this
    while(pNode != NULL)   //Keep traversing till the last node.
    {
       printf("%s ", pNode->addr);   //Print the addr in that node.
       pNode = pNode->next;   //Move on to the next node.
    }
}

/*
* frees the memory associated with this node and all subsequent nodes
*/
void destroyList(struct listNode *pNode){
    //TODO: complete this
    struct listNode *temp;   //Takes a temporary pointer which points to the node to be freed.
    while(pNode != NULL)   //Till the given list becomes empty.
    {
       temp = pNode;       //Copy the first node address to temp.
       pNode = pNode->next;   //Make pNode bypass the first node.
       free(temp);       //Free first node.
    }
}
  

int getLink(const char* srcAddr, char* link, const int maxLinkLength){
const int bufSize = 1000;
char buffer[bufSize];

int numLinks = 0;

FILE *pipe;

snprintf(buffer, bufSize, "curl -s "%s" | python getLinks.py", srcAddr);

pipe = popen(buffer, "r");
if(pipe == NULL){
fprintf(stderr, "ERROR: could not open the pipe for command %s ",
buffer);
return 0;
}

fscanf(pipe, "%d ", &numLinks);

if(numLinks > 0){
int linkNum;
double r = (double)rand() / ((double)RAND_MAX + 1.0);

for(linkNum=0; linkNum<numLinks; linkNum++){
fgets(buffer, bufSize, pipe);
  
if(r < (linkNum + 1.0) / numLinks){
break;
}
}

/* copy the address from buffer to link */
strncpy(link, buffer, maxLinkLength);
link[maxLinkLength-1] = '';
  
/* get rid of the newline */
{
char* pNewline = strchr(link, ' ');
if(pNewline != NULL){
*pNewline = '';
}
}
}

pclose(pipe);

if(numLinks > 0){
return 1;
}
else{
return 0;
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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