大二下 数据结构(五)

适用于电商专业大二年级下学期,数据结构专业选修课,不是物联网同学大二上的数据结构哦。
年代久远,仅供参考。

目标:掌握排序和折半查找算法。

内容:

查找表是学生记录的集合,记录由如下数据项组成:
(学号,姓名,数据结构课程成绩)
(1)用冒泡排序方法对查找表按照成绩非递减排序
(2)基于折半查找的方法对指定成绩的记录查找,输出查找成功的记录在有序序列中的位序及其完整记录内容或者说明查找失败。

测试实例:

(1) 成绩排列为{50 94 65 97 78 81 83 76 88 92 78},对应的学号和姓名项自行拟值
(2) 查找成绩分别为 78和89 的记录

代码

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

struct stu//create the array of structure and initialize the data.
{
int num;
char name[20];
int score;
}student[]={{0001,"Lydia",50},{0002,"Mary",94},{0003,"Mark",65},{0004,"Santanico",97},{0005,"Jack",78},{0006,"Rose",81},{0007,"Kenna",83},{0015,"Henry",76},{0015,"Katherine",88},{0010,"Claude",92},{0011,"Leith",78}};

typedef struct SSTable{
stu *elem;
int length;
int tablesize;
};
SSTable T;

int InitTable(SSTable &T)//initialize the sequence table
{
T.elem=(stu *)malloc(LIST_INIT_SIZE*sizeof(stu));
if(!T.elem)return -2;
T.length=0;
T.tablesize=LIST_INIT_SIZE;
return 1;
}

void InputTable(SSTable &T)
{
printf("Before Sorting, data in the table are as followed:\nNO. Name Score of DS:\n");
for(int i=0;i<=10;i++){
T.elem[i+1]=student[i];//assign the data from the array to the table
T.length++;
printf("%-10d %-10s %-10d\n",T.elem[i+1].num,T.elem[i+1].name,T.elem[i+1].score);
}
}

void BubbleSort(SSTable &T)
{
int i ,j;
stu temp;
int sorted=0;

for(i = 0; i < T.length && ( !sorted); i++){//sorting the data in non-decreasing order
sorted = 1;
for(j = 1; j < T.length-i; j++)
{
if(T.elem[j].score>T.elem[j+1].score)
{
temp=T.elem[j];
T.elem[j]=T.elem[j+1];
T.elem[j+1]=temp;
sorted=0;
}
}
}
stu *k;//print out the data after sorting
printf("-------------------------------------------------------\nAfter Bubble Sorting, data in the table are as followed:\nNO. Name Score of DS:\n");
for(k = T.elem + 1; k <= T.elem+T.length; k++)
printf("%-10d %-10s %-10d\n",k->num,k->name,k->score);
}

int result;
int Search_Bin(SSTable T,int key)//binary search funtion
{
int low = 1,high = T.length;// put initial range values

while ( low <= high ) {
int mid = ( low + high )/2;
if (key == T.elem[mid].score) {
//print out the data for corresponding score
printf("-------------------------------------------------------\nSearched Successfully! Data are as followed:\n");
printf("NO. Name Score of DS\n");
printf("%-10d %-10s %-10d\n",T.elem[mid].num,T.elem[mid].name,T.elem[mid].score);
result = mid;

int k;
for (k = 1; T.elem[mid - k].score >= T.elem[mid].score; k++){
printf("NO. Name Score of DS\n");
printf("%-10d %-10s %-10d\n",T.elem[mid - k].num,T.elem[mid - k].name,T.elem[mid - k].score);
}
for (k = 1; T.elem[mid + k].score <= T.elem[mid].score; k++){
printf("NO. Name Score of DS\n");
printf("%-10d %-10s %-10d\n",T.elem[mid + k].num,T.elem[mid + k].name,T.elem[mid + k].score);
}
return result;
}
else {
if ( key < T.elem[mid].score)
high = mid - 1;
else low = mid + 1;
}
}
result = -1;
if(result==-1)//print out that no such record is in the table
printf("\nSearching failed, no such record in the table!\n\n");
return result;
}

int main(){
int i;

InitTable(T);
InputTable(T);
BubbleSort(T);

int key[2];//declare the array of keys to be searched
for(int i=0;i<=1;i++){
printf("\nPlease input the score of (%d) to be searched:\n",i+1);
scanf("%d", &key[i]);
Search_Bin(T, key[i]);
}

system("pause");
}

