數據結構與演算法分析c語言描述答案

❶ 急需數據結構C語言版（清華大學出版社）的期末考試試題及答案

《數據結構》期末考試試卷（ A ）

一、 選擇題（每小題2分，共24分）
1．計算機識別、存儲和加工處理的對象被統稱為( A )
A.數據 B.數據元素
C.數據結構 D.數據類型
2．棧和隊列都是（ A ）
A．限制存取位置的線性結構 B．順序存儲的線性結構
C．鏈式存儲的線性結構 D．限制存取位置的非線性結構
3．鏈棧與順序棧相比，比較明顯的優點是( D )
A.插入操作更加方便 B.刪除操作更加方便
C.不會出現下溢的情況 D.不會出現上溢的情況
4．採用兩類不同存儲結構的字元串可分別簡稱為( B )
A.主串和子串 B.順序串和鏈串
C.目標串和模式串 D.變數串和常量串
5． 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是：B
A. 110 B .108
C. 100 D. 120
6．串是一種特殊的線性表，其特殊性體現在：B
A.可以順序存儲 B .數據元素是一個字元
C. 可以鏈接存儲 D. 數據元素可以是多個字元
7．設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為： C
A. 2h B .2h-1
C. 2h+1 D. h+1
軟體開發網
8．樹的基本遍歷策略可分為先根遍歷和後根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和後序遍歷。這里，我們把 由樹轉化得到的二叉樹叫做這棵樹對應的二叉樹。下列結論哪個正確？ A
A. 樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同
B .樹的後根遍歷序列與其對應的二叉樹的後序遍歷序列相同
C. 樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同
D. 以上都不對
9．一個有n個頂點的無向圖最多有多少邊？C
A. n B .n(n-1)
C. n(n-1)/2 D. 2n
10．在一個圖中，所有頂點的度數之和等於所有邊數的多少倍?C
A. 1/2 B .1
C. 2 D. 4
11．當在二叉排序樹中插入一個新結點時，若樹中不存在與待插入結點的關鍵字相同的結點，且新結點的關鍵字小於根結點的關鍵字，則新結點將成為（ A ）
A．左子樹的葉子結點 B．左子樹的分支結點
C．右子樹的葉子結點 D．右子樹的分支結點
軟體開發網
12．對於哈希函數H(key)=key%13,被稱為同義詞的關鍵字是( D )
A.35和41 B.23和39
C.15和44 D.25和51
二、已知某棵二叉樹的前序遍歷結果為A,B,D,E,G,C,F,H,I,J，其中中序遍歷的結果為D,B,G,E,A,H,F,I,J,C。請畫出二叉的具體結構。（注意要寫出具體步驟）（10分）
原理見課本128頁

三、有圖如下，請寫出從頂點c0出發的深度優先及寬度優先遍歷的結果。(10分)
深度優先；C0-C1-C3-C4-C5-C2
寬度優先：C0-C1-C2-C3-C4-C5
四、有圖如下，按Kruskal演算法求出其最小生成樹。要求寫出完整的步驟。（10分）
原理見課本250頁

五、給定線性表（12，23，45，66，76，88，93，103，166），試寫出在其上進行二分查找關鍵字值12，93，166的過程。並寫出二分查找的演算法。（20分）
0 1 2 3 4 5 6 7 8
12 23 45 66 76 88 93 103 166
過程：
mid=(0+8)/2=4
high=3,low=0 mid=1
high=0,low=0 mid=0（找到12）
high=8,low=5,mid=6（找到93）
high=8,low=7,mid=7
high=8 low=8 mid=8
演算法：見課本84頁上

六、知單鏈表的結點結構為
Data next
下列演算法對帶頭結點的單鏈表L進行簡單選擇排序，使得L中的元素按值從小到大排列。
請在空缺處填入合適的內容，使其成為完整的演算法。 (可用文字說明該演算法的基本思想及執行的過程，10分)
void SelectSort(LinkedList L)
{
LinkedList p,q,min;
DataType rcd;
p= (1) ;
while(p!=NULL) {
min=p;
q=p->next;
while(q!=NULL){
if( (2) )min=q;
q=q->next;
}
if( (3) ){
rcd=p->data;
p->data=min->data;
min->data=rcd;
}
(4) ;
}
}
本題不會。嘿嘿。。。。
七、一個完整的演算法應該具有哪幾個基本性質？分別簡要說明每一性質的含意。(5分)
輸入：
四個基本性質：1.輸入：有零個或多個有外部提供的量作為演算法的輸入
2：輸出：演算法產生至少一個量作為輸出
3.：確定性：組成演算法的每條指令是清晰的，無歧異的。
4.：有限性：演算法中每條指令的執行次數是有限的，執行每條指令的時間也是有限的

