作者在 2011-10-09 13:38:16 发布以下内容
#define MAXSIZE 100
#define ERROR 0
#include<iostream>
#include<cstdio>
using namespace std;
typedef int ElemType;
typedef struct {
ElemType elem[MAXSIZE];
int length;
}SqList;
void InitList(SqList &L)//初始化操作，将线性表置空
{
L.length = 0;
}
void CreatList(SqList &L,int n)//建立一个顺序存储的线性表
{
int i;
for(i = 0;i < n; i++)
scanf("%d",&L.elem[i]);
L.length = n;
fflush(stdin);
}
void Output(SqList L)//输出线性表L
{
int i;
for(i = 0;i < L.length;i++)
printf("%d ",L.elem[i]);
printf("\n");
}
int IsEmpty(SqList L)//判断表是否为空，为空返回1
{
if(L.length == 0)
return 1;
else
return 0;
}
int Compare(SqList L1,SqList L2) //比较两个顺序表的大小
{
// 若 A<B，则返回 -1；若 A=B，则返回 0；若 A>B，则返回 1
int i = 0;
while(i<L1.length && i<L2.length)
{
if(L1.elem[i] > L2.elem[i])
return 1;
else if(L1.elem[i] < L2.elem[i])
return -1;
else i++;
}
if ( L1.length == L2.length )
return 0;
else if(L1.length < L2.length)
return -1;
else
return 1;
}
int Inversion(SqList &L)//将一个顺序表逆置
{
int i,temp;
for(i=0;i<L.length/2;i++)
{
temp = L.elem[i];
L.elem[i] = L.elem[L.length-i-1];
L.elem[L.length-i-1] = temp;
}
return 1;
}
int GetElem(SqList L,int i) //取表中第i元素
{
if(i < 0||i >= L.length)
return ERROR;
else
return L.elem[i];
}
int LocateElem(SqList L,ElemType x)
//定位函数，返回L中与第一个与x相等的数据元素的位置（从1算起），否则返回值为0
{
int k = 0;
while(k <= L.length && L.elem[k] != x)
k++;
if(k <= L.length)
return ++k;
else
return -1;
}
int ListInsert(SqList &L,ElemType x,int i)
//在线性表L中第i个数据元素之前插入一个数据元素x
{
int k;
if(i < 0 || i > L.length || L.length == MAXSIZE)
return 0;
else
{
for(k = L.length;k >= i;k--)
L.elem[k] = L.elem[k-1];
L.elem[i] = x;
L.length = L.length + 1;
}
return 1;
}
int Delete(SqList &L,int i)//删除线性表L中第i（0 <= i < L.length）个数据元素
{
int k;
if(i < 0 || i >= L.length)//下标越界
return 0;
else//移动后面的元素
{
for(k = i;k < L.length;k++)
L.elem[k] = L.elem[k + 1];
L.length--;
}
return 1;
}
void Clear(SqList &L)//清空线性表L
{
InitList(L);
}
void MergeList(SqList &la,SqList &lb,SqList &lc)//合并有序表la,lb到表lc中，使得表lc依然有序
{
int i,j,k;
i = j = k = 0;
while(i < la.length && j < la.length)//la和lb均不空
if(la.elem[i] < lb.elem[j])
lc.elem[k++] = la.elem[i++];
else if(la.elem[i] > lb.elem[j])
lc.elem[k++] = lb.elem[j++];
else //la和lb中的当前元素相等时，同时移动指针
{
lc.elem[k++] = lb.elem[j++];
++i;
}
while(i < la.length)//la非空，lb已空
lc.elem[k++] = la.elem[i++];
while(j < lb.length)//la已空，lb非空
lc.elem[k++] = lb.elem[j++];
lc.length = k;
}
int SortInc(SqList &L)//对顺序表数据元素按升序排列
{
//用冒泡法排序
int temp;
for(int i = 0;i < L.length - 1;i++)
for(int j = i;j < L.length;j++)
{
if(L.elem[i] > L.elem[j])
{
temp = L.elem[i];
L.elem[i] = L.elem[j];
L.elem[j] = temp;
}
}
return 0;
}
int SortDec(SqList &L)//对顺序表数据元素按降序排列
{
//用冒泡法排序
int temp;
for(int i = L.length - 1;i > 0;i--)
for(int j = i;j >= 0 ;j--)
{
if(L.elem[i] > L.elem[j])
{
temp = L.elem[i];
L.elem[i] = L.elem[j];
L.elem[j] = temp;
}
}
return 0;
}
void output()
{
int i;
for(i = 0;i < 10;i ++)
printf(" ");
for(i = 0;i < 32;i ++)
printf("*");
printf("\n");
}
void mainpp()//显示窗口
{
int i;
output();
for(i = 0;i < 10;i ++)
printf(" ");
printf("* ");
printf("1.建立一个顺序表");
for(i = 0;i < 10;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i ++)
printf(" ");
printf("* ");
printf("2.输出一个顺序表");
for(i = 0;i < 10;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i ++)
printf(" ");
printf("* ");
printf("3.在顺序表中查找");
for(i = 0;i < 10;i ++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i ++)
printf(" ");
printf("* ");
printf("4.向顺序表中插入一个元素");
for(i = 0;i < 2;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i ++)
printf(" ");
printf("* ");
printf("5.删除顺序表中的一个元素");
for(i = 0;i < 2;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i++)
printf(" ");
printf("* ");
printf("6.从顺序表中取出一个元素");
for(i = 0;i < 2;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i++)
printf(" ");
printf("* ");
printf("7.将两个顺序表合并");
for(i = 0;i < 8;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i++)
printf(" ");
printf("* ");
printf("8.比较两个顺序表的大小");
for(i = 0;i < 4;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i++)
printf(" ");
printf("* ");
printf("9.将顺序表逆置");
for(i = 0;i < 12;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i++)
printf(" ");
printf("* ");
printf("10.将顺序表中升序排序");
for(i = 0;i < 5;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i++)
printf(" ");
printf("* ");
printf("11.将顺序表中降序排序");
for(i = 0;i < 5;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i++)
printf(" ");
printf("* ");
printf("12.判断顺序表中是否为空");
for(i = 0;i < 3;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i++)
printf(" ");
printf("* ");
printf("0.退 出 ");
for(i = 0;i < 8;i++)
printf(" ");
printf("*");
printf("\n");
output();
}
int main()//主函数
{
int n,i,k = 1,m,p,q,x;
SqList l,la,lc;
InitList(l);
mainpp();
while(k)
{
printf("请选择0--12：");
scanf("%d",&m);
getchar();
switch(m)
{
case 0:exit(0);
case 1:{
printf("请输入顺序表元素的个数:\n");
printf("输入元素值，构建顺序表:\n");
scanf("%d",&n);
CreatList(l,n);
Output(l);
break;
}
case 2:Output(l);printf("\n");break;
case 3:{
printf("请输入要查找的元素值：");
scanf("%d",&x);
k = LocateElem(l,x);
printf("要查找的元素的定位：%d\n",k);
printf("\n");
break;
}
case 4:{
printf("请输入要插入的元素的位置及其值：");
fflush(stdin);
scanf("%d",&i);
scanf("%d",&x);
ListInsert(l,x,i);
Output(l);
printf("\n");
break;
}
case 5:{
printf("请输入要删除元素的位置：");
fflush(stdin);
scanf("%d",&i);
Delete(l,i);
Output(l);
printf("\n");
break;
}
case 6:{
printf("请输入要取出的元素的序号：");
fflush(stdin);
scanf("%d",&i);
k = GetElem(l,i);
printf("取出的第%d个元素为：%d\n",i,k);
break;
}
case 7:{
InitList(la);
InitList(lc);
printf("请输入第2个顺序表元素的个数： \n");
printf("输入元素值，构建顺序表:\n");
scanf("%d",&m);
CreatList(la,m);
printf("\n新建的顺序表为:\n");
Output(la);
MergeList(l,la,lc);
printf("输出合并后的顺序表中的元素：\n");
Output(lc);
break;
}
case 8:{
InitList(la);
printf("请输入第2个顺序表元素的个数： \n");
printf("输入元素值，构建顺序表:\n");
scanf("%d",&m);
CreatList(la,m);
printf("\n新建的顺序表为:\n");
Output(la);
p = Compare(l,la);
if(p == 1)
printf("l > la");
else if(p == -1)
printf("l < la");
else
printf("l == la");
break;
}
case 9:{
Inversion(l);
Output(l);
printf("\n");
break;
}
case 10:{
SortInc(l);
Output(l);
printf("\n");
break;
}
case 11:{
SortDec(l);
Output(l);
printf("\n");
break;
}
case 12:{
q = IsEmpty(l);
if(q == 1)
printf("此表为空");
else
printf("此表不空");
printf("\n");
break;
}
default :exit(0);
}
printf("继续运行吗？Y（1）/N（0）：");
scanf("%d",&k);
if(!k)
exit(0);
}
return 0;
}