《数据结构（C语言）》苏小红课本案例

期末了，赶紧复习一波，手打一份书上的代码以便随时查阅

第二章：

//顺序表存储结构

#define MAXSIZE 100

typedef struct

{

    Elemtype *elemt;

    int   length;

}Sqlist;

Status InitList(Sqlist &L)

{

    L.elemt=new Elemtype[MAXSIZE];

    if(!L.elemt) exit(OVERFLOW);

//    L.length=MAXQSIZE;

    L.length=0;

    return OK;

}

Status GetElemt(Sqlist &L,int i,Elemtype &e)

{

    if(i<1||i>L.length) return ERROR;

//    [错了]e=L->elemt[i];

    e=L->elemt[i-1];

    return OK;

}

Status LocateElem(Sqlist &L,Elemtype e)

{

    for(i=0;i<L.length;++i)

    {

        if(L.elemt[i]==e) return i+1;

    }

    return 0;

}

//Status SearchElemt(Sqlist &L,int &j,Elemtype e)

//{

//    if(j<1||j>L.length) return ERROR;

//    for(int i=0;i<L.length;++i)

//        if(L.elemt[i]==e)

//        {

//            j=i+1;

//            return OK;

//        }

//    return ERROR;

//}

Status ListInsert(Sqlist &L ,int i,Elemtype e)

{

    if(i<1||i>L.length) return ERROR;//忘记了

    if(L.length==MAXSIZE)return ERROR;//又忘记了

    for(j=L.length-1;j>=i-1;--j)

    {

        L.elemt[j+1]=L.elemt[j];

    }

    L.elemt[i-1]=e;

    L.length++;

    return OK;

}

Status ListDelete(Sqlist &L,int i)

{

    if(i<1||i>L.length) return ERROR;//忘了

//    for(j=i-1;j<L.length-1;++j)

//    {

//        L.elemt[j]=L.elemt[j+1];

//    }

    for(j=i;j<=L.length-1;++j)

        L.elemt[j-1]=L.elemt[j];

    L.length--;

    return OK;

}

//单链表的存储

typedef struct LNode

{

    ElemType data;

    struct LNode * next;

}LNode,*Linklist;

Status InitLink(Linklist &L)

{

    L=new LNode;

//    if(!L) exit(OVERFLOW);

    L->next=NULL;

    return OK;

}

//单链表的取值

Status GetElemt(Linklist &L,int i,Elemtype &e)

{

    p=L->next;

    j=1;

    while(p&&j<i)

    {

        p=p->next;++j;

    }

    if(!p||j>i) return ERROR;

    e=p->data;

    return OK;

}

//单链表的按值查找

LNode LocateElem(Linklist &L,Elemtype e)

{

    p=L->next;j=1;

//    while(p->data!=e)

//    {

//        p=p->next;

//    }

//    return p;

    while(p&&p->data!=e)

        p=p->next;

    return p;

}

//单链表的插入

Status ListInsert(Linklist &L,int i,Elemtype e)

{

//    p=L->next;j=1;

    p=L;j=0;

    while(p&&j<i-1)

    {

        p=p->next;++j;

    }

    if(!p||j>i-1) return ERROR;

    s=new LNode;

    s->data=e;

    s->next=p->next;

    p->next=s;

    return OK;

}

//删除

Status DeleteElemt(Linklist &L,int i)

{

    p=L;j=0;

    while(p->next&&j<i-1)

    {

        p=p->next;++j;

    }

    if(!p->next||j>i-1) return ERROR;

    s=p->next;

    p->next=s->next;

    delete s;

    return OK;

}

//单链表的创建--前插

void CreateList_H(Linklist &L,int n)

{

    L=new LNode;

    L->next=NULL;

    for(i=-0;i<n;++i)

    {

        p=new LNode;

        cin>>p->data;

        p->next=L->next;

        L->next=p;

    }

}

//单链表的创建——尾插

void CreateList_T(Linklist &L,int n)

{

    L=new LNode;

    L->next=NULL;

    r=L;

    for(i=0;i<n;i++)

    {

        p=new LNode;

        cin>>p->data;

        p->next=NULL;

        r->next=p;

        r=p;

    }

}

