📄 xtjd2.htm
字号:
}<br>
else {<br>
qn=q->next; q->next=c->next;<br>
c->next=q; q=qn;<br>
}<br>
while (p) {pn=p->next; p->next=c->next; c->next=p; p=pn;} <br>
while (q) {qn=q->next; q->next=c->next; c->next=q; q=qn;}<br>
free(b);<br>
}//MergeList<br>
<br>
2.33<br>
void CutApart-LinkList(LinkList &l, LinkList la, LinkList lb, LinkList lc){<br>
//单链表l中的元素含有三类字符：字母、数字和其它字符<br>
//本算法将l分割为la、lb和lc三个循环链表，它们分别只含字母、数字和其它字符<br>
la=(LinkList)malloc(sizeof(LNode)); la->next=la;<br>
lb=(LinkList)malloc(sizeof(LNode)); lb->next=lb;<br>
lc=(LinkList)malloc(sizeof(LNode)); lc->next=lc;<br>
pn=l->next;<br>
while (pn){<br>
p=pn; pn=pn->next;<br>
switch {<br>
case ('a'<=p->data && p->data<='z')<br>
||('A'<=p->data && p->data<='Z') : p->next=la->next; la->next=p; break; <br>
case ('0'<=p->data && p->data<='9') : p->next=lb->next; lb->next=p; break;<br>
default : p->next=lc->next; lc->next=p;<br>
}//switch<br>
}//while<br>
free(l);<br>
}//CutApart-LinkList<br>
<br>
2.39<br>
typedef struct {<br>
float coef;<br>
int expn;<br>
}*Poly, ElemType;<br>
<br>
float Polynomial(Poly &p, int m, float x0){<br>
//多项式p的顺序存储结构中依次存放有c<sub>1</sub>,e<sub>1</sub>,c<sub>2</sub>,e<sub>2</sub>,...,c<sub>m</sub>,e<sub>m</sub><br>
//x<sub>0</sub>为给定值，本算法计算p<sub>n</sub>(x<sub>0</sub>)的值<br>
x=x0^p[0].expn;<br>
pn=p[0].coef*x;<br>
for (i=1; i<=m; ++i){<br>
x=x*x0^(p[i].expn-p[i-1].expn);<br>
pn=pn+p[i].coef*x;<br>
}<br>
retrun pn;<br>
}//Polynomial</font></p>
<p style="line-height: 150%; margin-top: 0; margin-bottom: 0" align="left"> </p>
<font color="#0000FF">(以下内容来自http://bbs.kaoyan.com)</font>
<p>
第二章 线性表</p>
<p>2.10
<p>Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素<br>
{<br>
if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;<br>
for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件<br>
a.elem[i+count-1]=a.elem[i+count+k-1];<br>
a.length-=k;<br>
return OK;<br>
}//DeleteK
<p>2.11
<p>Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中<br>
{<br>
if(va.length+1>va.listsize) return ERROR;<br>
va.length++;<br>
for(i=va.length-1;va.elem[i]>x&&i>=0;i--)<br>
va.elem[i+1]=va.elem[i];<br>
va.elem[i+1]=x;<br>
return OK;<br>
}//Insert_SqList
<p>2.12
<p>int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A<B;值为零,表示A=B<br>
{<br>
for(i=1;A.elem[i]||B.elem[i];i++)<br>
if(A.elem[i]!=B.elem[i]) return A.elem[i]-B.elem[i];<br>
return 0;<br>
}//ListComp
<p>2.13
<p>LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针<br>
{<br>
for(p=l->next;p&&p->data!=x;p=p->next);<br>
return p;<br>
}//Locate
<p>2.14
<p>int Length(LinkList L)//求链表的长度<br>
{<br>
for(k=0,p=L;p->next;p=p->next,k++);<br>
return k;<br>
}//Length
<p>2.15
<p>void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb接在ha后面形成链表hc<br>
{<br>
hc=ha;p=ha;<br>
while(p->next) p=p->next;<br>
p->next=hb;<br>
}//ListConcat
<p>2.16
<p>见书后答案.
<p>2.17
<p>Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b<br>
{<br>
p=L;q=(LinkList*)malloc(sizeof(LNode));<br>
q.data=b;<br>
if(i==1)<br>
{<br>
q.next=p;L=q; //插入在链表头部<br>
}<br>
else<br>
{<br>
while(--i>1) p=p->next;<br>
q->next=p->next;p->next=q; //插入在第i个元素的位置<br>
}<br>
}//Insert
<p>2.18
<p>Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素<br>
{<br>
if(i==1) L=L->next; //删除第一个元素<br>
else<br>
{<br>
p=L;<br>
while(--i>1) p=p->next;<br>
p->next=p->next->next; //删除第i个元素<br>
}<br>
}//Delete
<p>2.19
<p>Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素<br>
{<br>
p=L;<br>
while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素<br>
if(p->next) //如果还有比mink更大的元素<br>
{<br>
q=p->next;<br>
while(q->data<maxk) q=q->next; //q是第一个不小于maxk的元素<br>
p->next=q;<br>
}<br>
}//Delete_Between
<p>2.20
<p>Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素<br>
{<br>
p=L->next;q=p->next; //p,q指向相邻两元素<br>
while(p->next)<br>
{<br>
if(p->data!=q->data)<br>
{<br>
p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步<br>
}<br>
else<br>
{<br>
while(q->data==p->data) q=q->next;<br>
p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素<br>
}<br>
}//while<br>
}//Delete_Equal
<p>2.21
<p>void reverse(SqList &A)//顺序表的就地逆置<br>
{<br>
for(i=1,j=A.length;i<j;i++,j--)<br>
A.elem[i]<->A.elem[j];<br>
}//reverse
<p>2.22
<p>void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2<br>
{<br>
p=L->next;q=p->next;s=q->next;p->next=NULL;<br>
while(s->next)<br>
{<br>
q->next=p;p=q;<br>
q=s;s=s->next; //把L的元素逐个插入新表表头<br>
}<br>
q->next=p;s->next=q;A->next=s;<br>
}//LinkList_reverse<br>
分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.
<p>2.23
<p>void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间<br>
{<br>
p=A->next;q=B->next;C=A;<br>
while(p&&q)<br>
{<br>
s=p->next;p->next=q; //将B的元素插入<br>
if(s)<br>
{<br>
t=q->next;q->next=s; //如A非空,将A的元素插入<br>
}<br>
p=s;q=t;<br>
}//while<br>
}//merge1
<p>2.24
<p>void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间<br>
{<br>
pa=A->next;pb=B->next;pre=NULL; //pa和pb分别指向A,B的当前元素<br>
while(pa&&pb)<br>
{<br>
if(pa->data<pb->data)<br>
{<br>
pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表<br>
}<br>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -