圖的十字連結清單
圖的十字連結清單就是圖的鄰接表和逆鄰接表結合在一起的東西，比較友善在查找一個結點的出度和入度
采用的是數組加連結清單的形式，首先現在結點構造的數組中填入結點，然後在采用連結清單的方法在每個結點後面添加相應的邊。
邊就是兩個結點的組成的集合嘛。
那首先要構造兩個資料類型，一個是連結清單的，一個是數組的嘛；如下
數組的結構體定義如下：
這個就是由很多個單連結清單組成的。
基本思想如下：
首先要有一找尋頂點在數組中位置的函數。使用者輸入頂點數首先先初始化數組，然後使用者出入邊數，根據邊數來建立，使用者輸入一條邊的兩個頂點，通過函數找到位置，建立一個新的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;
}
測試用的圖如下：