1.要求

编程实现顺序表的基本操作，并设计一个菜单调用。

①建立（初始化）、遍历、取值、查找、插入、删除

②判空、求元素个数、前驱、后继、置为空表、销毁

2.分析

我们需要去定义一个结构体（以下代码的结构体名为SqList),其中有一个表示顺序表基位置的elem,和一个表示顺序表长度的length.

里面的很多操作都与数组操作有很大的相似性。值得注意的是，插入和删除的i取值的范围，在插入中i的取值范围是1至length+1(1和length+1也可），删除是1至length（1和length都可以）

3.代码实现

1）环境：我使用的是DEV C++，在此软件上创建了一个项目。

2)代码

i) 头文件（com_h2.H)

//作用：防止头文件的重复包含和编译 #ifndef _FUNC_H//先测试 _FUNC_H是否被宏定义过 #define _FUNC_H //如果没有宏定义下面就宏定义_FUNC_H并编译以下语句 //函数结果状态代码 #define OK 1#define OVERFLOW -2#define ERROR 0#define MAXSIZE 100 //顺序表可能达到的长度 typedef int Status; typedef int ElemType;//定义顺序表的结构体typedef struct sqlist {ElemType *elem;//存储空间的基地址 int length;}SqList; //定义了一个结构体，名字为Sqlist extern Status InitList(SqList &L); extern Status EstablishList(SqList &L,ElemType a[],ElemType n);extern Status DestroyList(SqList &L);extern Status ClearList(SqList &L);extern Status ListEmpty(SqList L);extern Status ListLength(SqList L);extern Status GetElem(SqList L,ElemType i,ElemType &e);extern Status LocateElem(SqList L,ElemType e);extern Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e);extern Status NextElem(SqList L,ElemType cur_e,ElemType &next_e);extern Status ListInsert(SqList &L,ElemType i,ElemType e);extern Status ListDelete(SqList &L,ElemType i); extern Status TraverseList(SqList L); #endif //如果已经定义了则编译#endif后面的语句

ii)功能函数(function2.cpp)

#include#include#include "com_h2.H"/*初始化*/ Status InitList(SqList &L){L.elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType)); //创建MAXSIZE大小的空间if(!L.elem)return OVERFLOW; L.length=0; return OK; }/*赋值*/ Status EstablishList(SqList &L,ElemType a[],ElemType n){L.elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType)); //创建MAXSIZE大小的空间if(!L.elem)return OVERFLOW;L.length=n;for(int i=0;iL.length||i<1) return ERROR;e=L.elem[i-1];return OK; }/*查找*//*返回L中第1个值与e相同的位置*/Status LocateElem(SqList L,ElemType e){for(int i=0;i<L.length;i++){if(L.elem[i]==e)return i+1; }return ERROR;} /*求前驱*//*返回顺序表中cur_e的前驱元素pre_e*/Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e){for(int i=1;i<L.length;i++){if(L.elem[i]==cur_e){pre_e=L.elem[i-1];return OK;}}return ERROR;}/*求后继*//*返回顺序表中cur_e的后驱元素next_e*/Status NextElem(SqList L,ElemType cur_e,ElemType &next_e){for(int i=0;i<L.length-1;i++){if(L.elem[i]==cur_e){next_e=L.elem[i+1];return OK;}}return ERROR;} /*插入*//*在第i个前插入e插入的条件：1.i的范围为1—length+1. length<maxsize */Status ListInsert(SqList &L,ElemType i,ElemType e){if(iL.length+1||L.length==MAXSIZE)return ERROR;for(int j=L.length;j>i-1;j--)L.elem[j]=L.elem[j-1];L.elem[i-1]=e;L.length++;return OK;} /*删除*//*删除第i个位置的值删除的条件：i的范围是1-length */Status ListDelete(SqList &L,ElemType i){if(iL.length)return ERROR;for(int j=i-1;j<L.length-1;j++)L.elem[j]=L.elem[j+1];L.length--;return OK;}/*遍历顺序表*/ Status TraverseList(SqList L){printf("顺序表为："); for(int i=0;i<L.length;i++)printf("%4d",L.elem[i]); }

