Sekyoro的博客小屋

数据结构试验

发表于 更新于 分类于
本文字数： 28k 阅读时长 ≈ 25 分钟

数据结构实验

数据实验写了

不过也忘得差不多了

人生艰难啊..

1.

image-20210530155126345

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
/*
**合并有序数组
*/


#include <stdio.h>
#include <stdlib.h>
typedef struct LinkedList
{
    int data;
    struct LinkedList *next;
} LinkedList, *pLinkedList;
void CreateLinkedList(pLinkedList, int);
void MergeList(pLinkedList, pLinkedList);
pLinkedList Initial(void);
int main(void)
{
    int size;
    pLinkedList pa, pb;
    pa = Initial();
    pb = Initial();
    printf("Enter the size of first LinkedList:\n");
    scanf("%d", &size);
    CreateLinkedList(pa, size);
    printf("Enter the size of second LinkedList:\n");
    scanf("%d", &size);
    CreateLinkedList(pb, size);
    MergeList(pa, pb);
    pa = pa->next;
    printf("the result is:\n");
    while (pa)
    {
        printf("%d\n", pa->data);
        pa = pa->next;
    }
    free(pa);
    free(pb);
    system("pause");
    return 0;
}
pLinkedList Initial(void)
{
    pLinkedList p = (pLinkedList)malloc(sizeof(LinkedList));
    p->next = NULL;
    return p;
}
void CreateLinkedList(pLinkedList p, int size)
{
    pLinkedList s, r;
    r = p;
    int num;
    printf("Enter the %d numbers:\n",size);
    while (size--)
    {
        scanf("%d", &num);
        s = (pLinkedList)malloc(sizeof(LinkedList));
        s->data = num;
        r->next = s;
        r = s;
    }
    r->next = NULL;
}
void MergeList(pLinkedList p, pLinkedList q)
{
    pLinkedList s, r;
    s = p;//s指针是作为整个归并的核心，它使得元素从小到大排序
    r = s->next;//q与r指针分别指向两个链表，随着排序的进行，后移
    q = q->next;
    while (r && q)
    {
        /**当一个链表中数据大于另一个链表
        **则指针s指向小元素值的节点，并使其后移，
        **然后指向较小元素值的指针后移*/
        if (r->data > q->data)
        {
            s->next = q;
            s = s->next;
            q = q->next;
        }
        /**当一个链表中数据小于另一个链表
        **道理类似，s指针指向小元素节点，并后移
        **然后指向较小元素的指针后移
        */
        else
        {

            s->next = r;
            s = s->next;
            r = r->next;
        }
    }
    /*链表p元素已取完，表明q还有未取元素
    **使s指针指向q
    */if (!r)
    {
        s->next = q;
    }
    //如果链表q元素取完,同理，使s指针指向还未取完元素的指针
    if (!q)
    {
        s->next = r;
    }
}

2.

image-20210530155212444

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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct DoubleNode
{
    int data;
    struct DoubleNode *next;
    struct DoubleNode *pre;
} DoubleNode, *pDoubleNode;

typedef struct DLinkList
{
    pDoubleNode head;
    pDoubleNode tail;
} DLinkList, *pDLinkList;
pDLinkList initial_node(void);
void Multi(pDLinkList, int);
void Div(pDLinkList, int);
void Add(pDLinkList, pDLinkList);
int terms(double);
int main(void)
{
    double prec;
    scanf("%lf", &prec);
    pDLinkList num ;
    pDLinkList sum ;
    num = initial_node();
    sum = initial_node();
    num->head->next->data = 2; //根据计算公式，第一项是2
    sum->head->next->data = 2;
    int t = terms(prec);
    for (int i = 1; i < t; i++)
    {

        Multi(num, i);
        Div(num, i);
        Add(num, sum);
    }
    pDoubleNode temp = sum->head->next->next;
    printf("3.");
    while (prec--)
    {
        printf("%d", temp->data);
        temp = temp->next;
    }
    return 0;
}
void Multi(pDLinkList L, int i) //乘法从尾部开始
{
    pDoubleNode tail = L->tail;
    int temp = 0;
    int ret = 0;
    while (L->head != tail)
    {
        temp = tail->data * i + ret;
        tail->data = temp % 10;
        ret = temp / 10;
        tail = tail->pre;
    }
}
void Div(pDLinkList L, int i) //除法从头部开始
{
    pDoubleNode head = L->head->next;//指向第一个有值的节点
    int temp = 0;
    int ret = 0;
    while (head != L->tail)
    {
        temp = head->data + ret * 10;
        head->data = temp / (2 * i + 1);
        ret = temp % (2 * i + 1);
        head = head->next;
    }
}
void Add(pDLinkList num, pDLinkList sum)
{
    int temp = 0;
    int ret = 0;
    pDoubleNode p = num->tail;
    pDoubleNode q = sum->tail;
    while (p != num->head)
    {
        temp = p->data + q->data + ret;
        q->data = temp % 10;
        ret = temp / 10;
        p = p->pre;
        q = q->pre;
    }
}
int terms(double n)
{
    double temp = 0;
    double sum = 0;
    int i = 0;
    for (i = 1; sum < n + 1; i++)
    {
        temp = (2 * i + 1) / i;
        temp = log10(temp);
        sum += temp;
    }
    return i;
}
pDLinkList initial_node(void)
{
    int num = 1000;
    pDLinkList L = (pDLinkList)malloc(sizeof(DLinkList));
    pDoubleNode s,r;
    L->head = (pDoubleNode)malloc(sizeof(DoubleNode));
    r = L->head;
    while (num--)
    {
        s = (pDoubleNode)malloc(sizeof(DoubleNode));
        s->data = 0;
        r->next = s;
        s->pre = r;
        L->head->pre = s;
        s->next = L->head;
        r = s; //r为尾指针    
    }
    L->tail = r;
    return L;
}

