（C++）利用双向链表基本实现从邻接矩阵到邻接链表的转换-创新互联
#include#includeusing namespace std;
struct node {
int data;
node* next;
node* parent;
};
class Linkedlist
{
public:
Linkedlist(): head(NULL), last(NULL){}
bool isEmpty() { return isEmpty(head); };
void insertEnd(int data) { return insertEnd(head,last, data); }
void insertFirst(int data) { return insertFirst(head, last, data); };
void removeFirst() { removeFirst(head, last); };
void removeEnd() { removeEnd(head, last); };
void Preshow() { Preshow(head); };
void Aftershow() { Aftershow(last); }
node* Get_head() { return head; }
//输入数组创建链表
void createListfromArr(int arr[], int n) {
for (int i = 0; i< n; i++) {
insertEnd(head, last, arr[i]);
}
return;
}
private:
node* head;
node* last;
//判断是否为空
bool isEmpty(node* head) {
if (head == NULL)
return true;
else
return false;
}
void insertAsFistElement(node*& head, node*& last, int data) {
node* tmp = new node;
tmp->data = data;
tmp->next = NULL;
tmp->parent = NULL;
head = tmp;
last = tmp;
}
//在末尾添加数据
void insertEnd(node*& head, node*& last, int data) {
if (isEmpty(head))
insertAsFistElement(head, last, data);
else {
node* tmp = new node;
tmp->data = data;
tmp->next = NULL;
last->next = tmp;
tmp->parent = last;
last = tmp;
}
}
//在开始添加数据
void insertFirst(node*& head, node*& last, int data) {
if (isEmpty(head))
insertAsFistElement(head, last, data);
else {
node* tmp = new node;
tmp->data = data;
tmp->parent = NULL;
head->parent = tmp;
tmp->next = head;
head = tmp;
}
}
//删除最后一个数据。
void removeEnd(node*& head, node*& last) {
if (isEmpty(head))
cout<< "Empty link list!"<< endl;
else if (head == last) {
delete head;
head = NULL;
last = NULL;
}
else {
node* tmp = last;
last = last->parent;
last->next = NULL;
delete tmp;
}
}
//删除第一个数据。
void removeFirst(node*& head, node*& last) {
if (isEmpty(head))
cout<< "Empty link list!"<< endl;
else if (head == last) {
delete head;
head = NULL;
last = NULL;
}
else {
node* tmp = head;
head = head->next;
head->parent = NULL;
delete tmp;
}
}
//从头开始遍历
void Preshow(node* current) {
if (isEmpty(current))
cout<< "the list is empty!"<< endl;
else {
while (current != NULL) {
cout<< current->data<< "->";
current = current->next;
}
cout<< "NULL"<< endl;
}
}
//从尾开始遍历
void Aftershow(node* current) {
if (isEmpty(current))
cout<< "the list is empty!"<< endl;
else {
while (current != NULL) {
cout<< current->data<< "->";
current = current->parent;
}
cout<< "NULL"<< endl;
}
}
};
//输入邻接矩阵创建邻接链表：
void test03()
{
vector>Matrix; //接收输入的邻接矩阵
vectorMyVector; //目标得到的邻接链表
//接受维数：
int dim; cin >>dim;
//接收邻接矩阵：
for (int i = 0; i< dim; i++)
{
vectormatrix; //邻接矩阵的内部矩阵
for (int j = 0; j< dim; j++)
{
int num; cin >>num;
matrix.push_back(num);
}
Matrix.push_back(matrix);
}
//检测邻接矩阵
for (int i = 0; i< dim; i++)
{
for (int j = 0; j< dim; j++)
{
cout<< Matrix[i][j];
}
cout<< endl;
}
//建立并遍历邻接链表
for (int i = 0; i< dim; i++)
{
Linkedlist Mylist;
for (int j = 0; j< dim; j++)
{
if (Matrix[i][j] == 1)
{
Mylist.insertEnd(j + 1);
}
}
MyVector.push_back(Mylist.Get_head());
//遍历：
cout<< i+1<< ": ";
Mylist.Preshow();
cout<< endl;
}
}
int main() {
test03();
return 0;
}
输入：
9
0 1 1 1 0 0 0 0 0
1 0 0 0 1 1 0 0 0
1 0 0 1 0 0 0 1 0
1 0 1 0 0 0 0 1 1
0 1 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0输出：
011100000
100011000
100100010
101000011
010000100
010000000
000010000
001100000
000100000
1: 2->3->4->NULL
2: 1->5->6->NULL
3: 1->4->8->NULL
4: 1->3->8->9->NULL
5: 2->7->NULL
6: 2->NULL
7: 5->NULL
8: 3->4->NULL
9: 4->NULL你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页标题：（C++）利用双向链表基本实现从邻接矩阵到邻接链表的转换-创新互联
文章地址：http://myzitong.com/article/ddpsgd.html