Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   need help with Linked list manipulation (http://www.go4expert.com/forums/help-linked-list-manipulation-t13198/)

einjelle 24Aug2008 15:22

need help with Linked list manipulation
 
This program asks the user to enter any number of lines.
Then, the user is asked what he would like to do:


void deleteLine();
void deleteRange();
void insertLine();
void replaceRange();
void swapLines();



so far, the deleteLine() is the only one working, together with its subfunctions getline(), which gets the deleted line and removeLine() which removes the chosen line.

:chomp: I've been coding for 8 ours already. I can't figure out how to code the other functions which are:

deleteRange
(user enters a two numbers, "from" and "to" and deletes that range)

replaceRange
(user enters numbers "from" and "to" and program asks user to replace each line in the range)

insertLine
(user enters the line number after which a new line is to be inserted. Program asks the user to enter the new line to be inserted.)

swapLines
(user enters two lines numbers whose contents are to be swapped)

PHP Code:


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


typedef struct line
{
    
charline;
    
struct line *prev, *next;
LINE;

LINE *p;
LINE *list = NULL// this will serve as the head of a list.
LINE *endList NULL// this points to the last element of a list.
LINE *newNode NULL;

const 
int LINE_MAX 80;

int c;

char *getline(LINE*headunsigned line_no);
void removeLine(LINE*pint line_no);
void removeRange(LINE*pint startint endint rng);
void insertNode(char newlineint line_no);


void deleteLine();
void deleteRange();
void insertLine();
void replaceRange();
void swapLines();

int main()
{

    
printf("Pls enter any number of lines. End with a ^D/^Z:\n");
    
printf("\n");

    
char line[LINE_MAX];
    
char *pline NULL;



        while (
fgets(lineLINE_MAXstdin))
    {
        
int len strlen(line);
        
line[len-1] = '\0';
        
pline = (char *)malloc(sizeof(char) * (len 1));
        
strncpy(plinelinelen);
        
pline[len] = '\0';

        
LINE *temp;
        
// test first if your list is non empty
        
if (list != NULL)
        {
            for (
temp = list; temp->next != NULLtemp temp->next)
                ;
            
// at this point, you're at the last element
            
temp->next = (LINE*)malloc(sizeof(LINE));
            
temp->next->line pline;
            
temp->next->prev temp;
            
temp->next->next NULL;
            
endList temp->next;

        }

        else  
// our list is empty
        
{
            
// temp at the last element of the list.
            
temp = (LINE *)malloc(sizeof(LINE));
            
temp->line pline;
            
temp->prev temp->next NULL;
            list = 
temp;
            
endList temp;
        }

    }

    
printf("\nWhat would you like to do?\n");
    
printf("[1] Delete Line\n");
    
printf("[2] Delete Range\n");
    
printf("[3] Insert Line\n");
    
printf("[4] Replace Range\n");
    
printf("[5] Swap Lines\n");

    
int choice;
    
scanf("%d", &choice);

    switch(
choice){

        case 
1deleteLine(); break;
        case 
2deleteRange(); break;
        case 
3insertLine(); break;
        case 
5swapLines(); break;

        default: 
printf("1-5"); break;
    }


}


void deleteLine(){


    
=list;


    for(
c=0p!=NULLp=p->next){
            
c++;
    }


    
int num;

    
printf("\nEnter the line number to be removed\n (line number starts from 0)\n");
    
scanf("%d", &num);

    if((
num ==0) && (== 1)){
        
printf("\nList is empty.\n");
        
abort();
    }

    else if  ( 
num >= c){
        
printf("\nNot a valid line number.\n");
        
abort();
    }

    else{

        
printf("\n");
        
printf("\nThe line [%s] was removed"getline(list,num));

        
printf("\n");
        
printf("\nModified List:\n");
        
printf("\n");
    }

    
removeLine(list,num);

    for (
= list; p!= NULLp=p->next){
        
printf("%s\n"p->line);
    }

    
system("PAUSE");
}

void deleteRange(){

    
=list;
    for(
c=0p!=NULLp=p->next){
            
c++;
    }

    
int from,torange;

    
printf("\nPlease enter the range of lines you want to remove\n\t");
    
printf("from:");
    
scanf("%d", &from);
    
printf("\n\tto:");
    
scanf("%d", &to);



    
range = (to-from)+1;


    
printf("\n");

    if( (
from==0) && (to==0) && (c==1) ){
        
printf("\nThe list is empty");
        
abort();
    }

    else if(
from || to || from to ){
        
printf("\nNot a valid range.");
        
abort();
    }

    else{

            if(
from==0){

                while(
from<range){
                    
printf("Line [%s] was removed\n\t"getline(list,from));
                    
from++;
                }
            }

            else{
                while(
from<=range){
                    
printf("Line [%s] was removed\n\t"getline(list,from));
                    
from++;
                }
            }
    }


    
removeRange(list,from,to,range);

    
printf("\n");
    
printf("\nModified List:\n");
    
printf("\n");

    for (
= list; p!= NULLp=p->next){
        
printf("%s\n"p->line);
    }

    
system("PAUSE");

}

void insertLine(){

    
int num;
    
char newline;
    
char bago;

    
printf("Enter the number of the line after which you would like to insert an new line:  ");
    
scanf("%d", &num);

    
printf("Enter the line:  ");
    
scanf("%s", &newline);

    
p=list;
    
insertNode(newline,num);

    for (
= list; p!= NULLp=p->next){
        
printf("%s\n"p->line);
    }


    
system("PAUSE");


}


void swapLines(){

    
int num1,num2,j,k;
    
LINE*p2;

    
printf("Enter the first line number:  ");
    
scanf("%d", &num1);

    
printf("Enter the second line number:  ");
    
scanf("%d", &num2);

    for(
j=0j<num1;j++){

        
p=p->next;
    }

    for(
k=0k<num2k++){

        
p2=p2->next;
    }

    
p->prev->next=p2->next->prev;
    
p2=p->prev->next;


    for (
= list; p!= NULLp=p->next){
        
printf("%s\n"p->line);
    }

    
system("PAUSE");
}


/*-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/




char *getline(LINE*headunsigned line_no){


    
int i=0;

    for(
p=headi<line_noi++){

         
p=p->next;

    }
    return 
p->line;
}


void removeLine(LINE *pint line_no){

    
int j;
    for (
0line_noj++){
        
p->next;
    }

    if (
p->prev == NULL){
        
p->next->prev=NULL;
        *
= *p->next;
    }

    else if (
p->next == NULL){
        
p->prev->next=NULL;
    }

    else{
        
p->next->prev p->prev;
        
p->prev->next p->next;
    }
}

void removeRange(LINE *pint startint endint rng){

    
int j;
    
int k=0;
    
LINE*head;

        for (
0startj++){
            
p->next;
        }

        if (
p->prev == NULL){
            
p->next->prev=NULL;
            *
= *p->next;
        }

        else if (
p->next == NULL){
            
p->prev->next=NULL;
        }

        else{
            
p->next->prev p->prev;
            
p->prev->next p->next;
        }
}

void insertNode(char newlineint line_no){

        
int i;
        
LINE *tempo,*t,*r;

        
=list;

        for(
c=0p!=NULLp=p->next){
                    
c++;
        }

        
=list;

        
r=p;
        
// here r stores the first location
        
if(line_no >= || line_no <= 0){
            
printf("Invalid line number");
            return;
        }

        if (
line_no == 0){
            
tempo=(LINE *)malloc(sizeof(LINE));
            
//tempo->line=newline;

            // IF LIST IS NULL ADD AT BEGINNING
            
if ( p== NULL){
                
p=tempo;
                
p->next=NULL;
            }

            else{
                
tempo->next=p;
                
p=tempo;
            }
        }

        else{

            for(
i=0;i<line_no;i++){

                
t=r//t will be holding previous value
                
r=r->next;
            }

            
tempo=(LINE*)malloc(sizeof(LINE));
            
//tempo->line=newline;
            
t->next=tempo;
            
t=tempo;
            
t->next=r;
            return;
        }


help please :)

xpi0t0s 26Aug2008 20:42

Re: need help with Linked list manipulation
 
You have some uninitialised variables in swapLines(). (Did your compiler warn you about that?)
That's not the only problem in this function; p->prev->next=p2->next->prev; p2=p->prev->next; doesn't seem sufficient to swap two lines over. Consider the case [a]<->[p]<->[b]<->[p2]<->[c], endpoint cases NULL<-[p]<->[b]<->[p2]<->[c] and [a]<->[p]<->[b]<->[p2]->NULL and p2>p [a]<->[p2]<->[b]<->[p]<->[c]. Work out on paper what pointers need updating in each case.

insertLine won't work at all; have a close look at char newline; scanf("%s", &newline); char newline defines newline to be a single character; if you try to copy a string into it you'll corrupt your stack.

insertNode() has a number of bugs; what about p->prev; if inserting at the top; why "t=r;" as it's a doubly-linked list - just use r->prev if you want the previous node; you don't check line_no against c; what about r->prev (which points at old t instead of tempo...by the way...t = tempo = great way of confusing yourself, not to mention the constant use of meaningless variable names. Wouldn't it be a lot clearer if the code said nodeBefore->next=newNode; newNode->next=nodeAfter; newNode->prev=nodeBefore; nodeAfter->prev=newNode;) and t(was tempo)->prev. Again you can solve a lot of this by working it out on paper and comparing it with the code.

The rest of the code seems to suffer from duplicates of the above comments. DON'T use global temporary variables (p). DO use meaningful variable names. DO work it out on paper.


All times are GMT +5.5. The time now is 14:23.