943,453 Members | Top Members by Rank

Ad:
  • C Code Snippet
  • Views: 907
  • C RSS
0

finding nth last element with 0(n) complexity

by on Oct 29th, 2009
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.

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
C Code Snippet (Toggle Plain Text)
  1. // p is position of element to find
  2.  
  3. int nthlast(struct node *n,int p) {
  4.  
  5. struct node *f, *s;
  6. if(n) {
  7. int cnt=0;
  8. f = n;// start address store in first pointer
  9. while(n != NULL && cnt<p-1)
  10. n=n->next, cnt++; // move the the pointer p-1 times
  11. if(!n) /* if the entered poistion is greater than the no of elements */
  12. return -1;
  13. if(p <= 0)
  14. return -2; /* if entered poisition is lessthan or equal to zero */
  15. s = n;
  16. while(n) {
  17. int cnt = 0;
  18. while(n != NULL && cnt < p-1)
  19. n=n->next, cnt++;
  20. if(n) {
  21. f = s;
  22. s = n;
  23. }
  24. else {
  25. int i=0;
  26. while(i<cnt-1) {
  27. i++;
  28. f=f->next;
  29. }
  30. return f->data;
  31. }
  32. if(p==1) {
  33. n=n->next;
  34. s = n;
  35. }
  36. }
  37. return f->data;
  38. }
  39. else
  40. return 0;
  41. }
  42.  
  43.  
  44. //Driver code:
  45.  
  46.  
  47. int main()
  48. {
  49.  
  50. struct node*p=NULL;
  51. int n,d,i=0,ele,a[10]={1,2,3,4,5,6,7,8,9,10};
  52.  
  53. while(i<10)
  54. {
  55.  
  56. insert(&p,a[i++]);
  57. }
  58. display(p);
  59. printf("nter the pos\n");
  60. scanf("%d",&n);
  61. if((ele = nthlast(p,n)) > 0)
  62. printf("\n%d",ele);
  63. else if(!ele)
  64. printf("list empty\n");
  65. else if(ele == -1)
  66. printf("no of elements less than the pos\n");
  67. else
  68. printf("positio shuold be > 0\n");
  69.  
  70. return 0;
  71. }
  72.  
  73.  
  74. inserting elements function:
  75.  
  76. void insert(struct node**p,int num)
  77. {
  78. if(*p==NULL)
  79. {
  80. (*p)=malloc(sizeof(struct node));
  81. (*p)->next=NULL;
  82. (*p)->data=num;
  83. }
  84. else
  85. {
  86. insert(&((*p)->next),num);
  87. }
  88. }
Message:
Previous Thread in C Forum Timeline: Compile program for both 32 and 64 bit?
Next Thread in C Forum Timeline: gedit plugin: code completion (gtk)





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC