数据结构实验一

雨点打透心脏的1/2处 2022-06-06 05:45 207阅读 0赞

# 实验目录 #

1、基于sequlist.h中定义的顺序表，编写算法函数reverse(sequence\_list \*L)，实现顺序表的就地倒置。

2、编写一个算法函数void sprit( sequence\_list \*L1,sequence\_list \*L2,sequence\_list \*L3)，  
将顺序表L1中的数据进行分类，奇数存放到存到顺序表L2中，偶数存到顺序表L3中，编写main()进行测试。

3、已知顺序表L1，L2中数据由小到大有序，请用尽可能快的方法将L1与L2中的数据合并到L3中，使数据在L3中按升序排列。

4、假设顺序表la与lb分别存放两个整数集合，函数inter(seqlist \*la,seqlist \*lb,seqlist \*lc)  
的功能是实现求顺序表la与lb的交集存放到顺序表lc中,请将函数补充完整.

5、请编写一个算法函数partion(sequence\_list \*L)，尽可能快地将顺序表L中的所有奇数调整到表的左边，  
所有偶数调整到表的右边，并分析算法的时间复杂度。

## 实验一 ##

/**********************************/
    /*文件名称：lab1-01.c             */
    /**********************************/
    /*基于sequlist.h中定义的顺序表，编写算法函数reverse(sequence_list *L)，实现顺序表的就地倒置。*/
    //#include "sequlist.h"
    /*请将本函数补充完整，并进行测试*/
    void reverse(sequence_list *L)
    {
        int temp;
        for(int i=0;i<L->size/2;i++)
        {
            temp=L->a[i];
            L->a[i]=L->a[L->size-1-i];
            L->a[L->size-1-i]=temp;
        }
    }
    int main()
    {
        sequence_list L;			/*定义顺序表*/
        input(&L);	        		/*输入测试用例*/
        print(&L);                  /*输出原表*/
        reverse(&L);		            /*顺序表倒置*/
        print(&L);                  /*输出新表*/
    }

## 实验二 ##

/**********************************/
    /*文件名称：lab1_02.c             */
    /**********************************/
    
    /*编写一个算法函数void sprit( sequence_list *L1,sequence_list *L2,sequence_list *L3)，
    将顺序表L1中的数据进行分类，奇数存放到存到顺序表L2中，偶数存到顺序表L3中，编写main()进行测试。
    */
    
    //#include "sequlist.h"
    /*请将本函数补充完整，并进行测试*/
    void sprit(sequence_list *L1,sequence_list *L2,sequence_list *L3)
    {
        L2->size=0;
        L3->size=0;
        for(int i=0; i<L1->size; i++)
        {
            if(L1->a[i]&1)
                L2->a[L2->size++]=L1->a[i];
            else
                L3->a[L3->size++]=L1->a[i];
        }
    }
    int main()
    {
        sequence_list L1,L2,L3;		/*定义三个顺序表*/
        input(&L1);				    /*输入L1*/
        sprit(&L1,&L2,&L3);		    /*对L1进行分类*/
        print(&L1);				    /*输出L1、L2和L3*/
        print(&L2);
        print(&L3);
    }

## 实验三 ##

/**********************************/
    /*文件名称：lab1_03.c                 */
    /**********************************/
    
    /*已知顺序表L1，L2中数据由小到大有序，请用尽可能快的方法将L1与L2中的数据合并到L3中，使数据在L3中按升序排列。*/
    
    //#include "sequlist.h"
    /*请将本函数补充完整，并进行测试*/
    void merge(sequence_list *L1,sequence_list *L2,sequence_list *L3)
    {
        L3->size=0;
        int cnt1=0,cnt2=0;
        while(cnt1<L1->size&&cnt2<L2->size)
        {
            if(L1->a[cnt1]<L2->a[cnt2])
            L3->a[L3->size++]=L1->a[cnt1++];
            else
            L3->a[L3->size++]=L2->a[cnt2++];
        }
        while(cnt1<L1->size)
        {
            L3->a[L3->size++]=L1->a[cnt1++];
        }
        while(cnt2<L2->size)
        {
            L3->a[L3->size++]=L2->a[cnt2++];
        }
    }
    int main()
    {
        sequence_list L1,L2,L3;
        input(&L1);				/*输入时请输入有序数据*/
        input(&L2);				/*输入时请输入有序数据*/
        merge(&L1,&L2,&L3);		/*合并数据到L3*/
        print(&L3);				/*输出L3*/
    }

## 实验四 ##

/**********************************/
    /*文件名称：lab1_04.c                 */
    /**********************************/
    /*假设顺序表la与lb分别存放两个整数集合，函数inter(seqlist *la,seqlist *lb,seqlist *lc)
    的功能是实现求顺序表la与lb的交集存放到顺序表lc中,请将函数补充完整.  */
    //#include "sequlist.h"
    /*请将本函数补充完整，并进行测试*/
    void  inter(sequence_list *la,sequence_list *lb,sequence_list *lc)
    {
        lc->size=0;
        for(int i=0; i<la->size; i++)
            for(int j=0; j<lb->size; j++)
            {
                if(la->a[i]==lb->a[j])
                {
                    lc->a[lc->size++]=la->a[i];
                    break;
                }
            }
    }
    int main()
    {
        sequence_list la,lb,lc;
        inputfromfile(&la,"1.txt"); 		/*从文件1.txt建立顺序表*/
        inputfromfile(&lb,"2.txt");		/*从文件2.txt建立顺序表*/
        print(&la); 				 	    /*输出la*/
        print(&lb);  				        /*输出lb*/
        inter(&la,&lb,&lc);   		    /*求la与lb的交集存于lc中*/
        print(&lc); 					    /*输出lc*/
        return 0;
    }

## 实验五 ##

/**********************************/
    /*文件名称：lab1_05.c                 */
    /**********************************/
    /*
    请编写一个算法函数partion(sequence_list *L)，尽可能快地将顺序表L中的所有奇数调整到表的左边，
    所有偶数调整到表的右边，并分析算法的时间复杂度。
    */
    //#include "sequlist.h"
    /*请将本函数补充完整，并进行测试*/
    void partion(sequence_list *L)
    {
        int i=0,j=L->size-1;
        while(i<j)
        {
            while(L->a[i]%2&&i<j) i++;
            while
            {
            if(L->a[i]%2==0&&L->a[j]%2){        //  找到左边的偶数，右边的奇数，那么就进行交换；  
                int temp=L->a[j];  
                L->a[j]=L->a[i];  
                L->a[i]=temp;  
            }
    }
    }
    int main()
    {
        sequence_list L;
        inputfromfile(&L,"3.txt");
        print(&L);  						/*输出表L*/
        partion(&L);
        print(&L);  						/*输出新表*/
        return 0;
    }