數據演算法與拓撲

A. 數據結構拓撲排序序列

拓撲排序序列有6種。先找到第一個沒有被指的，就是C1，加入序列。然後擦掉跟C1有關的邊，此時C2和C3都滿足沒有被指，選一個，比如選C2，加入序列，擦掉和C2有關的邊，這個時候可以選C3,C4,C5或C6，如此而已。

B. 拓撲排序

1、堆棧

棧是一種特殊的線性表，插入或刪除棧元素的運算只能在表的一端進行，稱運算的一端為棧頂，另一端稱為棧底。隊列也是一種特殊的線性表（基本操作都是線性操作的子集）。

特點：後進先出

棧又稱為「後進先出」的線性表，簡稱LIFO表。

棧的鏈式實現是以鏈表作為棧的存儲結構，並在這種存儲結構上實現棧的基本運算。棧的鏈式實現稱為鏈棧。

2、有向無環圖

描述含有公共子式的表達式的有效工具；

描述一項工程或系統的進行過程的有效工具。

3、一些概念

通常我們把計劃、施工過程、生產流程、程序流程等都當成一個工程，一個大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動。這些活動完成時，整個工程也就完成了。

我們用一種有向圖來表示這些工程、計劃等，在這種有向圖中，頂點表示活動，有向邊表示活動的優先關系，這種用頂點表示活動，用弧來表示活動間的優先關系的有向圖叫做頂點表示活動的網路(ActireOnVertices)簡稱為AOV網。

拓撲排序：

假設G=(V，E)是一個具有n個頂點的有向圖，V中頂點序列vl，v2，…，vn稱做一個拓撲序列(TopologicalOrder)，當且僅當該頂點序列滿足下列條件：若在有向圖G中存在從頂點vi到vj的一條路徑，則在頂點序列中頂點vi必須排在頂點vj之前。通常，在AOV網中，將所有活動排列成一個拓撲序列的過程叫做拓撲排序掘虧(TopologicalSort)。

在AOV網中不應該出現有向環。因為環的存在意味著某項活動將以自己為先決條件，顯然無法形成拓撲序列。

判定網中是否存在環的方法：對有向圖構造其頂點的拓撲有序序列，若網中所有頂點都出現在它的拓撲有序序列中，則該AOV網中一定不存在環。

4、拓撲排序的演算法思想

輸入AOV網路。令n為頂點個數。

（1）在AOV網路中選一個沒有直接前驅的頂點，並輸出之；

（2）從圖中刪去該頂點,同時刪去所有它發出的有向邊；

重復以上步驟，直到全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或圖中還有未輸出的頂點，但已跳出處理循環。這說明圖中還剩下一些頂點，它們都有直接前驅，再也找不到沒有前驅的頂點了。這時AOV網路中必定存在有向環。

5、拓撲排序演算法的C語言描述

在實現拓撲排序的演算法中，採用鄰接表作為有向圖的存儲結構，每個頂點設置一個單鏈表，每個單鏈表有一個表頭結點，在表頭結點中增加一個存放頂點入度的域count，這些表頭結點構成一個數組。

為了避免重復檢測入度為0的點，另設一棧存放所有入度為0的點。

對於有n個頂點和e條邊的有向圖而言，for循環中建立入度為0的頂點棧時間為O（n）；若在拓撲排序過程中不出現有向環，則判擾神每個頂點出棧、入棧和入度減1的操作在while循環語句中均執行e次，因此拓撲排序總的時間花費為O(n+e)。

6、拓撲排序演算法的C語言實現

#include"stdio.h"

#defineMAX_VERTEX_NUM20

#include"conio.h"

#include"stdlib.h"

#defineSTACK_INIT_SIZE16

#defineSTACKINCREMENT5

typedef intSElemType;

typedefcharVertexType;

typedefstruct

{

SElemType*base;

SElemType*top;

intstacksize;

}SqStack;

//我們依然用鄰接表來作圖的存儲結構

typedefstructArcNode{

intadjvex;

struct李歷ArcNode*nextarc;

intinfo;

}ArcNode; //表結點類型

