943,963 Members | Top Members by Rank

Ad:
  • C Discussion Thread
  • Unsolved
  • Views: 312
  • C RSS
Nov 3rd, 2009
0

nth last element with o(n) complexity

Expand Post »
written a code for finding nth last element but no idea how to caluculate complexity.

how can i make this, of 0(n) complexity.

  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. }
Similar Threads
Reputation Points: 34
Solved Threads: 4
Junior Poster
Iam3R is offline Offline
110 posts
since Oct 2009

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C Forum Timeline: Assigning an array values from another array
Next Thread in C Forum Timeline: [Help] How to Get Linux Kernel Behavior





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


Follow us on Twitter


© 2011 DaniWeb® LLC