八、何謂隊列的"假溢"現象？如何解決？（5分）
隊列的假溢現象是指數組實現的順序隊列中，隊尾指針已到達數組的下表上界產生上溢而隊頭指針之前還有若干 空間閑置的現象。解決的辦法之一是利用循環隊列技術使數組空間的首尾相連。

九、說明並比較文件的各種物理結構。（6分）

❷ c語言數據結構（考題，測試你的能力）－－編寫源代碼

P88 稀疏矩陣十字鏈表相加演算法如下：
/*假設ha為A稀疏矩陣十字鏈表的頭指針，hb為B稀疏矩陣十字鏈表的頭指針*/
#include<stdio.h>
#define maxsize 100
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext
{ int v;
struct linknode *next;} k;
};

struct linknode creatlindmat( ) /*建立十字鏈表*/
{ int x, m, n, t, s, i, j, k;
struct linknode *p , *q, *cp[maxsize],*hm;
printf("請輸入稀疏矩陣的行、列數及非零元個數\n");
scanf("%d%d%d",&m,&n,&t);
if (m>n) s=m; else s=n;
hm=(struct linknode*)malloc(sizeof(struct linknode)) ;
hm->i=m; hm->j=n;
cp[0]=hm;
for (i=1; i<=s;i++)
{ p=(struct linknode*)malloc(sizeof(struct linknode)) ;
p->i=0; p->j=0;
p->rptr=p; p->cptr=p;
cp[i]=p;
cp[i-1]->k.next=p;
}
cp[s]->k.next=hm;
for( x=1;x<=t;x++)
{ printf("請輸入一個三元組(i,j,v)\n");
scanf("%d%d%d",&i,&j,&k);
p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=i; p->j=j; p->k.v=k;
/*以下是將p插入到第i行鏈表中 */
q=cp[i];
while ((q->rptr!=cp[i]) &&( q->rptr->j<j))
q=q->rptr;
p->rptr=q->rptr;
q->rptr=p;
/*以下是將P插入到第j列鏈表中*/
q=cp[j];
while((q->cptr!=cp[j]) &&( q->cptr->i<i))
q=q->cptr;
p->cptr=q->cptr;
q->cptr=p;
}
return hm;
}
/* ha和hb表示的兩個稀疏矩陣相加，相加的結果放入ha中*/
struct linknode *matadd(struct linknode *ha, struct linknode *hb)
{ struct linknode *pa, *pb, *qa, *ca,*cb,*p,*q;
struct linknode *hl[maxsize];
int i , j, n;
if((ha->i!=hb->i)||(ha->j!=hb->j))
printf("矩陣不匹配,不能相加\n");
else
{ p=ha->k.next; n=ha->j;
for (i=1;i<=n; i++)
{ hl[i]=p;
p=p->k.next;
}
ca=ha->k.next; cb=hb->k.next;
while(ca->i==0)
{pa=ca->rptr; pb=cb->rptr;
qa=ca;
while(pb->j!=0)
{ if((pa->j<pb->j)&&(pa->j!=0))
{ qa=pa; pa=pa->rptr;}
else if ((pa->j>pb->j)||(pa->j==0)) /*插入一個結點*/
{ p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=pb->i; p->j=pb->j;
p->k.v=pb->k.v;
qa->rptr=p; p->rptr=pa;
qa=p; pb=pb->rptr;
j=p->j; q=hl[j]->cptr;
while((q->i<p->i)&&(q->i!=0))
{ hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=p; p->cptr=q;
hl[j]=p;
}
else
{pa->k.v=pa->k.v+pb->k.v;
if(pa->k.v==0) /*刪除一個結點*/
{ qa->rptr=pa->rptr;
j=pa->j; q=hl[j]->cptr;
while (q->i<pa->i)
{hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=q->cptr;
pa=pa->rptr; pb=pb->rptr;
free(q);
}
else
{ qa=pa; pa=pa->rptr;
pb=pb->rptr;
}
}
}
ca=ca->k.next; cb=cb->k.next;
}
}
return ha;
}
void print(struct linknode *ha) /*輸出十字鏈表*/
{ struct linknode *p,*q;
p=ha->k.next;
while(p->k.next!=ha)
{ q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
p=p->k.next;
}
q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
}

void main()
{
struct linknode *ha=NULL,*hb=NULL,*hc=NULL;
ha=creatlindmat( ); /*生成一個十字鏈表ha*/
hb=creatlindmat( ); /*生成另一個十字鏈表hb*/
printf("A:\n"); /*輸出十字鏈表ha*/
print(ha);printf("\n");
printf("B:\n"); /*輸出十字鏈表hb*/
print(hb);printf("\n");
hc=matadd(ha,hb); /*十字鏈表相加*/
printf("A+B:\n"); /*輸出相加後的結果*/
print(hc);printf("\n");
}

P94 數據類型描述如下：
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
}

P95 數據類型描述如下：
struct node2
{ elemtype data;
struct node2 *link1,*link2;
}

P96 求廣義表的深度depth(LS)
int depth(struct node1 *LS)
{
int max=0,dep;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}

P96 廣義表的建立creat(LS)
void creat(struct node1 *LS)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node*)malloc(sizeof(struct node));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node*)malloc(sizeof(struct node));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}

