一.线性表

1. 顺序表

概念：用一组地址连续的存储单元依次存储线性表的数据元素，通常使用数组。 特点：逻辑上相邻的数据元素，其物理次序也是相邻的。

定义和基本操作的实现：

1.宏定义：

#include <iostream> #define OK 1 #define ERROR 0 #define OVERFLOW -2 using namespace std; const int MAXSIZE=5; typedef int ElemType;

2.结构体：

typedef struct{ int *elem; int length; }SqList;//构造一个结构体，elem为储存空间的基地址，length为当前长度，结构类型为SqList;

3.创建一个线性表：

int InitList(SqList &L){ L.elem=new ElemType[MAXSIZE]; if(!L.elem) exit(OVERFLOW); L.length=0; return OK; }//构造一个空的顺序表L

4.输入元素：

int Input(SqList &L,int n){ cout<<"请输入元素："<<endl; for(int i=0;i<n;i++){ cin>>L.elem[i]; L.length++; } return OK; }//输入元素

5.定位：

int LocateElem(SqList L,ElemType e){ int flag=0; for(int i=0;i<L.length;i++){ if(L.elem[i]==e){ cout<<i+1<<endl; flag=1; } } if(flag==0) cout<<"未找到目标元素！"<<endl; return 0; }//定位

6.插入：

int 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; }//插入

7.删除：

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

8.输出：

int Output(SqList &L,int i){ cout<<"新的线性表为:"<<endl; for(int j=0;j<i;j++){ cout<<L.elem[j]<<' '; } return OK; }

完整代码：

#include <iostream> #define OK 1 #define ERROR 0 #define OVERFLOW -2 using namespace std; const int MAXSIZE=5; typedef int ElemType; typedef struct{ int *elem; int length; }SqList;//构造一个结构体，elem为储存空间的基地址，length为当前长度，结构类型为SqList; int InitList(SqList &L){ L.elem=new ElemType[MAXSIZE]; if(!L.elem) exit(OVERFLOW); L.length=0; return OK; }//构造一个空的顺序表L int Input(SqList &L,int n){ cout<<"请输入元素："<<endl; for(int i=0;i<n;i++){ cin>>L.elem[i]; L.length++; } return OK; }//输入元素 int LocateElem(SqList L,ElemType e){ int flag=0; for(int i=0;i<L.length;i++){ if(L.elem[i]==e){ cout<<i+1<<endl; flag=1; } } if(flag==0) cout<<"未找到目标元素！"<<endl; return 0; }//定位 int 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; }//插入 int ListDelete(SqList &L,int i){ if((i<1)||(i>L.length)) return ERROR; for(int j=i;j<=L.length-1;j++){ L.elem[j-1]=L.elem[j]; } --L.length; return OK; }//删除 int Output(SqList &L,int i){ cout<<"新的线性表为:"<<endl; for(int j=0;j<i;j++){ cout<<L.elem[j]<<' '; } return OK; } int main(){ SqList MYL; char a; a='Y'; int data,i,num; int key=0; InitList(MYL); cout<<"请输入元素个数："<<endl; cin>>num; int current=num; Input(MYL,num); while(a=='Y'){ cout<<"请选择你需要的帮助(0=定位，1=插入，2=删除)"<<endl; cin>>key; if(key==0){ cout<<endl<<"请输入所需要定位的元素："; cin>>data; LocateElem(MYL,data); } if(key==1){ cout<<endl<<"请输入要插入的元素："; cin>>data; cout<<endl<<"请输入要插入的位置："; cin>>i; ListInsert(MYL,i,data); current=current+1; Output(MYL,current); } if(key==2){ cout<<endl<<"请输入要删除的位置："; cin>>i; ListDelete(MYL,i); current=current-1; Output(MYL,current); } cout<<endl<<"请问是否继续?(Y:继续 N:结束)"<<endl; getchar(); cin>>a; } return 0; }