|
Str_Misaligned in Double Link List
Hello all expert programmer, i truly new to C programming.
I hope you all can help me out from this trouble.
My program is a link list program which consists of char and int.
Below is my program :
Skip List Header File
#ifndef _SkipList_
#define _SkipList_
struct SkipNode
{
int value;
struct SkipNode **forward; // Array of pointer
};
struct SkipList
{
struct SkipNode *head;
int currentLevel;
/* The current level of the set is also
stored as this is needed by the insert,
delete and search algorithms
*/
};
#define MAX_LEVEL 4
#endif
Link List Header File :
#ifndef _LList_
#define _LList_
// Single Node
struct node
{
char customerName[20];
int customerNumber;
char transactionDescription[30];
struct node *next;
struct node *previous;
};
// Consists of many nodes as a Link List
struct LList
{
struct node *head;
struct node *tail;
};
// Add index to struct
#endif
Implementation File :
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h> // memset
#include "Link_List.h"
#include "Skip_List.h"
// -------------------------------------------------------
/*
1. Insert Behind // Done
2. Insert In Front // Done
3. Random Insert Front-nth // Done
4. Remove Behind until zero or one only // Done
5. Remove In Front // Done
6. Random Remove/RangeRemove -nth // Done
7. Display // Done
8. Length Index // Done
9. Palindrome
10. Full Reverse // Done // Circular Link List
Remove first node, insert front
Remove second node, insert front
11. merge // Done SortedMerge MergeSort
12. Count a particular int // Done
13. Get_Node_At_Index // Done
14. Split List // Done
15. Remove Duplicates // Done
16. Swap // Done
17. Empty // Done
18. Calcualte number of node can malloc
from heap memory
19. Middle of Link List // Done
20. Compare two link list
21.Interwine two link list // Done
Random and swap cannot operate in head and tail
Double Link List
Double Circular Link List
Associate Link List
Adjacency List
Skip List
Floyd's Cycle-Finding Algorithm(The Tortoise and the Hare Algorithm)
Josephus problem
Searching
move-to-front heuristic = Once an elemnt found move to
first node
Range search
Bi-Directional search
Linear search
Binary search
Sorting
Library Sort
Merge Sort
Radix sort
Bucket Sort
Index
[url]http://www.codeuu.com/[/url]
[url]http://www.nist.gov/dads/[/url]
[url]http://www-igm.univ-mlv.fr/~lecroq/string/node31.html[/url]
[url]http://www.thescripts.com/forum/thread708138.html[/url]
*/
/*
Random must have a index to indicate the postion where
almost same as array in order to achieve fast
processing
*/
/*
Memory Checking
these are some popular bounds-checking implementations
ccured [url]http://manju.cs.berkeley.edu/ccured/[/url]
cyclone [url]http://www.research.att.com/viewProject.cfm?prjID=67[/url]
splint [url]http://www.splint.org/[/url]
tinycc [url]http://fabrice.bellard.free.fr/tcc/[/url]
valgrind [url]http://valgrind.org/info/[/url]
rational purify [url]http://www-306.ibm.com/software/awdtools/purify/[/url]
electric fence [url]http://directory.fsf.org/project/ElectricFence/[/url]
parasoft insure++ [url]http://www.parasoft.com/jsp/products...product=Insure[/url]
more information: [url]http://www.doc.ic.ac.uk/teaching/pro...ewSuffield.pdf[/url]
Steensgaard’s algorithm
*/
// -------------------------------------------------------
// tail->next = head; Circular Link List
void draw();
int Main_menu();
int DLL_Function();
int ODCLL_Function();
int SL_Function();
int AL_Function();
int BST_Function();
// --------------------List Function----------------------
int number_list();
struct LList* list_allocate(struct LList *);
void list_deallocate(struct LList *);
void Initialize_List(struct LList *);
int LList_ValidateIsAlloc(struct LList *);
int* Method_Interwine(int *);
struct LList* Interwine(struct LList *, struct LList *);
struct LList* SortedInsert(struct LList *, struct node *);
struct LList* InsertBehind(struct LList *, struct node *);
struct LList* InsertFront(struct LList *, struct node*);
struct LList* RandomInsert(struct LList *, struct node*);
// Random Insert cannot insert at head and tail
struct LList* RemoveBehind(struct LList *);
struct LList* RemoveFront(struct LList *);
struct LList* RandomRemove(struct LList *);
// Random Remove cannot remove head and tail
struct LList* RemoveDuplicates(struct LList *);
struct LList* MergeList(struct LList *, struct LList *);
struct LList* SwapNode(struct LList *);
struct LList* ReverseSwapNode(struct LList *, struct node *, struct node *);
struct LList* ReverseList(struct LList *);
struct LList* MergeSort(struct LList *);
void SplitList(struct LList *);
void AISplitList(struct LList *);
void UserSplitList(struct LList *);
int count_specific_value(struct LList *);
int get_Value_at_index(struct LList *);
int Validate_Index(struct LList *, int);
int isEmpty(struct LList *);
int length_of_List(struct LList *);
int Middle_of_List(struct LList *);
// --------------------Node Function----------------------
struct node* node_allocate();
void node_deallocate(struct node *);
void Initialize_node(struct node *, int *);
int node_validateIsAlloc(struct node *);
void userInput(int *, struct node *);
void display(const struct LList *);
// -------------------Skip List---------------------------
// Skip List Function
struct SkipList* SL_allocate(struct SkipList *);
void SL_deallocate(struct SkipList *);
struct SkipList* SL_Insert(struct SkipList *, struct SkipNode *);
struct SkipList* SL_Remove(struct SkipList *);
// Skip Node Function
struct SkipNode* SN_allocate();
void SN_deallocate(struct node *);
void SN_Initialize(struct SkipNode *);
int SN_ValidateIsAlloc(struct SkipNode *);
int SN_Searching(struct SkipList *);
void SN_display(const struct SkipList *);
// ------------------------------------------------------
int main(int argc, char *argv[]) // char **argv
{
// Link List
struct LList *myList = 0;
struct LList *myListSecond = 0;
struct LList *myListThird = 0;
struct node *node;
int *ptr, numberSplit = 0, numberList, choice, DLL_choice, ODCLL_choice,
SL_choice, middle, length = 0, result,
number, *numberptr, resultNumber;
// DLL Function Continue variable
char Main_menu_continue = 'y', DLL_continue = 'y',
ODCLL_continue = 'y', SL_continue = 'y';
// Skip List
struct SkipList *mySkipList = 0;
struct SkipNode *skipNode;
numberptr = &number;
draw();
do
{
choice = Main_menu();
switch(choice)
{
case 1:
{
do
{
DLL_choice = DLL_Function();
switch(DLL_choice)
{
case 1:
{
numberList = number_list();
if (numberList == 1)
{
myList = list_allocate(myList);
}
else if (numberList == 2)
{
myList = myList;
myListSecond = list_allocate(myListSecond);
myListSecond = myListSecond;
}
else if (numberList == 3)
{
myListThird = list_allocate(myListThird);
}
break;
}
case 2:
{
node = node_allocate();
break;
}
case 3:
{
userInput(numberptr, node);
break;
}
case 4:
{
Initialize_node(node, numberptr);
break;
}
case 5:
{
if (numberList == 1)
{
myList = InsertBehind(myList, node);
}
else if (numberList == 2)
{
myListSecond = InsertBehind(myListSecond, node);
}
else if (numberList == 3)
{
myListThird = InsertBehind(myListThird, node);
}
break;
}
case 6:
{
if (numberList == 1)
{
myList = InsertFront(myList, node);
}
else if (numberList == 2)
{
myListSecond = InsertFront(myListSecond, node);
}
else if (numberList == 3)
{
myListThird = InsertFront(myListThird, node);
}
break;
}
case 7:
{
if (numberList == 1)
{
myList = RandomInsert(myList, node);
}
else if (numberList == 2)
{
myListSecond = RandomInsert(myListSecond, node);
}
else if (numberList == 3)
{
myListThird = RandomInsert(myListThird, node);
}
break;
}
case 8:
{
if (numberList == 1)
{
myList = RemoveBehind(myList);
}
else if (numberList == 2)
{
myListSecond = RemoveBehind(myListSecond);
}
else if (numberList == 3)
{
myListThird = RemoveBehind(myListThird);
}
break;
}
case 9:
{
if (numberList == 1)
{
myList = RemoveFront(myList);
}
else if (numberList == 2)
{
myListSecond = RemoveFront(myListSecond);
}
else if (numberList == 3)
{
myListThird = RemoveFront(myListThird);
}
break;
}
case 10:
{
if (numberList == 1)
{
myList = RandomRemove(myList);
}
else if (numberList == 2)
{
myListSecond = RandomRemove(myListSecond);
}
else if (numberList == 3)
{
myListThird = RandomRemove(myListThird);
}
break;
}
case 11:
{
if (numberList == 1)
{
myList = RemoveDuplicates(myList);
}
else if (numberList == 2)
{
myListSecond = RemoveDuplicates(myListSecond);
}
else if (numberList == 3)
{
myListThird = RemoveDuplicates(myListThird);
}
break;
}
case 12:
{
myList = MergeList(myList, myListSecond);
break;
}
case 13:
{
if (numberList == 1)
{
myList = SwapNode(myList);
}
else if (numberList == 2)
{
myListSecond = SwapNode(myListSecond);
}
else if (numberList == 3)
{
myListThird = SwapNode(myListThird);
}
break;
}
case 14:
{
if (numberList == 1)
{
SplitList(myList);
}
else if (numberList == 2)
{
SplitList(myListSecond);
}
else if (numberList == 3)
{
SplitList(myListThird);
}
break;
}
case 15:
{
if (numberList == 1)
{
resultNumber = count_specific_value(myList);
}
else if (numberList == 2)
{
resultNumber = count_specific_value(myListSecond);
}
else if (numberList == 3)
{
resultNumber = count_specific_value(myListThird);
}
break;
}
case 16:
{
if (numberList == 1)
{
result = get_Value_at_index(myList);
}
else if (numberList == 2)
{
result = get_Value_at_index(myListSecond);
}
else if (numberList == 3)
{
result = get_Value_at_index(myListThird);
}
break;
}
case 17:
{
if (numberSplit == 1)
{
myList = MergeSort(myList);
}
else if (numberSplit == 2)
{
myListSecond = MergeSort(myListSecond);
}
else if (numberSplit == 3)
{
myListThird = MergeSort(myListThird);
}
break;
}
case 18:
{
// Searching
break;
}
case 19:
{
if (numberList == 1)
{
middle = Middle_of_List(myList);
}
else if (numberList == 2)
{
middle = Middle_of_List(myListSecond);
}
else if (numberList == 3)
{
middle = Middle_of_List(myListThird);
}
break;
}
case 20:
{
if (numberList == 1)
{
length = length_of_List(myList);
}
else if (numberList == 2)
{
length = length_of_List(myListSecond);
}
else if (numberList == 3)
{
length = length_of_List(myListThird);
}
break;
}
case 21:
{
ptr = Method_Interwine(ptr);
if ( *(ptr + 0) == 1 && *(ptr + 1) == 2)
{
myList = Interwine(myList, myListSecond);
}
else if ( *(ptr + 0) == 1 && *(ptr + 1) == 3)
{
myList = Interwine(myList, myListThird);
}
else if ( *(ptr + 0) == 2 && *(ptr + 1) == 3)
{
myList = Interwine(myListSecond, myListThird);
}
if (ptr != NULL)
{
free(ptr);
}
break;
}
case 22:
{
if (numberList == 1)
{
myList = ReverseList(myList);
}
else if (numberList == 2)
{
myListSecond = ReverseList(myListSecond);
}
else if (numberList == 3)
{
myListThird = ReverseList(myListThird);
}
}
case 23:
{
if (numberList == 1)
{
display(myList);
}
else if (numberList == 2)
{
display(myListSecond);
}
else if (numberList == 3)
{
display(myListThird);
}
break;
}
default:
{
fprintf(stdout, "\n\n\t\t\tInvalid Choice");
break;
}
}
// fflush must put before scanf
fflush(stdin);
fprintf(stdout, "\n\n\t\tDouble Link List Continue : ");
scanf("%c", &DLL_continue);
}while(DLL_continue == 'y');
break;
}
case 2:
{
do
{
ODCLL_choice = ODCLL_Function();
switch(ODCLL_choice)
{
case 1:
{
numberList = number_list();
if (numberList == 1)
{
myList = list_allocate(myList);
}
else if (numberList == 2)
{
myList = myList;
myListSecond = list_allocate(myListSecond);
myListSecond = myListSecond;
}
else if (numberList == 3)
{
myListThird = list_allocate(myListThird);
}
break;
}
case 2:
{
node = node_allocate();
break;
}
case 3:
{
userInput(numberptr, node);
break;
}
case 4:
{
Initialize_node(node, numberptr);
break;
}
case 5:
{
if (numberList == 1)
{
myList = SortedInsert(myList, node);
}
else if (numberList == 2)
{
myListSecond = SortedInsert(myListSecond, node);
}
else if (numberList == 3)
{
myListThird = SortedInsert(myListThird, node);
}
break;
}
case 6:
{
if (numberList == 1)
{
myList = RemoveBehind(myList);
}
else if (numberList == 2)
{
myListSecond = RemoveBehind(myListSecond);
}
else if (numberList == 3)
{
myListThird = RemoveBehind(myListThird);
}
break;
}
case 7:
{
if (numberList == 1)
{
display(myList);
}
else if (numberList == 2)
{
display(myListSecond);
}
else if (numberList == 3)
{
display(myListThird);
}
break;
}
default:
{
fprintf(stdout, "\n\n\t\t\tInvalid Choice");
break;
}
}
// fflush must put before scanf
fflush(stdin);
fprintf(stdout, "\n\n\t\tOrder Double Link List Continue : ");
scanf("%c", &ODCLL_continue);
}while(ODCLL_continue == 'y');
break;
}
case 3:// Skip List
{
do
{
SL_choice = SL_Function();
switch(SL_choice)
{
case 1:
{
mySkipList = SL_allocate(mySkipList);
break;
}
case 2:
{
skipNode = SN_allocate();
break;
}
case 3:
{
userInput(numberptr, node);
break;
}
case 4:
{
SN_Initialize(skipNode);
break;
}
case 5:
{
mySkipList = SL_Insert(mySkipList, skipNode);
break;
}
case 6:
{
mySkipList = SL_Remove(mySkipList);
break;
}
case 7:
{
break;
}
case 8:
{
break;
}
case 9:
{
break;
}
default:
{
fprintf(stdout, "\n\n\t\t\tInvalid Choice");
break;
}
}
// fflush must put before scanf
fflush(stdin);
fprintf(stdout, "\n\n\t\t\tSkip Lis Continue : ");
scanf("%c", &SL_continue);
}while(SL_continue == 'y');
break;
}
case 4:
{
break;
}
case 5:
{
break;
}
default:
{
break;
}
}
fflush(stdin);
fprintf(stdout, "\n\n\t\t\tMain Menu Continue : ");
scanf("%c", &Main_menu_continue);
}while(Main_menu_continue == 'y');
if (myList != NULL)
{
free(myList);
}
if (myListSecond != NULL)
{
free(myListSecond);
}
if (myListThird != NULL)
{
free(myListThird);
}
//*/
// -----------Testing Purposes------------------------
return 0;
}
// ------------------------------------------------------
void draw()
{
int loop;
printf("\n\n\n ");
for (loop=0;loop<60;loop++)
{
printf("-");
}
printf("\n\n\t Welcome to newly Link List Simulation Program");
printf("\n\n ");
for (loop=0;loop<60;loop++)
{
printf("-");
}
printf("\n\n\n\n\n");
}
// -------------------------------------------------------
int number_list()
{
int number;
fprintf(stdout, "\n\n\t\t Which list to allocate : ");
scanf("%d", &number);
return number;
}
// -------------------------------------------------------
struct LList* list_allocate(struct LList *myList)
{
int count = 1;
do
{
myList = (struct LList *)malloc(sizeof(struct LList));
assert(myList != NULL);
// Ptr must initialize No dangling ptr
if (count == 2)
{
fprintf(stdout, "\n\t\t\tList Memory Allocation unsuccessful");
exit(0);
}
count++;
fflush(stdout);
}while( LList_ValidateIsAlloc(myList) == 0 && count < 3);
/*
Continue to loop even though memory is exhausted
for first time but not over second times because
this is unrealistic
*/
Initialize_List(myList); // Initilize Link List
return myList;
}
// -------------------------------------------------------
void list_deallocate(struct LList *myList)
{
if (myList != NULL)
{
free(myList);
myList = NULL;
}
else
{
exit(0);
}
}
// -------------------------------------------------------
void Initialize_List(struct LList *myList)
{
if (LList_ValidateIsAlloc(myList) != 0) // Not NULL
{
myList->head = NULL;
myList->tail = NULL;
}
else
{
exit(0);
}
}
// -------------------------------------------------------
int LList_ValidateIsAlloc(struct LList *myList)
{
assert(myList != NULL);
// If allocation is successful, then return true
if (myList != NULL)
{
// fprintf(stdout, "Memory Allocation successful");
return 1;
}// Three control structure
else
{
fprintf(stdout, "Memory exhausted");
return 0;
}
}
// -------------------------------------------------------
struct node* node_allocate()
{
struct node *node;
int count = 1;
do
{
node = (struct node *)malloc(sizeof(struct node));
assert(node != 0);
count++;
}while( node_validateIsAlloc(node) == 0 && count < 3);
if (node != NULL)
{
return node;
}
else
{
exit(0);
}
}
// -------------------------------------------------------
void node_deallocate(struct node *node)
{
if (node != NULL)
{
free(node);
node = NULL;
}
else
{
exit(0);
}
}
// -------------------------------------------------------
void Initialize_node(struct node *node, int * numberptr)
{
if (node != NULL)
{
node->next = NULL;
node->customerNumber = *numberptr;
}
}
// -------------------------------------------------------
int node_validateIsAlloc(struct node *node)
{
// If allocation is successful, then return true
if (node != NULL)
{
fprintf(stdout, "\n\n\t\tNode Memory Allocation successful");
return 1;
}
else
{
fprintf(stdout, "Memory exhausted");
return 0;
}
}
// ------------------------------------------------------
void userInput(int *numberptr, struct node *node)
{
int number;
fflush(stdin);
printf("\n\t\t\tEnter Customer Name : ");
gets(node->customerName);
fflush(stdin);
printf("\n\t\t\tEnter Customer Number : ");
fflush(stdin);
scanf("%d", &number);
fflush(stdin);
printf("\n\t\t\tEnter Transaction description : ");
gets(node->transactionDescription);
*numberptr = number;
}
// ------------------------------------------------------
struct LList* SortedInsert(struct LList *myList, struct node *node)
{
struct node *traversal, *traversal_before;
int length;
if (myList != NULL)
{
traversal = myList->head;
traversal_before = myList->head;
if (myList->head == NULL)
{
myList->head = node;
myList->tail = node; // Traversal ptr
// Circular
// myList->tail->next = myList->head;
}
else
{
length = 1;
while(traversal->next != NULL && traversal->customerNumber < node->customerNumber)
{
traversal = traversal->next;
traversal_before = traversal_before->next;
length++;
}
// Insert after traversal
if (traversal->customerNumber < node->customerNumber)
{
if (traversal->next != NULL)
{
// Node next point to traversal next
/*
1(traversal)
2(node)
3(traversal->next)
*/
node->next = traversal->next;
// 2 -> 3
}
traversal->next = node;
node->previous = traversal;
while(traversal != NULL)
{
traversal = traversal->next;
myList->tail = traversal;
}
}
// Insert before traversal
else
{
if (length == 1)
{
node->next = traversal;
traversal->previous = node;
myList->head = node;
myList->tail = node;
}
else
{
traversal_before = traversal_before->previous;
traversal_before->next = node;
node->previous = traversal_before;
node->next = traversal;
traversal->previous = node;
}
}
}
}
else
{
exit(0);
}
return myList;
}
// ------------------------------------------------------
struct LList* InsertBehind(struct LList *myList, struct node *node)
{
if (myList != NULL)
{
if (myList->head == NULL)
{
myList->head = node;
myList->tail = node; // Traversal ptr
myList->tail->next = NULL;
node->previous = NULL;
node->next = NULL;
return myList;
}
else
{
while (myList->tail != NULL)
{
myList->tail->next = node; // Previous node point to newly node
node->previous = myList->tail; // New node point to previous node
myList->tail = node; // Traversal to new node
return myList;
}
}
}
else
{
return myList;
}
return myList;
}
// ------------------------------------------------------
struct LList* InsertFront(struct LList *myList, struct node *node)
{
struct LList *tempHead;
if (myList != NULL)
{
tempHead = (struct LList *)malloc(sizeof(struct LList *));
assert(tempHead != 0);
if ( LList_ValidateIsAlloc(tempHead) == 1 )
{
tempHead->head = myList->head;
node->next = myList->head;
node->previous = NULL;
myList->head = node;
}
else
{
exit(0);
}
free(tempHead);
}
else
{
return myList;
}
return myList;
}
// ------------------------------------------------------
struct LList* RandomInsert(struct LList *myList, struct node *node)
{
struct node *traversal_First;
struct node *traversal_Second;
struct node *dummy_one;
struct node *dummy_two;
// Position of node insert
int index, length = 1;
if (myList != NULL)
{
traversal_First = myList->head;
traversal_Second = myList->head;
dummy_one = myList->head;
dummy_two = myList->head;
do
{
printf("\n\n\t\t\t\tEnter a index to random insert : ");
scanf("%d", &index); // Validate index no exceed length of list
if ( Validate_Index(myList, index) == 1 )
{
length = 1;
while (myList->tail != NULL && traversal_Second != NULL)
{
if (length == index)
{
traversal_First = traversal_First->previous;
traversal_First->next = node;
node->next = traversal_Second;
node->previous = traversal_First;
traversal_Second->previous = node;
goto exit;
}
traversal_First = traversal_First->next;
traversal_First->previous = dummy_one;
dummy_one = traversal_First;
traversal_Second = traversal_Second->next;
traversal_Second->previous = dummy_two;
dummy_two = traversal_Second;
length++;
}
exit:
return myList;
}
}while( Validate_Index(myList, index) == 0);
}
else
{
return myList;
}
}
// -----------------------------------------------------
struct LList* RemoveBehind(struct LList *myList)
{
struct node *traversal;
struct node *dummy;
int length = 1, real_length;
int numberNode;
real_length = length_of_List(myList);
if (myList != NULL)
{
do
{
fprintf(stdout, "\n\n\t\t\tHow many removed node count from behind : ");
scanf("%d", &numberNode);
}while(numberNode > real_length || numberNode == 0);
traversal = myList->head;
length = 1;
while (traversal->next != NULL)
{
traversal = traversal->next;
length++;
}
// 1 2 3 4 5
numberNode = length - numberNode;
do
{
dummy = myList->tail;
myList->tail = myList->tail->previous;
dummy->customerNumber = NULL;
node_deallocate(dummy); // free what pointed by dummy Error
length--;
}while(length != numberNode);
// myList->tail->next = NULL;
}
else
{
return myList;
}
myList = myList;
return myList;
}
// -----------------------------------------------------
struct LList* RemoveFront(struct LList *myList)
{
struct node *removeHead, *removeTail, *traversal, *dummy;
int numberNode, length, loop;
if (myList != NULL)
{
removeHead = myList->head;
removeTail = myList->head;
traversal = myList->head;
dummy = myList->head;
do
{
fprintf(stdout, "\n\n\t\t\tHow many removed node count from in front : ");
scanf("%d", &numberNode);
length = length_of_List(myList);
}while(numberNode > length || numberNode == length || numberNode == 0);
myList->head = myList->head->next;
for (loop=0;loop<numberNode - 1;loop++)
{
myList->head = myList->head->next;
removeTail = removeTail->next;
}
removeTail->next = NULL;
myList->head->previous = NULL;
do
{
dummy = removeHead;
removeHead = removeHead->next;
traversal = traversal->next;
dummy->customerNumber = NULL;
node_deallocate(dummy);
}while(traversal != NULL);
}
else
{
return myList;
}
return myList;
}
// ------------------------------------------------------
struct LList* RandomRemove(struct LList *myList)
{
struct node *traversal, *traversal_first, *middle, *middle_two, *freeNode;
int indexOne, indexTwo, length, remove_length; // To form a range
if (myList != NULL)
{
traversal = myList->head;
traversal_first = myList->head;
middle = myList->head;
middle_two = myList->head;
length = length_of_List(myList);
fprintf(stdout, "\n\n\t\t Enter an index or range to remove : ");
do
{
fprintf(stdout, "\n\n\t\t Enter random remove first index : ");
scanf("%d", &indexOne);
fprintf(stdout, "\n\n\t\t Enter random remove second index : ");
scanf("%d", &indexTwo);
}while(indexOne > length || indexTwo > length || indexOne == 0);
// Range Remove
if (indexTwo != 0)
{
length = 1;
while(traversal_first->next != NULL)
{
if (indexTwo >= length)
{
traversal_first = traversal_first->next;
middle_two = middle_two->next;
length++;
}
if (length <= indexOne)
{
traversal = traversal->next;
middle = middle->next;
}
/* if (length <= indexTwo)
{
middle_two = middle_two->next;
}*/
if (indexOne == length)
{
traversal = traversal->previous;
traversal->next = NULL;
}
if (length - 1 == indexTwo)
{
//middle_two = middle_two->previous;
//middle_two->next = NULL;
traversal_first->previous = NULL;
remove_length = (indexTwo - indexOne) + 1;
length = 1;
while(length <= remove_length)
{
freeNode = middle;
if (middle->next != NULL)
{
middle = middle->next;
}
middle->previous = NULL;
freeNode->customerNumber = 0;
freeNode->previous = NULL;
freeNode->next = NULL;
node_deallocate(freeNode);
length++;
}
traversal->next = traversal_first;
traversal_first->previous = traversal;
goto exit;
}
}
}
// Single Random Remove
else
{
length = 1;
while(traversal != NULL)
{
if (indexOne == length)
{
traversal = traversal->previous;
traversal_first = traversal_first->next;
traversal->next = traversal_first;
traversal_first->previous = traversal;
middle->customerNumber = NULL;
node_deallocate(middle);
goto exit;
}
traversal = traversal->next;
traversal_first = traversal_first->next;
middle = middle->next;
length++;
}
}
}
else
{
exit(0);
}
exit:
return myList;
}
// ------------------------------------------------------
struct LList* RemoveDuplicates(struct LList *myList)
{
struct node *traversal, *traversal_before,
*traversal_remove, *traversal_after;
int temp_length = 1, length, inner_loop = 1;
char deallocate = 'n';
if (myList != NULL)
{
traversal = myList->head;
traversal_remove = myList->head;
traversal_before = myList->head;
traversal_after = myList->head;
length = length_of_List(myList);
// Compare and to remove duplicates
while(traversal != NULL)
{
traversal_remove = myList->head;
traversal_before = myList->head;
traversal_after = myList->head;
inner_loop = 1;
while(traversal_after != NULL)
{
deallocate = 'n';
if (temp_length == inner_loop)
{
if (traversal_after->next != NULL)
{
traversal_remove = traversal_remove->next;
traversal_before = traversal_before->next;
traversal_after = traversal_after->next;
inner_loop++;
}
}
// Two customers can have same name but not customer number
if (traversal->customerNumber == traversal_remove->customerNumber
&& traversal->customerName == traversal_remove->customerName)
{
if (traversal_remove->next == NULL && inner_loop == length)
{
traversal_before = traversal_before->previous;
traversal_before->next = NULL;
deallocate = 'y';
}
else
{
traversal_before = traversal_before->previous;
if (traversal_after->next != NULL)
{
traversal_before->next = traversal_after->next;
traversal_after->next->previous = traversal_before;
deallocate = 'y';
}
}
}
traversal_after = traversal_after->next;
traversal_before = traversal_after;
if (deallocate == 'y')
{
node_deallocate(traversal_remove);
}
traversal_remove = traversal_after;
inner_loop++;
}
traversal = traversal->next;
temp_length++;
}
}
else
{
return myList;
}
return myList;
}
// ------------------------------------------------------
struct LList* MergeList(struct LList *first, struct LList *second)
{
struct node *dummy;
if (first != NULL && second != NULL)
{
dummy = first->tail;
first->tail->next = second->head; // first list point to second list
first->tail = first->tail->next; // traverse to new tail after merge list
first->tail->previous = dummy; // tail node point back to second last node
second = NULL;
dummy = NULL;
free(second);
free(dummy);
}
else
{
return first;
}
return first;
}
// ------------------------------------------------------
struct LList* MergeSort(struct LList *myList)
{
return myList;
}
// ------------------------------------------------------
int* Method_Interwine(int *ptr)
{
int numberFirstList, numberSecondList;
ptr = (int *)malloc(sizeof(int) * 2);
assert (ptr != NULL);
// fflush(stdin);
if (ptr != NULL)
{
printf("\n\n\t\t\tEnter First List : ");
scanf("%d", &numberFirstList);
// fflush(stdin);
printf("\n\t\t\tEnter Second List : ");
scanf("%d", &numberSecondList);
if (numberFirstList != 0 && numberSecondList != 0)
{
*(ptr + 0) = numberFirstList;
*(ptr + 1) = numberSecondList;
}
}
else
{
exit(0);
}
// To ensure the function definition malloc memory
// is appear in main
return ptr;
}
// ------------------------------------------------------
struct LList* Interwine(struct LList *myList, struct LList *myListSecond)
{
struct node *traversal_first, *traversal_second;
// Traversal for first list after current
struct node *traversal_next;
int length, first_length, second_length;
/*
Interwine example
First List - 6,3,8,1,44
Second List - 9,-3,10,100,54
Result - 6,9,3,-3,8,10,1,100,44,54
*/
first_length = length_of_List(myList);
second_length = length_of_List(myListSecond);
if (first_length >= 2 && second_length >= 2)
{
if (myList != NULL && myListSecond != NULL)
{
traversal_first = myList->head;
traversal_second = myListSecond->head;
// Point at second node of first list
traversal_next = myList->head->next;
length = 1;
do
{
// Algorithm
// Pointing
if (myListSecond->head->next != NULL)
{
myListSecond->head = myListSecond->head->next;
}
// // bug
if (length != 1 && length != second_length)
{
traversal_second = myListSecond->head->previous;
}
if (length == second_length)
{
traversal_second = myListSecond->head;
}
traversal_first->next = traversal_second;
traversal_second->previous = traversal_first;
traversal_second->next = traversal_next;
// bug
if (traversal_next != NULL)
{
traversal_next->previous = traversal_second;
}
if (traversal_first->next != NULL && traversal_first->next->next)
{
traversal_first = traversal_first->next->next;
}
if (myList->tail != NULL && traversal_next != NULL)
{
traversal_next = traversal_next->next;
}
if (myList->tail->next != NULL)
{
myList->tail = myList->tail->next;
}
length++;
if (length == second_length + 1)
{
// myListSecond->head->next = NULL;
// myListSecond->tail->previous = NULL;
goto exit;
}
}while(myList->tail != NULL);
}
else
{
exit(0);
}
}
exit:
display(myList);
// list_deallocate(myListSecond);
return myList;
}
// ------------------------------------------------------
void SplitList(struct LList *myList)
{
int choice;
printf("\n\n\t\t\t\t 1. AI Split\n\t\t\t\t 2. User Split");
fprintf(stdout, "\n\n\t\t\t\t Enter a Choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
{
if (myList != NULL)
{
AISplitList(myList);
}
break;
}
case 2:
{
if (myList != NULL)
{
UserSplitList(myList);
}
break;
}
default:
{
fprintf(stdout, "Invalid choice");
}
}
}
// ------------------------------------------------------
void AISplitList(struct LList *myList)
{
struct LList *firstList, *secondList, *thirdList,
*fourthList, *fifthList;
// Temp Tail
struct node *traversal, *traversal_second,
*traversal_third, *traversal_fourth,
*traversal_fifth;
// temp_length indicate location to split
// real_length indicate real length
// user_length indicate length to split
int temp_remainder, user_length, temp_length = 1,
numberSplit, real_length, count_list = 1;
float remainder ;
traversal = myList->head;
traversal_second = myList->head;
traversal_third = myList->head;
traversal_fourth = myList->head;
traversal_fifth = myList->head;
firstList = (struct LList *)malloc(sizeof(struct LList));
assert (firstList != 0);
secondList = (struct LList *)malloc(sizeof(struct LList));
assert (secondList != 0);
thirdList = (struct LList *)malloc(sizeof(struct LList));
assert (thirdList != 0);
fourthList = (struct LList *)malloc(sizeof(struct LList));
assert (fourthList != 0);
fifthList = (struct LList *)malloc(sizeof(struct LList));
assert (fifthList != 0);
real_length = length_of_List(myList);
/*
AI
This may seems unrealistic in real world database
application
*/
if (real_length <= 10)
{
fprintf(stdout, "\n\n\t\t\tRecommended number of split is 2 List");
}
else if (real_length > 10 && real_length <= 20)
{
fprintf(stdout, "\n\n\t\t\tRecommended number of split is 2 and 4 List");
}
else if (real_length > 20 && real_length <= 50)
{
fprintf(stdout, "\n\n\t\t\tRecommended number of split is 5 List");
}
else
{
fprintf(stdout, "\n\n\t\t\tRecommended number of split cannot be achieve");
}
do
{
fprintf(stdout, "\n\n\t\t\t\tHow many list to split : ");
scanf("%d", &numberSplit);
}while(numberSplit > real_length && numberSplit == real_length || numberSplit == 0 && numberSplit < 6);
// Make it as balanced as possible How to split perfect split and not balance split 2-3,3-4(2-5),4-5
user_length = real_length;
// --------------------------------------------
/*
UL
NS __
Remainder < 2 _____|
| |__
Got ________________|
Remainder | | __
| |_____|
______________| |__
| |
| |
| |________________
|
_______________| Remainder >= 2
|
| ________ NS ________ UL
| |
| |
|______________|
|
No |
Remainder |________ NS ________ UL
*/
if (real_length % numberSplit != 0)
{
// User length is length of sub list
// To check remainder
if (real_length % numberSplit < 2)
{
// Remainder 1/2 = 0.5
temp_remainder = user_length % numberSplit;
remainder = (float)temp_remainder;
// Handle remainder = 1
remainder = remainder / numberSplit;
user_length = user_length / numberSplit;
if (remainder >= 0.5)
{
user_length = user_length + 1;
if (numberSplit == 2)
{
// 5/2
if (user_length == 3)
{
while(traversal_second != NULL)
{
while(count_list <= numberSplit)
{
if (count_list == 1)
{
if (temp_length == 1)
{
firstList->head = traversal;
traversal = traversal->next;
traversal_second = traversal_second->next;
}
if (temp_length == 2)
{
traversal = traversal->next;
traversal_second = traversal_second->next;
}
if (temp_length == 3)
{
firstList->tail = traversal;
traversal_second = traversal_second->next;
}
goto loop;
}
if (count_list == 2)
{
if (temp_length == 1)
{
secondList->head = traversal_second;
firstList->tail->next = NULL;
secondList->head->previous = NULL;
traversal_second = traversal_second->next;
}
if (temp_length == 2)
{
secondList->tail = traversal_second;
goto exit;
}
goto loop;
}
}
loop:
temp_length++;
if (temp_length > user_length && count_list != 3)
{
temp_length = 1;
count_list++;
}
}
}
// 7/2
if (user_length == 4)
{
while(traversal_second != NULL)
{
while(count_list <= numberSplit)
{
if (count_list == 1)
{
if (temp_length == 1)
{
firstList->head = traversal;
traversal = traversal->next;
traversal_second = traversal_second->next;
}
if (temp_length == 2 || temp_length == 3)
{
traversal = traversal->next;
traversal_second = traversal_second->next;
}
if (temp_length == 4)
{
firstList->tail = traversal;
traversal_second = traversal_second->next;
}
goto loop1;
}
if (count_list == 2)
{
if (temp_length == 1)
{
secondList->head = traversal_second;
firstList->tail->next = NULL;
secondList->head->previous = NULL;
traversal_second = traversal_second->next;
}
if (temp_length == 2)
{
traversal_second = traversal_second->next;
}
if (temp_length == 3)
{
secondList->tail = traversal_second;
goto exit;
}
goto loop1;
}
}
loop1:
temp_length++;
if (temp_length > user_length && count_list != 3)
{
temp_length = 1;
count_list++;
}
}
}
// 9/2
if (user_length == 5)
{
while(traversal_second != NULL)
{
while(count_list <= numberSplit)
{
if (count_list == 1)
{
if (temp_length == 1)
{
firstList->head = traversal;
traversal = traversal->next;
traversal_second = traversal_second->next;
}
if (temp_length == 2 || temp_length == 3 || temp_length == 4)
{
traversal = traversal->next;
traversal_second = traversal_second->next;
}
if (temp_length == 5)
{
firstList->tail = traversal;
traversal_second = traversal_second->next;
}
goto loop2;
}
if (count_list == 2)
{
if (temp_length == 1)
{
secondList->head = traversal_second;
firstList->tail->next = NULL;
secondList->head->previous = NULL;
traversal_second = traversal_second->next;
}
if (temp_length == 2 || temp_length == 3)
{
traversal_second = traversal_second->next;
}
if (temp_length == 4)
{
secondList->tail = traversal_second;
goto exit;
}
goto loop2;
}
loop2:
temp_length++;
if (temp_length > user_length && count_list != 3)
{
temp_length = 1;
count_list++;
}
}
}
}
}
// 14/4
if (numberSplit == 4)
{
if (user_length == 4)
{
while(traversal_fourth != NULL)
{
while(count_list <= numberSplit)
{
if (count_list == 1)
{
if (temp_length == 1)
{
firstList->head = traversal;
traversal = traversal->next;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
traversal_fourth = traversal_fourth->next;
}
if (temp_length == 2 || temp_length == 3)
{
traversal = traversal->next;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
traversal_fourth = traversal_fourth->next;
}
if (temp_length == 4)
{
firstList->tail = traversal;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
traversal_fourth = traversal_fourth->next;
}
goto loop9;
}
if (count_list == 2)
{
if (temp_length == 1)
{
secondList->head = traversal_second;
firstList->tail->next = NULL;
secondList->head->previous = NULL;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
traversal_fourth = traversal_fourth->next;
}
if (temp_length == 2 || temp_length == 3)
{
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
traversal_fourth = traversal_fourth->next;
}
if (temp_length == 4)
{
secondList->tail = traversal_second;
traversal_third = traversal_third->next;
traversal_fourth = traversal_fourth->next;
}
goto loop9;
}
if (count_list == 3)
{
if (temp_length == 1)
{
thirdList->head = traversal_third;
secondList->tail->next = NULL;
thirdList->head->previous = NULL;
traversal_third = traversal_third->next;
traversal_fourth = traversal_fourth->next;
}
if (temp_length == 2 || temp_length == 3)
{
traversal_third = traversal_third->next;
traversal_fourth = traversal_fourth->next;
}
if (temp_length == 4)
{
thirdList->tail = traversal_third;
traversal_fourth = traversal_fourth->next;
}
goto loop9;
}
if (count_list == 4)
{
if (temp_length == 1)
{
fourthList->head = traversal_fourth;
thirdList->tail->next = NULL;
fourthList->head->previous = NULL;
traversal_fourth = traversal_fourth->next;
}
if (temp_length == 2)
{
fourthList->tail = traversal_fourth;
goto exit;
}
goto loop9;
}
loop9:
temp_length++;
if (temp_length > user_length && count_list != 4)
{
temp_length = 1;
count_list++;
}
}
}
}
}
}
// Remainder not equal to 0.5
// Handle remainder = 2
else
{
if (numberSplit == 3)
{
// 7/3
if (user_length == 2)
{
while(traversal_third != NULL)
{
while(count_list <= numberSplit)
{
if (count_list == 1)
{
if (temp_length == 1)
{
firstList->head = traversal;
traversal = traversal->next;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
if (temp_length == 2)
{
firstList->tail = traversal;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
goto loop3;
}
if (count_list == 2)
{
if (temp_length == 1)
{
secondList->head = traversal_second;
firstList->tail->next = NULL;
secondList->head->previous = NULL;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
if (temp_length == 2)
{
secondList->tail = traversal_second;
traversal_third = traversal_third->next;
}
goto loop3;
}
if (count_list == 3)
{
if (temp_length == 1)
{
thirdList->head = traversal_third;
secondList->tail->next = NULL;
thirdList->head->previous = NULL;
traversal_third = traversal_third->next;
}
if (temp_length == 2)
{
traversal_third = traversal_third->next;
}
if (temp_length == 3)
{
thirdList->tail = traversal_third;
goto exit;
}
goto loop3;
}
loop3:
temp_length++;
if (temp_length > user_length && count_list != 3)
{
temp_length = 1;
count_list++;
}
}
}
}
// 13/3
if (user_length == 4)
{
while(traversal_third != NULL)
{
while(count_list <= numberSplit)
{
if (count_list == 1)
{
if (temp_length == 1)
{
firstList->head = traversal;
traversal = traversal->next;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
if (temp_length == 2 || temp_length == 3)
{
traversal = traversal->next;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
if (temp_length == 4)
{
firstList->tail = traversal;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
goto loop4;
}
if (count_list == 2)
{
if (temp_length == 1)
{
secondList->head = traversal_second;
firstList->tail->next = NULL;
secondList->head->previous = NULL;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
if (temp_length == 2 || temp_length == 3)
{
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
if (temp_length == 4)
{
secondList->tail = traversal_second;
traversal_third = traversal_third->next;
}
goto loop4;
}
if (count_list == 3)
{
if (temp_length == 1)
{
thirdList->head = traversal_third;
secondList->tail->next = NULL;
thirdList->head->previous = NULL;
traversal_third = traversal_third->next;
}
if (temp_length == 2 || temp_length == 3 || temp_length == 4)
{
traversal_third = traversal_third->next;
}
if (temp_length == 5)
{
thirdList->tail = traversal_third;
goto exit;
}
goto loop4;
}
loop4:
temp_length++;
if (temp_length > user_length && count_list != 3)
{
temp_length = 1;
count_list++;
}
}
}
}
// 16/3
if (user_length == 5)
{
while(traversal_third != NULL)
{
while(count_list <= numberSplit)
{
if (count_list == 1)
{
if (temp_length == 1)
{
firstList->head = traversal;
traversal = traversal->next;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
if (temp_length == 2 || temp_length == 3 || temp_length == 4)
{
traversal = traversal->next;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
if (temp_length == 5)
{
firstList->tail = traversal;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
goto loop5;
}
if (count_list == 2)
{
if (temp_length == 1)
{
secondList->head = traversal_second;
firstList->tail->next = NULL;
secondList->head->previous = NULL;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
if (temp_length == 2 || temp_length == 3 || temp_length == 4)
{
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
}
if (temp_length == 5)
{
secondList->tail = traversal_second;
traversal_third = traversal_third->next;
}
goto loop5;
}
if (count_list == 3)
{
if (temp_length == 1)
{
thirdList->head = traversal_third;
secondList->tail->next = NULL;
thirdList->head->previous = NULL;
traversal_third = traversal_third->next;
}
if (temp_length == 2 || temp_length == 3 || temp_length == 4 || temp_length == 5)
{
traversal_third = traversal_third->next;
}
if (temp_length == 6)
{
thirdList->tail = traversal_third;
goto exit;
}
goto loop5;
}
loop5:
temp_length++;
if (temp_length > user_length && count_list != 3)
{
temp_length = 1;
count_list++;
}
}
}
}
}
if (numberSplit == 4)
{
// 9/4
if (user_length == 2)
{
while(traversal_fourth != NULL)
{
while(count_list <= numberSplit)
{
if (count_list == 1)
{
if (temp_length == 1)
{
firstList->head = traversal;
traversal = traversal->next;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
traversal_fourth = traversal_fourth->next;
}
if (temp_length == 2)
{
firstList->tail = traversal;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
traversal_fourth = traversal_fourth->next;
}
goto loop6;
}
if (count_list == 2)
{
if (temp_length == 1)
{
secondList->head = traversal_second;
firstList->tail->next = NULL;
secondList->head->previous = NULL;
traversal_second = traversal_second->next;
traversal_third = traversal_third->next;
traversal_fourth = traversal_fourth->next;
}
if (temp_length == 2)
{
secondList->tail = traversal_second;
|
29-Feb-2008, 07:05