3.

image-20210530155312387

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
//快速转置
#include <stdio.h>
#include <stdlib.h>
#define maxsize 1000

typedef struct Triple
{
    int elem;
    int i, j;
} Triple;

typedef struct
{
    Triple data[maxsize];
    int row, col, len;
} TSMatrix;

void initial(TSMatrix *);
void Transpose(TSMatrix *, TSMatrix *);
void print(TSMatrix *);

int main(void)
{

    TSMatrix *M = (TSMatrix *)malloc(sizeof(TSMatrix));
    TSMatrix *N = (TSMatrix *)malloc(sizeof(TSMatrix));
    initial(M);
    Transpose(M, N);
    print(N);
    return 0;
}

void print(TSMatrix *result)
{
    for (int i = 0; i < result->len; i++)
    {
        printf("%d %d %d\n", result->data[i].i, result->data[i].j, result->data[i].elem);
    }
}
void Transpose(TSMatrix *M, TSMatrix *N)
{
    N->row = M->col;
    N->col = M->row;
    N->len = M->len;
    if (N->len)
    {
        int num[maxsize], cpos[maxsize];
        //num[col]表示col列非零元个数,
        //cpos[col]表示col列第一个非零元在转置后三元组表位置
        for (int i = 0; i <M->col; i++)
            num[i] = 0;

        for (int i = 0; i < M->len; i++)
            num[M->data[i].j]++;

        cpos[0] = 0;

        for (int i = 1; i < M->col; i++)
            cpos[i] = cpos[i - 1] + num[i - 1];

        int col, q;
        for (int i = 0; i < M->len; i++)
        {
            col = M->data[i].j; //M的三元组表第i个元素对应的列,即为转置后的行
            q = cpos[col];      //M第col列第一个非零元在转置后三元组表位置
            N->data[q].i = M->data[i].j;
            N->data[q].j = M->data[i].i;
            N->data[q].elem = M->data[i].elem;
            ++cpos[col]; //指向下个非零元
        }
    }
}
void initial(TSMatrix *M)
{
    int m, n;
    int r, c, element;
    scanf("%d %d", &m, &n);
    M->row = m;
    M->col = n;
    M->len = 0;
    while (scanf("%d %d %d",&r,&c,&element)&&(r!=0||c!=0||element!=0))
    {    
        M->data[M->len].i = r;
        M->data[M->len].j = c;
        M->data[M->len].elem = element;
        M->len++;
    }
}

4.

image-20210530155806685

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
#include <stdio.h>
#include <stdlib.h>
#define maxsize 101

typedef struct Tripe
{
    int data;
    int row;
    int col;
} Tripe;

typedef struct TSmatrix
{
    int num;
    int row,col;
    Tripe Element[maxsize];
} TSmatrix, *pTsmatrix;

void initial(pTsmatrix);
void add(pTsmatrix, pTsmatrix, pTsmatrix);
void print(pTsmatrix);

int main(void)
{
    pTsmatrix a = (pTsmatrix)malloc(sizeof(TSmatrix));
    pTsmatrix b = (pTsmatrix)malloc(sizeof(TSmatrix));
    pTsmatrix c = (pTsmatrix)malloc(sizeof(TSmatrix));
    int r,col;
    scanf("%d %d",&r,&col);
    a->row = b->row = c->row = r;
    a->col = b->col = c->col = col;
    scanf("%d %d", &a->num, &b->num);
    initial(a);
    initial(b);
    add(a, b, c);
    print(c);
    return 0;
}

