线性表的实现（一）（顺序表实现）——数据结构（严蔚敏C语言实现版）
|字数总计:1.3k|阅读时长:7分钟|阅读量:|
采用函数实现和声明分开，SeqList.h包含结构体声明和所有函数的声明，SeqList.c包含所有函数的实现，main.c主函数实现,代码在vs中测试运行通过，其中部分代码是假设存储的数中没有重复的数
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
|
#pragma once
#include "SeqList.h"
#include <stdio.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
|
#pragma once
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);
|
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
|
#include "SeqList.h"
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
void Init(SeqList *mylist)
{
mylist->base = (ElemType *)malloc(sizeof(ElemType) * 8);
assert(mylist->base != NULL);
mylist->capacicty = 8;
mylist->size = 0;
}
void push_back(SeqList *mylist, ElemType Item)
{
if (mylist->size >= mylist->capacicty)
{
printf("空间已满\n");
return;
}
mylist->base[mylist->size] = Item;
mylist->size++;
}
void push_front(SeqList *mylist, ElemType Item)
{
if (mylist->size >= mylist->capacicty)
{
printf("空间已满\n");
return;
}
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)
{
printf("空间已满\n");
return;
}
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;
|
