0%

线性表作业

简介

最近没博文写,把上周线性表的作业拿来写一下,以后可能还会写链表之类的数据结构课的作业(恬不知耻)

Link List

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
208
209
210
211
212
213
214
215
216
217
218
219
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define M 100
typedef struct{
int number;
char name[20];
char sex;
char addr[20];
} node;
typedef struct{
node stu[50];
int last; //列表中的最后一个学生
} sequenlist;
sequenlist *L;

sequenlist *Creat(){
int i = 0;
sequenlist *L;
node student;
L = (sequenlist *)malloc(sizeof(sequenlist));
L->last = -1;
printf("Please input the information of the student(End it by input the number 0)\n");
while(1){
printf("Input the number:");
scanf("%d", &student.number);
if(student.number==0)
break;
printf("Input the name, sex and address\n");
scanf("%s %s %s",student.name,&student.sex,student.addr);
L->stu[i++] = student;
L->last++;
}
return L;
} //建立一个表,其中已经按照姓名字典排序

void Input(sequenlist *L,node student){
int i, j;
for (i = 0; i <= L->last;i++)
if(strcmp(student.name,L->stu[i].name)<0)
break;
for (j = L->last; j >= i;j--)
L->stu[j + 1] = L->stu[j];
L->stu[i] = student;
L->last++;
} //按照姓名字典排序将学生数据插入进线性表中

int Delete(sequenlist *L,int n){
int i, j;
for (i = 0; i <= L->last;i++)
if(L->stu[i].number==n)
break;
if(i>L->last){
printf("404!\n");
return 0;
}
else{
for (j = i; j < L->last;j++)
L->stu[j] = L->stu[j + 1];
L->last--;
return 1;
}
} //根据学号查找并且删除对应学生数据

void Locate(sequenlist *L,char name[]){
int i;
for (i = 0; i <= L->last;i++){
if(strcmp(L->stu[i].name,name)==0){
printf("\nNumber:%d\nName:%s\nSex:%c\nAddress:%s", L->stu[i].number, L->stu[i].name, L->stu[i].sex, L->stu[i].addr);
break;
}
}
if(i<L->last)
printf("404 Not Found!\n");
} //根据学生的姓名找到对应的学生并输出其信息

void Output(sequenlist *L){
int i;
printf("Number Name Sex Address\n");
for (i = 0; i <= L->last;i++)
{
printf("%6d%12s", L->stu[i].number, L->stu[i].name);
printf(" %c%12s\n", L->stu[i].sex, L->stu[i].addr);
}
} //输出当前所有的学生信息

int main(){
sequenlist StudentList;
StudentList = *Creat();
int step = 0;
while(step!=1&&step!=2&&step!=3&&step!=4){
printf("Please choose the next step\n1 is Input, 2 is Delete, 3 is Locate, 4 is Output,5 is Exit\n(input Enter to Confirm):");
scanf("%d", &step);
if(step==1){
node stu = {0};
char temp[2] = {0};
printf("Please give the Student information:\n");
printf("Name:");
scanf("%s", stu.name);
printf("Number:");
scanf("%d", &stu.number);
printf("Sex(f or m):");
scanf("%s", temp);
stu.number = temp[0];
printf("Address:");
scanf("%s", stu.addr);

Input(&StudentList, stu);
step = 0;
}
else if(step==2){
printf("Please input the number:");
int num;
scanf("%d", &num);
Delete(&StudentList, num);
step = 0;
}
else if(step==3){
printf("Please input the Name:");
char name[20];
scanf("%s", name);
Locate(&StudentList, name);
step = 0;
}
else if(step==4){
Output(&StudentList);
step = 0;
}
else if(step==5)
exit(0);
}
}


//以下是作业后面的另外的题目,不会被主函数调用

/*试用顺序存储结构设计一个算法,仅用一个辅助结点,实现将线性表中的结点循环右移k位的运算,并分析算法的时间复杂度。*/

int Move(sequenlist *L,int n,int k){
int j = 0;
if(n<0||n>L->last)
return 0;
else if(j<k){
for (int i = L->last+j; i >= n + j; i--)
{
L->stu[i + j] = L->stu[i - 1 + j];
}
j++;
}
} //时间复杂度:O(kn)

/*已知一顺序表递增有序,试设计一算法,将x插入到表中的适当位置,以保持顺序表的有序性。*/

void Input2(sequenlist *L,node student)
{
int i, j;
for (i = 0; i <= L->last;i++)
if(strcmp(student.name,L->stu[i].name)<0)
break;
for (j = L->last; j >= i;j--)
L->stu[j + 1] = L->stu[j];
L->stu[i] = student;
L->last++;
}

/*设有两个顺序表A和B,元素的个数分别是m和n,若表中的数据都是由小到大顺序排列的,且这(m+n)个数据中没有相同的。
试设计算法将A和B合并成一个线性表C,并存储到另一个向量中。*/


int Combine(int A[],int B[],int Alast,int Blast){
int C[1000];
int k = 0;
for (int i = 0; i < Alast;i++){
for (int j = 0; j < Blast;j++){
if(A[i]>B[j]){
C[k] = B[j];
k++;
}
else{
C[k] = A[i];
k++;
break;
}
}
}
return C;
}


/*设有一个顺序表中,写出在其值为x的元素之后插入m个元素的算法(假设顺序表的长度足以容纳m个元素)。*/

void InputMNumbers(int list[],int last,int x,int m){
int i,j,temp;
for (i = 0; i <= last;i++){
if(list[i]==x)
break;
}
for (j = 0; j <= m; j++)
{
list[last + 1 - j] = list[last - j];
printf("input the number");
scanf("%d", temp);
list[x + j] = temp;
}
}

/*设有一线性表E={e1,e2,…,en-1,en),试设计一个算法,将线性表逆置,
即:使元素排列次序颠倒过来,成为逆线性表E¢={en,en-1,…,e2,e1),要求逆线性表占用原线性表空间,并且用顺序表表示,写出处理过程。*/

void ReturnList(int list[],int last){
int half = (last+1) / 2;
int temp;
for (int i = 0; i <= half; i++){
temp = list[i];
list[i] = list[last - i];
list[last - i] = temp;
}
}