數據結構java課後答案

Ⅰ 求數據結構（java版）實驗樹和二叉樹題目答案

/**
* @param args
之前在大學的時候寫的一個二叉樹演算法，運行應該沒有問題，就看適不適合你的項目了 */
public static void main(String[] args) {

BiTree e = new BiTree(5);
BiTree g = new BiTree(7);
BiTree h = new BiTree(8);
BiTree l = new BiTree(12);
BiTree m = new BiTree(13);
BiTree n = new BiTree(14);
BiTree k = new BiTree(11, n, null);
BiTree j = new BiTree(10, l, m);
BiTree i = new BiTree(9, j, k);
BiTree d = new BiTree(4, null, g);
BiTree f = new BiTree(6, h, i);
BiTree b = new BiTree(2, d, e);
BiTree c = new BiTree(3, f, null);
BiTree tree = new BiTree(1, b, c);
System.out.println("遞歸前序遍歷二叉樹結果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("非遞歸前序遍歷二叉樹結果: ");
tree.iterativePreOrder(tree);
System.out.println();
System.out.println("遞歸中序遍歷二叉樹的結果為:");
tree.inOrder(tree);
System.out.println();
System.out.println("非遞歸中序遍歷二叉樹的結果為:");
tree.iterativeInOrder(tree);
System.out.println();
System.out.println("遞歸後序遍歷二叉樹的結果為:");
tree.postOrder(tree);
System.out.println();
System.out.println("非遞歸後序遍歷二叉樹的結果為:");
tree.iterativePostOrder(tree);
System.out.println();
System.out.println("層次遍歷二叉樹結果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("遞歸求二叉樹中所有結點的和為:"+getSumByRecursion(tree));
System.out.println("非遞歸求二叉樹中所有結點的和為:"+getSumByNoRecursion(tree));

System.out.println("二叉樹中,每個節點所在的層數為:");
for (int p = 1; p <= 14; p++)
System.out.println(p + "所在的層為:" + tree.level(p));
System.out.println("二叉樹的高度為:" + height(tree));
System.out.println("二叉樹中節點總數為:" + nodes(tree));
System.out.println("二叉樹中葉子節點總數為:" + leaf(tree));
System.out.println("二叉樹中父節點總數為:" + fatherNodes(tree));
System.out.println("二叉樹中只擁有一個孩子的父節點數:" + oneChildFather(tree));
System.out.println("二叉樹中只擁有左孩子的父節點總數:" + leftChildFather(tree));
System.out.println("二叉樹中只擁有右孩子的父節點總數:" + rightChildFather(tree));
System.out.println("二叉樹中同時擁有兩個孩子的父節點個數為:" + doubleChildFather(tree));
System.out.println("--------------------------------------");
tree.exChange();
System.out.println("交換每個節點的左右孩子節點後......");
System.out.println("遞歸前序遍歷二叉樹結果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("非遞歸前序遍歷二叉樹結果: ");
tree.iterativePreOrder(tree);
System.out.println();
System.out.println("遞歸中序遍歷二叉樹的結果為:");
tree.inOrder(tree);
System.out.println();
System.out.println("非遞歸中序遍歷二叉樹的結果為:");
tree.iterativeInOrder(tree);
System.out.println();
System.out.println("遞歸後序遍歷二叉樹的結果為:");
tree.postOrder(tree);
System.out.println();
System.out.println("非遞歸後序遍歷二叉樹的結果為:");
tree.iterativePostOrder(tree);
System.out.println();
System.out.println("層次遍歷二叉樹結果: ");
tree.LayerOrder(tree);
System.out.println();

System.out.println("遞歸求二叉樹中所有結點的和為:"+getSumByRecursion(tree));
System.out.println("非遞歸求二叉樹中所有結點的和為:"+getSumByNoRecursion(tree));

System.out.println("二叉樹中,每個節點所在的層數為:");
for (int p = 1; p <= 14; p++)
System.out.println(p + "所在的層為:" + tree.level(p));
System.out.println("二叉樹的高度為:" + height(tree));
System.out.println("二叉樹中節點總數為:" + nodes(tree));
System.out.println("二叉樹中葉子節點總數為:" + leaf(tree));
System.out.println("二叉樹中父節點總數為:" + fatherNodes(tree));
System.out.println("二叉樹中只擁有一個孩子的父節點數:" + oneChildFather(tree));
System.out.println("二叉樹中只擁有左孩子的父節點總數:" + leftChildFather(tree));
System.out.println("二叉樹中只擁有右孩子的父節點總數:" + rightChildFather(tree));
System.out.println("二叉樹中同時擁有兩個孩子的父節點個數為:" + doubleChildFather(tree));
}
}

Ⅱ 關於《數據結構與演算法分析 java語言描述》 的課後習題答案和項目設計的答案

http://download.csdn.net/download/tangzhnju/3688376， 別人的勞動成果，我只是搬運工，我下載看了下，好像不是所有題目都有答案，不過也很有參考意義
補充：不好意思，沒看清楚作者應該不是你需要的那一份

Ⅲ 求一些JAVA數據結構的試題及答案解析

1 下列數據結構中，能用二分法進行查找的是__A____。
A、順序存儲的有序線性表 B、線性鏈表 C、二叉鏈表 D、有序線性鏈表 解析：二分法查找只適用於順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列(即從小到大，但允許相鄰元素值相等)。 2 在軟體設計中，不屬於過程設計工具的是__D____。 A、PDL(過程設計語言) B、PAD圖 C、N-S圖 D、DFD圖 解析：軟體設計工具包括：程序流程圖、N-S、PAD、HIPO，判定表，PDL(偽碼)。而DFD(數據流圖)屬於結構化分析工具。
3 在switch(expression)語句中，expression的數據類型不能是__A____。 A、double B、char C、byte D、short
解析：表達式expression只能返回這個幾種類型的值：int、byte、short和char。多分支語句把表達式返回的值依次與每個case子句中的值相比較，如果遇到匹配的值，則執行該case子句後的語句序列。
4 下列敘述中，錯誤的是__D____。
A、父類不能替代子類 B、子類能夠替代父類 C、子類繼承父類 D、父類包含子類 5 通過繼承實現代碼復用：
Java中所有的類都是通過直接或間接地繼承java.lang.Object類得到的。繼承而得到的類稱為子類，被繼承的類稱為父類。子類不能繼承父類中訪問許可權為private的成員變數和方法，子類可以重寫父類的方法，及命名與父類同名的成員變數。 子類通過隱藏父類的成員變數和重寫父類的方法，把父類的狀態和行為改變為自身的狀態和行為。注意：子類中重寫的方法和父類中被重寫的方法要具有相同的名字，相同的參數表和相同的返回類型，只是函數體不同。
由於子類繼承了父類所有的屬性(私有的除外)，所以子類對象可以作為父類對象使用。程序中凡是使用父類對象的地方，都可以用子類對象來代替。一個對象可以通過引用子類的實例來調用子類的方法。
java運行時系統根據調用該方法的實例，來決定調用哪個方法。對子類的一個實例，如果子類重寫了父類的方法，則運行時系統調用子類的方法;如果子類繼承了父類的方法(未重寫)，則運行時系統調用父類的方法。
6 自定義表格類中的model部分應實現的介面是___A___。
A、AbstractTableModel B、JTable C、TableModel D、TableModelable 7 下列代碼中，將引起編譯錯誤的行是__B____。 1)public class Exercise{
2) public static void main(String args[]){ 3) float f=0.0; 4) f+=1.0; 5) } 6) }
A、第2行 B、第3行 C、第4行 D、第6行
解析：float定義變數賦值時，需要在數值後面加f以標識它為浮點型，讓系統知道該給它精確到多少位。