//双向链表

typedef struct DuLNode

{

    Elemtype data;

    struct DuLNode *ptr;

    struct DuLNode *next;

}DulNode,*DuLinkList;

//双向链表的插入

Status ListInsert_Dul(DuLinkList &L，int i,Elemtype e)

{

//    p=L;j=1;

//    while(p&&j<i-1)

//    {

//       p=p->next;++j;

//    }

//    if(!p||j>i-1) return ERROR;

//

//    s=new DulNode;

//    s->data=e;

//    s->next=p->next;

//    s->ptr=p->ptr;

//    p->next->ptr=s;

//    p->next=s;

    if(!(p=GetElem_Dul(L,i)))

        return ERROR;

    s=new LNode;

    s->data=e;

    s->ptr=p->ptr;

    s->next=p;

    p->ptr->next=s;

    p->ptr=s;

    return OK;

}

//双向链表的删除

Status ListDelete_Dul(Linklist &L,int i)

{

    if(!(p=GetElemt_Dul(L,i)))

        return ERROR;

    p->next->ptr=p->ptr;

    p->ptr->next=p->next;

    delete p;

    return OK;

}

　　第三章：

#define MAXSIZE

typedef struct

{

    SElemtTpye *base;

    SElemtTpye *top;

    int stacksize;

}SqStack ;

Status InitStack(SqStack &S)

{

    S.base=new SElemtTpye[MAXSIZE];

    // [危阻]if(!S.basa)return ERROR;

    if(!S.base) exit(OVERFLOW);

    S.top=S.base;

    S.stacksize=MAXSIZE;

    return OK;

}

Status Push(SqStack &S,SElemtTpye e)

{

    if(S.top-S.base==S.stacksize) return ERROR;

    *S.top=e;

    S.top++;

    // S.stacksize++;

    return OK;

}

Status Pop(SqStack &S,SElemtTpye &e)

{

    if(S.top==S.base) return ERROR;

    S.top--;

    e=*S.top;

    // S.stacksize--;

    return Ok;

}

SElemtTpye GetTop(SqStack &S)

{

    if(S.top==S.base) return ERROR;

    // S.top--;

    // return *S.top;

    return *(S.top-1);

}

//全媚

typedef struct StackNode

{

    struct StackNode *next;

    ElemtTpye data;

}StackNode,*LinkStack;

Status InitStack(LinkStack &S)

{

    S=NULL;

    return OK;

    // S=new StackNode;

    // if(!S) return ERROR;

    // S.next=NULL;

    // return OK;

}

Status Push(LinkStack &S,ElemtTpye e)

{

    p=new StackNode;

    if(!p) return ERROR;

    p->data=e;

    p->next=S;

    S=p;

    return OK;

}

Status Pop(LinkStack &S,ElemtTpye &e)

{

    if(!S)return ERROR;

    e=S.data;

    p=S;

    S=S->next;

    delete p;//梨芝瞥慧阻

    return OK;

}

ElemtTpye GetTop(LinkStack &S)

{

    if(!S) return ERROR;

    return S->data;

}

#define MAXQSIZE 100

typedef struct

{

    QElemtype *base;

    int front;

    int rear;

}SqQueue;

Status InitQueue(SqQueue &Q)

{

    Q.base=new QElemtype[MAXQSIZE];

    if(!Q.base) exit(OVERFLOW);

    Q.front=Q.rear=0;

    return OK;

}

Status EnQueue(SqQueue &Q,Elemtype e)

{

    if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;

    Q.base[Q.rear]=e;

    Q.rear=(Q.rear+1)%MAXQSIZE;

    return OK;

}

Status DeQueue(SqQueue &Q,Elemtype &e)

{

    if(Q.rear==Q.front) return ERROR;

    e=Q.base[Q.front];

    Q.front=(Q.front+1)%MAXQSIZE;

    return OK;

}

Elemtype GetTop(SqQueue &Q)

{

    if(Q.front==Q.base) return ERROR;

    return Q.base[Q.front];

}

//全錦