typedefstructVNode{

VertexTypedata;

intcount;

ArcNode*firstarc;

}VNode,AdjList[MAX_VERTEX_NUM];//頭結點

typedefstruct{

AdjListvertices; //鄰接表

intvexnum,arcnum;

}ALGraph;

intInitStack(SqStack&S)

{

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)exit(-1);

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return1;

}//InitStack

intPush(SqStack&S,SElemTypee)

{

if((S.top-S.base)>=S.stacksize)

{

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!S.base)exit(-1);

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}//if

*(S.top)=e;

S.top++;

return1;

}//Push

intPop(SqStack&S,SElemType&e)

{

if(S.top==S.base)return0;

--S.top;

e=*S.top;

return1;

}//Pop

intStackEmpty(SqStack&S)

{

if(S.top==S.base)return1;

elsereturn0;

}//StackEmpty

intLocateVex(ALGraphG,charu)

{

inti;

for(i=0;i<G.vexnum;i++)

{if(u==G.vertices[i].data)returni;}

if(i==G.vexnum){printf("Erroru! ");exit(1);}

return0;

}

voidCreateALGraph_adjlist(ALGraph&G)

{

inti,j,k,w;

charv1,v2,enter;

ArcNode*p;

printf("Inputvexnum&arcnum: ");

scanf("%d",&G.vexnum);

scanf("%d",&G.arcnum);

printf("InputVertices(以回車隔開各個數據): ");

for(i=0;i<G.vexnum;i++)

{ scanf("%c%c",&enter,&G.vertices[i].data);//注意點，解說

G.vertices[i].firstarc=NULL;

}//for

printf("InputArcs(v1,v2,w)以回車分開各個數據: ");

for(k=0;k<G.arcnum;k++)

{

scanf("%c%c",&enter,&v1);

scanf("%c%c",&enter,&v2);

//scanf("%d",&w);

i=LocateVex(G,v1);

j=LocateVex(G,v2);

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j;

//p->info=w;

p->nextarc=G.vertices[i].firstarc;//前插法,即每次都插入到頭結點的後面

G.vertices[i].firstarc=p;

printf("Next ");

}//for

return;

}//CreateALGraph_adjlist

voidFindInDegree(ALGraph&G)

{

inti,j;

for(i=0;i<G.vexnum;i++)

{

G.vertices[i].count=0;

}//for

for(j=0;j<G.vexnum;j++)

{

//G.vertices[i].count++;

for(ArcNode*p=G.vertices[j].firstarc;p;p=p->nextarc)

G.vertices[p->adjvex].count++;

}//for

}//FindInDegree

intTopoSort(ALGraph&G)

{

SqStackS;

FindInDegree(G);

InitStack(S);

for(inti=0;i<G.vexnum;i++)

if(G.vertices[i].count==0)Push(S,i);

intcountt=0;

while(!StackEmpty(S))

{

inti,m;

m=Pop(S,i);

printf("%c",G.vertices[i].data);++countt;

for(ArcNode*p=G.vertices[i].firstarc;p;p=p->nextarc)

{ intk;

k=p->adjvex;

if(!(--G.vertices[k].count))Push(S,k);

}//for

}//while

if(countt<G.vexnum)return0;

elsereturn1;

}//TopoSort

intmain()

{

ALGraphG;

CreateALGraph_adjlist(G);

TopoSort(G);

return1;

}

7、malloc函數和realloc函數

realloc:void*realloc(void*block,size_tsize)，將block所指存儲塊調整為大小size，返回新塊的地址。如能滿足要求，新塊的內容與原塊一致；不能滿足要求時返回NULL，此時原塊不變。

C. 數據結構與演算法分析

本文出自：

www點54manong點com

請尊重原創，轉載請註明出處，謝謝！

什麼是數據結構，為什麼要學習數據結構？數據結構是否是一門純數學課程？它在專業課程體系中起什麼樣的作用？我們要怎麼才能學好數據結構？… 相信同學們在剛開始《數據結構》這門課的學習時，心裡有著類似前面幾個問題的這樣那樣的疑問。希望下面的內容能幫助大家消除疑惑，下定決心堅持學好這門課：

1 學習數據數據結構的意義

