数据结构实训作业(III)
数据结构实训作业(III)
用户7267083
发布于 2022-12-08 13:59:03
发布于 2022-12-08 13:59:03
代码可运行
运行总次数：0
代码可运行
数据结构实训作业(III)
于2020年10月13日2020年10月13日由Sukuna发布
第一关
本关任务：编写一个算法，将数组A中的n个元素A[0]至A[n-1]循环右移k位。要求算法时间复杂度为O（n），空间复杂度为O（1）
这一关的写出来不难,但是想出好的过程很难,这里就是对数组进行调换,因为我们发现循环之后数组分成两部分,类似于快速排序的分划结果,这个时候我们会思考可不可以用两部分颠倒的的思想来做
void reverse(ElemType a[],int s,int e)
{
int temp;
while(s < e)
{
temp = a[s];
a[s] = a[e];
a[e] = temp;
s++;
e--;
}
}
void ShiftRightCircular(ElemType *A,int n,int k)
{
/************** begin *****************/
if(k >= n)
k = k%n;
if(k > 0){
reverse(A,0,n-k-1);
reverse(A+(n-k),0,k-1);
reverse(A,0,n-1);
}
if(k < 0){
reverse(A,0,-k-1);
reverse(A+(n+k),0,-k-1);
reverse(A,0,n-1);
}
/************** end *****************/
}第二关
矩阵加法,矩阵的形式是三元组顺序表
我先写个函数,表示矩阵的插入(往后插),接着就对A和B进行遍历,如果行列值不一样,就插入行列值较少的数,i和j是两个数据指针,指向目前遍历的位置,插入A就i后移,插入B就B往后移,以此类推(行列相等就判断相加是否为0,最后i和j都要加)
void EnterTriple(TSMatrix *Q,int row,int col,int e)
{
Q->tu++;
Q->data[Q->tu].i=row;
Q->data[Q->tu].j=col;
Q->data[Q->tu].e=e;
}
TSMatrix ADD(TSMatrix A,TSMatrix B)
//返回矩阵A、B相加的结果
{
/************** begin *****************/
TSMatrix C;
for(int i=0;i<MAXSIZE+1;i++) {
C.data[i].i=0;
C.data[i].j=0;
C.data[i].e=0;
}
C.tu=1;
C.nu=A.nu;
C.mu=A.mu;
int i=1,j=1;
while(i<=A.tu&&j<=B.tu)
{
if(A.data[i].i<B.data[j].i)
{
EnterTriple(&C,A.data[i].i,A.data[i].j,A.data[i].e);
i++;
}
else if(A.data[i].i==B.data[j].i)
{
if(A.data[i].j<B.data[j].j)
{
EnterTriple(&C,A.data[i].i,A.data[i].j,A.data[i].e);
i++;
}
else if(A.data[i].j>B.data[j].j)
{
EnterTriple(&C,B.data[j].i,B.data[j].j,B.data[j].e);
j++;
}
else
{
if(B.data[j].e+A.data[i].e!=0)
EnterTriple(&C,B.data[j].i,B.data[j].j,B.data[j].e+A.data[i].e);
i++;
j++;
}
}
else
{
EnterTriple(&C,B.data[j].i,B.data[j].j,B.data[j].e);
j++;
}
}
while(i<=A.tu)
{
EnterTriple(&C,A.data[i].i,A.data[i].j,A.data[i].e);
i++;
}
while(j<=B.tu)
{
EnterTriple(&C,B.data[j].i,B.data[j].j,B.data[j].e);
j++;
}
for(int i=0;i<C.tu;i++){
C.data[i]=C.data[i+1];
}
C.tu--;
return C;
/************** end *****************/
}第三关
思想是这样的首先找到子串出现的位置,然后把子串之后的保存,经过几个操作,temp里存的是字符串后面的元素,pFound由于是指针操作,改变了原地址的值,所以说S.ch目前指向之前的元素加第二个子串,链接即可 由于main函数里面用了fget,所以说要去除回车的影响,把应有的元素设置为0
#include <string.h>
void Replace(HString &S,HString T,HString V)
//
{
/************** begin *****************/
*(S.ch+S.length)=0;
*(T.ch+T.length)=0;
*(V.ch+V.length)=0;
char *pFound=NULL;
pFound=strstr(S.ch,T.ch);
while(pFound){
char temp[100]={0};
strcpy(temp,pFound+T.length);
strcpy(pFound,V.ch);
strcat(S.ch,temp);
pFound=strstr(pFound+V.length,T.ch);
}
S.length=strlen(S.ch);
/************** end *****************/
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020年10月13日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
