The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

#

浅究初等数论之中国剩余定理(Chinese Remainder Theorem)

 推论1:方程ax=b(mod n)对于未知量x有解,当且仅当gcd(a,n) | b。
 推论2:方程ax=b(mod n)或者对模n有d个不同的解,其中d=gcd(a,n),或者无解。
 定理1:设d=gcd(a,n),假定对整数x和y满足d=ax+by(比如用扩展Euclid算法求出的一组解)。如果d | b,则方程ax=b(mod n)有一个解x0满足x0=x*(b/d) mod n 。特别的设e=x0+n,方程ax=b(mod n)的最小整数解x1=e mod (n/d),最大整数解x2=x1+(d-1)*(n/d)。
 定理2:假设方程ax=b(mod n)有解,且x0是方程的任意一个解,则该方程对模n恰有d个不同的解(d=gcd(a,n)),分别为:xi=x0+i*(n/d) mod n 。


证明过程请详见 《算法导论》

    #include<iostream>
#include
<algorithm>
#include
<cmath>
#include
<cstdio>
using namespace std;

int EXTENDED_EUCLID(int a,int b,int &x,int &y)//扩展欧几里德算法
{
    
if(b==0)
    
{
        x
=1;
        y
=0;
        
return a;
    }

    
int r=EXTENDED_EUCLID(b,a%b,x,y);
    
int temp=x;
    x
=y;
    y
=temp-a/b*y;
    
return r;
}


int  MODULAR_LINEAR(int a,int b,int n)//求解模线性方程
{
    
int d,x,y;
    
int x0;
    d
=EXTENDED_EUCLID(a,n,x,y);
    x0
=(x*(b/d)+n)%n;
    
return x0;
}

//当时鱼头让我们研究的时候,没有考虑得太仔细,上面的方程只能求出一个可行解
//而下面的函数能够求出最小的整数解,甚至在模n内任意的解
long long  MODULAR_LINEAR(long long a,long long b,long long n)//求解模线性方程
{
    
long long d,x,y;
    
long long x0;
    d
=EXTENDED_EUCLID(a,n,x,y);
    
if(b%d)
        
return -1;
    x0
=(x*(b/d))%n+n;//确保是正数
    x0%=(n/d);//x0是第一个大于0的整数解
    return x0;
}


int CHINESE_RESIDUE_THEOREM(int n[],int b[],int k)//求解模线性方程组,所有数据从1号下标开始存储
{

    
int result=0;
    
int i;
    
int N=1;
    
int *m=new int [k+1];
    
int *reversem=new int [k+1];
    
int sum=0;
    
for(i=1;i<=k;i++)
    
{
        N
*=n[i];
    }

    
for(i=1;i<=k;i++)
    
{

        m[i]
=N/n[i];
        reversem[i]
=MODULAR_LINEAR(m[i],1,n[i]);
        sum
+=m[i]*reversem[i]*b[i];
    }

    result
=sum%N;
    
return result;
}



int main ()
{

    
int num;
    
int i;
    printf(
"参考格式:X mod n[i] = b[i]\n");
    cout
<<"请输入方程的个数:";
    cin
>>num;
    
int *n=new int [num+1];
    
int *b=new int [num+1];
    
for(i=1;i<=num;i++)
    
{

        cout
<<"请输入第"<<i<<"个方程的n和b:";
        cin
>>n[i]>>b[i];
    }

    
int result=CHINESE_RESIDUE_THEOREM(n,b,num);
    cout
<<"解为:";
    cout
<<result<<endl;
    cout
<<"谢谢你的使用"<<endl;
    system(
"pause");
    
return 0;
}

posted @ 2009-04-08 01:15 abilitytao 阅读(1551) | 评论 (0)编辑 收藏

