definition.h
=============================
#define INITSIZE 100 //顺序表初始空间分配量
#define INCREMENT 10 //顺序表空间分配增量
typedef char ElemType; //定义ElemType代表的数据类型
unsigned short listlen; //全局变量，用于记录目前一共有多少个顺序表
//定义顺序表结构
typedef struct{
ElemType *elem; //存储空间基址
unsigned int length; //当前长度
unsigned int listsize; //当前空间分配量
unsigned int e; //用于记录元素编号
}Sqlist;
short Menu(); //打印菜单，请用户选择
short InitList(Sqlist *); //创建顺序表
short InputList(Sqlist *); //插入数据
short DelList(Sqlist *); //删除数据
short Union(Sqlist *); //求顺序表并集
short Purge(Sqlist *); //删除表中重复元素
short Purge2(Sqlist *); //删除表中重复元素
short Bubble(Sqlist *); //冒泡排序
short Compare(Sqlist *); //比较两个顺序表的大小
short Exchange(Sqlist *); //前N个元素和后M个元素互换
short Location(Sqlist *, ElemType); //求元素位置
void Disp(Sqlist *); //显示顺序表信息
void Three(Sqlist *, unsigned, unsigned); //三次逆转法
short Realloc(Sqlist *); //增加空间
====================================================
main.c
===========================
#include
#include
#include"definition.h"
int main()
{ Sqlist L[10]; //最多可以建立10个顺序表
unsigned int i;
unsigned short choice; //记录用户选择的操作
short (*option[])(Sqlist *)={InitList, InputList, DelList, Union, Purge, Bubble, Compare, Exchange, Purge2}; //定义函数指针
listlen=0;//初始化顺序表数目
printf("请输入1创建一个顺序表。最多可以创建10个顺序表\n");
while( (choice=Menu())!='q'-49 ){//根据用户输入选择函数运行
i=0;
if(choice==0)
InitList(&L[listlen]); //插入数据
else if(choice==3)
Union(L); //合并顺序表
else if(choice==6)
Compare(L); //比较顺序表
else{
while(i>listlen || i printf("请问您要对哪个顺序表（1 — %d）进行操作：", listlen);
scanf("%d", &i);
} getchar();//用于接收多余的字符'\n'
option[choice](&L[i-1]);
}
//打印顺序表的内容
Disp(L);
}
for(i=0; i free(L[i].elem); //释放内存
return 0; //退出程序
} ===================================================
functions.c
=========================
#include
#include
#include
#include
#include"definition.h"
short Menu() //打印菜单，并且接受用户输入的操作
{ char ch='0';
do{
if( strchr("23456789", ch) )
printf("您还没有建立顺序表呢，请输入1建立一个顺序表。\n");
printf("\n");
printf("********************************\n");
printf("*** 请选择您要进行的操作 ***\n");
printf("********************************\n");
printf("* 1. 创建顺序表 *\n");
printf("* 2. 插入数据 *\n");
printf("* 3. 删除数据 *\n");
printf("* 4. 求顺序表并集 *\n");
printf("* 5. 删除重复元素 *\n");
printf("* 6. 冒泡排序 *\n");
printf("* 7. 比较顺序表大小 *\n");
printf("* 8. 前N个元素和后M个元素互换 *\n");
printf("* 9. 删除重复元素(2) *\n");
printf("* q. 退出 *\n");
printf("********************************\n");
printf("\n");
ch=getch();//getch()并不在屏幕上输出
}while( !strchr("123456789q", ch) || (listlen==0 && strchr("23456789", ch)) );//如果在ch不存在于""之间，则循环请用户输入操作号
return ch-49;//返回操作号
}
short InitList(Sqlist *L)//创建顺序表
{ if(listlen==10){ //当前已经有了10个顺序表
printf("最多只能创建10个顺序表。\n");
return 0;
}
L->elem=(ElemType *)malloc(INITSIZE*sizeof(ElemType));//分配空间
if(!L->elem){
printf("Not Enough Memory!\n");
return 1;//创建失败返回1
}
//创建成功，初始化顺序表长度和字符串长度
L->length=0;
L->listsize=INITSIZE;
L->e=0; //初始化元素编号
listlen++; //更新顺序表数目
printf("顺序表创建成功！您可以开始对顺序表进行操作了。\n");
return 0;//创建成功返回0
}
short InputList(Sqlist *L)//接受用户输入的字符串
{ unsigned int i;
ElemType temp; //用于暂时存储用户输入的字符
if(L->length){ //如果顺序表中存在数据
L->e=L->length+1;
while(L->e > L->length || L->e < 0){//如果用户输入不合法，则循环请用户输入
printf("请输入插入位置（0 — %d），0代表插入到最后：", L->length);
scanf("%d", &L->e);
} getchar();//用于接收多余的字符'\n'
} printf("请输入字符串：");
if(!L->e){//如果顺序表中不存在数据，或者用户前面输入为0
L->e=L->length;//从第length个位置开始插入字符。如果顺序表中不存在数据，此时length等于0
for(; ( L->elem[L->e]=getchar() )!='\n'; L->e++){//循环插入数据
L->length++;
if(L->length==L->listsize){//如果顺序表已满
if( Realloc(L) ) //增加空间
return 1;//增加空间失败，退出
} }
} else{//如果顺序表不空，而且用户前面输入不是0
L->e--;
for(; (temp=getchar())!='\n'; L->e++, L->length++){//从第e个位置开始，循环插入数据
if(L->length==L->listsize){//如果顺序表已满
if( Realloc(L) ) //增加空间
return 1;//增加空间失败，退出
}
i=L->length;
for(; i > L->e; i--){
L->elem[i]=L->elem[i-1];//将第e个位置开始的元素都向后移动一个位置
} L->elem[L->e]=temp;//将用户输入的字符插入第e个位置
} }
return 0;//返回
}
short DelList(Sqlist *L)
{ unsigned int i, j;
if(!L->length){ //如果顺序表中没有数据，退出
printf("\n该顺序表里没有数据。\n");
return 1;
}
//如果顺序表中存在数据
L->e=L->length+1;
while(L->e > L->length || L->e < 1){//如果用户输入不合法，则循环请用户输入
printf("请输入删除位置（1 — %d）：", L->length);
scanf("%d", &L->e);
} i=L->length+1;
j=L->length - L->e + 1;
while( ij ){//如果用户输入不合法，则循环请用户输入
printf("请输入删除数目（1 — %d）：", j );
scanf("%d", &i);
} getchar();//用于接收多余的字符'\n'
//开始删除数据
if(i==j)
; else
for( j=i+(--L->e); jlength; L->e++, j++ ){
L->elem[L->e]=L->elem[j];
} L->length-=i;//更新字符串长度
return 0;//返回
}
short Union(Sqlist *L){ //求顺序表并集
unsigned short i=0, j=0;
unsigned k;
if(listlen printf("至少要有两个顺序表才能进行并集操作，请再建立一个顺序表。\n");
return 1;
}
while( ilistlen||i==j){//如果用户输入不合法，则循环请用户输入
printf("\n请输入您想要进行并集操作的两个顺序表，两个数字之间用空格隔开（1 — %d）：", listlen);
scanf("%d %d", &i, &j);
}
//开始进行并集操作
for(i--, j--, k=0; k if( !Location(&L[i], L[j].elem[k]) ){//在顺序表i中找不到顺序表j中的第k+1个元素，将第k+1个元素插入顺序表i
if(L[i].length==L[i].listsize){ //如果顺序表已满
if( Realloc(&L[i]) ){ //增加空间
printf("\n没有足够的内存用于完成并集操作。\n");
return 1;//增加空间失败，退出
} }
L[i].elem[L[i].length]=L[j].elem[k];//插入到表i
L[i].length++;//表i长度增加
} }
printf("\n并集操作完成。操作结果保存于顺序表 %d 。\n", ++i);
return 0;//无误返回
}
short Purge(Sqlist *L) //删除表中重复元素
{ unsigned i, j, k;
for(i=0; ilength; i++){
for(j=i+1; jlength;){
if(L->elem[i]==L->elem[j]){//若找到重复元素
for(k=j; klength; k++)//删除重复元素
L->elem[k]=L->elem[k+1];
L->length--;//顺序表长度减1
} else
j++;
} }
printf("\n重复数据已经删除完毕。\n");
return 0;
}
short Purge2(Sqlist *L) //删除表中重复元素
{ Sqlist T=*L;
unsigned i;
T.length=1;
for(i=1; ilength; i++){
if( !Location(&T, L->elem[i]) ){//若找不到重复元素
T.elem[T.length]=L->elem[i];//插入
T.length++;//更新长度
} }
L->length=T.length;//更新长度
printf("\n重复数据已经删除完毕。");
return 0;
}
short Bubble(Sqlist *L)
{ char ch='2';
ElemType temp;
unsigned i, j, k=L->length-1;
unsigned short l;
while( !strchr("01", ch) ){//如果用户输入不合法，则循环请用户输入
printf("\n请问您要进行降序排序还是升序排序？0代表降序，1代表升序。\n");
ch=getch();
}
if(ch=='0'){
for(l=1; l; k--){
l=0;
for(i=0, j=1; i if(L->elem[i] < L->elem[j]){
temp=L->elem[i];
L->elem[i]=L->elem[j];
L->elem[j]=temp;
l=1;
} }
} }
else{
for(l=1; l; k--){
l=0;
for(i=0, j=1; i if(L->elem[i] > L->elem[j]){
temp=L->elem[i];
L->elem[i]=L->elem[j];
L->elem[j]=temp;
l=1;
} }
} }
printf("\n排序完成。\n");
return 0;
}
short Compare(Sqlist *L)//比较两个顺序表
{ unsigned short i=0, j=0;
unsigned k;
if(listlen printf("至少要有两个顺序表才能进行比较，请再建立一个顺序表。\n");
return 1;
}
while( ilistlen||i==j){//如果用户输入不合法，则循环请用户输入
printf("\n请输入您想要比较的两个顺序表，两个数字之间用空格隔开（1 — %d）：", listlen);
scanf("%d %d", &i, &j);
}
//开始进行比较
for(i--, j--, k=0; k if(L[i].elem[k] > L[j].elem[k]){
printf("\n顺序表 %d 比顺序表 %d 大。\n", ++i, ++j);
return 1;
} if(L[i].elem[k] < L[j].elem[k]){
printf("\n顺序表 %d 比顺序表 %d 大。\n", ++j, ++i);
return 2;
} }
if(L[i].length > L[j].length){
printf("\n顺序表 %d 比顺序表 %d 大。\n", ++i, ++j);
return 1;
} if(L[i].length < L[j].length){
printf("\n顺序表 %d 比顺序表 %d 大。\n", ++j, ++i);
return 2;
}
printf("\n两表相等。\n");
return 0;//相等返回0
}
short Exchange(Sqlist *L) //前N个元素和后M个元素互换
{ unsigned i=0;
while(i=L->length){//如果用户输入不合法，则循环请用户输入
printf("\n请输如互换点（1 — %d）：", L->length-1);
scanf("%d", &i);
}
//三次逆转
Three(L, 0, i-1);
Three(L, i, L->length-1);
Three(L, 0, L->length-1);
printf("\n互换完成。\n");
return 0;
}
void Three(Sqlist *L, unsigned i, unsigned j)//三次逆转法
{ ElemType temp;
for(; i temp=L->elem[i];
L->elem[i]=L->elem[j];
L->elem[j]=temp;
} }
short Location(Sqlist *L, ElemType elem)//求元素位置
{ unsigned l;
for(l=0; l < L->length && L->elem[l]!=elem; l++)
; if(l==L->length)//在顺序表中找不到elem
return 0; //返回0
return ++l;//找到则返回元素位置
}
short Realloc(Sqlist *L)//增加空间
{ ElemType *newbase;
newbase=(ElemType *)realloc(L->elem, (L->listsize+INCREMENT)*sizeof(ElemType) );//增加空间
if(!newbase){//如果分配失败
printf("Not Enough Memory!\n");
return 1;//返回1
} //如果分配成功
L->elem=newbase;//将指针指向新分配好的空间
L->listsize+=INCREMENT;//增大listsize的值
return 0;//返回
}
void Disp(Sqlist *L) //显示顺序表信息
{ unsigned short i;
unsigned j;
printf("\n当前一共有 %d 个顺序表。每个表的数据如下：\n", listlen);
for(i=0; i printf("\n顺序表 %d ：", i+1);
for(j=0; j printf("%c", L[i].elem[j]);
printf("\n字符串长度：%d 顺序表长度：%d", L[i].length, L[i].listsize);
printf("\n");
} }
