数据结构上机作业1-5章(3)

LinkList p,q; nt i; p=s;

while(p->next->next!=s) p=p->next; q=p->next; i=q->data;

p->next=q->next; free(q); return i; }

2.32② 已知有一个单向循环链表，其每个结点中

含三个域：prev、data和next，其中data为数据域，next为指向后继结点的指针域，prev也为指针域，但它的值为空(NULL)，试编写算法将此单向循环链表改为双向循环链表，即使prev成为指向前驱结点的指针域。

void PerfectBiLink(BiLinkList &CL) {

BiLinkList p;

for(p=CL;!p->next->prev;p=p->next) p->next->prev=p; }

◆2.33③ 已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。

void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll) {

LinkList p,q,r,s; p=lc;q=lo;

r=ld,s=ll->next; while(s) {

if(s->data>='0'&&s->data<='9')

{

r->next=s;

r=r->next; }

else if(s->data>='A'&&s->data<='Z'||s->data>='a'&&s->data<='z') {

p->next=s;

p=p->next; } else {

q->next=s; q=q->next; }

s=s->next; }

p->next=NULL; q->next=NULL; r->next=NULL; }

2.37④ 设以带头结点的双向循环链表表示的线性表L=(a1,a2,...,an)。试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。 void ReverseEven(BiLinkList &L) {

BiLinkList p; p=L->next;

if(p->next==L){} else {

while(p->next!=L&&p->next->next!=L) {

p->next=p->next->next; p=p->next; }

if(p->next==L) p->next=L->prev->prev; else p->next=L->prev; p=p->next;

while(p->prev->prev!=L) {

p->next=p->prev->prev; p=p->next; }

p->next=L;

for(p=L;p->next!=L;p=p->next) p->next->prev=p; L->prev=p; }

}

◆2.39③ 试对稀疏多项式Pn(x)采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为给定值），并分析你的算法的时间复杂度。 float f(float x,int j) {

int i;

float s = 1;

for( i = 0 ; i < j; ++i ){ s *= x; }

return s; }

float Evaluate(SqPoly pn, float x) /* pn.data[i].coef 存放ai， */ /* pn.data[i].exp存放ei (i=1,2,...,m) */

/* 本算法计算并返回多项式的值。不判别溢出。 */ /* 入口时要求0≤e1

float s = 0;

for( i = 0; i < pn.length; ++i ){

s += pn.data[i].coef * f( x, pn.data[i].exp ); }

return s; }

◆2.41② 试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）结点。

void Difference(LinkedPoly &pa)/* 稀疏多项式 pa 以循环链表作存储结构， */ /* 将此链表修改成它的导函数，并释放无用结点 */ {

LinkedPoly p; p=pa->next;

if(!p->exp) {

pa->next=p->next; p=p->next; }

while(p!=pa) {

p->coef=p->coef*p->exp ; p->exp--; p=p->next;

} }

第三章

◆3.17③ 试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如'序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，'a+b&b+a'是属该模式的字符序列，而'1+3&3-1'则不是。