A complex number can be represented by two parts, real and image. A series compl
ID: 3557619 • Letter: A
Question
A complex number can be represented by two parts, real and image. A series complex data can be organized as a group of elements by linked list, which is shown as below: struct Complex
{
float real; float image;
struct Complex *next;
};
struct Complex* Generate (float a, float b)
{
// return one new Complex node
}
void Push (struct Complex **source, struct Complex *newNode)
{
// create linked list data by stack creation,
// insert the newNode into the head of source.
// (backward linked list creation)
}
void Print (struct Complex *source)
{
// print out all linked list data as the form, A+Bi,
// and the related distance, |A+Bi|
}
void FrontBackSplit (struct Complex* source, struct Complex** front, struct Complex** back)
{
// Split the nodes of the given list into front and back halves,
// and return the two lists using the reference parameters.
// If the length is odd, the extra node should go in the front list.
// You will probably need special case code to deal with the
// (length <2) cases.
}
void Sort (struct Complex **source)
{
// sort the data of linked list source in increasing order of
// complex number distance
}
struct Complex* AppendMergeReal (struct Complex* source1,
struct Complex* source2)
{
// Merge two complex linked lists (source1 and source2) into
// union of real part of source1 and source2.
// For example, real part of source1 are {1 2 3 3 5}, and real part
// of source2 are {2 3 5 8 8 9}, the merged result are {1 2 3 3 5 8 8 9}.
}
void RecursiveReverse (struct Complex** source)
{
// Recursively reverses the given linked list by changing its .next
// pointers and its head pointer in one pass of the list.
}
Please verify your program by following test code
int main()
{
float data1_real[11] = {3, 2, -5, -9, 7, 9, 4, -2, 4, -7, -7};
float data1_image[11] = {7, -8, -7, 5, -2, 4, 4, 3, -6, 7, 9};
struct Complex *newNode;
struct Complex *source1 = NULL, *dest = NULL;
struct Complex *front, *back; char c;
// Generate Complex data linked list with data1 for (int i=0; i<11; i++) {
newNode = Generate(data1_real[i], data1_image[i]); Push(&source1, newNode);
}
// print out complex data of source1 printf("Original data of source1: "); Print(source1);
// use FrontBackSplit() to divide source1 data into front part
// and back part, and print out these two split data FrontBackSplit(source1, &front, &back); printf(" Front part: ");
print(front); pritf(" Back part: "); print(back);
// sort input complex data according to the distance
// and print out sorted data of front and back individually printf(" Sorted front part: ");
Sort(&front); Print(front);
printf(" Sorted back part: "); Sort(&back);
Print(back);
printf(" ===================================================== ");
// sorted data according to real part
float
data2_real[6] = { 2,
3,
5,
9,
9, 9};
float
data2_image[6] = { 7,
-8,
-7,
5,
-2, 4};
float
data3_real[8] = { 3,
4,
5,
5,
6, 8, 9, 9};
float
data3_image[8] = {-8,
5,
-2,
4,
7, 9, 3, 4};
struct Complex *source2 = NULL, *source3 = NULL; struct Complex *result;
// Generate Complex data linked list with data2 and data3 for (int i=5; i>=0; i--) {
newNode = Generate(data2_real[i], data2_image[i]); Push(&source2, newNode);
}
for (int i=7; i>=0; i--) {
newNode = Generate(data3_real[i], data3_image[i]); Push(&source3, newNode);
}
// Verify AppendMergeReal() function and print out the result printf(" Original data of source2: ");
Print(source2);
printf(" Original data of source3: "); Print(source3);
printf(" Merged data of source2 and source3: "); result = AppendMergeReal(source2, source3); Print(result);
// Reverse merged data of source2 and source3 and print out the result printf(" Reverse test (merged data): "); RecursiveReverse(&result);
Print(result);
getch(); return 1;
}
float
data2_real[6] = { 2,
3,
5,
9,
9, 9};
float
data2_image[6] = { 7,
-8,
-7,
5,
-2, 4};
float
data3_real[8] = { 3,
4,
5,
5,
6, 8, 9, 9};
float
data3_image[8] = {-8,
5,
-2,
4,
7, 9, 3, 4};
Explanation / Answer
i hope this helps...
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct node
{
int data;
struct node* next;
};
/* function prototypes */
struct node* SortedMerge(struct node* a, struct node* b);
void FrontBackSplit(struct node* source,
struct node** frontRef, struct node** backRef);
/* sorts the linked list by changing next pointers (not data) */
void MergeSort(struct node** headRef)
{
struct node* head = *headRef;
struct node* a;
struct node* b;
/* Base case -- length 0 or 1 */
if ((head == NULL) || (head->next == NULL))
{
return;
}
/* Split head into 'a' and 'b' sublists */
FrontBackSplit(head, &a, &b);
/* Recursively sort the sublists */
MergeSort(&a);
MergeSort(&b);
/* answer = merge the two sorted lists together */
*headRef = SortedMerge(a, b);
}
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;
/* Base cases */
if (a == NULL)
return(b);
else if (b==NULL)
return(a);
/* Pick either a or b, and recur */
if (a->data <= b->data)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return(result);
}
/* UTILITY FUNCTIONS */
/* Split the nodes of the given list into front and back halves,
and return the two lists using the reference parameters.
If the length is odd, the extra node should go in the front list.
Uses the fast/slow pointer strategy. */
void FrontBackSplit(struct node* source,
struct node** frontRef, struct node** backRef)
{
struct node* fast;
struct node* slow;
if (source==NULL || source->next==NULL)
{
/* length < 2 cases */
*frontRef = source;
*backRef = NULL;
}
else
{
slow = source;
fast = source->next;
/* Advance 'fast' two nodes, and advance 'slow' one node */
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}
/* 'slow' is before the midpoint in the list, so split it in two
at that point. */
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}
/* Function to print nodes in a given linked list */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Function to insert a node at the beginging of the linked list */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* res = NULL;
struct node* a = NULL;
/* Let us create a unsorted linked lists to test the functions
Created lists shall be a: 2->3->20->5->10->15 */
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&a, 20);
push(&a, 3);
push(&a, 2);
/* Sort the above created Linked List */
MergeSort(&a);
printf(" Sorted Linked List is: ");
printList(a);
getchar();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.