iii）主函数（function2.cpp)

#include#include#include "com_h2.h"int main(int argc, char** argv) {SqList L;ElemType a[MAXSIZE],n,i,order1,order2,e;int cur_e,next_e,pre_e;printf("=======================菜单1========================\n");printf("1.初始化顺序表\n");printf("2.为顺序表赋值\n");printf("0.退出\n");printf("====================================================\n");do{printf("请输入你的选择："); scanf("%d",&order1);switch(order1){case 1:if(!InitList(L))printf("初始化失败！！！\n");elseprintf("初始化成功！！！\n");break;case 2:printf("请输入赋值的个数：");scanf("%d",&n);printf("请输入要赋值的元素值：\n");for(int i=0;i<n;i++)scanf("%d",&a[i]);if(!EstablishList(L,a,n))printf("赋值失败！！！\n");else{printf("创建成功！！！\n");TraverseList(L);printf("\n"); }break;case 0:printf("程序退出！！！\n");break;default:printf("输入的选择不合法！！！\n");}}while(order1!=0&&order1!=1&&order1!=2);do{printf("=========================菜单2==========================\n");printf(" 1.获得第i个位置的值2.查找e在顺序表的位置 \n");printf(" 3.在第i个位置插入e 4.删除第i个位置的值 \n");printf(" 5.求cur_e的前驱pre_e 6.求cur_e的后继next_e \n");printf(" 7.清空顺序表 8.求表长\n");printf(" 9.判断顺序表是否为空 10.遍历顺序表 \n");printf(" 0.退出程序 \n"); printf("========================================================\n"); printf("请输入你的选择：");scanf("%d",&order2);switch(order2){case 1:printf("请输入你要查找的位置i:");scanf("%d",&i);if(!GetElem(L,i,e))printf("i输入错误！！！\n");elseprintf("第%d个位置的值为%d\n",i,e);break;case 2:printf("请输入你要查找的e的值：");scanf("%d",&e);if(!LocateElem(L,e))printf("%d不存在于此顺序表中！！！\n",e);elseprintf("%d在此顺序表的第%d个位置上\n",e,LocateElem(L,e));break;case 3:printf("请输入i和e的值（格式：i,e):");scanf("%d,%d",&i,&e);if(!ListInsert(L,i,e))printf("i输入错误！！！\n");else{printf("插入成功！！！\n");TraverseList(L);printf("\n");}break;case 4:printf("请输入要删除的位置i:");scanf("%d",&i);if(!ListDelete(L,i))printf("删除失败！！！\n");else{printf("删除成功！！！\n");TraverseList(L);printf("\n");}break;case 5:printf("请输入需要求前驱的元素cur_e:");scanf("%d",&cur_e);if(!PriorElem(L,cur_e,pre_e))printf("%d不存在前驱！！！\n",cur_e);elseprintf("%d的前驱为%d\n",cur_e,pre_e);break;case 6:printf("请输入需要求后继的元素cur_e:");scanf("%d",&cur_e);if(! NextElem(L,cur_e,next_e))printf("%d不存在后继！！！\n",cur_e);elseprintf("%d的后继为%d\n",cur_e,next_e);break;case 7:ClearList(L);printf("清空成功！！！\n");printf("顺序表的长度为%d\n",L.length);break;case 8:printf("此顺序表的表长为：%d\n",ListLength(L));break;case 9:if(!ListEmpty(L))printf("该顺序表不为空！！！\n");elseprintf("该顺序表为空！！！\n");break;case 10:TraverseList(L);printf("\n");break;case 0:printf("程序退出！！！\n");break;default:printf("输入不合法！！!\n");} }while(order2!=0);DestroyList(L);return 0;}