數據結構是計算機科學與技術專業、計算機信息管理與應用專業，電子商務等專業的基礎課，是十分重要的核心課程。所有的計算機系統軟體和應用軟體都要用到各種類型的數據結構。因此，要想更好地運用計算機來解決實際問題，僅掌握幾種計算機程序設計語言是難以應付當前眾多復雜的課題。要想有效地使用計算機、充分發揮計算機的性能，還必須學習和掌握好數據結構的有關知識。打好「數據結構」這門課程的扎實基礎，對於學習計算機專業的其他課程，如操作系統、資料庫管理系統、軟體工程、編譯原理、人工智慧、圖視學等都是十分有益的。

2 為什麼要學習數據結構

在計算機發展的初期，人們使用計算機的目的主要是處理數值計算問題。當我們使用計算機來解決一個具體問題時，一般需要經過下列幾個步驟：首先要從該具體問題抽象出一個適當的數學模型，然後設計或選擇一個解此數學模型的演算法，最後編出程序進行調試、測試，直至得到最終的解答。例如，求解梁架結構中應力的數學模型的線性方程組，可以使用迭代演算法來求解。

由於當時所涉及的運算對象是簡單的整型、實型或布爾類型數據，所以程序設計者的主要精力是集中於程序設計的技巧上，而無須重視數據結構。隨著計算機應用領域的擴大和軟、硬體的發展，非數值計算問題越來越顯得重要。據統計，當今處理非數值計算性問題佔用了85%以上的機器時間。這類問題涉及到的數據結構更為復雜，數據元素之間的相互關系一般無法用數學方程式加以描述。因此，解決這類問題的關鍵不再是數學分析和計算方法，而是要設計出合適的數據結構，才能有效地解決問題。下面所列舉的就是屬於這一類的具體問題。

例1：圖書館信息檢索系統。當我們根據書名查找某本書有關情況的時候；或者根據作者或某個出版社查找有關書籍的時候，或根據書刊號查找作者和出版社等有關情況的時候，只要我們建立了相關的數據結構，按照某種演算法編寫了相關程序，就可以實現計算機自動檢索。由此，可以在圖書館信息檢索系統中建立一張按書刊號順序排列的圖書信息表和分別按作者、書名、出版社順序排列的索引表，如圖1.1所示。由這四張表構成的文件便是圖書信息檢索的數學模型，計算機的主要操作便是按照某個特定要求（如給定書名）對圖書館藏書信息文件進行查詢。

諸如此類的還有學生信息查詢系統、商場商品管理系統、倉庫物資管理系統等。在這類文檔管理的數學模型中，計算機處理的對象之間通常存在著的是一種簡單的線性關系，這類數學模型可稱為線性的數據結構。

例2：八皇後問題。在八皇後問題中，處理過程不是根據某種確定的計演算法則，而是利用試探和回溯的探索技術求解。為了求得合理布局，在計算機中要存儲布局的當前狀態。從最初的布局狀態開始，一步步地進行試探，每試探一步形成一個新的狀態，整個試探過程形成了一棵隱含的狀態樹。如圖1.2所示（為了描述方便，將八皇後問題簡化為四皇後問題）。回溯法求解過程實質上就是一個遍歷狀態樹的過程。在這個問題中所出現的樹也是一種數據結構，它可以應用在許多非數值計算的問題中。

例3：教學計劃編排問題。一個教學計劃包含許多課程，在教學計劃包含的許多課程之間，有些必須按規定的先後次序進行，有些則沒有次序要求。即有些課程之間有先修和後續的關系，有些課程可以任意安排次序。這種各個課程之間的次序關系可用一個稱作圖的數據結構來表示，如圖1.3所示。有向圖中的每個頂點表示一門課程，如果從頂點vi到vj之間存在有向邊<vi，vj>，則表示課程i必須先於課程j進行。由以上三個例子可見，描述這類非數值計算問題的數學模型不再是數學方程，而是諸如線性表、樹、圖之類的數據結構。因此，可以說數據結構課程主要是研究非數值計算的程序設計問題中所出現的計算機操作對象以及它們之間的關系和操作的學科。

