Skip to content

Instantly share code, notes, and snippets.

@sunxu

sunxu/main.c

Created November 29, 2012 13:03
Show Gist options
  • Save sunxu/4168907 to your computer and use it in GitHub Desktop.
Save sunxu/4168907 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. sunxu created this gist Nov 29, 2012.
    165 changes: 165 additions & 0 deletions main.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,165 @@
    #include <stdio.h>
    #include <stdbool.h>
    #include <stdlib.h>

    //链表节点，链表头结点不存储数据
    typedef struct _node{
    int data;
    struct _node * next;
    } node;

    typedef node* pnode;

    bool empty(pnode head){
    if(NULL == head || NULL == head->next)
    return true;
    return false;
    }

    pnode add_element(pnode head, int value){
    if (NULL == head) {
    return head;
    }

    pnode node = head;
    while (NULL != node->next && value > node->next->data) {
    node = node->next;
    }

    if(NULL != node->next && value == node->next->data){
    return head;
    }

    pnode new = malloc(sizeof(node));
    if (NULL == new) {
    return head;
    }

    new->next = node->next;
    node->next = new;
    new->data = value;

    return head;
    }

    void clear_list(pnode head){
    pnode t = head->next;
    pnode tmp;
    while (NULL != t) {
    tmp = t->next;
    free(t);
    t = tmp;
    }
    head->next = NULL;
    }

    bool has_same_element(pnode aHead, pnode bHead){
    if(empty(aHead))
    return false;

    if(empty(bHead))
    return false;

    aHead = aHead->next;
    bHead = bHead->next;

    while (NULL != aHead && NULL != bHead) {
    while (NULL != aHead && NULL != bHead && aHead->data < bHead->data) {
    aHead = aHead->next;
    }

    while (NULL != aHead && NULL != bHead && aHead->data > bHead->data) {
    bHead = bHead->next;
    }

    if(NULL != aHead && NULL != bHead && aHead->data == bHead->data){
    return true;
    }
    }

    return false;
    }

    pnode merge(pnode aHead, pnode bHead){
    if(NULL == aHead){
    perror("NULL pointer in merge()");
    exit(1);
    }

    if(empty(bHead))
    return aHead;

    bHead = bHead->next;
    while (NULL != bHead ) {
    add_element(aHead, bHead->data);
    bHead = bHead->next;
    }

    return aHead;
    }

    pnode combine(pnode aHead, int value){
    pnode tmpList = malloc(sizeof(node));
    tmpList->next = NULL;
    add_element(tmpList, value);

    pnode head = aHead->next;
    while (NULL != head) {
    add_element(tmpList, head->data + value);
    head = head->next;
    }

    merge(aHead, tmpList);
    free(tmpList);
    return aHead;
    }

    void print_list(pnode head){
    printf("list at %p ",head);
    head = head->next;
    while (NULL != head) {
    printf("%d ",head->data);
    head = head->next;
    }
    printf("\n");
    }

    bool has_zero_sum(int* value, int count){
    pnode positive = malloc(sizeof(node));
    pnode negative = malloc(sizeof(node));

    for (int i = 0; i < count; i++) {
    if(0 == value[i]){
    return true;
    }else if(0 < value[i]){
    combine(positive, value[i]);
    }else{
    combine(negative, -value[i]);
    }

    print_list(positive);
    print_list(negative);

    if (has_same_element(positive, negative)) {
    return true;
    }
    }

    return false;
    }


    int main(int argc, const char * argv[])
    {
    int value[]={12,34,23,67,-1,2,3,14,15,67,-9,42,56};
    //int value[]={-90,1,2,3,4,5,6,7,8};
    int count = sizeof(value)/sizeof(value[0]);

    if (has_zero_sum(value, count)) {
    printf("True\n");
    }else{
    printf("False\n");
    }

    return 0;
    }