顺序表的操作总结-白红宇

顺序表的操作总结

阅读量：321 次

发布时间：2019-03-04

本文共 5710 字，大约阅读时间需要 19 分钟。

定义

#include <iostream>#define ElemType int#define OK 1#define ERROR 0#define OVERFLOW -2#define MAXSIZE 100using namespace std;//定义typedef int Status;typedef struct{       ElemType *elem;    int length;}SqList;

初始化

Status InitList(SqList &L){       L.elem = new ElemType[MAXSIZE];    if(!L.elem) return OVERFLOW;    L.length = 0;    return OK;}

基本方法

取值

Status GetElem(SqList L, int i, ElemType &e){       if(i<1||i>L.length) return ERROR;    e = L.elem[i-1];    return OK;}

查找元素(返回第一个元素下标

int LocateElem(SqList L, ElemType e){       for(int i=0; i<L.length; i++)        if(L.elem[i]==e) return i+1;    return 0;}

修改元素

Status ChangeElem(SqList &L, int i, ElemType e){       if(i<1||i>L.length) return ERROR;    L.elem[i-1] = e;    return OK;}

插入元素

Status ListInsert(SqList &L, int i, ElemType e){       if((i<1)||(i>L.length+1)) return ERROR;    if(L.length==MAXSIZE) return ERROR;    for(int j=L.length-1;j>=i-1;j--)        L.elem[j+1] = L.elem[j];    L.elem[i-1] = e;    ++L.length;    return OK;}

删除

Status ListDelete(SqList &L, int i){       if((i<1)||(i>L.length)) return ERROR;    for(int j=i;j<L.length;j++)        L.elem[j-1] = L.elem[j];    --L.length;    return OK;}

打印

void DelayElem(SqList &L){       for(int i=1;i<=L.length;i++) {           ElemType e;        GetElem(L,i,e);        if(i==L.length)            cout<<e<<"("<<i<<")"<<endl;        else            cout<<e<<"("<<i<<")"<<"->";    }}

创建顺序表

Status CreateElem(SqList &L){       int n;    cout<<"输入链表元素个数";    cin>>n;    for(int i=0;i<n;i++)    {           ElemType e;        cout<<"第"<<i+1<<"个元素:";        cin>>e;        ListInsert(L,i+1,e);    }    return OK;}

print<仅供参考>

void PrintStatus(SqList &L){       cout<<"第一次操作，请初始化表"<<endl;    CreateElem(L);}void PrintStatus_2(SqList &L){       cout<<"目前L中元素:"<<endl;DelayElem(L);    cout<<"输入1修改顺序表"<<endl;    cout<<"输入2删除顺序表"<<endl;    cout<<"输入3退出"<<endl;}

main

int main(){       SqList L;    int choices,i;    InitList(L);    PrintStatus(L);    PrintStatus_2(L);    cin>>choices;    while(choices&&choices!=3) {           switch(choices)        {           case 1:            cout<<"输入需要修改的元素的index";            cin>>i;            cout<<"输入修正值:";            ElemType e;            cin>>e;            if(ChangeElem(L,i,e))                cout<<"ok"<<endl;            else                cout<<"error"<<endl;            break;        case 2:            cout<<"输入需要删除的元素的下标";            cin>>i;            if(ListDelete(L,i))                cout<<"ok"<<endl;            else                cout<<"error"<<endl;            break;        case 3:            break;        default:            cout<<"输入不正确"<<endl;            break;        }        if(choices!=3) {               PrintStatus_2(L);            cin>>choices;        }    }    return 0;}

交集

SqList SameListElem(SqList &L1,SqList &L2){       SqList L3;    InitList(L3);    for(int i=0;i<L2.length;i++)        ListInsert(L3,L3.length+1,L2.elem[i]);    for(int i=0;i<L1.length;i++) {           int j = LocateElem(L3,L1.elem[i]);        if(j!=0)            continue;        else            ListInsert(L3, L3.length, L1.elem[i]);    }    cout<<"并集：";    PrintList(L3);    return L3;}

并集

SqList CrossList(SqList &L1, SqList &L2){       SqList L3;    InitList(L3);    if(L1.length>L2.length) {           for(int i=0;i<L2.length;i++)            ListInsert(L3,L3.length+1,L2.elem[i]);    } else {           for(int i=0;i<L1.length;i++)            ListInsert(L3,L3.length+1,L1.elem[i]);    }    for(int i=0;i<L3.length;i++) {           int j = LocateElem(L1,L3.elem[i]);        if(j==0)            ListDelete(L3,i+1);        else            continue;    }    cout<<"交集：";    PrintList(L3);    return L3;}

差集

Status uniqueElem(SqList &L1, SqList &L2){       if(L1.length<L2.length) return ERROR;    //L3复制L1    SqList L3;    InitList(L3);    for(int i=0;i<L1.length;i++)        ListInsert(L3,L3.length+1,L1.elem[i]);    //主体循环    int times=0;    for(int i=0;i<L1.length;i++) {           int j = LocateElem(L2,L1.elem[i]);        //L1的元素在L2中存在，需要进行删除操作        if(j==0)            continue;        else        {               int temp = i+1;            temp-=times;            ListDelete(L3,temp);            times++;        }    }    cout<<"差集：";    PrintList(L3);    return OK;}

调用上面三方法

void Option(SqList L1, SqList L2){       cout<<"请选择您需要进行的操作"<<endl;    cout<<"输入1求并集"<<endl;    cout<<"输入2求交集"<<endl;    cout<<"输入3求差集"<<endl;    cout<<"输入0退出操作"<<endl;    int option;    cin>>option;    //并集    //交集    //差集: 并集-交集    while(option!=0){           SqList L5,L6,L3,L4;        L5 = L1;        L6 = L2;        switch(option)        {           case 1:            SameListElem(L1,L2);            break;        case 2:            CrossList(L1,L2);            break;        case 3:            L3 = SameListElem(L1,L2);            L4 = CrossList(L1,L2);            uniqueElem(L3,L4);            break;        default:            cout<<"您的输入有误，请重新输入"<<endl;            break;        }        cout<<"请选择您需要进行的操作"<<endl;        cout<<"输入1求并集"<<endl;        cout<<"输入2求交集"<<endl;        cout<<"输入3求差集"<<endl;        cout<<"输入0退出操作"<<endl;        cin>>option;    }

int main(){       srand(time(NULL));    //随机产生两个集合    int len1 = rand() % 10 + 1;    int len2 = rand() % 10 + 1;    vector<ElemType> temp1,temp2;    for (int i = 0; i < len1; ++i)    {           temp1.push_back(i + 1);    }    for (int i = 0; i < len2; ++i)    {           temp2.push_back(i + 1);    }    random_shuffle(temp1.begin(), temp1.end());    random_shuffle(temp2.begin(), temp2.end());    SqList L1,L2;    InitList(L1);    InitList(L2);    //插入到顺序表中    InsertElem(L1,temp1);    InsertElem(L2,temp2);    PrintList(L1);    PrintList(L2);    Option(L1,L2);    return 0;}