list.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LEN 10          /* 链表长度 */
#define MAX 99          /* 链表元素最大值 */

struct node {
    int data;
    struct node* next;
};
typedef struct node Node,*List;

List init_list(void);   /* 初始化随机链表 */
List merge(List,List);  /* 归并非递增链表 */
List create_asc(void);  /* 建立非递减链表 */
void deleven(List);     /* 删除偶数元素结点 */
void insert(List);      /* 插入结点 */
void reverse(List);     /* 链表就地逆置 */
void traverse(List);    /* 链表遍历 */
void destroy(List);     /* 销毁链表 */

int main()
{
    srand(time(NULL));  /* 初始化随即种子 */
    Node* l1 = init_list();
    printf( "随机链表l1:\n" );
    traverse(l1);
    printf( "l1逆置后为:\n" );
    reverse(l1);
    traverse(l1);
    printf( "删除l1所有偶数元素结点:\n" );
    delete(l1);
    traverse(l1);
    printf( "创建非递减有序链表l2:\n" );
    Node* l2 = create_asc();
    traverse(l2);
    printf( "随机插入结点到链表l2:\n" );
    insert(l2);
    traverse(l2);
    printf( "创建非递减有序链表l3:\n" );
    Node* l3 = create_asc();
    traverse(l3);
    printf( "l2,l3归并为非递增链表l4:\n" );
    Node* l4 = merge(l2,l3);
    traverse(l4);

    destroy(l1);
    destroy(l4);
    return 0;
}

List merge_list(Node* first, Node* second)
{
    Node* head;
    if (!first) return second;
    if (!second) return first;
    if (first->data < second->data){
        head = first;
        first = first->next;
    }else{
        head = second;
        second = second->next;
    }
    head->next = merge_list(first, second);
    return head;
}

List merge_sort(Node* head)
{
    if (head==NULL||head->next==NULL) return head;
    Node *p=head, *q=head;
    while (q->next && q->next->next){
        p = p->next;
        q = q->next->next;
    }
    q = p->next;
    p->next = NULL;
    return merge_list(merge_sort(head),merge_sort(q));
}

List init_list(void)
{
    Node* head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    int i;
    for (i=0; i<LEN; i++){
        Node* p = (Node*)malloc(sizeof(Node));
        p->data = rand()%MAX+1;
        p->next = head->next;
        head->next = p;
    }
    return head;
}

List merge(List l1, List l2)
{
    reverse(l1);
    reverse(l2);
    Node* p = l1->next;
    Node* q = l2->next;
    Node* cur = l1;
    while (p && q){
        if (p->data >= q->data){
            cur->next = p;
            cur = p;
            p = p->next;
        } else {
            cur->next = q;
            cur = q;
            q = q->next;
        }
    }
    cur->next = p?p:q;
    free(l2);
    return l1;
}

List create_asc(void)
{
    int i;
    int len = LEN+rand()%10;
    Node* head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    for (i=0; i<len; i++)
        insert(head);
    return head;
}

void insert(List l)
{
    int n = rand()%MAX+1;
    Node* p = l;
    while (p->next && n > p->next->data )
        p = p->next;
    Node* q = (Node*)malloc(sizeof(Node));
    q->data = n;
    q->next = p->next;
    p->next = q;
}

void deleven(List l)
{
    Node* p = l;
    Node* q = l->next;
    while (1){
        while (q){
            if (q->data%2==0) break;
            p = p->next;
            q = q->next;
        }
        if (!q) break;
        printf( "%2d was deleted.\n",q->data );
        p->next = q->next;
        free(q); q = p->next;
    }
}

void reverse(List l)
{
    Node* p = l->next;
    Node* q = l->next;
    l->next = NULL;
    while (p){
        q = q->next;
        p->next = l->next;
        l->next = p;
        p = q;
    }
}

void traverse(List l)
{
    Node* p = l->next;
    while (p){
        printf( "%2d ",p->data );
        p = p->next;
    }
    printf( "\n" );
}

void destroy(List l)
{
    Node* p = l;
    while (p){
        p = p->next;
        free(l);
        l = p;
    }
}