POJ 2996-Help Me with the Game(模拟题)

     摘要: 这道题直接模拟就好了,不过我有一点不明白的是,确定棋子的位置时两次的搜索顺序为什么不同?如果说要考虑玩家的视角的话,为什么输出的格式还是一样的呢?呵呵。值得一提的是:为了模拟这道题,我把所有的步骤分布来写了。1.初步读入数据,略去棋盘框架(input);2.精确读入棋盘点每个棋子的信息,过滤(filter);3.搜索(read)4.输出(print)不过值得注意的是:这样写代码会很长,看来怎么缩短...  阅读全文

posted @ 2009-04-04 23:27 abilitytao 阅读(434) | 评论 (0)编辑 收藏

POJ 2643-Election(map容器水之)

这道题的大意是:
有n个党派,每个党派有一位主席,现在选举国家领导人,m个人投票,看看获胜的是那个党或者是个人;
PS:题目里没说清楚,就是每个党派只有一个候选人,这个要注意下,其它的没什么好说的了,此题不难。
#include<iostream>
#include
<cmath>
#include
<string>
#include
<algorithm>
#include
<map>
using namespace std;

map
<string,string>mymap_party;
map
<int,string>mymap_name;
map
<string,int>mymap_index;

int votenum[1000000];

int main()
{
    
int i;
    
int n,m;
    memset(votenum,
0,sizeof(votenum));
    scanf(
"%d",&n);
    cin.ignore();
    
for(i=1;i<=n;i++)
    
{
        
string temp1;
        
string temp2;
        getline(cin,temp1);
        getline(cin,temp2);
        mymap_party[temp1]
=temp2;
        mymap_name[i]
=temp1;
        mymap_index[temp1]
=i;
    }

    scanf(
"%d",&m);
    cin.ignore();
    
for(i=1;i<=m;i++)
    
{

        
string temp;
        getline(cin,temp);
        votenum[mymap_index[temp]]
++;
    }

    
int max=0;
    
int maxmark=0;
    
int secmax=0;
    
for(i=1;i<=n;i++)
    
{

        
if(votenum[i]>max)
        
{
            secmax
=max;
            max
=votenum[i];
            maxmark
=i;
        }

        
else if(votenum[i]>secmax)
        
{
            secmax
=votenum[i];
        }

    }

    
string test("independent");
    
if(max==secmax)
        printf(
"tie\n");
    
else if(max!=secmax&&mymap_party[mymap_name[maxmark]]==test)
        cout
<<mymap_name[maxmark]<<endl;
    
else 
        cout
<<mymap_party[mymap_name[maxmark]]<<endl;
    system(
"pause");


    
return 0;

}









posted @ 2009-04-04 17:12 abilitytao 阅读(341) | 评论 (0)编辑 收藏

POJ 1093-Sorting It All Out(早知道不用拓扑排序了。。。)

     摘要: 刚上完数据结构课,想练习一下邻接表以及拓扑排序,于是找到了这道题,没想到这道题远远不止拓扑排序这么简单,汗~PS:这道题用拓扑排序要特别注意,当度为零的点>1时,要判断图中是否有环。我就是错在这里,结果调了一个下午。 #include<iostream>#include<algorithm>#include<cassert>#include<cma...  阅读全文

posted @ 2009-04-04 01:05 abilitytao 阅读(531) | 评论 (1)编辑 收藏

ACM模板之—堆栈(模板类)

//BEGIN_TEMPLATE_BY_ABILITYTAO_ACM
#include<iostream>
#include
<algorithm>
#include
<cassert>
using namespace std;

template
<class T>
class Stack
{

private:
    
int top;
    T 
*element;
    
int maxsize;
public:
    Stack(
int n=100000);
    
~Stack(){delete []element;}
    
void push(const T &item);
    T pop();
    T gettop();
    
int size();
    
void clear(){top=-1;}
    
bool isempty()const {return top==-1;}
    
bool isfull()const {return top==maxsize-1;}
}
;

