C语言 算法与数据结构 单链表 基本操作及实验案例

实验要求：

实现单链表的如下操作：
1.初始化、2.判空、3.清空、4.计数(长度)、5.按位置查找、6.按值查找、7.插入、8.删除、9.创建(头插法)、10.创建(尾插法)、11.逆置、12.显示等。
13.（10%）实现在有序的单链表插入元素，仍保持其有序性
14.（10%）实现有序链表A，B的合并，1)仍保持其有序性 15.2）改为逆序

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<Windows.h>
#include<time.h>
typedef int elemtype;
typedef struct node //节点结构体
{
    elemtype data;
    struct node * next;
} LinkList;

//功能选择菜单
int meau();
//初始化链表H,给头指针H赋值，创建空链表
LinkList * DefaultList();
//判空，判断链表H是否为空
int IsEmpty(LinkList * H);
//清空，清空链表H
void DelList(LinkList * H);
//计数(长度)，计算H的长度并返回
int LenLIist(LinkList *H);
//按位置查找，在H中的查找第space并返回地址指针，过大返回尾指针，过小返回头指针
LinkList * SearchSpace(LinkList *H,int space);
//按值查找，在H中的第space位置查找num
LinkList * SearchNum(LinkList *H,int num,int * space);
//插入，在H中的第space位置插入num
LinkList * InsertList(LinkList *H,int space,int num);
//删除H中的第space个元素
int DelElemt(LinkList *H,int space);
//创建(头插法)，直到输入-999完成创建
void HeadInsert(LinkList *H);
//创建(尾插法)，直到输入-999完成创建
void ButtonInsert(LinkList *H);
//逆置H
LinkList * ExchangeList(LinkList *H);
//显示H
void DisplayList(LinkList *H);
//实现在有序的单链表H插入元素num，仍保持其有序性
void InsertRuleList(LinkList *H,int num);
//有序链表H，K的合并，1)仍保持其有序性,合并到H中并返回H
LinkList * ContactList(LinkList *H,LinkList *K);
//有序链表H，K的合并，1)仍保持其有序性逆置,合并到H中并返回H
LinkList * ContactListExchange(LinkList *H,LinkList *K);