void print(pTsmatrix result)
{
    for (int i = 1; i <= result->num; i++)
    {
        printf("%d %d %d\n", result->Element[i].row, result->Element[i].col, result->Element[i].data);
    }
}
void add(pTsmatrix a, pTsmatrix b, pTsmatrix c)
{
    int i = 1, j = 1;
    int k = 0;
    
    while ((i <= a->num) && (j <= b->num))
    {

        if ((a->Element[i].row == b->Element[j].row) && (a->Element[i].col == b->Element[j].col))
        {//两个非零元行相同列相同，则进行相加并判断值是否为0

            if ((a->Element[i].data + b->Element[j].data) == 0)
            {
                i++;
                j++;//值为0则不管，i,j递增
            }
            else
            {
                k++;
                c->Element[k].data = a->Element[i].data + b->Element[j].data;
                c->Element[k].row = a->Element[i].row;
                c->Element[k].col = a->Element[i].col;
                i++;
                j++;//值不为0,则赋值并递增i,j,k
            }
        }
        else if ((a->Element[i].row < b->Element[j].row) || (a->Element[i].row == b->Element[j].row && (a->Element[i].col < b->Element[j].col)))
        {//若a的非零元行数小于b的非零元,意味着c = a+0 则直接将a的值赋给c
        //后面同理，因为a元素对应在b矩阵处值为0
        //i,k递增
            k++;
            c->Element[k].row = a->Element[i].row;
            c->Element[k].col = a->Element[i].col;
            c->Element[k].data = a->Element[i].data;
            i++;
        }
        else
        {//剩下的情况就是b矩阵的值的位置对应在a矩阵中的值为0
        //即 c = 0+b
        //j,k递增
            k++;
            c->Element[k].row = b->Element[j].row;
            c->Element[k].col = b->Element[j].col;
            c->Element[k].data = b->Element[j].data;
            j++;
        }
    }
    while (i <= a->num)
    {//若a矩阵中还有未处理完的非零元，则直接加上
        k++;
        c->Element[k].row = a->Element[i].row;
        c->Element[k].col = a->Element[i].col;
        c->Element[k].data = a->Element[i].data;
        i++;
    }
    while (j <= b->num)
    {//道理同上,b矩阵的值直接赋给c
        k++;
        c->Element[k].row = b->Element[j].row;
        c->Element[k].col = b->Element[j].col;
        c->Element[k].data = b->Element[j].data;
        j++;
    }
    c->num = k;
}

void initial(pTsmatrix p)
{

    for (int i = 1; i <= p->num; i++)
    {
        scanf("%d %d %d", &p->Element[i].row, &p->Element[i].col, &p->Element[i].data);
    }
}

5.

image-20210530155750904

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <stdio.h>
#include <stdlib.h>

typedef struct OLNode
{
    int i, j, e;
    struct OLNode *down, *right;
} OLNode, *OLlink;

typedef struct
{
    OLlink *rhead, *chead; //指向行或列第一个非零元(指向结构体的指针),可以用数组rhead[row]表示第row行的数据
    int m, n, len;         //行列数,非零元个数
} CrossList;

void initial(CrossList *);
void plus(CrossList *, CrossList *);
void print(CrossList *);
void Insert(CrossList *, OLlink, OLlink, OLlink *, OLlink *);
void add(CrossList *, OLlink, OLlink, OLlink *, OLlink *);

int main(void)
{
    CrossList *M = (CrossList *)malloc(sizeof(CrossList));
    CrossList *N = (CrossList *)malloc(sizeof(CrossList));
    scanf("%d %d", &M->m, &M->n);
    N->m = M->m;
    N->n = M->n;
    scanf("%d %d", &M->len, &N->len);
    initial(M);
    initial(N);
    plus(M, N);
    print(M);
    return 0;
}

void print(CrossList *M)
{
    for (int row = 1; row <= M->m; row++)
    {
        OLlink pa = M->rhead[row];
        while (pa)
        {
            printf("%d %d %d\n", pa->i, pa->j, pa->e);
            pa = pa->right;
        }
    }
}

void plus(CrossList *M, CrossList *N)
{
    OLlink pa, pb;
    OLlink pre; //指向前面一个节点,方便插入
    OLlink *hl = (OLlink *)malloc((M->n + 1) * sizeof(OLlink));

    for (int j = 1; j <= M->n; j++)
        hl[j] = M->chead[j]; //hl[]表示的是每列非零元的pre指向元素，与pre类似

    for (int row = 1; row <= M->m; row++) //行遍历
    {
        pa = M->rhead[row];
        pb = N->rhead[row];
        pre = NULL;
        while (pb) //当pb有非零元素时进行处理
        {
            if (pa == NULL || pa->j > pb->j)
            {

                Insert(M, pa, pb, &pre, hl);
                pb = pb->right;
            }
            else if (pa != NULL && pa->j < pb->j)
            {
                pre = pa;
                pa = pa->right;
            }
            else if (pa->j == pb->j)
            {
                add(M, pa, pb, &pre, hl);
                pb = pb->right;
            }
        }
    }
}

void add(CrossList *M, OLlink pa, OLlink pb, OLlink *pre, OLlink *hl)
{

    int data = pa->e + pb->e;
    if (data)
    {
        pa->e = data;
    }
    else
    {
        OLlink temp = (OLlink)malloc(sizeof(OLNode));
        if ((*pre) == NULL)
            M->rhead[pa->i] = pa->right;
        else
        {
            (*pre)->right = pa->right;
        }
        temp = pa;
        pa = pa->right;
        if (M->chead[temp->j] == temp)
            M->chead[temp->j] = hl[temp->j] = temp->down;
        else
            hl[temp->j]->down = temp->down;
        free(temp);
    }
}

