将若干城市信息存入一个带头结点的单链表，结点中的城市信息包括，城市名，城市的位置坐标，要求能够利用城市名和位置坐标进行有关添加，插入，删除，修改及查询成操作。要求：1给定一个城市名，返回其坐标 。2给定一个位置坐标P和一个距离d，返回所有与P的距离小于等于d的城市。 3城市之间奇数相通，所有质数与质数+1城市相通。求两城市的最短路线。

这题其它的问题九九可以自己解决，就是那个最短路线不是很会理解~感觉题目提示信息不是很明确~帮忙看看~

据说这是数据结构的问题，应该可以找到原题和答案的，就是那个求两个城市的最短路线那里卡壳了~帮忙看看~

PS:我把求最短路径理解成两种意思~
1：求所有任意连通城市之间的最短距离
2：求指定两个城市所有连通路径之间的最短路径~
那个出题给九九的竟然要两种可能都试试~

PS感觉相通之间的城市太多了~稍微逻辑推理就知道两个直接相通的城市之间直线距离最短~如果两个城市相通~最多不会超过3段~感觉出题的应该是以第一种理解为主~不过第二种情况是有算法值得学习的~

这个是网络里，路由对数据包传输的最短路径问题。好像有个TTL来算步长，步长越短表示越近，也有改良版本的加上检测线路质量的权衡值来作判断。
发发你看到的题目看看，这是一个经典题

我看到的就是1楼的~别人转发来给我看的~

晚点我上网找找类似的题发出来大家研究一下吧。。。

好的，那麻烦你了~

路由算法，信息量有点大，可以直接跳到 7典型种类 的部分看它的基本算法。
http://baike.baidu.com/link?url=uXw3gG0pLtq7cWI5RLS32ibQN0fCgFIUPZmk7yGPAFLptaMeYk5bRQEmgJE1UUG341qyTOOYY26RltftDq2A5q

而你的问题好像叫最短路径算法，其实这最短路径算法用在了解决路由算法上。
http://baike.baidu.com/view/349189.htm

自从电脑修好后，九九就要准备学习数据结构了，在学数据结构之前先要把链表基础打好~
最近在写链表操作的时候受了yangfrancis和x版主的启发，所以自己打算重新写写~

下面第一波已经完善了链表的创建~
有什么建议可以提出一下，好让九九去完善~
还是以拿最短距离为例~

/*
将若干城市信息存入一个带头结点的单链表，
结点中的城市信息包括，城市名，城市的位置坐标，要求能够利用城市名和位置坐标进行有关
添加，插入，删除，修改及查询成操作。
要求：
1给定一个城市名，返回其坐标 。
2给定一个位置坐标P和一个距离d，返回所有与P的距离小于等于d的城市。
3城市之间奇数相通，所有质数与质数+1城市相通。求两城市的最短路线。
*/
#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#include<conio.h>
#include<string.h>

#define LEN sizeof(Node)
#define S(a) sizeof(a)/sizeof(*a)
#define FIND(a,b)b-a

typedef struct Node
{
    int num;
    char name[20];
    double x;
    double y;
    struct Node* next;
}Node;

typedef void FUN(Node** head);
FUN fun_0,fun_1,fun_2,fun_3,fun_4,fun_5;

void cr_Node(Node **head);
void insert(Node** head,Node* ins,Node* p_ins);//插入节点----ins 插入节点的地址 p_ins被插入节点的地址

void menu();

void find_member(Node* head,int flag,int (*pfun1)(const void* p1,const void* p2));

void creat(Node** p);//创建节点
void date(Node* head);//输入数据
void my_scanf(const void *s,const void *p);
void print(Node* p);
void print_one(Node* p);
void del(Node* p);//删除节点
void my_free(Node* head);//释放节点
void change();

int my_continue(const void* p);
int my_strcmp(const void* p1,const void* p2);

int n=0;

void menu();

