数据结构实验报告
- 格式：docx
- 大小：156.16 KB
- 文档页数：11
实验五 #include #include #include #define OK 1; #define MAX_VERTEX_NUM 40 #define MAXQSIZE 100 typedef int QElemType; typedef int VertexType; typedef int InfoType; typedef struct ArcNode{ int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 }ArcNode; typedef struct VNode{ VertexType data; // 顶点信息 ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM]; // 头结点 typedef struct{ AdjList vertices; int vexnum,arcnum; // 图的当前顶点数和弧数 int kind; // 图的种类标志 }ALGraph; int CreateGraph(ALGraph &G) {// 采用数组(邻接矩阵)表示法,构造有向图G int i,k,j,v1,v2; printf("输入顶点数目:"); scanf("%d",&G.vexnum); printf("输入弧的数目:"); scanf("%d",&G.arcnum); for(i=0;i{ G.vertices[i].data=i; G.vertices[i].firstarc=NULL; // 没有相关信息 }
printf("输入弧的始点i和终点j\n"); for(k=0;kprintf("输入第%d条弧的始点i:",k+1); scanf("%d",&v1); printf("输入第%d条弧的终点j:",k+1); scanf("%d",&v2); i=v1;j=v2; while(i<1||i>G.vexnum||j<1||j>G.vexnum){ printf("输入第%d条弧的始点i:",k+1); scanf("%d",&v1); printf("输入第%d条弧的终点j:",k+1); scanf("%d",&v2); i=v1;j=v2; } i--; j--; printf("%d%d\n",v1,v2); ArcNode *p; p=new ArcNode; if(!p){ printf("空间不足!\n"); return(0); } p->adjvex=j; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; } printf("有向图建立成功！\n\n"); return OK; } void DFS(ALGraph G,int v,int *visited) { int w; visited[v]=1; printf("%d->",v+1); for(w=G.vertices[v].data; G.vertices[v].firstarc!=NULL; w=G.vertices[v].firstarc->adjvex,G.vertices[v].firstarc=G.vertices[v].firstarc->nextarc) if(visited[w]==0) DFS(G,w,visited); } void DFSGraph(ALGraph G) { int v; int visited[MAX_VERTEX_NUM]; for(v=0;vvisited[v]=0; for(v=0;vif(visited[v]==0) DFS(G,v,visited); printf("\n"); } typedef struct SqQueue { QElemType *base; int front; int rear; }SqQueue; int InitQueue(SqQueue &Q) { Q.base=new QElemType; if(!Q.base) { printf("error"); return 0; } Q.front=Q.rear=0; return OK; } int EnQueue(SqQueue &Q,QElemType e) { if((Q.rear+1)%MAXQSIZE==Q.front) { printf("error"); return 0; } Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; } int QueueEmpty(SqQueue Q) { if(Q.front==Q.rear) { return OK;}
else return 0;
} int DeQueue(SqQueue &Q,QElemType &e) { if(Q.front==Q.rear) { printf("error"); return 0; } e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return e; } void BFSGrahp(ALGraph G) { int v,w,u; int visited[MAX_VERTEX_NUM]; SqQueue Q; for(v=0;vvisited[v]=0; InitQueue(Q); for(v=0;vif(visited[v]==0) { visited[v]=1; printf("%d->",v+1); EnQueue(Q,v); while(!QueueEmpty(Q)) { DeQueue(Q,u); for(w=G.vertices[u].data; G.vertices[u].firstarc!=NULL;w=G.vertices[u].firstarc->adjvex,G.vertices[u].firstarc=G.vertices[u].firstarc->nextarc) if(visited[w]==0) { visited[w]=1; printf("%d->",w+1); EnQueue(Q,w); } if(visited[w]==0) { visited[w]=1; printf("%d->",w+1); EnQueue(Q,w); } } } } void main() { ALGraph G; CreateGraph(G); printf("\n深度优先遍历的结果:\n"); DFSGraph(G); printf("\n广度优先遍历的结果:\n"); BFSGrahp(G); printf("\n"); }
实验六 #include #include #include #include typedef int InfoType; #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b)) #define MAXSIZE 20 typedef int KeyType; struct RedType { KeyType key; InfoType otherinfo; };
struct SqList { RedType r[MAXSIZE+1]; int length; }; void InsertSort(SqList &L) { int i,j; for(i=2;i<=L.length;++i) if LT(L.r[i].key,L.r[i-1].key) { L.r[0]=L.r[i]; for(j=i-1;LT(L.r[0].key,L.r[j].key);--j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; } }
int Partition(SqList &L,int low,int high) { RedType t; KeyType pivotkey; pivotkey=L.r[low].key; while(low{ while(low=pivotkey) --high; t=L.r[low]; L.r[low]=L.r[high]; L.r[high]=t; while(low++low; t=L.r[low]; L.r[low]=L.r[high]; L.r[high]=t; } return low; } void QSort(SqList &L,int low,int high) { int pivotloc;
