snugkim
BAN USERIn C, it is a little bit of work to create doubly linked list.
#include<stdio.h>
#include<stdlib.h>
typedef struct ListNode {
int item;
struct ListNode *next;
struct ListNode *prev;
} node;
typedef struct List {
int size;
struct ListNode *head;
struct ListNode *tail;
} list;
node * createNode(int item) {
node * newnode = (node *) malloc(sizeof(node));
newnode->item = item;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
void insertNodeEnd(list * listFlower, int item) {
if (listFlower->head == NULL) {
listFlower->head = createNode(item);
listFlower->tail = listFlower->head;
listFlower->size++;
}
else {
node * conductor = listFlower->head;
while (conductor->next != NULL) {
conductor = conductor->next;
}
conductor->next = createNode(item);
conductor->next->prev = conductor;
listFlower->tail = conductor->next;
listFlower->size++;
}
}
void displayNode(list *listFlower) {
node * conductor = listFlower->head;
while (conductor != NULL) {
printf("%d ", conductor->item);
conductor = conductor->next;
}
printf("\n");
}
void displayNodeBackward(list *listFlower) {
node * conductor = listFlower->tail;
while (conductor != NULL) {
printf("%d ", conductor->item);
conductor = conductor->prev;
}
printf("\n");
}
int canPlaceFlowers(list * listFlower, int n) {
if (n > listFlower->size) {
return 0;
}
if (n == 0) {
return 1;
}
else if ( n==1 ) {
if (listFlower->size == 1) {
if (listFlower->head->item == 0) {
return 1;
}
else {
return 0;
}
}
}
int count = 0;
if (listFlower->head == NULL) {
return 0;
}
else {
node * conductor = listFlower->head;
while (conductor->next != NULL) {
if (conductor->prev != NULL) {
if (conductor->item == 0 && conductor->prev->item == 0 && conductor->next->item == 0) {
count++;
conductor->item = 1;
}
}
else {
if (conductor->item == 0 && conductor->next->item == 0) {
count++;
conductor->item = 1;
}
}
conductor = conductor->next;
}
if (conductor->prev->item == 0 && conductor->item == 0) {
count++;
conductor->item = 1;
}
if (count >= n) {
return 1;
}
else {
return 0;
}
}
}
int main() {
node *head = NULL;
node *tail = NULL;
list *listFlower = (list *) malloc(sizeof(list));
listFlower->head = head;
listFlower->tail = tail;
listFlower->size = 0;
int f, n = 10;
//printf("Please input the flowers in the flowerbed:(1 or 0)");
int array[10] = { 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 };
//int array[2] = { 0, 0 };
for (int i = 0; i < n; i++) {
//scanf("%d", &f);
insertNodeEnd(listFlower, array[i]);
}
displayNode(listFlower);
displayNodeBackward(listFlower);
int numFlower;
printf("Please input the number of flowers that you want to plant:");
printf("How many flowers? ");
scanf("%d", &numFlower);
int can = canPlaceFlowers(listFlower, numFlower);
if (can) {
printf("\ntrue\n");
}
else {
printf("\nfalse\n");
}
}
Sorry I am posting revised version. Previous one is not correct. I removed it but it seems that the post is not removed instantly. Here we go:
#include<stdlib.h>
#include<stdio.h>
int binarySearch(int * arr, int low, int high, int item)
{
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (item < arr[mid]) {
binarySearch(arr, low, mid, item);
}
else if (item > arr[mid]) {
binarySearch(arr, mid + 1, high, item);
}
else {
return mid;
}
}
int binarySearch_modified(int * arr, int low, int high, int length, int item)
{
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (item < arr[mid % length]) {
binarySearch_modified(arr, low, mid, length, item);
}
else if (item > arr[mid % length]) {
binarySearch_modified(arr, (mid + 1), high, length, item);
}
else {
return mid % length;
}
}
int main() {
int arr[6] = { 1, 2, 3, 4, 5, 6 };
int index = -1;
index = binarySearch(arr, 0, 5, 3);
if (index == -1) {
printf("not found\n");
}
else {
printf("found at index=%d\n", index);
}
int arr_shifted[6] = { 3, 4, 5, 6, 1, 2};
int shiftedBy = 4;
index = binarySearch_modified(arr_shifted, 0+shiftedBy, 5+shiftedBy, 6, 1);
if (index == -1) {
printf("not found\n");
}
else {
printf("found at index=%d\n", index);
}
}
Sorry. Please ignore my previous comment. I could not delete it.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int mystrcmp(char *a, char *b) {
if (a && b) {
while (*a == *b) {
if (*a == '\0' || *b == '\0') {
return 0;
}
a++;
b++;
}
return(*a - *b > 0 ? 1:-1);
}
else {
return 0;
}
}
void assertInt(int a, int b) {
if (a == b) {
printf("Passed\n");
}
else {
printf("Failed\n");
}
}
int main() {
char * a = "abc";
char * b = "def";
assertInt(strcmp(a, b), mystrcmp(a, b));
assertInt(strcmp("bcde", "bcde"), mystrcmp("bcde", "bcde"));
assertInt(strcmp("", "bcde"), mystrcmp("", "bcde"));
assertInt(strcmp("", ""), mystrcmp("", ""));
assertInt(strcmp("gde", ""), mystrcmp("gde", ""));
}
Implemented in C
#include<stdio.h>
#include<stdlib.h>
typedef struct listNode {
int item;
struct listNode * next;
} node;
node ** pHead;
node * createNode(int item) {
node * temp = (node *) malloc(sizeof(node));
temp->item = item;
temp->next = NULL;
return temp;
}
void insertNodeSorted(node * Head, int item) {
if (Head == NULL) {
(*pHead) = createNode(item);
}
else {
while (Head->next != NULL && Head->next->item < item)
Head = Head->next;
node * temp = Head->next;
Head->next = createNode(item);
Head->next->next = temp;
}
}
void displayNode(node * Head) {
while (Head != NULL) {
printf("%d ", Head->item);
Head = Head->next;
}
printf("\n");
}
int main() {
node * Head = NULL;
pHead = &Head;
insertNodeSorted(Head, 3);
insertNodeSorted(Head, 20);
insertNodeSorted(Head, 8);
insertNodeSorted(Head, 15);
insertNodeSorted(Head, 11);
displayNode(Head);
return 0;
}
- snugkim April 15, 2017