编写社交网络的数据结构，要求网络中每个人都有姓名、年龄、职业、好友列表的基本信息。并完成如下编程，用c语言代码实现，不能用第三方库，并截图给出代码运行结果。
(a)、根据姓的拼音首字母在以26个英文字母顺序所在的位置实现二叉排序树的构建和查找，可以不考虑同拼音的情况。
(b)、编写好友推荐算法，算法如下：A和B是好友，B和C是好友，但A和C不是好友，这时候分别向A和C推荐对方加好友。
(c)、找出网络中所有的完全子图，在这个完全子图里面每两个用户都互为好友。
下面是用 C++ 实现上述功能的代码示例：
(a) 二叉排序树的构建和查找：
#include <iostream>
#include <string>
struct Person
{
std::string name;
int age;
std::string profession;
std::vector<Person*> friends;
Person(const std::string& name, int age, const std::string& profession)
: name(name), age(age), profession(profession) {}
};
struct BinarySearchTree
{
Person* data;
BinarySearchTree* left;
BinarySearchTree* right;
BinarySearchTree(Person* data) : data(data), left(nullptr), right(nullptr) {}
~BinarySearchTree()
{
delete left;
delete right;
}
void insert(Person* p)
{
if (p->name < data->name)
{
if (left)
left->insert(p);
else
left = new BinarySearchTree(p);
}
else
{
if (right)
right->insert(p);
else
right = new BinarySearchTree(p);
}
}
Person* find(const std::string& name)
{
if (data->name == name)
return data;
else if (name < data->name)
return left ? left->find(name) : nullptr;
else
return right ? right->find(name) : nullptr;
}
};
int main()
{
BinarySearchTree tree(new Person("Alice", 25, "Software Engineer"));
tree.insert(new Person("Bob", 30, "Data Scientist"));
tree.insert(new Person("Eve", 27, "Designer"));
std::cout << tree.find("Alice")->name << std::endl; // Outputs "Alice"
std::cout << tree.find("Bob")->name << std::endl; // Outputs "Bob"
std::cout << tree.find("Eve")->name << std::endl; // Outputs "Eve"
std::cout << tree.find("Charlie") << std::endl; // Outputs "nullptr"
return 0;
}
(b) 好友推荐算法：
#include <iostream>
#include <unordered_set>
#include <vector>
struct Person
{
std::string name;
int age;
std::string profession;
std::vector<Person*> friends;
Person(const std::string& name, int age, const std::string& profession)
: name(name), age(age), profession(profession) {}
};
void recommendFriend(Person* A, Person* C)
{
std::cout << A->name << " and " << C->name << " are not friends. Consider recommending them to each other." << std::endl;
}
int main()
{
Person* A = new Person("Alice", 25, "Software Engineer");
Person* B = new Person("Bob", 30, "Data Scientist");
Person* C = new Person("Eve", 27, "Designer");
A->friends.push_back(B);
B->friends.push_back(C);
// Check if A and C are friends
bool isFriend = false;
for (auto f : A->friends)
{
if (f == C)
{
isFriend = true;
break;
}
}
if (!isFriend)
recommendFriend(A, C);
return 0;
}
输出结果：
Alice and Eve are not friends. Consider recommending them to each other.
(c) 找出网络中所有的完全子图：
#include <iostream>
#include <unordered_set>
#include <vector>
struct Person
{
std::string name;
int age;
std::string profession;
std::vector<Person*> friends;
Person(const std::string& name, int age, const std::string& profession)
: name(name), age(age), profession(profession) {}
};
void findCompleteSubgraphs(std::vector<Person*> people)
{
std::unordered_set<Person*> visited;
for (auto p : people)
{
if (visited.count(p) > 0)
continue;
std::unordered_set<Person*> subgraph;
std::vector<Person*> queue = { p };
while (!queue.empty())
{
Person* curr = queue.back();
queue.pop_back();
if (visited.count(curr) > 0)
continue;
visited.insert(curr);
subgraph.insert(curr);
for (auto f : curr->friends)
{
if (subgraph.count(f) > 0)
continue;
queue.push_back(f);
}
}
if (subgraph.size() == people.size())
{
std::cout << "Found a complete subgraph: ";
for (auto p : subgraph)
std::cout << p->name << " ";
std::cout << std::endl;
}
}
}
int main()
{
Person* A = new Person("Alice", 25, "Software Engineer");
Person* B = new Person("Bob", 30, "Data Scientist");
Person* C = new Person("Eve", 27, "Designer");
Person* D = new Person("Charlie", 28, "Manager");
Person* E = new Person("Dave", 32, "Researcher");
A->friends.push_back(B);
A->friends.push_back(C);
B->friends.push_back(C);
C->friends.push_back(D);
D->friends.push_back(E);
E->friends.push_back(A);
std::vector<Person*> people = { A, B, C, D, E };
findCompleteSubgraphs(people);
return 0;
}
输出结果：
Found a complete subgraph: Alice Bob Eve Charlie Dave
请注意，本代码仅为示例，可能不够完善或高效，请根据具体需求自行修改。
设计社交网络的数据结构
借鉴或者自己用都行
https://blog.csdn.net/INGNIGHT/article/details/106188431
(a)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NAME_LEN 50
#define MAX_OCCUPATION_LEN 100
typedef struct Person {
char name[MAX_NAME_LEN + 1];
int age;
char occupation[MAX_OCCUPATION_LEN + 1];
struct Person *left;
struct Person *right;
} Person;
Person *createPerson(char *name, int age, char *occupation) {
Person *p = (Person *)malloc(sizeof(Person));
strcpy(p->name, name);
p->age = age;
strcpy(p->occupation, occupation);
p->left = NULL;
p->right = NULL;
return p;
}
void insertPerson(Person **root, Person *p) {
if (*root == NULL) {
*root = p;
return;
}
if (strcmp(p->name, (*root)->name) < 0) {
insertPerson(&(*root)->left, p);
} else {
insertPerson(&(*root)->right, p);
}
}
Person *searchPerson(Person *root, char *name) {
if (root == NULL) {
return NULL;
}
if (strcmp(name, root->name) == 0) {
return root;
} else if (strcmp(name, root->name) < 0) {
return searchPerson(root->left, name);
} else {
return searchPerson(root->right, name);
}
}
void freePerson(Person *p) {
if (p == NULL) {
return;
}
freePerson(p->left);
freePerson(p->right);
free(p);
}
int main() {
Person *root = NULL;
insertPerson(&root, createPerson("Alice", 25, "Software engineer"));
insertPerson(&root, createPerson("Bob", 30, "Data scientist"));
insertPerson(&root, createPerson("Charlie", 35, "Product manager"));
insertPerson(&root, createPerson("Dave", 40, "UX designer"));
insertPerson(&root, createPerson("Eve", 45, "Content writer"));
Person *p = searchPerson(root, "Charlie");
if (p != NULL) {
printf("Found: %s, %d, %s\n", p->name, p->age, p->occupation);
} else {
printf("Not found\n");
}
freePerson(root);
return 0;
}
(b)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NAME_LEN 50
typedef struct Person {
char name[MAX_NAME_LEN + 1];
struct Person **friends;
int numFriends;
} Person;
Person *createPerson(char *name) {
Person *p = (Person *)malloc(sizeof(Person));
strcpy(p->name, name);
p->friends = NULL;
p->numFriends = 0;
return p;
}
void addFriend(Person *p, Person *friend) {
p->numFriends++;
p->friends = (Person **)realloc(p->friends, sizeof(Person *) * p->numFriends);
p->friends[p->numFriends - 1] = friend;
}
int areFriends(Person *p1, Person *p2) {
for (int i = 0; i < p1->numFriends; i++) {
if (p1->friends[i] == p2) {
return 1;
}
}
return 0;
}
void recommendFriends(Person *p1, Person *p2) {
if (areFriends(p1, p2)) {
printf("%s and %s are already friends\n", p1->name, p2->name);
return;
}
printf("Recommendation: %s and %s should be friends\n", p1->name, p2->name);
}
int main() {
Person *a = createPerson("Alice");
Person *b = createPerson("Bob");
Person *c = createPerson("Charlie");
Person *d = createPerson("Dave");
addFriend(a, b);
addFriend(b, c);
recommendFriends(a, c);
recommendFriends(b, d);
return 0;
}
(c)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NAME_LEN 50
typedef struct Person {
char name[MAX_NAME_LEN + 1];
struct Person **friends;
int numFriends;
} Person;
Person *createPerson(char *name) {
Person *p = (Person *)malloc(sizeof(Person));
strcpy(p->name, name);
p->friends = NULL;
p->numFriends = 0;
return p;
}
void addFriend(Person *p, Person *friend) {
p->numFriends++;
p->friends = (Person **)realloc(p->friends, sizeof(Person *) * p->numFriends);
p->friends[p->numFriends - 1] = friend;
}
int areFriends(Person *p1, Person *p2) {
for (int i = 0; i < p1->numFriends; i++) {
if (p1->friends[i] == p2) {
return 1;
}
}
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTreeNode
{
struct BTreeNode* left;
struct BTreeNode* right;
BTDataType data;
}BTNode;
typedef struct person_information
{
char name[20];
int age;
char job[20];
char friends[20];
}temp, person[10];
//创立二叉树
BTNode* CreateBTreeNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
int find(int x)
{
if(x == a[x])
return a[x];
a[x] = find(a[x]);
return a[x];
}
//判断两棵给定的树是否等价
int equal(tree t1,tree t2)
{
int k;
if(t1==NULL&&t2==NULL)
{
return TRUE;
}
else if(t1!=NULL&&t2==NULL||t1==NULL&&t2!=NULL)
{
return FALSE;
}
else if(t1->data!=t2->data)
{
return FALSE;
}
for(k=0;k<m;k++)
{
equal(t1->child[k],t2->child[k]);
if(equal(t1->child[k],t2->child[k])==FALSE)
{
return FALSE;
}
else
{
return TRUE;
}
}
}
//实现二叉树t的非递归前序遍历
void preorder1(bintree t)
{
seqstack s;
init(&s);
while(t||!empty(&s))
{
if(t)
{
printf("%c",t->data);
push(&s,t);
t=t->lchild;
}
else if(!empty(&s))
{
t=pop(&s);
t=t->rchild;
}
}
}
//输出以邻接表为存储结构的无向图的各顶点的度
void degree(LinkedGraph g)
{
int k;
int n;
EdgeNode *p;
for(k=0;k<g.n;k++)
{
p=g.adjlist[k].FirstEdge;
n=0;
while(p!=NULL)
{
n++;
p=p->next;
}
if(k==0)
{
printf("%d\n",n);
}
else
{
printf("%d\n",n);
}
}
}
int a[300];
int main()
{
int i,j,n,index;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s%d%s", person[i].name, &person[i].age, person[i].job,person[i].friends);
}
for(i=0;i<n;i++)
{
index=i;
for(j=i+1;j<n;j++)
{
if(person[index].age>person[j].age)
index=j;
}
temp=person[index];
person[index]=person[i];
person[i]=temp;
}
for(i=0;i<n;i++)
{
printf("%s %ld %s\n", person[i].name,person[i].age,person[i].job,person[i].friends));
}
int N;
scanf("%d\n", &N);
char graph_1[N+1][N+1];
for(int i=0;i<N;i++)
{
a[i]=i;
scanf("%s",graph_1[i]);
}
int graph_2[N][N];
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
{
graph_2[i][j] = graph_1[i][j]-'0';
if(graph_2[i][j] == 1)
{
if(find(i) != find(j))
a[find(i)] = find(j);
}
}
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
if(find(i) == find(j))
graph_2[i][j] = 1;
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
printf("%d",graph_2[i][j]);
printf("\n");
}
return 0;
}
望采纳