数据结构(一)

声明:本文仅限用于学术交流,引用或转载本文时请注明出处!

当了一学期数据结构的助教,终于结束了,准备把这学期得实验都贴上来,因为我是带的非计算机专业得数据结构,题目都不是很难,所以都直接贴题目和代码了。

顺序表得操作

题目要求

1、熟悉C语言的上机环境,掌握C语言的基本结构;
2、掌握线性表的顺序存储结构的定义;
3、熟悉对顺序表的一些基本操作和具体的函数定义;
4、掌握在线性表的顺序存储结构上的一些其他操作。
实验要求:已知两个非递减有序的线性表La和Lb,将La和Lb合并成一个线性表Lc,Lc也非递减有序。
5、
输入格式:
输入数据包含三行,第一行有两个正整数m和n(空格隔开),分别表示La和Lb的长度。第二行有m个整数(空格隔开),表示La中的元素。第三行有n个整数(空格隔开),表示Lb中的元素。(依次读取第二行m个和第三行n个整数,创建La和Lb)
输出格式:
输出格式包含三行,第一行为La中的元素顺序输出。第二行为Lb中的元素顺序输出。第三行为Lc中的元素顺序输出。
输入:
5 3
1 3 5 7 9
2 3 6
输出:
1 3 5 7 9
2 3 6
1 2 3 3 5 6 7 9

代码

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
//如果代码有错,请自行修改
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef struct
{
int *elem;
int length;
int listsize;
} SqList;
//初始化线性表
Status InitList(SqList &L)
{
L.elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int));
if (!L.elem)
exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
//线性表中插入元素
Status ListInsert_Sq(SqList &L, int i, int e)
{

int *newbase;
int *q, *p;
if (i < 1 || i > L.length + 1)
return ERROR;
if (L.length >= L.listsize)
{
newbase = (int *)realloc(L.elem, (LIST_INIT_SIZE + LISTINCREMENT) * sizeof(int));
if (!newbase)
exit(OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
q = &(L.elem[i - 1]);
for (p = &(L.elem[L.length - 1]); p >= q; --p)
{
*(p + 1) = *p;
}
*q = e;
L.length++;
return OK;
}
//合并两个线性表
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc)
{
int *pa, *pb, *pc, *pa_last, *pb_last;
pa = La.elem;
pb = Lb.elem;
Lc.listsize = Lc.length = La.length + Lb.length ;
pc = Lc.elem = (int *)malloc(Lc.listsize * sizeof(int));
if (!Lc.elem)
exit(OVERFLOW);
pa_last = La.elem + La.length - 1 ;
pb_last = Lb.elem + Lb.length - 1 ;
while (pa <= pa_last && pb <= pb_last)
{
if (*pa <= *pb)
{
*pc++ = *pa++;
}
else
{
*pc++ = *pb++;
}
}
while (pa <= pa_last )
*pc++ = *pa++;
while (pb <= pb_last )
*pc++ = *pb++;
}
//打印线性表
void Display(SqList Lc)
{
int i ;
for (i = 0; i < Lc.length; ++i)
printf("%d ", Lc.elem[i]);
printf("\n");
}
int main()
{
SqList La, Lb, Lc;
int m, n;
int i ;
int e;
InitList(La);
InitList(Lb);
scanf("%d %d", &m, &n);
for (i = 1 ; i <= m; i++)
{
scanf("%d", &e);
ListInsert_Sq(La, i, e);

}
for (i = 1 ; i <= n; i++)
{
scanf("%d", &e);
ListInsert_Sq(Lb, i, e);

}
MergeList_Sq(La, Lb, Lc);
Display(La);
Display(Lb);
Display(Lc);
return 0;
}

参考资料

《数据结构(C语言版)》 严蔚敏 吴伟民 编著

wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器