圖的十字鏈表

圖的十字鏈表

圖的十字鏈表就是圖的鄰接表和逆鄰接表結(jié)合在一起的東西，比較方便在查找一個(gè)結(jié)點(diǎn)的出度和入度
</br>采用的是數(shù)組加鏈表的形式，首先現(xiàn)在結(jié)點(diǎn)構(gòu)造的數(shù)組中填入結(jié)點(diǎn)，然后在采用鏈表的方法在每個(gè)結(jié)點(diǎn)后面添加相應(yīng)的邊。
邊就是兩個(gè)結(jié)點(diǎn)的組成的集合嘛。
&#8195那首先要構(gòu)造兩個(gè)數(shù)據(jù)類型，一個(gè)是鏈表的，一個(gè)是數(shù)組的嘛；如下

image.png

數(shù)組的結(jié)構(gòu)體定義如下：

image.png

這個(gè)就是由很多個(gè)單鏈表組成的。

基本思想如下：

首先要有一找尋頂點(diǎn)在數(shù)組中位置的函數(shù)。用戶輸入頂點(diǎn)數(shù)首先先初始化數(shù)組，然后用戶出入邊數(shù)，根據(jù)邊數(shù)來創(chuàng)建，用戶輸入一條邊的兩個(gè)頂點(diǎn)，通過函數(shù)找到位置，創(chuàng)建一個(gè)新的node，然后讓node初始化node，連接，創(chuàng)建一個(gè)樹，就好了。代碼如下：

//  main.cpp
//  十字鏈表
//
//  Created by 橘子和香蕉 on 2018/11/24.
//  Copyright ? 2018 橘子和香蕉. All rights reserved.
//
/*
在開發(fā)中遇到的問題：
1:在添加結(jié)點(diǎn)的時(shí)候，開始時(shí)候要查找結(jié)點(diǎn)在數(shù)組中的位置，若是沒有那就添加，找結(jié)點(diǎn)位置函數(shù)返回值是-1；，我遇到的問題是在添加新結(jié)點(diǎn)的時(shí)候結(jié)點(diǎn)的位置沒有更新這個(gè)結(jié)點(diǎn)在數(shù)組中的位置 ，講-1添加進(jìn)去了。
2刪除結(jié)點(diǎn)中遇到的問題，首先要分為兩個(gè)方面
  a：如果結(jié)點(diǎn)在第一個(gè)位置，怎么刪除
  b：結(jié)點(diǎn)在不在第一個(gè)位置，怎么刪除
刪除其實(shí)就是單鏈表中的刪除操作，用兩個(gè)指針一個(gè)在前，一個(gè)在后的，遍歷鏈表刪除。
*/
#include <iostream>
using namespace std;
#define  MAXSIZE 100
#define dataType char
typedef struct node{
  int tail;//弧尾在數(shù)組中的位置
  int head;//弧首在數(shù)組中的位置
  node *tailNode;//以這個(gè)頂點(diǎn)為弧尾的下一條的位置
  node *headNode;//以這個(gè)頂點(diǎn)為弧頭的下一天的位置
  int info;//權(quán)重
}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);//初始化結(jié)點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)
  void create();//創(chuàng)建圖
  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 公有函數(shù)聲明開始
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，說明這個(gè)結(jié)點(diǎn)還沒有在數(shù)組中，先是要添加，然后頂點(diǎn)數(shù)+1；邊數(shù)+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){
      //        兩個(gè)頂點(diǎn)都沒有在數(shù)組中，那添加之后頂點(diǎn)個(gè)數(shù)+2.邊數(shù)+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 公有函數(shù)聲明結(jié)束
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
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 一些概念 數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，而且確保經(jīng)過這...
    Winterfell_Z閱讀 6,607評(píng)論 0贊 13
  • 1. 圖的定義和基本術(shù)語 線性結(jié)構(gòu)中，元素僅有線性關(guān)系，每個(gè)元素只有一個(gè)直接前驅(qū)和直接后繼；樹形結(jié)構(gòu)中，數(shù)據(jù)元素（...
    yinxmm閱讀 5,673評(píng)論 0贊 3
  • 大部分內(nèi)容來自于《大話數(shù)據(jù)結(jié)構(gòu)》，代碼全部使用Swift實(shí)現(xiàn)。至于為什么抽風(fēng)寫這個(gè)？??你懂的。 1.線性表 線性表...
    一劍孤城閱讀 82,175評(píng)論 12贊 111
  • 1.每次刪除后面重復(fù)的元素 2.使用數(shù)組的indexOf()方法 3.觀察數(shù)組該元素是否是第一次出現(xiàn) 4.利用Ob...
    txwslyf閱讀 176評(píng)論 0贊 0
  • 1.檢查當(dāng)前安裝的PHP包 yum list installed | grep php 如果有安裝的PHP包，先刪...
    隨想的風(fēng)閱讀 985評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容