template
<class T>
Stack
<T>::Stack(int n = 100000):top(-1),maxsize(n)
{

    element
=new T[maxsize];
    assert(element
!=0);
}


template
<class T>
void Stack<T>::push(const T &item)
{

    assert(
!isfull());
    element[
++top]=item;
}


template
<class T>
T Stack
<T>::pop()
{

    assert(
!isempty());
    
return element[top--];
}


template
<class T>
T Stack
<T>::gettop()
{

    assert(
!isempty());
    
return element[top];
}

template
<class T>
int Stack<T>::size()
{
    
return top+1;
}

//END_TEMPLATE_BY_ABILITYTAO_ACM


int main ()
{

    Stack
<int>test;
    
bool b;
    
int i;
    
int n;
    
for(i=1;i<=10;i++)
    
{
        b
=test.isfull();
        test.push(i);
    }

    n
=test.size();
    b
=test.isfull();
    
for(i=1;i<=5;i++)
        
int n=test.pop();
    test.clear();
    
for(i=1;i<=10;i++)
        test.push(i);
    
for(i=1;i<=10;i++)
    
{
        b
=test.isempty();
        cout
<<test.pop();
    }

    b
=test.isempty();
    
return 0;
    


}

posted @ 2009-04-03 12:02 abilitytao 阅读(1671) | 评论 (5)编辑 收藏

C++中模板使用介绍(转)

1. 模板的概念。

我们已经学过重载(Overloading),对重载函数而言,C++的检查机制能通过函数参数的不同及所属类的不同。正确的调用重载函数。例如,为求两个数的最大值,我们定义MAX()函数需要对不同的数据类型分别定义不同重载(Overload)版本。

//函数1.

int max(int x,int y);
{return(x>y)?x:y ;}

//函数2.
float max( float x,float y){
return (x>y)? x:y ;}

//函数3.
double max(double x,double y)
{return (c>y)? x:y ;}

但如果在主函数中,我们分别定义了 char a,b; 那么在执行max(a,b);时 程序就会出错,因为我们没有定义char类型的重载版本。

现在,我们再重新审视上述的max()函数,它们都具有同样的功能,即求两个数的最大值,能否只写一套代码解决这个问题呢?这样就会避免因重载函数定义不 全面而带来的调用错误。为解决上述问题C++引入模板机制,模板定义:模板就是实现代码重用机制的一种工具,它可以实现类型参数化,即把类型定义为参数, 从而实现了真正的代码可重用性。模版可以分为两类,一个是函数模版,另外一个是类模版。

2.   函数模板的写法

函数模板的一般形式如下:

Template <class或者也可以用typename T>

返回类型 函数名(形参表)
{//
函数定义体 }

说明: template是一个声明模板的关键字,表示声明一个模板关键字class不能省略,如果类型形参多余一个 ,每个形参前都要加class <类型 形参表>可以包含基本数据类型可以包含类类型.

请看以下程序:

//Test.cpp

#include <iostream>

using std::cout;

using std::endl;

//声明一个函数模版,用来比较输入的两个相同数据类型的参数的大小,class也可以被typename代替,

//T可以被任何字母或者数字代替。

template <class T>

T min(T x,T y)

{ return(x<y)?x:y;}

void main( )

{

     int n1=2,n2=10;

     double d1=1.5,d2=5.6;

     cout<< "较小整数:"<<min(n1,n2)<<endl;

     cout<< "较小实数:"<<min(d1,d2)<<endl;

     system("PAUSE");

}

程序运行结果: 

 

程序分析:main()函数中定义了两个整型变量n1 , n2 两个双精度类型变量d1 , d2然后调用min( n1, n2); 即实例化函数模板T min(T x, T y)其中T为int型,求出n1,n2中的最小值.同理调用min(d1,d2)时,求出d1,d2中的最小值.

3. 类模板的写法

定义一个类模板:

Template < class或者也可以用typename T >
class
类名{
//类定义......
};

