作业答案1、2
- 格式：doc
- 大小：42.00 KB
- 文档页数：4
第一章绪论
1.1 设有数据结构B=（K，R）
其中：K={k1, k2, …, k9}
R={ <k1, k3>，<k1, k8>，<k2, k3>，<k2, k4>，<k2, k5>，<k3, k9>，<k5, k6>，<k8, k9>，<k9, k7>，<k4, k7>，<k4, k6> }
画出这逻辑结构的图示，并确定是哪种数据结构。
答：网状结构（或图状结构）。
1.2 定义抽象数据类型复数，其基本操作有加、减、乘、除、取实部、取虚部。
答：
ADT Complex{
数据对象：D={e1,e2|e1,e2∈实数集}
数据关系：R={<e1,e2>}，其中e1表示复数的实部，e2表示复数的虚部
基本操作：
InitComplex( &C,v1,v2 )
操作结果：构造一个复数，元素e1,e2分别被赋以参数v1,v2的值。
DestroyComplex(&C)
初始条件：复数C已存在。
操作结果：复数C被销毁。
Add(C1, C2, &C3)
初始条件：复数C1，C2已存在。
操作结果：用复数C3返回C1和C2的和。
Subtract (C1, C2, &C3)
初始条件：复数C1，C2已存在。
操作结果：用复数C3返回C1和C2的差。
Multiply (C1, C2, &C3)
初始条件：复数C1，C2已存在。
操作结果：用复数C3返回C1和C2的积。
Divide(C1, C2, &C3)
初始条件：复数C1，C2已存在。
操作结果：用复数C3返回C1和C2的商。
GetReal(C,&e)
初始条件：复数C已存在。
操作结果：用e返回C的实部。
GetImage(C,&e)
初始条件：复数C已存在。
操作结果：用e返回C的虚部。
} ADT Complex
1.3 编程求1!+2!+3!+4!+ … +n!，并求其时间复杂度。
答：
方法一：float factorsum(int n)
{int i,j;
int f,w;
f=0;
for(i=1;i<=n;i++)
{w=1;
for(j=1;j<=i;j++)
w=w*j;
f=f+w;
}
return f;
}
选择处于最里层循环的语句w=w*j作为基本语句，内层循环执行的次数由外层循环变量i 决定，总次数为1+2+……+n=n(n+1)/2，所以时间复杂度为O(n2)。
方法二：float factorsum(int n)
{int i,j;
int f,w;
f=0; w=1;
for(i=1;i<=n;i++)
{ w=w*i;
f=f+w;
}
return f;
}
算法为单循环，所以时间复杂度为O(n)。
第二章线性表
2.1实现顺序表的销毁、取元素、求前驱、求后继操作。
# define List_Init_Size 100
# define listincrement 10
typedef struct{
ElemType *elem;
int length;
int listsize;
} Sqlist;
Status DestoryList(Sqlist &L){
free(L.elem); L.elem=Null;
}
Status GetElem(Sqlist L, int i, ElemType &e){
if ((i<1)||(i>L.length)) return error;
e=L.elem[i-1];
return ok;
}
Status PriorElem(Sqlist L, ElemType cur_e, ElemType &pre_e){
if (L.elem[0]= = cur_e) return error; //这句也可以省略，因为下面for循环从第2个元素开始for (i=2;i<=L.length;i++)
{if (L.elem[i-1]= = cur_e) { pre_e=L.elem[i-2]; return ok;}
}
return error;
}
Status NextElem(Sqlist L, ElemType cur_e, ElemType &next_e){
if (L.elem[L.length-1]= = cur_e) return error; //这句也可以省略，因为下面for循环到倒数第2个元素结束
for (i=1;i<=L.length-1;i++)
{if (L.elem[i-1]= = cur_e) { next_e=L.elem[i]; return ok;}
}
return error;
}
2.2 实现单链表的销毁、求表长、求前驱、求后继操作。
Typedef struct Lnode{
Elemtype data;
struct Lnode *next;
}LNode,*LinkList;
Status DestoryList(LinkList &L){
while(L){ p=L->next; free(L); L=p;}
return ok;
}
int ListLength(LinkList L){
p= L->next; j=0;
while(p) {p= p->next; j++; }
return j;
}
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e){
p= L->next; //p用来记录cur_e的前一个元素
while((p->next)&&(p->next->data!=cur_e))
p=p->next;
if (!(p->next)) return error;
pre_e=p->data;
return ok;
}
或者：
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e){
p= L->next; //p用来记录cur_e的前一个元素
while((p->next) {
if(p->next->data= =cur_e)
{ pre_e=p->data; return ok;}
p=p->next;
}
return error;
}
Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e){ p= L->next; //p用来记录cur_e的位置
while((p->next)&&(p->data!=cur_e))
p=p->next;
if (!(p ->next)) return error;
next_e=p->next ->data;
return ok;
}
或者：
Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e){ p= L->next; //p用来记录cur_e的位置
while((p->next) {
if(p ->data= =cur_e)
{ next_e=p->next ->data; return ok;}
p=p->next;
}
return error;
}
2.3 逆置带头结点的单链表L。
void inverse(LinkList &L) {
p= L->next; L->next=null;
while(p) {temp= p->next; p ->next= L->next; L->next=p; p=temp;} }。