int main()
{
    
    Node* head=NULL;

    typedef void (*COM)();
    COM com[]={fun_0,fun_1,fun_2,fun_3,fun_4,fun_5};
    char c=0;

    while (c!=S(com))
    {
        menu();
        c=getch()-'0'-1;

        system("cls");

        if (c>-1&&c<S(com))
        {
            com[c](&head);
            fflush(stdin);
            printf("\n即将返回菜单\n");
            system("pause");
            system("cls");
        }
    }

    my_free(head);//清空链表要养成习惯(受x版主的影响)

    return 0;
}
void fun_0(Node** head)
{
    cr_Node(head);
}
void fun_1(Node** head)
{
    do
    {
        find_member(*head,0,my_strcmp);
    }while (my_continue("还需要继续查找吗(Y||N)?\n"));
}
void fun_2(Node** head)
{

}
void fun_3(Node** head)
{

}
void fun_4(Node** head)
{

}
void fun_5(Node** head)
{

}
void menu()
{
    system("cls");
    printf("**********<<城市管理系统>>**********\n");
    printf("1:创建(添加数据)\n");
    printf("2:查找数据\n");
    printf("3:插入数据\n");
    printf("4:删除数据\n");
    printf("5:修改数据\n");
    printf("6:退出\n");
}
void cr_Node(Node** head)
{
    Node* p=*head;

    while (*head&&p->next)
        p=p->next;

    do
    {
        Node* p2=p;

        system("cls");

        creat(&p);//创建节点
        date(p);//输入数据
        insert(head,p,p2);//插入节点到链表
    }while (my_continue("还需要继续创建城市数据吗(Y||N)?\n"));
}
void creat(Node **p)
{
     *p=(Node* )malloc(LEN);
     (*p)->next=NULL;

}
void insert(Node** head,Node* ins,Node* p_ins)
{
    if (p_ins==NULL)//当p_ins为NULL时属于头插(空链表属于头插)
    {
        ins->next=*head;
        *head=ins;
        return ;
    }

    ins->next=p_ins->next;
    p_ins->next=ins;
}
void print(Node* head)
{
    Node* p=head;

    printf("编号           名称          x坐标    y坐标\n");
    while (p)
    {
        print_one(p);
        p=p->next;
    }
}

void print_one(Node* p)
{
    printf("%-10d%-20s%-8.2f%-8.2f\n",p->num,p->name,p->x,p->y);
}
void my_free(Node* head)
{
    Node* p=head;
    
    if (head==NULL)
        return ;

    while (p->next)
    {
        p=p->next;
        free(head);
        head=p;
    }

    free(head);
}
void date(Node* p)
{
    void *pr[][3]=
    {
        "请输入第城市的编号:\n","%d",&p->num,
        "请输入城市的名称:\n","%20[^\n]%*c",p->name,
        "请输入城市的x坐标:\n","%lf",&p->x,
        "请输入城市的y坐标:\n","%lf",&p->y,
    };

    int i=0;

    ++n;
    printf("正在创建第%d个城市的数据\n",n);

    for (i=0;i<S(pr);++i)
    {
        printf(pr[i][0]);
        my_scanf(pr[i][1],pr[i][2]);
    }
}

void my_scanf(const void* s,const void* p)
{
    while (scanf(s,p)!=1)
    {
        printf("输入数据有误,请重新输入数据\n");
        fflush(stdin);
    }

    fflush(stdin);
}
int my_continue(const void* p)
{
    char c=0;
    printf(p);

    while (1)
    {
        int k=0;
        c=getch();
        k=((c=='y'||c=='Y'||c=='n'||c=='N'));
        if (k)
            return (c=='Y'||c=='y');

        printf("输入只能在Y或N之间选择,请重新输入:\n");
    }
}

void find_member(Node* head,int flag,int (*pfun1)(const void* p1,const void* p2))
{
    Node* p=head;
    char name[20]={0};
    int k=(int* )head->name-(int* )head;
    system("cls");
    printf("请输入查找城市的名称:\n");
    my_scanf("%20[^\n]%*c",name);

    while (p)
    {
        if ((*pfun1)(name,(int* )p+k)==flag)
        {
            printf("编号           名称          x坐标    y坐标\n");
            print_one(p);
            return ;
        }
        p=p->next;
    }

    printf("没有找到城市的数据\n");

}
void del(Node* p)//删除节点
{

}
int my_strcmp(const void* p1,const void* p2)
{
    return strcmp(p1,p2);

}
void change()
{}

九九会做多少就做多少~代更~

其实九九原意是想强化链表操作的~感觉前期菜单功能没有处理好~后期制作才补上~看来要大改一下主体结构了~这次就当积累一下经验~下次更时间也许较长~九九还要养成功能系统化和尽量增强功能通用性的习惯~下次更的时间也许较长了~

[此贴子已经被作者于2017-2-14 20:01编辑过]

收到的鲜花

• azzbcc 于 2017-02-13 09:23 送鲜花  5朵   附言：void creat(Node** p)或者 Node *create().
• 炎天 于 2017-02-14 01:23 送鲜花  6朵   附言：好文章

9楼第二更~
有点像我曾经写那个大型学生信息管理系统的味道了~

[此贴子已经被作者于2017-2-13 10:34编辑过]