學習數據結構的目的是為了了解計算機處理對象的特性，將實際問題中所涉及的處理對象在計算機中表示出來並對它們進行處理。與此同時，通過演算法訓練來提高學生的思維能力，通過程序設計的技能訓練來促進學生的綜合應用能力和專業素質的提高。

3數據結構課程的內容

數據結構與數學、計算機硬體和軟體有十分密切的關系，它是介於數學、計算機硬體和計算機軟體之間的一門計算機專業的核心課程，是高級程序設計語言、操作系統、編譯原理、資料庫、人工智慧、圖視學等課程的基礎。同時，數據結構技術也廣泛應用於信息科學、系統工程、應用數學以及各種工程技術領域。

數據結構課程重在討論軟體開發過程中的方案設計階段、同時設計編碼和分析階段的若干基本問題。此外，為了構造出好的數據結構及其實現，還需考慮數據結構及其實現的評價與選擇。因此，數據結構的內容包括三個層次的五個「要素」，如圖1.3所示。

數據結構的核心技術是分解與抽象。通過分解可以劃分出數據的三個層次；再通過抽象，舍棄數據元素的具體內容，就得到邏輯結構。類似地，通過分解將處理要求劃分成各種功能，再通過抽象舍棄實現細節，就得到運算的定義。上述兩個方面的結合使我們將問題變換為數據結構。這是一個從具體（即具體問題）到抽象（即數據結構）的過程。然後，通過增加對實現細節的考慮進一步得到存儲結構和實現運算，從而完成設計任務。這是一個從抽象（即數據結構）到具體（即具體實現）的過程。熟練地掌握這兩個過程是數據結構課程在專業技能培養方面的基本目標。

結束語：數據結構作為一門獨立的課程在國外是從1968年才開始的，但在此之前其有關內容已散見於編譯原理及操作系統之中。20世紀60年代中期，美國的一些大學開始設立有關課程，但當時的課程名稱並不叫數據結構。1968年美國唐.歐.克努特教授開創了數據結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本演算法》是第一本較系統地闡述數據的邏輯結構和存儲結構及其操作的著作。從20世紀60年代末到70年代初，出現了大型程序，軟體也相對獨立，結構程序設計成為程序設計方法學的主要內容，人們越來越重視數據結構。從70年代中期到80年代，各種版本的數據結構著作相繼出現。目前，數據結構的發展並未終結，一方面，面向各專門領域中特殊問題的數據結構得到研究和發展，如多維圖形數據結構等；另一方面，從抽象數據類型和面向對象的觀點來討論數據結構已成為一種新的趨勢，越來越被人們所重視。

D. 數據結構拓撲排序序列

對一個有向無環圖簡稱G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊<u，v>∈E(G)，則u在線性序列中出現在v之前。通叢友常，這樣的線性序列稱為滿足拓撲次序的序列，簡稱野友拓撲序列。

由拓撲序列的生成方法的出圖中三種不同拓撲排序的序列：第一種：c1、c2、c4、c3、c5、c6，第二種：c1、c2、c4、c3、c6、c5，第三種：c1、c3、c2、c4、c5、c6。

循環結束後，若輸出的頂點數小於網中的頂點數，則輸出「有迴路」信息，否則輸出的頂點序列就是一種拓撲序列。

參考資料來源：網路-拓撲排序

E. 什麼是拓撲關系怎樣理解拓撲關系也是一種數據，拓撲關系對空間資料庫建設有何幫助

英文
topology
的音譯.
拓撲學就是以空間幾何的形式來表現事物內部的結構,原理,工作狀況等.
比如你的計算機吧,學過搜索演算法吧(廣度優先(breath-first)和深度優先(depth-first,
不知道中文譯的對不對)演算法).你在分析的時候不是把所有的狀態畫敗前成一個樹狀表,然後來看一步步怎御枯薯樣查找的么.這就是運用拓撲邏輯的方法.
當然,從這里你就可以看到,拓撲都在處理離散的狀態.
說白了,系統邏輯流程圖也是拓撲圖.
聽起鎮者很深奧,很玄,其實常常用到

F. 數據結構中有關拓撲排序的相關知識

