单链表基础练习

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR -1
typedef struct LNode {
    int data;
    struct LNode *next;
}LNode, *LinkList;
LinkList createlist(LinkList L, int n);             //采用尾插法创建链表
LinkList createlist_tail(LinkList L, int n);        //采用头插法创建链表
LinkList bing(LinkList La, LinkList Lb);            //合并两个链表
void showList(LinkList L);                          //打印链表
void selectsort_low(LinkList L);                    //直接选择排序-降序排序
void selectsort_high(LinkList L);                   //直接选择排序-升序排序
void Insertsort_high(LinkList L);                   //直接插入排序-升序排序   
void Insertsort_low(LinkList L);                    //直接插入排序-降序排序
void freeList(LinkList L);                          //释放链表  
int  ListDelete_L(LinkList L, int i, int *e);       //删除第i个元素，并由e返回其值
int  ListInsert_L(LinkList L, int i, int e);        //在第i个位置前插入元素e
int  GetElem_L(LinkList L, int i, int *e);          //查找第i个元素，存在则返回OK，否则ERROR

LinkList createlist(LinkList L, int n)              //采用尾插法创建链表
{
    int i;
    LinkList p, r;
    L = (LinkList)malloc(sizeof(LNode));
    if (L == NULL)
        exit(1);
    r = L;  //r是尾指针
    for (i = 1; i <= n; i++)
    {
        p = (LinkList)malloc(sizeof(LNode));
        if (!p)
        {
            printf(" Not enough heap ");
            exit(1);
        }
        scanf("%d", &p->data);
        r->next = p; //将新结点p连入r的后边
        r = p;
    }
    r->next = NULL;
    return L;
}

LinkList createlist_tail(LinkList L, int n)         //采用头插法创建链表
{
    int i;
    LinkList p;
    L = (LinkList)malloc(sizeof(LNode));
    if (L == NULL)
        exit(1);
    for (i = 1; i <= n; i++)
    {
        p = (LinkList)malloc(sizeof(LNode));
        if (!p)
        {
            printf(" Not enough heap ");
            exit(1);
        }
        scanf("%d", &p->data);
        p->next = L->next;   //把新建立的结点插入到上一个结点的前面,表头L-->|2|-->|1|-->NULL 
        L->next = p;
    }
    return L;
}

LinkList bing(LinkList La, LinkList Lb)
{  //La和Lb是非递减的，求La和Lb的并集
    LinkList pa, pb, pc, t;
    pa = La->next;
    pc = La;
    pb = Lb->next;
    while (pa&&pb)
    {
        if (pa->data<pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else if (pa->data>pb->data)
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        else
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
            t = pb;
            pb = pb->next;
            free(t);
        }
    }
    pc->next = pa ? pa : pb;
    free(Lb);
    return La;
}