typedef struct QNode

{

    Elemtype data;

    struct QNode *next;

}QNode,*QueuePtr;

typedef struct

{

    QueuPtr front;

    QueuePtr rear;

}*LinkQueue;

Status InitQueue(LinkQueue &Q)

{

    Q.front=Q.rear=new QNode;

    Q.front->next=NULL;

    return OK;

}

Status EnQueue(LinkQueue &Q,Elemtype e)

{

    p=new QNode;

    p->data=e;

    p->next=NULL;

    Q.rear->next=p;

    Q.rear=p;

    return OK;

}

Status DeQueue(LinkQueue &Q,Elemtype &e)

{

    if(Q.front==Q.rear)return ERROR;

    p=Q.front->next;

    e=p->data;

    Q.front->next=p->next;

    if(p==Q.rear) Q.rear=Q.front;

    delete p;

    return OK;

}

　　第四章：

//串的顺序定义

#define MAXSIZE 100

typedef struct

{

    char ch[MAXSIZE];

    int length;

}SString;

//串的链式定义--完全没记住Orz

//typedef struct a

//{

//    char ch[MAXQSIZE];

//    int length;

//    struct a * next;

//}*c;

//typedef struct

//{

//    c

//}LString;

#define CHUNKSIZE 100

typedef struct Chunk

{

    char ch[CHUNKSIZE];

    struct Chunk * next;

}Chunk;

typedef struct

{

    Chunk *head,*tail;

    int length;

}LString;

第五章:

//二叉树的顺序存储结构

#define MAXTSIZE 100

typedef TElemtype SqBiTree[MAXSIZE];

SqBiTree Bt;

//二叉树的链式存储表示

typedef struct BiTNode

{

    Elemtype data;

    struct BiTNode * rchild,*lchrild;

}BiTNode,*BiTree;

//中序遍历的递归算法

void InOrderTraverse(BiTree &T)

{

    if(T)

    {

        InOrderTraverse(T->lchild);

        cout<<T->data;

        InOrderTraverse(T->rchild);

    }

}

//先序遍历的顺序建立二叉链表

void CreateBiTree(BiTree &T)

{

    cin>>ch;

    if(ch=='#')

    {

        T=NULL;

    }

    else

    {

        T=new BiNode;

        T->data=ch;

        CreateBiTree(T->lchild);

        CreateBiTree(T->rchild);

    }

}

//复制二叉树

void Copy(BiTree &T,Bi &NewT)

{

    if(!T)

    {

        NewT=NULL;

        return;

    }

    else

    {

        NewT=new BiNode;

        NewT->data=T->data;

        Copy(T->lchild,NewT->lchild);

        Copy(T->rchild,NewT->rchild);

    }

}

//计算二叉树深度

void Depth(BiTree &T)

{

    if(!T) return 0;

    else

    {

        m=Depth(T->lchild);

        n=Depth(T->rchild);

        if(m>n)

        {

            return m+1;

        }

        else

        {

            return n+1;

        }

    }

}

//统计二叉树结点个数

int NodeCount(BiTree &T)

{

    if(!T) return 0;

    else

    {

        return NodeCount(T->rchild)+NodeCount(T->lchild)+1;

    }

}

//二叉树的二叉线索存储表示

typedef struct BiThrNode

{

    Elemtype data;

    struct BiThrNode *lchild,*rchild;

    int ltag,rtag;

}BiThrNode,*BiThrTree;

//以节点p为根的子树中序线索化

//1代表是线索，0代表是子树

void InThreading(BiThrTree p)

{

    if(p)

    {

        InThreading(p->lchild);

        if(!p->lchild)

        {

            p->ltag=1;

            p->lchild=pre;

        }

        else

        {

            p->ltag=0;

        }

        if(!pre->rchild)

        {

            p->rtag=1;

            pre->rchild=p;

        }

        else

        {

            pre->rtag=0;

        }

        InThreading(p->rchild);

    }

}

//带头节点的二叉树中序线索化

void InOrderThread(BiThrTree &Thrt,BiTree T)

