第1章 绪论要求：
1、基本概念：数据结构、数据元素等；
2、算法及其时间复杂度；
3、数据结构的抽象数据类型表示；
教材习题解答：
1、略
2、╳、╳、√
3、
4、//通过参数表中的参数显式传递
#include <stdio.h>
#define N 10 //设定为N次多项式
void Assign(float a[])
{
int i;
printf("多项式共有%d项，请依次输入各系数的值\n",N+1);
for(i=0;i<=N;i++)
{
printf("请输入第%d次项系数：",i);
scanf("%f",a+i);
}
}
float Pn(float x0,float a[])
{
int i;
float pn=a[0],x=1;
for(i=1;i<=N;i++)
{
x = x*x0;
pn = pn+a[i]*x;
}
return pn;
}
void main()
{
float a[N+1]={0};
float x0;
Assign(a);
printf("请输入x0的值：");
scanf("%f",&x0);
printf("多项式的值是：%f\n",Pn(x0,a));
}
参考练习：
1、试设计将数组int a[n]中所有奇数移到偶数之前的算法，要求不能使用其它新数组，且时间复杂度为O(n)。
参考解答：
void shift(int a[],int n)
{ int i=0,j=n-1,t;
while(i<j)
{ while(a[i]%2==1)i++;
while(a[j]%2==0)j--;
if(i<j){t=a[i]; a[i]=a[j]; a[j]=t;}
}
2、数据的基本单位是 C 。
A)数据项 B)数据类型 C)数据元素 D)数据变量
3、下面程序段的时间复杂度为 C 。
for(i=0;i<m;i++)
for(j=0;j<n;j++)
A[i][j]=i*j;
A) O(m2) B) O(n2) C) O(m×n) D) O(m+n)
4、数据结构用二元组表示时，它包括 数据元素 的有限集D和D上 关系 的集合R。
5、数据结构是一门研究 非数值计算 的程序设计问题中计算机操作对象以及它们之间的关系和操作等的学科。
6、50个学生围成一圈，从第50个开始逆向报数，报到5时被淘汰，求最后一个学生的位置号。
/* 采用前插法创建链表，首先定义3个结点类型的指针变量，其中h作为头，p和q在创建链表中使用。
初始将h和p赋初值NULL，表示为空的链表，i表示结点中学生的位置编号，由于逆时针数数，所以 从50开始。循环中如果为空链表，则创建链表的第一个结点，用h和p指向，如果不是第一个结点 则又创建一个结点（q指向），并将这个结点链接在p所指结点之后，然后p指向q所指结点，循环 完后将链表首尾相连，即p所指结点的后继指针指向h所指结点。 */
#include <stdio.h>
#include <stdlib.h>
#define N 50
#define M 5
typedef struct node
{
int number; //学生的编号
struct node * next; //后续学生所在结点的地址（指针）
}NODE;
NODE *Create(void) //创建N个学生结点的环形链表，并返回其中编号为N的结点的地址
{
NODE *p,*q,*h;
int i;
i = N;
h = NULL;
p = NULL;
while(i>0)
{
if(h==NULL) //如果是空链表
{
h = (NODE *)malloc(sizeof(NODE));
p = h;
p->number = i;
}
else //如果不是空链表
{
q = (NODE *)malloc(sizeof(NODE));
q->number = i;
p->next = q;
p = q;
}
i--;
}
p->next = h;
return h;
}
void Deal(NODE *h)
{
NODE *p,*q;
int k;
p = h;
k=1;
while(p!=NULL && p->next!=p)
{
q = p;
p = p->next;
k = k+1;
if(k == M)
{
k = 0;
q->next = p->next;
printf("%d\t",p->number);
free(p);
p = q;
}
}
printf("%d\t",p->number);
}
void main()
{
NODE *h;
h = Create();
Deal(h);
}
1、基本概念：数据结构、数据元素等；
2、算法及其时间复杂度；
3、数据结构的抽象数据类型表示；
教材习题解答：
1、略
2、╳、╳、√
3、
4、//通过参数表中的参数显式传递
#include <stdio.h>
#define N 10 //设定为N次多项式
void Assign(float a[])
{
int i;
printf("多项式共有%d项，请依次输入各系数的值\n",N+1);
for(i=0;i<=N;i++)
{
printf("请输入第%d次项系数：",i);
scanf("%f",a+i);
}
}
float Pn(float x0,float a[])
{
int i;
float pn=a[0],x=1;
for(i=1;i<=N;i++)
{
x = x*x0;
pn = pn+a[i]*x;
}
return pn;
}
void main()
{
float a[N+1]={0};
float x0;
Assign(a);
printf("请输入x0的值：");
scanf("%f",&x0);
printf("多项式的值是：%f\n",Pn(x0,a));
}
参考练习：
1、试设计将数组int a[n]中所有奇数移到偶数之前的算法，要求不能使用其它新数组，且时间复杂度为O(n)。
参考解答：
void shift(int a[],int n)
{ int i=0,j=n-1,t;
while(i<j)
{ while(a[i]%2==1)i++;
while(a[j]%2==0)j--;
if(i<j){t=a[i]; a[i]=a[j]; a[j]=t;}
}
2、数据的基本单位是 C 。
A)数据项 B)数据类型 C)数据元素 D)数据变量
3、下面程序段的时间复杂度为 C 。
for(i=0;i<m;i++)
for(j=0;j<n;j++)
A[i][j]=i*j;
A) O(m2) B) O(n2) C) O(m×n) D) O(m+n)
4、数据结构用二元组表示时，它包括 数据元素 的有限集D和D上 关系 的集合R。
5、数据结构是一门研究 非数值计算 的程序设计问题中计算机操作对象以及它们之间的关系和操作等的学科。
6、50个学生围成一圈，从第50个开始逆向报数，报到5时被淘汰，求最后一个学生的位置号。
/* 采用前插法创建链表，首先定义3个结点类型的指针变量，其中h作为头，p和q在创建链表中使用。
初始将h和p赋初值NULL，表示为空的链表，i表示结点中学生的位置编号，由于逆时针数数，所以 从50开始。循环中如果为空链表，则创建链表的第一个结点，用h和p指向，如果不是第一个结点 则又创建一个结点（q指向），并将这个结点链接在p所指结点之后，然后p指向q所指结点，循环 完后将链表首尾相连，即p所指结点的后继指针指向h所指结点。 */
#include <stdio.h>
#include <stdlib.h>
#define N 50
#define M 5
typedef struct node
{
int number; //学生的编号
struct node * next; //后续学生所在结点的地址（指针）
}NODE;
NODE *Create(void) //创建N个学生结点的环形链表，并返回其中编号为N的结点的地址
{
NODE *p,*q,*h;
int i;
i = N;
h = NULL;
p = NULL;
while(i>0)
{
if(h==NULL) //如果是空链表
{
h = (NODE *)malloc(sizeof(NODE));
p = h;
p->number = i;
}
else //如果不是空链表
{
q = (NODE *)malloc(sizeof(NODE));
q->number = i;
p->next = q;
p = q;
}
i--;
}
p->next = h;
return h;
}
void Deal(NODE *h)
{
NODE *p,*q;
int k;
p = h;
k=1;
while(p!=NULL && p->next!=p)
{
q = p;
p = p->next;
k = k+1;
if(k == M)
{
k = 0;
q->next = p->next;
printf("%d\t",p->number);
free(p);
p = q;
}
}
printf("%d\t",p->number);
}
void main()
{
NODE *h;
h = Create();
Deal(h);
}