说明:其中,template是声明各模板的关键字,表示声明一个模板,模板参数可以是一个,也可以是多个。

例如:定义一个类模板:

// ClassTemplate.h
#ifndef ClassTemplate_HH

#define ClassTemplate_HH

template<typename T1,typename T2>

class myClass{

private:

     T1 I;

     T2 J;

public:

     myClass(T1 a, T2 b);//Constructor

     void show();

};

//这是构造函数

//注意这些格式

template <typename T1,typename T2>

myClass<T1,T2>::myClass(T1 a,T2 b):I(a),J(b){}

//这是void show();

template <typename T1,typename T2>

void myClass<T1,T2>::show()

{

     cout<<"I="<<I<<", J="<<J<<endl;

}

#endif

// Test.cpp

#include <iostream>

#include "ClassTemplate.h"

using std::cout;

using std::endl;

void main()

{

     myClass<int,int> class1(3,5);

     class1.show();

     myClass<int,char> class2(3,'a');

     class2.show();

     myClass<double,int> class3(2.9,10);

     class3.show();

     system("PAUSE");

}

最后结果显示:

 

4.非类型模版参数

一般来说,非类型模板参数可以是常整数(包括枚举)或者指向外部链接对象的指针。

那么就是说,浮点数是不行的,指向内部链接对象的指针是不行的。


template<typename T, int MAXSIZE>

class Stack{

Private:

       T elems[MAXSIZE];

};

Int main()

{

       Stack<int, 20> int20Stack;

       Stack<int, 40> int40Stack;

};

posted @ 2009-04-03 11:14 abilitytao 阅读(14457) | 评论 (16)编辑 收藏

CONST使用解析(转)

看到const 关键字,C++程序员首先想到的可能是const 常量。这可不是良好的条件反射。如果只知道用const 定义常量,那么相当于把火药仅用于制作鞭炮。const 更大的魅力是它可以修饰函数的参数、返回值,甚至函数的定义体。

const 是constant 的缩写,“恒定不变”的意思。被const 修饰的东西都受到强制保护,可以预防意外的变动,能提高程序的健壮性。所以很多C++程序设计书籍建议:“Use const whenever you need”。


1.用const 修饰函数的参数

如果参数作输出用,不论它是什么数据类型,也不论它采用“指针传递”还是“引用传递”,都不能加const 修饰,否则该参数将失去输出功能。const 只能修饰输入参数:

如果输入参数采用“指针传递”,那么加const 修饰可以防止意外地改动该指针,起到保护作用。

例如StringCopy 函数:

void StringCopy(char *strDestination, const char *strSource);

其中strSource 是输入参数,strDestination 是输出参数。给strSource 加上const修饰后,如果函数体内的语句试图改动strSource 的内容,编译器将指出错误。

如果输入参数采用“值传递”,由于函数将自动产生临时变量用于复制该参数,该输入参数本来就无需保护,所以不要加const 修饰。

例如不要将函数void Func1(int x) 写成void Func1(const int x)。同理不要将函数void Func2(A a) 写成void Func2(const A a)。其中A 为用户自定义的数据类型。

对于非内部数据类型的参数而言,象void Func(A a) 这样声明的函数注定效率比较底。因为函数体内将产生A 类型的临时对象用于复制参数a,而临时对象的构造、复制、析构过程都将消耗时间。

为了提高效率,可以将函数声明改为void Func(A &a),因为“引用传递”仅借用一下参数的别名而已,不需要产生临时对象。但是函数void Func(A &a) 存在一个缺点:

“引用传递”有可能改变参数a,这是我们不期望的。解决这个问题很容易,加const修饰即可,因此函数最终成为void Func(const A &a)。

以此类推,是否应将void Func(int x) 改写为void Func(const int &x),以便提高效率?完全没有必要,因为内部数据类型的参数不存在构造、析构的过程,而复制也非常快,“值传递”和“引用传递”的效率几乎相当。

