데이터 구조 재 미 있 는 문제 - 동적 양 방향 링크 의 사용
12313 단어 데이터 구조
1: #include <stdio.h>
2: #include <stdlib.h>
3:
4: typedef struct node {
5: int data;
6: int freq;
7: struct node *prior;
8: struct node *next;
9: } dbLNode, *dbLinkList;
10:
11: /* , */
12: dbLinkList GreatdbLinkList(int n) {
13: dbLinkList p, r, list = NULL;
14: int e;
15: int i;
16: list = (dbLinkList)malloc(sizeof(dbLNode)); /* head, */
17: list->next = list->prior = NULL;
18:
19: for(i = 1; i <= n; i++) {
20: scanf("%d", &e);
21: p = (dbLinkList)malloc(sizeof(dbLNode));
22: p->data = e;
23: p->freq = 0;
24: p->next = NULL;
25: p->prior = NULL;
26:
27: if(!list->next) {
28: list->next = p; /* */
29: p->prior = list;
30: }
31: else {
32: r->next = p; /* */
33: p->prior = r;
34: }
35:
36: r = p;
37: }
38:
39: return list;
40: }
41:
42: /* , */
43: void visit(dbLinkList *l, int x) {
44: dbLinkList p = *l, q, r, s;
45: p = p->next; /*p */
46:
47: while(p->data != x && p != NULL)p = p->next;
48:
49: if(p == NULL) {
50: printf("Input error!
");
51: return;
52: }
53:
54: p->freq ++;
55: printf("Visiting this node
");
56:
57: while((p->prior) != *l && p->freq > p->prior->freq)
58: {
59:
60: /* */
61: q = p->prior;
62: r = p->next;
63: s = p->prior->prior;
64: p->prior = q->prior;
65: p->next = q;
66: q->prior = p;
67: q->next = r;
68: r->prior = q;
69: s->next = p;
70: }
71:
72: }
73:
74: void TransdbLinkList(dbLinkList l)
75: { /* , */
76: l = l->next;
77:
78: while(l != NULL) {
79: printf("(data:%d ,freq:%d)--> ", l->data, l->freq);
80: l = l->next;
81: }
82:
83: printf("X
");
84:
85: }
86:
87: int main()
88: {
89: dbLinkList l;
90: int d;
91: printf("Input five integer to creat a doubly link list
");
92: l = GreatdbLinkList(5);
93: TransdbLinkList(l);
94:
95: printf("Please input the data that you want to vist
");
96:
97: scanf("%d", &d);
98:
99: while(d != 0) {
100: visit(&l, d);
101: TransdbLinkList(l);
102: scanf("%d", &d);
103: }
104: return 0;
105: }
106: