c语言大作业, 链表写的最爽的一次(bushi
我只是想写一个邻接表而已，怎么用C语言实现就这么复杂捏
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 |
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> /*begin define node1*/ typedef struct _node { // 用于存输入数据 int data; struct _node *next; } node; node *makeNode(int d) { node *p = (node*)malloc(sizeof(struct _node)); p->data = d; p->next = NULL; return p; } void freeList(node *p) { if (p == NULL) return; freeList(p->next); free(p); } /*begin define node2*/ typedef struct _node2 { // 存组合中指向的两个节点 node *p1, *p2; struct _node2 *next; } node2; node2* makeNode2(node *p1, node *p2) { node2 *p = (node2*)malloc(sizeof(struct _node2)); p->p1 = p1; p->p2 = p2; p->next = NULL; return p; } void freeNode2list(node2 *p) { if (p == NULL) return; freeNode2list(p->next); free(p); } /*begin define node3*/ typedef struct _nodeofhead { // 实现邻接表 node2 *head; struct _nodeofhead *next; } node3; node3* makeNode3(node2 *h) { node3 *p = (node3*)malloc(sizeof(struct _nodeofhead)); p->head = h; p->next = NULL; return p; } void freeNode3list(node3 *p) { if (p == NULL) return; freeNode2list(p->head); freeNode3list(p->next); free(p); } node3* findInNode3(node3 *p, int key) { // 在邻接表中查找和相等的组合 for (node3* i = p; i; i = i->next) { int a = i->head->p1->data; int b = i->head->p2->data; if (a + b == key) return i; } return NULL; } int main() { /* 用邻接表实现,把和相同的组合存到一个邻接表中 读入数据的时候也存入一个数据链表 其中所有插入均使用头插法 */ node *headofdata = NULL; int n; scanf("%d", &n); for (int i = 0; i < n; ++ i) { int x; scanf("%d", &x); // add to head if (headofdata == NULL) headofdata = makeNode(x); else { node *t = makeNode(x); t->next = headofdata; headofdata = t; } } node3 *list = NULL; for (node *p1 = headofdata; p1; p1 = p1->next) { // 遍历数据链表 for (node *p2 = p1->next; p2; p2 = p2->next) { // 防止重复 int d1 = p1->data, d2 = p2->data; if (d1 == d2) continue; // 防止组合中出现相同的数 node3 *pos = findInNode3(list, d1 + d2); bool flag = false; if (pos) { // 防止组合中出现相同的数 for (node2 *i = pos->head; i && !flag; i = i->next) { int d = i->p1->data; if (d == d1 || d == d2) flag = true; } } if (flag) continue; // 将当前节点插入pos之后 if (pos == NULL) { // 找不到就要新开一个node3 if (list == NULL) { list = makeNode3(makeNode2(p1, p2)); } else { node3 *t = makeNode3(makeNode2(p1, p2)); t->next = list; list = t; } } else { // 找到了就直接插入 node2 *t = makeNode2(p1, p2); t->next = pos->head; pos->head = t; } } } // 输出 int cnt = 0; for (node3 *p = list; p; p = p->next) { if (p->head->next == NULL) continue; for (node2 *i = p->head; i; i = i->next) { printf("%d+%d", i->p1->data, i->p2->data); putchar(i->next ? '=': '\n'); } cnt ++; } printf("%d\n", cnt); // 释放链表 freeNode3list(list); freeList(headofdata); } |
发表回复