C语言数据结构--链表（2）

╰+攻爆jí腚メ 2024-03-23 12:40 54阅读 0赞

1、**利用链表的几个基础操作算法完成以下功能：**

(1)空链表L定义初始化（利用链表初始化函数）

(2)给链表赋初值：包含5个以上任意整数（利用头插法或尾插法）

(3)打印出链表L（自己设计打印函数）

（打印格式如：12 10 60 30 11 17 80）

(4)打印出链表的长度（利用求长度函数）

(5)打印出链表第3个元素

(6)x置（如在以上示例中，打印出30的位置是4，需要**改写**按值查找函数）

(7)在第4个元素位置前插入元素999

(8)打印出新链表：

（如：12 10 60 999 30 11 17 80）

(9)删除L的第3个元素

(10)打印出新链表L

（如：12 10 999 30 11 17 80）

①单链表的存储结构

typedef struct Node
    {
        int data;
        struct Node * next;
    }Node,*LinkList;

②初始化单链表

void InitList(LinkList *L)
    {
        *L = (LinkList)malloc(sizeof(Node));
        (*L)->next = NULL;
    }

③尾插法创建单链表

//用尾插法创建单链表
    void CreateTail(LinkList L)
    {
        Node *r,*s;                  //定义两个指针变量，r指向链表的尾结点，s指向新创建的结点
        int flag=1;                  //定义一个标志变量，用于控制循环的结束
        int c;                       //定义一个整型变量，用于存储输入的数据
        r=L;                        //让r指向链表的头结点
        while(flag)                 //循环直到flag为0
        {
            scanf("%d",&c);         //从标准输入读取一个整数赋值给c
            if(c!=-99)                     //如果c不等于-99，表示还有数据需要插入链表
            {
                s = (Node*) malloc(sizeof(Node));  //动态分配一个结点的内存空间，并让s指向它
                s->data = c;                            //将c的值赋给s所指结点的数据域
                r->next = s;                             //将s所指结点链接到r所指结点的后面
                r=s;                                     //让r指向s，即更新尾结点的位置
            }
            else                                        //如果c等于-99，表示没有数据需要插入链表
            {
                flag = 0;                              //将flag置为0，结束循环
                r->next = NULL;                        //将尾结点的指针域置为NULL，表示链表结束
            }
        }
    }

④实现链表的查找功能（按值查找 和 按位置查找

按位置查找

Node *Get(LinkList L,int i)
    {
        int j;                                    //定义一个整型变量，用于记录当前遍历到的结点的位置
        Node *p;                                  //定义一个指针变量，用于遍历链表
        p=L;j=0;                                  //让p指向链表的头结点，并将j初始化为0
        if(i<=0) return NULL;                     //如果i小于等于0，表示无效的位置，返回NULL
        while((p->next!=NULL)&&(j<i))             //循环直到p指向NULL或者j等于i
        {
            p = p->next;                            //让p指向下一个结点
            j++;                                    //将j加1，表示移动了一个位置
        }
        if(i==j) return  p;                         //如果i等于j，表示找到了第i个结点，返回p
        else return NULL;                          //否则，表示没有找到第i个结点，返回NULL
    }

按值查找

int Locate(LinkList L,int key)
    {
        int i=0;                               //定义一个整型变量，用于记录当前遍历到的结点的位置
        Node *p;                              //定义一个指针变量，用于遍历链表
        p = L->next;                          //让p指向链表的第一个结点
        while(p!=NULL)                      //循环直到p指向NULL
        {
            if (p->data!=key)                //如果p所指结点的数据域不等于key
            {
                p = p->next;                 //让p指向下一个结点
                i++;                         //将i加1，表示移动了一个位置
            }
            else                            //否则，表示找到了值等于key的结点
                break;                      //跳出循环
        }
        return i;                          //返回i，表示找到的结点的位置，如果没有找到，返回0
    }

⑤求链表的长度

int	ListLength(LinkList L)
    {
        Node *p;             //定义一个指针变量，用于遍历链表
        int j;              //定义一个整型变量，用于记录链表的结点个数
        p=L->next;         //让p指向链表的第一个结点
        j=0;              //将j初始化为0
        while(p!=NULL)    //循环直到p指向NULL
        {
            p=p->next;     //让p指向下一个结点
            j++;          //将j加1，表示增加了一个结点
        }
        return j;     //返回j，表示链表的长度
    }

⑥实现链表的插入功能

