山东理工大学：《数据结构》课程教学资源（数据结构自编习题集）

数据结构 自主训练集 山东理工大学信科系 殷超等编著 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

算法3： Status ReverseList_L-3(LinkList&L) p-L->next: L->next=Null; ∥L->next:此结点域保存当前结点*s的net值 while(p) s=p: 小指示当前结点，P指示*s的后继，不断链 p-p->next: s->next=L->next: L->next=s, return OK: //ReverseList L-3 1算法 可理 算法4： Status ReverseList_L-4(LinkList&L) p=L->next while(p->next)p=p->next. 仰指向最后结点 while(L->next!=p){ ∥L>next=p表示己别除掉an之前的所有结点 q=L->next: g指向当前结点 L->next-q->next /刚除q,并借助头结点的next域找到下一结点，不断链 q->next-p->next: *q插入p之后 p->next=q: return OK; ∥ReverseList L-4

5 算法 3： Status ReverseList_L-3(LinkList &L){ p=L->next; L->next= Null; // L->next：此结点域保存当前结点*s 的 next 值 while(p){ s=p; //s 指示当前结点，p 指示*s 的后继，不断链 p=p->next ; s->next=L->next ; L->next=s; } return OK; }// ReverseList_L-3 //算法 3 也可理解为从表头进行的表头插入法。 //算法 4 可理解为从表尾进行的表头插入法。 算法 4： Status ReverseList_L-4(LinkList &L){ p=L->next; while(p->next) p= p->next; //p 指向最后结点 while(L->next!=p){ // L->next=p 表示已删除掉 an 之前的所有结点 q=L->next ; //q 指向当前结点 L->next=q->next； //删除*q，并借助头结点的 next 域找到下一结点，不断链 q->next=p->next； //*q 插入*p 之后 p->next=q； } return OK; }// ReverseList_L-4

作业4： 己知两个具有相同结点个数的集合A、B:A={ala2,an,B=b1b2.,bn。集合用 带头结点的单链表表示，设集合A、B的头指针分别为La和Lb。写一算法将A、B合并成 集合C={al,bl,a2,b2,.,an,bn,且集合C的头指针仍为La。 要求：不再另分配空间。 参考答案4： 北工中平西 地工中四平。 Status MergeList L(LinkList&La,LinkList Lb) a=La->next b=Lb->next t=b->next; a、b分别指向单链表La和Lb的当前结点，t指向6的后继结点 while (t){ b->next=a->next; a->next=b: 插入结点b a=a->next->next b=t t=t->next; 后移a、b、t指针 a->next=b; 插入Lb中最后结点 return OK: MergeList_I

6 作业 4： 已知两个具有相同结点个数的集合 A、B：A={a1a2.,an}，B={b1b2.,bn}。集合用 带头结点的单链表表示, 设集合 A、B 的头指针分别为 La 和 Lb。写一算法将 A、B 合并成 集合 C={a1,b1,a2,b2,.,an,bn }，且集合 C 的头指针仍为 La。 要求：不再另分配空间。 参考答案 4： Status MergeList_L(LinkList &La，LinkList Lb){ a = La->next; b = Lb->next; t = b->next; //a、b 分别指向单链表 La 和 Lb 的当前结点，t 指向*b 的后继结点 while (t) { b->next = a->next; a->next = b; //插入结点*b a = a->next->next; b = t； t = t->next; //后移 a、b、t 指针 } a->next = b; //插入 Lb 中最后结点 return OK; }// MergeList_L

作业5： 在双向链表（带头结点）中实现第一个结点与第二个结点的位置互换。仅限修改指针域， 假设该双向链表含3个以上结点。 参考答案5： 算法1： Status Exchange _DuL(DuLinkList&L){ ∥使用2个辅助指针p,q:先删除首结点*p,再将其插入合适位置。 p=L->next; g=p->next>next,/辅助指针p、q L->next=p->next p->next->next-p p->next=q; 对正向链 q->prior p; p->prior=L->next: L->next>prior=L对逆向链 //Exchange1_DuL 算法2 /父 Aa1a2a3子= Status Exchange2_DuL(DuLinkList&L) 使用1个辅助指针P:分别对各结点相应指针调整 p=L->next->next 辅助指针p L->next->next=p->next; L->next->prior=p 对a1所在结占 p->ncxt->prior=L>next对a3所在结点 p->next L->next p->prior =L: ∥对a2所在结点 L->next=p 对头结点 ∥Exchange2_DuL >

7 作业 5： 在双向链表(带头结点)中实现第一个结点与第二个结点的位置互换。仅限修改指针域， 假设该双向链表含 3 个以上结点。 参考答案 5： 算法 1： Status Exchange1_DuL(DuLinkList &L){ //使用 2 个辅助指针 p,q：先删除首结点*p,再将其插入合适位置。 p = L->next; q = p->next->next; //辅助指针 p、q L->next = p->next; p->next->next=p; p->next=q; //对正向链 q->prior = p; p->prior = L->next; L->next->prior = L; //对逆向链 }// Exchange1_DuL 算法 2： Status Exchange2_DuL(DuLinkList &L){ //使用 1 个辅助指针 p:分别对各结点相应指针调整 p = L->next->next; //辅助指针 p L->next->next = p->next; L->next->prior = p; //对 a1 所在结点 p->next->prior = L->next; //对 a3 所在结点 p->next = L->next; p->prior = L; //对 a2 所在结点 L->next = p //对头结点 }// Exchange2_DuL

算法3： a23 Status Exchange3 DuL(DuLinkList &L) 不使用辅助指针：可以实现，但表述教复杂 L->next->next=L >next->next->next L->next->next->prior->next =L->next: L->next=L->next->next->prior; L->next->next->next->prior=L->next->next: L->next->next->prior=L->next: Lnext->prior-L ∥Exchange3_Dul

8 算法 3： Status Exchange3_DuL(DuLinkList &L){ //不使用辅助指针：可以实现，但表述教复杂 L->next->next= L->next->next->next; L->next->next ->prior->next = L->next； L->next=L->next-> next-> prior; L->next->next -> next ->prior=L->next->next; L->next->next ->prior=L-> next； L->next-> prior=L； }// Exchange3_DuL

作业6： 在一个至少含有三个元素的循环链表L中，既无头指针，也无头结点P为指向某结点的 指针，别除该结点的前驱结点。 参考答案6： q p 分析：算法关健是找到p前驱的前驱* 算法1 Status DelPrel_CirL(CirLinkList&L,LNode*p){ g=p: while (q->nextl =p)q=q->next; 找*p的前驱*g r=q while (r->next!=q)r=r->next; 找*q的前驱*r r->next =p; 删除结点 free(q): return OK: /DelPre1_CirL 算法2： Status DelPre2_CirL(CirLinkList&LLNode*p) I=D: while(r->next.>net=p）【=r->net, /找*D前驱的前服◆灯 q =r->next 记录要删除的结点位置，以释放空间 r->next=p; 除结点 free(q). return OK //DelPre2_CirL

9 作业 6： 在一个至少含有三个元素的循环链表 L 中,既无头指针,也无头结点, p 为指向某结点的 指针,删除该结点的前驱结点。 参考答案 6： 分析：算法关键是找到*p 前驱的前驱*r. 算法 1: Status DelPre1_CirL(CirLinkList &L,LNode *p){ q = p; while ( q->next! = p ) q = q->next; //找*p 的前驱*q r = q; while ( r->next! = q ) r = r->next; //找*q 的前驱*r r->next = p; //删除结点 free(q); return OK; }// DelPre1_CirL 算法 2: Status DelPre2_CirL(CirLinkList &L,LNode *p){ r = p; while ( r->next->next! = p ) r = r->next; //找*p 前驱的前驱*r q = r->next; //记录要删除的结点位置，以释放空间 r->next = p; //删除结点 free(q); return OK; }// DelPre2_CirL