美文网首页
有头的单链表

有头的单链表

作者: 萌面大叔2 | 来源:发表于2017-02-15 13:08 被阅读0次
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FILENAME "/Users/ccj/Desktop/stu.txt"
typedef struct Student
{
    char name[20];
    int num;

}Student;

typedef struct LINK
{
    Student data;
    struct LINK *next;
}LINK,*pLINK;


typedef enum IsRepeat
{
    YES,
    NO
}IsRepeat;


IsRepeat checkRepeatData(pLINK head,Student stu)
{
    pLINK temp;
    for (temp=head->next; temp!=NULL; temp=temp->next)
    {
        if(temp->data.num==stu.num)
        {
            return YES;
        }
    }
    if(temp==NULL)
    {
        return NO;
    }
    return NO;
}

//创建链表（创建头结点）
pLINK createList(pLINK head)
{
    if(head==NULL)
    {
        head=(pLINK)malloc(sizeof(LINK));
        head->next=NULL;
        
    }
    printf("链表创建成功\n");
    return head;
}


//打印数据
void printData(pLINK head)
{
    if(NULL==head)
    {
        printf("无信息可打印\n");
        return;
    }
    pLINK temp=head->next;
    printf("head-->");
    for(;temp!=NULL;temp=temp->next)
    {
        printf("[%s,%d]--->",temp->data.name,temp->data.num);
    }
    printf("NULL\n");
}

Student getData(pLINK head);

void headInsertData(pLINK head)
{

    pLINK p=(pLINK)malloc(sizeof(LINK));
    p->next=head->next;
    head->next=p;
    p->data=getData(head);
    printf("数据插入成功\n");
}

void myScanf(char *str,int size)
{
    int i=0;
    for (i=0; i<size-1; i++)
    {
        str[i]=getchar();
        if(str[i]=='\n')
        {
            break;
        }
    }
    //说明在中途碰到了\n
    if(str[i]=='\n')
    {
        str[i]='\0';
    }
    else
    {
        str[i]='\0';
        //吸收缓存里面的残留的字符
        while (getchar()!='\n');
    
    }
}
Student getData(pLINK head)
{
    printf("请输入学生信息[姓名 学号]:");
    Student stu;
    myScanf(stu.name, 20);
    scanf("%d",&stu.num);
    getchar();
    int errorCount=0;
    while(checkRepeatData(head, stu)==YES)
    {
        errorCount++;
        if(errorCount==3)
        {
            printf("输入错误次数过多\n");
            exit(0);//结束整个程序(错误码)
        }
        printf("该学号学生已存在\n");
        printf("请重新输入数据[姓名 学号]:");
        myScanf(stu.name, 20);
        scanf("%d",&stu.num);
        getchar();
    }
    return stu;
}

void tailInsertData(pLINK head)
{

    //找尾指针：最后一个节点的地址
    pLINK temp;
    for(temp=head;temp->next!=NULL;temp=temp->next)
    {
    
    }
    //这个循环跳出的条件：temp->next==null;
    pLINK p=(pLINK)malloc(sizeof(LINK));
    p->data=getData(head);
    temp->next=p;
    p->next=NULL;
    printf("尾部数据插入成功\n");
}

void headDeleteData(pLINK head)
{
    if(head==NULL||head->next==NULL)
    {
        printf("无信息可删\n");
        return;
    }
    pLINK p=head->next;
    head->next=p->next;
    free(p);
    p=NULL;
    printf("删除数据成功\n");
}

void tailDeleteData(pLINK head)
{
    if(head==NULL||head->next==NULL)
    {
        printf("无信息可删\n");
        return;
    }
    pLINK temp;
    
    //相当等待状态，等待temp->next->next==NULL;
    for (temp=head; temp->next->next!=NULL; temp=temp->next);
    pLINK p=temp->next;
    temp->next=NULL;
    free(p);
    p=NULL;
    printf("尾删成功\n");
    
}

int getListLength(pLINK head)
{
    if(head->next==NULL)
    {
        return 0;
    }
    int count=0;
    pLINK temp=head->next;
    for(;temp!=NULL;temp=temp->next)
    {
        count++;
    }
    return count;
}



void randomInsertData(pLINK head)
{
    int length=getListLength(head);
//    printf("length=%d\n",length);
    printf("请输入要插入数据的位置:");
    int index;
    scanf("%d",&index);
    getchar();
    if(index<=0||index>length+1)
    {
        printf("位置越界\n");
        return;
    }
    if(index==1)
    {
        headInsertData(head);
    }
    else if(index==length+1)
    {
        tailInsertData(head);
    }
    else
    {
        pLINK temp;
        int i=1;
        for (temp=head->next;i<index-1; temp=temp->next,i++)
        {
            
        }
        pLINK p=(pLINK)malloc(sizeof(LINK));
        p->data=getData(head);
        p->next=temp->next;
        temp->next=p;
        printf("数据插入成功\n");
        
    }
}