P97 輸出廣義表print(LS)
void print(struct node1 *LS)
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c ",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}

P98 該演算法的時間復雜度為O(n)。整個完整程序如下：
#include<stdio.h>
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
};

void creat(struct node1 LS) /*建立廣義表的單鏈表*/
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}
void print(struct node1 LS) /*輸出廣義單鏈表*/
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}
int depth(struct node1 LS) /*求廣義表的深度*/
{
int max=0;
while(LS!=NULL)
{ if(LS->atom==0)
{ int dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
main()
{ int dep;
struct node1 *p=NULL;
creat(p); /*建立廣義表的單鏈表*/
print(p); /*輸出廣義單鏈表*/
dep=depth(p); /*求廣義表的深度*/
printf("%d\n",dep);
}

第六章 樹
P109 二叉鏈表的結點類型定義如下：
typedef struct btnode
{ anytype data;
struct btnode *Lch,*Rch;
}tnodetype;

P109 三叉鏈表的結點類型定義如下：
typedef struct btnode3
{ anytype data;
struct btnode *Lch,*Rch，*Parent ;
}tnodetype3;

P112 C語言的先序遍歷演算法：
void preorder (tnodetype *t)
/*先序遍歷二叉樹演算法，t為指向根結點的指針*/
{ if (t!=NULL)
{printf("%d ",t->data);
preorder(t->lch);
preorder(t->rch);
}
}

P113 C語言的中序遍歷演算法：
void inorder(tnodetype *t)
/*中序遍歷二叉樹演算法，t為指向根結點的指針*/
{
if(t!=NULL)
{inorder(t->lch);
printf("%d ",t->data);
inorder(t->rch);
}
}

P113 C語言的後序遍歷演算法：
void postorder(tnodetype *t)
/*後序遍歷二叉樹演算法，t為指向根結點的指針*/
{
if(t!=NULL)
{ postorder(t->lch);
postorder(t->rch);
printf("%d ",t->data);
}
}

P114 如果引入隊列作為輔助存儲工具，按層次遍歷二叉樹的演算法可描述如下：
void levelorder(tnodetype *t)
/*按層次遍歷二叉樹演算法，t為指向根結點的指針*/
{tnodetype q[20]; /*輔助隊列*/
front=0;
rear=0; /*置空隊列*/
if (t!=NULL)
{ rear++;
q[rear]=t; /*根結點入隊*/
}
while (front!=rear)
{ front++;
t=q [front];
printf ("%c\n",t->data);
if (t->lch!=NULL) /*t的左孩子不空，則入隊*/
{ rear++;
q [rear]=t->lch;
}
if (t->rch!=NULL) /*t的右孩子不空，則入隊*/
{ rear++;
q [rear]=t->rch;
}
}
}

P115 以中序遍歷的方法統計二叉樹中的結點數和葉子結點數，演算法描述為：
void inordercount (tnodetype *t)
/*中序遍歷二叉樹，統計樹中的結點數和葉子結點數*/
{ if (t!=NULL)
{ inordercount (t->lch); /*中序遍歷左子樹*/
printf ("%c\n",t->data); /*訪問根結點*/
countnode++; /*結點計數*/
if ((t->lch==NULL)&&(t->rch==NULL))
countleaf++; /*葉子結點計數*/
inordercount (t->rch); /*中序遍歷右子樹*/
}
}

P115 可按如下方法計算一棵二叉樹的深度：
void preorderdeep (tnodetype *t,int j)
/*先序遍歷二叉樹，並計算二叉樹的深度*/
{ if (t!=NULL)
{ printf ("%c\n",t->data); /*訪問根結點*/
j++;
if (k<j) k=j;
preorderdeep (t->lch,j); /*先序遍歷左子樹*/
preorderdeep (t->rch,j); /*先序遍歷右子樹*/
}
}

P117 線索二叉樹的結點類型定義如下：
struct nodexs
{anytype data;
struct nodexs *lch, *rch;
int ltag,rtag; /*左、右標志域*/
}

P117 中序次序線索化演算法
void inorderxs (struct nodexs *t)
/*中序遍歷t所指向的二叉樹，並為結點建立線索*/
{ if (t!=NULL)
{ inorderxs (t->lch);
printf ("%c\n",t->data);
if (t->lch!=NULL)
t->ltag=0;
else { t->ltag=1;
t->lch=pr;
} /*建立t所指向結點的左線索，令其指向前驅結點pr*/
if (pr!=NULL)
{ if (pr->rch!=NULL)
pr->rtag=0;
else { pr->rtag=1;
pr->rch=p;
}
} /*建立pr所指向結點的右線索，令其指向後繼結點p*/
pr=p;
inorderxs (t->rch);
}
}

P118 在中根線索樹上檢索某結點的前驅結點的演算法描述如下：
struct nodexs * inpre (struct nodexs *q)
/*在中根線索樹上檢索q所指向的結點的前驅結點*/
{ if (q->ltag==1)
p=q->lch;
else { r=q->lch;
while (r->rtag!=1)
r=r->rch;
p=r;
}
return (p);
}

P119 在中根線索樹上檢索某結點的後繼結點的演算法描述如下：
struct nodexs * insucc (struct nodexs *q)
/*在中根線索樹上檢索q所指向的結點的後繼結點*/
{ if (q->rtag==1)
p=q->rch;
else { r=q->rch;
while (r->ltag!=1)
r=r->lch;
p=r;
}
return (p);
}

P120 演算法程序用C語言描述如下：
void sortBT(BT *t,BT *s) /*將指針s所指的結點插入到以t為根指針的二叉樹中*/
{ if (t==NULL) t=s; /*若t所指為空樹，s所指結點為根*/
else if (s->data < t->data)
sortBT(t->lch,s); /*s結點插入到t的左子樹上去*/
else
sortBT(t->rch,s); /*s結點插入到t的右子樹上去*/
}

P121 二叉排序樹結點刪除演算法的C語言描述如下：
void delnode(bt,f,p)
/*bt為一棵二叉排序樹的根指針，p指向被刪除結點，f指向其雙親*/
/*當p=bt時f為NULL*/
{ fag=0; /*fag=0時需修改f指針信息，fag=1時不需修改*/
if (p->lch==NULL)
s=p->rch; /*被刪除結點為葉子或其左子樹為空*/
else if (p->rch==NULL)
s=p->lch;
else { q=p; /*被刪除結點的左、右子樹均非空*/
s=p->lch;
while (s->rch!=NULL)
{ q=s;
s=s->rch;
} /*尋找s結點*/
if (q=p)
q->lch=s->lch;
else q->rch=s->lch;
p->data=s->data; /*s所指向的結點代替被刪除結點*/
DISPOSE(s);
Fag=1;
}
if (fag=0) /*需要修改雙親指針*/
{ if (f=NULL)
bt=s; /*被刪除結點為根結點*/
else if (f->lch=p)
f->lch=s;
else f->rch=s;
DISPOSE(p); /*釋放被刪除結點*/
}
}

第七章 圖
P134 用鄰接矩陣表示法表示圖，除了存儲用於表示頂點間相鄰關系的鄰接矩陣外，通常還需要用一個順序表來存儲頂點信息。其形式說明如下：
# define n 6 /*圖的頂點數*/
# define e 8 /*圖的邊(弧)數*/
typedef char vextype; /*頂點的數據類型*/
typedef float adjtype; /*權值類型*/
typedef struct
{vextype vexs[n];
adjtype arcs[n][n];
}graph;

P135 建立一個無向網路的演算法。
CREATGRAPH(ga) /*建立無向網路*/
Graph * ga;
{
int i,j,k;
float w;
for(i＝0;i<n;i++ )
ga ->vexs[i]＝getchar(); /*讀入頂點信息，建立頂點表*/
for(i＝0;i<n;i++ )
for(j＝0;j<n;j++)
ga ->arcs[i][j]＝0; /*鄰接矩陣初始化*/
for(k＝0;k<e;k++) /*讀入e條邊*/
(scanf("％d％d％f",&I,&j,&w); /*讀入邊(vi,vj)上的權w */
ga ->arcs[i][j]＝w;
ga - >arcs[j][i]＝w;
}
} /*CREATGRAPH*/

P136 鄰接表的形式說明及其建立演算法：
typedef struct node
{int adjvex; /*鄰接點域*/
struct node * next; /*鏈域*/
}edgenode; /*邊表結點*/
typedef struct
{vextype vertex; /*頂點信息*/
edgenode link; /*邊表頭指針*/
}vexnode; /*頂點表結點*/
vexnode ga[n];

CREATADJLIST(ga) /*建立無向圖的鄰接表*/
Vexnode ga[ ];
{int i,j,k;
edgenode * s;
for(i=o;i<n;i++＝ /*讀入頂點信息*/
(ga[i].vertex＝getchar();
ga[i].1ink＝NULL; /*邊表頭指針初始化*/
}
for(k＝0;k<e;k++＝ /*建立邊表*/
{scanf("％d％d",&i,&j); /*讀入邊(vi , vj)的頂點對序號*/
s＝malloc(sizeof(edgenode)); /*生成鄰接點序號為j的表結點*s */
s-> adjvex＝j;
s- - >next：＝ga[i].Link;
ga[i].1ink＝s; /*將*s插入頂點vi的邊表頭部*/
s＝malloc(size0f(edgende)); /*生成鄰接點序號為i的邊表結點*s */
s ->adjvex＝i;
s ->next＝ga[j].1ink;
ga[j].1ink＝s; /*將*s插入頂點vj的邊表頭部*/
}
} /* CREATADJLIST */

P139 分別以鄰接矩陣和鄰接表作為圖的存儲結構給出具體演算法，演算法中g、g1和visited為全程量，visited的各分量初始值均為FALSE。
int visited[n] /*定義布爾向量visitd為全程量*/
Graph g; /*圖g為全程量*/

DFS(i) /*從Vi+1出發深度優先搜索圖g，g用鄰接矩陣表示*/
int i;
{ int j;
printf("node：％c＼n" , g.vexs[i]); /*訪問出發點vi+1 */
Visited[i]＝TRUE; /*標記vi+l已訪問過*/
for (j＝0;j<n;j++) /*依次搜索vi+1的鄰接點*/
if((g.arcs[i][j]＝＝1) ＆＆(! visited[j]))
DFS(j); /*若Vi+l的鄰接點vj+l未曾訪問過，則從vj+l出發進行深度優先搜索*/
} /*DFS*/
vexnode gl[n] /*鄰接表全程量*/

DFSL(i) /*從vi+l出發深度優先搜索圖g1，g1用鄰接表表示*/
int i;
{ int j;
edgenode * p;
printf("node：％C\n" ,g1[i].vertex);
vistited[i]＝TRUE;
p＝g1[i].1ink; /*取vi+1的邊表頭指針*/
while(p !＝NULL) /*依次搜索vi+l的鄰接點*/
{
if(! Vistited[p ->adjvex])
DFSL(p - >adjvex); /*從vi+1的未曾訪問過的鄰接點出發進行深度優先搜索*/
p＝p - >next; /*找vi+l的下一個鄰接點*/
}
} /* DFSL */

P142 以鄰接矩陣和鄰接表作為圖的存儲結構，分別給出寬度優先搜索演算法。
BFS(k) /＊從vk+l出發寬度優先搜索圖g，g用鄰接矩陣表示，visited為訪問標志向量*/
int k;
{ int i,j;
SETNULL(Q); /*置空隊Q */
printf("％c＼n"，g.vexs[k]); /*訪問出發點vk+l*x/
visited[k]＝TRUE; /*標記vk+l已訪問過*/
ENQUEUE(Q，K); /*已訪問過的頂點(序號)入隊列*/
While(!EMPTY(Q)) /*隊非空時執行*/
{i＝DEQUEUE(Q); /*隊頭元素序號出隊列*/
for(j＝0;j<n;j++)
if((g.arcs[i][j]＝＝1)＆＆(! visited[j]))
{printf("％c＼n" , g.vexs[j]); /*訪問vi+l的未曾訪問的鄰接點vj+l */
visited[j]＝TRUE;
ENQUEUE(Q,j); /*訪問過的頂點入隊*/
}
}
} /* BFS */
BFSL(k) /*從vk+l出發寬度優先搜索圖g1，g1用鄰接表表示*/
int k
{ int i;
edgenode * p;
SETNULL(Q);
printf("％c＼n" , g1[k].vertex);
visited[k]＝TRUE;
ENQUEUE(Q,k);
while(! EMPTY(Q));
{ i＝DEQUEUE(Q);
p＝g1[i].1ink /*取vi+l的邊表頭指針*/
while(p !＝NULL) /*依次搜索vi+l的鄰接點*/
{ if( ! visited[p - >adjvex]) /*訪問vi+l的未訪問的鄰接點*/
{ printf{"％c＼n" , g1[p - >adjvex].vertex};
visited[p - >adjvex]＝TRUE;
ENQUEUE(Q,p - >adjvex); /*訪問過的頂點入隊*/
}
p＝p - >next; /*找vi+l的下一個鄰接點*/
}
}
} /*BFSL*/

P148 在對演算法Prim求精之前，先確定有關的存儲結構如下：
typdef struct
{Int fromvex，endvex; /*邊的起點和終點*/
float length; /*邊的權值*/
} edge;

float dist[n][n]; /*連通網路的帶權鄰接矩陣*/
edgeT[n-1]; /*生成樹*/

P149 抽象語句(1)可求精為：
for(j=1;j<n;j++) /*對n-1個藍點構造候選紫邊集*/
{T[j-1].fromvex＝1}; /*紫邊的起點為紅點*/
T[j-1].endvex＝j+1; /*紫邊的終點為藍點*/
T[j-1].1ength＝dist[0][j]; /*紫邊長度*/
}

P149 抽象語句(3)所求的第k條最短紫邊可求精為：
min＝max; /*znax大於任何邊上的權值*/
for (j＝k;j<n-1;j++) /*掃描當前候選紫邊集T[k]到T[n-2]，找最短紫邊*/
if(T[j].1ength<min)
{min＝T[j].1ength;m＝j; /*記錄當前最短紫邊的位置*/
}

P149 抽象語句(4)的求精：
e＝T[m];T[m]＝T[k];T[k]＝e， /* T[k]和T[m]交換*/
v＝T[kl.Endvex]; /* v是剛被塗紅色的頂點*/

P149 抽象語句(5)可求精為：
for(j＝k+1;j<n-1;j++) /*調整候選紫邊集T[k+1]到T[n-2]*/
{d＝dist[v-1][T[j].endvex-1]; /*新紫邊的長度*/
if(d<T[j].1ength) /*新紫邊的長度小於原最短紫邊*/
{T[j].1ength＝d;
T[j].fromvex＝v; /*新紫邊取代原最短紫邊*/
}
}

P150 完整的演算法：
PRIM() /*從第一個頂點出發構造連通網路dist的最小生成樹，結果放在T中*/
{int j , k , m , v , min , max＝l0000;
float d;
edge e;
for(j=1;j<n;j++) /*構造初始候選紫邊集*/
{T[j-1].formvex＝1; /*頂點1是第一個加入樹中的紅點*/
T[j-1].endvex＝j+1;
T[j-1].length＝dist[o][j];
}
for(k＝0;k<n-1;k++) /*求第k條邊*/
{min＝max;
for(j＝k;j<n-1;j++) /*在候選紫邊集中找最短紫邊*/
if(T[j].1ength<min)
{min＝T[j].1ength;
m＝j;
} /*T[m]是當前最短紫邊*/
}
e＝T[m];T[m]＝T[k];T[k]＝e; /*T[k]和T[m]交換後，T[k]是第k條紅色樹邊*/
v＝T[k].endvex ; /* v是新紅點*/
for(j＝k+1;j<n-1;j++) /*調整候選紫邊集*/
{d＝dist[v-1][T[j].endvex-1];
if(d<T[j].1ength);
{T[j].1ength＝d;
T[j].fromvex＝v;
}
}
} /* PRIM */

P151 Kruskl演算法的粗略描述：
T＝(V,φ);
While(T中所含邊數<n-1)
{從E中選取當前最短邊(u,v);
從E中刪去邊(u,v);
if((u,v)並入T之後不產生迴路，將邊(u,v)並入T中;
}

P153 迪傑斯特拉演算法實現。演算法描述如下：
#define max 32767 /*max代表一個很大的數*/
void dijkstra (float cost[][n],int v)
/*求源點v到其餘頂點的最短路徑及其長度*/
{ v1=v-1;
for (i=0;i<n;i++)
{ dist[i]=cost[v1][i]; /*初始化dist*/
if (dist[i]<max)
pre[i]=v;
else pre[i]=0;
}
pre[v1]=0;
for (i=0;i<n;i++)
s[i]=0; /*s數組初始化為空*/
s[v1]=1; /*將源點v歸入s集合*/
for (i=0;i<n;i++)
{ min=max;
for (j=0;j<n;j++)
if (!s[j] && (dist[j]<min))
{ min=dist[j];
k=j;
} /*選擇dist值最小的頂點k+1*/
s[k]=1; /*將頂點k+1歸入s集合中*/
for (j=0;j<n;j++)
if (!s[j]&&(dist[j]>dist[k]+cost[k][j]))
{ dist[j]=dist[k]+cost[k][j]; /*修改 V-S集合中各頂點的dist值*/
pre[j]=k+1; /*k+1頂點是j+1頂點的前驅*/
}
} /*所有頂點均已加入到S集合中*/
for (j=0;j<n;j++) /*列印結果*/
{ printf("%f\n%d",dist[j],j+1;);
p=pre[j];
while (p!=0)
{ printf("%d",p);
p=pre[p-1];
}
}
}

P155 弗洛伊德演算法可以描述為：
A(0)[i][j]=cost[i][j]; //cost為圖的鄰接矩陣
A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]}
其中 k=1,2,…,n

P155 弗洛伊德演算法實現。演算法描述如下：
int path[n][n]; /*路徑矩陣*/
void floyd (float A[][n],cost[][n])
{ for (i=0;i<n;i++) /*設置A和path的初值*/
for (j=0;j<n;j++)
{ if (cost[i][j]<max)
path[i][j]=j;
else { path[i][j]=0;
A[i][j]=cost[i][j];
}
}
for (k=0;k<n;k++)
/*做n次迭代，每次均試圖將頂點k擴充到當前求得的從i到j的最短路徑上*/
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (A[i][j]>(A[i][k]+A[k]

❸ 清華大學嚴蔚敏數據結構題集完整答案(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)//求k階斐波那契序列的第m項的值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++) //求出序列第k至第m個元素的值
{
sum=0;
for(j=i-k;j<i;j++) sum+=temp[j];
temp[i]=sum;
}
f=temp[m];
}
return OK;
}//fib
分析:通過保存已經計算出來的結果,此方法的時間復雜度僅為O(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])//求i!*2^i序列的值且不超過maxint
{
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
分析:當某一項的結果超過了maxint時,它除以前面一項的商會發生異常.
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的i次方
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中第i個元素起的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)//把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和B,並用返回值表示結果,值為正,表示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)//把鏈表hb接在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)//在無頭結點鏈表L的第i個元素之前插入元素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; //插入在第i個元素的位置
}
}//Insert
2.18
Status Delete(LinkList &L,int i)//在無頭結點鏈表L中刪除第i個元素
{
if(i==1) L=L->next; //刪除第一個元素
else
{
p=L;
while(--i>1) p=p->next;
p->next=p->next->next; //刪除第i個元素
}
}//Delete
2.19
Status Delete_Between(Linklist &L,int mink,int maxk)//刪除元素遞增排列的鏈表L中值大於mink且小於maxk的所有元素
{
p=L;
while(p->next->data<=mink) p=p->next; //p是最後一個不大於mink的元素
if(p->next) //如果還有比mink更大的元素
{
q=p->next;
while(q->data<maxk) q=q->next; //q是第一個不小於maxk的元素
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; //把L的元素逐個插入新表表頭
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse
分析:本演算法的思想是,逐個地把L的當前元素q插入新的鏈表頭部,p為新表表頭.
2.23
void merge1(LinkList &A,LinkList &B,LinkList &C)//把鏈表A和B合並為C,A和B的元素間隔排列,且使用原存儲空間
{
p=A->next;q=B->next;C=A;
while(p&&q)
{
s=p->next;p->next=q; //將B的元素插入
if(s)
{
t=q->next;q->next=s; //如A非空,將A的元素插入
}
p=s;q=t;
}//while
}//merge1
2.24
void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素遞增排列的鏈表A和B合並為C,且C中元素遞減排列,使用原空間
{
pa=A->next;pb=B->next;pre=NULL; //pa和pb分別指向A,B的當前元素
while(pa||pb)
{
if(pa->data<pb->data||!pb)
{
pc=pa;q=pa->next;pa->next=pre;pa=q; //將A的元素插入新表
}
else
{
pc=pb;q=pb->next;pb->next=pre;pb=q; //將B的元素插入新表
}
pre=pc;
}
C=A;A->next=pc; //構造新表頭
}//reverse_merge
分析:本演算法的思想是,按從小到大的順序依次把A和B的元素插入新表的頭部pc處,最後處理A或B的剩餘元素.
2.25
void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素遞增排列的線性表A和B的元素的交集並存入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]; //當發現了一個在A,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和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]; //當發現了一個在A,B中都存在的元素
i++;j++; //且C中沒有,就添加到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]; //找到了相同元素same
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和C中找出共有元素,記為same,再在A中從當前位置開始, 凡小於same的
元素均保留(存到新的位置),等於same的就跳過,到大於same時就再找下一個same.
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的元素指針r
if(r->next->data==u)
{
s=r->next;
while(s->data==u)
{
t=s;s=s->next;free(t); //確定第一個大於u的元素指針s
}//while
r->next=s; //刪除r和s之間的元素
}//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)//完成雙向循環鏈表結點的pre域
{
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; //任何一個結點的LRPtr域值與其左結點指針進行異或運算即得到其右結點指針
}
}//Print_XorLinkedList
2.35
Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在異或鏈表L的第i個元素前插入元素x
{
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 //在p,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的第i個元素
{
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; //按題目要求調整了next鏈的結構,此時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)//求稀疏多項式P1減P2的差式P3
{
PolyTerm *p,*q,*r;
Create_SqPoly(P3); //建立空多項式P3
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或P2的剩餘項
{
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)//對有頭結點循環鏈表結構存儲的稀疏多項式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)//把循環鏈表存儲的稀疏多項式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

❹ 我有兩道數據結構的問題 希望能給出詳細解答和做題步驟

數據結構與演算法的地位對於一個程序員來說不言而喻。今天這篇文章不是來勸你們學習數據結構與演算法的，也不是來和你們說數據結構與演算法有多重要。
主要是最近幾天後台有讀者問我是如何學習數據結構與演算法的，有沒有什麼捷徑，是要看視頻還是看書，去哪刷題等.....而且有些還是大三大四的，搞的我都替你們著急、擔心.....
所以我今天就分享下自己平時都是怎麼學習的。
學習演算法的捷徑就是多刷題
說實話，要說捷徑，我覺得就是腳踏實地著多動手去刷題，多刷題。
但是，如果你是小白，也就是說，你連常見的數據結構，如鏈表、樹以及常見的演算法思想，如遞歸、枚舉、動態規劃這些都沒學過，那麼，我不建議你去刷題的。而是先去找本書先去學習這些，然後再去刷題。
也就是說，假如你要去諸如leetcode這些網站刷題，那麼，你要先具備一定的基礎，這些基礎包括：
1、常見數據結構：鏈表、樹(如二叉樹)。
2、常見演算法思想：貪婪法、分治法、窮舉法、動態規劃，回溯法。
以上列出來的算是最基本的吧。就是說你刷題之前，要把這些過一遍再去刷題。如果你連這些最基本的都不知道的話，那麼你再刷題的過程中，會很難受的，思路也會相對比較少。
總之，千萬不要急，先把這些基本的過一遍，力求理解，再去刷題。這些基礎的數據結構與演算法，我是在大一第二學期學的，我沒看視頻，我是通過看書學的，那時候看的書是：
1、演算法分析與分析基礎：這本比較簡單，推薦新手看。
2、數據結構與演算法分析---C語言描述：代碼用C寫的，推薦看。
3、挑戰程序設計競賽(第二版)：也是很不錯的一本書，推薦看。