數據結構課程設計拓排序

① 數據結構課程設計 排序

要代碼我可以給你寫 其它的就要你自己寫了

② 數據結構的課程設計-拓撲排序的演算法

#include<stdio.h>
int mat[105][105];/*存圖的邊*/
int indeg[105];/*存入度*/
int ans[105];/*結果*/
int top =0;
void main()
{
int n;/*圖大小*/
int m;/*邊個數*/
int i,j;
int a,b;
scanf("%d%d",&n,&m);
for(i=0;i<n;++i)indeg[i]=0;
for(i=0;i<m;++i)
{
scanf("%d%d",&a,&b);
/*a到b有一條專邊,輸入范屬圍[0,n-1]*/
indeg[b]++;
mat[a][b]=1;
}
while(top<n)
{
for(i=0;i<n;++i)
if(indeg[i]==0)
{
indeg[i]=-1;
break;
}
j=i;
ans[top++]=j;
for(i=0;i<n;++i)
if(mat[j][i])
mat[j][i]=0,--indeg[i];
}
for(i=0;i<top;++i)
printf("%d ",ans[i]);
puts("");
}

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

//首先是用鄰接表表視圖,下面是鄰接表的數據結構定義
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;
}

④ 數據結構課程設計教學計劃安排檢驗程序（拓撲排序）

難得碰到個稍微有點意思的問題，雖然沒分，也答了吧

輸入格式：
第一行，兩個整數n和m，分別表示課程數和學期數
然後緊接著n行，每行一個字元串，表示各個課程的名稱
然後一個整數k，表示共有k對課程之間有先後關系
然後k行，每行兩個字元串s1和s2，表示課程s1必須在課程s2之前學

#include <stdio.h>
#include <memory.h>
#include <string.h>
#define MAXN 25
int n,m;
int indeg[MAXN],outdeg[MAXN];
int list[MAXN][MAXN];
char names[MAXN][15];
int stack[MAXN];
int dep;
int order[MAXN];

int find_id(char *name)
{
int i;
for (i=0;i<n;i++)
if (!strcmp(name,names[i])) return i;
return -1;
}

int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
for (i=0;i<n;i++) scanf("%s",names[i]);
memset(indeg,0,sizeof(indeg));
memset(outdeg,0,sizeof(outdeg));
scanf("%d",&k);
while (k--)
{
char name[15];
scanf("%s",name);
i=find_id(name);
scanf("%s",name);
j=find_id(name);
if (i==-1 || j==-1)
{
puts("Invalid name, please enter again");
k++;
}
else
{
indeg[j]++;
list[i][outdeg[i]++]=j;
}
}
k=0;
dep=0;
for (i=0;i<n;i++)
if (indeg[i]==0) stack[dep++]=i;
while (dep>0)
{
dep--;
i=stack[dep];
order[k++]=i;
while (outdeg[i]>0)
{
j=list[i][--outdeg[i]];
indeg[j]--;
if (indeg[j]==0) stack[dep++]=j;
}
}
if (k<n) puts("No Solution!");
else
{
int d,r;
d=n/m;
r=n%m;
k=0;
for (i=0;i<m;i++)
{
printf("Course(s) in term %d:\n",i+1);
for (j=0;j<d+(i<r ? 1 : 0);j++)
{
puts(names[k]);
k++;
}
putchar('\n');
}
}
}

⑤ 數據結構課程設計的各種排序演算法的綜合比較 哪位大神幫寫一下~

排序法 平均時間 最差情形 穩定度 額外空間 備注
冒泡 O(n2) O(n2) 穩定 O(1) n小時較好
交換 O(n2) O(n2) 不穩定 O(1) n小時較好
選擇 O(n2) O(n2) 不穩定 O(1) n小時較好
插入 O(n2) O(n2) 穩定 O(1) 大部分已排序時較好
基數 O(logRB) O(logRB) 穩定 O(n) B是真數(0-9)，R是基數(個十百)
Shell O(nlogn) O(ns) 1<s<2 不穩定 O(1) s是所選分組
快速 O(nlogn) O(n2) 不穩定 O(nlogn) n大時較好
歸並 O(nlogn) O(nlogn) 穩定 O(1) n大時較好
堆 O(nlogn) O(nlogn) 不穩定 O(1) n大時較好

⑥ 課程設計 實現拓撲排序演算法

