数据结构严蔚敏源码

1. 严蔚敏的数据结构（C语言版）绪论抽象数据类型Triplet的表示和实现

&T表示引用类型，函数调用时值传递， Status DestroyTeiplet(Triplet &T) 忠 三元组T整个进行了改变，被销毁了，所以用了&T，进行了引用传递，功能类似于指针传递，不过书写类型可以类似于值传递；Status Get(Triplet T,int i,ElemType &e) 仅仅是查询三元组，没有改变三元组的内容，所以用了直接调用值传递；建议去看下关于函数调用的 引用传递 值传递 和指针传递的 各种参数传递形式

2. 下面这是严蔚敏《数据结构C语言版》习题集6.36的答案，这是类C，还是纯C语言，还是C++

基本上就是C语言，返回值它直接写了一个Status，程序里的返回值是TRUE和FALSE，如果把STATUS改成BOOL就是标准的C语言了。C语言是C++的一个子集，这个程序也可以认为是C++写的。

3. 严蔚敏数据结构题集(C语言版)实习题答案

/* 用邻接矩阵表示的图的prim算法的源程序*/

#include<stdio.h>
#define MAXVEX 6

typedef char VexType;

typedef float AdjType;

typedef struct {
int n; /* 图的顶点个数 */
/*VexType vexs[MAXVEX]; 顶点信息 */
AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */
} GraphMatrix;

typedef struct{
int start_vex, stop_vex; /* 边的起点和终点 */
AdjType weight; /* 边的权 */
} Edge;

Edge mst[5];

#define MAX 1e+8

void prim(GraphMatrix * pgraph, Edge mst[]) {
int i, j, min, vx, vy;
float weight, minweight; Edge edge;

for (i = 0; i < pgraph->n-1; i++) {
mst[i].start_vex = 0;
mst[i].stop_vex = i+1;
mst[i].weight = pgraph->arcs[0][i+1];
}

for (i = 0; i < pgraph->n-1; i++) { /* 共n-1条边 */
minweight = MAX; min = i;
for (j = i; j < pgraph->n-1; j++)/* 从所有边(vx,vy)(vx∈U,vy∈V-U)中选出最短的边 */
if(mst[j].weight < minweight) {
minweight = mst[j].weight;
min = j;
}

/* mst[min]是最短的边(vx,vy)(vx∈U, vy∈V-U)，将mst[min]加入最小生成树 */
edge = mst[min];
mst[min] = mst[i];
mst[i] = edge;
vx = mst[i].stop_vex; /* vx为刚加入最小生成树的顶点的下标 */

for(j = i+1; j < pgraph->n-1; j++) { /* 调整mst[i+1]到mst[n-1] */
vy=mst[j].stop_vex; weight = pgraph->arcs[vx][vy];
if (weight < mst[j].weight) {
mst[j].weight = weight;
mst[j].start_vex = vx;
}
}
}
}

GraphMatrix graph = {
6,
{{0,10,MAX,MAX,19,21},
{10,0,5,6,MAX,11},
{MAX,5,0,6,MAX,MAX},
{MAX,6,6,0,18,14},
{19,MAX,MAX,18,0,33},
{21,11,MAX,14,33,0}
}
};

int main(){
int i;
prim(&graph,mst);
for (i = 0; i < graph.n-1; i++)
printf("(%d %d %.0f)\n", mst[i].start_vex,
mst[i].stop_vex, mst[i].weight);
return 0;
}

4. 为什么数据结构第三版上机指导的源程序都不能运行

我也不知道那个是第三版，不知道你是不是用的 严蔚敏比如和吴伟民编着的C语言版的数据结构？
那里面写的全是伪代码，比如下面的程序：
void union(List& La,List Lb)//定义合并顺序表的函数
{
La_len=ListLength(La);Lb_len=ListLength(Lb);
for(i=1;i<Lb_len;i++)
{
GetElem(Lb,i,e);
if(!LocateElem(La,e,equal)) ListInsert(La,++La_len;E);
}
}
这是我数据结构课本上的代码，就是伪代码，为什么呢？
像ListLength()，GetElem()，LocateElem()，ListInsert()函数在C的编译器根本不会识别这些函数，而那些编写书籍的人认为，这些比较基本的一些操作你自己可以实现，他给你省略了这些。你可以通过函数英文名可以大概知道这个函数大概想实现什么样的操作！这就是传说中的伪代码！

