高级数据结构课设1.7z

/*******
 * 算法空间复杂度O（n）时间复杂度O（nlogn）
 * 运用双向链表O（1）删除元素，哈希的思想达到O（n）求出答案，排序用快排O（nlogn）
 * 瓶颈在排序上，可以用基数排序，复杂度可以控制在O（n）;
 ********/

#include 
#include 
#include 

#define MAXLINE 6
typedef struct Node Node;
typedef struct ListNode ListNode;

struct ListNode
{
    int val;
    ListNode *pre *next;
};

struct Node
{
    int val pos;
    ListNode *addr;
};

int
cmp_val（const void *a const void *b）
{
    return （（Node *）b）->val - （（Node *）a）->val;
}

int
cmp_pos（const void *a const void *b）
{
    return （（Node *）b）->pos - （（Node *）a）->pos;
}

ListNode*
link（ListNode *listnode ListNode *head Node *node）
{
    listnode->next = head;
    listnode->val = node->val;
    node->addr = listnode;
    if（head） head->pre = listnode;
    return listnode;
}

ListNode*
make_list（Node *arr）
{
    if（arr == NULL） return NULL;
    ListNode *head = NULL *tp = NULL;
    int i;
    for（i = 0; i < MAXLINE; ++i） {
        tp = （ListNode *） malloc（sizeof（ListNode））;
        tp->pre = tp->next = NULL;
        head = link（tp head arr）;
        ++arr;
    }
}

int
min（int a int b）
{
    return a > b ? b : a;
}

void
erase_node（ListNode *node）
{
    ListNode *tp = node;
    if（node->pre） node->pre->next = node->next;
    if（node->next） node->next->pre = node->pre;
    free（node）; node = NULL;
}

void
solve（Node *arr）
{
    if（arr == NULL） return;
    qsort（arr MAXLINE sizeof（Node） cmp_pos）;
    int *res = （int*） malloc（sizeof（int） * MAXLINE）;
    int cnt = MAXLINE - 1 i;
    for（i = 0; i < MAXLINE; ++i --cnt ++arr） {
        ListNode *tp = arr->addr;
        res[cnt] = 1<<30;
        if（tp->pre） res[cnt] = abs（tp->val - tp->pre->val）;
        if（tp->next） res[cnt] = min（res[cnt] abs（tp->val - tp->next->val））;
        erase_node（tp）;
    }
    res[0] = 0; //第一个元素默认为0
    for（i = 0; i < MAXLINE; ++i） {
        if（i） printf（“ “）;
        printf（“%d“ res[i]）;
    }
    printf（“\n“）;
    free（res）;
}

int
main（void）
{
    Node *arr = （Node *） malloc（sizeof（Node） * MAXLINE）;
    int i;
    for（i = 0; i < MAXLINE; ++i） {
        scanf（“%d“ &arr[i].val）;
        arr[i].pos = i;
    }
    qsort（arr MAXLINE sizeof（Node） cmp_val）;
    ListNode *head = make_list（arr）;
    solve（arr）;
    return 0;
}