日常帮写第二份

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
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define LIST_INIT_SIZE 100
#define INCREMENT_SIZE 10

struct stu
{
int num;
char name[20];
int score;
};
stu student[11]={{1110,"晨晨",50},{1111,"倩倩",94},{1112,"瑶瑶",65},{1113,"事事",97},{1114,"依依",78},{1115,"格格",81},{1116,"嗒嗒",83},{1117,"帅帅",76},{1118,"咯咯",88},{1119,"噢噢",92},{1120,"娅娅",78}};//创建结构体数组

typedef struct SSTable{
stu *elem;
int length;
int tablesize;
};
SSTable List;
int result;

int InitTable(SSTable &T)//生成顺序表
{
T.elem=(stu *)malloc(LIST_INIT_SIZE*sizeof(stu));
if(!T.elem)return -2;
T.length=0;
T.tablesize=LIST_INIT_SIZE;
return 1;
}

void InputTable(SSTable &T)
{
printf("表中数据如下:\n学号 姓名 数据结构成绩:\n");
for(int i=0;i<=10;i++){
T.elem[i+1].num=student[i].num;//把结构体数组中的数据录入到Table中
strcpy(T.elem[i+1].name,student[i].name);
T.elem[i+1].score=student[i].score;
T.length++;
printf("%-10d %-10s %-10d\n",T.elem[i+1].num,T.elem[i+1].name,T.elem[i+1].score);//并打印出table中的数据
}
}
void OutputTable(SSTable T)
{
stu *i;
printf("表中数据如下:\n学号 姓名 数据结构成绩:\n");
for(i = T.elem + 1; i <= T.elem+T.length; i++)
printf("%-10d %-10s %-10d\n",i->num,i->name,i->score);
}

void BubbleSort(SSTable &T)
{
int i ,j;
stu temp;
int sorted=0;

for(i = 0; i < T.length && ( !sorted); i++){
sorted = 1;
for(j = 1; j < T.length-i; j++)
{
if(T.elem[j].score>T.elem[j+1].score)
{
temp=T.elem[j];
T.elem[j]=T.elem[j+1];
T.elem[j+1]=temp;
sorted=0;
}
}
}
}

int Search_Bin(SSTable T,int key)
{
int low = 1,high = T.length;// 置区间初值

while ( low <= high ) {
int mid = ( low + high )/2;
if (key == T.elem[mid].score) {
//打印对应成绩的信息
printf("查找成功!信息如下:\n");
printf("学号 姓名 数据结构成绩:\n");
printf("%-10d %-10s %-10d\n",T.elem[mid].num,T.elem[mid].name,T.elem[mid].score);
result = mid;

int k;
for (k = 1; T.elem[mid - k].score >= T.elem[mid].score; k++){
printf("学号 姓名 数据结构成绩:\n");
printf("%-10d %-10s %-10d\n",T.elem[mid - k].num,T.elem[mid - k].name,T.elem[mid - k].score);
}
for (k = 1; T.elem[mid + k].score <= T.elem[mid].score; k++){
printf("学号 姓名 数据结构成绩:\n");
printf("%-10d %-10s %-10d\n",T.elem[mid + k].num,T.elem[mid + k].name,T.elem[mid + k].score);
}
return result;
} // 找到待查元素的处理方式
else {
if ( key < T.elem[mid].score)
high = mid - 1; // 继续在前半区间进行查找
else low = mid + 1; // 继续在后半区间进行查找
}
}
result = -1;
return result;//在顺序表中找不到待查元素的处理方式
}

int main(){
int i;

InitTable(List);
InputTable(List);
BubbleSort(List);
printf("\n冒泡排序方法对查找表按照成绩非递减排序后:\n");
OutputTable(List);

int k1, k2;//声明待查找的两个数据的key
printf("\n请输入待查找数据(1)的成绩:\n");
scanf("%d", &k1);
Search_Bin(List, k1);
if(result==-1)
printf("查找失败!");

printf("\n\n请输入待查找数据(2)的成绩:\n");
scanf("%d", &k2);
Search_Bin(List, k2);
if(result==-1)
printf("查找失败!");

system("pause");
}