链表的创建，倒置，查询，插入操作

ゝ一世哀愁。 2022-05-27 06:19 153阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
        int data;
        struct node *next;
    }linknode,*linkp;
    
    int CreateList(linkp H); //创建链表,并返回链表中数值个数
    void InversionList(linkp H); //将已经创建并赋值的链表进行倒置
    linkp GetList(linkp H,int i);//按照序号进行查找(链表头结点序号为0)
    linkp LocateList(linkp H,int data); //按照数值进行查找,结果返回查到的输入数值在链表中的序号
    void InsertList(linkp H, int num, int i); //将数值num插入首节点为H的链表的第i位置（链表头结点序号为0）
    
    
    int main()
    {
        linkp findpNo,findpNum,r,H;
        int i = 0;   
        int no = 0; //输入的待查询的序号
        int findno = 0;//输入的待查询的数值
        int count = 0;//链表中包含数值个数
        int insertnum = 0;//向链表中插入的数值
        int insertno = 0;//将需要插入的数值插到链表的序号
        H = (linkp)malloc(sizeof(linknode));
        H->next = NULL;
        count =CreateList(H); //创建链表并赋值
        if(count==0)
        {   
            printf("该链表只有头结点，不包含任何数据！\n");
            return -1; 
        }   
        r = H;
        printf("\n#####步骤1：链表倒置前序列值#####\n");
        while(r->next)
        {   
            r = r->next;
            printf("链表第%d个数字是%d\n", ++i, r->data);
        }   
        
        printf("\n#####步骤2：链表倒置后序列值#####\n");
        InversionList(H); //将链表进行倒置
        r = H;
        i = 0;
        while(r->next)
        {   
            r = r->next;
            printf("链表第%d个数字是%d\n", ++i, r->data);
        }
    
        printf("\n#####步骤3：通过序号查找链表的数值#####\n");
        /**按照序号查找链表的某个节点**/
        while(1)
        {
            printf("请输入需要查找的序号(链表头结点序号为0,输入-1不再查询)：");
            scanf("%d", &no);
            if(no==-1)
                break;
            if(no>count)
            {
                printf("序号范围[0~%d],请重新输入序号!\n", count);
                continue;
            }
            findpNo = GetList(H, no);
            if(findpNo==H)
            {
                printf("链表头结点无数值！\n");
                continue;
            }
            printf("链表序号[%d]所对应数值是:[%d]\n", no, findpNo->data);
    
        }
    
        /**通过数值查找链表的某个节点**/
        printf("\n#####步骤4：通过数值查找其在链表的位置#####\n");
        while(1)
        {
            printf("请输入需要查找的数值(链表头结点序号为0,输入-1不再查询)：");
            scanf("%d", &findno);
            if(findno==-1)
                break;
            findpNum = LocateList(H,findno);
            if(findpNum == NULL)
            {
                printf("输入的数值不在所查链表中!\n");
            }
            else
            {
                r = H;
                i = 0;
                while(r->next)
                {
                    i++;
                    r = r->next;
                    if(r==findpNum)
                    {
                        printf("链表中数值[%d]所对应序号是[%d]\n", findno, i);
                        break;
                    }
                }
    
            }
    
        }
    
        /**向列表中插入数据，并打印插入数据后的链表数据序列**/
    
        printf("\n#####步骤5：通过输入的数值和序号将数值插入到链表的指定位置#####\n");
        while(1)
        {
            printf("请输入向链表中插入的数值以及序号(usage:insertnum inserno;注:两者同为-1,则停止插入数据):");
            scanf("%d,%d", &insertnum,&insertno);
            if(insertnum==-1 && insertno==-1)
                break;
            if(insertno>count)
            {
                printf("插入范围是1~%d,请重新输入!\n", count);
                continue;
            }
    
    
            InsertList(H, insertnum, insertno);
            count++;
            r = H;
            i = 0;
            while(r->next)
            {
                r = r->next;
                printf("链表第%d个数字是%d\n", ++i, r->data);
            }
    
        }
        return 0;
    }
    
    int CreateList(linkp H)
    {
        linkp r,p;
        int num = -1;
        int count = 0;
        r = H;
    
        while( 1 )
        {
            printf("请输入存入链表中的数字\n");
            scanf("%d", &num);
            if ( -1 == num )
            {
                break;
            }
            count++;
            linkp p = (linkp)malloc(sizeof(linknode));
            p->data = num;
            p->next = NULL;
            r->next = p;
            r = p;
        }
        return count;
    }
    
    void InversionList(linkp H)
    {
        linkp p,q;
        p = H->next; //p指向头结点下一个节点
        H->next = NULL; //将头结点与其下一个节点断开连接，此时p节点成为链表的第一个节点
        while(p)
        {
            q = p; //保存链表余下节点的头一个节点
            p = p->next; //将p节点向后移
            q->next = H->next; //将链表余下节点的第一个节点插入到原链表头结点与其指向节点(NULL)中间
            H->next = q;//将H指向将要插入的节点
    
        }
    
    }
    
    linkp GetList(linkp H,int i)
    {
        int j = 0;
        linkp r;
        r = H;
        if(i<0) //判断序号是否合法
        {
            printf("输入序号有误！");
            return NULL;
        }
        else if(i==0)
            return H;
        else
        {
            while(r->next)
            {
                j++;
                r=r->next;
                if(j==i)
                {
                    return r;
                }
            }
        }
    }
    
    linkp LocateList(linkp H, int num)
    {
        linkp r;
        int i = 0;
        r = H;
        while(r->next)
        {
            i++;
            r = r->next;
            if(r->data==num)
                return r;
        }
        return NULL;
    
    }
    
    
    void InsertList(linkp H, int num, int i)
    {
        linkp p,new;
        new = (linkp)malloc(sizeof(linknode));
        new->data = num;
        p = GetList(H,i-1);
        new->next = p->next;
        p->next = new;
    }