2 u010643777 u010643777 于 2014.05.01 17:02 提问

C语言 删除图中制定的节点

/*/////////////////////////////////////////////////////////////*/
/* 图的深度优先遍历 /
/
/////////////////////////////////////////////////////////////*/
#include
#include

struct node /* 图顶点结构定义 /
{
int vertex; /
顶点数据信息 /
struct node *nextnode; /
指下一顶点的指标 /
};
struct index
{ struct node *nextnode;
struct index *next;
};
typedef struct node *graph;/
图形的结构新型态 /
typedef struct index * graphindex;
struct node head[9]; /
图形顶点数组 /
int visited[9]; /
遍历标记数组 */

/********************根据已有的信息建立邻接表********************/
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
{
graph newnode; /*指向新节点的指针定义*/
graph ptr;
int from; /* 边的起点 /
int to; /
边的终点 */
int i;

for ( i = 0; i < num; i++ ) /* 读取边线信息,插入邻接表*/
{
from = node[i][0]; /* 边线的起点 /
to = node[i][1]; /
边线的终点 */

  /* 建立新顶点 */
  newnode = ( graph ) malloc(sizeof(struct node));
  newnode->vertex = to;        /* 建立顶点内容       */
  newnode->nextnode = NULL;    /* 设定指标初值       */
  ptr = &(head[from]);         /* 顶点位置           */
  while ( ptr->nextnode != NULL ) /* 遍历至链表尾   */
     ptr = ptr->nextnode;     /* 下一个顶点         */
  ptr->nextnode = newnode;    /* 插入节点        */

}
}

/********************** 图的深度优先搜寻法********************/

void dfs(int current)
{
graph ptr;

visited[current] = 1; /* 记录已遍历过 /
printf("vertex[%d]\n",current); /
输出遍历顶点值 /
ptr = head[current].nextnode; /
顶点位置 /
while ( ptr != NULL ) /
遍历至链表尾 /
{
if ( visited[ptr->vertex] == 0 ) /
如过没遍历过 /
dfs(ptr->vertex); /
递回遍历呼叫 /
ptr = ptr->nextnode; /
下一个顶点 */
}
}

graphindex creata(graph ga,int n)
{
graphindex p,k,r;
int i;
p=(graphindex)malloc(sizeof(struct index));
p->nextnode=&(ga[1]);/*建立索引,这样就可以方便删除图中的一些节点*/
r=p;
for(i=2;i<=n;i++)
{
k=(graphindex)malloc(sizeof(struct index));
k->nextnode=&(ga[i]);
k->next=NULL;
r->next=k;
r=k;
}
return p;
}
void my_free(graph ga)
{ graph ptr,fre;
ptr=ga->nextnode;
while(ptr!=NULL)
{
fre=ptr->nextnode;
free(ptr);
ptr=fre;
}
free(ga);
}
graphindex delete_a(graphindex ga,int a)
{ graphindex k,r;
graph gtr,ptr,rtr,ktr;
if((*ga->nextnode).vertex==a)
{
r=ga->next;
my_free(&(*ga->nextnode));
free(ga);
ga=r;
}
else
{
k=ga;
while((*k->nextnode).vertex!=a)
{
r=k;
k=k->next;
}
r->next=k->next;
my_free(&(*k->nextnode));
free(k);
}
for(k=ga;k!=NULL;k=k->next)
{
gtr=(*k->nextnode).nextnode;
if(gtr->vertex==a)
{
(*k->nextnode).nextnode=gtr->nextnode;
free(gtr);
gtr=(*k->nextnode).nextnode;
}
else
{ gtr=(*k->nextnode).nextnode;/代码在这里不能够运行,为什么?我想删除链表中的元素/
while(gtr->vertex!=a)
{
rtr=ptr;
gtr=gtr->nextnode;
}
rtr->nextnode=gtr->nextnode;
free(gtr);
}
}
return ga;
}
/****************************** 主程序******************************/

int main()
{
graph ptr;
graphindex pindex,k;
int deletnode;
int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 /
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} };/
有向表*/
int i;
for ( i = 1; i <= 8; i++ ) /* 顶点数组初始化 /
{
head[i].vertex = i; /
设定顶点值 /
head[i].nextnode = NULL; /
指针为空 /
visited[i] = 0; /
设定遍历初始标志 */
}

creategraph(node,20); /* 建立邻接表 /
printf("Content of the gragh's ADlist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf("vertex%d ->",head[i].vertex); /
顶点值 /
ptr = head[i].nextnode; /
顶点位置 /
while ( ptr != NULL ) /
遍历至链表尾 /
{
printf("%d ",ptr->vertex); /
印出顶点内容 /
ptr = ptr->nextnode; /
下一个顶点 /
}
printf("\n"); /
换行 /
}
printf("\nThe end of the dfs are:\n");
dfs(1); /
打印输出遍历过程 /
printf("\n");
pindex=creata(head,8);
for(k=pindex;k!=NULL;k=k->next)
{
printf("%d\t",(*k->nextnode).vertex);
for(ptr=(*k->nextnode).nextnode;ptr!=NULL;ptr=ptr->nextnode)/
对邻接表进行遍历*/
printf("%d\t",ptr->vertex);
printf("\n");
}
printf("input the node you want to delete:\n");
scanf("%d",&deletnode);
pindex=delete_a(pindex,deletnode);
for(k=pindex;k!=NULL;k=k->next)
{
printf("%d\t",(*k->nextnode).vertex);
for(ptr=(*k->nextnode).nextnode;ptr!=NULL;ptr=ptr->nextnode)/*对邻接表进行遍历*/
printf("%d\t",ptr->vertex);
printf("\n");
}
puts(" Press any key to quit...");
getchar();

}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!