#include<stdio.h>
#include<stdlib.h>
#define MAX_VEXTEX_NUM 20
#define M 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VEXTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
typedef struct //構件棧
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
void InitStack(SqStack *); //函數聲明
int Pop(SqStack *, ElemType *);
void Push(SqStack *,ElemType );
int StackEmpty(SqStack *);
void CreatGraph(ALGraph *);
void FindInDegree(ALGraph , int * );
void TopologicalSort(ALGraph );
void InitStack(SqStack *S)//初始化棧
{
S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
int Pop(SqStack *S,ElemType *e)//出棧操作
{
if(S->top==S->base)
{return ERROR;}
*e=*--S->top;
//printf("%d\n",e);
// return e;
return 0;
}
void Push(SqStack *S,ElemType e)//進棧操作
{if(S->top-S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top = S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}*S->top++=e;
}
int StackEmpty(SqStack *S)//判斷棧是否為空
{
if(S->top==S->base)
return OK;
else
return ERROR;}
void CreatGraph(ALGraph *G)//構件圖
{int m, n, i;
ArcNode *p;
printf("請輸入頂點數和邊數:");
scanf("%d%d",&G->vexnum,&G->arcnum);
for (i = 1; i <= G->vexnum; i++)
{G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
}
for (i = 1; i <= G->arcnum; i++) //輸入存在邊的點集合
{
printf("\n請輸入存在邊的兩個頂點的序號:");
scanf("%d%d",&n,&m);
while (n < 0 || n > G->vexnum || m < 0 || m > G->vexnum)
{printf("輸入的頂點序號不正確 請重新輸入:");
scanf("%d%d",&n,&m);
}
p = (ArcNode*)malloc(sizeof(ArcNode));
if (p == NULL)
{printf("memory allocation failed,goodbey");
exit(1);
}
p->adjvex = m;
p->nextarc = G->vertices[n].firstarc;
G->vertices[n].firstarc = p;
}
printf("建立的鄰接表為:\n"); //輸出建立好的鄰接表
for(i = 1; i <= G->vexnum; i++)
{
printf("%d",G->vertices[i].data);
for(p = G->vertices[i].firstarc; p; p = p->nextarc)
printf("%3d",p->adjvex);
printf("\n");
}}
void FindInDegree(ALGraph G, int indegree[])//求入度操作
{
int i;
for (i = 1; i <= G.vexnum; i++)
{
indegree[i] = 0;
}
for (i = 1; i <= G.vexnum; i++)
{while (G.vertices[i].firstarc)
{indegree[G.vertices[i].firstarc->adjvex]++;
G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
}
}
}
void TopologicalSort(ALGraph G) //進行拓撲排序
{
int indegree[M];
int i, k, n;
int count = 0;
ArcNode *p;
SqStack S;
FindInDegree(G, indegree);
InitStack(&S);
for (i = 1; i <= G.vexnum; i++)
{
printf("第%d個點的入度為%d \n", i, indegree[i]);
}
printf("\n");
for ( i = 1; i <= G.vexnum; i++)
{
if (!indegree[i])
Push(&S,i);
}
printf("進行拓撲排序輸出順序為:"); //輸出結果
while(!StackEmpty(&S))
{
Pop(&S,&n);
printf("%4d",G.vertices[n].data);
count++;
for (p = G.vertices[n].firstarc; p != NULL; p = p->nextarc)
{
k = p->adjvex;
if (!(--indegree[k]))
{
Push(&S,k);
}
}

}printf("\n");

if (count < G.vexnum)
{
printf("出現錯誤\n");
}
else
{
printf("排序成功\n");
}
}
int main(void) //主函數
{
ALGraph G;
CreatGraph(&G);
TopologicalSort(G);
system("pause");
return 0;
}

⑦ 求 數據結構 拓撲排序的代碼詳解

按照你的要求下的程序，自己也復習了一遍，這學期我們也學數據結構，有問題可以繼續問哦
#define MAX 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int ElemType;
typedef struct biaoNode
{
int xiabiao;//數據域
struct biaoNode *nextbiao;//指針域
}biaoNode;//表結點的定義

typedef struct touNode //頭結點
{
int data;//數據域
int indegree;//度數
biaoNode *firstarc;//指針
}touNode,AdjList[MAX];//AdjList[MAX]鄰接表存儲方式

typedef struct
{
AdjList shuzu;//數組鄰接表
int dingdianshu,bianshu;//dingdianshu定點數，bianshu邊數
}tu;//圖的定義

typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;//棧，這個你應該很熟悉了~
void creattu(tu *G)//此函數創建圖
{
int m, n, i;
biaoNode *p;//表結點指針
printf("input dingdianshu and bianshu:");
scanf("%d%d",&G->dingdianshu,&G->bianshu);//輸入節點數和邊數
for (i = 1; i <= G->dingdianshu; i++)//for循環是初始化一個圖，數據域為i，度數為0，第一個相鄰的弧為空
{
G->shuzu[i].data = i;
G->shuzu[i].indegree=0;
G->shuzu[i].firstarc = 0;
}
for (i = 1; i <= G->bianshu; i++)
{

scanf("%d%d",&n,&m);//輸入一個從n到m的弧，注意是有向的，順序不能相反
while (n < 0 || n > G->dingdianshu || m < 0 || m > G->dingdianshu)//若下標或者第一個相鄰的點不符合要求澤輸出錯誤，要求重新輸入
{
printf("input error:");
scanf("%d%d",&n,&m);
}
p = (biaoNode*)malloc(sizeof(biaoNode));//分配一個節點用來存儲剛才下標為m信息
if (p == 0)//沒有分配成功，則輸出錯誤
{
printf("error");
exit(0);
}
p->xiabiao = m;//p下標m
p->nextbiao = G->shuzu[n].firstarc;//p的nextbiao指針指向n
G->shuzu[n].firstarc = p;//同理n的第一個鄰接點是m也就是p（剛剛賦值了嘛）
G->shuzu[m].indegree++;//m的入度+1，因為相鄰n嘛，因為是有向圖，
}
printf("outpu G:\n");

for(i = 1; i <= G->dingdianshu; i++)//輸出各節點的信息，包括數據和度數，和與它相鄰的點的下標
{
printf("%2d",G->shuzu[i].data);
printf("%7d",G->shuzu[i].indegree);
for(p = G->shuzu[i].firstarc; p; p = p->nextbiao)
{
printf("%7d",p->xiabiao);
}
printf("\n");
}
}

int Pop(SqStack *S)//從棧中彈出，這個你也很熟悉吧，數據結構課本上可是有哦
{
int e;
if(S->top==S->base)
{
printf("zhan kong\n");
}
S->top=S->top-1;
e=*S->top;
printf("%3d",e);
return(e);
}
void Push(SqStack *S,ElemType e)//入棧
{
if(S->top-S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S->base)
{
printf("zhan fen pei shi \n");
exit(0);
}
S->top = S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top=e;
S->top++;
}
int StackEmpty(SqStack *S)//棧置空
{
if(S->top==S->base)
return 1;
else
return 0;
}
void InitStack(SqStack *S)//初始化棧
{
S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S->base)
{
printf("zhan chu shi hua shi \n");
exit(0);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
void paixu(tu G)//排序，這個可是重點哦，其思想是1）在有向圖中查找一個沒有後繼（或前驅）的頂點並添加到頂點表中。（2）從圖中刪除該頂點和所有以該頂點為頭（尾）的弧。重復上述兩步，當圖為空時，頂點表將以拓撲次序出現。

{
int count=0;
int i;
biaoNode *p;
SqStack S;
InitStack(&S);
for(i=1;i<=G.dingdianshu;i++)//找出入度為0的節點，入棧
{
if(G.shuzu[i].indegree==0)
Push(&S,i);
}
printf("G input:");
while(!StackEmpty(&S))//如果棧不空，也就是有入度為0的節點
{
i=Pop(&S);//彈出
count++;//計數器+1
for(p=G.shuzu[i].firstarc;p!=0;p=p->nextbiao)//與i相鄰的節點度數減1
{
G.shuzu[p->xiabiao].indegree--;
if(G.shuzu[p->xiabiao].indegree==0)
Push(&S,p->xiabiao);//如果減1後，其入度為0，則入棧
}
}
printf("\n");
if(count!=G.dingdianshu)//如果呢，整個一個大排序下來我們技術器的度數不是這個圖的節點數，那麼，就是出現錯誤了，否則排序成功。
printf("chu xian cuo wu\n");
else
printf("pai xu cheng gong\n");
}
main()//main函數條例很清晰，我就不廢話啦~
{
tu G;
creattu(&G);
paixu(G);
}