数据结构算法与应用——c语言描述答案
【篇一：《数据结构——用c语言描述》+课后题答案】
book/read/data-structure/h971111102.html
习题解答(唐策善版)(其他版本在上面)
第一章 绪论（参考答案）
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
10101 100
11 91 99
12 92 100
?? ????
20101 99
21 91 98
?? ?? ??
30101 98
31 91 97
到y=0时，要执行10*100次，可记为o（10*y）=o（1）
1.52100 , (2/3)n ,log n 2n , n1/2, n3/2 , (3/2)n , nlogn2 ,2, n!
第二章 线性表(参考答案)
在以下习题解答中，假定使用如下类型定义：
（1）顺序存储结构：
#define maxsize 1024
typedef int elemtype;// 实际上，elemtype可以是任意类型
typedef struct
{ elemtype data[maxsize];
int last; // last表示终端结点在向量中的位置
}sequenlist;
（2）链式存储结构（单链表）
typedef struct node
{elemtype data;
struct node*next；
}linklist;
（3）链式存储结构（双链表）
typedef struct node
{elemtype data;
struct node*prior,*next；
, n n
}dlinklist;
（4）静态链表
typedef struct
{elemtype data;
int next;
}node;
node sa[maxsize];
2.1头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la，往往简称为“链
表la”。
头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。
开始结点：即上面所讲第一个元素的结点。
2.2 只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。
void insert(elemtype a[],int elenum,elemtype x)
// 向量a目前有elenum个元素，且递增有序，本算法将x插入到向量a中，并保持向量的递增有序。
{ int i=0,j;
while (ielenum a[i]=x) i++; // 查插入位置
for (j= elenum-1;j=i;j--) a[j+1]=a[j];// 向后移动元素
a[i]=x; // 插入元素
} // 算法结束
void rightrotate(elemtype a[],int n,k)
// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。 { int num=0; // 计数，最终应等于n
int start=0;// 记录开始位置（下标）
while (numn)
{ temp=a[start]; //暂存起点元素值，temp与向量中元素类型相同
empty=start;//保存空位置下标
next=(start-k+n) %n; // 计算下一右移元素的下标
while (next !=start)
{ a[empty]=a[next];// 右移
num++; // 右移元素数加1
empty=next;
next=(next-k+n) %n; // 计算新右移元素的下标
}
a[empty]=temp; // 把一轮右移中最后一个元素放到合适位置
num++;
start++; // 起点增1，若numn则开始下一轮右移。
}
} // 算法结束
算法二
算法思想：先将左面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;in/2;i++) //全部n个元素逆置
{temp=a[i]; a[i]=a[n-1-i]; a[n-1-i]=temp; }
} // 算法结束
void insert(linklist *l,elemtype x)
// 带头结点的单链表l递增有序，本算法将x插入到链表中，并保持链表的递增有序。 { linklist *p=l-next, *pre=l，*s;
// p为工作指针，指向当前元素，pre为前驱指针，指向当前元素的前驱
s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出
s-data=x;c语言程序设计教材答案
while (p p-data=x) {pre=p; p=p-next;} // 查插入位置
pre-next=s; s-next=p; // 插入元素
} // 算法结束
void invert(linklist *l)
// 本算法将带头结点的单链表l逆置。
//算法思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次前插入以l为头结点的链表中。
{ linklist *p=l-next,*s;
// p为工作指针，指向当前元素，s为p的后继指针
l-next=null;//头结点摘下，指针域置空。算法中头指针l始终不变
while (p)
{s=p-next; // 保留后继结点的指针
p-next=l-next; // 逆置
l-next=p;
p=s; // 将p指向下个待逆置结点
}
} // 算法结束
(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 表示元素的个数，静态链指针等于-1时链表结束while (p！=-1)
{ i++; p=sa[p].next; }
return(i);
} // 算法结束
void union_invert(linklist *a,*b,*c)
// a和b是两个带头结点的递增有序的单链表，本算法将两表合并成
// 一个带头结点的递减有序单链表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;// 恢复待逆置结点的指针
}
// 以下while (pa)和while (pb)语句，只执行一个
while (pa) // 将a表中剩余元素逆置
{ r=pa-next;// 保留后继结点的指针
pa-next=c-next;// 逆置
c-next=pa;
pa=r;// 恢复待逆置结点的指针
}
while (pb) // 将b表中剩余元素逆置
{ r=pb-next;// 保留后继结点的指针
pb-next=c-next;// 逆置
c-next=pb;
pb=r;// 恢复待逆置结点的指针
}
free(b);//释放b表头结点
} // 算法结束
void deleteprior(linklist *l)
/
/ 长度大于1的单循环链表，既无头结点，也无头指针，本算法删除*s 的前驱结点 { linklist *p=s-next,*pre=s; // p为工作指针，指向当前元素，
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论