Ⅳ 20分——數據結構習題答案（電子版）

說明:
1. 本文是對嚴蔚敏《數據結構(c語言版)習題集》一書中所有演算法設計題目的解決方案,主要作者為一具.以下網友:biwier,szm99,siice,龍抬頭,iamkent,zames,birdthinking,lovebuaa等為答案的修訂和完善工作提出了寶貴意見,在此表示感謝;
2. 本解答中的所有演算法均採用類c語言描述,設計原則為面向交流、面向閱讀,作者不保證程序能夠上機正常運行(這種保證實際上也沒有任何意義);
3. 本解答原則上只給出源代碼以及必要的注釋,對於一些難度較高或思路特殊的題目將給出簡要的分析說明,對於作者無法解決的題目將給出必要的討論.目前尚未解決的題目有: 5.20, 10.40;
4. 請讀者在自己已經解決了某個題目或進行了充分的思考之後,再參考本解答,以保證復習效果;
5. 由於作者水平所限,本解答中一定存在不少這樣或者那樣的錯誤和不足,希望讀者們在閱讀中多動腦、勤思考,爭取發現和糾正這些錯誤,寫出更好的演算法來.請將你發現的錯誤或其它值得改進之處向作者報告: [email protected]

第一章 緒論
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 || m==k) f=1;
else
{
for(i=0;i<=k-2;i++) temp[i]=0;
temp[k-1]=1;temp[k]=1; //初始化
sum=1;
j=0;
for(i=k+1;i<=m;i++,j++) //求出序列第k至第m個元素的值
temp[i]=2*sum-temp[j];
f=temp[m];
}
return OK;
}//fib
分析: k階斐波那契序列的第m項的值f[m]=f[m-1]+f[m-2]+......+f[m-k]
=f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1]
=2*f[m-1]-f[m-k-1]
所以上述演算法的時間復雜度僅為O(m). 如果採用遞歸設計,將達到O(k^m). 即使採用暫存中間結果的方法,也將達到O(m^2).
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[MAXSIZE];
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[ 0 ].totalscore+=result[i].score;
if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;
else score[ 0 ].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 temp;
float *p=a;
printf("Input number of terms:");
scanf("%d",&n);
printf("Input value of x:");
scanf("%f",&x);
printf("Input the %d coefficients from a0 to a%d:\n",n+1,n);
p=a;xp=1;sum=0; //xp用於存放x的i次方
for(i=0;i<=n;i++)
{
scanf("%f",&temp);
sum+=xp*(temp);
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,並用返回值表示結果,值為1,表示A>B;值為-1,表示A<B;值為0,表示A=B
{
for(i=1;i<=A.length&&i<=B.length;i++)
if(A.elem[i]!=B.elem[i])
return A.elem[i]>B.elem[i]?1:-1;
if(A.length==B.length) return 0;
return A.length>B.length?1:-1; //當兩個字元表可以互相比較的部分完全相同時,哪個較長,哪個就較大
}//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));
C=pc;
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
}//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中
}
else {i++;j++;}
}//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&&p!=L) 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

