数据结构课程设计拓排序

① 数据结构课程设计 排序

要代码我可以给你写 其它的就要你自己写了

② 数据结构的课程设计-拓扑排序的算法

#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);
}