C语言 数据结构 线性表的顺序存储及其操作实验

1.顺序表的基本操作实践。实现顺序表的建立、输入、输出、查找、插入、删除等功能，每个功能用一个函数实现。

(1)建立4个元素的顺序表list[]={3，2，4，5}，实现顺序表建立的基本操作。

(2)在list[]={3，2，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。

(3)在list[]={3，3，4，9，5}中删除指定位置（i=3）上的元素4，实现顺序表的删除的基本操作。

2. 基本算法实践。若一个线性表采用顺序表L存储，其中所有元素为整数。设计一个时间空间尽可能高效的算法，将所有元素分成两部分，其中前部分元素均小于等于整数k1，后部分均大于等于整数k2。例如：{6,4,10,7,9,2,20,1,3,30}，k1=5，k2=8时候，一种结果为（[3,4,1,2],,6,7,[20,10,9,30]）。（其实这题应该可以直接将顺序表排序也可达到题目要求，但这就与k1,k2无任何关系，与出题初衷不符（也可能是我想错了！！！））

3.有序顺序表基本算法实践。假设表示集合的顺序表是一个有序顺序表，设计一个高效的算法实现集合求差集运算，即C=A-B。例如A={1，3，4，5，6，7}，B={3，5，6，8，9，11}，输出A-B的结果={1,4,7}

#include

#include

#define MaxSize 50

typedef int ElemType;

typedef struct

{

    ElemType data[MaxSize];

    int length;

}Sqlist;

void CreateList1(Sqlist*&L,ElemType a[],int n)//第一题，建立线性表并将题中数据元素输入

{

    int i=0,k=0;

    L = (Sqlist *)malloc(sizeof(Sqlist));

    while(idata[k]=a[i];

    k++;i++;

    }

    L->length = k;

}

void CreateList(Sqlist *&L)//建立线性表并输入数据元素

{

    L = (Sqlist *)malloc(sizeof(Sqlist));

    printf("请规定线性表长度");

    scanf("%d",&L->length);

    for(int q=0;qlength;q++){   //将值赋给新创建的顺序表

        printf("请输入第%d个元素",q+1);

        scanf("%d",&L->data[q]);

    }

}

void DispList(Sqlist *L)//输出线性表

{

    for(int i=0;ilength;i++){

        printf("%d\t",L->data[i]);

    }

    printf("\n");

}

int LocateElem(Sqlist *L,ElemType e)//按元素查找,因题中未做要求，故未调用

{

    int i=0;

    while(ilength&&L->data[i]!=e)

        i++;

    if(i>=L->length)

        return 0;

    else

        return i+1;

}

bool ListInsert(Sqlist *&L,int i,ElemType e)//插入数据元素（按题中要求）

{

    int j;

    if(iL->length+1||L->length==MaxSize)

        return false;

    i--;

    for (j=L->length;j>i;j--)

        L->data[j]=L->data[j-1];

    L->data[i]=e;

    L->length++;

    return true;

}

bool ListDlete(Sqlist *&L,int i)//删除数据元素（按题中要求）

{

    int j;

    if(iL->length)

        return false;

    i--;

    for(j=i;jlength-1;j++)

        L->data[i]=L->data[j+1];

    L->length--;

    return true;

}

void Partitionl(Sqlist *&L,Sqlist *&C,int k1,int k2);//声明函数

void DifferenceSet(Sqlist *LA,Sqlist *LB,Sqlist *&LC);//声明函数

int main(){

    Sqlist *L;

    printf("第一题\n\n");

    int a[4]={3,2,4,5},e;

    CreateList1(L, a, 4);//按题目要求创建顺序表

    DispList(L);//输出顺序表

    ListInsert(L,4,9);//按题目要求插入数据元素

    DispList(L);//输出线性表

    ListDlete(L,3);//删除指定位置（i=3）上的元素

    DispList(L);//输出线性表

    printf("\n第二题\n");

    int k1,k2;

    Sqlist *C;

    C=(Sqlist *)malloc(sizeof(Sqlist));//创建一个新的线性表

    CreateList(L);//创建顺序表并输入数据元素

    printf("请规定k1的大小");

    scanf("%d",&k1);

    printf("请规定k2的大小");

    scanf("%d",&k2);

    Partitionl(L,C,k1,k2);

    DispList(C);//输出第二题要求的线性表

    printf("\n第三题\n");

    Sqlist *LA,*LB,*LC;

    printf("线性表A\n");

    CreateList(LA);//创建顺序表LA并输入数据元素

    printf("线性表B\n");

    CreateList(LB);//创建顺序表LB并输入数据元素

    DifferenceSet(LA,LB,LC);//求差集

    DispList(LC);//输出第三题要求的线性表

    }

void Partitionl(Sqlist *&L,Sqlist *&C,int k1,int k2)

{

    int i=0,j=L->length-1,t=0,z=0;

    C->length=L->length;//规定新线性表的长度

    for(int q=0;qlength;q++){

       if(L->data[q]>=k2){   // 将大于k2的元素放入顺序表

            C->data[j]=L->data[q];

            j--;

       }

       if(L->data[q]data[i]=L->data[q];

            i++;

        }

       }

    for(int q=0;qlength;q++){   //将大小处于k1k2之间的元素放入顺序表

        if(L->data[q]>k1&&L->data[q]data[i]=L->data[q];

            i++;

        }

    }

    printf("输出的线性表为\n");

}

void DifferenceSet(Sqlist *LA,Sqlist *LB,Sqlist *&LC){

    int i=0,j=0,k=0;

    LC=(Sqlist *)malloc(sizeof(Sqlist));//创建一个新的线性表

    while(ilength&&jlength){

        if(LA->data[i]< LB->data[j]){   //比较A、B两个线性表中数据元素的大小

            LC->data[k]=LA->data[i];

            i++;k++;

        }

        else if(LA->data[i]> LB->data[j]){

            j++;

        }

        else{                  //(LA->data[i]= LB->data[j]

            i++;j++;

        }

    }

    while(ilength){      //若A的长度大于B的长度

        LC->data[k]=LA->data[i];

        i++;k++;

}

    LC->length=k;          //线性表的长度为k

    printf("A和B的差集为\n");

}

运行结果：

当时为方便将输出截图插入实验报告中，将“\t”改成了“、”，截完图之后又把“、”改回了“\t” 。