{

    Thrt=new BiThrNode;

    Thrt->ltag=0;

//    Thrt->lchild=T;

    Thrt->rtag=1;

    Thrt->rchild=Thrt;

    if(!T)

    {

        Thrt->lchild=Thrt;

    }

    else

    {

        Thrt->lchild=T;pre=Thr;

        InThreading(T);

        pre->rchild=Thrt;

        pre->rtag=1;

        Thrt->rchild=pre;//忘了

    }

}

//遍历中序线索二叉树

//输出左边->输出自己->输出右边

void InOrderTravese_Thr(BiThrTree &T)

{

    p=T->lchild;

    while(p!=T)

    {

        while(!p->ltag) p=p->lchild;

        cout<<p->data;//输出左边

        while(p->rchild&&p->rchild!=T)

        {

            p=p->rchild;

            cout<<p->data;//输出自己

        }

        p=p->rchild;//往右边走

    }

}

//————————哈夫曼树的存储结构

typedef struct

{

    int weight;

    int parent,lchild,rchild;

}HNode,*HuffmanTree;

//构造哈夫曼树

void CreateHuffmanTree(HuffmanTree &HT,int n)

{

    if(n<=1)return;

    m=2*n-1;

    HT=new HTNode[m+1];

    for(i=1;i<=m;++i)

    {

        HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;

    }

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

    {

        cin>>HT[i].weight;

    }

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

    {

        Select(HT,i-1,s1,s2);

        HT[i].lchild=s1;

        HT[i].rchild=s2;

        HT[s1].parent=i;

        HT[s2].p79d7;iiarent=i;

        HT[i].weight=HT[s1].weight+HT[s2].weight;

    }

}

//------------------哈夫曼编码表的存储表示

typedef char **HuffmanCode;

//根据哈夫曼树求哈夫曼编码

void CreateHuffmanNode(HuffmanTree HT,HuffmanCode &HC,int n)

{

    HC=new char*[n+1];

    cd =new char[n];

    cd[n-1]='\0';

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

    {

        start=n-1;

        c=i;f=HT[i].parent;

        while(!f)

        {

            start--;

            if(HT[f].lchild==c)cd[start]='0';

            else cd[start]='1';

            c=f;

            f=HT[f].parent;

        }

        HC[i]=new char[n-start];

        strcpy(H[i],&cd[start]);

    }

    delete cd;

}

　　第六章：

//#define MAXINT

//typedef struct

//{

//    ELemtype vertice[MAXQSIZE];

//    int arc[MAXSIZE][MAXSIZE];

//    int vernum,arcnum;

//}AMGraph;

#define MaxInt 32767    //表示极大值，即∞

#define MVNum 100         //最大顶点数

typedef char VerTexType;  //假设顶点的数据类型为字符型

typedef int ArcType;   //假设边的权值类型为整型

typedef struct

{

  VerTexType   vexs[MVNum];       		//顶点表

  ArcType      arcs[MVNum][MVNum];     //邻接矩阵

  int vexnum,arcnum;         		//图的当前点数和边数

}AMGraph;

//采用邻接矩阵表示法，创建无向网G

Status CreateUDN(AMGraph &G)

{

    cin>>G.vexnum>>G.arcnum; 	//输入总顶点数，总边数

    for(i = 0; i<G.vexnum; ++i)

      cin>>G.vexs[i];                        	//依次输入点的信息

    for(i = 0; i<G.vexnum;++i) 	//初始化邻接矩阵，边的权值均置为极大值

        for(j = 0; j<G.vexnum;++j)

            G.arcs[i][j] = MaxInt;

    for(k = 0; k<G.arcnum;++k)

    {                     //构造邻接矩阵

       cin>>v1>>v2>>w;   //输入一条边依附的顶点及权值

       i = LocateVex(G, v1);

       j = LocateVex(G, v2);  //确定v1和v2在G中的位置

       G.arcs[i][j] = w; //边<v1, v2>的权值置为w

       G.arcs[j][i] = G.arcs[i][j]; //置<v1, v2>的对称边<v2, v1>的权值为w

   }

   return OK;

}

 int LocateVex(MGraph G,VertexType u)

 { /* 初始条件:图G存在,u和G中顶点有相同特征 */

   /* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */

   int i;

   for(i=0;i<G.vexnum;++i)

     if(u==G.vexs[i])

       return i;

   return -1;

 }

