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
|
#include <stdio.h>
#include <stdlib.h>
//循序表实例
/* 逻辑顺序和物理顺序一致，连续存储，可以任意访问*
类型声名如下：*/
/*静态存储*/
#define LIST_INIT_SIZE 100 //存储空间的初始分配量,这是顺序存储的缺点
#define LIST_INCREMENT 10 // 存储空间的分配增量
typedef int ElemType; //存储元素的数据类型，可以自定义
typedef struct
{
ElemType *elem; //存储空间的基地址
int length; //当前长度
int listsize; // 当前分配的存储容量
} SqList;
//初始化线性表
int InitList_Sq(SqList &L)
{
//构造一个空的先线性表
L.elem = (ElementType *)malloc(LIST_INIT_SIZE * sizeof(ElementType)); //分配空间
//测试分配是否成功
if (!L.elem)
return 0;
//初始化
L.length = 0; //初始数据量为0
L.listsize = LIST_INIT_SIZE; //初始存储量为最大
return 1;
}
//销毁线性表:动态分配必须释放
int DestoryList(SqList &L)
{
free(L.elem); //由INIT函数可以知道，此处可以直接一步释放
//释放后不要忘记修改参数的值
L.elem = NULL;
L.length = 0;
L.listsize = 0;
return 1;
}
//求线性表的长度
int GetLength(SqList L)
{
return L.length; //length里面记录了表中元素的个数
}
//求线性表中第i个元素
int GetElem(SqList L, int i, ElemType &e)
{
//注意进行数据i是否合法的判断
if (i < 1 || i > L.length)
{
return 0;
}
//返回对应的值
e = *(L.elem + i - 1); //注意线性表中第i个元素的下标为i-1,下标为i的元素的下标为i+1
return 1;
}
//按值查找求下标
ElemType LocateElem(SqList L, ElemType e)
{
ElemType *p;
int i = 1;
p = L.elem;
//循环遍历，比较查找
while (i < L.length && (*p++ != e))
{
i++;
}
//判断返回值是否合理
if (i <= L.length)
{
return i;
}
else
{
return 0;
}
}
//插入数据
int ListInsert(SqList &L, ElemType e, int i)
{
/*插入算法：
first,将新元素e插入到L中逻辑序号为i的位置，对应于L.elem[i-1]
second,判断i的值是否合法（1<=i<=L.length+1）
third,second满足时，将L.elem[i-1...length-1]都后移一个位置
然后在L.elem[i-1]处插入e,然后对表中相关参量进行修改。*/
//这里先使用一种特别笨的算法进行插入操作，后续进一步学习会介绍更加简洁的算法，但是每一种算法的实现都要掌握
//判断i是否合法
ElemType *p;
if (i < 1 || i > L.length + 1)
{
return 0;
}
//这是一个拓展功能，使得数据无论如何都可以呗被存储。可有可无，有的学校不讲
if (L.length >= L.listsize)
{ //realloc函数自带释放原有空间的功能
ElemType *newbase = (ElemType *)realloc(L.elem,
(L.listsize + LIST_INCREMENT) * sizeof(ElemType));
if (!newbase)
{ //判断是否拓展成功
return 0;
}
L.elem = newbase;
L.listsize += LIST_INCREMENT; //修改表中相关参数的值
}
ElemType *q = &(L.elem[i - 1]); //q为插入的位置
for (p = &(L.elem[L.length - 1]); p >= q; --p) //先让p指向最后一个位置，然后一直遍历到q,
{
*(p + 1) = *p; //等价于p--;
*q = e; //让新的元素e插入到第i个位置，也就是数组的i-1处。
++L.length; //修改表中的相关参数
return 1;
}
}
//删除某个位置的元素
int ListDelete_Sq(SqList &L, int i, ElemType &e)
{
/*
1，删除顺序表中逻辑序号为i的元素
2，判断输入i是否合法
3，当2生效时，将L.elem[i.......length-1]的每一个
元素都前移一个位置，然后修改表中的相关参数。
*/
ElemType *p, *q;
if (i < 1 || i > L.length)
{ //step 1,判断
return 0;
}
p = &(L.elem[i - 1]); //step 2，定位
e = *p; //不是必须的
q = L.elem + L.length - 1; //表末尾的位置
for (++p; p <= q; ++p)
{ //step 3,修改
*(p - 1) = *p;
}
--L.length; //重要！！
return 1;
}
//显示当前表中的数据
void display(SqList L)
{
for (int i = 1; i <= L.length; i++)
{
printf("%d", L.elem[i - 1]);
}
}
|