相关说明

  • 文章内容:数据结构实验

  • 所属课程:数据结构

  • 实验学时:2学时

  • 授课学院:武汉理工大学计算机学院

  • 作者主页:https://blog.csdn.net/cxh_1231


实验目的:

  掌握线性表的基本结构和操作方法,培养学生灵活使用表解决实际问题的能力。


实验内容:

  一条记录有学号和成绩两个数据项,按成绩由大到小建立两个有序表(分别用顺序表和链式表实现),并合并成一个有序表。

  第一个表输入的数据如下(学号,成绩):(1,70),(2,85), (3,75), (4,90),

  第二个表输入的数据如下(学号,成绩):(5,60),(6,80), (7,76),(8,50)。

提示:

  1,编写初始化函数,插入函数,显示函数,释放函数,对两个表统一处理。

  2,编写合并函数,把两个有序表合并成一个新的有序表(保留原表)。

  3,分别用顺序表和链表实现。


实验代码①:顺序表实现

注:手机无法正常显示请在电脑端打开此文章

  1// *.cpp: 定义控制台应用程序的入口点。  
 2#include <iostream>  
 3using namespace std;  
 4#define LIST_INIT_SIZE 100  
 5#define LISTINCREASE 10  
 6#define Status int  
 7#define SCORE double  
 8#define NUMBER int  
 9#define OK 1  
10#define ERROR 0  
11#define OVERFLOW -2  
12#define EXIST 2  
13//定义线性表  
14typedef struct {  
15    NUMBER *num;  
16    SCORE *score;  
17    int length;  
18    int listsize;  
19}SqList1;  
20//初始化线性表  
21Status InitList(SqList1 &L) {  
22    L.num = (NUMBER *)malloc(LIST_INIT_SIZE * sizeof(NUMBER));  
23    L.score = (SCORE *)malloc(LIST_INIT_SIZE * sizeof(SCORE));  
24    if (!L.num) exit(OVERFLOW);  
25    L.length = 0;  
26    L.listsize = LIST_INIT_SIZE;  
27    return OK;  
28}  
29//将数据输入到线性表1 中,并按照成绩有大到小排序  
30Status InsertSqList1(SqList1 &L, NUMBER num, SCORE score) {  
31    int i;  
32    if (L.length == L.listsize)  
33        return OVERFLOW;  
34    if (L.length == 0) {  
35        L.num[0] = num;  
36        L.score[0] = score;  
37        L.length++;  
38        return OK;  
39    }  
40    for (i = 0; i < L.length; i++) {  
41        if (num ==L.num[i]) return EXIST;  
42    }  
43    for (i = L.length; i > 0, score < L.score[i - 1]; i--) {  
44        L.num[i] = L.num[i-1];  
45        L.score[i] = L.score[i-1];  
46    }  
47    L.num[i] = num;  
48    L.score[i] = score;  
49    L.length++;  
50    return OK;  
51}  
52//将两个成绩单合并  
53void MergeList_Sq(SqList1 &L1, SqList1 &L2, SqList1 &L3) {  
54    int i=0,j=0,k=0;  
55    while (i < L1.length && j < L2.length) {  
56        if (L1.score[i] <= L2.score[j])  
57        {  
58            L3.num[k] = L1.num[i];  
59            L3.score[k] = L1.score[i];  
60            L3.length++;  
61            i++;  
62            k++;  
63        }  
64        else  
65        {  
66            L3.num[k] = L2.num[j];  
67            L3.score[k] = L2.score[j];  
68            L3.length++;  
69            j++;  
70            k++;  
71        }  
72    }  
73    while (i<L1.length)  
74    {  
75        L3.num[k] = L1.num[i];  
76        L3.score[k] = L1.score[i];  
77        L3.length++;  
78        i++;  
79        k++;  
80    }  
81    while (j<L2.length)  
82    {  
83        L3.num[k] = L2.num[j];  
84        L3.score[k] = L2.score[j];  
85        L3.length++;  
86        j++;  
87        k++;  
88    }  
89}  
90//打印成绩单  
91void PrintList(SqList1 &L) {  
92    int i;  
93    if (L.length == 0) {  
94        cout << "无任何成绩数据!n";  
95        return;  
96    }  
97    cout << "学号t成绩n";  
98    for (i = L.length-1; i >=0; i--) {  
99        cout << L.num[i] << "t" << L.score[i] << endl;  
100    }  
101    cout << endl;  
102    return;  
103}  
104//主函数  
105int main(){  
106    SqList1 L1, L2, L3;  
107    NUMBER num;  
108    SCORE score;  
109    InitList(L1);  
110    InitList(L2);    
111    InitList(L3);  
112    cout << "-->1:将成绩输入到成绩单1中 n-->2:将成绩输入到成绩单2中n-->3:打印成绩单1n-->4:打印成绩单2n-->5:将成绩单1、2合并并输出n" << endl;  
113    int choice,flag;  
114    while (1)  
115    {  
116        cout << "请输入操作项:";  
117        cin >> choice;  
118        switch (choice) {  
119        case 1:  
120            cout << "请输入学号、成绩:";  
121            cin >> num >> score;  
122            flag = InsertSqList1(L1, num, score);  
123            if (flag == OK) cout << "成绩输入成功!nn";  
124            if (flag == OVERFLOW) cout << "空间不足,输入成绩失败!nn";  
125            if (flag == EXIST) cout << "该考生号已存在! 输入成绩失败!nn";  
126            break;  
127        case 2:  
128            cout << "请输入学号、成绩:";  
129            cin >> num >> score;  
130            flag = InsertSqList1(L2, num, score);  
131            if (flag == OK) cout << "成绩输入成功!nn";  
132            if (flag == OVERFLOW) cout << "空间不足,输入成绩失败!nn";  
133            if (flag == EXIST) cout << "该考生号已存在! 输入成绩失败!nn";  
134            break;    
135        case 3:  
136            PrintList(L1);  
137            break;  
138        case 4:  
139            PrintList(L2);  
140            break;  
141        case 5:  
142            MergeList_Sq(L1, L2, L3);  
143            cout << "合并成功,即将输出:n";  
144            PrintList(L3);  
145            break;  
146        }  
147    }  
148    return 0;  
149}  


