关于数据结构——线性表一问题

Question

设有一个线性表 (e0, e1, …, en-2, en-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (en-1, en-2, …, e1, e0)。

会编写的请帮下忙哈

Answer 1

#include
#include
#include
#include
#include
#define OK 1
#define ERROR 0
#define list_init_size 100 //线性表存储空间的初始分配量
#define list_increament 10 //线性表存储空间的分配增量
typedef int elemtype;
struct node
{
elemtype * elem;
int length;
int listsize;
};
typedef struct node sqlist;
//初始化一个空的顺序表L，若初始化成功返回1，否则返回0。
int initlist_sq(sqlist *l,int n)
{
int i;
l->elem=(elemtype *)malloc(list_init_size*sizeof(elemtype));
if(!(l->elem))
{
printf("内存分配失败.\n");
return ERROR;
}
printf("请输入线性表中的元素:\n");
for(i=0;i<n;i++)
scanf("%d",&(l->elem[i]));
printf("\n");
l->length=n;
l->listsize=list_init_size;
return OK;
}
//打印线性表
void print_sq(sqlist *l)
{
int i,j=1;
for(i=0;ilength;i++)
{
printf("%4d",l->elem[i]);
j++;
if(j%10==0)
printf("\n");
}
printf("\n该线性表的长度是%d.\n",l->length);
printf("\n该线性表的最大容量是%d.\n",l->listsize);
}
//从线性表L中取第i个元素，并由e带出。若取元素成功则返回1，取元素不成功返回0。
int getelem_sq(sqlist *l,int i,elemtype *e)
{
if(i>0&&ilength)
{
*e=l->elem[i-1];
return OK;
}
else
{
printf("输入的位置有问题\n");
return ERROR;
}

}
//判断线性表L是否为空表，若是空表返回1，若不是空表返回0。
int listempty_sq(sqlist *l)
{
if(l->length>0)
{
printf("该线性表不为空.\n");
return ERROR;
}
else
{
printf("该线性表为空.\n");
return OK;
}
}
//清空一个线性表L，若清空成功返回1。
int clearlist_sq(sqlist *l)
{
l->length=0;
printf("该线性表已清空.\n");
return OK;
}
//在线性表L中找cure的前驱结点并由pre_e带出。
void priorelem_sq(sqlist *l,int cur_e,elemtype *pre_e)
{
int i;
int flag=0;
if(l->elem[0]==cur_e)
{
printf("第一个元素没有前驱结点.\n");
flag=1;
}
else
{
for(i=1;ilength;i++)
{
if(l->elem[i]==cur_e)
{
*pre_e=l->elem[i-1];
printf("该线性表中第%d个元素%d的前驱结点是%d\n",i+1,cur_e,*pre_e);
flag++;
}
else
continue;

}
}
if(flag==0)
printf("在该线性表中找不见元素%d\n",cur_e);
}
//在线性表L中找cure的后继结点，若有则由next_e带出。
void nextelem_sq(sqlist *l,int cur_e,elemtype *next_e)
{
int i;
int flag=0;
if(l->elem[l->length-1]==cur_e)
{
printf("最后一个元素没有后继结点.\n");
flag=1;
}
else
{
for(i=1;ilength;i++)
{
if(l->elem[i]==cur_e)
{
*next_e=l->elem[i+1];
printf("该线性表中第%d个元素%d的后继结点是%d\n",i+1,cur_e,*next_e);
flag++;
}
else
continue;

}
}
if(flag==0)
printf("在该线性表中找不见元素%d\n",cur_e);

}
//返回线性表的长度
int listlength_sq(sqlist *l)
{
return(l->length);
}
//在线性表L的第i个位置插入一个数据元素e。插入不成功返回0。
int listinsert_sq(sqlist *l,int i,elemtype e)
{
int j;
elemtype * newbase;
if(il->length+1)
{
printf("插入的位置错误\n");
return ERROR;
}
if(l->length>=l->listsize)
{
newbase=(elemtype *)realloc(l->elem,(l->listsize+list_increament)*sizeof(elemtype));
if(!newbase)
{
printf("内存在扩充时失败");
return ERROR;
}
l->elem=newbase;
l->listsize=l->listsize+list_increament;
}
for(j=l->length-1;j>=i-1;j--)
l->elem[j+1]=l->elem[j];
l->elem[i-1]=e;
l->length++;
return OK;

}
//删除线性表L中的第i个数据元素,并由e带出删除的元素，若删除不成功返回0。
int listdelete_sq(sqlist *l,int i,elemtype *e)
{
int j;
if(il->length)
{
printf("输入的位置有问题\n");
return ERROR;
}
*e=l->elem[i-1];
for(j=i;jlength-1;j++)
l->elem[j-1]=l->elem[j];
l->length--;
return OK;
}
//将现有的线性表置逆。
void convert_sq(sqlist *l)
{
int i,j,t;
for(i=0,j=l->length-1;i<j;i++,j--)
{
t=l->elem[i];
l->elem[i]=l->elem[j];
l->elem[j]=t;

}
}
//将非递减的有序表La和Lb归并为一个新的非递减的有序表Lc。
int mergelist_sq(sqlist *la,sqlist *lb,sqlist *lc)
{
elemtype *pa,*pb,*pc,*pa_last,*pb_last;
pa=la->elem;
pb=lb->elem;
pa_last=la->elem+la->length-1;
pb_last=lb->elem+lb->length-1;
lc->listsize=lc->length=la->length+lb->length;
lc->elem=(elemtype*)malloc((la->length+lb->length)*sizeof(elemtype));
pc=lc->elem;
while(pa<=pa_last&&pb<=pb_last)
{
if(*pa<*pb)
*pc++=*pa++;
else
*pc++=*pb++;
}
while(pa<=pa_last)
*pc++=*pa++;
while(pb<=pb_last)
*pc++=*pb++;
return OK;
}
//La和Lb中的元素分别表示两个集合A和B，求一个新的集合A=（A-B）∪(B-A)。
int unionl(sqlist *la,sqlist *lb)
{
int i,j;
elemtype *newbase;
if(la->length+lb->length>la->listsize)
newbase=(elemtype*)realloc(la->elem,(la->listsize+list_increament)*sizeof(elemtype));
if(!newbase)
{
printf("\na表的长度不够，且内存分配失败");
return ERROR;
}
for(i=1;ilength;i++)
{
for(j=1;jlength;j++)
if(lb->elem[i-1]==la->elem[j-1])
break;
else
continue;
if(j>la->length)
{
la->elem[j-1]=lb->elem[i-1];
la->length++;
}
}
return OK;
}
void deld_sq(sqlist *l)
{
int i,j,k;
elemtype s;
for(i=0;ilength-2;i++)
for(j=i+1;jlength-1;j++)
if(l->elem[i]==l->elem[j])
{
for(k=j;klength-2;k++)
l->elem[k]=l->elem[k+1];
l->length--;
j--;
}
for(i=0;ilength-2;i++)
for(j=i+1;jlength-1;j++)
if(l->elem[i]>l->elem[j])
{
s=l->elem[i];
l->elem[i]=l->elem[j];
l->elem[j]=s;
}
}
//在线性表L中查找与k相匹配的元素，返回在表中的位置。
void sqsearch(sqlist *l,int k)
{
int i;
int flag=0;
for(i=0;ilength-1;i++)
{
if(l->elem[i]==k)
{
printf("元素%d的位置是%d!\n",k,i+1);
flag++;
}
else
continue;
}
if(flag==0)
printf("线性表中不存在元素:%d!\n",k);
}
int cmp(int a,int b)
{
if(a>b)
return 1;
else
return 0;
}
//在线性表L中找第一个与e满足compare关系的元素的位序。
void locateelem_sq(sqlist *l,int e, int (*compare)(int a,int b))
{
int i=1;
int flag=0;
for(i=1;ilength;i++)
{
if(compare(l->elem[i-1],e))
{
printf("比%d大的元素的位序为:%d\n",e,i);
flag++;
}
else
continue;
}
if(flag==0)
printf("不存在比%d大的元素!\n",e);
}
void showmenu()
{
printf(" * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");
printf(" * 选择响应的操作 *\n");
printf(" * * * * * * * * * * * * * * * * * * * * * * * * * * * * * **\n");
printf(" * *\n");
printf(" * [0] 显 示 该 表 [99] 退 出 程 序 *\n");
printf(" * [1] 读 取 元 素 [ 2] 插 入 元 素 [ 3] 删 除 元 素 *\n");
printf(" * [ 4] 寻 找 前 驱 [ 5] 寻 找 后 继 [ 6] 返 回 表 长 *\n");
printf(" * [ 7] 置 逆 操 作 [ 8] 合 并 两 表 [ 9] 两 表 并 集 *\n");
printf(" * [10] 判 空 [11] 清 空 [12]有序无重复元素 *\n");
printf(" * [13] 顺 序 检 索 [14] 寻 找 位 序 *\n");
printf(" * *\n");
printf(" * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");
}
void main()
{
int n,m,i,k,cure,select;
elemtype e, pre_e, next_e;
sqlist l,r,la,lb,lc;
printf("请输入你要创建的线性表的长度:");
scanf("%d",&n);
printf("\n");
initlist_sq(&l,n);
printf("你创建的线性表如下:\n");
print_sq(&l);
while(1)
{
showmenu();
printf("请选择响应的操作:");
scanf("%d",&select);
switch(select)
{
case 99:exit(1);
case 0:print_sq(&l);
break;
case 1:
printf("请输入所取元素的位置:\n");
scanf("%d",&i);
if(getelem_sq(&l,i,&e)==1)
printf("线性表中第%d个元素为%d\n",i,e);
break;
case 2:
printf("请输入要插入的位置:\n");
scanf("%d",&i);
printf("请输入要插入的元素:\n");
scanf("%d",&cure);
listinsert_sq(&l,i,cure);
printf("插入操作完成后的线性表是:");
print_sq(&l);
break;
case 3:printf("你要删除哪一个元素：\n");
scanf("%d",&i);
listdelete_sq(&l,i,&e);
printf("你删除的第%d个元素是:%d\n",i,e);
printf("删除操作完成后的线性表是:");
print_sq(&l);
break;
case 4:
printf("请输入要寻找前驱结点的元素:\n");
scanf("%d",&cure);
priorelem_sq(&l,cure,&pre_e);
break;
case 5:
printf("请输入一个元素以便寻找其后继结点:\n");
scanf("%d",&cure);
nextelem_sq(&l,cure,&next_e);
break;
case 6:
printf("该线性表的长度是%d\n",listlength_sq(&l));
break;
case 7:
printf("置逆之前的线性表为：\n");
print_sq(&l);
convert_sq(&l);
printf("置逆之后的线性表为：\n");
print_sq(&l);
break;
case 8:printf("\n请输入你要创建的线性表la的长度:");
scanf("%d",&n);
initlist_sq(&l,n);
printf("\n请输入你要创建的线性表lb的长度:");
scanf("%d",&m);
initlist_sq(&r,m);
mergelist_sq(&l,&r,&lc);
printf("合并后的线性表为:\n");
print_sq(&lc);
break;
case 9:
printf("请输入la的长度n:");
scanf("%d",&n);
initlist_sq(&la,n);
printf("请输入lb的长度m:");
scanf("%d",&m);
initlist_sq(&lb,m);
unionl(&la,&lb);
printf("并集后的la为:\n");
print_sq(&la);
break;
case 10:
listempty_sq(&l);
break;
case 11:
clearlist_sq(&l);
break;
case 12:deld_sq(&l);
printf("\n修改为有序且无重复元素后的线性表为:");
printf("\n");
print_sq(&l);
break;
case 13:
printf("请输入要查找的元素:");
scanf("%d",&k);
sqsearch(&l, k);
break;
case 14:
printf("请输入一个数据元素:\n");
scanf("%d",&cure);
locateelem_sq(&l,cure,cmp);
break;
default:
printf("请选择菜单中的操作,按99退出程序\n");
}
}
}

Answer 2

#include<iostream.h>
#include"SqList.h"
void fun2(SqList I)
{
int temp,p,q;
q=I.length/2;
p=I.length/2;
for(int i=1;i<=p;i++)
{
temp=I.elem[q+i];
I.elem[q+i]=I.elem[q-i];
I.elem[q-i]=temp;
}
cout<<"输出顺序表:"<<endl;
for(int w=0;w<I.length;w++) cout<<I.elem[w]<<" ";
}
void fun1(SqList M)
{
int temp,q,s;
q=M.length/2;

for(int i=0;i!=q;i++)
{

s=M.length-i-1;
temp=M.elem[i];
M.elem[i]=M.elem[s];
M.elem[s]=temp;
}
cout<<"输出顺序表:"<<endl;
for(int v=0;v<M.length;v++) cout<<M.elem[v]<<" ";
}

int main()
{
SqList L;
InitList_Sq(L);
Create_Sq(L);
Print_Sq(L);
switch(L.length%2)
{
case 0:fun1(L);break;
case 1:fun2(L);break;
}
return 0;
}

SqList
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

typedef int ElemType;

#define LIST_INIT_SIZE 10
#define LISTINCREMENT 2
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;

Status InitList_Sq(SqList &L)
{
// 构造一个空的线性表L。
L.elem = new ElemType[LIST_INIT_SIZE];
if (!L.elem) return OVERFLOW; // 存储分配失败
L.length = 0; // 长度为0
L.listsize = LIST_INIT_SIZE; // 初始存储容量
return OK;
} // InitList_Sq

Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
ElemType *p,*q;
if (i < 1 || i > L.length+1) return ERROR;
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

Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{
ElemType *p,*q;
if ((i < 1) || (i > L.length)) return ERROR;
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

void Create_Sq(SqList &L)
{
cout<<"请输入元素个数:";
cin>>L.length;
cout<<"创建顺序表"<<endl;
for(int i=0;i<L.length;i++)
{
cout<<"请输入第"<<i+1<<"个数：";
cin>>L.elem[i];
}
}

void Print_Sq(SqList &L)
{
cout<<"输出顺序表:"<<endl;
for(int i=0;i<L.length;i++) cout<<L.elem[i]<<" ";
}本回答被提问者采纳

Answer 3

#include<iostream.h>
#include"SqList.h"
void
fun2(SqList
I)
{
int
temp,p,q;
q=I.length/2;
p=I.length/2;
for(int
i=1;i<=p;i++)
{
temp=I.elem[q+i];
I.elem[q+i]=I.elem[q-i];
I.elem[q-i]=temp;
}
cout<<"输出顺序表:"<<endl;
for(int
w=0;w<I.length;w++)
cout<<I.elem[w]<<"
";
}
void
fun1(SqList
M)
{
int
temp,q,s;
q=M.length/2;
for(int
i=0;i!=q;i++)
{
s=M.length-i-1;
temp=M.elem[i];
M.elem[i]=M.elem[s];
M.elem[s]=temp;
}
cout<<"输出顺序表:"<<endl;
for(int
v=0;v<M.length;v++)
cout<<M.elem[v]<<"
";
}
int
main()
{
SqList
L;
InitList_Sq(L);
Create_Sq(L);
Print_Sq(L);
switch(L.length%2)
{
case
0:fun1(L);break;
case
1:fun2(L);break;
}
return
0;
}
SqList
#define
TRUE
1
#define
FALSE
0
#define
OK
1
#define
ERROR
0
#define
INFEASIBLE
-1
#define
OVERFLOW
-2
typedef
int
Status;
typedef
int
ElemType;
#define
LIST_INIT_SIZE
10
#define
LISTINCREMENT
2
typedef
struct{
ElemType
*elem;
int
length;
int
listsize;
}SqList;
Status
InitList_Sq(SqList
&L)
{
//
构造一个空的线性表L。
L.elem
=
new
ElemType[LIST_INIT_SIZE];
if
(!L.elem)
return
OVERFLOW;
//
存储分配失败
L.length
=
0;
//
长度为0
L.listsize
=
LIST_INIT_SIZE;
//
初始存储容量
return
OK;
}
//
InitList_Sq
Status
ListInsert_Sq(SqList
&L,
int
i,
ElemType
e)
{
ElemType
*p,*q;
if
(i
<
1
||
i
>
L.length+1)
return
ERROR;
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
Status
ListDelete_Sq(SqList
&L,
int
i,
ElemType
&e)
{
ElemType
*p,*q;
if
((i
<
1)
||
(i
>
L.length))
return
ERROR;
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
void
Create_Sq(SqList
&L)
{
cout<<"请输入元素个数:";
cin>>L.length;
cout<<"创建顺序表"<<endl;
for(int
i=0;i<L.length;i++)
{
cout<<"请输入第"<<i+1<<"个数：";
cin>>L.elem[i];
}
}
void
Print_Sq(SqList
&L)
{
cout<<"输出顺序表:"<<endl;
for(int
i=0;i<L.length;i++)
cout<<L.elem[i]<<"
";
}

Answer 4

typedef struct LNode
{ int data;
struct next * node;
}linklist;
void f(linklist *l)
{ int i; int j=length-1;
for(i=0;i<j;i++,j--)
{t=a[j];a[j]=a[i];a[i]=t;}
}