| | |
finding nth last element with 0(n) complexity
Please support our C advertiser: Programming Forums - DaniWeb Sister Site
I am very poor in calculating complexities.
Please some one let me know what is the complexity of the below program.
I actually want to write a program for finding the nth last element with 0(n) complexity.
but unable write, please give me some idea.
the below code works perfectly and i considered all the posibilities.
please mention if any other possibilities can be covered.
Please some one let me know what is the complexity of the below program.
I actually want to write a program for finding the nth last element with 0(n) complexity.
but unable write, please give me some idea.
the below code works perfectly and i considered all the posibilities.
if list empty : returns zero if postion is < 0 : returns -2 if position is > no of elements in the list : returns -1
please mention if any other possibilities can be covered.
Last edited by Iam3R; Oct 29th, 2009 at 6:37 am. Reason: added insert code for better understanding
// p is position of element to find int nthlast(struct node *n,int p) { struct node *f, *s; if(n) { int cnt=0; f = n;// start address store in first pointer while(n != NULL && cnt<p-1) n=n->next, cnt++; // move the the pointer p-1 times if(!n) /* if the entered poistion is greater than the no of elements */ return -1; if(p <= 0) return -2; /* if entered poisition is lessthan or equal to zero */ s = n; while(n) { int cnt = 0; while(n != NULL && cnt < p-1) n=n->next, cnt++; if(n) { f = s; s = n; } else { int i=0; while(i<cnt-1) { i++; f=f->next; } return f->data; } if(p==1) { n=n->next; s = n; } } return f->data; } else return 0; } //Driver code: int main() { struct node*p=NULL; int n,d,i=0,ele,a[10]={1,2,3,4,5,6,7,8,9,10}; while(i<10) { insert(&p,a[i++]); } display(p); printf("nter the pos\n"); scanf("%d",&n); if((ele = nthlast(p,n)) > 0) printf("\n%d",ele); else if(!ele) printf("list empty\n"); else if(ele == -1) printf("no of elements less than the pos\n"); else printf("positio shuold be > 0\n"); return 0; } inserting elements function: void insert(struct node**p,int num) { if(*p==NULL) { (*p)=malloc(sizeof(struct node)); (*p)->next=NULL; (*p)->data=num; } else { insert(&((*p)->next),num); } }
Similar Threads
- Finding the nth row (SQL)...debative question (MS SQL)
- Hash Table template implementation help (C++)
- Shifting Arrays (one space to right) (C)
- Random Numbers (C)
- stl vector - can you delete by position? (C++)
- Arrays (C++)
| Thread Tools | Search this Thread |
Tag cloud for C
#include * append array arrays asterisks bash binarysearch calculate changingto char character cm command copyimagefile creafecopyofanytypeoffileinc createprocess() database directory dynamic execv feet fgets file floatingpointvalidation fork forloop framework function functions getlogicaldrivestrin givemetehcodez global grade graphics gtkwinlinux hacking histogram homework ide include incrementoperators input intmain() iso kernel keyboard kilometer lazy license linked linkedlist linux list lists looping loopinsideloop. lowest matrix meter microsoft mqqueue number oddnumber odf openwebfoundation overwrite pause pdf pointer posix process program programming radix recursion recv recvblocked research reversing segmentationfault sequential single socket socketprogramming spoonfeeding standard strchr string student system testing threads turboc unix urboc user variable whythiscodecausesegmentationfault windowsapi



