A. python類的多重繼承問題深入分析
Python類的多重繼承問題深入分析
首先得說明的是,Python的類分為經典類 和 新式類
經典類是python2.2之前的東西,但是在2.7還在兼容,但是在3之後的版本就只承認新式類了
新式類在python2.2之後的版本中都可以使用
經典類和新式類的區別在於:
經典類是默認沒有派生自某個基類的,而新式類是默認派生自object這個基類的:
代碼如下:
# old style
class A():pass
# new style
class A(obejct):pass
2.經典類在類多重繼承的時候是採用從左到右深度優先原則匹配方法的..而新式類是採用C3演算法(不同於廣度優先)進行匹配的
3.經典類是沒有__MRO__和instance.mro()調用的,而新式類是有的.
為什麼不用經典類，要更換到新式類
因為在經典類中的多重繼承會有些問題...可能導致在繼承樹中的方法查詢繞過後面的父類:
代碼如下:
class A():
def foo1(self):
print "A"
class B(A):
def foo2(self):
pass
class C(A):
def foo1(self):
print "C"
class D(B, C):
pass
d = D()
d.foo1()
按照經典類的查找順序從左到右深度優先的規則，在訪問d.foo1()的時候,D這個類是沒有的..那麼往上查找,先找到B,裡面沒有,深度優先,訪問A,找到了foo1(),所以這時候調用的是A的foo1()，從而導致C重寫的foo1()被繞過.
所以python引入了新式類的概念,每個基類都繼承自object並且,他的匹配規則也從深度優先換到了C3
C3演算法
C3演算法是怎麼做匹配的呢..在問答版塊上面討論之後,歸結如下:
C3演算法的一個核心是merge.
在merge列表中，如果第一個序列mro的第一個類是出現在其它序列，並且也是第一個，或者不出現其它序列，那麼這個類就會從這些序列中刪除，並合到訪問順序列表中
比如:(引用問題中zhuangzebo的回答@zhuangzebo)
代碼如下:
class A(O):pass
class B(O):pass
class C(O):pass
class D(A,B):pass
class E(C,D):pass
首先需要知道 O(object)的mro(method resolution order)列表是[O,]
那麼接下來是:
代碼如下:
mro(A) = [A, O]
mro(B) = [B, O]
mro(C) = [C, O]
mro(D) = [D] + merge(mro(A), mro(B), [A, B])
= [D] + merge([A, O], [B, O], [A, B])
= [D, A] + merge([O], [B, O], [B])
= [D, A, B] + merge([O], [O])
= [D, A, B, O]
mro(E) = [E] + merge(mro(C), mro(D), [C, D])
= [E] + merge([C, O], [D, A, B, O], [C, D])
= [E, C] + merge([O], [D, A, B, O], [D])
= [E, C, D] + merge([O], [A, B, O])
= [E, C, D, A, B] + merge([O], [O])
= [E, C, D, A, B, O]
然後還有一種特殊情況:
比如：
merge(DO,CO,C) 先merge的是D
merge(DO,CO,C) 先merge的是C
意思就是.當出現有 一個類出現在兩個序列的頭(比如C) 這種情況和 這個類只有在一個序列的頭(比如D) 這種情況同時出現的時候,按照順序方式匹配。
新式類生成的訪問序列被存儲在一個叫MRO的只讀列表中..
你可以使用instance.__MRO__或者instance.mro()來訪問
最後匹配的時候就按照MRO序列的順序去匹配了
C3和廣度優先的區別:
舉個例子就完全明白了:
代碼如下:
class A(object):pass
class B(A):pass
class C(B):pass
class D(A):pass
class E(D):pass
class F(C, E):pass
按照廣度優先遍歷,F的MRO序列應該是[F,C,E,B,D,A]
但是C3是[F,E,D,C,B,A]
意思是你可以當做C3是在一條鏈路上深度遍歷到和另外一條鏈路的交叉點,然後去深度遍歷另外一條鏈路,最後遍歷交叉點
新式類和經典類的super和按類名訪問問題
在經典類中,你如果要訪問父類的話,是用類名來訪問的..
代碼如下:
class A():
def __init__(self):
print "A"
class B(A):
def __init__(self):
print "B"
A.__init__(self) #python不會默認調用父類的初始化函數的
這樣子看起來沒三問題,但是如果類的繼承結構比較復雜，會導致代碼的可維護性很差..
所以新式類推出了super這個東西...
代碼如下:
class A():
def __init__(self):
print "A"
class B(A):
def __init__(self):
print "B"
super(B,self).__init__()
這時候，又有一個問題:當類是多重繼承的時候,super訪問的是哪一個類呢?
super實際上是通過__MRO__序列來確定訪問哪一個類的...實際上就是調用__MRO__中此類後面的一個類的方法.
比如序列為[F,E,D,C,B,A]那麼F中的super就是E,E的就是D
super和按照類名訪問 混合使用帶來的坑
代碼如下:
class A(object):
def __init__(self):
print "enter A"
print "leave A"
class B(object):
def __init__(self):
print "enter B"
print "leave B"
class C(A):
def __init__(self):
print "enter C"
super(C, self).__init__()
print "leave C"
class D(A):
def __init__(self):
print "enter D"
super(D, self).__init__()
print "leave D"
class E(B, C):
def __init__(self):
print "enter E"
B.__init__(self)
C.__init__(self)
print "leave E"
class F(E, D):
def __init__(self):
print "enter F"
E.__init__(self)
D.__init__(self)
print "leave F"
這時候列印出來是：
代碼如下:
enter F
enter E
enter B
leave B
enter C
enter D
enter A
leave A
leave D
leave C
leave E
enter D
enter A
leave A
leave D
leave F
可以看出來D和A的初始化函數被亂入了兩次！
按類名訪問就相當於C語言之前的GOTO語句...亂跳,然後再用super按順序訪問..就有問題了
所以建議就是要麼一直用super,要麼一直用按照類名訪問
最佳實現:
避免多重繼承
super使用一致
不要混用經典類和新式類
調用父類的時候注意檢查類層次
以上便是本人對於python類的繼承的認識了，希望對大家能有所幫助
B. 廣度優先搜索C語言演算法
廣度優先搜索演算法，是按層遍歷各個結點，以求出最短或最優的解，
常用於計算路徑的最短距離，和最佳通路。
例如：迷宮的最短路徑計算，推箱子的移動最小步數等小游戲，都是按廣度搜索來進行的。
這個演算法是教程中很經典的，有很多例子和代碼。你可以好好研究！
如下是一段迷宮的最佳路徑求解演算法。
#include
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int maze[5][5],prev[5][5];
int que[32];
int qn;
void print(int x,int y)
{
if(prev[x][y]!=-2)
{
print(prev[x][y]>>3,prev[x][y]&7);
}
printf("(%d, %d)\n",x,y);
}
int main()
{
int i,j,cx,cy,nx,ny;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
scanf("%d",&maze[i][j]);
}
}
memset(prev,-1,sizeof(prev));
prev[0][0]=-2;
que[0]=0;
qn=1;
for(i=0;i<qn;i++)
{
cx=que[i]>>3;
cy=que[i]&7;
for(j=0;j<4;j++)
{
nx=cx+dx[j];
ny=cy+dy[j];
if((nx>=0)&&(nx=0)&&(ny<5)&&(maze[nx][ny]==0)&&(prev[nx][ny]==-1))
{
prev[nx][ny]=(cx<<3)|cy;
que[qn++]=(nx<<3)|ny;
if((nx==4)&&(ny==4))
{
print(nx,ny);
return 0;
}
}
}
}
return 0;
}
C. c語言圖的遍歷，鄰接表存儲，深度，廣度優先遍歷
（1） 圖的建立，按採用鄰接表作為存儲結構。
（2） 從指定頂點出發進行深度優先搜索遍歷。
（3） 從指定頂點出發進行廣度優先搜索遍歷。
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"math.h"
#define MAX_INT 1000
#define MAX_VERTEX_NUM 20
#define MAX_QUEUE_NUMBER 20
typedef struct ArcNode
{
int adjvex;
double adj;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VexNode
{
char szName[40];
ArcNode *firstarc;
}VexNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vexs;
int vexnum,arcnum;
}Net;
//定義隊列
typedef struct{
int *elem;
int front, rear;
}Queue;
void InitQueue(Queue &Q)
{
Q.elem = new int[MAX_QUEUE_NUMBER];
Q.front = Q.rear = 0;
}
int EmptyQueue(Queue Q)
{
if(Q.front==Q.rear)
return 0;
else
return 1;
}
void DestroyQueue(Queue &Q){
delete []Q.elem;
Q.front = Q.rear = 0;
}
void EnterQueue(Queue &Q, int e)
{
if((Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)
Q.elem[Q.rear ] = e;
else
printf("隊列滿!\n");
Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER;
}
void LeaveQueue(Queue &Q, int &e)
{
if(Q.rear != Q.front)
e = Q.elem[Q.front];
else
printf("隊列空!\n");
Q.front = (Q.front+1)%MAX_QUEUE_NUMBER;
}
int LocateVex(Net ga,char *name)
{
int i;
for(i=0;i<ga.vexnum;i++)
if(strcmp(name,ga.vexs[i].szName)==0)
return i;
return -1;
}
void crt_net(Net &ga)
{
ArcNode *p;
char name1[40],name2[40];
int i,j,k;
double w;
printf("請輸入頂點數和弧數：");
scanf("%d%d",&ga.vexnum,&ga.arcnum);
printf("請依次輸入頂點名：\n");
for(i=0;i<ga.vexnum;i++)
{
scanf("%s",ga.vexs[i].szName);
ga.vexs[i].firstarc=NULL;
}
for(k=0;k<ga.arcnum;k++)
{
printf("請輸入相鄰的兩個定點和權值：");
scanf("%s%s%lf",name1,name2,&w);
i=LocateVex(ga,name1);
j=LocateVex(ga,name2);
p=new ArcNode;
p->adjvex=j;
p->adj=w;
p->nextarc=ga.vexs[i].firstarc;
ga.vexs[i].firstarc=p;
}
}
void DFS(Net ga,char *name,int *visited)
{
int v,w;
ArcNode *p;
v=LocateVex(ga,name);
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
p=ga.vexs[v].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
DFS(ga,ga.vexs[w].szName,visited);
p=p->nextarc;
}
}
void DFSTravel(Net ga,char *name)
{
int v,k=0;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
DFS(ga,ga.vexs[v].szName,visited);
}
}
void BFSTravel(Net ga,char *name)
{
ArcNode *p;
int v,w,u,k=0;
Queue Q;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
InitQueue(Q);
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
{
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
EnterQueue(Q,v);
while(EmptyQueue(Q)!=0)
{
LeaveQueue(Q,u);
p=ga.vexs[u].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
{
printf("%s ",ga.vexs[w].szName);
visited[w]=1;
EnterQueue(Q,w);
}
p=p->nextarc;
}
}
}
}
}
void main()
{
char name[40];
Net ga;
crt_net(ga);
printf("請輸入深度優先遍歷開始點的名：");
scanf("%s",name);
printf("深度優先遍歷：");
DFSTravel(ga,name);
printf("\n");
printf("請輸入廣度優先遍歷開始點的名：");
scanf("%s",name);
printf("廣度優先遍歷：");
BFSTravel(ga,name);
printf("\n");
}