fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4.  
  5. struct node {
  6.   int first;
  7.   struct node *rest;
  8. };
  9.  
  10. void add_to_front(struct node **ptrhead, int item) {
  11.  
  12.   assert(ptrhead != NULL); // ptrhead must be valid
  13.  
  14.   struct node *newnode = malloc(sizeof(struct node));
  15.  
  16.   if (newnode == NULL) {
  17.     printf("ERROR! add_to_front ran out of memory!\n");
  18.     exit(EXIT_FAILURE);
  19.   }
  20.  
  21.   newnode->first = item;
  22.   newnode->rest = *ptrhead;
  23.   *ptrhead = newnode;
  24. }
  25.  
  26. int remove_from_front(struct node **ptrhead) {
  27.  
  28.   assert(ptrhead != NULL); // ptrhead must be valid
  29.   assert(*ptrhead != NULL); // list must be non-empty  
  30.  
  31.   struct node *lst = *ptrhead;
  32.  
  33.   int retval = lst->first;
  34.   *ptrhead = lst->rest;
  35.   free(lst);
  36.  
  37.   return(retval);
  38. }
  39.  
  40. void print_list(struct node *lst) {
  41.   if (lst == NULL) {
  42.     printf("empty\n");
  43.     return;
  44.   }
  45.   while (lst != NULL) {
  46.     printf("%d",lst->first);
  47.     if (lst->rest != NULL) {
  48.       printf(":");
  49.     }
  50.     lst = lst->rest;    
  51.   }
  52.   printf(".\n");
  53. }
  54.  
  55. void destroy_list(struct node *lst) {
  56.   struct node *next;
  57.   while (lst != NULL) {
  58.     next = lst->rest;
  59.     free(lst);
  60.     lst = next;
  61.   }
  62. }
  63.  
  64.  
  65.  
  66. typedef struct sequence *Sequence;
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74. struct sequence
  75. {
  76. 	struct node* lst;
  77. 	int length;
  78. };
  79.  
  80. Sequence new_sequence()
  81. {
  82. 	// PRE:  true
  83. 	// POST: returns a new, empty Sequence
  84. 	// TIME: O(1)
  85. 	Sequence s = malloc(sizeof(struct sequence));
  86. 	if(!s)
  87. 	{
  88. 		printf("ERROR! new_sequence ran out of memory\n");
  89. 		exit(EXIT_FAILURE);
  90. 	}
  91. 	s->lst = 0;
  92. 	s->length = 0;
  93. 	return s;
  94. }
  95.  
  96. void delete_sequence(Sequence s)
  97. {
  98. 	// PRE:  s is a valid Sequence
  99. 	// POST: s is no longer a valid Sequence
  100. 	// TIME: O(n) [O(sequence length)]
  101. 	destroy_list(s->lst);
  102. 	free(s);
  103. }
  104.  
  105. int sequence_length(Sequence s)
  106. {
  107. 	// PRE:  s is a valid Sequence
  108. 	// POST: returns the number of items in s
  109. 	// TIME: O(1)
  110.  
  111. 	return s->length;
  112. }
  113.  
  114. int sequence_item_at(Sequence s, int pos)
  115. {
  116. 	// PRE:  s is a valid non-empty Sequence
  117. 	//       0 <= pos < length
  118. 	// POST: returns the item at pos
  119. 	// TIME: O(n) [O(sequence length)]
  120. 	struct node* temp = s->lst;
  121. 	for(; pos > 0; --pos)
  122. 	{
  123. 		temp = temp->rest;
  124. 	}
  125. 	return temp->first;
  126. }
  127.  
  128. void sequence_insert_at(Sequence s, int pos, int item)
  129. {
  130. 	// PRE:  s is a valid Sequence
  131. 	//       0 <= pos <= length
  132. 	// POST: changes s to insert item at pos
  133. 	//       length of s is now +1
  134. 	//       all previous items with position >= pos
  135. 	//         are now at position +1
  136. 	// TIME: O(n) [O(sequence length)]
  137. 	++s->length;
  138. 	if(pos)
  139. 	{
  140. 		struct node* ptr = s->lst;
  141. 		for(; pos > 1; --pos)
  142. 		{
  143. 			ptr = ptr->rest;
  144. 		}
  145. 		add_to_front(&ptr->rest, item);
  146. 		print_list(ptr);
  147. 		print_list(ptr->rest);
  148. 		print_list(s->lst);
  149. 	}
  150. 	else
  151. 	{
  152. 		add_to_front(&s->lst, item);
  153. 	}
  154. }
  155.  
  156. int sequence_remove_at(Sequence s, int pos)
  157. {
  158. 	// PRE:  s is a valid non-empty Sequence
  159. 	//       0 <= pos < length
  160. 	// POST: returns the item at pos
  161. 	//       changes s to remove item at pos
  162. 	//       length of s is now -1
  163. 	//       all previous items with position >= pos
  164. 	//         are now at position -1
  165. 	// TIME: O(n) [O(sequence length)]
  166. 	--s->length;
  167. 	if(pos)
  168. 	{
  169. 		struct node* ptr = s->lst;
  170. 		for(; pos > 1; --pos)
  171. 		{
  172. 			ptr = ptr->rest;
  173. 		}
  174. 		return remove_from_front(&ptr->rest);
  175. 	}
  176. 	else
  177. 	{
  178. 		return remove_from_front(&s->lst);
  179. 	}
  180.  
  181. }
  182.  
  183. void sequence_insert_start(Sequence s, int item)
  184. {
  185. 	// NOTE: equivalent to: sequence_insert_at(s, 0, item);
  186. 	// TIME: O(1)
  187. 	sequence_insert_at(s, 0, item);
  188. }
  189.  
  190. int sequence_remove_start(Sequence s)
  191. {
  192. 	// NOTE: equivalent to: sequence_remove_at(s, 0);
  193. 	// TIME: O(1)
  194. 	return sequence_remove_at(s, 0);
  195. }
  196.  
  197. void sequence_reverse(Sequence s)
  198. {
  199. 	// PRE:  s is a valid Sequence
  200. 	// POST: reverses the order of all of the items in s
  201. 	// TIME: O(n) [O(sequence length)]
  202. 	struct node* temp = s->lst;
  203. 	s->lst = 0;
  204. 	while(temp)
  205. 	{
  206. 		add_to_front(&s->lst, remove_from_front(&temp));
  207. 	}
  208. }
  209.  
  210. void print_sequence(Sequence s)
  211. {
  212. 	// PRE:  s is a valid Sequence
  213. 	// POST: Prints out every item in s
  214. 	// TIME: O(n) [O(sequence length)]
  215. 	printf("SEQUENCE START\n");
  216. 	struct node* temp = s->lst;
  217. 	for(int i = 0; temp; temp = temp->rest)
  218. 	{
  219. 		printf("%d: %d\n", i++, temp->first);
  220. 	}
  221. 	printf("SEQUENCE END\n");
  222. }
  223.  
  224. Sequence fibseq(int n)
  225. {
  226. 	// PRE:  n >= 0
  227. 	// POST: produces a Sequence of length n+1 corresponding
  228. 	//       to the Fibonacci Sequence (from 0...n)
  229. 	// TIME: O(n)
  230. 	Sequence s = new_sequence();
  231. 	if(n)
  232. 	{
  233. 		int a = 0;
  234. 		int b = 1;
  235. 		sequence_insert_start(s, a);
  236. 		for(; n; --n)
  237. 		{
  238. 			int temp = a;
  239. 			a += b;
  240. 			b = temp;
  241. 			sequence_insert_start(s, a);
  242. 		}
  243. 		sequence_reverse(s);
  244. 	}
  245. 	else
  246. 	{
  247. 		sequence_insert_start(s, 0);
  248. 	}
  249. 	return s;
  250. }
  251.  
  252.  
  253. int main()
  254. {
  255. 	Sequence derp = new_sequence();
  256. 	sequence_insert_at(derp, 0, 15);
  257. 	sequence_insert_at(derp, 0, 16);
  258. 	sequence_insert_at(derp, 0, 17);
  259. 	sequence_insert_at(derp, 2, 5);
  260. 	print_sequence(derp);
  261. 	sequence_reverse(derp);
  262. 	print_sequence(derp);
  263. 	sequence_remove_at(derp, 1);
  264. 	print_sequence(derp);
  265. 	delete_sequence(derp);
  266. Sequence test = fibseq(10);
  267. print_sequence(test);
  268. delete_sequence(test);
  269. 	return 0;
  270. }
Success #stdin #stdout 0s 1920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
16:5:15.
5:15.
17:16:5:15.
SEQUENCE START
0: 17
1: 16
2: 5
3: 15
SEQUENCE END
SEQUENCE START
0: 15
1: 5
2: 16
3: 17
SEQUENCE END
SEQUENCE START
0: 15
1: 16
2: 17
SEQUENCE END
SEQUENCE START
0: 0
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55
SEQUENCE END
https://ideone.com/cCWsF9
language:
C99 (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!