///邻接表的存储表示

#define MVNum 100 //最大顶点数

typedef struct ArcNode{//边结点

    int adjvex; //该边所指向的顶点的位置

    struct ArcNode * nextarc;  	//指向下一条边的指针

    OtherInfo info;   //和边相关的信息

}ArcNode;

typedef struct VNode{

    VerTexType data;   	//顶点信息

    ArcNode * firstarc; 	//指向第一条依附该顶点的边的指针

}VNode, AdjList[MVNum];    //AdjList表示邻接表类型

typedef struct{

    AdjList vertices; 	//邻接表

    int vexnum, arcnum;  //图的当前顶点数和边数

}ALGraph;

　

///采用邻接表表示法，创建无向图G

Status CreateUDG(ALGraph &G){

　

　  cin>>G.vexnum>>G.arcnum;               	//输入总顶点数，总边数

    for(i = 0; i<G.vexnum; ++i){          	//输入各点，构造表头结点表

       cin>> G.vertices[i].data;           	//输入顶点值

       G.vertices[i].firstarc=NULL;       	//初始化表头结点的指针域为NULL

    }//for

    for(k = 0; k<G.arcnum;++k){        		//输入各边，构造邻接表

       cin>>v1>>v2;                 			//输入一条边依附的两个顶点

       i = LocateVex(G, v1);

       j = LocateVex(G, v2);

       p1=new ArcNode;               			//生成一个新的边结点*p1

　　   p1->adjvex=j;                   			//邻接点序号为j

　  　 p1->nextarc= G.vertices[i].firstarc;  G.vertices[i].firstarc=p1;

      //将新结点*p1插入顶点vi的边表头部

       p2=new ArcNode; //生成另一个对称的新的边结点*p2

　　   p2->adjvex=i;                   			//邻接点序号为i

　  　 p2->nextarc= G.vertices[j].firstarc;  G.vertices[j].firstarc=p2;

      //将新结点*p2插入顶点vj的边表头部

    }

    return OK;

}//CreateUDG

void DFS(Graph G, int v)

{

  cout<<v;

  visited[v] = true; //访问第v个顶点

  //依次检查邻接矩阵v所在的行

  for(w = FirstAdjVex(G,v);w>0; w=NextAdjVex(G,v,w))

    if(!visited[w])

      DFS(G, w);

   //w是v的邻接点，如果w未访问，则递归调用DFS

}

void DFS(AMGraph G, int v)

{

  cout<<v;

  visited[v] = true;  //访问第v个顶点

  for(w = 0;w<G.Vexnum;w++) //依次检查邻接矩阵v所在的行

    if((G.arcs[v][w]!=0)&&(!visited[w]))

        DFS(G, w);

   //w是v的邻接点，如果w未访问，则递归调用DFS

}

void DFS(ALGraph G, int v)

{        		//图G为邻接表类型

  cout<<v;

  visited[v] = true;  //访问第v个顶点

  p= G.vertices[v].firstarc;     //p指向v的边链表的第一个边结点

  while(p!=NULL)

  {   //边结点非空

      w=p->adjvex;               	//表示w是v的邻接点

      if(!visited[w])

        DFS(G, w); 	//如果w未访问，则递归调用DFS

      p=p->nextarc;                	//p指向下一个边结点

  }

}

void BFS (Graph G, int v)

{

    //按广度优先非递归遍历连通图G

    cout<<v;

    visited[v] = true;    	//访问第v个顶点

    InitQueue(Q);//辅助队列Q初始化，置空

    EnQueue(Q, v);//v进队

    while(!QueueEmpty(Q))

    {  //队列非空

       DeQueue(Q, u); //队头元素出队并置为u

       for(w = FirstAdjVex(G, u); w>=0; w = NextAdjVex(G, u, w))

            if(!visited[w])

            {   	//w为u的尚未访问的邻接顶点

                 cout<<w;

                 visited[w] = true;

                 EnQueue(Q, w); //w进队

            }//if

    }//while

}//BFS