void insertData(pLINK head)
{
    if(head==NULL)
    {
        printf("链表没有创建\n");
        return ;
    }
    
    int select;
    while (1)
    {
        printf("========\n");
        printf("1.头插数据\n");
        printf("2.尾插数据\n");
        printf("3.任意位置插入数据\n");
        printf("4.返回上一层\n");
        printf("========\n");
        scanf("%d",&select);
        getchar();
        switch (select)
        {
            case 1:
                headInsertData(head);
                break;
            case 2:
                tailInsertData(head);
                break;
            case 3:
                randomInsertData(head);
                break;
            case 4:
                return;
            default:
                break;
        }
    }
}

void randomDeleteData(pLINK head)
{
    if(head->next==NULL)
    {
        printf("无信息可删\n");
        return;
    }
    int length=getListLength(head);
    printf("请输入要删除数据的位置:");
    int index;
    scanf("%d",&index);
    getchar();
    if(index<=0||index>length)
    {
        printf("位置越界\n");
        return;
    }
    if(index==1)
    {
        headDeleteData(head);
    }
    else if (index==length)
    {
        tailDeleteData(head);
    }
    else
    {
        int i=1;
        pLINK temp;
        for (temp=head->next; i<index-1; temp=temp->next,i++);
        
        pLINK p=temp->next;
        temp->next=p->next;
        free(p);
        p=NULL;
        printf("删除数据成功\n");
    }
}

void deleteData(pLINK head)
{
    if(head==NULL||head->next==NULL)
    {
        printf("没有信息可删\n");
        return ;
    }
    int select;
    while (1)
    {
        printf("========\n");
        printf("1.头删数据\n");
        printf("2.尾删数据\n");
        printf("3.任意位置删除数据\n");
        printf("4.返回上一层\n");
        printf("========\n");
        scanf("%d",&select);
        getchar();
        switch (select)
        {
            case 1:
                headDeleteData(head);
                break;
            case 2:
                tailDeleteData(head);
                break;
            case 3:
                randomDeleteData(head);
                break;
            case 4:
                return;
            default:
                break;
        }
    }
}


void searchData(pLINK head)
{
    if(head==NULL||head->next==NULL)
    {
        printf("无信息可查询\n");
        return ;
    }
    int num;
    printf("请输入要查询的学号:");
    scanf("%d",&num);
    pLINK temp;
    for(temp=head->next;temp!=NULL;temp=temp->next)
    {
        if(temp->data.num==num)
        {
            printf("[%s,%d]\n",temp->data.name,num);
            return;
        }
    }
    if(NULL==temp)
    {
        printf("查无此人\n");
    }
}

void changeData(pLINK head)
{
    if(head==NULL||head->next==NULL)
    {
        printf("无信息可修改\n");
        return ;
    }
    char name[20];
    printf("请输入姓名:");
    myScanf(name, 20);
    pLINK temp;
    for(temp=head->next;temp!=NULL;temp=temp->next)
    {
        if(strcmp(temp->data.name, name)==0)
        {
            printf("该学生原来信息[%s,%d]\n",temp->data.name,temp->data.num);
            printf("请输入要修改的信息[姓名 学号]:");
            Student stu;
            myScanf(stu.name, 20);
            scanf("%d",&stu.num);
            temp->data=stu;
            printf("修改成功\n");
            return;
        }
    }
    if(temp==NULL)
    {
        printf("查无此人\n");
    }
}

void saveData(pLINK head)
{
    if(head==NULL||head->next==NULL)
    {
        printf("无信息可保存\n");
        return;
    }
    //1.
    FILE *fp=fopen(FILENAME, "w");
    if(fp==NULL)
    {
        perror("fopen failed");
        return;
    }
    //2.
    pLINK temp;
    for (temp=head->next; temp!=NULL; temp=temp->next)
    {
        fwrite(&temp->data, sizeof(Student), 1, fp);
    }
    //3.
    fclose(fp);
    printf("保存成功\n");

}


pLINK readDataFromFile()
{
    pLINK head=(pLINK)malloc(sizeof(LINK));
    head->next=NULL;
    
    FILE *fp=fopen(FILENAME, "r");
    if(fp==NULL)
    {
        perror("fopen failed:");
        return head;
    }
    Student stu;
    while (fread(&stu, sizeof(stu), 1, fp)==1)
    {
        pLINK p=(pLINK)malloc(sizeof(LINK));
        p->data=stu;
        //先找最后一个节点的位置
        pLINK temp;
        for(temp=head;temp->next!=NULL;temp=temp->next);
        temp->next=p;
        p->next=NULL;
        
    }
    
    fclose(fp);
    printf("读取数据成功\n");
    return head;
}

pLINK offList(pLINK head)
{
    pLINK first=(pLINK)malloc(sizeof(LINK));
    first->next=NULL;
    pLINK tail=first;
    while (head->next!=NULL)
    {
        pLINK min=head->next;
        pLINK minf=head;
        pLINK temp;
        for (temp=head->next; temp->next!=NULL; temp=temp->next)
        {
            if(min->data.num>temp->next->data.num)
            {
                min=temp->next;
                minf=temp;
            }
        }
        //脱链
        minf->next=min->next;
        
        //穿链
        tail->next=min;
        min->next=NULL;
        tail=tail->next;
        
    }
    free(head);
    head=NULL;
    return first;
}