將入度為0的結點入隊，刪除後同時將所有相鄰頂點的先決條件減一。當某個頂點的計數為0時，將它入隊。這是關鍵思想。

G. 演算法與數據結構，C語言版本的拓撲排序問題求助。

如果可以,你能把程序寫上來.我可以給你講.

H. 數據結構中 關於圖拓撲排序演算法 有個地方不太明白 希望能得到解答

我知道你哪裡不明白了，你沒看見上面的for循環，1，如果不為0，則不執行if了，但執行for循環。2，執行for循環的目的就是把所有的入度減1，減為0的入棧。

I. 數據結構課設 題目：拓撲排序演算法

//首先是用鄰接表表視圖,下面是鄰接表的數據結構定義
const int MaxVertexNum = {圖的最大頂點數，要大於等於具體圖的頂點數n};
const int MaxEdgetNum = {圖的最大邊數，要大於等於具體圖的邊數e};

typedef VertexType vexlist[MaxVertexNum]; //定義vexlist為存儲頂點信息的數組類型

struct edgenode //定義鄰接表中的邊結點類型
{
int adjvex; //鄰接點域
int weight; //權值域
edgenode* next;//指向下一個邊結點的鏈域
};

typedef edgenode* adjlist[MaxVertexNum]; //定義adjlist為存儲n個表頭指針的數組類型

//通過從鍵盤上輸入的n個頂點信息和e條有向邊信息建立頂點數組GV和鄰接表GL
void Create2(vexlist GV, adjlist GL, int n, int e)
{
int i,j,k;
//建立頂點數組
cout<<"輸入"<<n<<"個頂點的值："<<endl;
four(i = 0; i<n; i++)
cin>>GV[i];
//初始化鄰接表
for(i=0; i<n; i++)
GL[i] = NULL;
//建立鄰接表
cout<<"輸入"<<e<<"條邊："<<endl;
for(k=1; k<=e; k++)
{
//輸入一條邊<i,j>
cin>>i>>j;
//分配新結點
edgenode* p = new edgenode;
//將j值賦給新結點的鄰接點域
p->adjvex = j;
//將新結點插入到鄰接表表頭
p->next = GL[i];
GL[i] = p;
}
}

//對鄰接表GL表示的有n個頂點的有向圖拓撲排序
void TopoSort(adjlist GL, int n)
{
int i,j,k,top,m=0; //m統計拓撲排序中的頂點數
edgenode* p;
//定義存儲圖中每個頂點入度的一維整型數組d
int* d = new int[n];
//初始化數組d中每個元素值為0
for(i=0; i<n; i++)
d[i] = 0;
//利用數組d記錄每個頂點的入度
for(i = 0; i < n; i++)
{
p = GL[i];
while(p != NULL)
{
j = p->adjvex;
d[j]++;
p = p->next;
}
}
//初始化用於鏈接入度為0的棧頂指針top為-1
top = -1;
//建立初始棧
for(i = 0; i < n; i++)
if(d[i] == 0)
{
d[i] = top;
top = i;
}
//每循環一次刪除一個頂點及所有出邊
while(top != -1)
{
j = top; //j的值為一個入度為0的頂點序號
top = d[top]; //刪除棧頂元素
cout<<j<<' '; //輸出一個入度為0的頂點
m++; //輸出頂點個數加1
p = GL[j]; //p指向鄰接點表的第一個結點
while(p != NULL)
{
k = p->adjvex;
d[k]--;
if( d[k] == 0) //把入度為0的元素進棧
{
d[k] = top;
top = k;
}
p = p->next;
}
}
cout<<endl;
if(m<n)
cout<<"存在迴路！"<<endl;
delete []d;
}

J. 在拓撲排列演算法中,要用到那些基本的數據結構

拓撲排序嗎，這是圖論裡面的一個基礎的演算法，具體說要用到什知賣么數據結構，我會告訴你沒有嗎？

如果硬要說的話，可能包括圖的存儲，也就是鄰接矩陣或者鄰接表搭型逗。

然後實現拓撲排序有兩種方法：

1. 不斷找到租旅入度為0的點，然後輸出。

2. 深搜。

如果你感興趣的話，我可以幫上述兩種方法的代碼都給你。