void FlattenList(node *head, node **tail)3 {
node *curNode = head; while (curNode){
/* The current node has a child */
2There are other, equally efficient solutions to this problem. One such solution involves insert- ing child lists after their parents rather than at the end of the list. 3You need a pointer to the tail pointer so that changes to the tail pointer are retained when the function returns.}
}
if (curNode->child) { Append(curNode->child, tail);
} curNode = curNode->next;
/* Appends the child list to the end of the tail and updates * the tail. */
void Append(node *child, node **tail) {
}
•
Unflatten the list. Restore the data structure to its original condi- tion before it was passed to FlattenList.
node *curNode;
/* Append the child child list to the end */ (*tail)->next = child;
child->prev = *tail;
/*Find the new tail, which is the end of the child child *list. */
for (curNode = child; curNode->next; curNode = curNode->next)
; /* Body intentionally empty */
/* Update the tail pointer now that curNode is the new
* tail.
*/ *tail = curNode;
void RemoveChars (char str[], char remove[]) {
}
int src, dst, removeArray[256];
/* Zero all elements in array */ for (src = 0; src <>
removeArray[src] = 0;
}
/* Set true for chars to be removed */ src = 0; while (remove[src]) {
removeArray[remove[src]] = 1; src++;
}
/* Copy char unless it must be removed */ src = dst = 0; do { /* do..while terminates after copying NUL */
if (!removeArray[str[src]]) { str[dst++] = str[src];
} } while (str[src++]);
void ReverseWords (char s t r [ ] )
{
int start = 0, end = 0, length; length = strlen(str);
/* Reverse entire string */ ReverseString(str, start, length - 1);
while (end <>
/* Save position of beginning of word */ start = end;
/* Scan to next non-word character */ while (end <>
end++;
/* Back up to end of word */ end--;
/* Reverse word */ ReverseString(str, start, end);
} end++; /* Advance to next token */92
Chapter 5
}
}
return;
void ReverseString (char str[], int start, int end) { char temp;
}
while (end > start) { /* Exchange characters */ temp = str [start]; str [start] = str [end] ; str[end] = temp;
/* Move indices towards middle */ start++; end--;
}
return;
int StrToInt (char str[]) {
}
int i = 0, isNeg = 0, num = 0;
if (str[0] == '-') { isNeg = 1;
i = 1;
}
while (str[i]) { num *= 10;
num += (str[i++] - '0');
}
if (isNeg) num *= -1;
return num;
}
void IntToStr(int num, char str[])
{
int i = 0, j =0, isNeg = 0; /* Buffer big enough for largest int, - sign and NUL */ char temp[MAX_DIGITS_INT + 2];
/* Check to see if the number is negative */ if (num <>
}
num *= -1; isNeg = 1;}
/* Fill buffer with digit characters in reverse order */ while (nutn) {
temp[i + + ] = (num % 10) + '0' ; nura /= 10;
if (isNeg) temp [i + + ] = ' - ' ;
/* Reverse the characters */ while (i > 0)
str[j+ + ] = temp[--i];
/* NUL terminate the string */ str[j] = '\0';
4. Recursive--inline--macro--linkage mingle--PrrProcessor
5. BInary Search
6. Permutation
int Permute( char inString[]) { int length, i, *used; char *out;
}
length = strlen(inString); out = (char *) malloc(length+l); if (!out)
return 0; /* Failed */
/* so printf doesn't run past the end of the buffer */ out[length] = '\0'; used = (int *) malloc(sizeof(int) * length); if (!used)
return 0; /* Failed */
/* start with no letters used, so zero array */ for (i = 0; i <>
used[i] = 0;
} DoPermute(inString, out, used, length, 0);
free(out); free(used); return 1; /* Success! */
void DoPermute(char in[], char out [] , int used[], int length, int recursLev)
{
}
int i ;
/* Base case */ if (recursLev == length) {
printf("%s\n", out); /* print permutation */ return;
}
/* Recursive case */ for (i = 0; i <>
•
Implement a function that prints all possible combinations of the characters in a string. These combinations range in length from one to the length of the string. Two combinations that differ only in ordering of their characters are the same combination. In other words, "12" and "31" are different combinations from the input string "123", but "21" is the same as "12".
}
if (used[i]) /* if used, skip to next letter */ continue;
out[recursLev] = in[i]; /* put current letter in output */ used[i] =1; /* mark this letter as used */ DoPermute(in, out, used, length, recursLev + 1); used[i] =0; /* unmark this letter */
5. Bit operations:
& | ^ << >> ~
6. number 1 in a number
int count(int number)
{
int cnt = 0;
while(number) {
number = number & (number - 1);
cnt++;
}
return cnt;
}
7. Semaphore: mutex: Spinlock: --sleep---Intr context--Process context---.Blocking mode
No comments:
Post a Comment