运行结果①:


实验代码②:链式表实现

注:手机无法正常显示请在电脑端打开此文章

  1// 线性表的应用 链式表实现.cpp: 定义控制台应用程序的入口点。  
 2#include <iostream>  
 3using namespace std;  
 4#define Status int  
 5#define NUMBER int  
 6#define SCORE double  
 7#define OK 1  
 8#define ERROR 0  
 9#define OVERFLOW -2  
10#define NULL 0  
11#define EXIST 2  
12#define Status int  
13//定义链表  
14typedef struct LNode {  
15    NUMBER num;  
16    SCORE score;  
17    LNode *next;  
18}LNode, *LinkList;  
19//将数据按照顺序插入到链表中  
20Status InsertList(LinkList &L,NUMBER num,SCORE score) {  
21    LinkList p, q;  
22    q = new LNode;  
23    q->num = num;  
24    q->score = score;  
25    if (L == NULL)  {   //如果是空表,直接将数据插入到头指针处  
26        L = q;  
27        L->next = NULL;  
28        return OK;  
29    }  
30    if (L->score < score) {  //插入头部  
31        q->next = L;  
32        L = q;  
33        return OK;  
34    }  
35    p = L;  
36    while (p->next != NULL && p->next->score > score )   //进行比较数据大小  寻找插入点  
37        p = p->next;  
38    q->next = p->next;  
39    p->next = q;  
40    return OK;  
41}  
42//合并两个链表  
43Status CombineList(LinkList &L1, LinkList &L2, LinkList &L) {  
44    LinkList p1, p2;  
45    p1 = L1;  
46    p2 = L2;  
47    if (p1 == NULL && p2 == NULL) {  
48        return ERROR;  
49    }  
50    while (p1 != NULL) {  
51        InsertList(L, p1->num, p1->score);  
52        p1 = p1->next;  
53    }  
54    while(p2 != NULL) {  
55        InsertList(L, p2->num, p2->score);  
56        p2 = p2->next;  
57    }  
58    return OK;  
59}  
60//打印链表  
61Status PrintList(LinkList &L) {  
62    LinkList p;  
63    p = L;  
64    if (L==NULL){  
65        return ERROR;  
66    }    
67    cout << "学号t成绩" << endl;  
68    while (p != NULL){  
69        cout << p->num << "t" << p->score << endl;  
70        p = p->next;  
71    }  
72    cout << endl;  
73    return OK;  
74}  
75int main()  
76
{  
77    LinkList L1, L2,L;  
78    L1 = NULL; L2 = NULL;L=NULL;  
79    NUMBER num;  
80    SCORE score;  
81    cout << "-->1:将成绩输入到成绩单1中 n-->2:将成绩输入到成绩单2中n-->3:打印成绩单1n-->4:打印成绩单2n-->5:合并成绩单1、2" << endl;  
82    int choice, flag;  
83    while (1)  
84    {  
85        cout << "请输入操作项:";  
86        cin >> choice;  
87        switch (choice) {  
88        case 1:  
89            cout << "请输入学号、成绩:";  
90            cin >> num >> score;  
91            flag = InsertList(L1, num, score);  
92            if (flag == OK) cout << "成绩输入成功!nn";  
93            if (flag == OVERFLOW) cout << "空间不足,输入成绩失败!nn";  
94            if (flag == EXIST) cout << "该考生号已存在! 输入成绩失败!nn";  
95            break;  
96        case 2:  
97            cout << "请输入学号、成绩:";  
98            cin >> num >> score;  
99            flag = InsertList(L2, num, score);  
100            if (flag == OK) cout << "成绩输入成功!nn";  
101            if (flag == OVERFLOW) cout << "空间不足,输入成绩失败!nn";  
102            if (flag == EXIST) cout << "该考生号已存在! 输入成绩失败!nn";  
103            break;  
104        case 3:  
105            flag = PrintList(L1);  
106            if (flag == ERROR)  cout << "当前成绩单为空!请导入成绩!" << endl << endl;  
107            break;  
108        case 4:  
109            flag = PrintList(L2);  
110            if (flag == ERROR)  cout << "当前成绩单为空!请导入成绩!" << endl << endl;  
111            break;  
112        case 5:  
113            cout << "合并成绩单L1和L2:n";  
114            flag = CombineList(L1, L2, L);  
115            if(flag == ERROR) cout << "当前成绩单为空!请导入成绩!" << endl << endl;  
116            PrintList(L);  
117            break;  
118        }  
119    }  
120    return 0;  
121}  



运行结果②:


您的支持就是我们前进的动力

本篇文章来源于微信公众号: 计科