1.
⑴解：(79,62,34,57,26,48)
⑵解：(26,34,48,57,62,79)
⑶解：(48,56,57,62,79,34)
⑷解：(56,57,79,34)
⑸解：(26,34,39,48,57,62)
2.
解：
為了排版方便，假定采用以下輸出格式表示單鏈接表的示意圖；每個(gè)括號(hào)內(nèi)的數(shù)據(jù)表示一個(gè)元
素結(jié)點(diǎn)，其中第一個(gè)數(shù)據(jù)為元素值，第二個(gè)數(shù)據(jù)為后繼結(jié)點(diǎn)的指針，第一個(gè)元素結(jié)點(diǎn)前的數(shù)值為
表頭指針。
⒈(7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0))
⒉(3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0))
⒊(2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0))
⒋(8(56,4),(57,7),(79,5),(34,0))
3.對(duì)于List類(lèi)型的線性表,編寫(xiě)出下列每個(gè)算法。
⑴ 從線性表中刪除具有最小值的元素并由函數(shù)返回，空出的位置由最后一個(gè)元素填補(bǔ)，若
線性表為空則顯示出錯(cuò)信息并退出運(yùn)行。
解： ElemType DMValue(List&L)
//從線性表中刪除具有最小值的元素并由函數(shù)返回,空出的位置
//由最后一個(gè)元素填補(bǔ),若線性表為空則顯示出錯(cuò)信息并退出運(yùn)行
{
if(ListEmpty(L)){
cerr<<"List is Empty!"<<end1;
exit(1);
}
ElemType x;
x=L.list[0];
int k=0;
for(int i=1;i<L.size;i++){
ElemType y=L.list[i];
if(y<x){x=y;k=i;}
}
L.list[k]=L.list[L.size-1];
L.size--;
return x;
}
⑵ 從線性表中刪除第i個(gè)元素并由函數(shù)返回。
解：int Deletel(List& L,int i)
//從線性表中刪除第i個(gè)元素并由函數(shù)返回
{
if(i<1||i>L.size){
cerr<<"Index is out range!"<<end1;
exit(1);
}
ElemType x;
x=L.list[i-1];
for(int j=i-1;j<L.size-1;j++)
L.list[j]=L.list[j+1];
L.size--;
return x;
}
⑶ 向線性表中第i個(gè)元素位置插入一個(gè)元素。
解：void Inser1(List& L,int i,ElemType x)
//向線性表中第i個(gè)元素位置插入一個(gè)元素
{
if(i<1||i>L.size+1){
cerr<<"Index is out range!"<<end1;
exit(1);
}
if(L.size==MaxSize)
{
cerr<<"List overflow!"<<end1;
exit(1);
}
for(int j=L.size-1;j>i-1;j--)
L.list[j+1]=L.list[j];
L.list[i-1]=x;
L.size++;
}
⑷ 從線性表中刪除具有給定值x的所有元素。
解：void Delete2(List& L,ElemType x)
//從線性表中刪除具有給定值x的所有元素
{
int i=0;
while(i<L.size)
if(L.list[i]==x){
for(int j=i+1;j<L.sizr;j++)
L.list[j-1]=L.list[j];
L.size--;
}
else
i++;
}
⑸ 從線性表中刪除其值在給定值s和t之間(要求s小于t)的所有元素。
解：void Delete3(List& L,ElemType s,ElemType t)
//從線性表中刪除其值在給定值s和t之間的所有元素
{
int i=0;
while(i<L.size)
if((L.list[i]>=s)&&(L.list[i]<=t)){
for(int j=i+1;j<L.size;j++)
L.list[j-i]=L.list[j];
L.size--;
}
else
i++;
}
⑹ 從有序表中刪除其值在給定值s和t之間(要求s小于t)的所有元素。
解：void Delete4(List& L,ElemType s,ElemType t)
//從有序表中刪除其值在給定值s和t之間的所有元素
{
int i=0;
while(i<L.size)//從有序表L中查找出大于等于s的第一個(gè)元素
if(L.list[i]<s)i++;
else break;
if(i<L.size){
While((i+j<L.size)&&(L.list[i+j]<=t))
j++;//求出s和t之間元素的個(gè)數(shù)
for(int k=i+j;k<L.size;k++)
L.list[k-j]=L.list[k];
L.size-=j;
}
}
⑺ 將兩個(gè)有序表合并成一個(gè)新的有序表并由變量返回。
解：void Merge(List& L1,List& L2,List& L3)
//將兩個(gè)有序表合并成一個(gè)新的有序表并由變量返回
{
if(L1.size+L2.size>MaxSize){
cerr<<"List overflow!"<<end1;
exit(1);
}
int i=0,j=0,k=0;
while((i<L1.size)&&(j<L2.size)){
if(L1.list[i]<=L2.list[j])
{ //將L1中的元素賦給L
L.list[k]=L1.list[i];
i++;
}
else{ //將L2中的元素賦給L
L.list[k]=L2.list[j];
j++;
}
k++;
}
while(i<L1.size){ //將L1中剩余的元素賦給L
L.list[k]=L1.list[i];
i++;k++;
}
while(j<L2.size){ //將L2中剩余的元素賦給L
L.list[k]=L2.list[j];
j++;k++;
}
L.size=k;
}
⑻ 從線性表中刪除所有其值重復(fù)的元素，使其所有元素的值均不同，如對(duì)于線性表(2,8,9,
2,5,5,6,8,7,2)，則執(zhí)行此算法后變?yōu)?2,8,9,5,6,7)。
解：void Delete5(List& L)
//從線性表中刪除所有其值重復(fù)的元素,使其所有元素的值均不同
{
int i=0;
while(i<L.size){
int j=i+1;
while(j<L.size)
{ //刪除重復(fù)值為L(zhǎng).list[i]的所有元素
if(L.list[j]==L.list[i]){
for(int k=j+1;k<L.size;k++)
L.list[k-1]=L.list[k];
L.size--;
}
else
j++;
}
i++;
}
}
4.對(duì)于結(jié)點(diǎn)類(lèi)型為L(zhǎng)Node的單鏈接表,編寫(xiě)出下列每個(gè)算法。
⑴ 將一個(gè)單鏈接表按逆序鏈接,即若原單鏈表中存儲(chǔ)元素的次序?yàn)閍1,a2,...,an,則
逆序鏈接后變?yōu)閍n,an-1,...a1。
解：void Contrary(LNode*&HL)
//將一個(gè)單多辦實(shí)事有按逆序鏈接
{
LNode*p=HL;//p指向待逆序的第一個(gè)結(jié)點(diǎn)，初始指向原表頭結(jié)點(diǎn)
HL=NULL;//HL仍為逆序后的表頭指針，祿始值為空
while(p!=NULL)
{ //把原單鏈表中的結(jié)點(diǎn)依次進(jìn)行逆序鏈接
LNode*q=p; //q指向待處理的結(jié)點(diǎn)
p=p->next; //p指向下一個(gè)待逆序的結(jié)點(diǎn)
//將q結(jié)點(diǎn)插入到已陳序單鏈表的表頭
q->next=HL;
HL=q;
}
}
⑵ 刪除單鏈表中的第i個(gè)結(jié)點(diǎn)。
解：void Delete1(LNode*&HL,int i)
//刪除單鏈表中的第i個(gè)結(jié)點(diǎn)
{
if(i<1||HL==NULL){
cerr<<"Index is out range!"<<end1;
exit(1);
}
LNode*ap,*cp;
ap=NULL;cp=HL; //cp指向當(dāng)前結(jié)點(diǎn)，ap指向其前驅(qū)結(jié)點(diǎn)
int j=1;
while(cp!=NULL)
if(j==i)
break; //cp結(jié)點(diǎn)即為第i個(gè)結(jié)點(diǎn)
else{ //繼續(xù)向后尋找
ap=cp;
cp=cp->next;
j++;
}
if(cp==NULL){
cerr<<"Index is out range!"<<end1;
exit(1);
}
if(ap==NULL)
HL=HL->next;
else
ap->next=cp->next;
delete cp;
}
⑶ 從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回，若單鏈表為空，則顯示出錯(cuò)信息
并停止運(yùn)行。
解：ElemType MaxValue(LNode*HL)
//從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回
{
if(HL==NULL){
cerr<<"Linked list is empty!"<<end1;
exit(1);
}
ElemType max=HL->data;
LNode*p=HL->next;
while(p!=NULL){
if(max<p->data) max=p->data;
p=p->next;
}
return max;
}
⑷ 統(tǒng)計(jì)出單鏈表中結(jié)點(diǎn)的值等于給定值x的結(jié)點(diǎn)數(shù)。
解：int Count(LNode*HL,ElemType x)
//統(tǒng)計(jì)出單鏈表中結(jié)點(diǎn)的值等于給定值x的結(jié)點(diǎn)數(shù)
{
int n=0;
while(HL!=NULL){
if(HL->data==x) n++;
HL=HL->next;
}
return n;
}
⑸ 根據(jù)一維數(shù)組a[n]建立一個(gè)單鏈表，使單鏈表中元素的次序與a[n]中元素的次序相同，
并使該算法的時(shí)間復(fù)雜度為O(n)。
解：void Create(LNode*&HL,ElemType a[],int n)
//根據(jù)一維數(shù)組a[n]建立一個(gè)單鏈表
{
InitList(HL);
for(int i=n-1;i>=0;i--)
InsertFront(HL,a[i];
}
⑹ 將一個(gè)單鏈表重新鏈接成有序單鏈表。
解：void OrderList(LNode*&HL)
//將一個(gè)單鏈表重新鏈接成有序單鏈表
{
LNode* p=HL;//p指向待處理的第一個(gè)結(jié)點(diǎn)，初始指向原表頭結(jié)點(diǎn)
HL=NULL; //HL仍為待建立的有序表的表頭指針，祿始值為空
while(p!=NULL)
{ //把原單鏈表中的結(jié)點(diǎn)依次進(jìn)行有序鏈接
LNode* q=p; //q指向待處理的結(jié)點(diǎn)
p=p->next; //p指向下一個(gè)待處理的結(jié)點(diǎn)
LNode* ap=NULL,*cp=HL;
//cp指向有序表中待比較的結(jié)點(diǎn)，ap指向其前驅(qū)結(jié)點(diǎn)
while(cp!=NULL)
{ //為插入q結(jié)點(diǎn)尋找插入位置
if(q->data<cp->data)
break;
else{
ap=cp;
cp=cp->next;
}
} //將q結(jié)點(diǎn)插入到ap和cpxf hko pp uj
q->next=cp;
if(ap==NULL)
HL=q;
else
ap->next=q;
}
}
⑺ 將兩個(gè)有序單鏈表合并成一個(gè)有序單鏈表，合并后使原有單鏈表為空。
解：LNode*Mergel(LNode*&p1,LNode*&p2)
//將兩個(gè)有序單鏈表合并成一個(gè)有序單鏈表
{
LNode a; //a結(jié)點(diǎn)作為結(jié)果的有序單鏈表的表頭附加結(jié)點(diǎn)，這樣便于處理，處理
//結(jié)束后返回a結(jié)點(diǎn)的鐨針域的值
LNode*p=&a; //p指向結(jié)果的有序單鏈表的表尾結(jié)點(diǎn)
p->next=NULL;//初始指向表頭附加結(jié)點(diǎn)
while((p1!=NULL)&&(p2!=NULL))
{//處理兩個(gè)表非空的情況
if(p1->data<p2->data){
p->next=p1;p1=p1->next;
}
else{
p->next=p2;p2=p2->;
}
p=p->next;
}
if(p1!=NULL)p->next=p1;
if(p2!=NULL)p->next=p2;
p1=p2=NULL;
return a.next;
}
⑻ 根據(jù)兩個(gè)有序單鏈表生成一個(gè)新的有序單鏈表，原有單鏈表保持不變。如假定兩個(gè)有序單鏈
表中的元素為(2,8,10,20)和(3,8,9,15,16)，則生成的新單鏈表中的元素為(2,3,8,8,9,10,15,
16,20)。
解：LNode*Merge2(LNode*p1,LNode*p2)
//根據(jù)兩個(gè)有序單鏈表生成一個(gè)新的有序單鏈表
{
LNode a; //用a作為新的有序單鏈表的表頭附加結(jié)點(diǎn)
LNode*p=&a; //p指向結(jié)果有序單鏈表的表尾結(jié)點(diǎn)
p->next=NULL; //初始指向表頭附加結(jié)點(diǎn)
while((p1!=NULL&&(p2!=NULL))
{ //處理兩個(gè)表非空時(shí)的情況
LNode*newptr=new LNode;
if(p1->data<p2->data)
{ //由p1->data建立新結(jié)點(diǎn)，然后p1指針后移
newptr->data=p1->data;
p1=p1->next;
}
else
{ //由p2->data建立新結(jié)點(diǎn)，然后p2指針后移
newptr->data=p2->data;
p2=p2->next;
}
//將newptr結(jié)點(diǎn)插入到結(jié)果的有序表的表尾
p->next=newptr;
p=newptr;
}
while(p1!=NULL)
{ //繼續(xù)處理p1單鏈表中剩余的結(jié)點(diǎn)
LNode*newptr=new LNode;
newptr->data=p1->data;
p1=p1->next;
p->next=newptr;
p=newptr;
}
while(p2!=NULL)
{ //繼續(xù)處理p2單鏈表中剩余的結(jié)點(diǎn)
LNode*newptr=new LNode;
newptr->data=p2->data;
p2=p2->next;
p->next=newptr;
p=newptr;
}
p->next=NULL;
return a.next;
}
⑼ 根據(jù)一個(gè)元素類(lèi)型為整型的單鏈表生成兩個(gè)單鏈表，使得第一個(gè)單鏈表中包含原單鏈表中所有
元素值為奇數(shù)的結(jié)點(diǎn)，使得第二個(gè)單鏈表中包含原單鏈表中所有元素值為偶數(shù)的結(jié)點(diǎn)。原有單鏈表
保持不變。
解：void Separate(LNode*HL,LNode*&p1,LNode*&p2)
//根據(jù)一個(gè)單鏈表HL按條件拆分生成兩個(gè)單鏈表p1和p2
{
LNode a,b; //a和b結(jié)點(diǎn)分別作為p1和p2單鏈表的表頭附加結(jié)點(diǎn)
LNode*t1=&a,*t2=&b; //t1和t2分別作為指向p1和p2單鏈表的
//表尾結(jié)點(diǎn)，初始指向表頭附加結(jié)點(diǎn)
Lnode*p=HL;
while(p!=NULL)
{ //每循環(huán)一次產(chǎn)生一個(gè)新結(jié)點(diǎn)，并把它加入到p1或p2單鏈表
//的未尾
LNode*newptr=new LNode;
if(p->data%2==1){
newptr->data=p->data;
t1->next=newptr;
t1=newptr;
}
else{
newptr->data=p->data;
t2->next=newptr;
t2=newptr;
}
p=p->next;
}
t1->next=t2->next=NULL;
p1=a.next;p2=b.next; //把指向兩個(gè)單鏈表的表頭結(jié)點(diǎn)的指針?lè)謩e賦給
//p1和p2返回
}
6.編寫(xiě)一個(gè)算法，使用表頭附加結(jié)點(diǎn)的循環(huán)單鏈表解決約瑟夫(Josephus)問(wèn)題。其問(wèn)題是
：設(shè)有n個(gè)人圍坐在一張圓桌周?chē)?，現(xiàn)從某個(gè)人開(kāi)始從1報(bào)數(shù)，數(shù)到m的人出列(即離開(kāi)坐位，
不參加以后的報(bào)數(shù))，接著從出列的下一個(gè)人開(kāi)始重新從1報(bào)數(shù)，數(shù)到m的人又出列，如此下
去直到所有人都出列為止，試求出它們的出列次序。
假如，當(dāng)n=8、m=4時(shí)，若從第一個(gè)人(假定每個(gè)人的編號(hào)依次為1,2...,n)開(kāi)始報(bào)數(shù)，則得
到的出列次序?yàn)?4,8,5,2,1,3,7,6。
此算法要求以n、m和s(假定從第s個(gè)人開(kāi)始第一次報(bào)數(shù))作為值參。
解：
void Josephus(int n,int m,int s)
//使用帶表頭附加結(jié)點(diǎn)的循環(huán)單鏈表解決約瑟夫問(wèn)題
{
//生成表頭附加結(jié)點(diǎn)，此時(shí)循環(huán)單鏈表為空
LNode*HL=new LNode;
HL->next=HL;
int i;
//生成含有n個(gè)結(jié)點(diǎn)、結(jié)點(diǎn)依次為1,2,...n的帶表頭結(jié)點(diǎn)的循環(huán)單鏈表
for(i=n;i>=1;i--){
//生成新的結(jié)點(diǎn)
LNode*newptr=new LNode;
newptr->data=i;
//把新的結(jié)點(diǎn)插入到表頭
newptr->next=HL->next;
HL->next=newptr;
}
//從表頭開(kāi)始順序查找出第s個(gè)結(jié)點(diǎn)，對(duì)應(yīng)第一個(gè)開(kāi)始報(bào)數(shù)的人
LNode*ap=HL,*cp=HL->next;
for(i=1;i<s;i++){
//ap和cp指針后移一個(gè)位置
ap=cp;
cp=cp->next;
//若cp指向了表頭附加結(jié)點(diǎn)，則仍需后移ap和cp指針，使之指向表頭結(jié)點(diǎn)
if(cp==HL){ap=HL;cp=HL->next;}
}
//依次使n-1個(gè)人出列
for(i=1;i<n;i++){
//順序查找出待出列的人，即為循環(huán)結(jié)束后cp所指向的結(jié)點(diǎn)
for(int j=1;j<m;j++){
ap=cp;
cp=cp->next;
if(cp==HL){ap=HL;cp=HL->next;}
}
//輸出cp結(jié)點(diǎn)的值，即出列的人
cout<<cp->data<<"";
//從單鏈表中刪除cp結(jié)點(diǎn)
ap->next=cp->next;
delete cp;
//使cp指向被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)
cp=ap->next;
//若cp指向了表頭附加結(jié)點(diǎn)，則后移ap和cp指針
if(cp==HL){ap=HL;cp=HL->next;}
}
//使最后一個(gè)人出列
cout<<HL->next->data<<end1;
//刪除表頭結(jié)點(diǎn)和表頭附加結(jié)點(diǎn)
delete HL->next;
delete HL;
}
7.對(duì)于在線性表抽象數(shù)據(jù)類(lèi)型中定義的每一個(gè)操作，寫(xiě)出結(jié)點(diǎn)類(lèi)型為L(zhǎng)Node的帶頭附加結(jié)點(diǎn)
的循環(huán)單鏈表上實(shí)現(xiàn)的對(duì)應(yīng)算法。
⑴初始化單鏈表
解：void InitList(LNode*HL)
{
HL->next=HL;//將單鏈表置空
}
⑵刪除單鏈表中的所有結(jié)點(diǎn)，使之成為一個(gè)空表
void ClearList(LNode*HL)
{
LNode*cp,*np;
cp=HL->next;//將指向第一個(gè)結(jié)點(diǎn)的指針賦給cp
while(cp!=HL)//遍歷單鏈表，向系統(tǒng)交回每一個(gè)結(jié)點(diǎn)。
{
np=cp->next;//保存下一個(gè)結(jié)點(diǎn)的指針。
delete cp;//刪除當(dāng)前結(jié)點(diǎn)。
cp=np;//使下一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)。
}
HL->next=HL;//置單鏈表為空
}
⑶得到單鏈表的長(zhǎng)度
int ListSize(LNode*HL)
{
LNode*p=HL->next;
int i=0;
while(p!=HL){i++;p=p->next;}
return i;
}
⑷檢查單鏈表是否為空
int ListEmpty(LNode*hl)
{
return(HL->next==HL);
}
⑸得到單鏈表中第pos個(gè)結(jié)點(diǎn)中的元素
ElemType GetElem(LNode*HL,int pos)
{
if(pos<1){
cerr<<"pos is out range!"<<end1;
exit(1);
}
LNode* p=HL->next;
int i=0;
while(p!=HL){
i++;
if(i==pos)break;
p=p->next;
}
if(p!=HL)return p->data;
else{
cerr<<"pos is out range!"<<end1;
exit(1);
}
}
⑹遍歷單鏈表
void TraverseList(LNode*HL)
{
LNode* p=HL->next;
while(p!=HL){
cout<<p->data<<"";
p=p->next;
}
cout<<end1;
}
⑺從單鏈表查找具有給定值的第一個(gè)元素
int Find(LNode* HL,ElemType& item)
{
LNode* p=HL->next;
while(p!=HL)
if(p->data==item){
item=p->data;
return 1;
}
else
p=p->next;
return 0;
}
⑻更新單鏈表中具有給定值的第一個(gè)元素
int Updata(LNode* HL,const ElemType& item)
{
LNode* p=HL->next;
while(p!=HL)//查找元素
if(p->data==item)break;
else p=p->next;
if(p==HL)return 0;
else{//更新元素
p->data=item;
return 1;
}
}
⑼向單鏈表的未尾插入一個(gè)元素
void InsertRear(LNode* HL,const ElemType& item)
{
LNode* newptr;
newptr=new LNode;
newptr->data=item;//把新元素賦給動(dòng)態(tài)結(jié)點(diǎn)*newptr的值域。
LNode* p=HL;
while(p->next!=HL)//從表頭開(kāi)始遍歷到最后一個(gè)結(jié)點(diǎn)為止。
p=p->next;
newptr->next=HL;p->next=newptr;//把新結(jié)點(diǎn)鏈接到表尾。
}
⑽向單鏈表的表頭插入一個(gè)元素
void InsertFront(LNode* HL,const ElemType& item)
{
LNode* newptr;
newptr=new LNode;
newptr->data=item;
newptr->next=HL->next;
HL->next=newptr;
}
(11)向單鏈表中插入一個(gè)元素
void Insert(LNode* HL,const ElemType& item)
{
LNode* newptr;
newptr=new LNode;
newptr->data=item;
LNode *ap,*cp;
ap=HL;cp=HL->next;
while(cp!=HL)
if(item<cp->data)break;
else{ap=cp;cp=cp->next;}
newptr->next=cp;
ap->next=newptr;
}
(12)從單鏈表中刪除表頭元素
ElemType DeleteFront(LNode* HL)
{
if(HL->next==HL){
cerr<<"Deleteing from an empty list!"<<end1;
exit(1);
}
LNode* p=HL->next;
HL->next=p->next;
ElemType temp=p->data;
delete p;
return temp;
}
(13)從單鏈表中刪除等于給定值的第一個(gè)元素
int Delete(LNode* HL,const ElemType& item)
{
LNode*ap=HL,*cp=HL->next;
while(cp!=HL)
if(cp->data==item)break;
else{ap=cp;cp=cp->next;}
if(cp==HL){
cerr<<"Deleted element is not exitst!"<<end1;
return 0;
}
else{
ap->next=cp->next;
delete cp;
return 1;
}
}
(14)利用單鏈表進(jìn)行數(shù)據(jù)排序
void LinkSort(ElemType a[],int n)
{
LNode* head=new LNode;
InitList(head);
int i;
for(i=0;i<n;i++)
Insert(head.a[i]);
LNode* p=head->next;
i=0;
while(p!=head){
a[i++]=p->data;
p=p->next;
}
ClearList(head);
delete head;
}
*8.對(duì)于結(jié)點(diǎn)類(lèi)型為DNode的雙向鏈表，編寫(xiě)出下列每一個(gè)算法。
⑴向雙向鏈表的未尾插入一個(gè)值為x的結(jié)點(diǎn)。
解：void InsertRear(DNode*&DL,ElemType x)
{
//建立值為x的結(jié)點(diǎn)
DNode* newptr=new DNode;
newptr->data=x;
newptr->left=newptr->right=newptr;
//當(dāng)鏈表為空時(shí)完成插入
if(DL==NULL){DL=newptr;return;}
//當(dāng)鏈表不為空時(shí)完成插入
DNode*p=DL->left;
newptr->right=p->right;
DL->left=newptr;
newptr->left=p;
p->right=newptr;
}
⑵向雙向循環(huán)表的第i個(gè)結(jié)點(diǎn)位置插入一個(gè)值為x的結(jié)點(diǎn)。
解：void Insert(DNode*&DL,int i, ElemType x)
{
//i值越界，退出執(zhí)行
if(i<=0){
cerr<<"i is out range!"<<end1;
exit(1);
}
//建立值為x的新結(jié)點(diǎn)
DNode*newptr=new DNode;
newptr->data=x;
newptr->left=newptr->right=newptr;
//當(dāng)鏈表為空同時(shí)i等于1時(shí)進(jìn)行插入，i不為1則退出
if(DL==NULL)if(i==1){DL=newptr;return;}
else{out<<"i is range!"<<end1;
exit(1);
}
//實(shí)現(xiàn)i等于1時(shí)的插入
if(i==1){newptr->right=DL;
newptr->left=DL->left;
DL->left->right=newptr;
DL->left=newptr;
DL=newptr;
return;
}
//查找第i個(gè)結(jié)點(diǎn)
int k=1;
DNode*p=DL->right;
while(p!=DL){
k++;
if(k==i)break;
p=p->right;
}
//i值越界，退出執(zhí)行
if(i>k+1){
cerr<<"i is out range!"<<end1;
exit(1);
}
//把newptr結(jié)點(diǎn)插入到p結(jié)點(diǎn)之前
newptr->right=p;
newptr->left=p->left;
p->left->right=newptr;
p->left=newptr;
return;
}
⑶從雙向循環(huán)鏈表中刪除值為x的結(jié)點(diǎn)。
解：bool Delete(DNode*&DL,ElemType x)
{
if(DL==NULL)return 0;
//當(dāng)表頭結(jié)點(diǎn)為x時(shí)則刪除之
DNode*p=DL;
if(DL->data==x){
DL=DL->right;
p->left->right=DL;
DL->left=p->left;
delete p;
return 1;
}
//查找值為x的結(jié)點(diǎn)
p=p->right;
while(p!=DL){
if(p->data==x)break;
else p=p->right;
}
//不存在值為x的結(jié)點(diǎn)則返回0
if(p==DL)return 0;
//刪除值為x的結(jié)點(diǎn)
p->left->right=p->right;
p->right->left=p->left;
delete p;
return 1;
}
9.假定有一種帶頭附加結(jié)點(diǎn)的鏈表，每個(gè)結(jié)點(diǎn)含三個(gè)域：data、next和range，其中data
為整型值域，next和range均為指針域，現(xiàn)在所有結(jié)點(diǎn)已經(jīng)由next域鏈接起來(lái)，試編一算法
，利用range域把所有結(jié)點(diǎn)按照其值從小到大的順序鏈接起來(lái)，當(dāng)然由此域鏈接得到的單鏈
表的表頭指針保存在表頭附加結(jié)點(diǎn)的range域中。
解：void OrderList(SLNode* SL)
//假定SLNode類(lèi)型為按題目要求所定義的結(jié)點(diǎn)類(lèi)型，SL為指向表頭附加結(jié)點(diǎn)的指針
{
SL->range=NULL;
for(SLNode*p=SL->next;p!=NULL;p=p->next)
{ //每循環(huán)一次把p所指向的結(jié)點(diǎn)按序插入到以range域鏈接的有序表中
SLNode*ap,*cp;
//為p結(jié)點(diǎn)尋找合適的插入位置
ap=SL;cp=ap->range;
while(cp!=NULL)
if(p->data<cp->data)
break;
else{
ap=cp;
cp=cp->range;
}
//插入位置在ap和cp之間，把結(jié)點(diǎn)插入其中
p->range=cp;
ap->range=p;
}
}
10.編一程序，實(shí)現(xiàn)下列功能：
⒈按照9題對(duì)結(jié)點(diǎn)的要求生成一個(gè)具有10個(gè)整數(shù)元素結(jié)點(diǎn)的帶表頭附加結(jié)點(diǎn)的根據(jù)next域
鏈接的鏈表，元素值由隨機(jī)函數(shù)產(chǎn)生；
⒉按照next域鏈接的次序輸出鏈表中每個(gè)結(jié)點(diǎn)的值；
⒊調(diào)用按第9題要求編寫(xiě)的操作算法；
⒋按照range域鏈接的次序輸出鏈表中每個(gè)結(jié)點(diǎn)的值。
解：
//lx2-7.cpp
#include<isotream.h>
#include<stdlib.h>
typedef int ElemType;//規(guī)定元素類(lèi)型為整型
struct SLNode//定義單鏈表結(jié)點(diǎn)
{
ElemType data;
SLNode*next;
SLNode*range;
};
void OrderList(SLNode* SL)
{
SL->range=NULL;
for(SLNode*p=SL->next;p!=NULL;p=p->next)
{
SLNode *ap,*cp;
//為p結(jié)點(diǎn)尋找合適的插入位置
ap=SL;cp=ap->range;
while(cp!=NULL)
if(p->data<cp->data)
break;
else{
ap=cp;
cp=cp->range;
}
//插入位置在ap和cp之間，把p結(jié)點(diǎn)插入其中
p->range=cp;
ap->range=p;
}
}
void main()
{
//按next域鏈接生成具有10個(gè)整數(shù)元素結(jié)點(diǎn)的鏈表
SLNode*a=new SLNode;
a->next=NULL;
int i;
SLNode* p;
for(i=0;i<10;i++){
p=new SLNode;
p->data=range()%30; //假定產(chǎn)生30以內(nèi)的隨機(jī)整數(shù)
p->next=a->next;
a->next=p;
}
//按next域鏈接的次序輸出單鏈表
for(p=a->next;p!=NULL;p=p->next)
cout<<p->data<<"";
cout<<end1;
//調(diào)用按第9題要求編寫(xiě)的操作算法
orderList(a);
//按range域鏈接的次序輸出單鏈表
for(p=a->range;p!=NULL;p=p->range)
cout<<p->data<<"";
cout<<end1;
}