void DFSTraverse(Graph G)

{

   // 对图 G 作深度优先遍历。

  for (v=0; v<G.vexnum; ++v)

     visited[v] = FALSE; // 访问标志数组初始化

  for (v=0; v<G.vexnum; ++v)

     if(!visited[v])

        DFS(G, v);

       // 对尚未访问的顶点调用DFS

}

///无向网G用邻接矩阵存储

///普里姆算法从顶点u出发构造的最小生成树

void MiniSpanTree_Prim(AMGraph G, VertexType u)

{

  k = LocateVex ( G, u ); //U的下标k

  for( j=0; j<G.vexnum; ++j )  // 辅助数组初始化

      if (j!=k) closedge[j] = { u, G.arcs[k][j] };

  closedge[k].lowcost = 0;      // 初始，U＝{u}

  for (i=1; i<G.vexnum; ++i)

  {

       k = Min(closedge);

       // 求出加入生成树的下一个顶点(k)

      printf(closedge[k].adjvex, G.vexs[k]);

     // 输出生成树上一条边

     closedge[k].lowcost = 0;    // 第k顶点并入U集

     for (j=0; j<G.vexnum; ++j)

          //修改其它顶点的最小边

        if (G.arcs[k][j] < closedge[j].lowcost)

          closedge[j] = { G.vexs[k], G.arcs[k][j]};

}

///克鲁斯卡尔（Kruscal）算法

struct

{

    VerTexType  Head;  //边的始点

    VerTexType  Tail;   // 边的终点

    ArcType lowcost;   // 边上的权值

}Edge[arcnum];

void MiniSpanTree_Kruskal(AMGraph  G)

{

    sort(Edge);

    for(i=0;i<G.Vexnum;i++)

        Vexset[i]=i;

    for(i=1;i<G.Vexnum;i++)

    {

        v1=LocateVex(G,Edge[i].Head);

        v2=LocateVex(G,Edge[i].Tail);

        vs1=Vexset[v1];

        vs2=Vexset[v2];

        if(vs1!=vs2)

        {

            cout<<Edge[i].Head<<Edge[i].Tail;

            for(i=0;i<G.Vexnum;i++)

                if(Vexset[i]==vs2)

                    Vexset[i]=vs1;

        }

    }

}

///用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径

void ShortestPath_DIJ(AMGraph G, int v0)

{

    n=G.vexnum; //n为G中顶点的个数

    for(v = 0; v<n; ++v)

    {  //n个顶点依次初始化

        S[v] = false; 	//S初始为空集

        D[v] = G.arcs[v0][v];   //将v0到各个终点的最短路径长度初始化

        if(D[v]< MaxInt)

            Path [v]=v0; //v0和v之间有弧，将v的前驱置为v0

        else

            Path [v]=-1;  //如果v0和v之间无弧，则将v的前驱置为-1

    }//for

    S[v0]=true; 	//将v0加入S

    D[v0]=0;  //源点到源点的距离为0

    /*―

        开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集

    ―*/

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

    { //对其余n−1个顶点，依次进行计算

        min= MaxInt;

        for(w=0;w<n; ++w)

            if(!S[w]&&D[w]<min)

            {

                v=w;

                min=D[w];

            }

        //选择一条当前的最短路径，终点为v

        S[v]=true; //将v加入S

        //更新从v0出发到集合V−S上所有顶点的最短路径长度

        for(w=0;w<n; ++w)

            if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])

            {

                D[w]=D[v]+G.arcs[v][w];//更新D[w]

                Path[w]=v; //更改w的前驱为v

            }//if

    }//for

}//ShortestPath_DIJ

///用Floyd算法求有向网G中各对顶点v和w之

///间的最短路径

Void ShortestPath_Floyed(AMGraph G)

