【C语言】数据结构C语言版实验1 线性表的顺序实现

待我称王封你为后i 2022-12-23 00:42 204阅读 0赞

## 运行环境：Dev-C++ ##

vs2013可能不能运行

## 首先新建一个头文件sequlist.h ##

#include<stdio.h>
    #include<stdlib.h>
    
    #define MAXSIZE 100
    typedef int datatype;
    typedef struct{
        datatype a[MAXSIZE];
        int size;
    
    }sequence_list;
    /*初始化顺序表*/
    void initseqlist(sequence_list *L)
    {
        L->size = 0;
    }
    /*输入顺序表*/
    void input(sequence_list *L)
    {
        datatype x;
        initseqlist(L);
        printf("请输入一组数据，以0做为结束符：\n");
        scanf_s("%d", &x);
        while (x)
        {
            L->a[L->size++] = x;
            scanf_s("%d", &x);
        }
    }
    /*从文件输入顺序表*/
    void inputfromfile(sequence_list *L, char *f)
    {
        int i, x;
        FILE *fp = fopen(f,"r");
        L->size = 0;
        if (fp)
        {
            while (!feof(fp))
            {
                fscanf(fp, "%d", &L->a[L->size++]);
            }
            fclose(fp);
        }
    }
    /*输出顺序表*/
    void print(sequence_list *L)
    {
        int i;
        for (i = 0; i < L->size; i++)
        {
            printf("%5d", L->a[i]);
            if ((i + 1) % 10 == 0)
                printf("\n");
        }
        printf("\n");
    }

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

代码：

/*源文件 文件名称 lab1.c */
    #include "sequlist.h"
    /*请将本函数补充完整，并进行测试*/
    void reverse(sequence_list *L)
    {
        int i,j;
        datatype x;
        i=0;
        j=L->size-1;
        while (i<j)
        {
            x=L->a[i];
            L->a[i]=L->a[j];
            L->a[j]=x;
            i++;
            j--;
        }
    }
    
    int main()
    {
    
        sequence_list L;        /*定义顺序表*/
        input(&L);                    /*输入测试用例*/
        print(&L);                  /*输出原表*/
        reverse(&L);
        print(&L);                  /*输出新表*/
    }

测试：

![e1d9db22f2d0d0ab8fb1342ef5b0fc07.png][]

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

代码：

/*源文件 文件名称 lab2.c */
    #include "sequlist.h"
    /*请将本函数补充完整，并进行测试*/
    void sprit(sequence_list *L1,sequence_list *L2,sequence_list *L3)
    {
        int i,j,k;
        i=j=k=0;
        for (i=0;i<L1->size;i++)
        {
            if (L1->a[i]%2==1)
                    L2->a[j++]=L1->a[i];
            else
                    L3->a[k++]=L1->a[i];
    
        }
        L2->size=j;
        L3->size=k;
    }
    int main()
    {   sequence_list L1,L2,L3;        /*定义三个顺序表*/
        input(&L1);                    /*输入L1*/
        sprit(&L1,&L2,&L3);            /*对L1进行分类*/
        print(&L1);                    /*输出L1、L2和L3*/
        print(&L2);
        print(&L3);
    }

测试：

![1cc5726b3bf6956896c140d028185d87.png][]

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

代码：

/*源文件 文件名称 lab3.c */
    #include "sequlist.h"
    /*请将本函数补充完整，并进行测试*/
    void merge(sequence_list *L1,sequence_list *L2,sequence_list *L3)
    {
            int i,j,k;
            i=j=k=0;
            while (i<L1->size && j<L2->size )
            {
                if (L1->a[i]<L2->a[j])
                    L3->a[k++]=L1->a[i++];
                else
                    L3->a[k++]=L2->a[j++];
            }
            while (i<L1->size)
                    L3->a[k++]=L1->a[i++];
            while (j<L2->size)
                    L3->a[k++]=L2->a[j++];
            L3->size=k;
    
    }
    int main()
    {
        sequence_list L1,L2,L3;
        input(&L1);                /*输入时请输入有序数据*/
        input(&L2);                /*输入时请输入有序数据*/
        merge(&L1,&L2,&L3);        /*合并数据到L3*/
        print(&L3);                /*输出L3*/
    }

测试：

![6a5013053b471d5e8d2cf9a57a08b058.png][]

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

新建两个文本文件

![f8a8f04faaa6237eb544582d24229dc5.png][]

![22374a9a9bd5211cb076d5e65801ba93.png][]

代码：

/*源文件 文件名称 lab4.c */
    #include "sequlist.h"
    /*请将本函数补充完整，并进行测试*/
    void  inter(sequence_list *la,sequence_list *lb,sequence_list *lc)
    {
        int i,j,k;
        k=0;
        for (i=0; i<la->size; i++)
        {
                j=0;
               while (j<lb->size  &&  la->a[i]!=lb->a[j])
                    j++;
               if (j<lb->size)
                        lc->a[k++]=la->a[i];
        }
        lc->size=k;
    }
    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;
    }

测试：

![cd10cf473d5b21140effd4df5bdc5656.png][]

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

新建一个文本文件

![3616eb8f273b7a0680de5f226046712e.png][]

代码：

/*源文件 文件名称 lab5.c */
    #include "sequlist.h"
    /*请将本函数补充完整，并进行测试*/
    void partion(sequence_list *L)
    {
    
        int i,j;
        datatype x;
        i=0;
        j=L->size-1;
        do
        {
           while (i<j && L->a[i]%2==1 )
                    i++;
            while (i<j && (L->a[j]&0x1)==0)
                    j--;
            if (i<j)
            {
                x=L->a[i];
                L->a[i++]=L->a[j];
                L->a[j--]=x;
            }
        }while (i<j);
    
    }
    int main()
    {
      sequence_list L;
      inputfromfile(&L,"3.txt");
      print(&L);                          /*输出表L*/
      partion(&L);
      print(&L);                          /*输出新表*/
      return 0;
    }

测试：

![4deb71c6e0169c0713b440d1982e0eef.png][]

[e1d9db22f2d0d0ab8fb1342ef5b0fc07.png]: /images/20221120/a30fbe5b3e2145259065f7496217e6bb.png
[1cc5726b3bf6956896c140d028185d87.png]: /images/20221120/5ceb921c208948c498500323c7ee7b2b.png
[6a5013053b471d5e8d2cf9a57a08b058.png]: /images/20221120/d396deaf83c64720bbf77d90fad5e729.png
[f8a8f04faaa6237eb544582d24229dc5.png]: /images/20221120/d90bb088f86d41cfa121e91a3cafdada.png
[22374a9a9bd5211cb076d5e65801ba93.png]: https://img-blog.csdnimg.cn/img_convert/22374a9a9bd5211cb076d5e65801ba93.png
[cd10cf473d5b21140effd4df5bdc5656.png]: https://img-blog.csdnimg.cn/img_convert/cd10cf473d5b21140effd4df5bdc5656.png
[3616eb8f273b7a0680de5f226046712e.png]: https://img-blog.csdnimg.cn/img_convert/3616eb8f273b7a0680de5f226046712e.png
[4deb71c6e0169c0713b440d1982e0eef.png]: https://img-blog.csdnimg.cn/img_convert/4deb71c6e0169c0713b440d1982e0eef.png