问题是如此的缠绵,我只好将“const &”修饰输入参数的用法总结一下。

对于非内部数据类型的输入参数,应该将“值传递”的方式改为“const 引用传递”,目的是提高效率。例如将void Func(A a) 改为void Func(const A &a)。

对于内部数据类型的输入参数,不要将“值传递”的方式改为“const 引用传递”。否则既达不到提高效率的目的,又降低了函数的可理解性。例如void Func(int x) 不应该改为void Func(const int &x)。


2 .用const 修饰函数的返回值
如果给以“指针传递”方式的函数返回值加const 修饰,那么函数返回值(即指针)的内容不能被修改,该返回值只能被赋给加const 修饰的同类型指针。例如函数
const char * GetString(void);
如下语句将出现编译错误:
char *str = GetString();
正确的用法是
const char *str = GetString();
如果函数返回值采用“值传递方式”,由于函数会把返回值复制到外部临时的存储单元中,加const 修饰没有任何价值。
例如不要把函数int GetInt(void) 写成const int GetInt(void)。
同理不要把函数A GetA(void) 写成const A GetA(void),其中A 为用户自定义的数据类型。
如果返回值不是内部数据类型,将函数A GetA(void) 改写为const A & GetA(void)的确能提高效率。但此时千万千万要小心,一定要搞清楚函数究竟是想返回一个对象的“拷贝”还是仅返回“别名”就可以了,否则程序会出错。
函数返回值采用“引用传递”的场合并不多,这种方式一般只出现在类的赋值函数中,目的是为了实现链式表达。

例如:
class A
{
A & operate = (const A &other); // 赋值函数
};
A a, b, c; // a, b, c 为A 的对象

a = b = c; // 正常的链式赋值
(a = b) = c; // 不正常的链式赋值,但合法
如果将赋值函数的返回值加const 修饰,那么该返回值的内容不允许被改动。上例中,语句 a = b = c 仍然正确,但是语句 (a = b) = c 则是非法的。


3. const 成员函数
任何不会修改数据成员(即函数中的变量)的函数都应该声明为const 类型。如果在编写const 成员函数时,不慎修改了数据成员,或者调用了其它非const 成员函数,编译器将指出错误,这无疑会提高程序的健壮性。以下程序中,类stack 的成员函数GetCount 仅用于计数,从逻辑上讲GetCount 应当为const 函数。编译器将指出GetCount 函数中的错误。
class Stack
{
public:
void Push(int elem);
int Pop(void);
int GetCount(void) const; // const 成员函数
private:
int m_num;
int m_data[100];
};
int Stack::GetCount(void) const
{
++ m_num; // 编译错误,企图修改数据成员m_num
Pop(); // 编译错误,企图调用非const 函数
return m_num;
}
const 成员函数的声明看起来怪怪的:const 关键字只能放在函数声明的尾部,大概是因为其它地方都已经被占用了。
关于Const函数的几点规则:

a. const对象只能访问const成员函数,而非const对象可以访问任意的成员函数,包括const成员函数.
b. const对象的成员是不可修改的,然而const对象通过指针维护的对象却是可以修改的.
c. const成员函数不可以修改对象的数据,不管对象是否具有const性质.它在编译时,以是否修改成员数据为依据,进行检查.
e. 然而加上mutable修饰符的数据成员,对于任何情况下通过任何手段都可修改,自然此时的const成员函数是可以修改它的

posted @ 2009-04-03 11:01 abilitytao 阅读(194) | 评论 (0)编辑 收藏

ACM模板之—循环队列(模板类)

//BEGIN_TEMPLATE_BY_ABILITYTAO_ACM
#include<cassert>
#include
<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;