Ⅳ 數據結構（Java）》在線作業一

1:B,2:b,3:b,4:b
,5:b,6:a,7:b,8:a
,9:b,10:a,11:b
12:b,13:b,14:a

不解釋、保守正確10題以上。

Ⅵ Java數據結構疑問

數據結構好幾年了，都忘了，只能解決兩問題。

第一個問題：

前序遍歷的話，是先根節點，後是左右節點。

中序遍歷是先左節點，後是根節點，最後是右節點。

前序遍歷a是第一個，所以整個二叉樹的根節點是a；

所以中序遍歷的a節點前的節點（dgb）都是二叉樹的左子樹的節點，a後的節點（echf）為右子樹的節點；

前序遍歷是，左子樹的順序是：bdg，則b肯定是左子樹的根節點，即為a的左節點；

左子樹剩下dg節點，由於中序遍歷時dg節點在b前，所以dg節點肯定是b節點的左子樹節點，又因為不管是前序遍歷還是中序遍歷，順序都是dg，所以d是b的左節點，g是d的右節點。

右子樹的節點（echf），前序（cefh）時c在最前，所以c是a的右節點，中序（echf）在c前的節點為c的左子樹節點，只有e，所以e為c的左節點；

只剩下hf節點，前序（fh）和中序（hf）順序不一致，則只能是如圖所示結果。

如圖所示，後序遍歷(遍歷順序，左子樹，右子樹，根)的順序為：gdbehfca

問題四：

E1最後出的，說明E1一直在棧中，E2第一個出的，則E2是進入棧後就出來，此時容量至少是2；

E4第二個出的，說明E3進入棧後沒有直接出來直到E4進入棧並出來之後，E3才出來，此時容量至少是3；

隨後出來的是E6，則說明E5進入棧後也沒直接出來，也是E6出來才輪到E5，此時容量至少也是3。

所以答案是3。

Ⅶ 數據結構（Java）在線作業

B D B B B B

B A B B A
B B B B A
A B B

Ⅷ 數據結構java版楊淑萍和聶哲主編習題及答案

344099997幫你解決