void showList(LinkList L)
{
    LinkList p;
    p = L->next;
    printf("The La is:");
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void selectsort_low(LinkList L) //降序排序
{
    int temp;
    LinkList p, q, m;
    if (!L->next || !L->next->next)
        return;
    p = L->next;  //p指向第一个结点
    while (p->next)
    {
        m = p;      //m指向当前最大结点
        q = p->next;
        while (q)
        {
            if (q->data > m->data)
                m = q;
            q = q->next;
        }
        if (p != m)
        {       //将两个结点的数据域交换
            temp = m->data;
            m->data = p->data;
            p->data = temp;
        }
        p = p->next;
    } //while(q->next)
}

void selectsort_high(LinkList L)   //升序排序
{
    int temp;
    LinkList p, q, m;
    if (!L->next || !L->next->next)
        return;
    p = L->next;  //p指向第一个结点
    while (p->next)
    {
        m = p;      //m指向当前最小结点
        q = p->next;
        while (q)
        {
            if (q->data < m->data)
                m = q;
            q = q->next;
        }
        if (p != m)
        {       //将两个结点的数据域交换
            temp = m->data;
            m->data = p->data;
            p->data = temp;
        }
        p = p->next;
    } //while(q->next)
}  //selectsort

void Insertsort_high(LinkList L) {
    /*
    p 指针指向下一个需要插入到链表的结点
    q指针是找到已生成链表的部分中P应该插入的位置
    r指针指向q的前驱指针，如果找到位置时记录插入位置前一个位置以辅助插入
    整个的循环是P取完所有结点之后结束的（即所有的结点都已按顺序插入了）
    比较p->data与q->data的值用来找到插入位置的
    */
    int count = 0;
    LinkList p, q, r, u;
    p = L->next; L->next = NULL;  //置空表，然后将原链表结点逐个插入到有序表中
    while (p != NULL) {          //当链表尚未到尾，p为当前指针
        r = L; q = L->next;
        while (q != NULL&&q->data <= p->data) {  //查p结点在链表中的插入位置，这时q是当前指针
            r = q; q = q->next;
        }
        count++;
        u = p->next; 
        p->next = r->next; 
        r->next = p; 
        p = u; //将P结点链入链表中，r是q的前驱，u是下一个待插入结点的指针
        printf("\n第%d趟后为:", count);
        showList(L);
    }
}

void Insertsort_low(LinkList L)
{
    int count = 0;
    LinkList p, q, r, u;
    p = L->next; L->next = NULL;  //置空表，然后将原链表结点逐个插入到有序表中
    while (p != NULL) {          //当链表尚未到尾，p为当前指针
        r = L; q = L->next;
        while (q != NULL&&q->data > p->data) {  //查p结点在链表中的插入位置，这时q是当前指针
            r = q; q = q->next;
        }
        count++;
        u = p->next;
        p->next = r->next;
        r->next = p;
        p = u; //将P结点链入链表中，r是q的前驱结点，u是下一个待插入结点的指针
        printf("\n第%d趟后为:", count);
        showList(L);
    }
}

void freeList(LinkList L)
{
    LinkList p = L;  //释放链表
    if (!L) return;
    do {
        L = L->next;        //释放之前先保存下个节点的地址
        free(p);        //通过p释放当前节点
        p = L;          //更新p
    } while (p != NULL);
}

int  ListInsert_L(LinkList L, int i, int e)
{
    LinkList p, s;
    int j = 0;
    p = L;
    while (p&&j < i - 1)
    {
        p = p->next;
        ++j;  //寻找第i个结点
    }
    if (!p || j > i - 1)   //i小于1或者大于表长+1
        return ERROR;
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

int  ListDelete_L(LinkList L, int i, int *e)
{
    LinkList p, q;
    int j = 0;
    p = L;
    while (p->next && j < i - 1) {  //寻找第i个结点，并令p指向其前驱
        p = p->next;
        ++j;
    }
    if (!(p->next) || j > i - 1)    //删除位置不合理
        return ERROR;
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return OK;
}

int  GetElem_L(LinkList L, int i, int *e)
{
    // L为带头结点单链表的头指针
    //当第i个元素存在时，其值赋值给e并返回OK，否则返回ERROR
    LinkList p;
    int j = 1;  //j为计数器
    p = L->next;
    while (p && j < i) {  //直到p为空或者找到第i个元素
        p = p->next;
        ++j;
    }
    if (!p || j > i)
        return ERROR;
    *e = p->data;
    return OK;
}

int main(void)
{
    LinkList La = NULL, Lb = NULL;
    int n = 6;
    int e;
    printf("Input %d numbers for La:\n", n);
    La = createlist(La, n);
    showList(La);
    selectsort_high(La);     //直接选择排序-升序排序
    printf("直接选择排序-升序:");
    showList(La);
    selectsort_low(La);      //直接选择排序-降序排序
    printf("直接选择排序-降序:");
    showList(La);
    Insertsort_high(La);     //直接插入排序-升序排序
    printf("\n最后直接插入排序-升序:");
    showList(La);
    Insertsort_low(La);      //直接插入排序-降序排序
    printf("\n最后直接插入排序-降序:");
    showList(La);
    printf("\n在第2个元素前面插入元素6:");
    ListInsert_L(La, 2, 6);
    showList(La);
    GetElem_L(La, 2, &e);
    printf("\n第%d个元素是%d\n",2,e);
    printf("\n删除第4个元素");
    ListDelete_L(La, 4, &e);
    printf(",删除的元素为%d\n",e);
    showList(La);
    printf("\nInput %d numbers for Lb:\n", n);
    Lb = createlist(Lb, n);
    printf("\nThe Lb is:");
    showList(Lb);
    La = bing(La, Lb);
    printf("\nLa 和 Lb 合并之后:");
    showList(La);
    freeList(La);  //释放
}