数据结构 自主训练集 山东理工大学信科系 殷超等编著 2014.9
数据结构 自主训练集 山东理工大学 信科系 殷 超 等编著 2014.9
作业1： 编写算法求一元多项式Pnx-∑aixi的值Pn(x0,并确定算法中基本操作的执行次数 和整个算法的时间复杂度。 输入为：a(i-0,l,n:按a0到an的顺序或逆序)、x0、n,输出为Pn(x0)。 参考答案1： 算法1： void polyvaluel0! float co ∥co:coefficient系数 printf("Input number of terms:") scanf"%d".&n): printf("Input value of x:") scanf("%f&x): xp-1:sum-0. for(=0,<=ni++）】 scanf("%f&co); sum+=co*xp. xp"-x printf("Value is%f,sum) //polyvalue1 基本操作：sum+=co*xp: 执行次数：n次： 算法的时间复杂度：O(n)。 1-
- 1 - 作业 1： 编写算法求一元多项式 Pn(x)= ∑aixi 的值 Pn(x0),并确定算法中基本操作的执行次数 和整个算法的时间复杂度。 输入为：ai(i=0,1,.,n；按 a0 到 an 的顺序或逆序)、x0 、n,输出为 Pn(x0)。 参考答案 1： 算法 1： void polyvalue1(){ float co; // co：coefficient 系数 printf("Input number of terms:"); scanf("%d",&n); printf("Input value of x:"); scanf("%f",&x); printf("Input the %d coefficients from a0 to a%d:\n",n+1,n); xp=1;sum=0; //xp 用于存放 x 的 i 次方 for(i=0;i<=n;i++) { scanf("%f",& co); sum+= co*xp; xp*=x; } printf("Value is:%f",sum); }//polyvalue1 基本操作：sum+= co*xp； 执行次数：n 次； 算法的时间复杂度：O（n）
算法2： Pn0, for(i=m:i)=0:-) scanf"%f"&ai) Pn=Pn*x0+ai: return Pn //polyvalue2 基本操作：Pm=Pm*x0+ai 执行次数：+1次 算法的时间复杂度：O(n)
2 算法 2： float polyvalue2(float x0,int n){ Pn=0; for ( i=n ; i>=0 ; i- ) { scanf("%f",& ai); Pn = Pn*x0 +ai; } return Pn; }//polyvalue2 基本操作：Pn = Pn*x0 + ai; 执行次数：n+1 次； 算法的时间复杂度：O（n）
作业2： 对带头结点的单链表L,在指针P所指的结点上插入数据元素为©的新结点（设由指 针s指示)：在p所指结点之前插入新结点O(,在p所指结点之后插入新结点0)，分别 写出插入算法，思考：在p所指结点之前插入新结点O(),如何改进至0(1)？ 参考答案2： Status Prelnsert(LinkList&L,LNode p,ElemType e) ∥带头结点的单链表L,在指针p所指的结点前插入数据元素为©的新结点 a=L /注意初值的选取！为什么不设为g=L>next?p=L>next时有误！ return ERROR: ∥单链表L为空或指针p为空 s =(LinkList)malloc (sizeof (LNode)): s->data =e: s->next =p: ∥或s>next=q>next;此时*g是p的前驱 a->next s Prelnsert 时间复杂度为O(n) Status NextInsert(LinkList &L.LNode *p,ElemTy 带头结点的单链表L,在指针p所指的结点后插入数据元素为的新结点 if(IL->)return ERROR; ∥单链表L为空或指针p为空 s=(LinkList)malloc (sizeof (LNode)): s->data =e s->next=p->next; p->next return OK //NextInsert 时间复杂度为O1) Status Prelnsert Imp(LinkList &L,LNode *p.Elem Type e) 带头结点的单链表L,在指针p所指的结点前插入数据元素为©的新结点，改进至0) if(IL->nextl!p)return ERROR: ∥单链表L为空或指针p为空 s=(LinkList)malloc (sizeof (LNode)): s->data=p->data: p->data=e: ∥交换*D和*s的数据元素值 s->next=p->next. p->next= return OK; //Prelnsert_Imp 时间复杂度为0(1). 3
3 作业 2： 对带头结点的单链表 L，在指针 p 所指的结点上插入数据元素为 e 的新结点（设由指 针 s 指示）：在 p 所指结点之前插入新结点 O(n), 在 p 所指结点之后插入新结点 O(1)，分别 写出插入算法，思考：在 p 所指结点之前插入新结点 O(n)，如何改进至 O(1)? 参考答案 2： Status PreInsert(LinkList &L，LNode *p，ElemType e){ //带头结点的单链表 L，在指针 p 所指的结点前插入数据元素为 e 的新结点 q = L; //注意初值的选取！为什么不设为 q = L->next ？p=L->next 时有误！ if (!q->next || !p) return ERROR; // 单链表 L 为空或指针 p 为空 while ( q->next ! = p ) q = q->next; s = (LinkList) malloc (sizeof (LNode) ); s->data = e; s->next = p; // 或 s->next = q->next;此时*q 是*p 的前驱 q->next = s; return OK; }// PreInsert 时间复杂度为 O(n). Status NextInsert(LinkList &L，LNode *p，ElemType e){ //带头结点的单链表 L，在指针 p 所指的结点后插入数据元素为 e 的新结点 if (!L->next || !p) return ERROR; // 单链表 L 为空或指针 p 为空 s = (LinkList) malloc (sizeof (LNode) ); s->data = e; s->next = p->next; p->next = s; return OK; }//NextInsert 时间复杂度为 O(1). Status PreInsert_Imp(LinkList &L，LNode *p，ElemType e){ //带头结点的单链表 L，在指针 p 所指的结点前插入数据元素为 e 的新结点，改进至 O(1) if (!L->next || !p) return ERROR; // 单链表 L 为空或指针 p 为空 s = (LinkList) malloc (sizeof (LNode) ); s->data = p->data; p->data = e; // 交换*p 和*s 的数据元素值 s->next = p->next; p->next = s; return OK; }// PreInsert_Imp 时间复杂度为 O(1)
作业3： 写一算法，实现对单链表的原地逆转。（带头结点，除头结点至少含3个以上结点） 参考答案3： 算法1： Status ReverseList_L-l(LinkList&L)f∥除头结点至少含3个以上结点 p=L->next->next; 仰指向当前结点，从第二个结点开始 L->next->next=Null:; while(p){ q=p: p=p->next q->next=L->next. L->next=g: return OK. //ReverseList_I-l 算法2： Status ReverseList_L-2(LinkList &L) p-L->next 仰指向当前结点 if!p)return OK: L为空表 t=Null: /t指示当前结点的next域 while(p) >next s指示当前结点的后继，不断链 t=p, p=s, L->pext=t return OK: )//ReverseList_L-2
4 作业 3： 写一算法，实现对单链表的原地逆转。 (带头结点，除头结点至少含 3 个以上结点) 参考答案 3： 算法 1： Status ReverseList_L-1(LinkList &L){ //除头结点至少含 3 个以上结点 p=L->next->next; //p 指向当前结点，从第二个结点开始 L->next->next=Null; while(p){ q=p; p=p->next; q->next =L ->next; L->next=q; } return OK; }// ReverseList_L-1 算法 2： Status ReverseList_L-2(LinkList &L){ p=L->next; //p 指向当前结点 if(!p) return OK; //L 为空表 t= Null; //t 指示当前结点的 next 域 while(p){ s=p->next; //s 指示当前结点的后继，不断链 p->next = t; t=p; p=s; } L->next=t; return OK; }// ReverseList_L-2