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");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;
}