Catalog
  1. 1. 问题描述
    1. 1.1. 1.算法2.1
    2. 1.2. 2.分别用链式和顺序表实现
    3. 1.3. 3.所涉及的基本操作全部用函数实现
    4. 1.4. 链式存储
      1. 1.4.1. 运行界面
    5. 1.5. 顺序表存储
      1. 1.5.1. 运行界面
数据结构实验一

问题描述

1.算法2.1

2.分别用链式和顺序表实现

3.所涉及的基本操作全部用函数实现

链式存储

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>

typedef struct LNode {
int data;
LNode *next;
}LNode,*LinkList;

void List_initialize(LinkList &L, int n)
{
LNode* p;
L = (LNode*)malloc(sizeof(LNode));
L->next = NULL;
for (int i = 0; i < n; ++i){
p = (LNode *)malloc(sizeof(LNode));
scanf("%d", &p->data);
p->next = L->next;
L->next = p;
}
}
bool compare(int a, int b)
{
if (a == b)
return true;
}
void List_show(LNode *head)
{
LNode *p = head->next;
while (p != NULL){
printf("%d ",p->data);
p = p->next;
}
}
int GetElem(LNode *L, int pos)
{
LNode *p = L->next;
for (int i = 0; i < pos - 1; i++)
p = p->next;
return p->data;
}
int Listlen(LNode *head)
{
LNode *p = head->next;
int len = 0;
while (p){
len++;
p = p->next;
}
return len;
}
int List_insert(LinkList &L, int i, int e)
{
if (i < 1)
return 0;
LNode *p = L;
LNode *s;
int j = 0;
while (p && j < i - 1) {
p = p->next;
++j;
}
if (!p)
return 0;
s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return 1;
}

LNode* List_only(LNode *head)
{
LNode *p, *q, *s;
p = head->next;
while (p->next != NULL){
q = p;
while (q->next != NULL){
if (q->next->data == p->data){
s = q->next;
q->next = s->next;
free(s);
}
else
q = q->next;
}
p = p->next;
}
return head;
}
void List_union(LinkList &L1, LinkList L2)
{
LinkList p, q, s;
p = L1;
q = L2;
while (p->next != NULL) {
while (q->next != NULL) {
if (p->next->data == q->next->data)
break;
else
q = q->next;
}
if (q->next == NULL) {
s = (LinkList)malloc(sizeof(LNode));
s->data = p->next->data;
s->next = NULL;
q->next = s;
}
p = p->next;
q = L2;
}
}
int main()
{
int lena, lenb;
LinkList la, lb;
printf("请输入集合A的元素个数:");
scanf("%d", &lena);
printf("请输入集合A元素:");
List_initialize(la, lena);
printf("原集合A:");
List_show(la);
printf("\n");
List_only(la);
printf("集合去重后个数:");
printf("%d",Listlen(la));
printf("\n");
printf("删除重复元素后的集合A为:");
List_show(la);
printf("\n");

printf("请输入集合B的元素个数:");
scanf("%d", &lenb);
printf("请输入集合B元素:");
List_initialize(lb, lenb);
printf("集合B:");
List_show(lb);
printf("\n");
List_only(lb);
printf("集合去重后个数:");
printf("%d", Listlen(lb));
printf("\n");
printf("删除重复元素后的集合B为:");
List_show(lb);
printf("\n");

printf("A和B的并集为:");
List_union(la, lb);
List_only(la);
List_show(la);

return 0;
}

运行界面

sy

顺序表存储

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
#include<iostream>
#include<cstdio>
using namespace std;

int a[10000], b[10000];
int lena, lenb;

void arrayA_initialize()
{
//输入集合A
printf("请输入集合元素个数(小于10000):");
scanf("%d", &lena);
while (lena >= 10000) {
printf("超出最大容量\n");
printf("请重新输入\n");
printf("请输入集合A元素个数(小于10000):");
scanf("%d", &lena);
}
printf("请输入集合A元素:");
int temp, cnta = 1;
scanf("%d", &a[0]);
for (int i = 1; i < lena; i++) {
int flag = 1;
scanf("%d", &temp);
for (int j = 0; j < i; j++) { //去重
if (temp == a[j])
flag = 0;
}
if (flag) {
a[cnta] = temp;
cnta++;
}
}
lena = cnta;
printf("数组A的长度最终为: %d\n", lena);
printf("去重后的数组A为 :\n");
for (int i = 0; i < lena; i++)
printf("%d ", a[i]);
printf("\n");
}

void arrayB_initialize()
{
//输入集合B
printf("请输入集合B元素个数(小于10000):");
scanf("%d", &lenb);
while (lenb >= 10000) {
printf("超出最大容量\n");
printf("请重新输入\n");
printf("请输入集合B元素个数(小于10000):");
scanf("%d", &lenb);
}
printf("请输入集合B元素:");
int temp, cntb = 1;
scanf("%d", &b[0]);
for (int i = 1; i < lenb; i++) {
int flag = 1;
scanf("%d", &temp);
for (int j = 0; j < i; j++) { //去重
if (temp == b[j])
flag = 0;
}
if (flag) {
b[cntb] = temp;
cntb++;
}
}
lenb = cntb;
printf("数组B的长度最终为: %d\n", lenb);
printf("去重后的数组B为 :\n");
for (int i = 0; i < lenb; i++)
printf("%d ", b[i]);
printf("\n");
}
int binarySearch(int a[], int b, int lena)
{
int left = 0, right = lena - 1, mid;
while (left <= right){
mid = (right + left) / 2;
if (a[mid] == b)
return 1;
else if (a[mid] > b){
right = mid - 1;
}
else
left = mid + 1;
}
return -1;
}
void array_insert(int a[], int lena, int b[], int lenb)
{
//将所有在数组B中但不在A中的数据元素插入到A中
int cnt = 0;
for (int i = 0; i < lenb; i++) {
if (binarySearch(a, b[i], lena) == -1) {
a[lena + cnt] = b[i];
cnt++;
}
}
lena += cnt;
printf("A与B合并后的集合为:\n");
for (int i = 0; i < lena; i++) {
printf("%d ", a[i]);
}

}
int main()
{
arrayA_initialize();
arrayB_initialize();
array_insert(a, lena, b, lenb);
return 0;
}

运行界面

sy

Author: Christopher Shen
Link: https://www.pasxsenger.com/2019/09/23/数据结构实验一/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