图的十字链表

图的十字链表就是图的邻接表和逆邻接表结合在一起的东西，比较方便在查找一个结点的出度和入度
</br>采用的是数组加链表的形式，首先现在结点构造的数组中填入结点，然后在采用链表的方法在每个结点后面添加相应的边。
边就是两个结点的组成的集合嘛。
&#8195那首先要构造两个数据类型，一个是链表的，一个是数组的嘛；如下

image.png

数组的结构体定义如下：

image.png

这个就是由很多个单链表组成的。

基本思想如下：

首先要有一找寻顶点在数组中位置的函数。用户输入顶点数首先先初始化数组，然后用户出入边数，根据边数来创建，用户输入一条边的两个顶点，通过函数找到位置，创建一个新的node，然后让node初始化node，连接，创建一个树，就好了。代码如下：

//  main.cpp
//  十字链表
//
//  Created by 橘子和香蕉 on 2018/11/24.
//  Copyright © 2018 橘子和香蕉. All rights reserved.
//
/*
在开发中遇到的问题：
1:在添加结点的时候，开始时候要查找结点在数组中的位置，若是没有那就添加，找结点位置函数返回值是-1；，我遇到的问题是在添加新结点的时候结点的位置没有更新这个结点在数组中的位置 ，讲-1添加进去了。
2删除结点中遇到的问题，首先要分为两个方面
  a：如果结点在第一个位置，怎么删除
  b：结点在不在第一个位置，怎么删除
删除其实就是单链表中的删除操作，用两个指针一个在前，一个在后的，遍历链表删除。
*/
#include <iostream>
using namespace std;
#define  MAXSIZE 100
#define dataType char
typedef struct node{
  int tail;//弧尾在数组中的位置
  int head;//弧首在数组中的位置
  node *tailNode;//以这个顶点为弧尾的下一条的位置
  node *headNode;//以这个顶点为弧头的下一天的位置
  int info;//权重
}node;
typedef struct Box{
  dataType data;
  node *in;//入度
  node *out;//出读
}Box;
class Graph{
private:
  Box base[MAXSIZE];
  int vertexNum;
  int edgeNum;
#pragma private mathod
  int locate(dataType x);//定位
public:
  void init(int vertexNum,int edgeNum);//初始化结点个数和边的个数
  void create();//创建图
  int indegree(dataType x);//入度
  int outdegree(dataType x);//出度
  void addEdge(dataType start,dataType end,int wieght);//添加一条边
  void deleteEdge(dataType start,dataType end);//删除一条边
  void printNode(dataType  data,bool isIn);
  void printBase();
};
#pragma 公有函数声明开始
void Graph::init(int vertexNum, int edgeNum){
  this->vertexNum = vertexNum;
  this->edgeNum = edgeNum;
}
int Graph::locate(dataType x){
  for (int i = 0; i<vertexNum; i++) {
      if(base[i].data == x){
          return I;
      }
  }
  return -1;
}
void Graph::create(){
  cout<<"input Graph node data \n";
  for (int i = 0; i<vertexNum; i++) {
      cin>>base[i].data;
      base[i].in = base[i].out = NULL;
  }
  cout<<"input Graph node Start  node and en node:\n";
  dataType start,end;
  int wieght;
  int startPosition,endPosition;
  node *p;
  
  for (int i = 0; i<edgeNum; i++) {
      cout<<"input edge start and end and wieght:\n";
      cin>>start>>end>>wieght;
      startPosition = locate(start);
      endPosition = locate(end);
      p = new node;
      p->info = wieght;
      p->tail = startPosition;
      p->head = endPosition;
      
      p->tailNode = base[startPosition].out;
      base[startPosition].out = p;
      p->headNode= base[endPosition].in;
      base[endPosition].in = p;
      
  }
  cout<<"create finish\n";
}
int  Graph::indegree(dataType x){
  int count = 0;
  node*p =base[ locate(x) ].in;
  while (p != NULL) {
      count++;
      p = p->headNode;
  }
  
  return count;
}
int Graph::outdegree(dataType x){
  int count = 0;
  node*p = base[locate(x)].out;
  while ( p != NULL) {
      count++;
      p = p->tailNode;
  }
  return count;
}
void  Graph::addEdge(dataType start, dataType end, int wieght){
  int startPosition = locate(start);
  int endPostion = locate(end);
  if(startPosition == -1){//返回值为-1，说明这个结点还没有在数组中，先是要添加，然后顶点数+1；边数+1；
      base[vertexNum].data = start;
      base[vertexNum].in = base[vertexNum].out = NULL;
      init(vertexNum+1, edgeNum+1);
  }
  if(endPostion == -1){
      base[vertexNum].data = end;
      base[vertexNum].in = base[vertexNum].out = NULL;
      init(vertexNum+1, edgeNum+1);
  }
  if(startPosition == -1 && endPostion == -1){
      //        两个顶点都没有在数组中，那添加之后顶点个数+2.边数+1；
      base[vertexNum].data = start;
      base[vertexNum].in = base[vertexNum].out = NULL;
      
      base[vertexNum].data = end;
      base[vertexNum].in = base[vertexNum].out = NULL;
      init(vertexNum+2, edgeNum+1);
  }
  
  node *p = new node;
  p->info = wieght;
  p->tail = startPosition;
  p->head = vertexNum-1;
 
  
  p->tailNode = base[startPosition].out;
  base[startPosition].out = p;
  p->headNode = base[endPostion].in;
  base[endPostion].in = p;
}

