數據結構嚴蔚敏源碼

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