西北大学《数据结构》典型例题（1-5章）

西北大学《数据结构》各章典型例题

第一章 绪论

1.1 试写一个算法，自大到小依次输出顺序读入的三个数X、Y和Z的值。

void Desceding(int &x, int &y, int &z) { //将x、y和z按从大到小的顺序排列 if (x

1.2 试编一个算法求一维数组float a[n]中的所有元素之和。

float sum(float a[], int n) {

// 求数组a[n]中所有元素之和 for (i=0; i

1.3 分析下列各算法的时间复杂度： （1）void prime(int n){

/* 判断n是否是素数 */

for (i=2; ((n%i)!=0)&&(i

if i>sqrt(n) printf(\ else printf(\

}/* prime */

最坏情况下O(sqrt(n))

(2) float sum1(int n){

/* 计算1！+2！+…+n! */ p=1; sum1=0;

for (i=1; i<=n; ++i){ p=p*i; sum1=sum1+p }

}/* sum1 */ O(n)

(3) float sum2(int n){

/* 计算1！+2！+…+n! */

sum2=0;

for (i=1; i<=n; ++i){ p=1;

for (j=1; j<=i; ++j) p=p*j; sum2=sum2+p; }

}/* sum2 */

O(n2)

(4) void sort(int a[],int n){

/* 将数组a中的元素按自小到大的顺序排列 */ for (i=1; i<=n-1; ++i){ k=i;

for (j=i+1; j<=n; ++j) if (a[j]j) {x=a[i];a[i]=a[k];a[k]=x;} }

}/* sort */

O(n2)

（5）void matrimult(a[m][n],b[n][l],c[m][l],int m,int n,int l){ /* a为m×n阶的矩阵，b为n×l阶的矩阵，c为m×l阶的矩阵 */ /* 计算c=a*b */ for (i=1; i<=m; ++i) for (j=1; j<=l; ++j) c[i,j]=0;

for (i=1; i<=m; ++i) for (j=1; j<=l; ++j) for (k=1; k<=n; ++k)

c[i,j]=c[i,j]+a[i,k]*b[k,i];

}/* matrimult */

O(n3)

第一章 绪论 1.16

void print_descending(int x,int y,int z)//按从大到小顺序输出三个数 {

scanf(\

if(xy; //<->为表示交换的双目运算符,以下同 if(yz;

if(xy; //冒泡排序 printf(\}//print_descending 1.17

Status fib(int k,int m,int &f)//求k阶斐波那契序列的第m项的值f {

int tempd;

if(k<2||m<0) return ERROR; if(m

else if (m==k-1) f=1; else {

for(i=0;i<=k-2;i++) temp[i]=0; temp[k-1]=1; //初始化

for(i=k;i<=m;i++) //求出序列第k至第m个元素的值 {

sum=0;

for(j=i-k;j

f=temp[m];

}

return OK; }//fib

分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 1.18

typedef struct{

char *sport;

enum{male,female} gender;

char schoolname; //校名为'A','B','C','D'或'E' char *result; int score; } resulttype; typedef struct{

int malescore; int femalescore; int totalscore; } scoretype;

void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中 {

scoretype score; i=0;

while(result[i].sport!=NULL) {

switch(result[i].schoolname) {

case 'A':

score[ 0 ].totalscore+=result[i].score;

if(result[i].gender==0) score[ 0 ].malescore+=result[i].score; else score[ 0 ].femalescore+=result[i].score; break; case 'B':

score.totalscore+=result[i].score;

if(result[i].gender==0) score.malescore+=result[i].score; else score.femalescore+=result[i].score; break;

…… …… …… } i++； }

for(i=0;i<5;i++) {

printf(\

printf(\ printf(\ printf(\ }

}//summary 1.19

Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint {

last=1;

for(i=1;i<=ARRSIZE;i++) {a[i-1]=last*2*i;

if((a[i-1]/last)!=(2*i)) reurn OVERFLOW; last=a[i-1]; return OK; }

}//algo119

分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 1.20

void polyvalue() {

float ad; float *p=a;

printf(\ scanf(\

printf(\ for(i=0;i<=n;i++) scanf(\ printf(\ scanf(\

p=a;xp=1;sum=0; //xp用于存放x的i次方 for(i=0;i<=n;i++) {

sum+=xp*(*p++); xp*=x; }

printf(\}//polyvalue

第二章 线性表

2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

Status OrderListInsert-sq(SqList va, ElemType x) {

//将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法1) if (va.length==va.listsize){ newbase=(ElemType

*)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase;

va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间

if (!va.length) {va.elem[0]=x; ++va.length; return OK;} q=&(va.elem[0]);

while (*q<=x)&&(q<=&(va.elem[va.length-1])) ++q; //查找插入位置 for (p=&(va.elem[va.length-1]); p>=q; --p) *(p+1)=*p; *q=x; ++va.length; return OK;

}//OrderListInsert-sq

Status OrderListInsert-sq(SqList va, ElemType x) {

//将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法2) if (va.length==va.listsize){ newbase=(ElemType

*)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase;

va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间

if (!va.length) {va.elem[0]=x; ++va.length; return OK;} p=&(va.elem[va.length-1]);

while (P>=&(va.elem[0])&&*p>x) {*(p+1)=*p; --p;} *(p+1)=x; ++va.length; return OK; }//OrderListInsert-sq

2.12 设A=(a1,...,am)和B=(b1,...,bn)均为顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表。若A'=B'=空表，则A=B；若A'=空表，而B'≠空表，或者两者均不为空表，且A'的首元小于B'的首元，则AB。试写一个比较A，B大小的算法。 int Compare-List(SqList a, SqList b){

//a,b为顺序表，若ab时，返回1 i=0;

while (i<=a.length-1) && (i<=b.length-1) && (a.elem[i]=b.elem[i]) ++i; switch {

case i=a.length && i=b.length : return 0; break; case (i=a.length && i<=b.length-1)

||(i<=a.length-1 && i<=b.length-1 && a.elem[i]

}//Compare-List