int InsList(LinkList L,int i,int e)
    
    {
        Node *pre,*s;              //定义两个指针变量，pre指向插入位置的前一个结点，s指向新创建的结点
        int k;                     //定义一个整型变量，用于记录当前遍历到的结点的位置
        pre=L;                    //让pre指向链表的头结点
        k=0;                      //将k初始化为0
        while(pre!=NULL&&k<i-1)   //循环直到pre指向NULL或者k等于i-1
        {
            pre=pre->next;        //让pre指向下一个结点
            k=k+1;                //将k加1，表示移动了一个位置
        }
        if(!pre)                  //如果pre为空，表示插入位置不合理
        {
            printf("插入位置不合理!");
            return ERROR;
        }
        s=(Node*)malloc(sizeof(Node));        //动态分配一个结点的内存空间，并让s指向它
        s->data=e;                            //将e的值赋给s所指结点的数据域
        s->next=pre->next;                     //将s所指结点链接到pre所指结点的后面
        pre->next=s;                         //将pre所指结点链接到s所指结点的前面
        return OK;
    }

⑦实现链表的删除功能

int DelList(LinkList L,int i)
    {
        Node *pre,*r;              //定义两个指针变量，pre指向删除位置的前一个结点，r指向删除的结点
        int k;                     //定义一个整型变量，用于记录当前遍历到的结点的位置
        pre=L;                    //让pre指向链表的头结点
        k=0;                      //将k初始化为0
        while(pre->next!=NULL && k<i-1)   //循环直到pre的下一个结点为空或者k等于i-1
        {
            pre=pre->next;                //让pre指向下一个结点
            k=k+1;                        //将k加1，表示移动了一个位置
        }
        if(!(pre->next))                 //如果pre的下一个结点为空，表示删除位置不合理
        {
            printf("删除结点的位置i不合理!");
            return ERROR;
        }
        r=pre->next;                      //让r指向pre的下一个结点，即要删除的结点
        pre->next=pre->next->next;        //将pre所指结点链接到r所指结点的后面，即跳过r所指结点
        free(r);                          //释放r所指结点的内存空间
        printf("成功删除结点!");
        return OK;
    }

⑧输出链表

void Display(LinkList L)
    {
        L = L->next;                //让L指向链表的第一个结点
        while(L!=NULL)              //循环直到L指向NULL
        {
            printf("%d ",L->data);            //输出L所指结点的数据域的值
            L = L->next;                           //让L指向下一个结点
        }
    }

完整代码和结果：

