C++ 线性表操作：基本功能实现与应用示例

#include using namespace std;

#define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MAXSIZE 100 typedef int Status; typedef int ElemType;

typedef struct { ElemType *elem; int length; } SqList;

// 初始化线性表 Status InitList(SqList &L) { L.elem=new ElemType [MAXSIZE]; if(!L.elem ) { exit(OVERFLOW); } L.length=0; return OK; }

// 删除线性表中的某个元素 Status ListDelete(SqList &L,int i) { if(i<1||i>L.length) return ERROR; else { for (int j = i-1; j < L.length; ++j) { L.elem[j]=L.elem[j+1]; } L.length--; return OK; } }

// 插入新的元素 Status ListInsert(SqList &L ,int i ,ElemType e) { if(i<1||i>L.length+1) return ERROR; if(MAXSIZE==L.length) return ERROR; else { 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 InputElem(SqList &L,int length) { L.length=length; for (int i = 0; i < length; ++i) { std::cin>>L.elem[i]; } return OK; }

// 判断线性表是否为空 int ListEmpty(SqList L) { return (L.length==0); }

// 遍历输出线性表中的元素 Status DispList(SqList L) { if(ListEmpty(L)) { return ERROR; } for (int i = 0; i < L.length; ++i) { std::cout<<L.elem[i]<<' '; } return OK; }

// 获取线性表中某个位置的元素 Status GetELem(SqList L,int i,int &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(e == L.elem[i]) { return i+1; } } return ERROR; }

// 删除线性表中在某个范围内的元素 Status DeleteElmeinRange(SqList &L, ElemType x, ElemType y) { if ( x > y ) return OVERFLOW; if( ListEmpty(L) ) return ERROR; SqList sl; InitList(sl); int j=0; for (int i = 0; i < L.length; ++i) { if ( L.elem[i] < x || L.elem[i] > y ) { sl.elem[j]=L.elem[i]; sl.length++; j++; } } L=sl; return OK; }

// 使线性表中的元素不重复 Status SingleValue(SqList &L) { if ( ListEmpty(L) ) return ERROR; for (int i = 0; i < L.length - 1; ++i) { int x = L.elem[i]; for (int j = i + 1; j < L.length; ++j) { if (L.elem[j] == x ) { ListDelete(L,j+1); j--; } } } return OK; }

// 直接插入排序 Status StraightInsertionSort(SqList &L) { if (ListEmpty(L) ) return ERROR; int temp; int j; for (int i = 1; i < L.length; ++i) { if (L.elem[i] < L.elem[i-1]) { temp=L.elem[i]; for ( j = i - 1; j >= 0 && temp < L.elem[j] ; --j ) { L.elem[j+1] = L.elem[j]; } L.elem[j+1]=temp; } } return OK; }

// 简单的划分 Status SimpleDivide(SqList &L) { if ( ListEmpty(L) ) return ERROR; for (int i = 1; i < L.length; ++i) { if(L.elem[i]<=L.elem[0]) { ListInsert(L,1,L.elem[i]); ListDelete(L,i+2); } } return OK; }

int main() { void mainMeun(SqList &L, int &e);

SqList L;
InitList(L);
int n;
std::cout<<'请输入要创建的元素个数:';
cin>>n;
InputElem(L,n);
int e;
while(1)
    {
        mainMeun(L,e);
    }

return 0;

}

// 主菜单函数 void mainMeun(SqList &L, int &e) { char i; int n,j; std::cout<<' 请输入您要进行的操作: ';

std::cout<<'	P:遍历当前线性表

' <<' G:获取某个位置的元素 ' <<' L:查找某个元素的位置 ' <<' I:在线性表中插入元素 ' <<' D:删除线性表中的某个元素 ' <<' M:删除线性表中在某个范围内的元素 ' <<' S:使线性表中的元素不重复 ' <<' F:简单的划分 ' <<' X:直接插入排序 ' <<' Q:退出系统 '; std::cin>>i; i= toupper(i); // 将输入的小写字母转换为大写字母 switch (i) { case 'G': cout<<'请输入要获取的元素位置:'; cin>>n; if( !GetELem(L,n,e) ) { cout<<'位置无效，请重新输入('<<1<<'-'<<L.length<<') '; } else cout<<'该元素为:'<<e; break; case 'P': DispList(L); break; case 'D': cout<<'请输入要删除的元素位置:'; cin>>n; if(ListDelete(L,n)) { cout<<'删除成功!'; } else { cout<<'删除失败!'; } break; case 'L': cout<<'请输入要查找的元素值:'; cin>>n; if(! LocateElem(L,n) ) { cout<<'该值在线性表中不存在'; } else { cout<<'该值为第'<<LocateElem(L,n)<<'个元素'; } break; case 'I': cout<<'请输入要插入的位置: '; cin>>n; cout<<'请输入要插入的元素值: '; cin>>j; if( ListInsert(L,n,j) ) cout<<'插入成功!'; else cout<<'插入失败!'; break; case 'M': int x,y; cin>>x; cin>>y; if ( OVERFLOW == DeleteElmeinRange(L,x,y) ) { cout<<'范围无效! '; } else if ( ERROR == DeleteElmeinRange(L,x,y) ) { cout<<'线性表为空! '; } else { DispList(L); } break; case 'S': cout<<'去重前:'; DispList(L); cout<<'去重后:'; SingleValue(L); DispList(L); break; case 'F': if ( ERROR == SimpleDivide(L) ) cout<<'线性表为空! '; else { cout<<'划分后的线性表为: '; DispList(L); } break; case 'X': if( ERROR == StraightInsertionSort(L) ) { cout<<'线性表为空! '; } else { cout<<'排序后的线性表为: '; DispList(L); } break; case 'Q': cout<<'感谢使用，再见!'; ::exit(0); default: std::cout<<'您的输入有误，请重新输入 '; break; } }