线性表的实现（二）（顺序表实现）——数据结构（严蔚敏C语言实现版）
|字数总计:1.4k|阅读时长:7分钟|阅读量:|
在线性表的实现（一）（顺序表实现）的基础上添加了可以自动增加空间的功能，添加数据时，如果线性表空间已满，则自动增加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
|
#pragma once
#include "SeqList.h"
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#pragma warning(disable : 4996)
int main()
{
SeqList mylist;
ElemType Item;
int pos;
int select = 1;
Init(&mylist);
while (select)
{
printf("**************************************\n");
printf("* [1] push_back [2] push_front *\n");
printf("* [3] show_list [4] pop_back *\n");
printf("* [5] pop_front [6] insert_pos *\n");
printf("* [7] find [8] length *\n");
printf("* [9] delete_pos [10] delete_val *\n");
printf("* [11] sort [12] resver *\n");
printf("* [13] clear [14*] destroy *\n");
printf("* [0] quit_system *\n");
printf("**************************************\n");
printf("请输入选项：>");
scanf("%d", &select);
if (select==0)
{
break;
}
if (!(select > 0 && select <= 14))
{
printf("输入有误,请重新输入\n");
}
switch (select)
{
case 0:
break;
case 1:
printf("请输入要插入的数字，以-1结束：");
while (scanf("%d", &Item), Item != -1)
{
push_back(&mylist, Item);
}
break;
case 2:
printf("请输入要插入的数字，以-1结束：");
while (scanf("%d", &Item), Item != -1)
{
push_front(&mylist, Item);
}
break;
case 3:
show(mylist);
break;
case 4:
pop_back(&mylist);
break;
case 5:
pop_front(&mylist);
break;
case 6:
printf("请输入要插入位置的下标：");
scanf("%d", &pos);
printf("请输入要插入的数字，以-1结束输入：");
while (scanf("%d", &Item), Item != -1)
{
insert_pos(&mylist, pos, Item);
}
break;
case 7:
printf("请输入要查找的数的值，以-1结束输入：");
while (scanf("%d", &Item), Item != -1)
{
int tmp = find(mylist, Item);
if (tmp >= 0)
{
printf("要查找的数在下标为%d处\n", find(mylist, Item));
}
else
{
printf("未找到\n");
}
}
break;
case 8:
printf("线性表的长度为%d\n", length(mylist));
break;
case 9:
printf("请输入要删除数的下标，以-1结束输入：");
while (scanf("%d", &pos), pos != -1)
{
delete_pos(&mylist, pos);
}
break;
case 10:
printf("请输入要删除数据的值，以-1结束输入");
while (scanf("%d", &Item), Item != -1)
{
delete_val(&mylist, Item);
}
break;
case 11:
sort(&mylist);
break;
case 12:
resver(&mylist);
break;
case 13:
clear(&mylist);
break;
case 14:
break;
default:
break;
}
}
free(mylist.base);
mylist.base = NULL;
return 0;
}
|
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
|
#pragma once
#define SEQLIST_INT_SIZE 8
#define INT_SIZE 3
typedef int ElemType;
typedef struct SeqList
{
ElemType *base;
int capacicty;
int size;
}SeqList;
void Init(SeqList *mylist);
void show(SeqList mylist);
void push_back(SeqList *mylist, ElemType Item);
void push_front(SeqList *mylist,ElemType Item);
void pop_back(SeqList *mylist);
void pop_front(SeqList *mylist);
void insert_pos(SeqList *mylist, int pos, int Item);
int find(SeqList mylist, ElemType Item);
int length(SeqList mylist);
void delete_pos(SeqList *mylist, int pos);
void delete_val(SeqList *mylist, ElemType Item);
void sort(SeqList *mylist);
void resver(SeqList *mylist);
void clear(SeqList *mylist);
void buymem(SeqList *mylist, int size);
|
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
|
#include "SeqList.h"
#include <stdio.h>
#include <assert.h>
#include <malloc.h>
#include <stdlib.h>
void buymem(SeqList *mylist, int size)
{
ElemType *newbase = realloc(mylist->base, sizeof(ElemType)*(mylist->capacicty + INT_SIZE));
if (newbase == NULL)
{
printf("增加空间失败\n");
return;
}
mylist->base = newbase;
mylist->capacicty += INT_SIZE;
}
void Init(SeqList *mylist)
{
mylist->base = (ElemType *)malloc(sizeof(ElemType) * SEQLIST_INT_SIZE);
assert(mylist->base != NULL);
mylist->capacicty = 8;
mylist->size = 0;
}
void push_back(SeqList *mylist, ElemType Item)
{
if (mylist->size >= mylist->capacicty)
{
buymem(mylist,INT_SIZE);
}
mylist->base[mylist->size] = Item;
mylist->size++;
}
void push_front(SeqList *mylist,ElemType Item)
{
if (mylist->size >= mylist->capacicty)
{
buymem(mylist, INT_SIZE);
}
for (int i = mylist->size; i >= 0; i--)
{
mylist->base[i + 1] = mylist->base[i];
}
mylist->base[0] = Item;
mylist->size++;
}
void show(SeqList mylist)
{
for (int i = 0; i < mylist.size; i++)
{
printf("%d ", mylist.base[i]);
}
printf("\n");
printf("%d\n", mylist.size);
}
void pop_back(SeqList *mylist)
{
if (mylist->size == 0)
{
printf("线性表已为空\n");
return;
}
mylist->size--;
}
void pop_front(SeqList *mylist)
{
if (mylist->size == 0)
{
printf("线性表已为空\n");
return;
}
if (mylist->size == 1)
{
mylist->size--;
return;
}
for (int i = 0; i < mylist->size - 1; i++)
{
mylist->base[i] = mylist->base[i + 1];
}
mylist->size--;
}
void insert_pos(SeqList *mylist, int pos, int Item)
{
if (mylist->size >= mylist->capacicty)
{
buymem(mylist, INT_SIZE);
}
if (!(pos >= 0 && pos <= mylist->size))
{
printf("输入的下标位置错误，请重新输入");
return;
}
for (int i = mylist->size; i >= pos; i--)
{
mylist->base[i+1] = mylist->base[i];
}
mylist->base[pos] = Item;
mylist->size++;
}
int find(SeqList mylist, ElemType Item)
{
for (int i = 0; i < mylist.size; i++)
{
if (mylist.base[i] == Item)
{
return i;
}
}
return -2;
}
int length(SeqList mylist)
{
return mylist.size;
}
void delete_pos(SeqList *mylist, int pos)
{
if (!(pos >= 0 && pos <= mylist->size))
{
printf("输入的下标位置错误，请重新输入");
return;
}
for (int i = pos; i < mylist->size - 1; i++)
{
mylist->base[i] = mylist->base[i + 1];
}
mylist->size--;
}
void delete_val(SeqList *mylist, ElemType Item)
{
int pos = find(*mylist, Item);
if (pos < 0)
{
printf("未找到该数值为%d的数，请重新输入", Item);
return;
}
delete_pos(mylist, pos);
}
void sort(SeqList *mylist)
{
if (mylist->size == 0)
{
printf("线性表已为空\n");
return;
}
int tmp;
for (int i = 0; i < mylist->size; i++)
{
for (int j = 0; j < mylist->size - i - 1; j++)
{
if (mylist->base[j] > mylist->base[j + 1])
{
tmp = mylist->base[j];
mylist->base[j] = mylist->base[j + 1];
mylist->base[j + 1] = tmp;
}
}
}
}
void resver(SeqList *mylist)
{
if (mylist->size == 0)
{
printf("线性表已为空\n");
return;
}
int tmp;
for (int i = 0, j = mylist->size - 1; i < j; i++, j--)
{
tmp = mylist->base[i];
mylist->base[i] = mylist->base[j];
mylist->base[j] = tmp;
}
}
void clear(SeqList *mylist)
{
mylist->size = 0;
}
|
