Creating a list from an array: #include #include #include \"list.h\" typedef str
ID: 3887427 • Letter: C
Question
Creating a list from an array:
#include
#include
#include "list.h"
typedef struct node {
ElemType val;
struct node *next;
} NODE;
struct list_struct {
NODE *front;
NODE *back;
};
LIST *lst_create() {
LIST *l = malloc(sizeof(LIST));
l->front = NULL;
l->back = NULL;
return l;
}
void lst_push_front(LIST *l, ElemType val) {
NODE *p = malloc(sizeof(NODE));
p->val = val;
p->next = l->front;
l->front = p;
if(l->back == NULL) // was empty, now one elem
l->back = p;
}
void lst_push_back(LIST *l, ElemType val) {
NODE *p;
if(l->back == NULL) // list empty - same as push_front
lst_push_front(l, val);
else { // at least one element before push
p = malloc(sizeof(NODE));
p->val = val;
p->next = NULL;
l->back->next = p;
l->back = p;
}
}
/**
* TODO
* function: lst_from_array
*
* description: creates a new list populated with the
* elements of array a[] in the same order as
* they appear in a[] (element at a[0] will be the
* first element in the list and so-on). List is
* returned as a LIST pointer.
*
* Parameter n indicates the length of the given array.
*
* runtime requirement: THETA(n)
*/
LIST * lst_from_array(ElemType a[], int n) {
return NULL; //placeholder
}
Explanation / Answer
//Please see the code below:
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType ;
// A linked list node
struct Node
{
ElemType val;
struct Node *front;
struct Node *back;
};
void insertAtEnd(struct Node** head_ref, int new_val)
{
/* 1. allocate node */
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
struct Node *last = *head_ref; /* used in step 5*/
/* 2. put in the val */
new_node->val = new_val;
/* 3. This new node is going to be the last node, so
make front of it as NULL*/
new_node->front = NULL;
/* 4. If the Linked List is empty, then make the new
node as head */
if (*head_ref == NULL)
{
new_node->back = NULL;
*head_ref = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last->front != NULL)
last = last->front;
/* 6. Change the front of last node */
last->front = new_node;
/* 7. Make last node as backious of new node */
new_node->back = last;
return;
}
/**
* TODO
* function: lst_from_array
*
* description: creates a new list populated with the
* elements of array a[] in the same order as
* they appear in a[] (element at a[0] will be the
* first element in the list and so-on). List is
* returned as a LIST pointer.
*
* Parameter n indicates the length of the given array.
*
* runtime requirement: THETA(n)
*/
Node * lst_from_array(ElemType a[], int n) {
struct Node* head = NULL;
for(int i=0;i<n;i++)
insertAtEnd(&head, i+1);
struct Node *temp=head;
while(temp)
{
printf("%d ",temp->val);
temp=temp->front;
}
return head; //placeholder
}
int main()
{
/* Start with the empty list */
ElemType arr[5]={1,2,3,4,5};
lst_from_array(arr,5);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.