2014华工复试笔试内容

 1 //public class DataStructure {
 2 //----------------------------------------------------------------------顺序队列    
 3     class Queue{
 4         /*判空：
 5               q.rear=q.front;
 6     
 7 **/
 8         /*入队：
 9               q.data[q.rear]=x;
10               q.rear=(q.rear+1)% Maxsize;
11     
12 **/
13         /*出队：
14               x=q.data[q.front];
15               q.front=(q.front+1)% Maxsize;
16     
17 **/
18         /*判满：
19               q.front==q.rear
20 **/
21     }
22     
23 //------------------------------------------------------------------求二叉树高度        
24     
25 /*        
26      Height(Bintree *T){
27 
28             int height1;
29             int height2;
30             if(T==null) return 0;
31             else{
32                     height1=Height(T->lchild);
33                     height2=Height(T->rchild);
34                     if(height1>height2) return (height1 +1);
35                     else{
36                             return (height2 +1);
37                     }
38             }
39         }
40 **/
41 
42 //----------------------------------------------------------------------十字链表    
43 
44     class ArcNode{
45 /*
46         #define MaxVertexNum 100;
47         //---------------------------------------
48         typedef struct ArcBox{
49              int tailvex,headvex;  //该弧的尾和头顶点的位置
50             struct ArcBox *hlink; //弧头相同的弧的链域
51             struct ArcBox *tlink;//弧尾相同的弧的链域
52                  InfoType *info; //该弧相关信息的指针 
53         }ArcNode;
54         
55         //---------------------------------------
56         typedef struct VexNode{
57                 VertexType data;
58                 ArcBox *firstin,*firstout;//分别指向该顶点第一条入弧和出弧
59         }VexNode;
60         //---------------------------------------
61         typedef struct{
62                 VexNode xlist[MaxVertexNum];//表头向量
63             int vexnum,arcnum;//有向图的当前顶点数和弧度
64         }OLGraph;
65             
66         Status CreateDG(OLGraph &G){
67                     scanf(&G.vexnum,&G.arcnum,&IncInfo);
68                     //IncInfo为0，则各弧不含其他信息
69                     for(int i=0;i<G.vexnum;++i){//构造表头向量
70             scanf(&G.xlist[i].data);//输入顶点值
71             G.xlist[i].firstin=NULL; G.xlist[i].firstout=NULL;
72                         //初始化指针
73                     }            
74                     for(k=0;k<G.arcnum;++k){//输入各弧并构造十字链表
75                         scanf(&v1,&v2);//输入一条弧的始点和终点
76                         i=LocateVex(G,v1); j=LocateVex(G,v2);
77                         //确定v1和v2在G中位置
78                         p=(ArcBox *)malloc(sizeof(ArcBox));//假设有足够空间
79                         *p={i,j,G.xlist[j].firstin,G.xlist[i].firstout,NULL}
80                              //对弧结点赋值
81                          //{tailvex,headvex,hlink,tlimk,info}
82 
83                         G.xlist[j].firstin=G.xlist[i].firstout=p;
84                         //完成在入弧和出弧链头的插入
85                         if(IncInfo) Innput(*p ->info);//若弧含有相关信息，则输入
86                     }
87         }//CreateDG
88     }
89  **/
90 }