作者在 2011-10-09 13:39:43 发布以下内容
//线性表的顺序表示指的是:用一组地址连续的存储单元依次存储线性表的数据元素.
//只要确定了存储线性表的起始位置,线性表中任一数据元素都可随机存取,
//所以线性表的顺序表存储结构是一种随机存取的存储结构.
#define OVERFLOW -1
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define NULL 0
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
#include<iostream>
#include<cstdio>
using namespace std;
typedef int Status;
typedef int ElemType;
//-----线性表的动态分配顺序存储结构-----
typedef struct
{
ElemType *elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;
//1.初始化空表
Status InitList_Sq(SqList &L)
{
//构造一个空的线性表L
L.elem = (ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType));
if(! L.elem)
exit(OVERFLOW); //存储分配失败
L.length = 0; //空表长度为0
L.listsize = LIST_INIT_SIZE; //初始存储容量
return OK;
}//InitList_Sq
//2.建立顺序表L
Status CreatList_Sq(SqList &L,int n)
{
int i;
ElemType e;
cout << "输入顺序表的长度:";
cin >> n;
L.length = n;
if (L.length > LIST_INIT_SIZE)
L.elem = (ElemType *) realloc(L.elem,L.length*sizeof(ElemType));
cout<<"输入数据:";
for(i = 0;i <= L.length-1;i++)
{
scanf("%d",&e);
L.elem[i] = e;
}
return OK;
}
//3.销毁线性表
Status DestoryList_Sq(SqList &L)
{
//销毁线性表L
if (L.elem)
{
free(L.elem);
L.elem = NULL;
L.length = L.listsize = 0;
return OK;
}
return ERROR;
}
//4.重置空表
Status ClearList_Sq(SqList &L)
{//将L重置为空表
L.length = 0;
cout << "Success!" <<endl;
return OK;
}
//5.判定是否空表
Status ListEmpty_Sq(SqList L)
{//判定是否空表,若L为空表,则返回TRUE,否则返回FALSE
if (L.length)
return ERROR;
return OK;
}
//6.求表长
int ListLength_Sq(SqList L)
{ //求L中数据元素的个数
return L.length;
}
//7.取表第i个元素
Status GetElem_Sq(SqList L, int i, ElemType &e)
{ //用e返回顺序表L中第i个数据元素的值
//i的合法值为1 <= i <= ListLength_Sq(L)
if ((i < 1)||(i > L.length))
return ERROR; //i值不合法
else
e = L.elem[i-1];
return OK;
}
//8.顺序表查找
int LocateElem_Sq(SqList L,ElemType e)
{ //在顺序线性表L中查找第1个值与e相等的元素的位序
//若找到,则返回其在L中的位序,否则返回0
int i = 1;
ElemType *p; //i的初值位第1个元素的位序
p = L.elem; //p的初值位第1个元素的存储位置
while (i <= L.length && L.elem[i] != e)
i++;
if (i <= L.length)
return (i);
else
return 0;
}//LocateElem_Sq
//9.求表L中元素的前驱
Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType &pre_e)
{ //求表L中cur_e元素的前驱,用pre_e返回
int i;
cout << "输入特定元素值:";
cin >> cur_e;
i = LocateElem_Sq(L,cur_e);
if (i <= 1)
return ERROR; //i值不合法
pre_e = L.elem[i-1];
cout << pre_e << endl;
return OK;
}
//10.求表L中元素的后继
Status NextElem_Sq(SqList L, ElemType cur_e, ElemType &next_e)
{ //求表L中cur_e元素的后继,用next_e返回
int i;
cout<<"输入特定元素值:";
cin>>cur_e;
i=LocateElem_Sq(L,cur_e);
if (i>=L.length)
return ERROR; //i值不合法
next_e=L.elem[i + 1];
cout<<next_e << endl;
return OK;
}
//11.插入结点
Status ListInsert_Sq(SqList &L, int i, ElemType e)
{ //在顺序线性表L中第i个位置之前插入新的元素e
ElemType *q,*p,*newbase; //i的合法值为1<=i<=ListLength_Sq(L)+1
if(i < 1 || i > L.length+1)
return ERROR; //i值不合法
if (L.length >= L.listsize)
{
//当前存储空间已满,增加分配
newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if (!newbase) exit(OVERFLOW); //存储分配失败
L.elem = newbase; //新基址
L.listsize += LISTINCREMENT; //增加存储容量
}
q = &(L.elem[i-1]); //q为插入位置
for (p = &(L.elem[L.length - 1]);p >= q;--p)
*(p+1) = *p; //插入位置及之后的元素后移
*q = e; //插入e
++L.length; //表长增1
return OK;
}//ListInsert_Sq
//12.删除结点
Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{ //在顺序线性表L中删除第i个元素,并用e返回其值
ElemType *p,*q;
//i的合法值为1 <= i <= ListLength_Sq(L)
if((i < 1) || (i > L.length))
return ERROR; //i值不合法
p = &(L.elem[i - 1]); //p为被删除元素的位置
e = *p; //被删除元素的值赋给e
q = L.elem + L.length - 1; //表尾元素的位置
for (++p;p <= q;++p)
*(p-1) = *p; //被删除元素之后的元素左移
--L.length; //表长减1
return OK;
}//ListDelete_Sq
//13.表遍历
Status ListTraverse(SqList L,Status(* visit)(ElemType e))
{ //遍历表. 依次对L的每个数据元素调用函数visit().一旦visit()失败,则操作失败.
int i;
for (i = 0;i <= L.length - 1;i++)
{
(* visit)(L.elem[i]);
cout<<" ";
}
cout<<endl;
return OK;
}
//14.归并顺序表
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc)
{ //已知顺序线性表La和Lb的元素按值非递减排列
//归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列
ElemType *pa,*pb,*pc,*pa_last,*pb_last;
pa = La.elem;
pb = Lb.elem;
Lc.listsize = Lc.length = La.length + Lb.length;
pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType));
if (!Lc.elem)
exit(OVERFLOW); //存储分配失败
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
while (pa <= pa_last && pb <= pb_last)
{//归并
if (pa <= pb)
*pc++ = *pa++;
else
*pc++ = *pb++;
}
while (pa <= pa_last)
*pc++ = *pa++; //插入La的剩余元素
while (pb <= pb_last)
*pc++ = *pb++; //插入Lb的剩余元素
}//MergeList_Sq
//15.输出顺序表
void Output(SqList L)//输出线性表L
{
int i;
for(i = 0;i < L.length;i++)
printf("%d ",L.elem[i]);
printf("\n");
}
//16.对顺序表数据元素按升序排列
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;
}
//17.对顺序表数据元素按降序排列
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;
}
//18.将一个顺序表逆置
int Inversion_Sq(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;
}
void output()//窗口边框
{
int i;
for(i = 0;i < 10;i ++)
printf(" ");
for(i = 0;i < 31;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("13.求表L中元素的前驱");
for(i = 0;i < 6;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i++)
printf(" ");
printf("* ");
printf("14.求表L中元素的后驱");
for(i = 0;i < 6;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i++)
printf(" ");
printf("* ");
printf("15.销毁线性表");
for(i = 0;i < 13;i++)
printf(" ");
printf("*");
printf("\n");
for(i = 0;i < 10;i++)
printf(" ");
printf("* ");
printf("16.重置顺序表");
for(i = 0;i < 13;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 = 0,i,j = 0,k = 1,m,p,q,x,y,e,cur_e = 0,pre_e = 0,next_e;
SqList l,la,lc;
InitList_Sq(l);
mainpp();
while(k)
{
printf("请选择0--16：");
scanf("%d",&m);
getchar();
switch(m)
{
case 0:exit(0);
case 1:{
CreatList_Sq(l,n);
Output(l);
break;
}
case 2:Output(l);printf("\n");break;
case 3:{
printf("请输入要查找的元素值：");
scanf("%d",&x);
j = LocateElem_Sq(l,x) + 1;
printf("要查找的元素的位序：%d\n",j);
printf("\n");
break;
}
case 4:{
printf("请输入要插入的元素的位置及其值：");
fflush(stdin);
scanf("%d",&i);
scanf("%d",&x);
ListInsert_Sq(l,i,x);
Output(l);
printf("\n");
break;
}
case 5:{
printf("请输入要删除元素的位置：");
fflush(stdin);
scanf("%d",&i);
ListDelete_Sq(l,i,y);
Output(l);
printf("\n");
break;
}
case 6:{
printf("请输入要取出的元素的序号：");
fflush(stdin);
scanf("%d",&i);
GetElem_Sq(l,i,e);
printf("取出的第%d个元素为：%d\n",i,e);
break;
}
case 7:{
InitList_Sq(la);
InitList_Sq(lc);
printf("请输入第2个顺序表元素的个数： \n");
printf("输入元素值，构建顺序表:\n");
scanf("%d",&m);
CreatList_Sq(la,m);
printf("\n新建的顺序表为:\n");
Output(la);
MergeList_Sq(l,la,lc);
printf("输出合并后的顺序表中的元素：\n");
Output(lc);
break;
}
case 8:{
InitList_Sq(la);
printf("请输入第2个顺序表元素的个数： \n");
printf("输入元素值，构建顺序表:\n");
scanf("%d",&m);
CreatList_Sq(la,m);
printf("\n新建的顺序表为:\n");
Output(la);
if(p == 1)
printf("l > la");
else if(p == -1)
printf("l < la");
else
printf("l == la");
break;
}
case 9:{
Inversion_Sq(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 = ListEmpty_Sq(l);
if(q == 1)
printf("此表为空");
else
printf("此表不空");
printf("\n");
break;
}
case 13:
{
PriorElem_Sq(l,cur_e,pre_e);
break;
}
case 14:
{
NextElem_Sq(l,cur_e,next_e);
break;
}
case 15:
{
DestoryList_Sq(l);
break;
}
case 16:
{
ClearList_Sq(l);
break;
}
default :exit(0);
}
printf("继续运行吗？Y（1）/N（0）：");
scanf("%d",&k);
if(!k)
exit(0);
}
return 0;
}