❶ 數據結構（C語言版） 圖的遍歷和拓撲排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等*/
#include<limits.h> /* INT_MAX 等*/
#include<stdio.h> /* EOF(=^Z 或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函數結果狀態代碼*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因為在math.h 中已定義OVERFLOW 的值為3,故去掉此行*/
typedef int Status; /* Status 是函數的類型,其值是函數結果狀態代碼，如OK 等*/
typedef int Boolean; Boolean 是布爾類型,其值是TRUE 或FALSE */
/* .........................*/
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向圖,有向網,無向圖,無向網} */
typedef struct ArcNode
{
int adjvex; /* 該弧所指向的頂點的位置*/
struct ArcNode *nextarc; /* 指向下一條弧的指針*/
InfoType *info; /* 網的權值指針） */
}ArcNode; /* 表結點*/
typedef struct
{
VertexType data; /* 頂點信息*/
ArcNode *firstarc; /* 第一個表結點的地址,指向第一條依附該頂點的弧的指針*/
}VNode,AdjList[MAX_VERTEX_NUM]; /* 頭結點*/
typedef struct
{
AdjList vertices;
int vexnum,arcnum; /* 圖的當前頂點數和弧數*/
int kind; /* 圖的種類標志*/
}ALGraph;
/* .........................*/
/* .........................*/
/*ALGraphAlgo.cpp 圖的鄰接表存儲(存儲結構由ALGraphDef.h 定義)的基本操作*/
int LocateVex(ALGraph G,VertexType u)
{ /* 初始條件: 圖G 存在,u 和G 中頂點有相同特徵*/
/* 操作結果: 若G 中存在頂點u,則返回該頂點在圖中位置;否則返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
Status CreateGraph(ALGraph &G)
{ /* 採用鄰接表存儲結構,構造沒有相關信息的圖G(用一個函數構造4 種圖) */
int i,j,k;
int w; /* 權值*/
VertexType va,vb;
ArcNode *p;
printf("請輸入圖的類型(有向圖:0,有向網:1,無向圖:2,無向網:3): ");
scanf("%d",&(G.kind));
printf("請輸入圖的頂點數,邊數: ");
scanf("%d,%d",&(G.vexnum),&(G.arcnum));
printf("請輸入%d 個頂點的值(<%d 個字元):\n",G.vexnum,MAX_NAME);
for(i=0;i<G.vexnum;++i) /* 構造頂點向量*/
{
scanf("%s",G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
if(G.kind==1||G.kind==3) /* 網*/
printf("請順序輸入每條弧(邊)的權值、弧尾和弧頭(以空格作為間隔):\n");
else /* 圖*/
printf("請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):\n");
for(k=0;k<G.arcnum;++k) /* 構造表結點鏈表*/
{
if(G.kind==1||G.kind==3) /* 網*/
scanf("%d%s%s",&w,va,vb);
else /* 圖*/
scanf("%s%s",va,vb);
i=LocateVex(G,va); /* 弧尾*/
j=LocateVex(G,vb); /* 弧頭*/
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if(G.kind==1||G.kind==3) /* 網*/
{
p->info=(int *)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 圖*/
p->nextarc=G.vertices[i].firstarc; /* 插在表頭*/
G.vertices[i].firstarc=p;
if(G.kind>=2) /* 無向圖或網,產生第二個表結點*/
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if(G.kind==3) /* 無向網*/
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 無向圖*/
p->nextarc=G.vertices[j].firstarc; /* 插在表頭*/
G.vertices[j].firstarc=p;
}
}
return OK;
}
void DestroyGraph(ALGraph &G)
{ /* 初始條件: 圖G 存在。操作結果: 銷毀圖G */
int i;
ArcNode *p,*q;
G.vexnum=0;
G.arcnum=0;
for(i=0;i<G.vexnum;++i)
{
p=G.vertices[i].firstarc;
while(p)
{
q=p->nextarc;
if(G.kind%2) /* 網*/
free(p->info);
free(p);
p=q;
}
}
}
VertexType* GetVex(ALGraph G,int v)
{ /* 初始條件: 圖G 存在,v 是G 中某個頂點的序號。操作結果: 返回v 的值*/
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.vertices[v].data;
}
int FirstAdjVex(ALGraph G,VertexType v)
{ /* 初始條件: 圖G 存在,v 是G 中某個頂點*/
/* 操作結果: 返回v 的第一個鄰接頂點的序號。若頂點在G 中沒有鄰接頂點,則返回-1 */
ArcNode *p;
int v1;
v1=LocateVex(G,v); /* v1 為頂點v 在圖G 中的序號*/
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ /* 初始條件: 圖G 存在,v 是G 中某個頂點,w 是v 的鄰接頂點*/
/* 操作結果: 返回v 的(相對於w 的)下一個鄰接頂點的序號。*/
/* 若w 是v 的最後一個鄰接點,則返回-1 */
ArcNode *p;
int v1,w1;
v1=LocateVex(G,v); /* v1 為頂點v 在圖G 中的序號*/
w1=LocateVex(G,w); /* w1 為頂點w 在圖G 中的序號*/
p=G.vertices[v1].firstarc;
while(p&&p->adjvex!=w1) /* 指針p 不空且所指表結點不是w */
p=p->nextarc;
if(!p||!p->nextarc) /* 沒找到w 或w 是最後一個鄰接點*/
return -1;
else /* p->adjvex==w */
return p->nextarc->adjvex; /* 返回v 的(相對於w 的)下一個鄰接頂點的序號*/
}
Boolean visited[MAX_VERTEX_NUM]; /* 訪問標志數組(全局量) */
void(*VisitFunc)(char* v); /* 函數變數(全局量) */
void DFS(ALGraph G,int v)
{ /* 從第v 個頂點出發遞歸地深度優先遍歷圖G。演算法7.5 */
int w;
VertexType v1,w1;
strcpy(v1,*GetVex(G,v));
visited[v]=TRUE; /* 設置訪問標志為TRUE(已訪問) */
VisitFunc(G.vertices[v].data); /* 訪問第v 個頂點*/
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w); /* 對v 的尚未訪問的鄰接點w 遞歸調用DFS */
}
void DFSTraverse(ALGraph G,void(*Visit)(char*))
{ /* 對圖G 作深度優先遍歷。演算法7.4 */
int v;
VisitFunc=Visit; /* 使用全局變數VisitFunc,使DFS 不必設函數指針參數*/
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; /* 訪問標志數組初始化*/
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); /* 對尚未訪問的頂點調用DFS */
printf("\n");
}
typedef int QElemType; /* 隊列類型*/
#include"LinkQueueDef.h"
#include"LinkQueueAlgo.h"
void BFSTraverse(ALGraph G,void(*Visit)(char*))
{/*按廣度優先非遞歸遍歷圖G。使用輔助隊列Q 和訪問標志數組visited。演算法7.6 */
int v,u,w;
VertexType u1,w1;
LinkQueue Q;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE; /* 置初值*/
InitQueue(Q); /* 置空的輔助隊列Q */
for(v=0;v<G.vexnum;v++) /* 如果是連通圖,只v=0 就遍歷全圖*/
if(!visited[v]) /* v 尚未訪問*/
{
visited[v]=TRUE;
Visit(G.vertices[v].data);
EnQueue(Q,v); /* v 入隊列*/
while(!QueueEmpty(Q)) /* 隊列不空*/
{
DeQueue(Q,u); /* 隊頭元素出隊並置為u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w 為u 的尚未訪問的鄰接頂點*/
{
visited[w]=TRUE;
Visit(G.vertices[w].data);
EnQueue(Q,w); /* w 入隊*/
}
}
}
printf("\n");
}
void Display(ALGraph G)
{ /* 輸出圖的鄰接矩陣G */
int i;
ArcNode *p;
switch(G.kind)
{ case DG: printf("有向圖\n"); break;
case DN: printf("有向網\n"); break;
case AG: printf("無向圖\n"); break;
case AN: printf("無向網\n");
}
printf("%d 個頂點：\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.vertices[i].data);
printf("\n%d 條弧(邊):\n",G.arcnum);
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
if(G.kind<=1) /* 有向*/
{
printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==DN) /* 網*/
printf(":%d ",*(p->info));
}
else /* 無向(避免輸出兩次) */
{
if(i<p->adjvex)
{
printf("%s－%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==AN) /* 網*/
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("\n");
}
}
/* .........................*/
/* .........................*/
#include "pubuse.h"
#define MAX_NAME 3 /* 頂點字元串的最大長度+1 */
typedef int InfoType; /* 存放網的權值*/
typedef char VertexType[MAX_NAME]; /* 字元串類型*/
#include"ALGraphDef.h"
#include"ALGraphAlgo.h"
void print(char *i)
{
printf("%s ",i);
}
void main()
{
int i,j,k,n;
ALGraph g;
VertexType v1,v2;
printf("請選擇有向圖\n");
CreateGraph(g);
Display(g);
printf("深度優先搜索的結果:\n");
DFSTraverse(g,print);
printf("廣度優先搜索的結果:\n");
BFSTraverse(g,print);
DestroyGraph(g); /* 銷毀圖*/
}
❷ 無向圖採用鄰接表存儲結構,編寫演算法輸出圖中各連通分量的節點序列
//按廣度優先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數組visited.僅適用於鄰接表結構
void BFSTraverse1(ALGraph G,void(* Visit)(char *))
{
int v,u;
ArcNode * p;//p指向表結點
LinkQueue Q;//鏈隊列類型
for (v=0; v<G.vexnum; ++v)
{
visited[v] = FALSE;//置初值為未被訪問
}
InitQueue(&Q);//初始化輔助隊列Q
for (v=0; v<G.vexnum; ++v)//如果是連通圖，只v=0就遍歷全圖
{
if (! visited[v])//v尚未被訪問
{
visited[v] = TRUE;//設v為已被訪問
Visit(G.vertices[v].data);//訪問v
EnQueue(&Q,v);//v入隊
while (! QueueEmpty(Q))//隊列不空
{
DeQueue(&Q,&u);//隊頭元素出隊並置為u
for (p=G.vertices[u].firstarc; p; p=p->next)//p依次指向u的鄰接頂點
{
if (! visited[p->data.adjvex])//u的鄰接頂點尚未被訪問
{
visited[p->data.adjvex] = TRUE;//該鄰接頂點設為已被訪問
Visit(G.vertices[p->data.adjvex].data);//訪問該鄰接頂點
EnQueue(&Q,p->data.adjvex);//入隊該鄰接頂點序號
}
}
}//while
}//if
}//for(v=......)
printf("\n");
}
❸ C語言代碼 有向無環圖最長路徑的演算法 圖用領接表存儲
無向無環圖就是樹，
從根出發：
如果是計算最多的路徑，就用廣度優先（層次遍歷）就可以了，最後訪問的頂點一定是最多的路徑的
如果是計算最長的路徑長度，直接將上面的演算法改一下，每個頂點時記下前面的來路的值加上現在的，就可以求出最大值
或者直接用Dijkstra 演算法就可以了
❹ 操作系統(四)文件管理
文件—就是一組有意義的信息/數據集合
文件屬於抽象數據類型。為了恰當地定義文件，需要考慮有關文件的操作。操作系統提供系統調用，它對文件進行創建、寫、讀、重定位、搠除和截斷等操作。
所謂的「邏輯結構」，就是指在用戶看來，文件內部的數據應該是如何組織起來的。而「物理結構」指的是在操作系統看來，文件的數據是如何存放在外存中的。
無結構文件：文件內部的數據就是一系列二進制流或字元流組成。又稱「流式文件」
文件內部的數據其實就是一系列字元流，沒有明顯的結構特性。因此也不用探討無結構文件的「邏輯結構」問題。
有結構文件：由一組相似的記錄組成，又稱「記錄式文件」。每條記錄又若干個數據項組成。 [1] 一般來說，每條記錄有一個數據項可作為關鍵字。根據各條記錄的長度（佔用的存儲空間）是否相等，又可分為定長記錄和可變長記錄兩種。有結構文件按記錄的組織形式可以分為：
對於含有N條記錄的順序文件，查找某關鍵字值的記錄時，平均需要查找N/2次。在索引順序文件中，假設N條記錄分為√N組，索引表中有√N個表項，每組有√N條記錄，在查找某關鍵字值的記錄時，先順序查找索引表，需要查找√N /2次，然後在主文件中對應的組中順序查找，也需要查找√N/2次，因此共需查找√N/2+√N/2=√N次。顯然，索引順序文件提高了查找效率，若記錄數很多，則可採用兩級或多級索引
FCB的有序集合稱為「文件目錄」，一個FCB就是一個文件目錄項。FCB中包含了文件的基本信息（文件名、物理地址、邏輯結構、物理結構等），存取控制信息（是否可讀/可寫、禁止訪問的用戶名單等），使用信息（如文件的建立時間、修改時間等）。最重要，最基本的還是文件名、文件存放的物理地址。
對目錄的操作如下：
操作的時候，可以有以下幾種目錄結構：
早期操作系統並不支持多級目錄，整個系統中只建立一張目錄表，每個文件佔一個目錄項。
單級目錄實現了「按名存取」，但是不允許文件重名。在創建一個文件時，需要先檢查目錄表中有沒有重名文件，確定不重名後才能允許建立文件，並將新文件對應的目錄項插入目錄表中。顯然， 單級目錄結構不適用於多用戶操作系統。
早期的多用戶操作系統，採用兩級目錄結構。分為主文件目錄（MFD，Master File Directory）和用戶文件目錄（UFD，User Flie Directory）。
允許不同用戶的文件重名。文件名雖然相同，但是對應的其實是不同的文件。兩級目錄結構允許不同用戶的文件重名，也可以在目錄上實現實現訪問限制（檢查此時登錄的用戶名是否匹配）。但是兩級目錄結構依然缺乏靈活性，用戶不能對自己的文件進行分類
用戶（或用戶進程）要訪問某個文件時要用文件路徑名標識文件，文件路徑名是個字元串。各級目錄之間用「/」隔開。從根目錄出發的路徑稱為絕對路徑。
系統根據絕對路徑一層一層地找到下一級目錄。剛開始從外存讀入根目錄的目錄表；找到目錄的存放位置後，從外存讀入對應的目錄表；再找到目錄的存放位置，再從外存讀入對應目錄表；最後才找到文件的存放位置。整個過程需要3次讀磁碟I/O操作。
很多時候，用戶會連續訪問同一目錄內的多個文件，顯然，每次都從根目錄開始查找，是很低效的。因此可以設置一個「當前目錄」。此時已經打開了的目錄文件，也就是說，這張目錄表已調入內存，那麼可以把它設置為「當前目錄」。當用戶想要訪問某個文件時，可以使用從當前目錄出發的「相對路徑」
可見，引入「當前目錄」和「相對路徑」後，磁碟I/O的次數減少了。這就提升了訪問文件的效率。
樹形目錄結構可以很方便地對文件進行分類，層次結構清晰，也能夠更有效地進行文件的管理和保護。但是，樹形結構不便於實現文件的共享。為此，提出了「無環圖目錄結構」。
可以用不同的文件名指向同一個文件，甚至可以指向同一個目錄（共享同一目錄下的所有內容）。需要為每個共享結點設置一個共享計數器，用於記錄此時有多少個地方在共享該結點。用戶提出刪除結點的請求時，只是刪除該用戶的FCB、並使共享計數器減1，並不會直接刪除共享結點。只有共享計數器減為0時，才刪除結點。
其實在查找各級目錄的過程中只需要用到「文件名」這個信息，只有文件名匹配時，才需要讀出文件的其他信息。因此可以考慮讓目錄表「瘦身」來提升效率。
當找到文件名對應的目錄項時，才需要將索引結點調入內存，索引結點中記錄了文件的各種信息，包括文件在外存中的存放位置，根據「存放位置」即可找到文件。存放在外存中的索引結點稱為「磁碟索引結點」，當索引結點放入內存後稱為「內存索引結點」。相比之下內存索引結點中需要增加一些信息，比如：文件是否被修改、此時有幾個進程正在訪問該文件等。
為文件設置一個「口令」（如：abc112233），用戶請求訪問該文件時必須提供「口令」。
優點：保存口令的空間開銷不多，驗證口令的時間開銷也很小。
缺點：正確的「口令」存放在系統內部，不夠安全。
使用某個「密碼」對文件進行加密，在訪問文件時需要提供正確的「密碼」才能對文件進行正確的解密。 [3]
優點：保密性強，不需要在系統中存儲「密碼」
缺點：編碼/解碼，或者說加密/解密要花費一定時間。
在每個文件的FCB（或索引結點）中增加一個訪問控制列表（Access-Control List, ACL），該表中記錄了各個用戶可以對該文件執行哪些操作。
有的計算機可能會有很多個用戶，因此訪問控制列表可能會很大，可以用精簡的訪問列表解決這個問題
精簡的訪問列表：以「組」為單位，標記各「組」用戶可以對文件執行哪些操作。當某用戶想要訪問文件時，系統會檢查該用戶所屬的分組是否有相應的訪問許可權。
索引結點，是一種文件目錄瘦身策略。由於檢索文件時只需用到文件名，因此可以將除了文件名之外的其他信息放到索引結點中。這樣目錄項就只需要包含文件名、索引結點指針。
索引結點中設置一個鏈接計數變數count，用於表示鏈接到本索引結點上的用戶目錄項數。
當User3訪問「ccc」時，操作系統判斷文件「ccc」屬於Link類型文件，於是會根據其中記錄的路徑層層查找目錄，最終找到User1的目錄表中的「aaa」表項，於是就找到了文件1的索引結點。
類似於內存分頁，磁碟中的存儲單元也會被分為一個個「塊/磁碟塊/物理塊」。很多操作系統中，磁碟塊的大小與內存塊、頁面的大小相同
內存與磁碟之間的數據交換（即讀/寫操作、磁碟I/O）都是以「塊」為單位進行的。即每次讀入一塊，或每次寫出一塊
在內存管理中，進程的邏輯地址空間被分為一個一個頁面同樣的，在外存管理中，為了方便對文件數據的管理，文件的邏輯地址空間也被分為了一個一個的文件「塊」。於是文件的邏輯地址也可以表示為（邏輯塊號，塊內地址）的形式。用戶通過邏輯地址來操作自己的文件，操作系統要負責實現從邏輯地址到物理地址的映射
連續分配方式要求每個文件在磁碟上佔有一組連續的塊。用戶給出要訪問的邏輯塊號，操作系統找到該文件對應的目錄項（FCB）——可以直接算出邏輯塊號對應的物理塊號，物理塊號=起始塊號+邏輯塊號。還需要檢查用戶提供的邏輯塊號是否合法（邏輯塊號≥ 長度就不合法）因此 連續分配支持順序訪問和直接訪問 （即隨機訪問）
讀取某個磁碟塊時，需要移動磁頭。訪問的兩個磁碟塊相隔越遠，移動磁頭所需時間就越長。 連續分配的文件在順序讀/寫時速度最快，物理上採用連續分配的文件不方便拓展，且存儲空間利用率低，會產生難以利用的磁碟碎片可以用緊湊來處理碎片，但是需要耗費很大的時間代價。。
鏈接分配採取離散分配的方式，可以為文件分配離散的磁碟塊。分為隱式鏈接和顯式鏈接兩種。
用戶給出要訪問的邏輯塊號i，操作系統找到該文件對應的目錄項（FCB）…從目錄項中找到起始塊號（即0號塊），將0號邏輯塊讀入內存，由此知道1號邏輯塊存放的物理塊號，於是讀入1號邏輯塊，再找到2號邏輯塊的存放位置……以此類推。因此，讀入i號邏輯塊，總共需要i+1次磁碟I/O。
採用鏈式分配（隱式鏈接）方式的文件，只支持順序訪問，不支持隨機訪問，查找效率低。另外，指向下一個盤塊的指針也需要耗費少量的存儲空間。但是，採用隱式鏈接的鏈接分配方式，很方便文件拓展。另外，所有的空閑磁碟塊都可以被利用，不會有碎片問題，外存利用率高。
把用於鏈接文件各物理塊的指針顯式地存放在一張表中。即文件分配表（FAT，File Allocation Table）
一個磁碟僅設置一張FAT 。開機時，將FAT讀入內存，並常駐內存。FAT的各個表項在物理上連續存儲，且每一個表項長度相同，因此「物理塊號」欄位可以是隱含的。
從目錄項中找到起始塊號，若i>0，則查詢內存中的文件分配表FAT，往後找到i號邏輯塊對應的物理塊號。 邏輯塊號轉換成物理塊號的過程不需要讀磁碟操作。
採用鏈式分配（顯式鏈接）方式的文件，支持順序訪問，也支持隨機訪問 （想訪問i號邏輯塊時，並不需要依次訪問之前的0 ~ i-1號邏輯塊）， 由於塊號轉換的過程不需要訪問磁碟，因此相比於隱式鏈接來說，訪問速度快很多。顯然，顯式鏈接也不會產生外部碎片，也可以很方便地對文件進行拓展。
索引分配允許文件離散地分配在各個磁碟塊中，系統會為每個文件建立一張索引表，索引表中記錄了文件的各個邏輯塊對應的物理塊（索引表的功能類似於內存管理中的頁表——建立邏輯頁面到物理頁之間的映射關系）。索引表存放的磁碟塊稱為索引塊。文件數據存放的磁碟塊稱為數據塊。
在顯式鏈接的鏈式分配方式中，文件分配表FAT是一個磁碟對應一張。而索引分配方式中，索引表是一個文件對應一張。可以用固定的長度表示物理塊號 [4] ，因此，索引表中的「邏輯塊號」可以是隱含的。
用戶給出要訪問的邏輯塊號i，操作系統找到該文件對應的目錄項（FCB）…從目錄項中可知索引表存放位置，將索引表從外存讀入內存，並查找索引表即可只i號邏輯塊在外存中的存放位置。
可見， 索引分配方式可以支持隨機訪問。文件拓展也很容易實現 （只需要給文件分配一個空閑塊，並增加一個索引表項即可）但是 索引表需要佔用一定的存儲空間
索引塊的大小是一個重要的問題，每個文件必須有一個索引塊，因此索引塊應盡可能小，但索引塊太小就無法支持大文件，可以採用以下機制：
空閑表法適用於「連續分配方式」。分配磁碟塊：與內存管理中的動態分區分配很類似，為一個文件分配連續的存儲空間。同樣可採用首次適應、最佳適應、最壞適應等演算法來決定要為文件分配哪個區間。回收磁碟塊：與內存管理中的動態分區分配很類似，當回收某個存儲區時需要有四種情況——①回收區的前後都沒有相鄰空閑區；②回收區的前後都是空閑區；③回收區前面是空閑區；④回收區後面是空閑區。總之，回收時需要注意表項的合並問題。
操作系統保存著鏈頭、鏈尾指針。如何分配：若某文件申請K個盤塊，則從鏈頭開始依次摘下K個盤塊分配，並修改空閑鏈的鏈頭指針。如何回收：回收的盤塊依次掛到鏈尾，並修改空閑鏈的鏈尾指針。適用於離散分配的物理結構。為文件分配多個盤塊時可能要重復多次操作
操作系統保存著鏈頭、鏈尾指針。如何分配：若某文件申請K個盤塊，則可以採用首次適應、最佳適應等演算法，從鏈頭開始檢索，按照演算法規則找到一個大小符合要求的空閑盤區，分配給文件。若沒有合適的連續空閑塊，也可以將不同盤區的盤塊同時分配給一個文件，注意分配後可能要修改相應的鏈指針、盤區大小等數據。如何回收：若回收區和某個空閑盤區相鄰，則需要將回收區合並到空閑盤區中。若回收區沒有和任何空閑區相鄰，將回收區作為單獨的一個空閑盤區掛到鏈尾。 離散分配、連續分配都適用。為一個文件分配多個盤塊時效率更高
位示圖：每個二進制位對應一個盤塊。在本例中，「0」代表盤塊空閑，「1」代表盤塊已分配。位示圖一般用連續的「字」來表示，如本例中一個字的字長是16位，字中的每一位對應一個盤塊。因此可以用（字型大小，位號）對應一個盤塊號。當然有的題目中也描述為（行號，列號）
盤塊號、字型大小、位號從0開始，若n表示字長，則
如何分配：若文件需要K個塊，①順序掃描位示圖，找到K個相鄰或不相鄰的「0」；②根據字型大小、位號算出對應的盤塊號，將相應盤塊分配給文件；③將相應位設置為「1」。如何回收：①根據回收的盤塊號計算出對應的字型大小、位號；②將相應二進制位設為「0」
空閑表法、空閑鏈表法不適用於大型文件系統，因為空閑表或空閑鏈表可能過大。UNIX系統中採用了成組鏈接法對磁碟空閑塊進行管理。文件卷的目錄區中專門用一個磁碟塊作為「超級塊」，當系統啟動時需要將超級塊讀入內存。並且要保證內存與外存中的「超級塊」數據一致。
進行Create系統調用時，需要提供的幾個主要參數：
操作系統在處理Create系統調用時，主要做了兩件事：
進行Delete系統調用時，需要提供的幾個主要參數：
操作系統在處理Delete系統調用時，主要做了幾件
事：
在很多操作系統中，在對文件進行操作之前，要求用戶先使用open系統調用「打開文件」，需要提供的幾個主要參數：
操作系統在處理open系統調用時，主要做了幾件事：
進程使用完文件後，要「關閉文件」
操作系統在處理Close系統調用時，主要做了幾件事：
進程使用read系統調用完成寫操作。需要指明是哪個文件（在支持「打開文件」操作的系統中，只需要提供文件在打開文件表中的索引號即可），還需要指明要讀入多少數據（如：讀入1KB）、指明讀入的數據要放在內存中的什麼位置。操作系統在處理read系統調用時，會從讀指針指向的外存中，將用戶指定大小的數據讀入用戶指定的內存區域中。
進程使用write系統調用完成寫操作，需要指明是哪個文件（在支持「打開文件」操作的系統中，只需要提供文件在打開文件表中的索引號即可），還需要指明要寫出多少數據（如：寫出1KB）、寫回外存的數據放在內存中的什麼位置操作系統在處理write系統調用時，會從用戶指定的內存區域中，將指定大小的數據寫回寫指針指向的外存。
尋找時間（尋道時間）T S ：在讀/寫數據前，將磁頭移動到指定磁軌所花的時間。
延遲時間T R ：通過旋轉磁碟，使磁頭定位到目標扇區所需要的時間。設磁碟轉速為r（單位：轉/秒，或轉/分），則平均所需的延遲時間
傳輸時間T t ：從磁碟讀出或向磁碟寫入數據所經歷的時間，假設磁碟轉速為r，此次讀/寫的位元組數為b，每個磁軌上的位元組數為N。則
總的平均存取時間Ta
延遲時間和傳輸時間都與磁碟轉速相關，且為線性相關。而轉速是硬體的固有屬性，因此操作系統也無法優化延遲時間和傳輸時間，但是操作系統的磁碟調度演算法會直接影響尋道時間
根據進程請求訪問磁碟的先後順序進行調度。
優點：公平；如果請求訪問的磁軌比較集中的話，演算法性能還算過的去
缺點：如果有大量進程競爭使用磁碟，請求訪問的磁軌很分散，則FCFS在性能上很差，尋道時間長。
SSTF演算法會優先處理的磁軌是與當前磁頭最近的磁軌。可以保證每次的尋道時間最短，但是並不能保證總的尋道時間最短。（其實就是貪心演算法的思想，只是選擇眼前最優，但是總體未必最優）
優點：性能較好，平均尋道時間短
缺點：可能產生「飢餓」現象
SSTF演算法會產生飢餓的原因在於：磁頭有可能在一個小區域內來回來去地移動。為了防止這個問題，可以規定，只有磁頭移動到最外側磁軌的時候才能往內移動，移動到最內側磁軌的時候才能往外移動。這就是掃描演算法（SCAN）的思想。由於磁頭移動的方式很像電梯，因此也叫電梯演算法。
優點：性能較好，平均尋道時間較短，不會產生飢餓現象
缺點：①只有到達最邊上的磁軌時才能改變磁頭移動方向②SCAN演算法對於各個位置磁軌的響應頻率不平均
掃描演算法（SCAN）中，只有到達最邊上的磁軌時才能改變磁頭移動方向，事實上，處理了184號磁軌的訪問請求之後就不需要再往右移動磁頭了。LOOK調度演算法就是為了解決這個問題，如果在磁頭移動方向上已經沒有別的請求，就可以立即改變磁頭移動方向。（邊移動邊觀察，因此叫LOOK）
優點：比起SCAN演算法來，不需要每次都移動到最外側或最內側才改變磁頭方向，使尋道時間進一步縮短
SCAN演算法對於各個位置磁軌的響應頻率不平均，而C-SCAN演算法就是為了解決這個問題。規定只有磁頭朝某個特定方向移動時才處理磁軌訪問請求，而返回時直接快速移動至起始端而不處理任何請求。
優點：比起SCAN來，對於各個位置磁軌的響應頻率很平均。
缺點：只有到達最邊上的磁軌時才能改變磁頭移動方向，另外，比起SCAN演算法來，平均尋道時間更長。
C-SCAN演算法的主要缺點是只有到達最邊上的磁軌時才能改變磁頭移動方向，並且磁頭返回時不一定需要返回到最邊緣的磁軌上。C-LOOK演算法就是為了解決這個問題。如果磁頭移動的方向上已經沒有磁軌訪問請求了，就可以立即讓磁頭返回，並且磁頭只需要返回到有磁軌訪問請求的位置即可。
優點：比起C-SCAN演算法來，不需要每次都移動到最外側或最內側才改變磁頭方向，使尋道時間進一步縮短
磁碟地址結構的設計：
Q：磁碟的物理地址是（柱面號，盤面號，扇區號）而不是（盤面號，柱面號，扇區號）
A：讀取地址連續的磁碟塊時，採用（柱面號，盤面號，扇區號）的地址結構可以減少磁頭移動消耗的時間
減少延遲時間的方法：
Step 1：進行低級格式化（物理格式化），將磁碟的各個磁軌劃分為扇區。一個扇區通常可分為頭、數據區域（如512B大小）、尾三個部分組成。管理扇區所需要的各種數據結構一般存放在頭、尾兩個部分，包括扇區校驗碼（如奇偶校驗、CRC循環冗餘校驗碼等，校驗碼用於校驗扇區中的數據是否發生錯誤）
Step 2：將磁碟分區，每個分區由若干柱面組成（即分為我們熟悉的C盤、D盤、E盤）
Step 3：進行邏輯格式化，創建文件系統。包括創建文件系統的根目錄、初始化存儲空間管理所用的數據結構（如位示圖、空閑分區表）
計算機開機時需要進行一系列初始化的工作，這些初始化工作是通過執行初始化程序（自舉程序）完成的
初始化程序可以放在ROM（只讀存儲器）中。ROM中的數據在出廠時就寫入了，並且以後不能再修改。ROM中只存放很小的「自舉裝入程序」，完整的自舉程序放在磁碟的啟動塊（即引導塊/啟動分區）上，啟動塊位於磁碟的固定位置，開機時計算機先運行「自舉裝入程序」，通過執行該程序就可找到引導塊，並將完整的「自舉程序」讀入內存，完成初始化。擁有啟動分區的磁碟稱為啟動磁碟或系統磁碟（C:盤）
對於簡單的磁碟，可以在邏輯格式化時（建立文件系統時）對整個磁碟進行壞塊檢查，標明哪些扇區是壞扇區，比如：在FAT表上標明。（在這種方式中，壞塊對操作系統不透明）。
對於復雜的磁碟，磁碟控制器（磁碟設備內部的一個硬體部件）會維護一個壞塊鏈表。在磁碟出廠前進行低級格式化（物理格式化）時就將壞塊鏈進行初始化。會保留一些「備用扇區」，用於替換壞塊。這種方案稱為扇區備用。且這種處理方式中，壞塊對操作系統透明
❺ 有誰知道能解釋一下有向無環圖(DAG)么怎麼用程序做出來，及怎麼應用到經濟學實證上
我們說區塊鏈目前還不成熟，有各種各樣的問題，比如說處理速度慢、手續費高昂、存在安全隱患等等，這些都是用戶最直觀的體驗，體驗不是太好。區塊鏈還有一個問題，那就是高並發問題。
高並發問題是怎麼回事呢，我們簡單說一下。高並發是計算機領域的問題，簡單來講，高並發問題就是系統無法順利同時運行多個任務。
很多任務同時運行，一大堆用戶涌進來，系統承受不住這么多的任務，會出現高並發問題，你的系統就卡住了，就好比春運時候，12306系統總是卡住，有可能就是高並發問題造成的。
傳統互聯網尚且存在高並發問題，區塊鏈網路自然也存在這個問題，畢竟區塊鏈的成熟程度比起傳統互聯網，還有很大的差距。但是，如果沒有安全、可靠和高效的公鏈，整個區塊鏈產業的發展都將受到嚴重製約，應用落地也是空談。
在這種背景下，DAG 技術就被提出來了，DAG 的全稱是「Directed Acyclic Graph」，中文翻譯為「有向無環圖」。
DAG有向無環圖是怎麼回事呢，它到底能起到什麼作用呢？我們下面解釋一下。
一、DAG：一個新型的數據結構
DAG，中文名字叫「有向無環圖」，從字面意思看，「有向"就是說它是有方向的，
「無環」就是說它是沒有環路的、不能形成閉環的。所以，DAG其實是一種新型的數據結構，這個數據結構是有方向的，同時又是不能形成閉環的。
傳統區塊來講，我們總是以「區塊」為單位，一個區塊里往往包含了多筆交易信息。而在DAG中，沒有區塊的概念，而是以「單元」為單位，每個單元記錄的是單個用戶的交易，組成的單元不是區塊，而是一筆筆的交易，這樣一來，可以省去打包出塊的時間。
簡單來說，區塊鏈和DAG有向無環圖最大的區別就是：區塊鏈是一個接一個的區塊來存儲和驗證交易的分布式賬本，而DAG則是把每筆交易都看成一個區塊，每一筆交易都可以鏈接到多個先前的交易來進行驗證。
二、DAG 的工作原理
傳統區塊鏈上，就拿比特幣來講，它是單鏈式的結構，區塊與區塊之間按照時間戳的先後順序排列開來（如圖一），數據記錄在一條主鏈上。用不太恰當的比喻來講，這個
「單鏈式」結構是一條一字排列的鏈。
區塊鏈只有一條單鏈，打包出塊就無法並發執行。新的區塊會加入到原先的最長鏈之上，所有節點都以最長鏈為准，繼續按照時間戳的順序無限蔓延下去。而對於DAG來講，每個新加入的單元，不僅只加入到最長鏈的一個單元，還要加入到之前所有的單元（如圖二）。
舉個例子：假設我發布了一個新的交易，此時DAG結構已經有2個有效的交易單元，那麼我的交易單元會主動同時鏈接到前面的2個之中，去驗證並確認，直到鏈接到創世單元，而且，上一個單元的哈希會包含到自己的單元裡面。
換句話說，你要想進行一筆交易，就必須要驗證前面的交易，具體驗證幾個交易，根據不同的規則來進行。這種驗證手段，使得DAG可以非同步並發的寫入很多交易，並最終構成一種拓撲的樹狀結構，極大地提高擴展性。
依據DAG有向無環圖，每一筆交易都直接參與了維護全網。當交易發起後，直接廣播全網，跳過礦工打包區塊階段，這樣就省去了打包交易出塊的時間，提升了區塊鏈處理交易的效率。
隨著時間遞增，所有交易的區塊鏈相互連接，形成圖狀結構，如果要更改數據，那就不僅僅是幾個區塊的問題了，而是整個區塊圖的數據更改。DAG這個模式相比來說，要進行的復雜度更高，更難以被更改。
總結一下，DAG作為一種新型的去中心化數據結構，它屬於廣義區塊鏈的一種，具備去中心化的屬性，但是二者的不同之處在於：
區塊鏈組成單元是Block（區塊），DAG組成單元是TX（交易）。
區塊鏈是單線程，DAG是多線程。
區塊鏈所有交易記錄記在同一個區塊中，DAG每筆交易單獨記錄在每筆交易中。
區塊鏈需要礦工，DAG不需要礦工。
三、 DAG 的代表：IOTA
DAG當前的代表項目，最知名的無疑就是 IOTA。可以說，正是因為IOTA這個幣種在 2017年下半年沖進市值排行第四位，才使人們真正認識到了它的底層技術：DAG有向無環圖。
IOTA在DAG有向無環圖的基礎上提出了「纏結」概念，在IOTA裡面，沒有區塊的概念，共識的最小單位是交易。每一個交易都會引用過去的兩條交易記錄哈希，這樣前一交易會證明過去兩條交易的合法性，間接證明之前所有交易的合法性。這樣一來， 就不再需要傳統區塊鏈中的礦工這樣少量節點來驗證交易、打包區塊，從而提升效率，節省交易費用。
四、 DAG 的現狀
盡管理論上來講，DAG有向無環圖能夠彌補傳統區塊鏈的一些弊端，但是目前並不成熟，應用到數字貨幣領域的時間也比較短，還比較年輕 。
它沒有像比特幣那般經過長達10年的時間來驗證整個系統的安全性，也沒有像以太坊那般實現了廣泛的應用場景。不過，現在有些聲音提出要採用「傳統區塊鏈+DAG」的數據結構，但是還沒有非常突出的案例，這里就不多說了。
總結一下，本節我們介紹了區塊鏈的衍生技術：DAG有向無環圖，這是一種全新的數據結構，可以對區塊鏈處理交易的效率、並發力達到顯著的提升。
❻ 拓撲排序 編程
*/
#include <stdio.h>
#include <malloc.h>
// 輸出有向圖的一個拓撲序列。實現演算法7.12的程序
// 圖的鄰接表存儲表示
#define MAX_NAME 3 // 頂點字元串的最大長度+1
#define MAX_VERTEX_NUM 20
typedef int InfoType; // 存放網的權值
typedef char VertexType[MAX_NAME]; // 字元串類型
typedef enum{DG,DN,AG,AN}GraphKind; // {有向圖,有向網,無向圖,無向網}
typedef struct ArcNode
{
int adjvex; // 該弧所指向的頂點的位置
struct ArcNode *nextarc; // 指向下一條弧的指針
InfoType *info; // 網的權值指針）
}ArcNode; // 表結點
typedef struct VNode
{
VertexType data; // 頂點信息
ArcNode *firstarc; // 第一個表結點的地址,指向第一條依附該頂點的弧的指針
}VNode,AdjList[MAX_VERTEX_NUM];// 頭結點
typedef struct
{
AdjList vertices;
int vexnum,arcnum; // 圖的當前頂點數和弧數
int kind; // 圖的種類標志
}ALGraph;
// 若G中存在頂點u,則返回該頂點在圖中位置;否則返回-1。
int LocateVex(ALGraph G,VertexType u)
{
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
// 採用鄰接表存儲結構,構造沒有相關信息的圖G(用一個函數構造4種圖)。
int CreateGraph(ALGraph *G)
{
int i,j,k;
int w; // 權值
VertexType va,vb;
ArcNode *p;
printf("請輸入圖的類型(有向圖:0,有向網:1,無向圖:2,無向網:3): ");
scanf("%d",&(*G).kind);
printf("請輸入圖的頂點數和邊數:（空格）\n");
scanf("%d%d", &(*G).vexnum, &(*G).arcnum);
printf("請輸入%d個頂點的值(<%d個字元):\n",(*G).vexnum,MAX_NAME);
for(i = 0; i < (*G).vexnum; ++i) // 構造頂點向量
{
scanf("%s", (*G).vertices[i].data);
(*G).vertices[i].firstarc = NULL;
}
if((*G).kind == 1 || (*G).kind == 3) // 網
printf("請順序輸入每條弧(邊)的權值、弧尾和弧頭(以空格作為間隔):\n");
else // 圖
printf("請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):\n");
for(k = 0;k < (*G).arcnum; ++k) // 構造表結點鏈表
{
if((*G).kind==1||(*G).kind==3) // 網
scanf("%d%s%s",&w,va,vb);
else // 圖
scanf("%s%s",va,vb);
i = LocateVex(*G,va); // 弧尾
j = LocateVex(*G,vb); // 弧頭
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
if((*G).kind == 1 || (*G).kind == 3) // 網
{
p->info = (int *)malloc(sizeof(int));
*(p->info) = w;
}
else
p->info = NULL; // 圖
p->nextarc = (*G).vertices[i].firstarc; // 插在表頭
(*G).vertices[i].firstarc = p;
if((*G).kind >= 2) // 無向圖或網,產生第二個表結點
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
if((*G).kind == 3) // 無向網
{
p->info = (int*)malloc(sizeof(int));
*(p->info) = w;
}
else
p->info = NULL; // 無向圖
p->nextarc = (*G).vertices[j].firstarc; // 插在表頭
(*G).vertices[j].firstarc = p;
}
}
return 1;
}
// 輸出圖的鄰接表G。
void Display(ALGraph G)
{
int i;
ArcNode *p;
switch(G.kind)
{
case DG: printf("有向圖\n");
break;
case DN: printf("有向網\n");
break;
case AG: printf("無向圖\n");
break;
case AN: printf("無向網\n");
}
printf("%d個頂點：\n",G.vexnum);
for(i = 0; i < G.vexnum; ++i)
printf("%s ",G.vertices[i].data);
printf("\n%d條弧(邊):\n", G.arcnum);
for(i = 0; i < G.vexnum; i++)
{
p = G.vertices[i].firstarc;
while(p)
{
if(G.kind <= 1) // 有向
{
printf("%s→%s ",G.vertices[i].data,
G.vertices[p->adjvex].data);
if(G.kind == DN) // 網
printf(":%d ", *(p->info));
}
else // 無向(避免輸出兩次)
{
if(i < p->adjvex)
{
printf("%s－%s ",G.vertices[i].data,
G.vertices[p->adjvex].data);
if(G.kind == AN) // 網
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("\n");
}
}
// 求頂點的入度，演算法7.12、7.13調用
void FindInDegree(ALGraph G,int indegree[])
{
int i;
ArcNode *p;
for(i=0;i<G.vexnum;i++)
indegree[i]=0; // 賦初值
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
indegree[p->adjvex]++;
p=p->nextarc;
}
}
}
typedef int SElemType; // 棧類型
#define STACK_INIT_SIZE 10 // 存儲空間初始分配量
#define STACKINCREMENT 2 // 存儲空間分配增量
// 棧的順序存儲表示 P46
typedef struct SqStack
{
SElemType *base; // 在棧構造之前和銷毀之後，base的值為NULL
SElemType *top; // 棧頂指針
int stacksize; // 當前已分配的存儲空間，以元素為單位
}SqStack; // 順序棧
// 構造一個空棧S。
int InitStack(SqStack *S)
{
// 為棧底分配一個指定大小的存儲空間
(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if( !(*S).base )
exit(0); // 存儲分配失敗
(*S).top = (*S).base; // 棧底與棧頂相同表示一個空棧
(*S).stacksize = STACK_INIT_SIZE;
return 1;
}
// 若棧S為空棧（棧頂與棧底相同的），則返回1，否則返回0。
int StackEmpty(SqStack S)
{
if(S.top == S.base)
return 1;
else
return 0;
}
// 插入元素e為新的棧頂元素。
int Push(SqStack *S, SElemType e)
{
if((*S).top - (*S).base >= (*S).stacksize) // 棧滿，追加存儲空間
{
(*S).base = (SElemType *)realloc((*S).base,
((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));
if( !(*S).base )
exit(0); // 存儲分配失敗
(*S).top = (*S).base+(*S).stacksize;
(*S).stacksize += STACKINCREMENT;
}
*((*S).top)++=e;
// 這個等式的++ * 優先順序相同，但是它們的運算方式，是自右向左
return 1;
}
// 若棧不空，則刪除S的棧頂元素，用e返回其值，並返回1；否則返回0。
int Pop(SqStack *S,SElemType *e)
{
if((*S).top == (*S).base)
return 0;
*e = *--(*S).top;
// 這個等式的++ * 優先順序相同，但是它們的運算方式，是自右向左
return 1;
}
// 演算法7.12 P182
// 有向圖G採用鄰接表存儲結構。若G無迴路,則輸出G的頂點的一個拓撲序
// 列並返回1, 否則返回0。
int TopologicalSort(ALGraph G)
{
int i,k,count,indegree[MAX_VERTEX_NUM];
SqStack S;
ArcNode *p;
FindInDegree(G,indegree); // 對各頂點求入度indegree[0..vernum-1]
InitStack(&S); // 初始化棧
for(i=0;i<G.vexnum;++i) // 建零入度頂點棧S
if(!indegree[i])
Push(&S,i); // 入度為0者進棧
count=0; // 對輸出頂點計數
while(!StackEmpty(S))
{
// 棧不空
Pop(&S,&i);
printf("%s ",G.vertices[i].data); // 輸出i號頂點並計數
++count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
// 對i號頂點的每個鄰接點的入度減1
k=p->adjvex;
if(!(--indegree[k])) // 若入度減為0,則入棧
Push(&S,k);
}
}
if(count<G.vexnum)
{
printf("此有向圖有迴路\n");
return 0;
}
else
{
printf("為一個拓撲序列。\n");
return 1;
}
}
int main()
{
ALGraph f;
printf("請選擇有向圖\n");
CreateGraph(&f);
Display(f);
TopologicalSort(f);
system("pause");
return 0;
}
/*
輸出效果：
請選擇有向圖
請輸入圖的類型(有向圖:0,有向網:1,無向圖:2,無向網:3): 0
請輸入圖的頂點數和邊數:（空格）
4 4
請輸入4個頂點的值(<3個字元):
a
b
c
d
請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):
a b
a c
b d
c d
有向圖
4個頂點：
a b c d
4條弧(邊):
a→c a→b
b→d
c→d
a b c d 為一個拓撲序列。
請按任意鍵繼續. . .
*/
❼ 有向無環圖
6-5-2-3-4
6-2-3-5-4
6-2-5-3-4
2-6-3-5-4
2-6-5-3-4
有5個拓撲序列
選C
補充問題:(r+2) mod m = f
mod 就是取余
給你參考,不太清楚少用一個空間是不是在隊尾最後再少用一個.因為循環隊列一般最後一個空間就不用的,就是(r+1) mod m = f,不然隊空可,隊滿難以判斷的,r=f都有可能表示是空或滿,本來就少用一個空間.題目里又強調了少用一個空間,故認為是少用兩個空間了.
❽ 有向無環圖的判定及拓撲排序
五分您打發誰呢？數據結構要好好學啊
❾ 一個含有n個頂點的連通且無環無向圖在其鄰接矩陣存儲結構共有多少個零元素
原則上的確是n的平方，不過由於無向圖的鄰接矩陣是一個對稱矩陣，只需要存儲下三角或者上三角的元素，個數就是從1加到n，就是n（n+1）/ 2，不過題目問錯了，這是壓縮存儲，是用一維數組存放，一般好像不叫矩陣
其實更精確地說，上面的數字個數是普通對稱矩陣的，這個鄰接矩陣的對角線一定為0，所以，只需要存儲1 加到n-1，也就是n(n-1)/2就可以了
❿ 有n個頂點一條邊的無像圖採用連接表存儲時有個表頭節點有個列表節點
無向圖就是不分方向的圖 連接表的橫列有N項,縱列也是N項 形成的N*N項每項都被稱為邊結點 每項都有縱橫兩個坐標,例如點（N,N-1）,表示的就是從第N點向第N-1點有無路徑. 由於有E條邊,自然有E條路徑,但是由於無向,=雙向,所以要乘以二