template
<class T>
class Queue
{
private:
    
int front,rear;
    T 
*element;
    
int maxsize;
public:
    Queue(
int n=10000);
    
~Queue(){delete []element;}
    
void push_back(T item);
    T pop_front();
    T get_front();
    
void clear(){front=rear=0;}
    
bool isempty(){return front==rear;}
    
bool isfull(){return (rear+1)%maxsize==front;}
    
int lenth(){return (rear-front+maxsize)%maxsize;}
}
;


template
<class T>
Queue
<T>::Queue(int n=10000)
{
    front
=0;
    rear
=0;
    maxsize
=n;
    element
=new T[maxsize];
}


template
<class T>
void Queue<T>::push_back( T item)
{

    assert(
!isfull());
    rear
=(rear+1)%maxsize;
    element[rear]
=item;
}


template
<class T>
T Queue
<T>::pop_front()
{
    assert(
!isempty());
    front
=(front+1)%maxsize;
    
return element[front];
}


template
<class T>
T Queue
<T>::get_front()
{

    assert(
!isempty());
    
return element[(front+1)%maxsize];
}

//END_TEMPLATE_BY_ABILITYTAO_ACM






/////////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    Queue
<int> test(10);
    
int n;
    
int i;
    
for( i=1;i<=9;i++)
        test.push_back(i);
    n
=test.get_front();
    n
=test.lenth();
    test.clear();
    n
=test.lenth();
    
return 0;
}

虽然这个模板已经通过简单测试,不过我还是有几问题不太明白,希望大家能帮我解释一下:
这个队列中的数组写成动态形式是一个不错的想法,但是调试的时候比较麻烦,因为debug时在test.element下面看不到任何数组元素。不知道该怎么解决?

posted @ 2009-04-02 20:57 abilitytao 阅读(1770) | 评论 (8)编辑 收藏

数据结构作业之-拓扑排序(C++实现)

//张宏数据结构作业之__拓扑排序
//Get Guidance by Mr ZhangHong
//Student:abilitytao

#include
<iostream>
#include
<cmath>
#include
<cstdio>
#include
<algorithm>
#include
<stack>
using namespace std;
#define MAX 9999

stack
<int>mystack;
int indegree[MAX];

struct node 
{
    
int adjvex;
    node
* next;
}
adj[MAX];

int Create(node adj[],int n,int m)//邻接表建表函数,n代表定点数,m代表边数
{
    
int i;
    node 
*p;
    
for(i=1;i<=n;i++)
    
{
        
        adj[i].adjvex
=i;
        adj[i].next
=NULL;
    }

    
for(i=1;i<=m;i++)
    
{
        cout
<<"请输入第"<<i<<"条边:";
        
int u,v;
        cin
>>u>>v;
        p
=new node;
        p
->adjvex=v;
        p
->next=adj[u].next;
        adj[u].next
=p;
    }

    
return 1;
}



void print(int n)//邻接表打印函数
{
    
int i;
    node 
*p;
    
for(i=1;i<=n;i++)
    
{
        p
=&adj[i];
        
while(p!=NULL)
        
{
            cout
<<p->adjvex<<' ';
            p
=p->next;
        }

        cout
<<endl;
    }

}


void topsort(node adj[],int n)
{

    
int i;
    node 
*p;
    memset(indegree,
0,sizeof(indegree));
    
for(i=1;i<=n;i++)
    
{

        p
=adj[i].next;
        
while(p!=NULL)
        
{
            indegree[p
->adjvex]++;
            p
=p->next;
        }

    }

    
for(i=1;i<=n;i++)
    
{

        
if(indegree[i]==0)
            mystack.push(i);
    }

    
int count=0;
    
while(mystack.size()!=0)
    
{

        i
=mystack.top();
        mystack.pop();
        cout
<<i<<' ';
        count
++;
        
for(p=adj[i].next;p!=NULL;p=p->next)
        
{
            
int k=p->adjvex;
            indegree[k]
--;
            
if(indegree[k]==0)
                mystack.push(k);
        }

    }

    cout
<<endl;
    
if(count<n)cout<<"有回路"<<endl;
}




