数据结构与算法课后习题解答

数据结构与算法课后习题解答

第一章绪论（参考答案）

1.3 (1) O(n)

(2) (2) O(n)

(3) (3) O(n)

(4) (4) O(n1/2)

(5) (5) 执行程序段的过程中，x,y值变化如下：

循环次数 x y

0（初始） 91 100

1 92 100

2 93 100

…… ……

9 100 100

10 101 100

11 91

12

……

20 99

21 91 98

…… ……

30 101 98

31 91 97

到y=0时，要执行10*100次，可记为O（10*y）=O（n）

数据结构与算法课后习题解答

1.5 2100 , (2/3)n , log2n , n1/2 , n3/2 , (3/2)n , nlog2n , 2 n , n! , n n

第二章 线性表(参考答案)

在以下习题解答中，假定使用如下类型定义：

（1）顺序存储结构：

#define MAXSIZE 1024

typedef int ElemType;// 实际上，ElemType

typedef struct

{ ElemType data[MAXSIZE];

int last; // last

}sequenlist;

（2

*next；

}linklist;

（3）链式存储结构（双链表）

typedef struct node

{ElemType data;

struct node *prior,*next；

数据结构与算法课后习题解答

}dlinklist;

（4）静态链表

typedef struct

{ElemType data;

int next;

}node;

node sa[MAXSIZE];

2.1 la，往往简称为“链表la”。

是副产品）

2.2 2·3

void

elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的

{ int i=0,j;

while (i<elenum && A[i]<=x) i++; // 查找插入位置

for (j= elenum-1;j>=i;j--) A[j+1]=A[j];// 向后移动元素

A[i]=x; // 插入元素

数据结构与算法课后习题解答

} // 算法结束 2·4

void rightrotate(ElemType A[],int n,k)

// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。

{ int num=0; // 计数，最终应等于n

int start=0; // 记录开始位置（下标）

while (num<n)

{ temp=A[start]; //暂存起点元素值，temp

empty=start; //保存空位置下标

next=(start-K+n) %n; //

while (next !=start)

{ A[empty]=A[next];//

num++; 1

// 计算新右移元素的下标

// 把一轮右移中最后一个元素放到合适位置

num++;

start++; // 起点增1，若num<n则开始下一轮右移。 }

} // 算法结束

数据结构与算法课后习题解答

算法二

算法思想：先将左面n-k个元素逆置，接着将右面k个元素逆置，最后再将这n个元素逆置。

void rightrotate(ElemType A[],int n,k)

// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。

{ ElemType temp;

for(i=0;i<(n-k)/2;i++) //左面n-k个元素逆置

{temp=A[i]; A[i]=A[n-k-1-i]; A[n-k-1-i]=temp; }

for(i=1;i<=k;i++) //右面k个元素逆置

{temp=A[n-k-i]; A[n-k-i]=A[n-i]; A[n-i]=temp; }

for(i=0;i<n/2;i++) //全部n个元素逆置

{temp=A[i]; A[i]=A[n-1-i]; A[n-1-i]=temp; }

} // 算法结束 2·5

void

// L递增有序，本算法将x插入到链表中，并保持链表的递增有序。

，*s;

// p为工作指针，指向当前元素，pre为前驱指针，指向当前元素的前驱

s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出

s->data=x;

while (p && p->data<=x) {pre=p; p=p->next;} // 查找插入位置

pre->next=s; s->next=p; // 插入元素

数据结构与算法课后习题解答

} // 算法结束 2·6

void invert(linklist *L)

// 本算法将带头结点的单链表L逆置。

//点的链表中。

{ linklist *p=L->next,*s;

// p为工作指针，指向当前元素，s为p的后继指针

L->next=null;//

while (p)

{s=p->next; //

p->next=L->next; // 逆置

L->next=p;

p=s; }

} 2·7

(1) int length1(linklist *L)

// 本算法计算带头结点的单链表L的长度

{ linklist *p=L->next; int i=0;

数据结构与算法课后习题解答

// p为工作指针，指向当前元素，i 表示链表的长度

while (p)

{ i++; p=p->next; }

return(i);

} // 算法结束

(2) int length1(node sa[MAXSIZE])

// 本算法计算静态链表s中元素的个数。

{ int p=sa[0].next, i=0;

// p为工作指针，指向当前元素，i 时链表结束

while (p！=-1)

{ i++; p=sa[p].next; }

return(i);

} // 算法结束 2·8

void

// C，利用原表空间。

{ linklist *pa=A->next,*pb=B->next,*C=A,*r;

// pa,pb为工作指针，分别指向A表和B表的当前元素，r为当前逆置

//元素的后继指针, 使逆置元素的表避免断开。

//算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。

数据结构与算法课后习题解答

C->next=null;//头结点摘下，指针域置空。算法中头指针C始终不变

while (pa && pb) // 两表均不空时作

if (pa->data<=pb->data) // 将A表中元素合并且逆置

{ r=pa->next; // 保留后继结点的指针

pa->next=C->next; // 逆置

C->next=pa;

pa=r; // 恢复待逆置结点的指针 }

else // 将B表中元素合并且逆置

{ r=pb->next; // 保留后继结点的指针

pb->next=C->next; // 逆置

C->next=pb;

pb=r; // }

// 以下语句，只执行一个

// 将A表中剩余元素逆置

// 保留后继结点的指针

// 逆置

C->next=pa;

pa=r; // 恢复待逆置结点的指针 }

while (pb) // 将B表中剩余元素逆置

数据结构与算法课后习题解答

{ r=pb->next; // 保留后继结点的指针

pb->next=C->next; // 逆置…… 此处隐藏：2546字，全部文档内容请下载后查看。喜欢就下载吧 ……