呵呵，那个书上省去的你一定可以实现哦，相信自己!
我刚学了数据结构不到一年时间，如今我大三，当年我也犯了这个迷惑。我经常把课本上的代码敲上去，全是错误，后来我才明白了编教材的人这么写教材了！愿你早日走出这个误区！

5. 娓呭崕澶у︿弗钄氭晱鏁版嵁缁撴瀯棰橀泦瀹屾暣绛旀(c璇瑷鐗)

绗涓绔 缁璁
1.16
void print_descending(int x,int y,int z)//鎸変粠澶у埌灏忛‘搴忚緭鍑轰笁涓鏁
{
scanf("%d,%d,%d",&x,&y,&z);
if(x<y) x<->y; //<->涓鸿〃绀轰氦鎹㈢殑鍙岀洰杩愮畻绗,浠ヤ笅钖
if(y<z) y<->z;
if(x<y) x<->y; //鍐掓场鎺掑簭
printf("%d %d %d",x,y,z);
}//print_descending
1.17
Status fib(int k,int m,int &f)//姹俴阒舵枑娉㈤偅濂戝簭鍒楃殑绗珐椤圭殑鍊糵
{
int tempd;
if(k<2||m<0) return ERROR;
if(m<k-1) f=0;
else if (m==k-1) f=1;
else
{
for(i=0;i<=k-2;i++) temp[i]=0;
temp[k-1]=1; //鍒濆嫔寲
for(i=k;i<=m;i++) //姹傚嚭搴忓垪绗琸镊崇珐涓鍏幂礌镄勫
{
sum=0;
for(j=i-k;j<i;j++) sum+=temp[j];
temp[i]=sum;
}
f=temp[m];
}
return OK;
}//fib
鍒嗘瀽:阃氲繃淇濆瓨宸茬粡璁＄畻鍑烘潵镄勭粨鏋,姝ゆ柟娉旷殑镞堕棿澶嶆潅搴︿粎涓篛(m^2).濡傛灉閲囩敤阃掑綊缂栫▼(澶у氭暟浜洪兘浼氶栧厛𨱍冲埌阃掑綊鏂规硶),鍒欐椂闂村嶆潅搴﹀皢楂樿揪O(k^m).
1.18
typedef struct{
char *sport;
enum{male,female} gender;
char schoolname; //镙″悕涓'A','B','C','D'鎴'E'
char *result;
int score;
} resulttype;
typedef struct{
int malescore;
int femalescore;
int totalscore;
} scoretype;
void summary(resulttype result[ ])//姹傚悇镙＄殑鐢峰コ镐诲垎鍜屽洟浣撴诲垎,锅囱剧粨鏋滃凡缁忓偍瀛桦湪result[ ]鏁扮粍涓
{
scoretype score ;
i=0;
while(result[i].sport!=NULL)
{
switch(result[i].schoolname)
{
case 'A':
score[ 0 ].totalscore+=result[i].score;
if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;
else score[ 0 ].femalescore+=result[i].score;
break;
case 'B':
score .totalscore+=result[i].score;
if(result[i].gender==0) score .malescore+=result[i].score;
else score .femalescore+=result[i].score;
break;
钬︹ 钬︹ 钬︹
}
i++锛
}
for(i=0;i<5;i++)
{
printf("School %d:\n",i);
printf("Total score of male:%d\n",score[i].malescore);
printf("Total score of female:%d\n",score[i].femalescore);
printf("Total score of all:%d\n\n",score[i].totalscore);
}
}//summary
1.19
Status algo119(int a[ARRSIZE])//姹俰!*2^i搴忓垪镄勫间笖涓嶈秴杩噈axint
{
last=1;
for(i=1;i<=ARRSIZE;i++)
{
a[i-1]=last*2*i;
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
last=a[i-1];
return OK;
}
}//algo119
鍒嗘瀽:褰撴煇涓椤圭殑缁撴灉瓒呰繃浜唌axint镞,瀹冮櫎浠ュ墠闱涓椤圭殑鍟嗕细鍙戠敓寮傚父.
1.20
void polyvalue()
{
float ad;
float *p=a;
printf("Input number of terms:");
scanf("%d",&n);
printf("Input the %d coefficients from a0 to a%d:\n",n,n);
for(i=0;i<=n;i++) scanf("%f",p++);
printf("Input value of x:");
scanf("%f",&x);
p=a;xp=1;sum=0; //xp鐢ㄤ簬瀛樻斁x镄刬娆℃柟
for(i=0;i<=n;i++)
{
sum+=xp*(*p++);
xp*=x;
}
printf("Value is:%f",sum);
}//polyvalue

