线性链表和顺序表的基本操作

小鱼儿 2022-11-26 06:55 344阅读 0赞

## 线性链表和顺序表的基本操作 ##

**一、实验目的：**

线掌握线性表的逻辑特性以及在计算机内的两种存储结构，线性链表和顺序表存储结构下基本操作的实现，会灵活应用线性表结构解决某些实际问题。

**二、实验内容：**

1，线性表顺序存储结下的基本操作的实现（初始化，赋值、取值、插入、删除归并等）。  
2，线性表链式存储结下的基本操作的实现（初始化，赋值、取值、插入、删除归并等）。

**三、实验要求：**

在本题下面提交源程序和实验运行结果截图。
    上交纸质版实验报告和电子版实验报告。

**四、源程序及注释**

1，线性表顺序存储结下的基本操作的实现（初始化，赋值、取值、插入、删除归并等）。

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #define len sizeof(struct list)
    struct list
    {
        
    int data;
    struct list *next;
    };struct list *la,*lb;
    struct list * InitList()
    {
        
    struct list *head;
    head=(struct list *)malloc(len);
    return head;
    }
    struct list * ListInsert(struct list* &la)
    {
        
    struct list *p1,*head;
    int n;
    head=la;
    printf("请输入数据的个数\n");
    scanf("%d",&n);
    printf("请输入数据,用空格分开\n");
    while(n--)
    {
        
    p1=(struct list*)malloc(len);
    scanf("%d",&p1->data);
    p1->next=NULL;
    la->next=p1;
    la=p1;
    }
    return head;
    }
    void GetElem(struct list * la)
    {
        
    printf("请输入你要取得值的位置\n");
    int n;
    scanf("%d",&n);
    while(la->next&&n)
    {
        
    n--;
    la=la->next;
    }
    if(n)
    printf("输入的位置超出链表范围\n");
    else
    printf("所处位置的元素为%d\n",la->data);
    }
    void InsertElem(struct list * la)
    {
        
    struct list* pos;
    printf("请输入你要插入的位置和元素\n");
    int n,x;
    scanf("%d %d",&n,&x);
    while(la->next&&n)
    {
        
    n--;
    pos=la;
    la=la->next;
    }
    if(n)
    printf("输入的位置超出链表范围\n");
    else
    {
        
    struct list * p1;
    p1=(struct list*)malloc(len);
    p1->data=x;
    p1->next=pos->next;
    pos->next=p1; 
    printf("插入成功\n");
    } 
    }
    bool UnionList(struct list *pa,struct list *pb)
    {
        
    struct list *head;
    head=pa;
    while(pa->next){
        
    pa=pa->next;
    }
    pa->next=pb->next;
    printf("合并后的链表为:\n"); 
    while(head->next)
    {
        
    printf("%d ",head->next->data);
    head=head->next;
    }
    
    printf("\n");
    }
    int main()
    {
        
        printf("1,初始化链表\n");
    printf("2,对链表进行赋值\n");
    printf("3,向链表中取值\n");
    printf("4,向链表中插入元素\n");
    printf("5,归并链表\n"); 
    printf("6,退出程序\n");
    while(1)
    {
        
    
    int x;
    scanf("%d",&x);
    if(x==1)
    {
        
    printf("请输入你要初始化的链表a,b\n\n");
    getchar();
    char ch;
    ch=getchar();
    if(ch=='a')
    {
        
    la=InitList();
    if(!la)
    printf("初始化失败\n\n"); 
    else
    {
        
    la->next=NULL;
    printf("初始化成功\n\n"); 
    }
    }
    else if(ch=='b')
    {
        
    lb=InitList();
    if(!lb)
    printf("初始化失败\n\n"); 
    else
    {
        
    lb->next=NULL;
    printf("初始化成功\n\n"); 
    }
    }
    else
    printf("输入错误\n\n");
    }
    else if(x==2)
    {
        
    printf("请输入你要进行赋值的链表a或者b\n\n");
    getchar();
    char ch=getchar();
    if(ch=='a') 
    {
        
    if(!la)
    printf("请先对链表a进行初始化\n\n");
    else
    la=ListInsert(la); 
    }
    else if(ch=='b')
    {
        
    if(!lb)
    printf("请先对链表b进行初始化\n\n");
    else
    lb=ListInsert(lb);
    }
    }
    else if(x==3)
    {
        
    printf("请输入你要进行取值的链表a或者b\n\n");
    getchar();
    char ch=getchar();
    if(ch=='a') 
    {
        
    if(!la)
    printf("请先对链表a进行初始化\n\n");
    else
    GetElem(la); 
    }
    else if(ch=='b')
    {
        
    if(!lb)
    printf("请先对链表b进行初始化\n\n");
    else
    GetElem(lb);
    }
    }
    else if(x==4)
    {
        
    printf("请输入你要进行插入的链表a或者b\n\n");
    getchar();
    char ch=getchar();
    if(ch=='a') 
    {
        
    if(!la)
    printf("请先对链表a进行初始化\n\n");
    else
    InsertElem(la); 
    }
    else if(ch=='b')
    {
        
    if(!lb)
    printf("请先对链表b进行初始化\n\n");
    else
    InsertElem(lb);
    }
    } 
    else if(x==5)
    {
        
    if(!la)
    {
        
    printf("请先初始化链表a\n");
    break;
    }
    if(!la)
    {
        
    printf("请先初始化链表b\n");
    break;
    }
    UnionList(la,lb);
    } 
    else
    break;
    }
    return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70]