void Graph::deleteEdge(dataType  start , dataType end){
  int startPostion = locate(start);
  int endPostion = locate(end);
  if(startPostion == -1 || endPostion == -1){
      cout<<"can't not find edge\n";
      return;
  }
  node *nout = base[startPostion].out;
  node  *Hnout = base[startPostion].out;
  
 
  node *nin = base[endPostion].in;
  node *Hnin = base[endPostion].in;
  int num = 0;
  while (nout != NULL) {
      if(num == 0 && nout->tail == startPostion && nout->head == endPostion){
          base[startPostion].out = nout->tailNode;
          Hnout = nout;
          nout = nout->tailNode;
          continue;
      }
      if(nout->tail == startPostion && nout->head == endPostion){
          Hnout->tailNode = nout->tailNode;
          break;
      }
      num++;
      Hnout = nout;
      nout = nout->tailNode;
  }
  num=0;
  while (nin != NULL) {
     
      if(num == 0 && nin->tail == startPostion && nin->head  == endPostion){
          base[endPostion].in = nin->headNode;
          Hnin = nin;
          nin = nin->headNode;
          continue;
      }
      else if(nin->tail == startPostion && nin->head  == endPostion ){
          Hnin->headNode = nin->headNode;
          delete nin;
          break;
      }
      num++;
      Hnin = nin;
      nin = nin->headNode;
  }
  
}


void Graph::printNode(dataType data,bool isIn){
  cout<<"printNode++++++++++++++++++++++++++++++++\n";
  int position = locate(data);
  if(position == -1){
      cout<<"input error\n";
      return;
  }
  node *p = nullptr;
  isIn?(p = base[position].in):(base[position].out);
  while (p!= NULL) {
      cout<<"node start:"<<base[p->tail].data<<"\t"<<"node end"<<base[p->head].data<<"\t"<<"node weight:"<<p->info<<"\n";
      isIn? p = p->headNode:p = p->tailNode;
  }
  cout<<"printNode_________________________________\n";
}
void Graph::printBase(){
  cout<<"PrintBse +++++++++++++++++++++++++++++++++++++\n";
  for (int i = 0; i<vertexNum; i++) {
      cout<<"base:"<<base[i].data<<endl;
  }
  cout<<"vertexNum:"<<this->vertexNum<<endl;
  cout<<"edgeNum:"<<this->edgeNum<<endl;
  cout<<"PrintBse _____________________________________\n";
}


#pragma 公有函数声明结束
int main (){
  Graph h;
  h.init(4, 7);
  h.create();
  h.printBase();
  cout<<"入度"<< h.indegree('b')<<endl;
  cout<<"出度"<< h.outdegree('b')<<endl;
  h.printNode('b', true);
  h.addEdge('b', 'e', 1);
  cout<<"出度"<< h.outdegree('b')<<endl;
  h.deleteEdge('b', 'e');
  cout<<"出度"<< h.outdegree('b')<<endl;
  h.printBase();
  cout<<"入度"<< h.indegree('a')<<endl;
  cout<<"出度"<< h.outdegree('a')<<endl;
  h.deleteEdge('a', 'b');
  cout<<"出度"<<h.outdegree('a');
  cout<<"入度"<<h.indegree('b');
  return 1;
}

测试用的图如下：

image.png