void selectSort(pLINK head)
{
    pLINK i;
    for (i=head->next; i->next!=NULL; i=i->next)
    {
        pLINK j;
        pLINK min=i;
        for (j=i->next; j!=NULL; j=j->next)
        {
            if(min->data.num>j->data.num)
            {
                min=j;
            }
        }
        if(min!=i)
        {
            Student temp=min->data;
            min->data=i->data;
            i->data=temp;
        }
        
    }
    printf("排序成功\n");
    
}

void blueSort2(pLINK head)
{
    pLINK i;
    for (i=head->next; i->next!=NULL; i=i->next)
    {
        pLINK j;
        for(j=i->next;j!=NULL;j=j->next)
        {
            if(i->data.num>j->data.num)
            {
                Student temp=i->data;
                i->data=j->data;
                j->data=temp;
            }
        }
    }
    printf("排序成功\n");
}


void blueSort1(pLINK head)
{
    int i=0;
    int length=getListLength(head);
    for (i=0; i<length-1; i++)
    {
        pLINK j;
        for (j=head->next; j->next!=NULL; j=j->next)
        {
            if(j->data.num>j->next->data.num)
            {
                Student temp=j->data;
                j->data=j->next->data;
                j->next->data=temp;
            
            }
        }
    }
    printf("排序成功\n");
}

pLINK sort(pLINK head)
{
    if(head==NULL||head->next==NULL)
    {
        printf("无数据可排\n");
        return head;
    }
    int select;
    while(1)
    {
        printf("=====\n");
        printf("1.冒泡1\n");
        printf("2.冒泡2\n");
        printf("3.选择\n");
        printf("4.脱链\n");
        printf("5.返回上一层\n");
        printf("======\n");
        scanf("%d",&select);
        switch (select)
        {
            case 1:
                blueSort1(head);
                break;
            case 2:
                blueSort2(head);
                break;
            case 3:
                selectSort(head);
                break;
            case 4:
                head=offList(head);
                break;
            case 5:
                return head;
            default:
                break;
        }
    }
}

int main()
{
    pLINK head=NULL;
    int select;
    while (1)
    {
        printf("=========\n");
        printf("1.创建链表\n");
        printf("2.插入数据\n");
        printf("3.删除数据\n");
        printf("4.打印数据\n");
        printf("5.查找数据\n");
        printf("6.修改数据\n");
        printf("7.保存数据\n");
        printf("8.从文件读取数据\n");
        printf("9.排序(小-->大)\n");
        printf("10.退出\n");
        printf("=========\n");
        scanf("%d",&select);
        getchar();//吸收\n残留
        switch (select)
        {
            case 1:
                head=createList(head);
                break;
            case 2:
                insertData(head);
                break;
            case 3:
                deleteData(head);
                break;
            case 4:
                printData(head);
                break;
            case 5:
                searchData(head);
                break;
            case 6:
                changeData(head);
                break;
            case 7:
                saveData(head);
                break;
            case 8:
                head=readDataFromFile();
                break;
            case 9:
                head=sort(head);
                break;
            case 10:
                return 0;
            default:
                break;
        }
    }
    return 0;
}

相关文章

  • 数据结构——链表

    本文所讲的链表是单链表，链表采用无头链表 科普下：一般链表可以分为有头节点的链表与无头节点的链表 有头节点的链表：...

  • 线性表元素插入和删除

    单链表（链式存储结构）插入 单链表（链式存储结构）删除 有头结点的单链表在开始结点前插入元素等同在头结点后插入元素...

  • 有头的单链表

  • [数据结构]第二章线性表(3)——单链表

    单链表 什么是单链表？ 单链表的定义 别名 注释：或者可以理解为指向头节点的指针既可以表示整个单链表也可以表示头节...

  • 线性表的链式存储-单链表

    单链表操作 [x] 单链表的创建（尾插法、头插法） [x] 单链表的查找操作 [x] 单链表的删除操作 [x] 单...

  • 数据结构与算法-单链表的整表创建,删除,插入

    1.单链表的创建 2.单链表的插入 虽然上面我们有头插法,但是我们还是需要尾插法 单链表的删除

  • 线性表：顺序表和链表

    顺序表（数组）优缺点 链表优点 单链表使用 单链表结构 单链表初始化 单链表初始化 单链表建立: 头插法 尾插法 ...

  • JavaScript数据结构2——单链表

    以下的代码包括了以下几部分 单链表初始化 单链表的插入 单链表的删除 单链表的创建（头插法） 单链表的创建（尾插法...

  • 单链表 常用操作（golang）

    （单链表备忘记录）知识点： 单链表结构 创建链表方法头插法创建尾插法创建 遍历链表 逆序反转链表迭代递归头插法就地...

  • 数据结构_知识点_单链表

    1. 单链表定义 头指针：头指针是指向单链表第一个结点的指针，是链表必须有的。头结点：头结点可有可无，若有，则头指...

网友评论

      本文标题：有头的单链表

      本文链接：https://www.haomeiwen.com/subject/wwgluttx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|有头的单链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！