int main()
{
    system("color f0");
    system("title 链表操作主界面 dev: Ice2Faith");
    system("mode con cols=80 lines=35");
    LinkList * H=NULL;
    int sel;
    do
    {
        sel=meau();
        switch(sel)
        {
        case 1://1.初始化
        {
            H=DefaultList();
            printf("初始化完毕\n");
            system("pause");
            break;
        }
        case 2://2.判空
        {
            printf("%s",IsEmpty(H)==1?">/ 链表为空\n":">/ 链表不为空\n");
            system("pause");
            break;
        }
        case 3://3.清空
        {
            DelList(H);
            system("pause");
            break;
        }
        case 4:////4.计数(长度)
        {
            printf(">/ 链表长度为： %d\n",LenLIist(H));
            system("pause");
            break;
        }
        case 5:////5.按位置查找
        {
            int space;
            printf(">/ 请输入您要查找的位置：\n>/ ");
            scanf("%d",&space);
            LinkList * num=SearchSpace(H,++space);
            if(num==NULL)
                printf(">/ 输入位置不合法\n");
            else
                printf(">/ 您查找的第 %d 个元素是：%d\n",--space,num->data);
            system("pause");
            break;
        }
        case 6:////6.按值查找
        {
            int num,space;
            printf(">/ 请输入您要查找的元素：\n>/ ");
            scanf("%d",&num);
            SearchNum(H,num,&space)==NULL?printf(">/ 没有找到该元素\n"):printf(">/ 该元素存在位置-> %d\n",space);
            system("pause");
            break;
        }
        case 7:////7.插入
        {
            int num,space;
            printf(">/ 请输入您要插入的位置：\n>/ ");
            scanf("%d",&space);
            printf(">/ 请输入您要插入的元素：\n>/ ");
            scanf("%d",&num);
            InsertList(H,space,num);
            system("pause");
            break;
        }
        case 8:////8.删除
        {
            int space;
            printf(">/ 请输入您要删除的位置：\n>/ ");
            scanf("%d",&space);
            if(LenLIist(H)<space||space<1)
            {
                printf(">/ 操作失败，输入位置不合法\n");
                system("pause");
                break;
            }
            DelElemt(H,space)==-1?printf(">/ 操作失败，输入位置不合法\n"):printf(">/ 操作成功\n");
            system("pause");
            break;
        }
        case 9:////9.创建(头插法)
        {
            HeadInsert(H);
            system("pause");
            break;
        }
        case 10:////10.创建(尾插法)
        {
            ButtonInsert(H);
            system("pause");
            break;
        }
        case 11:////11.逆置
        {
            ExchangeList(H);
            system("pause");
            break;
        }
        case 12:////12.显示
        {
            DisplayList(H);
            system("pause");
            break;
        }
        case 13:////13.有序的单链表插入元素
        {
            LinkList * M=DefaultList();
            printf(">/ 请输入您的初始化顺序链表：\n>/ ");
            ButtonInsert(M);
            printf(">/ 请输入您要插入的元素：\n>/ ");
            int num;
            scanf("%d",&num);
            InsertRuleList(M,num);
            printf(">/ 这是您插入链表结果：\n>/ \n");
            DisplayList(M);
            system("pause");
            DelList(M);
            free(M);
            break;
        }
        case 14:////14.有序链表A，B的合并顺序
        {
            LinkList * X=DefaultList();
            LinkList * Y=DefaultList();
            printf(">/ 请输入您的初始化顺序链表A：\n>/ ");
            ButtonInsert(X);
            printf(">/ 请输入您的初始化顺序链表B：\n>/ ");
            ButtonInsert(Y);
            printf(">/ 这是您的A，B链表合并的结果：\n>/ \n");
            DisplayList(ContactList(X,Y));
            system("pause");
            DelList(X);
            free(X);
            free(Y);
            break;
        }
        case 15:////15.有序链表A，B的合并逆序
        {
            LinkList * X=DefaultList();
            LinkList * Y=DefaultList();
            printf(">/ 请输入您的初始化顺序链表A：\n>/ ");
            ButtonInsert(X);
            printf(">/ 请输入您的初始化顺序链表B：\n>/ ");
            ButtonInsert(Y);
            printf(">/ 这是您的A，B链表合并的结果：\n>/ \n");
            DisplayList(ContactListExchange(X,Y));
            system("pause");
            DelList(X);
            free(X);
            free(Y);
            break;
        }
        case 0:
        {
            free(H);
        }
        break;
        }
    }
    while(sel);
    return 0;
}