void Insert(CrossList *M, OLlink pa, OLlink pb, OLlink *pre, OLlink *hl) //插入有两种情况，一种是pa该行无非零元素，另一种pb所在列小于pa所在列
{
    OLlink p = (OLlink)malloc(sizeof(OLNode));
    p->i = pb->i;
    p->j = pb->j;
    p->e = pb->e;
    p->down = p->right = NULL;
    if ((*pre) == NULL)
    {
        M->rhead[p->i] = p;
      
    }
    else
    {
        (*pre)->right = p;
      
    }
    p->right = pa;
    
    (*pre) = p;
   // pa = (*pre)->right;//这一句可以不要
    if (!M->chead[p->j] || M->chead[p->j]->i > p->i)
    {
        p->down = M->chead[p->j];
        M->chead[p->j] = p;
    }
    else
    {
        p->down = hl[p->j]->down;
        hl[p->j]->down = p;
    }
    hl[p->j] = p;
   
}
void initial(CrossList *Clist)
{
    int i, j, e;
    Clist->rhead = (OLlink *)malloc((Clist->m + 1) * sizeof(OLlink));
    Clist->chead = (OLlink *)malloc((Clist->n + 1) * sizeof(OLlink));
    // if(rhead||chead)
    // exit(1);
    for (int i = 1; i <= Clist->m; i++)
        Clist->rhead[i] = NULL;
    for (int i = 1; i <= Clist->n; i++)
        Clist->chead[i] = NULL;
    OLlink s = (OLlink)malloc(sizeof(OLNode));
    for (int count = 0; count < Clist->len; count++)
    {
        OLlink cur = (OLlink)malloc(sizeof(OLNode));
        cur->down = NULL;
        cur->right = NULL;
        // if(cur==NULL)
        // exit(1);
        scanf("%d %d %d", &i, &j, &e);
        cur->i = i;
        cur->j = j;
        cur->e = e;
        if (Clist->rhead[i] == NULL)
        {
            Clist->rhead[i] = cur;
        }
        else
        {
            s = Clist->rhead[i];
            while (s->right != NULL && s->right->j < j)
                s = s->right;
            cur->right = s->right;
            s->right = cur;
        }
        if (Clist->chead[j] == NULL)
            Clist->chead[j] = cur;
        else
        {
            s = Clist->chead[j];
            while (s->down != NULL && s->down->i < i)
                s = s->down;
            cur->down = s->down;
            s->down = cur;
        }
    }
}

6.

image-20210530155731455

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
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAXSIZE 1000 //非零元个数
#define MAXRs 500    //矩阵最大行数
typedef struct Triple
{
    int row, col;
    int elem;
} Triple;

typedef struct RLSMatrix
{
    Triple data[MAXSIZE];
    int rpos[MAXRs]; //第row行第一个非零元在结果三元组中的位置
    int mu, nu, tu;  //分别表示行数,列数非零元个数
} RLSMatrix;

void Multi(RLSMatrix *, RLSMatrix *, RLSMatrix *);
void initial(RLSMatrix *);
void print(RLSMatrix *);

int main(void)
{
    RLSMatrix *M = (RLSMatrix *)malloc(sizeof(RLSMatrix));
    RLSMatrix *N = (RLSMatrix *)malloc(sizeof(RLSMatrix));
    RLSMatrix *result = (RLSMatrix *)malloc(sizeof(RLSMatrix));
    initial(M);
    initial(N);
    Multi(M, N, result);
    print(result);
    return 0;
}
void print(RLSMatrix* result)
{
    for(int i = 1;i<=result->tu;i++)
    {
        printf("%d %d %d\n",result->data[i].row,result->data[i].col,result->data[i].elem);
    }
}
void Multi(RLSMatrix *M, RLSMatrix *N, RLSMatrix *Q)
{
    int arow, brow; //M,N矩阵的row
    int ccol;       //Q结果矩阵的col
    int ctemp[MAXSIZE] = {0};
    // if(M->mu!=N->nu)
    // exit(1);
    Q->mu = M->mu;
    Q->nu = N->nu;
    Q->tu = 0;
    if (M->tu && N->tu)
    {
        for (arow = 1; arow <= M->mu; arow++)//对于M的每一行,根据行数确定三元组表取值范围(p)
        {
            memset(ctemp,0,(N->nu+1)*(sizeof(int)));
            Q->rpos[arow] = Q->tu+1;//每一行第一个非零元在三元组的位置是此时的非零元个数+1
            for (int p = M->rpos[arow]; p < M->rpos[arow + 1]; p++)//对于每一行的各个元素,取其列
            {
                brow = M->data[p].col;//列为N所对应的行数
                for (int q = N->rpos[brow]; q < N->rpos[brow + 1]; q++)
                {
                    ccol = N->data[q].col;//取得ccol为结果矩阵元素对应的列数
                    ctemp[ccol] += M->data[p].elem * N->data[q].elem;
                }
            }
            for (ccol = 1; ccol <= Q->nu; ++ccol)//对于每一列
            {
                if (ctemp[ccol])
                {
                    Q->tu++;
                    Q->data[Q->tu].row = arow;
                    Q->data[Q->tu].col = ccol;
                    Q->data[Q->tu].elem = ctemp[ccol];
                    
                }
            }
        }
    }
}
void initial(RLSMatrix *M)
{
    scanf("%d %d", &M->mu, &M->nu);
    int i, j, e;
    int count = 1;
    while (scanf("%d %d %d", &i, &j, &e) && (i != 0 || j != 0 || e != 0))
    {
        M->data[count].row = i;
        M->data[count].col = j;
        M->data[count].elem = e;
        count++;
    }
    M->tu = count-1;
    int num[MAXSIZE] = {0}; 
    for(int i = 1;i<=M->tu;i++)
    {
        num[M->data[i].row]++;
    }
    M->rpos[1] = 1;
    for(int i = 2;i<=M->mu;i++)
    M->rpos[i] = M->rpos[i-1]+num[i-1];
    M->rpos[M->mu+1] = M->tu+1; 
}

