① c語言循環結構輸出純數字圖形
#include<math.h>
#include<stdio.h>
int main()
{
int i,j,k,l;
for(i=0;i<7;i++)
{
for(j=i;j>=-i;j--)
{
printf("%d",abs(j));
}
for(k=1;k<14-2*i-1;k++)
printf("%c",'8');
printf("\n");
}
}
② C語言用選擇結構流程圖判斷一個數是否為奇數
int a;//定義變數
scanf("%d",&a);//輸入數字；
if(a%2)printf("該數為奇數")； //不能被2整除就是奇數
else printf("該數為偶數");
③ 數據結構(用c語言描述)，是隨機快速排序演算法，劃紅線部分那裡我不懂，希望有學霸能解釋一下，越詳細越好
這是一個randomi的函數，作用是返回一個隨機值，在1到r之間。
return後面那個公式就是返回的隨機數字。
1*rand()是隨機得到一個數字，在除以RAND_MAX得到的是一個隨機的百分比。
RAND_MAX就是rand()的范圍大小。
隨機百分比得到了，在乘(r－1)就得到這個(r－1)范圍內隨機比例。
最後再加上1保證得到的數字是在1和r之間的。
這樣就能輸出一個隨機數字了。
精髓是後面那個除法得到一個隨機的比例，前面的乘法和加法都是為了限定范圍的修修補補。
④ c語言版數據結構圖的一些基本操作函數如下，有三個地方不了解，請各位幫幫忙
（1）問題三：
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
*G不是指針，是指針G所指對象，就是ALGraph類型。程序中多處使用變數G，但是不同的地方，含義不同。在void CreateGraph(ALGraph *G)裡面，G是一個指針，因此，引用其所指對象，要用*G。其他情況下，ALGraph G，G不是指針。
（2）第一：這個void DFSTraverse(ALGraph G,void(*print)(char*)) 為什麼不能直接調用print函數，像調用DFS函數一樣？可以的，使用函數指針是為以後任意擴展輸出程序，以適應不同需要，並且可以作為參數傳遞。
（3）第二：FirstAdjVex(G,G.vertices[v].data)為什麼要用頂點，用了之後又取位置，而不直接用位置，會有什麼漏洞嗎？不會
int FirstAdjVex(ALGraph G,VertexType v)
{
ArcNode *p;
int v1;
v1=LocateVex(G,v);
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
利用已經定義的定位函數LocateVex直接定位頂點v，然後直接讀取其firstarc，很自然的過程。
⑤ C語言數據結構求解
方法很多，可以在插入數據後再對線性表進行刪改，也可以在插入前進行處理。
我這里代碼是在插入前處理。
（注釋掉的函數int getPNUM(struct Sqlist *st,int n);是我預留的，題2如果你想改成插入後，再對線性表素數進行查找，可以用這個函數。否則可以刪除）。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LIST_INIT_SIZE 800
struct Sqlist{
int *elem;
int length;
int listsize;
};
int insert2List(struct Sqlist *st,int num,int inx);//向線性表第inx個元素的位置插入一個元素。成功返回1,失敗返回0
int findNum(struct Sqlist *st,int num);//在線性表中查找指定數字，存在返回1，不存在返回0
//int getPNUM(struct Sqlist *st,int n);//查找素數，返回第幾n個素數的下標。未找到返回-1
void showList(struct Sqlist *st);//列印線性表
void clearList(struct Sqlist *st);//清空線性表
int main()
{
int i,k,nums[LIST_INIT_SIZE],n,num,cnt,flag;
struct Sqlist st={nums,0,LIST_INIT_SIZE};
srand(time(NULL));
//--------------題1-----------------------------------------------------------------------
n=100;
k=1;
printf("1、隨機生成100個【100,200】之間的隨機數，去除重復並保存到線性表 ");
while(n--)
{
num=rand()%101+100;
printf("--%3d產生隨機數%d ",k++,num);
if(findNum(&st,num))
printf("該數字已在線性表中存在，重復去除 ");
else
{
if(insert2List(&st,num,st.length+1))
printf("該隨機值已保存到線性表尾部 ");
else{
printf("異常!插入失敗! ");
return 1;
}
}
}
showList(&st);
clearList(&st);
//-------------題2----------------------------------------------------------------
n=20;
cnt=0;
k=1;
printf("1、隨機生成20個【1,200】之間的隨機數，在第一個素數後插入1個0，第二個素數後插入2個0，以此類推，最後輸出所有元素 ");
while(n--)
{
num=rand()%200+1;
printf("--%3d產生隨機數%d ",k++,num);
flag=1;
for(i=2;i<num;i++)
if(num%i==0)
{
flag=0;
break;
}
if(flag)
{
cnt++;
printf("該隨機值是一個素數，在其尾部插入%d個0 ",cnt);
for(i=0;i<cnt;i++)
num*=10;
printf("該隨機值變更為%d ",num);
}
if(insert2List(&st,num,st.length+1))
printf("該隨機值已保存到線性表尾部 ");
else{
printf("異常!插入失敗! ");
return 1;
}
}
showList(&st);
return 0;
}
void clearList(struct Sqlist *st)//清空線性表
{
st->length=0;
printf("線性表數據已清除 ");
}
void showList(struct Sqlist *st)//列印線性表
{
int i;
printf("當前線性表的數據為: ");
for(i=0;i<st->length;i++)
printf("%d ",st->elem[i]);
printf(" ");
}
int findNum(struct Sqlist *st,int num)//在線性表中查找指定數字，存在返回1，不存在返回0
{
int *p=st->elem;
while(p<=&st->elem[st->length-1])
if(*p++==num)
return 1;
return 0;
}
/*
int getPNUM(struct Sqlist *st,int n)//查找素數，返回第幾n個素數的下標。未找到返回-1
{
int i,j,flag,cnt=0;
for(i=0;i<st->length;i++)
{
flag=1;
for(j=2;j<st->elem[i];j++)
if(st->elem[i]%j==0)
{
flag=0;
break;
}
if(flag)
cnt++;
if(cnt==n)
return i;
}
return -1;
}
*/
int insert2List(struct Sqlist *st,int num,int inx)//向線性表第inx個元素的位置插入一個元素。成功返回1,失敗返回0
{
int i;
if(st->length==st->listsize)
{
printf("線性表已滿，插入失敗！ ");
return 0;
}
if(inx<1 && inx>st->length+1)
{
printf("插入位置無效！線性表當前數據長度為%d，插入位置必須大於1且不能大於%d！ ",st->length,st->length+1);
return 0;
}
for(i=st->length;i>=inx;i--)
st->elem[i]=st->elem[i-1];
st->elem[inx-1]=num;
st->length++;
return 1;
}
⑥ C語言數據結構具體鏈表學習，最好有圖示
面向對象實現其實也算簡單吧 你如果把類和對象理解了 就能很好的去運用面向對象思想了 我java和C#面向對象多學過 給你講解一下吧 首先 類是一個比較抽象的概念 類是一個對象群體的概括 比如：人類就可以看成一個類 動物類也是一個類 植物類也是一個類 也就是說類是一組對象的抽象概念 而對象呢 就是一個類的特指 比如：人類是一個類 而人類里的張三 張三就是一個對象 這些能理解么？ 我再給你說說類的組成吧 類由屬性、方法、構造方法等組成 屬性就用來描述一個類的共有特徵的 比如人類都有名字、年齡、身高、體重等 這些在類裡面都用屬性去定義描述，而封裝就是為了避免類的使用者在不知情的時候為屬性亂賦值 所以把屬性私有化，為每個屬性提供公有的訪問和賦值的方法，也就是get和set方法；再說說方法 方法是一個類的行為 當一個類需要去完成一件事情的時候 就為其定義方法 比如：人都有吃飯的行為 所以在可以定義一個吃法的方法 繼承的概念我覺得用一句話就能說清楚：老鼠的兒子會打洞，老鼠一生下來就會打洞 這就是繼承自父類的 至於構造方法 那是在一個類去構造生成一個對象時用到的 java中構造一個對象語法是這樣的：類名 自定義對象么 =new 類名(); 當這樣去new一個對象的時候就會去調用無參構造方法
就這些吧 這都是我個人的理解 希望對你有幫助 記得加分哦 嘻嘻
⑦ 數據結構（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); /* 銷毀圖*/
}
⑧ 初學c語言數據結構，求下面圖片的每行程序的作用，怎麼實現的，多謝
#include <stdio.h>
#include <malloc.h>
#define MAXV 100//最大頂點個數
int visited[MAXV];//全局數組
typedef int InfoType;
typedef struct
{ int edges[MAXV][MAXV];//鄰接矩陣
int vexnum,arcnum; //頂點數，弧數
} MGraph;//圖的鄰接矩陣類型
typedef struct ANode
{ int adjvex; //該弧的終點位置
struct ANode *nextarc; //指向下一條弧的指針
InfoType info; //該弧的相關信息,這里用於存放權值 n
} ArcNode;//弧的結點結構類型
typedef struct Vnode
{ //int data; //頂點信息
ArcNode *firstarc;//指向第一條弧
} VNode;//鄰接表頭結點的類型
typedef struct
{
VNode adjlist[MAXV];//鄰接表
int n,e;//圖中頂點數n和邊數e
} ALGraph;//圖的鄰接表類型
void init(MGraph &g);//初始化鄰接矩陣
void MatToList(MGraph,ALGraph *&);//將鄰接矩陣g轉換成鄰接表G
void DispAdj(ALGraph *);//輸出鄰接表G
void DFS(ALGraph *G,int v);//深搜
void BFS(ALGraph *G,int v);//廣搜
void main()
{
MGraph g;
g.vexnum=11;g.arcnum=13;
init(g);//初始化鄰接矩陣
ALGraph *G=(ALGraph *)malloc(sizeof(ALGraph));
MatToList(g,G);//將鄰接矩陣g轉換成鄰接表G
DispAdj(G);//輸出鄰接表G
for (int i=0;i<g.vexnum;i++) visited[i]=0;
printf("深度優先生成樹:");
DFS(G,3);//從頂點3開始深度搜索
printf("\n");
//////
for (i=0;i<g.vexnum;i++) visited[i]=0;
printf("廣度優先生成樹:");
BFS(G,3);//從頂點3開始廣度搜索
}
void DFS(ALGraph *G,int v)//從頂點v開始深度搜索
{
visited[v]=1;//置已訪問標記
ArcNode *p=G->adjlist[v].firstarc;//p指向頂點v的第一條弧的弧頭結點
while (p!=NULL)
{
if (visited[p->adjvex]==0)//若p->adjvex頂點未訪問,遞歸訪問它
{
printf("<%d,%d> ",v,p->adjvex);//輸出生成樹的一條邊
DFS(G,p->adjvex);//遞歸函數
}
p=p->nextarc;//p指向頂點v的下一條弧的弧頭結點
}
}
void BFS(ALGraph *G,int v)
{
int queue[MAXV],front=0,rear=0; //定義循環隊列並初始化
int visited[MAXV]; //定義存放結點的訪問標志的數組
for (int i=0;i<G->n;i++) visited[i]=0; //訪問標志數組初始化
visited[v]=1; //置已訪問標記
queue[rear]=v;//已訪問過的頂點v進隊
rear=(rear+1)%MAXV;
while (front!=rear)//若隊列不空時循環
{
int w=queue[front];//出隊並賦給w
front=(front+1)%MAXV;
ArcNode *p=G->adjlist[w].firstarc; //找與頂點w鄰接的第一個頂點
while (p!=NULL)
{
if (visited[p->adjvex]==0) //若當前鄰接頂點未被訪問
{
printf("<%d,%d> ",w,p->adjvex);//輸出生成樹的一條邊
visited[p->adjvex]=1;//置該頂點已被訪問的標志
queue[rear]=p->adjvex;//該頂點p的終點進隊
rear=(rear+1)%MAXV;
}
p=p->nextarc;//找下一個鄰接頂點
}
}
printf("\n");
}
void init(MGraph &g)
{
int i,j;
int A[MAXV][11];
for (i=0;i<g.vexnum;i++)
for (j=0;j<g.vexnum;j++)
A[i][j]=0;
A[0][3]=1;A[0][2]=1;A[0][1]=1;
A[1][5]=1;A[1][4]=1;
A[2][6]=1;A[2][5]=1;A[2][3]=1;
A[3][7]=1;
A[6][9]=1;A[6][8]=1;A[6][7]=1;
A[7][10]=1;
for (i=0;i<g.vexnum;i++)
for (j=0;j<g.vexnum;j++)
A[j][i]=A[i][j];//無向圖雙向路徑對稱
for (i=0;i<g.vexnum;i++)
for (j=0;j<g.vexnum;j++)
g.edges[i][j]=A[i][j];
}
void MatToList(MGraph g,ALGraph *&G)//將鄰接矩陣g轉換成鄰接表G
{
int i,j;
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;i<g.vexnum;i++)//表頭節點的指針域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<g.vexnum;i++)//對於鄰接矩陣中每個元素
for (j=g.vexnum-1;j>=0;j--)
if (g.edges[i][j]!=0)//鄰接矩陣的當前元素不為0---頂點i到j可以走通
{
ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode));//創建一個新的弧節點
p->adjvex=j;//弧節點的指向的終點位置
p->info=g.edges[i][j];//弧節點的長度
p->nextarc=G->adjlist[i].firstarc;//將*p鏈到表頭後
G->adjlist[i].firstarc=p;//更新表頭指針//G->adjlist[i]---表頭:頂點i連通到可連通的點
}
G->n=g.vexnum;//鄰接表G的節點數
G->e=g.arcnum;//弧數
}
void DispAdj(ALGraph *G)//輸出鄰接表G
{
printf("圖G的鄰接表:\n");
for (int i=0;i<G->n;i++)//
{
ArcNode *p=G->adjlist[i].firstarc;
if (p!=NULL) printf("%3d: ",i);//輸出表頭元素
while (p!=NULL)
{
printf("%3d",p->adjvex);//輸出表頭後鏈接的元素
p=p->nextarc;
}
printf("\n");
}
}
⑨ c語言常見的數據結構有哪些
1、線性數據結構
元素之間一般存在元素之間存在一對一關系，是最常用的一類數據結構，典型的有：數組、棧、隊列和線性表。
2、樹形結構
結點間具有層次關系，每一層的一個結點能且只能和上一層的一個結點相關，但同時可以和下一層的多個結點相關，稱為“一對多”關系，常見類型有：樹、堆。
3、圖形結構
在圖形結構中，允許多個結點之間相關，稱為“多對多”關系。
(1)線性數據結構：元素之間一般存在元素之間存在一對一關系，是最常用的一類數據結構，典型的有：數組、棧、隊列和線性表
(2)樹形結構：結點間具有層次關系，每一層的一個結點能且只能和上一層的一個結點相關，但同時可以和下一層的多個結點相關，稱為“一對多”關系，常見類型有：樹、堆
(3)圖形結構：在圖形結構中，允許多個結點之間相關，稱為“多對多”關系
⑩ 數據結構代碼（用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 enumGraphKind; /* */
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); /* 銷毀圖*/
}