{

    for(i=0;i<G.vexnum;++i)//各对结点之间初始已知路径及距离

        for(j=0;j<G.vexnum;++j)

        {

            D[i][j]=G.arcs[i][j];

            if(D[i][j]<MaxInt) path[i][j]=i;  //从v到w有直接路径

            else  path[i][j]=-1;

        }//for

    for(k=0;k<G.vexnum;++k)

        for(i=0;i<G.vexnum;++i)

            for(j=0;j<G.vexnum;++j)

                if(D[i][k]+D[k][j]<D[i][j])

                {

                    //从v经u到w的一条路径更短

                    D[i][j]=D[i][k]+D[k][j];

                    path[i][j]=path[k][j];

                }//if

}//ShortestPath_FLOYD

///拓扑排序AOV-网

//有向图G采用邻接表存储结构

//若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR。

Status TopologicalSort( ALGraph G , int top[])

{

    FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1]

    InitStack(S);

    for( i=0; i<G.vexnum; ++i)  //建零入度顶点栈S

        if(!indegree[i]) Push(S, i);//入度为零的顶点入栈

    count=0;   //对输出顶点计数

    while(!StackEmpty(S))

    {

        Pop(S, i);

        top[count]=i;

        ++count;

        for(p=G.vertices[i].Firstarc; p;  p=p->nextarc)

        {

            k=p->adjvex;  // 对i号顶点的每个邻接点的入度减一

            --indegree[k];

            if(!indegree[k]) Push(S,k); //若入度为零，则入栈

        }//for

    }//while

    if(count<G.vexnum )

        return ERROR;//该有向图有回路

    else

        return OK;

}//TopologicalSort

///拓扑排序

Status TopologicalOrder(ALGraph G,int topo[])

{

    FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1]，建零入度顶点栈S;

    InitStack(S);

    for(i=0;i<G.vexnum;++i)

        if(!indegree[i]) Push(S,i);

    m=0;

    while(!StackEmpty(S))

    {

        Pop(S, i);

        topo[m]=i;

        ++m;

        p=G.vertices[i].firstarc;

        while(p)

        {

            k=p->adjvex;  // 对j号顶点的每个邻接点的入度减1

            --indegree[k];

            if(indegree[k]==0)

                Push(S,k); //若入度减为零则入栈

            p=p->nextarc;

        }//for

    }//while

    if (m<G.vexnum )

        return ERROR;//该有向网有回路

    else

        return OK;

}//TopologicalOrder

///关键路径算法

Status CriticalPath(ALGraph  G)

{

    if(!TopologicalOrder(G,topo)) return ERROR;//有回路

    n=G.vexnum;

    for(i =0 ;i<n;++i) ve[i]=0;

    // /*求最早发生时间*/

    for(i=0;i<n;++i)

    {

        k=topo[i];

        p=G.vertices[k].firstarc;

        while(!p)

        {

            j=p->adjvex;

            if(ve[j]<ve[k]+p->weight)

                ve[j]=ve[k]+p->weight;

            p=p->nextarc;

        }

    }

    for(i=0;o<n;++i)

    {

        vl[i]=ve[n-1];

    }p;;

  // /*最晚发生时间*/

    for(i=n-1;i>=0;--i)

    {

        k=topo[i];

        p=G.vertices[k].firstarc;

        while(!p)

        {

            j=p->adjvex;

            if(vl[k]>vl[j]-p->weight)

                vl[k]=vl[j]-p->weight;

            p=p->nextarc;

        }

    }

    // /*判断每一活动是否为关键活动*/

    for(i=0;i<n;++i)

    {

        p=G.vertices[i].firstarc;

        while(!p)

        {

            j=p->adjvex;

            e=ve[i];

            l=vl[j]-p->weight;

            if(e==l)

                cout<<G.vertices[i].data<<G.vertices[j].data;

            p=p->nextarc;

        }

    }

}//CriticalPath

巴特西

《数据结构（C语言）》苏小红课本案例

第二章：

第三章：

第四章：

第五章:

第六章：

最新文章

热门文章

巴特西

《数据结构（C语言）》苏小红 课本案例

第二章：

第三章：

第四章：

第五章:

第六章：

最新文章

热门文章

《数据结构（C语言）》苏小红课本案例

　　第三章：

　　第四章：

　　第六章：