软件技术基础 上机答案

第三章

2 线性表逆置，即使元素排列次序颠倒过来

（1）顺序表 （2）链表

int invert(SeqList*L) void invert (linklist*head)

{ {

int i=1; linklist*p,*q,*r;

datatype temp; p=head->next;

while(i<=L->last/2) q=p->next;

{ while(q!=NULL)

temp=L->data[i]; {

L->data[i]=L->data[L->last-i+1]; r=q->next;

L->data[L->last-i+1]=temp; q->next=p;

} p=q;

} q=r;

}

head->next->next=NULL;

head->next=p;

}

6．//按字母、数字、其它字符分解单链表

void resolve(linklist*head,linklist*letter,linklist*digit,linklist*other) { linklist *p;

while(head->next!=NULL)

{ p=head->next;

head->next=head->next->next;

if((p->data>='A'&&p->data<='Z')||(p->data>='a'&&p->data<='z'))

insert(letter,p);

else if(p->data>='0'&&p->data<='9') insert(digit,p);

else insert(other,p);

}

}

第四章

1．//判字符串是否中心对称

int symmetry(linklist*head,stack*s)

//head为单链表的头指针，s为栈的结构体指针

{

int n=length(head)/2;

linklist*p=head->next;

datatype x;

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){

x=pop(s);

if(x==p->data) p=p->next;

else return 0;

}

return 1;

}

6．循环队列的结构类型定义：

const int m=5;

typedef int datatype;

typedef struct

{ datatype sequ[m];

int rear, quelen;

}qu;

说明：队满条件：sq->quelen==m 队空条件：sq->quelen==0 (注意：不需要空出一个位置) 入队：

void enqueue(qu *sq, datatype x)

{ if(sq->quelen==m) printf("queue is full");

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);

}

}

第五章

7．void strDelete(char*S,int i,int m)

{

char temp[80];int k;

k=i-1;

if(i>=strlen(S)) return;

else

{

strncpy(temp,S,k);

if(k+m>=strlen(S)) strcpy(temp+k,"\0");

else strcpy(temp+k,S+k+m);

strcpy(S,temp);

}

}

或者：

void strDelete(seqstring*S,int i,int m)

//字符串中字符的序号从1开始，数组元素从下标0开始使用

{

char temp[maxsize];

if(i<=S->len){

strncpy(temp,S->str,i-1); //将S->str中第i个字符之前的i-1个字符复制到temp中 strcpy(temp+i-1,S->str+i+m-1);//将S->str中第i+m个字符开始的字符连接到temp

之后

strcpy(S->str,temp); //将temp复制到S->str中

if(i<=S->len)

if(i+m-1<=S->len) S->len=S->len-m; //删除了字符串中间的部分字符 else S->len= i-1; //删除了字符串中从第i个字符开始的全部字符 }

}

11．//找马鞍点

void minmax(array*p)

{ int i,j,have=0;

for(i=0;i<m;i++)

{ p->min[i]=p->A[i][0];

for(j=1;j<n;j++)

if(p->A[i][j]<p->min[i]) p->min[i]=p->A[i][j];

} //分别找出m行的最小值

for (j=0;j<n;j++)

{ p->max[j]=p->A[0][j];

for(i=1;i<m;i++)

if(p->A[i][j]>p->max[j]) p->max[j]=p->A[i][j];

} //分别找出n列的最大值

for(i=0;i<m;i++)

for(j=0;j<n;j++)

if(p->min[i]==p->max[j]) //若相等，则是一个马鞍点

{ cout<<i<<","<<j<<","<<p->A[i][j]<<endl; //输出马鞍点

have=1;

}

if(!have) cout<<"矩阵中没有马鞍点！\n";

}

第六章

7．//交换左右子树

bitree*swap(bitree*p)

{

bitree*t1,*t2;

if(p!=NULL)

{

t1=swap(p->lchild);

t2=swap(p->rchild);

p->lchild=t2;

p->rchild=t1;

}

return p;

}