绗浜岀珷 绾挎ц〃
2.10
Status DeleteK(SqList &a,int i,int k)//鍒犻櫎绾挎ц〃a涓绗琲涓鍏幂礌璧风殑k涓鍏幂礌
{
if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;
for(count=1;i+count-1<=a.length-k;count++) //娉ㄦ剰寰鐜缁撴潫镄勬浔浠
a.elem[i+count-1]=a.elem[i+count+k-1];
a.length-=k;
return OK;
}//DeleteK
2.11
Status Insert_SqList(SqList &va,int x)//鎶妜鎻掑叆阃掑炴湁搴忚〃va涓
{
if(va.length+1>va.listsize) return ERROR;
va.length++;
for(i=va.length-1;va.elem[i]>x&&i>=0;i--)
va.elem[i+1]=va.elem[i];
va.elem[i+1]=x;
return OK;
}//Insert_SqList
2.12
int ListComp(SqList A,SqList B)//姣旇缉瀛楃﹁〃A鍜孊,骞剁敤杩斿洖鍊艰〃绀虹粨鏋,鍊间负姝,琛ㄧずA>B;鍊间负璐,琛ㄧずA<B;鍊间负闆,琛ㄧずA=B
{
for(i=1;A.elem[i]||B.elem[i];i++)
if(A.elem[i]!=B.elem[i]) return A.elem[i]-B.elem[i];
return 0;
}//ListComp
2.13
LNode* Locate(LinkList L,int x)//阈捐〃涓婄殑鍏幂礌镆ユ垒,杩斿洖鎸囬拡
{
for(p=l->next;p&&p->data!=x;p=p->next);
return p;
}//Locate
2.14
int Length(LinkList L)//姹傞摼琛ㄧ殑闀垮害
{
for(k=0,p=L;p->next;p=p->next,k++);
return k;
}//Length
2.15
void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//鎶婇摼琛╤b鎺ュ湪ha钖庨溃褰㈡垚阈捐〃hc
{
hc=ha;p=ha;
while(p->next) p=p->next;
p->next=hb;
}//ListConcat
2.16
瑙佷功钖庣瓟妗.
2.17
Status Insert(LinkList &L,int i,int b)//鍦ㄦ棤澶寸粨镣归摼琛↙镄勭琲涓鍏幂礌涔嫔墠鎻掑叆鍏幂礌b
{
p=L;q=(LinkList*)malloc(sizeof(LNode));
q.data=b;
if(i==1)
{
q.next=p;L=q; //鎻掑叆鍦ㄩ摼琛ㄥご閮
}
else
{
while(--i>1) p=p->next;
q->next=p->next;p->next=q; //鎻掑叆鍦ㄧ琲涓鍏幂礌镄勪綅缃
}
}//Insert
2.18
Status Delete(LinkList &L,int i)//鍦ㄦ棤澶寸粨镣归摼琛↙涓鍒犻櫎绗琲涓鍏幂礌
{
if(i==1) L=L->next; //鍒犻櫎绗涓涓鍏幂礌
else
{
p=L;
while(--i>1) p=p->next;
p->next=p->next->next; //鍒犻櫎绗琲涓鍏幂礌
}
}//Delete
2.19
Status Delete_Between(Linklist &L,int mink,int maxk)//鍒犻櫎鍏幂礌阃掑炴帓鍒楃殑阈捐〃L涓鍊煎ぇ浜巑ink涓斿皬浜巑axk镄勬墍链夊厓绱
{
p=L;
while(p->next->data<=mink) p=p->next; //p鏄链钖庝竴涓涓嶅ぇ浜巑ink镄勫厓绱
if(p->next) //濡傛灉杩樻湁姣攎ink镟村ぇ镄勫厓绱
{
q=p->next;
while(q->data<maxk) q=q->next; //q鏄绗涓涓涓嶅皬浜巑axk镄勫厓绱
p->next=q;
}
}//Delete_Between
2.20
Status Delete_Equal(Linklist &L)//鍒犻櫎鍏幂礌阃掑炴帓鍒楃殑阈捐〃L涓镓链夊肩浉钖岀殑鍏幂礌
{
p=L->next;q=p->next; //p,q鎸囧悜鐩搁偦涓ゅ厓绱
while(p->next)
{
if(p->data!=q->data)
{
p=p->next;q=p->next; //褰撶浉闾讳袱鍏幂礌涓岖浉绛夋椂,p,q閮藉悜钖庢帹涓姝
}
else
{
while(q->data==p->data)
{
free(q);
q=q->next;
}
p->next=q;p=q;q=p->next; //褰撶浉闾诲厓绱犵浉绛夋椂鍒犻櫎澶氢綑鍏幂礌
}//else
}//while
}//Delete_Equal
2.21
void reverse(SqList &A)//椤哄簭琛ㄧ殑灏卞湴阃嗙疆
{
for(i=1,j=A.length;i<j;i++,j--)
A.elem[i]<->A.elem[j];
}//reverse
2.22
void LinkList_reverse(Linklist &L)//阈捐〃镄勫氨鍦伴嗙疆;涓虹亩鍖栫畻娉,锅囱捐〃闀垮ぇ浜2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next; //鎶奓镄勫厓绱犻愪釜鎻掑叆鏂拌〃琛ㄥご
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse
鍒嗘瀽:链绠楁硶镄勬濇兂鏄,阃愪釜鍦版妸L镄勫綋鍓嶅厓绱烁鎻掑叆鏂扮殑阈捐〃澶撮儴,p涓烘柊琛ㄨ〃澶.
2.23
void merge1(LinkList &A,LinkList &B,LinkList &C)//鎶婇摼琛ˋ鍜孊钖埚苟涓篊,A鍜孊镄勫厓绱犻棿闅旀帓鍒,涓斾娇鐢ㄥ师瀛桦偍绌洪棿
{
p=A->next;q=B->next;C=A;
while(p&&q)
{
s=p->next;p->next=q; //灏咮镄勫厓绱犳彃鍏
if(s)
{
t=q->next;q->next=s; //濡侫闱炵┖,灏咥镄勫厓绱犳彃鍏
}
p=s;q=t;
}//while
}//merge1
2.24
void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//鎶婂厓绱犻掑炴帓鍒楃殑阈捐〃A鍜孊钖埚苟涓篊,涓擟涓鍏幂礌阃掑噺鎺掑垪,浣跨敤铡熺┖闂
{
pa=A->next;pb=B->next;pre=NULL; //pa鍜宲b鍒嗗埆鎸囧悜A,B镄勫綋鍓嶅厓绱
while(pa||pb)
{
if(pa->data<pb->data||!pb)
{
pc=pa;q=pa->next;pa->next=pre;pa=q; //灏咥镄勫厓绱犳彃鍏ユ柊琛
}
else
{
pc=pb;q=pb->next;pb->next=pre;pb=q; //灏咮镄勫厓绱犳彃鍏ユ柊琛
}
pre=pc;
}
C=A;A->next=pc; //鏋勯犳柊琛ㄥご
}//reverse_merge
鍒嗘瀽:链绠楁硶镄勬濇兂鏄,鎸変粠灏忓埌澶х殑椤哄簭渚濇℃妸A鍜孊镄勫厓绱犳彃鍏ユ柊琛ㄧ殑澶撮儴pc澶,链钖庡勭悊A鎴朆镄勫墿浣椤厓绱.
2.25
void SqList_Intersect(SqList A,SqList B,SqList &C)//姹傚厓绱犻掑炴帓鍒楃殑绾挎ц〃A鍜孊镄勫厓绱犵殑浜ら泦骞跺瓨鍏C涓
{
i=1;j=1;k=0;
while(A.elem[i]&&B.elem[j])
{
if(A.elem[i]<B.elem[j]) i++;
if(A.elem[i]>B.elem[j]) j++;
if(A.elem[i]==B.elem[j])
{
C.elem[++k]=A.elem[i]; //褰揿彂鐜颁简涓涓鍦ˋ,B涓閮藉瓨鍦ㄧ殑鍏幂礌,
i++;j++; //灏辨坊锷犲埌C涓
}
}//while
}//SqList_Intersect
2.26
void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//鍦ㄩ摼琛ㄧ粨鏋勪笂閲嶅仛涓婇
{
p=A->next;q=B->next;
pc=(LNode*)malloc(sizeof(LNode));
while(p&&q)
{
if(p->data<q->data) p=p->next;
else if(p->data>q->data) q=q->next;
else
{
s=(LNode*)malloc(sizeof(LNode));
s->data=p->data;
pc->next=s;pc=s;
p=p->next;q=q->next;
}
}//while
C=pc;
}//LinkList_Intersect
2.27
void SqList_Intersect_True(SqList &A,SqList B)//姹傚厓绱犻掑炴帓鍒楃殑绾挎ц〃A鍜孊镄勫厓绱犵殑浜ら泦骞跺瓨锲濧涓
{
i=1;j=1;k=0;
while(A.elem[i]&&B.elem[j])
{
if(A.elem[i]<B.elem[j]) i++;
else if(A.elem[i]>B.elem[j]) j++;
else if(A.elem[i]!=A.elem[k])
{
A.elem[++k]=A.elem[i]; //褰揿彂鐜颁简涓涓鍦ˋ,B涓閮藉瓨鍦ㄧ殑鍏幂礌
i++;j++; //涓擟涓娌℃湁,灏辨坊锷犲埌C涓
}
}//while
while(A.elem[k]) A.elem[k++]=0;
}//SqList_Intersect_True
2.28
void LinkList_Intersect_True(LinkList &A,LinkList B)//鍦ㄩ摼琛ㄧ粨鏋勪笂閲嶅仛涓婇
{
p=A->next;q=B->next;pc=A;
while(p&&q)
{
if(p->data<q->data) p=p->next;
else if(p->data>q->data) q=q->next;
else if(p->data!=pc->data)
{
pc=pc->next;
pc->data=p->data;
p=p->next;q=q->next;
}
}//while
}//LinkList_Intersect_True
2.29
void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)
{
i=0;j=0;k=0;m=0; //i鎸囩ずA涓鍏幂礌铡熸潵镄勪綅缃,m涓虹Щ锷ㄥ悗镄勪綅缃
while(i<A.length&&j<B.length&& k<C.length)
{
if(B.elem[j]<C.elem[k]) j++;
else if(B.elem[j]>C.elem[k]) k++;
else
{
same=B.elem[j]; //镓惧埌浜嗙浉钖屽厓绱爏ame
while(B.elem[j]==same) j++;
while(C.elem[k]==same) k++; //j,k钖庣Щ鍒版柊镄勫厓绱
while(i<A.length&&A.elem[i]<same)
A.elem[m++]=A.elem[i++]; //闇淇濈暀镄勫厓绱犵Щ锷ㄥ埌鏂颁綅缃
while(i<A.length&&A.elem[i]==same) i++; //璺宠繃鐩稿悓镄勫厓绱
}
}//while
while(i<A.length)
A.elem[m++]=A.elem[i++]; //A镄勫墿浣椤厓绱犻吨鏂板瓨鍌ㄣ
A.length=m;
}// SqList_Intersect_Delete
鍒嗘瀽:鍏堜粠B鍜孋涓镓惧嚭鍏辨湁鍏幂礌,璁颁负same,鍐嶅湪A涓浠庡綋鍓崭綅缃寮濮, 鍑″皬浜巗ame镄
鍏幂礌鍧囦缭鐣(瀛桦埌鏂扮殑浣岖疆),绛変簬same镄勫氨璺宠繃,鍒板ぇ浜巗ame镞跺氨鍐嶆垒涓嬩竴涓狲ame.
2.30
void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)//鍦ㄩ摼琛ㄧ粨鏋勪笂閲嶅仛涓婇
{
p=B->next;q=C->next;r=A-next;
while(p&&q&&r)
{
if(p->data<q->data) p=p->next;
else if(p->data>q->data) q=q->next;
else
{
u=p->data; //纭瀹氩緟鍒犻櫎鍏幂礌u
while(r->next->data<u) r=r->next; //纭瀹氭渶钖庝竴涓灏忎簬u镄勫厓绱犳寚阍坮
if(r->next->data==u)
{
s=r->next;
while(s->data==u)
{
t=s;s=s->next;free(t); //纭瀹氱涓涓澶т簬u镄勫厓绱犳寚阍坰
}//while
r->next=s; //鍒犻櫎r鍜宻涔嬮棿镄勫厓绱
}//if
while(p->data=u) p=p->next;
while(q->data=u) q=q->next;
}//else
}//while
}//LinkList_Intersect_Delete
2.31
Status Delete_Pre(CiLNode *s)//鍒犻櫎鍗曞惊鐜阈捐〃涓缁撶偣s镄勭洿鎺ュ墠椹
{
p=s;
while(p->next->next!=s) p=p->next; //镓惧埌s镄勫墠椹辩殑鍓嶉┍p
p->next=s;
return OK;
}//Delete_Pre
2.32
Status DuLNode_Pre(DuLinkList &L)//瀹屾垚鍙屽悜寰鐜阈捐〃缁撶偣镄刾re锘
{
for(p=L;!p->next->pre;p=p->next) p->next->pre=p;
return OK;
}//DuLNode_Pre
2.33
Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//鎶婂崟阈捐〃L镄勫厓绱犳寜绫诲瀷鍒嗕负涓変釜寰鐜阈捐〃.CiList涓哄甫澶寸粨镣圭殑鍗曞惊鐜阈捐〃绫诲瀷.
{
s=L->next;
A=(CiList*)malloc(sizeof(CiLNode));p=A;
B=(CiList*)malloc(sizeof(CiLNode));q=B;
C=(CiList*)malloc(sizeof(CiLNode));r=C; //寤虹珛澶寸粨镣
while(s)
{
if(isalphabet(s->data))
{
p->next=s;p=s;
}
else if(isdigit(s->data))
{
q->next=s;q=s;
}
else
{
r->next=s;r=s;
}
}//while
p->next=A;q->next=B;r->next=C; //瀹屾垚寰鐜阈捐〃
}//LinkList_Divide
2.34
void Print_XorLinkedList(XorLinkedList L)//浠庡乏钖戝彸杈揿嚭寮傛垨阈捐〃镄勫厓绱犲
{
p=L.left;pre=NULL;
while(p)
{
printf("%d",p->data);
q=XorP(p->LRPtr,pre);
pre=p;p=q; //浠讳綍涓涓缁撶偣镄凩RPtr锘熷间笌鍏跺乏缁撶偣鎸囬拡杩涜屽纾鎴栬繍绠楀嵆寰楀埌鍏跺彸缁撶偣鎸囬拡
}
}//Print_XorLinkedList
2.35
Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//鍦ㄥ纾鎴栭摼琛↙镄勭琲涓鍏幂礌鍓嶆彃鍏ュ厓绱爔
{
p=L.left;pre=NULL;
r=(XorNode*)malloc(sizeof(XorNode));
r->data=x;
if(i==1) //褰撴彃鍏ョ偣鍦ㄦ渶宸﹁竟镄勬儏鍐
{
p->LRPtr=XorP(p.LRPtr,r);
r->LRPtr=p;
L.left=r;
return OK;
}
j=1;q=p->LRPtr; //褰撴彃鍏ョ偣鍦ㄤ腑闂寸殑𨱍呭喌
while(++j<i&&q)
{
q=XorP(p->LRPtr,pre);
pre=p;p=q;
}//while //鍦╬,q涓ょ粨镣逛箣闂存彃鍏
if(!q) return INFEASIBLE; //i涓嶅彲浠ヨ秴杩囱〃闀
p->LRPtr=XorP(XorP(p->LRPtr,q),r);
q->LRPtr=XorP(XorP(q->LRPtr,p),r);
r->LRPtr=XorP(p,q); //淇鏀规寚阍
return OK;
}//Insert_XorLinkedList
2.36
Status Delete_XorLinkedList(XorlinkedList &L,int i)//鍒犻櫎寮傛垨阈捐〃L镄勭琲涓鍏幂礌
{
p=L.left;pre=NULL;
if(i==1) //鍒犻櫎链宸︾粨镣圭殑𨱍呭喌
{
q=p->LRPtr;
q->LRPtr=XorP(q->LRPtr,p);
L.left=q;free(p);
return OK;
}
j=1;q=p->LRPtr;
while(++j<i&&q)
{
q=XorP(p->LRPtr,pre);
pre=p;p=q;
}//while //镓惧埌寰呭垹缁撶偣q
if(!q) return INFEASIBLE; //i涓嶅彲浠ヨ秴杩囱〃闀
if(L.right==q) //q涓烘渶鍙崇粨镣圭殑𨱍呭喌
{
p->LRPtr=XorP(p->LRPtr,q);
L.right=p;free(q);
return OK;
}
r=XorP(q->LRPtr,p); //q涓轰腑闂寸粨镣圭殑𨱍呭喌,姝ゆ椂p,r鍒嗗埆涓哄叾宸﹀彸缁撶偣
p->LRPtr=XorP(XorP(p->LRPtr,q),r);
r->LRPtr=XorP(XorP(r->LRPtr,q),p); //淇鏀规寚阍
free(q);
return OK;
}//Delete_XorLinkedList
2.37
void OEReform(DuLinkedList &L)//鎸1,3,5,...4,2镄勯‘搴忛吨鎺掑弻钖戝惊鐜阈捐〃L涓镄勬墍链夌粨镣
{
p=L.next;
while(p->next!=L&&p->next->next!=L)
{
p->next=p->next->next;
p=p->next;
} //姝ゆ椂p鎸囧悜链钖庝竴涓濂囨暟缁撶偣
if(p->next==L) p->next=L->pre->pre;
else p->next=l->pre;
p=p->next; //姝ゆ椂p鎸囧悜链钖庝竴涓锅舵暟缁撶偣
while(p->pre->pre!=L)
{
p->next=p->pre->pre;
p=p->next;
}
p->next=L; //鎸夐樼洰瑕佹眰璋冩暣浜唍ext阈剧殑缁撴瀯,姝ゆ椂pre阈句粛涓哄师鐘
for(p=L;p->next!=L;p=p->next) p->next->pre=p;
L->pre=p; //璋冩暣pre阈剧殑缁撴瀯,钖2.32鏂规硶
}//OEReform
鍒嗘瀽:next阈惧拰pre阈剧殑璋冩暣鍙鑳藉垎寮杩涜.濡傚悓镞惰繘琛岃皟鏁寸殑璇,蹇呴’浣跨敤鍫嗘爤淇濆瓨锅舵暟缁撶偣镄勬寚阍,钖﹀垯灏嗕细镰村潖阈捐〃缁撴瀯,阃犳垚缁撶偣涓㈠け.
2.38
DuLNode * Locate_DuList(DuLinkedList &L,int x)//甯freq锘熺殑鍙屽悜寰鐜阈捐〃涓婄殑镆ユ垒
{
p=L.next;
while(p.data!=x&&p!=L) p=p->next;
if(p==L) return NULL; //娌℃垒鍒
p->freq++;q=p->pre;
while(q->freq<=p->freq) q=q->pre; //镆ユ垒鎻掑叆浣岖疆
if(q!=p->pre)
{
p->pre->next=p->next;p->next->pre=p->pre;
q->next->pre=p;p->next=q->next;
q->next=p;p->pre=q; //璋冩暣浣岖疆
}
return p;
}//Locate_DuList
2.39
float GetValue_SqPoly(SqPoly P,int x0)//姹傚崌骞傞‘搴忓瓨鍌ㄧ殑绋鐤忓氶”寮忕殑鍊
{
PolyTerm *q;
xp=1;q=P.data;
sum=0;ex=0;
while(q->coef)
{
while(ex<q->exp) xp*=x0;
sum+=q->coef*xp;
q++;
}
return sum;
}//GetValue_SqPoly
2.40
void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//姹傜█鐤忓氶”寮厮1鍑厮2镄勫樊寮厮3
{
PolyTerm *p,*q,*r;
Create_SqPoly(P3); //寤虹珛绌哄氶”寮厮3
p=P1.data;q=P2.data;r=P3.data;
while(p->coef&&q->coef)
{
if(p->exp<q->exp)
{
r->coef=p->coef;
r->exp=p->exp;
p++;r++;
}
else if(p->exp<q->exp)
{
r->coef=-q->coef;
r->exp=q->exp;
q++;r++;
}
else
{
if((p->coef-q->coef)!=0) //鍙链夊悓娆￠”鐩稿噺涓崭负闆舵椂镓嶉渶瑕佸瓨鍏P3涓
{
r->coef=p->coef-q->coef;
r->exp=p->exp;r++;
}//if
p++;q++;
}//else
}//while
while(p->coef) //澶勭悊P1鎴朠2镄勫墿浣欓”
{
r->coef=p->coef;
r->exp=p->exp;
p++;r++;
}
while(q->coef)
{
r->coef=-q->coef;
r->exp=q->exp;
q++;r++;
}
}//Subtract_SqPoly
2.41
void QiuDao_LinkedPoly(LinkedPoly &L)//瀵规湁澶寸粨镣瑰惊鐜阈捐〃缁撴瀯瀛桦偍镄勭█鐤忓氶”寮廘姹傚
{
p=L->next;
if(!p->data.exp)
{
L->next=p->next;p=p->next; //璺宠繃甯告暟椤
}
while(p!=L)
{
p->data.coef*=p->data.exp--;//瀵规疮涓椤规眰瀵
p=p->next;
}
}//QiuDao_LinkedPoly
2.42
void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//鎶婂惊鐜阈捐〃瀛桦偍镄勭█鐤忓氶”寮廘𨰾嗘垚鍙钖濂囨￠”镄𪞝鍜屽彧钖锅舵￠”镄凚
{
p=L->next;
A=(PolyNode*)malloc(sizeof(PolyNode));
B=(PolyNode*)malloc(sizeof(PolyNode));
pa=A;pb=B;
while(p!=L)
{
if(p->data.exp!=2*(p->data.exp/2))
{
pa->next=p;pa=p;
}
else
{
pb->next=p;pb=p;
}
p=p->next;
}//while
pa->next=A;pb->next=B;
}//Divide_LinkedPoly