int main()
{
    
int n;
    
int m;
    cout
<<"请输入顶点数及边数:";
    cin
>>n>>m;
    Create(adj,n,m);
    cout
<<"输入的邻接表为:"<<endl;
    print(n);
    cout
<<"拓扑排序结果为:"<<endl;
    topsort(adj,n);
    system(
"pause");
    
return 0;
}


posted @ 2009-04-01 17:45 abilitytao 阅读(3717) | 评论 (2)编辑 收藏

数据结构作业之邻接表的插入和删除

/*张宏数据结构(第七章_图)作业:
题目描述:在有向图中
(1)增加一条弧  Addarc(adj,u,v)
(2)删除一条弧  Delarc(adj,u,v)
*/

#include
<iostream>
#include
<cmath>
#include
<cstdio>
#include
<algorithm>
#include
<string>
using namespace std;
#define MAX 1000000

struct node 
{
    
int adjvex;
    node
* next;
}
adj[MAX];

int Create(node adj[],int n,int m)//邻接表建表函数,n代表定点数,m代表边数
{
    
int i;
    node 
*p;
    
for(i=1;i<=n;i++)
    
{

        adj[i].adjvex
=i;
        adj[i].next
=NULL;
    }

    
for(i=1;i<=m;i++)
    
{
        cout
<<"请输入第"<<i<<"条边:";
        
int u,v;
        cin
>>u>>v;
        p
=new node;
        p
->adjvex=v;
        p
->next=adj[u].next;
        adj[u].next
=p;
    }

    
return 1;
}



int  Addnode(int u,int v)//此函数用于增加边
{

    node 
*p;
    p
=new node;
    p
->adjvex=v;
    p
->next=adj[u].next;
    adj[u].next
=p;
    
return 1;
}



int deletenode(int u,int v)//此函数用于边的删除
{

    node 
*P=adj[u].next;
    node 
*q=&adj[u];
    
while(P!=NULL)
    
{

        
if(P->adjvex==v)
        
{
            q
->next=P->next;
            delete P;
            
break;
        }


    }

    
return 1;
}


void print(int n)//邻接表打印函数
{
    
int i;
    node 
*p;
    
for(i=1;i<=n;i++)
    
{
        p
=&adj[i];
        
while(p!=NULL)
        
{
            cout
<<p->adjvex<<' ';
            p
=p->next;
        }

        cout
<<endl;
    }

}



int main()
{

    
int n;
    
int m;
    cout
<<"                         数据结构第七章(图)作业"<<endl;
    cout
<<"                                    "<<endl;
    cout
<<"题目描述:"<<endl;
    cout
<<"有向图中(1)增加一条弧  Addarc(adj,u,v)"<<endl;
    cout
<<"        (2)删除一条弧  Delarc(adj,u,v)"<<endl<<endl<<endl;
    cout
<<"请输入顶点的数目: ";
    cin
>>n;
    cout
<<"请输入邻边的数目: ";
    cin
>>m;
    Create(adj,n,m);
    cout
<<"输入的邻接表为:"<<endl;
    print(n);
    
int u,v;
    cout
<<"接下来执行添加操作,请输入边u,v(注意请不要和上表中的边重复):";
    cin
>>u>>v;
    Addnode(u,v);
    cout
<<"此时邻接表为:"<<endl;
    print(n);
    cout
<<"接下来执行删除操作,请输入边u,v:";
    cin
>>u>>v;
    deletenode(u,v);
    cout
<<"此时邻接表为:"<<endl;
    print(n);
    cout
<<"演示结束,谢谢您的使用"<<endl;
    
return 0;
}


posted @ 2009-03-30 21:27 abilitytao 阅读(1148) | 评论 (0)编辑 收藏

仅列出标题
共42页: First 32 33 34 35 36 37 38 39 40 Last