| | |
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 |
#include adobe ansi api append array arrays asterisks binarysearch changingto char character cm copyimagefile cprogramme creafecopyofanytypeoffileinc csyntax database directory dynamic execv feet fgets file fork framework frequency function getlasterror givemetehcodez global grade gtkgcurlcompiling hacking hardware highest histogram include incrementoperators infiniteloop input interest kernel keyboard kilometer license linked linkedlist linux linuxsegmentationfault list lists locate logical_drives looping loopinsideloop. lowest match matrix meter microsoft motherboard mqqueue number odf opensource overwrite owf pattern pdf performance pointer posix probleminc process program programming radix recursion recv repetition research reversing scripting segmentationfault sequential socket socketprograming standard string systemcall testing threads turboc unix user voidmain() wab windows.h windowsapi



