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<stdio.h>
#include<stdlib.h>
#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;i<n;i++)
L.elem[i]=a[i];
return OK;
}
/*销毁*/
Status DestroyList(SqList &L){
free(L.elem);
L.length=0;
return OK;
}
/*清空*/
Status ClearList(SqList &L){
L.length=0;
return OK;
}
/*判断是否为空表*/
//c语言中除0以外均为真
Status ListEmpty(SqList L){
if(L.length==0)
return OK;
return ERROR;
}
/*返回数据元素个数*/
Status ListLength(SqList L){
return L.length;
}
/*取值*/
/*用e返回L中的第i个元素*/
Status GetElem(SqList L,ElemType i,ElemType &e){
if(i>L.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(i<1||i>L.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(i<1||i>L.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<stdio.h>
#include<stdlib.h>
#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");
else
printf("初始化成功！！！\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");
else
printf("第%d个位置的值为%d\n",i,e);
break;
case 2:
printf("请输入你要查找的e的值：");
scanf("%d",&e);
if(!LocateElem(L,e))
printf("%d不存在于此顺序表中！！！\n",e);
else
printf("%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);
else
printf("%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);
else
printf("%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");
else
printf("该顺序表为空！！！\n");
break;
case 10:
TraverseList(L);
printf("\n");
break;
case 0:
printf("程序退出！！！\n");
break;
default:
printf("输入不合法！！!\n");
}
}while(order2!=0);
DestroyList(L);
return 0;
}3)运行结果（DEV）
i)验证创建函数
?ii)验证取值和查找函数（菜单选择中的1和2）
?
?iii）验证插入和删除函数
iiii）验证前驱和后继函数
运行结果大概贴了一些，实在太多了，大家看看就好，可以自己试着运行一下。
4.总结?
? ? ? ?这个实验利用了引用调用代替指针，对我自己来说，更好理解和操作，其余的没有什么新的内容。总的来说，这次实验难度不大，但是代码比较多，还需注意输入不合理的处理，增强算法的健壮性。