#include <stdio.h>
    #include <malloc.h>
    #define OK 1
    #define ERROR -1
    
    typedef struct Node
    {
        int data;
        struct Node * next;
    }Node,*LinkList;
    
    //初始化
    void InitList(LinkList *L)
    {
        *L = (LinkList)malloc(sizeof(Node));
        (*L)->next = NULL;
    }
    
    //用尾插法创建单链表
    void CreateTail(LinkList L)
    {
        Node *r,*s;                  //定义两个指针变量，r指向链表的尾结点，s指向新创建的结点
        int flag=1;                  //定义一个标志变量，用于控制循环的结束
        int c;                       //定义一个整型变量，用于存储输入的数据
        r=L;                        //让r指向链表的头结点
        while(flag)                 //循环直到flag为0
        {
            scanf("%d",&c);         //从标准输入读取一个整数赋值给c
            if(c!=-99)                     //如果c不等于-99，表示还有数据需要插入链表
            {
                s = (Node*) malloc(sizeof(Node));  //动态分配一个结点的内存空间，并让s指向它
                s->data = c;                            //将c的值赋给s所指结点的数据域
                r->next = s;                             //将s所指结点链接到r所指结点的后面
                r=s;                                     //让r指向s，即更新尾结点的位置
            }
            else                                        //如果c等于-99，表示没有数据需要插入链表
            {
                flag = 0;                              //将flag置为0，结束循环
                r->next = NULL;                        //将尾结点的指针域置为NULL，表示链表结束
            }
        }
    }
    
    //查找
    //按位置查找
    Node *Get(LinkList L,int i)
    {
        int j;                                    //定义一个整型变量，用于记录当前遍历到的结点的位置
        Node *p;                                  //定义一个指针变量，用于遍历链表
        p=L;j=0;                                  //让p指向链表的头结点，并将j初始化为0
        if(i<=0) return NULL;                     //如果i小于等于0，表示无效的位置，返回NULL
        while((p->next!=NULL)&&(j<i))             //循环直到p指向NULL或者j等于i
        {
            p = p->next;                            //让p指向下一个结点
            j++;                                    //将j加1，表示移动了一个位置
        }
        if(i==j) return  p;                         //如果i等于j，表示找到了第i个结点，返回p
        else return NULL;                          //否则，表示没有找到第i个结点，返回NULL
    }
    
    //按值查找
    int Locate(LinkList L,int key)
    {
        int i=0;                               //定义一个整型变量，用于记录当前遍历到的结点的位置
        Node *p;                              //定义一个指针变量，用于遍历链表
        p = L->next;                          //让p指向链表的第一个结点
        while(p!=NULL)                      //循环直到p指向NULL
        {
            if (p->data!=key)                //如果p所指结点的数据域不等于key
            {
                p = p->next;                 //让p指向下一个结点
                i++;                         //将i加1，表示移动了一个位置
            }
            else                            //否则，表示找到了值等于key的结点
                break;                      //跳出循环
        }
        return i;                          //返回i，表示找到的结点的位置，如果没有找到，返回0
    }
    
    //求带头结点的单链表L的长度
    int	ListLength(LinkList L)
    {
        Node *p;             //定义一个指针变量，用于遍历链表
        int j;              //定义一个整型变量，用于记录链表的结点个数
        p=L->next;         //让p指向链表的第一个结点
        j=0;              //将j初始化为0
        while(p!=NULL)    //循环直到p指向NULL
        {
            p=p->next;     //让p指向下一个结点
            j++;          //将j加1，表示增加了一个结点
        }
        return j;     //返回j，表示链表的长度
    }
    
    //在带头结点的单链表L中第i个位置插入值为e的新结点s
    int InsList(LinkList L,int i,int e)
    
    {
        Node *pre,*s;              //定义两个指针变量，pre指向插入位置的前一个结点，s指向新创建的结点
        int k;                     //定义一个整型变量，用于记录当前遍历到的结点的位置
        pre=L;                    //让pre指向链表的头结点
        k=0;                      //将k初始化为0
        while(pre!=NULL&&k<i-1)   //循环直到pre指向NULL或者k等于i-1
        {
            pre=pre->next;        //让pre指向下一个结点
            k=k+1;                //将k加1，表示移动了一个位置
        }
        if(!pre)                  //如果pre为空，表示插入位置不合理
        {
            printf("插入位置不合理!");
            return ERROR;
        }
        s=(Node*)malloc(sizeof(Node));     //动态分配一个结点的内存空间，并让s指向它
        s->data=e;                            //将e的值赋给s所指结点的数据域
        s->next=pre->next;                     //将s所指结点链接到pre所指结点的后面
        pre->next=s;                         //将pre所指结点链接到s所指结点的前面
        return OK;
    }
    
    int DelList(LinkList L,int i)
    {
        Node *pre,*r;              //定义两个指针变量，pre指向删除位置的前一个结点，r指向删除的结点
        int k;                     //定义一个整型变量，用于记录当前遍历到的结点的位置
        pre=L;                    //让pre指向链表的头结点
        k=0;                      //将k初始化为0
        while(pre->next!=NULL && k<i-1)   //循环直到pre的下一个结点为空或者k等于i-1
        {
            pre=pre->next;                //让pre指向下一个结点
            k=k+1;                        //将k加1，表示移动了一个位置
        }
        if(!(pre->next))                //如果pre的下一个结点为空，表示删除位置不合理
        {
            printf("删除结点的位置i不合理!");
            return ERROR;
        }
        r=pre->next;                      //让r指向pre的下一个结点，即要删除的结点
        pre->next=pre->next->next;        //将pre所指结点链接到r所指结点的后面，即跳过r所指结点
        free(r);                 //释放r所指结点的内存空间
        printf("成功删除结点!");
        return OK;
    }
    
    void Display(LinkList L)
    {
        L = L->next;               //让L指向链表的第一个结点
        while(L!=NULL)             //循环直到L指向NULL
        {
            printf("%d ",L->data);         //输出L所指结点的数据域的值
            L = L->next;                          //让L指向下一个结点
        }
    }
    
    int main() {
        int len,pos1,pos2;
        int loc1,e;
        int loc2;
        LinkList L;
        Node *p;
        int  p1;
        InitList(&L);
        printf("请输入元素（输入‘-99’时结束）：\n");
        CreateTail(L);
        printf("链表：\n");
        Display(L);
        len = ListLength(L);
        printf("\n链表的长度为：%d",len);
        printf("\n请输入要查找元素的位置：");
        scanf("%d",&pos1);
        p = Get(L,pos1);
        printf("链表位置为%d的元素为：%d",pos1,p->data);
        printf("\n请输入要查找位置的元素：");
        scanf("%d",&pos2);
        p1 = Locate(L,pos2);
        printf("%d在链表的位置为：%d",pos2,p1);
        printf("\n请输入要插入元素的位置和值：");
        scanf("%d %d",&loc1,&e);
        InsList(L,loc1,e);
        printf("插入元素后的链表：");
        Display(L);
        printf("\n请输入要删除元素的位置：");
        scanf("%d",&loc2);
        DelList(L,loc2);
        printf("删除元素后的链表：");
        Display(L);
        return 0;
    }

![de6d7b9fd36d4879939e9ea19d96b466.png][]

[de6d7b9fd36d4879939e9ea19d96b466.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9085e8a602114bd59eeaf76213b11663.png