递归与广义表课件.pptVIP

演算法求精voidQueen(inti){for(intj=0;jn;j++){if(!col[j]!md[n+i-j-1]!sd[i+j]){/*第i行第j列沒有攻擊*/col[j]=md[n+i-j-1]=sd[i+j]=1;q[i]=j;/*在第i行第j列安放皇后*/if(i==n-1){/*輸出一個佈局*/for(j=0;jn;j++)coutq[j]‘,’;coutendl;}elseQueen(i+1);}col[j]=md[n+i-j-1]=sd[i+j]=0;q[i]=0;/*撤銷第i行第j列的皇后*/}}廣義表(GeneralLists)廣義表的概念n(?0)個表元素組成的有限序列，記作LS=(a0,a1,a2,…,an-1)LS是表名，ai是表元素，它可以是表(稱為子表)，可以是數據元素(稱為原子)。n為表的長度。n=0的廣義表為空表。n0時，表的第一個表元素稱為廣義表的表頭(head)，除此之外，其他表元素組成的表稱為廣義表的表尾(tail)。廣義表的特性有次序性有長度A=()B=(6,2)C=(‘a’,(5,3,‘x’))D=(B,C,A)E=(B,D)F=(4,F)有深度可共用可遞歸廣義表的表示只包括整數和字元型數據的廣義錶鏈表表示表中套表情形下的廣義錶鏈表表示5232436103914?????list25list1?1247‘a’‘s’廣義表結點定義結點類型utype=0,表頭；=1,整型原子；=2,字元型原子；=3,子表值valueutype=0時,存放引用計數(ref)；utype=1時,存放整數值(intinfo)；utype=2時,存放字元型數據(charinfo)；utype=3時,存放指向子表表頭的指針(hlink)尾指針tlinkutype=0時,指向該表第一個結點；utype?0時,指向同一層下一個結點utypevaluetlink廣義表的存儲表示EBF011430133D??0115132‘x’?012‘a’3?C?013330116DBBCA12?01A?廣義表的類定義classGenList; //GenList類的前視聲明classGenListNode{ //廣義表結點類的前視聲明structItems{//僅有結點資訊的項friendclassGenlistNode;friendclassGenlist;intutype; //＝0/1/2/3union{ //聯合intref;//utype=0,存放引用計數intintinfo; //utype=1,存放整數值charcharinfo;//utype=2,存放字元GenListNode*hlink; //utype=3,存放指向子表的指針}} classGenListNode{ //廣義表結點類定義friendclassGenlist;private:intutype; //＝0/1/2/3GenListNode*