㈠ 數據結構實現圖的基本操作
對鄰接表存儲的圖進行深度優先搜索演算法：
#include "stdio.h"
#define MAXVER 10 /* 最多頂點數 */
typedef char ElemType; /* 頂點元素類型 */
typedef struct node
{ int num;
struct node *next;
}slink; /* 邊或弧的結點類型 */
typedef struct
{ struct
{ ElemType vertex;
slink *first;
}ve[MAXVER]; /* 頂點信息結構 */
int vex,edge,tag; /* 存放頂點數、邊數和圖的類型 */
}adjlist; /* 鄰接表存儲結構類型名 */
/* 建立圖的鄰接表存儲表示。 */
void cregraph(adjlist *G,int n,int m) /* 建立鄰接表. n為頂點數，m為圖的類型 */
{ int i,e=0;slink *p,*q,*s;char x,y;
G->vex=n; G->tag=m;
for(i=0;i<n;i++)
{ G->ve[i].vertex=i+'A'; G->ve[i].first=NULL;} /* 初始化鄰接表 */
printf("Input edges(x-->y):"); /* 用大寫字母表示頂點 */
scanf("%c%c",&x,&y);
while(x!=' '&&y!=' ') /* 輸入邊或弧，遇空格符結束 */
{ e++; /* 統計邊或弧和數目 */
s=(slink *)malloc(sizeof(slink));
s->num=y-'A'; /* 生成結點插入 */
if(G->ve[x-'A'].first==NULL)
{ G->ve[x-'A'].first=s;
s->next=NULL;
}
else
{ p=G->ve[x-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) {p=q;q=q->next;}
p->next=s;s->next=q;
}
if(!G->tag) /* m=0表示建立無向圖的鄰接表 */
{ s=(slink *)malloc(sizeof(slink));
s->num=x-'A';
if(G->ve[y-'A'].first==NULL)
{ G->ve[y-'A'].first=s;s->next=NULL;}
else
{ p=G->ve[y-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) { p=q;q=q->next;}
p->next=s;s->next=q;
}
}
scanf("%c%c",&x,&y);
}
G->edge=e;
}
/* 輸出用鄰接表存儲表示的圖 */
void list(adjlist *G) /* 輸出鄰接表 */
{ int i; slink *p;
for(i=0;i<G->vex;i++)
{ printf("%d:%c--->",i,G->ve[i].vertex);
p=G->ve[i].first;
while(p)
{ printf("%3d",p->num);
p=p->next;
}
printf("\n");
}
}
/* 對鄰接表存儲的圖進行深度優先搜索演算法 */
int visited[MAXVER+1]; /* 頂點的訪問標記數組 */
dfs(adjlist *G,int v) /* v是訪問的起始點的下標 */
{ slink *p;
visited[v]=1;
printf("%3c",G->ve[v].vertex);
p=G->ve[v].first;
while(p)
{ if(visited[p->num]==0) /* 從V的未訪問過的鄰接點出發 */
dfs(G,p->num);
p=p->next; /* 找V的下一個鄰接點 */
}
}
void dfsgraph(adjlist *G)
{ int i;
for(i=0;i<G->vex;i++) if(!visited[i]) dfs(G,i);
}
main()
{ adjlist g;
int n=8;
cregraph(&g,n,0);
dfsgraph(&g);
}
對一個採用鄰接表作存儲結構的圖進行廣度優先遍歷：
/*鄰接表結構*/
#include "stdio.h"
#define MAXVER 10 /* 最多頂點數 */
typedef char ElemType; /* 頂點元素類型 */
typedef struct node
{ int num;
struct node *next;
}slink; /* 邊或弧的結點類型 */
typedef struct
{ struct
{ ElemType vertex;
slink *first;
}ve[MAXVER]; /* 頂點信息結構 */
int vex,edge,tag; /* 存放頂點數、邊數和圖的類型 */
}adjlist; /* 鄰接表存儲結構類型名 */
/*建立鄰接表*/
void cregraph(adjlist *G,int n,int m) /* n為頂點數，m為圖的類型 */
{ int i,e=0;slink *p,*q,*s;char x,y;
G->vex=n; G->tag=m;
for(i=0;i<n;i++)
{ G->ve[i].vertex=i+'A'; G->ve[i].first=NULL;} /* 初始化鄰接表 */
printf("Input edges(x-->y):"); /* 用大寫字母表示頂點 */
scanf("%c%c",&x,&y);
while(x!=' '&&y!=' ') /* 輸入邊或弧，遇空格符結束 */
{ e++; /* 統計邊或弧和數目 */
s=(slink *)malloc(sizeof(slink));
s->num=y-'A'; /* 生成結點插入 */
if(G->ve[x-'A'].first==NULL)
{ G->ve[x-'A'].first=s;
s->next=NULL;
}
else
{ p=G->ve[x-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) {p=q;q=q->next;}
p->next=s;s->next=q;
}
if(!G->tag) /* m=0表示建立無向圖的鄰接表 */
{ s=(slink *)malloc(sizeof(slink));
s->num=x-'A';
if(G->ve[y-'A'].first==NULL)
{ G->ve[y-'A'].first=s;s->next=NULL;}
else
{ p=G->ve[y-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) { p=q;q=q->next;}
p->next=s;s->next=q;
}
}
scanf("%c%c",&x,&y);
}
G->edge=e;
}
/* 輸出鄰接表 */
void list(adjlist *G) /* 輸出用鄰接表表示的圖 */
{ int i; slink *p;
for(i=0;i<G->vex;i++)
{ printf("%d:%c--->",i,G->ve[i].vertex);
p=G->ve[i].first;
while(p)
{ printf("%3d",p->num);
p=p->next;
}
printf("\n");
}
}
/* 對一個採用鄰接表作存儲結構的圖進行廣度優先遍歷 */
int visited[MAXVER];
void bfs(adjlist *G,int v)
{ int queue[MAXVER],front,rear,i;/* 定義一個分離隊列 */
slink *p;
front=rear=0; /* 隊列初始化為空 */
queue[rear++]=v; /* 初始頂點入隊列 */
while(front!=rear) /* 隊列不空 */
{ v=queue[front++]; /* 出隊列訪問 */
printf("%c->",G->ve[v].vertex);
visited[v]=1; /* 入訪問表 */
p=G->ve[v].first;
while(p!=NULL)
{ for(i=0;i<rear;i++)
if(p->num==queue[i]) break;
if(i>=rear)
queue[rear++]=p->num; /* 該鄰接點即沒被訪問過，也不在隊列中，則入隊列 */
p=p->next; /* 找V的下一個鄰接點 */
}
}
}
void bfsgraph(adjlist *G) /* 若還有不連通的部分，則跳過去訪問之 */
{ int i;
for(i=0;i<G->vex;i++)
if(!visited[i]) bfs(G,i);
}
main()
{ adjlist G;
cregraph(&G,8,0);
bfsgraph(&G);
}
最小生成樹的演算法：
/*求最小生成樹的Kruskal演算法描述*/
#define MAXE 10
struct edges
{ int bv,tv,w;}; /* 邊集類型，存儲一條邊的起始點bv終止頂點tv和權w */
typedef struct edges edgeset[MAXE+1];
int seeks(int set[],int v)
{ int i=v;
while(set[i]>0)
i=set[i];
return i;
}
kruskal(edgeset ge,int n,int e) /* ge表示的圖是按權值從小到大排列的 */
{ int set[MAXE],v1,v2,i,j;
for(i=1;i<=n;i++)
set[i]=0; /* 給set中的每個元素賦初值 */
i=1; /* i表示待獲取的生成樹中的邊數，初值為1 */
j=1; /* j表示ge中的下標，初值為1 */
while(j<n &&i<=e) /* 按邊權遞增順序，逐邊檢查該邊是否應加入到生成樹中 */
{ v1=seeks(set,ge[i].bv); /* 確定頂點v所在的邊通集 */
v2=seeks(set,ge[i].tv);
if(v1!=v2) /* 當v1,v2不在同一頂點集合，確定該邊應當選入生成樹 */
{ printf(" (%d,%d) ",ge[i].bv,ge[i].tv);
set[v1]=v2;
j++;
}
i++;
}
}
main()
{ edgeset e={{0,0,0},{4,5,2},{3,5,3},{1,4,5},{1,2,6},{2,4,7},{2,5,8},{1,3,9},{3,4,9},{1,5,13},{2,3,14}};
kruskal(e,5,10);
}
最短路徑的演算法：
#define Max 10 /* 預設最多頂點數 */
#define INFINITY 1000 /* 最大值 */
typedef struct
{ int vexnum,arcnum; /* 頂點數及邊或弧的數目 */
char vex[Max]; /* 存頂點信息的一維數組 */
int arc[Max][Max]; /* 存邊信息的二維數組 */
}AdjMatrix;
/* 建立有向圖的鄰接矩陣表示 */
void Creadjm(AdjMatrix *G)
{ int i,j,k,w;
printf("Input vex&arc:");
scanf("%d%d%*c",&G->vexnum,&G->arcnum);/*輸入頂點數和邊數，並讀掉回車符*/
printf("Input Vexinfo:");
for(k=0;k<G->vexnum;k++)
scanf("%c",&G->vex[k]); /* 輸入代表頂點的字元 */
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
G->arc[i][j]=INFINITY; /* 初始化鄰接矩陣 */
printf("Input %d edges:\n",G->arcnum);
for(k=0;k<G->arcnum;k++)
{ scanf("%d%d%d",&i,&j,&w); /* 輸入邊或弧 */
G->arc[i][j]=w;
}
}
/* 輸出用鄰接矩陣表示的有向圖 */
void list(AdjMatrix *G)
{ int i,j;
for(i=0;i<G->vexnum;i++)
{ printf("%6c----",G->vex[i]); /* 先輸出頂點信息 */
for(j=0;j<G->vexnum;j++)
printf("%4d",G->arc[i][j]); /* 再輸出與該頂點有關聯的邊或弧的信息 */
printf("\n");
}
}
/* 計算從頂點v0到其餘各點最短路徑演算法 */
void dijkstra(AdjMatrix *G,int n,int v0,int d[]) /* d數組存放各頂點最短路徑 */
{ int s[Max] ; /* s數組存放頂點是否找到最短路徑 */
int i,j,u,mindis;
for(i=0;i<n;i++)
{ d[i]=G->arc[v0][i];s[i]=0;}
s[v0]=1;
for(i=1;i<n;i++)
{ mindis=INFINITY;
for(j=0;j<n;j++)
if(s[j]==0 && d[j]<mindis) { u=j; mindis=d[j];}
s[u]=1; /* 頂點u已找到最短路徑 */
for(j=1;j<=n;j++) /* 修改j的最短路徑 */
if(s[j]==0&&d[j]>d[u]+G->arc[u][j]) d[j]=d[u]+G->arc[u][j];
}
}
main()
{ AdjMatrix G;
int d[Max],i;
Creadjm(&G);
list(&G);
dijkstra(&G,6,0,d);
for(i=0;i<G.vexnum;i++)
printf("%4d",d[i]);
}
㈡ 求救 急急急 數據結構 【實驗目的】 （1）掌握線性表的特點 （2）掌握線性表順序存儲結構和
題主你問的這個真心懶得寫 原因如下
顯然是作業 而且題主你一點都沒有試著解過
代碼很長
很無聊的問題
綜上，以後不要問類似的問題了
㈢ C語言 數據結構 （圖）校園導游咨詢模擬(代碼相關的)
導游咨詢幫實現
㈣ 實驗一 順序表的基本運算 一． 實驗目的： 掌握線性表在順序存儲結構上的插入、刪除運算。 二． 實驗要求
問老師吧 少年
㈤ 數據結構完整版實驗報告
(一)實驗目的和要求
實驗目的：熟練掌握線性表的基本操作在順序存儲結構上的實現。
實驗要求：任選一種高級程序語言編寫源程序，並調試通過，測試正確。
(二)實驗主要內容
1. 建立n個元素的順序表SqList，實現順序表的基本操作；
2. 在SqList的元素i之後插入一個元素，實現順序表插入的基本操作；
3. 在sqList中刪除指定位置i上的元素，實現順序表刪除的操作。
4.
(三)主要儀器設備
PC機，Windows XP操作平台，Visual C++
(四)實驗原理
順序表操作：定義一個順序表類，該類包括順序表的存儲空間、存儲容量和長度，以及構造、插入、刪除、遍歷等操作的方法
(五)實驗步驟與調試分析：
順序表操作：先構造有四個數據的順序表，在第4個位置插入9，再讀取並刪除第3個元素。
(六)實驗結果與分析：
順序表操作：
（七）附錄（源程序）：
#include<iostream>
using namespace std;
const int LIST_INIT_SIZE=10; //順序表初始長度
const int LISTINCREMENT=5; //順序表長度增值
class SqList
{
int *L; //定義存儲空間起始地址
int length; //順序表當前長度
int listsize; //順序表當前存儲容量
bool flag; //設立標志值記錄操作成敗
public:
SqList(int v1,int v2,int v3,int v4); //構造函數構造並初始化順序表
void ListInsert(int i,int e); //實現將e插入到順序表中第i個位置
void ListDelete(int i,int &e); //實現刪除順序表第i個元素
void ListVisit(); //實現順序表的遍歷
};
SqList::SqList(int v1,int v2,int v3,int v4) //構造並初始化順序表
{
L=new int[LIST_INIT_SIZE];
if(!L) //分配失敗
{
flag=false;
cout<<"ERROR"<<endl;
}
else //分配成功，進行初始化
{
*L=v1;
*(L+1)=v2;
*(L+2)=v3;
*(L+3)=v4;
length=4;
listsize=LIST_INIT_SIZE;
flag=true;
}
}
void SqList::ListInsert(int i,int e) //插入元素
{
int *p,*q;
int t;
if(i<1||i>length+1) cout<<"ERROR"<<endl; //插入位置錯誤
else
{
if(length==listsize) //空間不足，增加分配
{
p=new int[listsize+LISTINCREMENT];
if(!p) cout<<"ERROR"<<endl; //分配失敗
else //分配成功，復制順序表
{
for(t=0;t<length;t++)
*(p+t)=*(L+t);
q=L;L=p;p=q;
delete q;
listsize+=LISTINCREMENT;
}
}
for(t=length;t>=i;t--)
*(L+length)=*(L+length-1);
*(L+i-1)=e;
length++; //插入成功，表長加1
}
}
void SqList::ListDelete(int i,int &e)
{
if(i<1||i>length) cout<<"ERROR"<<endl; //刪除位置錯誤
else
{
e=*(L+i-1);
while(i<length)
{
*(L+i-1)=*(L+i);
i++;
}
length--; //刪除成功表長減1
}
}
void SqList::ListVisit() //遍歷
{
int i;
for(i=0;i<length;i++)
cout<<" "<<*(L+i);
cout<<endl;
}
int main()
{
int e=0;
SqList list(2,3,4,5);
list.ListVisit();
list.ListInsert(4,9);
list.ListVisit();
list.ListDelete(3,e);
list.ListVisit();
cout<<"e="<<e<<endl;
return 0;
}
㈥ 實驗五、二叉樹的基本操作和應用組織機構——二叉樹的建立和操作
//二叉樹的建立遍歷完全二叉樹判斷
#include<iostream>
#include<queue>
usingnamespacestd;
typedefstructNode{
chardata;
Node*lchild,*rchild;
}BiNode,*BiTree;
voidCreateBiTree(BiTree&bt)//輸入二叉樹元素
{
charc;
cin>>c;
if(c=='#'){
bt=NULL;
}
else{
bt=newBiNode;
bt->data=c;
cout<<"輸入"<<c<<"的左子樹"<<endl;
CreateBiTree(bt->lchild);
cout<<"輸入"<<c<<"的右子樹"<<endl;
CreateBiTree(bt->rchild);
}
}
intIsCBT(BiTree&bt)
{
BiNode*p=bt;
queue<BiNode*>q;
inttag=0;
if(p==NULL)return1;
q.push(p);
while(!q.empty())
{
p=q.front();q.pop();
if(p->lchild&&!tag)q.push(p->lchild);
elseif(p->lchild)return0;
elsetag=1;
if(p->rchild&&!tag)q.push(p->rchild);
elseif(p->rchild)return0;
elsetag=1;
}
return1;
}
voidpre(BiTree&bt){
if(bt){
cout<<bt->data<<"";
pre(bt->lchild);
pre(bt->rchild);
}
}
intmain()
{
BiTreebt;
CreateBiTree(bt);
pre(bt);
cout<<endl;
if(IsCBT(bt)){
cout<<"Yes,itisaCBT"<<endl;
}
else{
cout<<"No,itisnotaCBT"<<endl;
}
system("pause");
return0;
｝
㈦ 圖的基本操作與實現
看見題就復雜了