anyone can help me these problem? i am not sure what to do. typedef struct node
ID: 3766223 • Letter: A
Question
anyone can help me these problem? i am not sure what to do.
typedef struct node {
ElemType val;
struct node *next;
} NODE;
struct list_struct {
NODE *front;
NODE *back;
};
/** TODO
* function: lst_count
* description: Counts number of occurrences
* of x in the list and returns
* that value.
*/
int lst_count(LIST *l, ElemType x) {
return 0;
}
/* TODO
* For full credit, you cannot allocate any new memory!
*
* description: self-evident
*/
void lst_reverse(LIST *l) {
}
/** TODO
* function: lst_remove_all_fast
* description: same behavior as lst_remove_all_slow but has
* faster execution time even on "bad cases" as generated by
* the function above. Number of operations proportional to the
* length of the list regardless of number of matches and distribution
* of matches.
*
* Approach: all occurrences of x removed in a single pass
*
* returns: number of elements removed
*/
int lst_remove_all_fast(LIST *l, ElemType x) {
return 0;
}
// TODO
int lst_is_sorted(LIST *l){
return 0;
}
/** TODO
* function: lst_insert_sorted
*
* description: assumes given list is already in sorted order
* and inserts x into the appropriate position
* retaining sorted-ness.
* Note 1: duplicates are allowed.
*
* Note 2: if given list not sorted, behavior is undefined/implementation
* dependent. We blame the caller.
* So... you don't need to check ahead of time if it is sorted.
*/
void lst_insert_sorted(LIST *l, ElemType x) {
}
/** TODO
* function: lst_merge_sorted
*
* description: assumes both list a and b are in
* sorted (non-descending) order and merges them
* into a single sorted list with the same
* elements.
*
* This single sorted list is stored in a while
* b becomes empty.
*
* if either of given lists are not sorted,
* we blame the caller and the behavior is
* implementation dependent -- i.e., don't worry
* about it!
*
* Example:
*
* a: [2 3 4 9 10 30]
* b: [5 8 8 11 20 40]
*
* after call on (a,b)
*
* a: [2 3 4 5 8 8 9 10 11 20 30 40]
* b: []
*
* implementation: should not allocate ANY new list
* nodes -- it should just re-link existing
* nodes.
*
* Must be linear time in the |a|+|b| -- i.e.,
* the total number of elements being processed.
*/
void lst_merge_sorted(LIST *a, LIST *b){
}
Explanation / Answer
typedef struct node {
ElemType val;
struct node *next;
} NODE;
struct list_struct {
NODE *front;
NODE *back;
};
int lst_count(LIST *l, ElemType x) {
int count = 0;
while (l.next != NULL)
{
if(l.val == x){
count++;
}
}
return count;
}
void lst_reverse(LIST *l) {
list_struct mode* back = NULL;
list_struct node* current = head;
list_struct node* front;
while (l.next != NULL)
{
l.next = current->next;
current->next = back;
back = current;
current = next;
}
head = back;
}
int lst_remove_all_fast(LIST *l, ElemType x) {
free(l);
}
// TODO
int lst_is_sorted(LIST *l){
bool sorted = true;
while(sorted) {
unsorted = false;
list_struct node* current = head;
list_struct node* next;
while(current != null) {
next = current->next;
if(next < current) {
swap(current, next)
sorted = true;
}
current = current->next;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.