//功能选择菜单
int meau()
{
    system("cls");
    printf("----------------------------------------------------------------\n\n");
    printf("                          链表操作                         \n\n");
    printf("\t请选择：\t\tTips:使用功能2-12前必须初始化\n\n");
    printf("\t1.初始化\t2.判空\t\t3.清空\t4.计数(长度)\n\n");
    printf("\t5.按位置查找\t6.按值查找\t7.插入\t8.删除\n\n");
    printf("\t9.创建(头插法)\t10.创建(尾插法)\t11.逆置\t12.显示\t\n\n");
    printf("\t13.有序的单链表插入元素\n\n");
    printf("\t14.有序链表A，B的合并顺序\n\n");
    printf("\t15.有序链表A，B的合并逆序\n\n");
    printf("\t0.退出程序\n\n");
    printf("----------------------------------------------------------------\n\n>/ ");

    int sel;
    scanf("%d",&sel);
    while(sel<0||sel>15)
        scanf("%d",&sel);
    return sel;
}
//初始化链表
LinkList * DefaultList()
{
    LinkList * H;
    H=(LinkList *)malloc(sizeof(LinkList));
    H->next=NULL;
    return H;
}
//判空
int IsEmpty(LinkList * H)
{
    return H->next==NULL?1:-1;
}
//清空
void DelList(LinkList * H)
{
    LinkList * P,* B;
    P=H->next;
    H->next=NULL;
    while(P)           //释放空间并清空链表
    {
        B=P->next;
        free(P);
        P=B;
    }

}
//计数(长度)
int LenLIist(LinkList *H)
{
    int i=0;
    LinkList * P;
    P=H->next;
    while(P)           //遍历加点返回长度
    {
        i++;
        P=P->next;
    }
    return i;
}
//按位置查找
LinkList * SearchSpace(LinkList *H,int space)
{
    space--;
    int i=0;
    LinkList * P;       //查找其上一个节点的指针进行返回
    if(space<=0)
        return H;
    P=H;
    while(i!=space&&P->next!=NULL)
    {
        i++;
        P=P->next;
    }
    return P;
}
//按值查找
LinkList * SearchNum(LinkList *H,int num,int * space)
{
    LinkList * P;
    *space=1;
    P=H->next;
    while(P->data!=num)       //查找值并保存是第几个值
    {
        (*space)++;
        P=P->next;
        if(P==NULL)
            break;
    }
    return P;
}
//插入
LinkList * InsertList(LinkList *H,int space,int num)
{
    LinkList * P=SearchSpace(H,space);       //获得插入位置指针
    LinkList * B=P->next;       //记录下一个节点指针
    P->next=DefaultList();       //申请空间进行插入
    P->next->data=num;
    P->next->next=B;
    return P->next;
}
//删除
int DelElemt(LinkList *H,int space)
{
    LinkList * P=SearchSpace(H,space);       //利用方法获得删除位置上一个节点指针
    if(P==NULL)
        return -1;
    LinkList * B=P->next;       //删除节点释放空间
    P->next=B->next;
    free(B);
    return 1;
}
//创建(头插法)
void HeadInsert(LinkList *H)
{
	system("title dev: Ice2Faith");
    printf("请输入数据，以-999结束\n>/ ");
    LinkList * B=H->next;   //记录当前第一个节点的地址
    int num;
    scanf("%d",&num);
    while(num!=-999)       //将节点头插入H链表
    {
        B=H->next;
        H->next=DefaultList();
        H->next->data=num;
        H->next->next=B;
        scanf("%d",&num);

    }
}
//创建(尾插法)
void ButtonInsert(LinkList *H)
{
    int len=LenLIist(H);       //利用方法获得链表长度
    LinkList * P;
    if(len==0)         //判断是否为空链表对尾指针赋值
        P=H;
    else
        P=SearchSpace(H,++len);
    int num;
    printf("请输入数据，以-999结束\n>/ ");
    scanf("%d",&num);
    while(num!=-999)       //尾插进节点
    {
        P->next=DefaultList();
        P->next->data=num;
        P=P->next;

        scanf("%d",&num);
    }
}
//逆置
LinkList * ExchangeList(LinkList *H)
{
    LinkList *p=H->next;    //记录剩余的节点的地址
    LinkList *b=H->next;    //记录当前第一个节点的地址
    H->next=NULL;
    while(p)    //将剩余节点头插入H链表
    {
        b=H->next;
        H->next=p;
        p=p->next;
        H->next->next=b;
    }
    return H;
}
//显示
void DisplayList(LinkList *H)
{
	system("title dev: Ice2Faith");
    LinkList *p=H->next;
    while(p)    //遍历链表输出链表内容
    {
        printf("->%d",p->data);
        p=p->next;
    }
    printf("\n");
}
//实现在有序的单链表插入元素，仍保持其有序性
void InsertRuleList(LinkList *H,int num)
{
    LinkList *p=H->next;
    int space=1;
    while(num>p->data&&p->next!=NULL)   //找到应该插入的位置
    {
        space++;
        p=p->next;
    }
    InsertList(H,space,num);    //利用已有插入方法进行插入
}

//有序链表A，B的合并，1)仍保持其有序性
LinkList *  ContactList(LinkList *H,LinkList *K)
{
    LinkList * RE=H;               //合并的尾
    LinkList * HH=H->next;         //H剩的头
    LinkList * KH=K->next;         //K剩的头
    while(HH&&KH)       //当其中一个不为空时进行粘接
    {
        if(HH->data<KH->data)
        {
            RE->next=HH;
            HH=HH->next;
        }
        else
        {
            RE->next=KH;
            KH=KH->next;
        }
        RE=RE->next;
    }
    if(!HH) //当HH为空时赋值给KH进行剩余链接
    {
        HH=KH;
        while(HH)
        {
            RE->next=HH;
            HH=HH->next;
            RE=RE->next;
        }
    }

    return H;
}

//有序链表A，B的合并，1)仍保持其有序性逆置
LinkList * ContactListExchange(LinkList *H,LinkList *K)
{
    return  ExchangeList(ContactList(H,K)); //直接调用方法先合并再逆置
}