7.

image-20210530155715476

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 100
#define M (2 * N - 1)

typedef char *HuffmanCode[N + 1];
typedef struct
{
    int weight; //权值
    int parent; //父节点在ht数组中的位置
    int Lchild; //左孩子在ht数组中的位置
    int Rchild; //右孩子在ht数组中的位置
    char c;     //字符
} HTNode, HuffmanTree[M + 1];

void CrtHuffmanTree(HuffmanTree, int);       //构造哈夫曼树
void select(HuffmanTree, int, int *, int *); //用于寻找最小的两个值
//hc[N+1]为相应节点的编码
void CrtHuffmanCode(HuffmanTree, HuffmanCode, int); //根据哈夫曼树得到相应编码
//解码得到明文
void decode(HuffmanTree, HuffmanCode, int, char *);
//编码得到二进制串
void encode(HuffmanTree, HuffmanCode, int, char *);
//根据HuffmanTree得到HuffmanCode
//HuffmanCode储存的是每个字符对应的编码
void test(HuffmanTree ht, int n)
{
    int weight_[N + 1];
    for (int i = 1; i <= n; i++)
        scanf("%d", &weight_[i]); //输入n个叶子节点的权值
    for (int i = 1; i <= n; i++)
    {
        ht[i].weight = weight_[i];
        ht[i].parent = ht[i].Rchild = ht[i].Lchild = 0;
    }
    for (int i = 1; i <= n; i++)
        printf("%d\n", ht[i].weight);
}
int main(void)
{
    int size;
    scanf("%d", &size);
    getchar();
    HuffmanTree ht;
    for (int i = 1; i <= size; i++)
    {
        scanf("%c", &ht[i].c); //输入n个叶子节点的字符
        getchar();
    }
    CrtHuffmanTree(ht, size);
    HuffmanCode hc;
    CrtHuffmanCode(ht, hc, size);
    //  test(ht,size);
    char encoding_text[100] = {'\0'};
    encode(ht, hc, size, encoding_text);
    decode(ht, hc, size, encoding_text);
    return 0;
}

