数据结构-- 顺序表及其应用--顺序表的基本操作及有序表的合并

绝地灬酷狼 2023-07-03 13:30 5阅读 0赞

# 数据结构–顺序表及其应用——顺序表的基本操作及有序表的合并 #

## 【实验目的】 ##

帮助学生熟练掌握线性表的顺序存储结构（顺序表）的基本操作及其简单应用，实现两个有序表的合并操作。

## 【实验内容及要求】 ##

1.实现顺序表的各种基本操作，包括创建顺序表、插入和删除指定序号的元素、读取表元、获取最大和最小值元素、查找元素、表元素的排序、表元素逆置、顺序表的输入和输出等等；  
2.实现两个有序顺序表的合并。  
问题描述：创建两个有序的顺序表L1和L2，表中元素值由键盘随机输入，再将它们合并为一个新的顺序表L3,合并后L3仍然有序（重复元素只保留一个），最后输出顺序表中的各个元素值。  
3.设计测试用例，测试基本操作和合并操作的正确性。  
４.实现说明：这是第一个上机描述和实现的数据结构类型，旨在让学生加深对数据结构、逻辑结构、存储结构和算法及算法时间复杂度等概念的理解。

## 【源代码】 ##

#include <iostream>
    #include <stdlib.h>
    #define list_init_size 100
    #define listincrement 10
    #define elemtype int
    #define Status int
    #define TRUE        1
    #define FALSE       0
    #define OK          1
    #define ERROR       0
    #define INFEASIBLE   -1
    #define OVERFLOW   -2
    using namespace std;
    
    typedef struct
    {
        
        elemtype *elem;
        int length;
        int listsize;
    } Sqlist; 
    
    Status initlist_sq(Sqlist &L)//初始化
    {
        
        L.elem=(elemtype *)malloc(list_init_size*sizeof(elemtype));
        if(!L.elem)
            exit(OVERFLOW);
        L.length=0;
        L.listsize=list_init_size;
        return OK;
    }
    
    Status listinsert_sq(Sqlist &L,int i,elemtype e)//插入元素
    {
        
        elemtype *p,*q;
        if(i<1||i>L.length+1)
            return ERROR;
        if(L.length>=L.listsize)
        {
        
            elemtype *newbase = (elemtype*)realloc(L.elem,(L.listsize + listincrement)*sizeof(elemtype));
            if(!newbase)
                exit(OVERFLOW);
            L.elem=newbase;
            L.listsize +=listincrement;
        }
        q=&(L.elem[i-1]);
        for(p=&(L.elem[L.length-1]); p >= q; --p)
            *(p+1)=*p;
        *q=e;
        ++L.length;
        return OK;
    }
    
    Status listdelete_sq(Sqlist &L,int i,elemtype &e)//删除元素
    {
        
        elemtype *p,*q;
        if((i<1)||(i>L.length))
            return ERROR;
        p=&(L.elem[i-1]);
        e=*p;
        q=L.elem+L.length-1;
        for(++p; p<=q; ++p)
            *(p-1)=*p;
        --L.length;
        return OK;
    }
    
    Status getelem_sq(Sqlist L,int i,elemtype &e)//读取元素
    {
        
        if(L.length==0||i<1||i>L.length)
            return ERROR;
        e=*(L.elem+i-1);
        return OK;
    }
    
    Status getmax_sq(Sqlist L,int i,elemtype &e)//最大值
    {
        
        if(L.length==0||i<1||i>L.length)
            return ERROR;
        elemtype *last;
        e=*L.elem;
        last=L.elem+L.length-1;
        while(L.elem!=last)
        {
        
            if(*L.elem>e)
                e=*(L.elem);
            L.elem++;
        }
        return OK;
    }
    
    
    Status getmini_sq(Sqlist L,int i,elemtype &e)//最小值
    {
        
        if(L.length==0||i<1||i>L.length)
            return ERROR;
        elemtype *last;
        e=*L.elem;
        last=L.elem+L.length-1;
        while(L.elem!=last)
        {
        
            if(*L.elem<e)
                e=*(L.elem);
            L.elem++;
        }
        return OK;
    }
    
    Status locateelem_Sq(Sqlist L, elemtype e,Status (*compare)(elemtype,elemtype))//查找元素
    {
        
        int i=1;
        elemtype *p;
        p=L.elem;
        while(i<=L.length&&!(*compare)(*p++,e)) ++i;
        if(i<=L.length) return i;
        else return 0;
        while(i<=L.length)
        {
        
            if((*compare)(e,L.elem[i-1]))
            {
        
                return i;
            }
            i++;
        }
        return 0;
    }
    
    Status compare_sq(elemtype e1,elemtype e2)//比较
    {
        
        if(e1==e2)
            return TRUE;
        else
            return FALSE;
    }
    
    void mergelist_sq(Sqlist La,Sqlist Lb,Sqlist &Lc)//合并
    {
        
        elemtype *pa,*pb,*pc,*pa_last,*pb_last;
        pa=La.elem;
        pb=Lb.elem;
        Lc.listsize=Lc.length=La.length+Lb.length;
        pc=Lc.elem=(elemtype *)malloc(Lc.listsize*sizeof(elemtype));
        if(!Lc.elem)
            exit(OVERFLOW);
        pa_last=La.elem+La.length-1;
        pb_last=Lb.elem+Lb.length-1;
        while(pa<=pa_last&&pb<=pb_last)
        {
        
            if(*pa<=*pb)
                *pc++=*pa++;
            else *pc++=*pb++;
        }
        while(pa<=pa_last)
            *pc++=*pa++;
        while(pb<=pb_last)
            *pc++=*pb++;
    }
    
    void listreverse_sq(Sqlist &L)//表元素逆置
    {
        
        int i=0,j=L.length-1;
        elemtype temp=0;
        while(i<j)
        {
        
            temp=L.elem[i];
            L.elem[i]=L.elem[j];
            L.elem[j]=temp;
            i++;
            j--;
        }
    }
    
    void listsort_sq(Sqlist &L)//起泡法排序
    {
        
        elemtype t=0;
        for(int i=0; i<L.length-1; i++)
            for(int j=0; j<L.length-1-i; j++)
                if(L.elem[j]>L.elem[j+1])
                {
        
                    t=L.elem[j];
                    L.elem[j]=L.elem[j+1];
                    L.elem[j+1]=t;
                }
    }
    
    void  listput_sq(Sqlist &L,int n)//顺序表的定义算法
    {
        
        cout<<"请依次输入顺序表中要储存的"<<n<<"个元素："<<endl;
        for(int i=0; i<n; i++)
        {
        
            cin>>L.elem[i];
            L.length++;
        }
    }
    
    void  listout_sq(Sqlist &L)//顺序表的定义算法
    {
        
        for(int i=0; i<L.length; i++)
        {
        
            cout<<L.elem[i]<<" ";
        }
    }
    
    
    
    int main()
    {
        
        Sqlist L1,L2,L3;
        initlist_sq(L1);
        initlist_sq(L2);
        listput_sq(L1,10);
        listput_sq(L2,5);
        mergelist_sq(L1,L2,L3);
        listsort_sq(L3);
        listout_sq(L3);
        return 0;
    }

> [数据结构数据类型图示][Link 1]

## 【实验结果】 ##

输入顺序表L1和L2的元素：  
L1：0 1 2 3 4 5 6 7 8 9  
L2:1 2 3 4 5

最后得出结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]

[Link 1]: https://ss1.bdstatic.com/70cFvXSh_Q1YnxGkpoWK1HF6hhy/it/u=1437616115,2305873262&fm=26&gp=0.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200207111938894.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk=,size_16,color_FFFFFF,t_70