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