void CrtHuffmanTree(HuffmanTree ht, int n)
{
    // int w[N + 1];
    // for (int i = 1; i <= n; i++)
    //     scanf("%d", &w[i]); //输入n个叶子节点的权值
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &ht[i].weight); //输入n个叶子节点的权值
        ht[i].parent = ht[i].Rchild = ht[i].Lchild = 0;
    }
    int m = 2 * n - 1;
    for (int i = n + 1; i <= m; i++)
    {
        ht[i].weight = 0;
        ht[i].parent = ht[i].Rchild = ht[i].Lchild = 0;
    }
    int s1, s2; //s1,s2为两个值最小的无父结点
    for (int i = n + 1; i <= m; i++)
    {
        select(ht, i - 1, &s1, &s2);
        ht[i].weight = ht[s1].weight + ht[s2].weight;
        ht[s1].parent = ht[s2].parent = i;
        ht[i].Lchild = s1;
        ht[i].Rchild = s2;
    }
}
void select(HuffmanTree ht, int n, int *s1, int *s2)
{
    int min_1_w = 10000; //用来找最小值
    int min_2_w = 10000; //用来找最小值
    int min;
    for (int i = 1; i <= n; i++)
    {
        if (ht[i].parent == 0)
        {
            if (ht[i].weight < min_1_w)
            {
                min_1_w = ht[i].weight;
                min = i;
            }
        }
    } //找到第一个最小值
    *s1 = min;
    for (int j = 1; j <= n; j++)
    {
        if (ht[j].parent == 0)
        {
            if (j != *s1 && ht[j].weight < min_2_w) //倒数第二小的值大于等于最小的值,小于其余值
            {
                min_2_w = ht[j].weight;
                min = j;
            }
        }
    } //最小的第二个值
    *s2 = min;
}
void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n) //建立好哈夫曼树后,得到哈夫曼编码
{
    char *cd;                              //cd是指向字符的指针,用来存储字符串
    cd = (char *)malloc(n * sizeof(char)); //开辟n个单元,因为共有n个结点,最多只有n-1个编码位
    cd[n - 1] = '\0';                      //因为存储字符串,最后一位为空字符
    int start, c;                          //start为cd数组开始存储的起点,c用来标记每次往上找到的双亲的位置
    int p;                                 //p为双亲的位置
    for (int i = 1; i <= n; i++)
    {
        start = n - 1;    //这是cd数组的最后一位,是'/0'，因为储存字符串
        c = i;            //c为第一个结点,得到第一个结点的编码
        p = ht[i].parent; //寻找结点父亲
        while (p)         //若有父亲结点
        {
            --start;               //每次递减,从后向前得到编码
            if (ht[p].Lchild == c) //若子节点为左孩子,则为0
                cd[start] = '0';
            else
                cd[start] = '1';
            c = p;
            p = ht[p].parent;
        }
        /*
        while循环可改为
        for(c=i,p=ht[i].parent;p!=0;c=p,p=ht[p].parent)
        {
             --start;
            if (ht[p].Lchild == c)
                cd[start] = '0';
            else
                cd[start] = '1';
            c = p;
        }
        */
        hc[i] = (char *)malloc((n - start) * sizeof(char)); //为hc[i]分配空间,空间大小为编码的位数+1,最后一位为'\0'
        strcpy(hc[i], &cd[start]);                          //注意这里取地址符不可以去掉,因为本身cd是一个数组(指针),但复制时应该从start开始,所以取数组start位的元素地址
                                                            //   printf("%d:%s\n",i,hc[i]);//hc 存储的是n个字符分别的编码
    }
    free(cd);
}
void decode(HuffmanTree ht, HuffmanCode hc, int n, char *encoding_text)
{
    char *text = (char *)malloc(n * sizeof(char));
    memset(text, '\0', sizeof(text));
    int pos = 0;
    int t_pos = 0;
    while (encoding_text[pos] != '\0')
    {
        text[t_pos++] = encoding_text[pos++];
        for (int i = 1; i <= n; i++)
        {
            if (strcmp(text, hc[i])==0)
            {
                printf("%c", ht[i].c);
                memset(text, '\0', n * sizeof(char));
                t_pos = 0;
                break;
            }
            // else
            // {
            //     text[t_pos++] = encoding_text[pos++];

            // }
        }
       // text[t_pos++] = encoding_text[pos++];
    }
    printf("\n");
}
void encode(HuffmanTree ht, HuffmanCode hc, int n, char *encoding_text)
{
    //得到了哈夫曼编码,因为知道了每个字符相应的编码,解码就很简单了
    //进行编码
    getchar();
    char text[1000]; //进行编码的文本
    fgets(text, 1000, stdin);
    char c;
    for (int i = 0; text[i] != '\0'; i++)
    {
        c = text[i];
        for (int j = 1; j <= n; j++)
        {
            if (ht[j].c == c)
            {
                printf("%s", hc[j]);
                strcat(encoding_text, hc[j]);
            }
        }
    }
    printf("\n");
}

8.

image-20210530155656921

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
#include <stdio.h>
#include <stdlib.h>
#define MAX_Node 100

typedef struct
{
    int vex[MAX_Node];            //顶点信息
    int arcs[MAX_Node][MAX_Node]; //权值  邻接矩阵信息
    int arccount, vexcount;       //顶点个数,边的个数
} Graph, *PGraph;

void initial(PGraph);
void find_minpath(PGraph);
void output(PGraph);

int main(void)
{

    PGraph g = (PGraph)malloc(sizeof(Graph));
    initial(g);
    find_minpath(g);
    output(g);
    free(g);
    return 0;
}
void output(PGraph g)
{
    for(int i = 0;i<g->vexcount;i++)
    {
        printf("%d\n",g->arcs[0][i]);

    }

}