2，线性表链式存储结下的基本操作的实现（初始化，赋值、取值、插入、删除归并等）。

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #define len sizeof(struct list)
    struct list
    {
        
    int data;
    struct list *next;
    };struct list *la,*lb;
    struct list * InitList()
    {
        
    struct list *head;
    head=(struct list *)malloc(len);
    return head;
    }
    struct list * ListInsert(struct list* &la)
    {
        
    struct list *p1,*head;
    int n;
    head=la;
    printf("请输入数据的个数\n");
    scanf("%d",&n);
    printf("请输入数据,用空格分开\n");
    while(n--)
    {
        
    p1=(struct list*)malloc(len);
    scanf("%d",&p1->data);
    p1->next=NULL;
    la->next=p1;
    la=p1;
    }
    return head;
    }
    void GetElem(struct list * la)
    {
        
    printf("请输入你要取得值的位置\n");
    int n;
    scanf("%d",&n);
    while(la->next&&n)
    {
        
    n--;
    la=la->next;
    }
    if(n)
    printf("输入的位置超出链表范围\n");
    else
    printf("所处位置的元素为%d\n",la->data);
    }
    void InsertElem(struct list * la)
    {
        
    struct list* pos;
    printf("请输入你要插入的位置和元素\n");
    int n,x;
    scanf("%d %d",&n,&x);
    while(la->next&&n)
    {
        
    n--;
    pos=la;
    la=la->next;
    }
    if(n)
    printf("输入的位置超出链表范围\n");
    else
    {
        
    struct list * p1;
    p1=(struct list*)malloc(len);
    p1->data=x;
    p1->next=pos->next;
    pos->next=p1; 
    printf("插入成功\n");
    } 
    }
    bool UnionList(struct list *pa,struct list *pb)
    {
        
    struct list *head;
    head=pa;
    while(pa->next)
    {
        
    pa=pa->next;
    }
    pa->next=pb->next;
    printf("合并后的链表为:\n"); 
    while(head->next){
        
    printf("%d ",head->next->data);
    head=head->next;
    }
    printf("\n");
    }
    int main()
    {
        
        printf("1, 初始化链表\n");
    printf("2, 对链表进行赋值\n");
    printf("3, 向链表中取值\n");
    printf("4, 向链表中插入元素\n");
    printf("5, 归并链表\n"); 
    printf("6, 退出程序\n");
    while(1)
    {
        
    
    int x;
    scanf("%d",&x);
    if(x==1)
    {
        
    printf("请输入你要初始化的链表a,b\n\n");
    getchar();
    char ch;
    ch=getchar();
    if(ch=='a')
    {
        
    la=InitList();
    if(!la)
    printf("初始化失败\n\n"); 
    else{
        
    la->next=NULL;
    printf("初始化成功\n\n");
    }
    }
    else if(ch=='b'){
        
    lb=InitList();
    if(!lb)
    printf("初始化失败\n\n");
    else{
        
    lb->next=NULL;
    printf("初始化成功\n\n"); 
    }
    }
    else
    printf("输入错误\n\n");
    }
    else if(x==2)
    {
        
    printf("请输入你要进行赋值的链表a或者b\n\n");
    getchar();
    char ch=getchar();
    if(ch=='a') 
    {
        
    if(!la)
    printf("请先对链表a进行初始化\n\n");
    else
    la=ListInsert(la); 
    }
    else if(ch=='b')
    {
        
    if(!lb)
    printf("请先对链表b进行初始化\n\n");
    else
    lb=ListInsert(lb);
    }
    }
    
    else if(x==3)
    {
        
    printf("请输入你要进行取值的链表a或者b\n\n");
    getchar();
    char ch=getchar();
    if(ch=='a')
    {
        
    if(!la)
    printf("请先对链表a进行初始化\n\n");
    else
    GetElem(la); 
    }
    else if(ch=='b')
    {
        
    if(!lb)
    printf("请先对链表b进行初始化\n\n");
    else
    GetElem(lb);
    }
    }
    else if(x==4)
    {
        
    printf("请输入你要进行插入的链表a或者b\n\n");
    getchar();
    char ch=getchar();
    if(ch=='a') 
    {
        
    if(!la)
    printf("请先对链表a进行初始化\n\n");
    else
    InsertElem(la); 
    }
    else if(ch=='b')
    {
        
    if(!lb)
    printf("请先对链表b进行初始化\n\n");
    else
    InsertElem(lb);
    }
    }
    else if(x==5)
    {
        
    if(!la)
    {
        
    printf("请先初始化链表a\n");
    break;
    }
    if(!la)
    {
        
    printf("请先初始化链表b\n");
    break;
    }
    UnionList(la,lb);
    } 
    else
    break;
    }
    return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70]: /images/20221124/b11a06d5572842d9bf8e0e8e3267fa1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 1]: /images/20221124/d06e0e650b864532b8530eb686b01af0.png