大二下 数据结构(三)

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

目标:线性表在链式存储结构的实现。

内容:

已知某线性表中的数据元素由三个数据项(学号、姓名、成绩)组成,且数据元素按照学号递增有序,表长为n。选择带头结点的单链表作为存储结构。设计并实现如下算法:
(1) n个数据元素作为初始数据,置入相应的存储结构中。(测试时至少10个数据元素),输出线性表中各数据元素。
(2)将新的数据元素x插入到线性表的适当位置上,以保持该表的有序性,输出线性表中各数据元素。

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

#define MAX 10 //链表中数据的最大个数

struct stu
{
int num;
char name[20];
float score;
}student,temp;//创建结构体数组

typedef struct LNode{//定义单链表的存储结构
stu student;
struct LNode * next;
}LNode,* LinkList;

LNode *p;

void Create_LinkList(LinkList &L,int n){//逆向插法建立单链表
L=(LinkList)malloc(sizeof(LNode));
if(!L){
printf("Failed to create the LinkList!\n");
exit(-1);
}
L->next=NULL;//建立一个带头结点的单链表
for(int i=n;i>0;i--){
p=(LinkList)malloc(sizeof(LNode));//生成新结点
printf("Please input the data(number/name/score) of NO.%d student:",n-i+1);
scanf("%d%s%f",&p->student.num,p->student.name,&p->student.score);
p->next=L->next;
L->next=p;
}
}

void Insert(LinkList L){
p=(LinkList)malloc(sizeof(LNode));//生成新结点
printf("Please input the data(number/name/score) to be inserted:");
scanf("%d%s%f",&p->student.num,p->student.name,&p->student.score);
p->next=L->next;
L->next=p;
}

void Display(LinkList L){
printf("\nThe data in storage are:\nNO. NAME SCORE\n");
LNode *s;
s=L;
while(s->next!=NULL){
s=s->next;
printf(" %d %-s %-.1f\n",s->student.num,s->student.name,s->student.score);
}
printf("\n");
}

void LinkList_Sort(LinkList L){
LNode *p, *q, *min;

p=L->next;
while(p != NULL){
min = p;
q = p->next;
while (q != NULL){
if ((min->student.num) > (q->student.num))
min = q;

q = q->next;
}
if (min != p){
temp.num = min->student.num;
strcpy(temp.name,min->student.name);
temp.score=min->student.score;
min->student.num = p->student.num;
strcpy(min->student.name ,p->student.name);
min->student.score = p->student.score;
p->student.num = temp.num;
strcpy(p->student.name , temp.name);
p->student.score = temp.score;
}
p = p->next;
}
}

int main(){
LinkList L;

Create_LinkList(L,MAX);
Display(L);
Insert(L);
LinkList_Sort(L);
Display(L);
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
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define LIST_INIT_SIZE 100

struct students
{
int num;
char name[30];
float score;
}student,temp;

typedef struct LNode{
students student;
struct LNode * next;
}LNode,* LinkList;

LinkList L;
LNode *p;

int CreateLinkList(LinkList &L,int n){
L=(LinkList)malloc(sizeof(LNode));
if(!L){
printf("表头结点开辟失败!\n");
exit(-1);
}
L->next=NULL;
for(int i=n;i>0;i--){
p=(LinkList)malloc(sizeof(LNode));
printf("请输入第%d位学生信息学号/姓名/成绩:",n-i+1);
scanf("%d%s%f",&p->student.num,p->student.name,&p->student.score);
p->next=L->next;
L->next=p;
}
return 0;
}

int InsertLinkList(LinkList L){
p=(LinkList)malloc(sizeof(LNode));
printf("请输入待插入的数据(学号/姓名/成绩):");
scanf("%d%s%f",&p->student.num,p->student.name,&p->student.score);
p->next=L->next;
L->next=p;
return 0;
}

int PrintLinkList(LinkList L){
printf("\n单链表中的数据为:\n学号 姓名 成绩\n");
LNode *s;
s=L;
while(s->next!=NULL){
s=s->next;
printf(" %d %-s %-.1f\n",s->student.num,s->student.name,s->student.score);
}
printf("\n");
return 0;
}

int LinkListSort(LinkList L){
LNode *p, *q, *min;

p=L->next;
while(p != NULL){
min = p;
q = p->next;
while (q != NULL){
if ((min->student.num) > (q->student.num))
min = q;

q = q->next;
}
if (min != p){
temp.num = min->student.num;
strcpy(temp.name,min->student.name);
temp.score=min->student.score;
min->student.num = p->student.num;
strcpy(min->student.name ,p->student.name);
min->student.score = p->student.score;
p->student.num = temp.num;
strcpy(p->student.name , temp.name);
p->student.score = temp.score;
}
p = p->next;
}
return 0;
}

int main(){

CreateLinkList(L,10);
InsertLinkList(L);
LinkListSort(L);
PrintLinkList(L);

return 0;
}