void find_minpath(PGraph g)
{
    //记录节点是否已经判断过
    //1表示判断过
    int visited[MAX_Node];
    //记录0到各节点的最短路径
    int dist[MAX_Node];
    int min;

    int flag;//标记
    //初始化
    for (int i = 0; i < g->vexcount; i++)
    {
        visited[i] = 0;          //初始化,未判断
        dist[i] = g->arcs[0][i]; //初始化距离
    }

    visited[0] = 1; //初始节点置为判断

    for (int i = 1; i < g->vexcount; i++)
    {
        min = 10000;//最大值

        for (int j = 0; j < g->vexcount; j++)//遍历每个节点
        {
            if (visited[j] == 0)//未判断,即没有在集合中，尚未处理
            {
                if (dist[j] < min)//不是最大值min
                {
                    flag = j; //如果距离比MIN小,则j为中间路径,更新
                    min = dist[j];
                }
            }
        }
            visited[flag] = 1;//置为判断

            //更新路径
            for (int j = 0; j < g->vexcount; j++)
            {
                if (visited[j] == 0 && (min + g->arcs[flag][j] < dist[j]))
                {
                    dist[j] = min + g->arcs[flag][j];
                }
            }
        }
    
    for(int i = 0;i<g->vexcount;i++)
    {
        g->arcs[0][i] = dist[i];
    }
}
void initial(PGraph g)
{
    scanf("%d", &g->vexcount);

    for (int i = 0; i < g->vexcount; i++)
    {

        for (int j = 0; j < g->vexcount; j++)
        {
            scanf("%d", &g->arcs[i][j]);
        }
    }
}

9.

image-20210530155639357

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
#include <stdio.h>
#include <stdlib.h>
#define MAX_Node 100



typedef struct
{
    int vex[MAX_Node];            //顶点信息
    int arcs[MAX_Node][MAX_Node]; //权值  邻接矩阵信息
    int arccount, vexcount;       //顶点个数,边的个数
} Graph, *PGraph;

void initial(PGraph);
void find_minpath(PGraph,int[]);
void output(PGraph, int[]);

int x, y;//从x到y的最短路径

int main(void)
{

    int way[MAX_Node];
    PGraph g = (PGraph)malloc(sizeof(Graph));
    initial(g);
    find_minpath(g,way);
    output(g,way);
    free(g);
    return 0;
}
void output(PGraph g, int way[])
{

    int tmp, ans[MAX_Node], k = 0;
    tmp = y;
    while (tmp != x)
    {
        ans[k++] = tmp;
        tmp = way[tmp];//逆推,到达y点需要经过哪个点
    }
    //当tmp==x时跳出,到达x点需要经过x
    ans[k] = way[x];
    for (int i = k; i >= 0; i--)
        printf("%d\n", ans[i]);
}

void find_minpath(PGraph g,int way[])
{
    //记录节点是否已经判断过
    //1表示判断过
    int visited[MAX_Node];
    //记录0到各节点的最短路径
    int dist[MAX_Node];
    int min;

    int flag; //标记
    //初始化

    scanf("%d%d", &x, &y); //输入要求路径的两个点

    for (int i = 0; i < g->vexcount; i++)
    {
        visited[i] = 0;          //初始化,未判断
        dist[i] = g->arcs[x][i]; //初始化距离,从x到各点的距离
        way[i] = x;//初始化,到达第i点经过x 即 经过x到达i
    }

    visited[x] = 1; //初始节点置为判断

    for (int i = 1; i < g->vexcount; i++)
    {
        min = 10000; //最大值

        for (int j = 0; j < g->vexcount; j++) //遍历每个节点
        {
            if (visited[j] == 0) //未判断,即没有在集合中，尚未处理
            {
                if (dist[j] < min) //不是最大值min
                {
                    flag = j; //如果距离比MIN小,则j为中间路径,更新
                    min = dist[j];
                }
            }
        }
        visited[flag] = 1; //置为判断

        //更新路径
        for (int j = 0; j < g->vexcount; j++)
        {
            if (visited[j] == 0 && (min + g->arcs[flag][j] < dist[j]))
            {
                dist[j] = min + g->arcs[flag][j];
                way[j] = flag;//到达j点经过flag
                //这里加上路径
            }
        }
    }

 
}
void initial(PGraph g)
{
    scanf("%d", &g->vexcount);
    for (int i = 0; i < g->vexcount; i++)
    {

        for (int j = 0; j < g->vexcount; j++)
        {
            scanf("%d", &g->arcs[i][j]);
        }
    }
}

10.

image-20210530155622500

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
#include <stdio.h>
#include <stdlib.h>
#define MAX_Node 100
#define MAX 10000

typedef struct
{
    int vex[MAX_Node];            //顶点信息
    int arcs[MAX_Node][MAX_Node]; //权值  邻接矩阵信息
    int arccount, vexcount;       //顶点个数,边的个数
} Graph, *PGraph;

typedef struct ShortPath
{
    /* 矩阵A，存放每对顶点间最短路径长度 */
    int a[MAX_Node][MAX_Node];
    /* nextvex[i][j]存放vi到vj最短路径上vi的后继顶点的下标值 */
    int nextvex[MAX_Node][MAX_Node];
} ShortPath, *path;

void initial(PGraph);
void find_minpath(PGraph, path);
void output(path,int);

int main(void)
{
    int count; 
    PGraph g = (PGraph)malloc(sizeof(Graph));
    path p = (path)malloc(sizeof(ShortPath));
    initial(g);  
    find_minpath(g, p);
    scanf("%d",&count);
    output(p,count);
    free(g);
    free(p);
    return 0;
}
void output(path p,int count)
{
    int x,y;
    while(count--)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",p->a[x][y]);
    }

}

