软件设计的一些算法.docx

西安电子科技大学

软件基础

徐超龙
02101072

1.设有一个线性表E={e1, e2, … , en-1, en}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={ en , en-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。
顺序表逆置
/*****顺序表逆置子程序*****/
void invert(sequenlist*L)
{
int i,j;
datatype k;
i=L->last;
for(j=1;j<i;j++,i--)
{
k=L->data[j];
L->data[j]=L->data[i];
L->data[i]=k;
}
}

单链表逆置
/*****单链表逆置子程序*****/
void invert(linklist*&L)
{
linklist*p,*r,*k,*heat;
r=L;
k=L->next;
while(r->next!=NULL)
r=r->next;
heat=(linklist*)malloc(sizeof(linklist));
heat->next=r;
while(k->next!=NULL)
{
p=L;
while((p->next)!=r)
p=p->next;
p->next=NULL;
r->next=p;
r=p;

}
L=heat;
}

2.已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。
/*****单链表分解子程序*****/
void resolve(linklist*L,linklist*&let,linklist*&dig,linklist*&oth)
{
linklist*p1,*p2,*p3,*head1,*head2,*head3;
p1=(linklist*)malloc(sizeof(linklist));
p2=(linklist*)malloc(sizeof(linklist));
p3=(linklist*)malloc(sizeof(linklist));
head1=(linklist*)malloc(sizeof(linklist));
head1->next=NULL;
head2=(linklist*)malloc(sizeof(linklist));
head2->next=NULL;
head3=(linklist*)malloc(sizeof(linklist));
head3->next=NULL;
while(L!=NULL)
{
if((L->data<=57)&&(L->data>=48))
{
if(head1->next==NULL)
head1->next=L;
else
p1->next=L;
p1=L;
L=L->next;
p1->next=NULL;

}else
if(((L->data<=90)&&(L->data>=65))||((L->data<=122)&&(L->data>=97)))
{
if(head2->next==NULL)
head2->next=L;
else
p2->next=L;
p2=L;
L=L->next;
p2->next=NULL;
}else
{
if(head3->next==NULL)
head3->next=L;
else
p3->next=L;
p3=L;
L=L->next;
p3->next=NULL;

}
}
p1->next=head1;
p2->next=head2;
p3->next=head3;
let=head1;
dig=head2;
oth=head3;

}

3．设单链表中存放有n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。

/*****判断中心对称子程序*****/
int symmetry(linklist*head,stack*s)
{
linklist*p=head;
p=p->next;
int n=length(head)/2;
datatype dat;
for(int i=0;i<n;i++){
push(s,p->data);
p=p->next;
}
if(length(head)%2==1) p=p->next;
while(p!=NULL){
dat=pop(s);
if(dat==p->data) p=p->next;
else return 0;
}
return 1;
}
//判字符串是否中心对称

4假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。

/*****入队*****/
void enqueue(qu *sq, datatype x)
{ if(sq->quelen==m) printf("queue is full\n");
else { sq->quelen++;
sq->rear=(sq->rear+1)%m;
sq->sequ[sq->rear]=x;
}
}
/*****出队*****/
datatype *dequeue(qu *sq)
{ datatype *temp;
if(sq->quelen==0)
{ printf("queue is empty\n"); return NULL;}
else { temp=(datatype*)malloc(sizeof(datatype));
sq->quelen--;
*temp=sq->sequ[(sq->rear-sq->quelen+m)%m];
return (temp);
}
}

5．串采用顺序存储结构，编写朴素模式匹配算法，查找在串中是否存在给定的子串。（文件夹
/*****模式匹配子程序*****/
int Index(seqstring*L, seqstring*Sus)
{
int i=1,j=1;
while(i<=L->len&&j<=Sus->len)
if(L->str[i-1]==Sus->str[j-1])
{ i++; j++; }
else
{ i=i-j+2; j=1; }
if(j>Sus->len) return(1);
else return(-1);
}

6.若S是一个采用顺序结构存储的串，利用C的库函数strlen和strcpy（或strncpy）编写一算法void SteDelete(char*S,int I,int m)，要求从S中删除从第i个字符开始的连续m个字符。若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开始直至末尾的字符均删除。
//*****删除子串子程序*****/
void strDelete(seqstring*L,int i,int m)
{
char tem[maxsize];
if(i>=L->len)
{
printf("字符未被删除\n");
L->len=0;
}
else
if(i<=L->len)
{
strncpy(tem,L->str,i-1);
strcpy(tem+i-1,L->str+i+m-1);
strcpy(L->str,tem);
if(i<=L->len)
if(i+m-1<=L->len) L->len=L->len-m;
else L->len=L->len-i+1;
}
}

7. 若在矩阵Am×n中存在一个元素A[i][j]，其满足A[i][j]是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Am×n ，设计算法求出矩阵中所有马鞍点。
/*****马鞍点子程序****/
void minmax(array*p)
{ int i,j,flag=0;
for(i=1;i<=m;i++)
{
p->min[i]=p->A[i][1];
for(j=2;j<=n;j++)
if(p->A[i][j]<p->min[i]) p->min[i]=p->A[i][j];
}
for (j=0;j<n;j++)
{
p->max[j]=p->A[1][j];
for(i=2;i<=m;i++)
if(p->A[i][j]>p->max[j]) p->max[j]=p->A[i][j];
}
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(p->min[i]==p->max[j])
{
printf("马鞍点A[%d][%d]=%d\n",i,j,p->A[i][j]);
flag=1;
}
if(!flag) printf("矩阵中没有马鞍点！\n");
}

8. A和B是两个n×n阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储存入一维数组A和B，编写一个算法计算对称矩阵A和B的乘积，结果存入二维数组C。
/*****对称矩阵相乘子程序*****/
void mult(array*p)
{
int i,j,k,t1,t2;
datatype s;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
s=0;
for(k=0;k<n;k++)
{
if(i>=k)t1=i*(i+1)/2+k;
else t1=k*(k+1)/2+i;
if(k>=j)t2=k*(k+1)/2+j;
else t2=j*(j+1)/2+k;
s=s+p->A[t1]*p->B[t2];
}
p->C[i][j]=s;
}
}