void find_minpath(PGraph g, path p)
{
    int i, j, k;
    //初始化
    for (i = 0; i < g->vexcount; i++)
    {
        for (j = 0; j < g->vexcount; j++)
        {
            if (g->arcs[i][j] < MAX)  //如果两点存在路径
                p->nextvex[i][j] = j; //先把j初始化为i的下一个结点
            else
            {
                p->nextvex[i][j] = -1; //如果不存在该路径,则没有,置为-1
            }
            p->a[i][j] = g->arcs[i][j]; //距离初始化
        }
    }

    for (k = 0; k < g->vexcount; k++)
    {
        for (i = 0; i < g->vexcount; i++)
        {
            for (j = 0; j < g->vexcount; j++)
            {
                //k作为插入点,遍历 i,j
                //如果路径不存在,则继续
                if ((p->a[i][k] >= MAX) || (p->a[k][j] >= MAX))
                {
                    continue;
                }
                //如果路径存在且比直接路径短
                if(p->a[i][j]>(p->a[i][k]+p->a[k][j]))
                {
                       p->a[i][j]=p->a[i][k]+p->a[k][j];
                       p->nextvex[i][j] = p->nextvex[k][j];//将插入的点作为i的下一个点
                }
                
            }
        }
    }
}
void initial(PGraph g)
{
    scanf("%d", &g->vexcount);

    for (int i = 0; i < g->vexcount; i++)
    {

        for (int j = 0; j < g->vexcount; j++)
        {
            scanf("%d", &g->arcs[i][j]);
        }
    }
}

11.

image-20210530155607489

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
#include <stdio.h>
#include <stdlib.h>
#define MAX_Node 100
#define MAX 10000

typedef struct
{
    int vex[MAX_Node];            //顶点信息
    int arcs[MAX_Node][MAX_Node]; //权值  邻接矩阵信息
    int arccount, vexcount;       //顶点个数,边的个数
} Graph, *PGraph;

typedef struct ShortPath
{
    /* 矩阵A，存放每对顶点间最短路径长度 */
    int a[MAX_Node][MAX_Node];
    /* nextvex[i][j]存放vi到vj最短路径上vi的后继顶点的下标值 */
    int nextvex[MAX_Node][MAX_Node];
} ShortPath, *path;

void initial(PGraph);
void find_minpath(PGraph, path);
void output(path, int, int);

int main(void)
{
    int count;
    int x, y;

    PGraph g = (PGraph)malloc(sizeof(Graph));
    path p = (path)malloc(sizeof(ShortPath));
    initial(g);
    find_minpath(g, p);
    scanf("%d", &count);
    while (count--)
    {
        scanf("%d%d", &x, &y);
        printf("%d\n", x); //先输出首节点
        output(p, x, y);
        printf("%d\n", y); //若不存在中间节点,则输出尾结点
    }
    free(g);
    free(p);
    return 0;
}
void output(path p, int x, int y)
{
    int mid; //中间节点

    if (p->nextvex[x][y] != y) //如果存在中间节点
    {
        mid = p->nextvex[x][y];
        if (mid != -1) //存在弧
        {
            output(p, x, mid);
            printf("%d\n", p->nextvex[x][y]);
            output(p, mid, y);
        }
    }
}

void find_minpath(PGraph g, path p)
{
    int i, j, k;
    //初始化
    for (i = 0; i < g->vexcount; i++)
    {
        for (j = 0; j < g->vexcount; j++)
        {
            if (g->arcs[i][j] < MAX)  //如果两点存在路径
                p->nextvex[i][j] = j; //先把j初始化为i的下一个结点
            else
            {
                p->nextvex[i][j] = -1; //如果不存在该路径,则没有,置为-1
            }
            p->a[i][j] = g->arcs[i][j]; //距离初始化
        }
    }

    for (k = 0; k < g->vexcount; k++)
    {
        for (i = 0; i < g->vexcount; i++)
        {
            for (j = 0; j < g->vexcount; j++)
            {
                //k作为插入点,遍历 i,j
                //如果路径不存在,则继续
                if ((p->a[i][k] >= MAX) || (p->a[k][j] >= MAX))
                {
                    continue;
                }
                //如果路径存在且比直接路径短
                if (p->a[i][j] > (p->a[i][k] + p->a[k][j]))
                {
                    p->a[i][j] = p->a[i][k] + p->a[k][j];
                    p->nextvex[i][j] = p->nextvex[i][k]; //将插入的点作为i的下一个点
                }
            }
        }
    }
}
void initial(PGraph g)
{
    scanf("%d", &g->vexcount);

    for (int i = 0; i < g->vexcount; i++)
    {

        for (int j = 0; j < g->vexcount; j++)
        {
            scanf("%d", &g->arcs[i][j]);
        }
    }
}

-------------本文结束感谢您的阅读-------------
相关文章
感谢阅读.

欢迎关注我的其它发布渠道