-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path27902.html
322 lines (284 loc) · 71.6 KB
/
27902.html
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no"><title>线性表（上） | magic-H</title><meta name="keywords" content="算法"><meta name="author" content="magic-H"><meta name="copyright" content="magic-H"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="一.定义线性表（List）：零个或多个数据元素的有限序列。 线性表首先它是一个序列，也就是说元素之间是有先来后到的。 若元素存在多个，则第一个元素无前驱，而最后一个元素无后继，其他元素都只有一个直接前驱，和只有一个直接后继。 线性表元素的个数n(n>=0）定义为线性表的长度，当n=0时，称为空表。 二.线性表的存储结构 1. 线性表的顺序存储结构（1）顺序存储：">
<meta property="og:type" content="article">
<meta property="og:title" content="线性表（上）">
<meta property="og:url" content="https://magic-h.top/27902.html">
<meta property="og:site_name" content="magic-H">
<meta property="og:description" content="一.定义线性表（List）：零个或多个数据元素的有限序列。 线性表首先它是一个序列，也就是说元素之间是有先来后到的。 若元素存在多个，则第一个元素无前驱，而最后一个元素无后继，其他元素都只有一个直接前驱，和只有一个直接后继。 线性表元素的个数n(n>=0）定义为线性表的长度，当n=0时，称为空表。 二.线性表的存储结构 1. 线性表的顺序存储结构（1）顺序存储：">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg">
<meta property="article:published_time" content="2022-07-27T00:00:00.000Z">
<meta property="article:modified_time" content="2023-06-09T02:57:26.202Z">
<meta property="article:author" content="magic-H">
<meta property="article:tag" content="算法">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg"><link rel="shortcut icon" href="/img/favicon.ico"><link rel="canonical" href="https://magic-h.top/27902"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//sdk.51.la"/><link rel="preconnect" href="//fonts.googleapis.com" crossorigin=""/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@6/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.css" media="print" onload="this.media='all'"><script>!function(p){"use strict";!function(t){var s=window,e=document,i=p,c="".concat("https:"===e.location.protocol?"https://":"http://","sdk.51.la/js-sdk-pro.min.js"),n=e.createElement("script"),r=e.getElementsByTagName("script")[0];n.type="text/javascript",n.setAttribute("charset","UTF-8"),n.async=!0,n.src=c,n.id="LA_COLLECT",i.d=n;var o=function(){s.LA.ids.push(i)};s.LA?s.LA.ids&&o():(s.LA=p,s.LA.ids=[],o()),r.parentNode.insertBefore(n,r)}()}({id:"Jl7ITgjGBeVbLmqO",ck:"Jl7ITgjGBeVbLmqO"});
</script><script>!(function(c,i,e,b){
var h=i.createElement("script");
var f=i.getElementsByTagName("script")[0];
h.type="text/javascript";
h.crossorigin=true;
h.onload=function(){new c[b]["Monitor"]().init({id:"Jl7IrsA7TWlXlR99"});};
f.parentNode.insertBefore(h,f);h.src=e;})(window,document,"https://sdk.51.la/perf/js-sdk-perf.min.js","LingQue");</script><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Titillium+Web&display=swap" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
root: '/',
algolia: undefined,
localSearch: {"path":"search.xml","languages":{"hits_empty":"找不到您查询的内容：${query}"}},
translate: undefined,
noticeOutdate: undefined,
highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
copy: {
success: '复制成功',
error: '复制错误',
noSupport: '浏览器不支持'
},
relativeDate: {
homepage: false,
post: false
},
runtime: '天',
date_suffix: {
just: '刚刚',
min: '分钟前',
hour: '小时前',
day: '天前',
month: '个月前'
},
copyright: undefined,
lightbox: 'mediumZoom',
Snackbar: {"chs_to_cht":"你已切换为繁体","cht_to_chs":"你已切换为简体","day_to_night":"你已切换为深色模式","night_to_day":"你已切换为浅色模式","bgLight":"#49b1f5","bgDark":"#1f1f1f","position":"bottom-left"},
source: {
justifiedGallery: {
js: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.js',
css: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.css'
}
},
isPhotoFigcaption: false,
islazyload: false,
isAnchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
title: '线性表（上）',
isPost: true,
isHome: false,
isHighlightShrink: false,
isToc: true,
postUpdate: '2023-06-09 02:57:26'
}</script><noscript><style type="text/css">
#nav {
opacity: 1
}
.justified-gallery img {
opacity: 1
}
#recent-posts time,
#post-meta time {
display: inline !important
}
</style></noscript><script>(win=>{
win.saveToLocal = {
set: function setWithExpiry(key, value, ttl) {
if (ttl === 0) return
const now = new Date()
const expiryDay = ttl * 86400000
const item = {
value: value,
expiry: now.getTime() + expiryDay,
}
localStorage.setItem(key, JSON.stringify(item))
},
get: function getWithExpiry(key) {
const itemStr = localStorage.getItem(key)
if (!itemStr) {
return undefined
}
const item = JSON.parse(itemStr)
const now = new Date()
if (now.getTime() > item.expiry) {
localStorage.removeItem(key)
return undefined
}
return item.value
}
}
win.getScript = url => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
script.onerror = reject
script.onload = script.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
script.onload = script.onreadystatechange = null
resolve()
}
document.head.appendChild(script)
})
win.activateDarkMode = function () {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
win.activateLightMode = function () {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
}
}
const t = saveToLocal.get('theme')
if (t === 'dark') activateDarkMode()
else if (t === 'light') activateLightMode()
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
if (asideStatus === 'hide') {
document.documentElement.classList.add('hide-aside')
} else {
document.documentElement.classList.remove('hide-aside')
}
}
const detectApple = () => {
if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
document.documentElement.classList.add('apple')
}
}
detectApple()
})(window)</script><link rel="stylesheet" href="/css/mycss.css"><script src="/js/sakura.js"></script><script src="/js/snow2.js"></script><meta name="generator" content="Hexo 6.1.0"><link rel="alternate" href="/atom.xml" title="magic-H" type="application/atom+xml">
</head><body><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="https://s4.ax1x.com/2022/02/18/HT4dgI.png" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data is-center"><div class="data-item"><a href="/archives/"><div class="headline">文章</div><div class="length-num">21</div></a></div><div class="data-item"><a href="/tags/"><div class="headline">标签</div><div class="length-num">9</div></a></div><div class="data-item"><a href="/categories/"><div class="headline">分类</div><div class="length-num">0</div></a></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/%E7%9B%B8%E5%86%8C/"><i class="fa-fw fa fa-video"></i><span> 相册</span></a></div><div class="menus_item"><a class="site-page" href="/questions/"><i class="fa-fw fa fa-video"></i><span> 答疑</span></a></div><div class="menus_item"><a class="site-page" href="/artitalk/"><i class="fa-fw fa fa-home"></i><span> 说说</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间线</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207182124785.png')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">magic-H</a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/%E7%9B%B8%E5%86%8C/"><i class="fa-fw fa fa-video"></i><span> 相册</span></a></div><div class="menus_item"><a class="site-page" href="/questions/"><i class="fa-fw fa fa-video"></i><span> 答疑</span></a></div><div class="menus_item"><a class="site-page" href="/artitalk/"><i class="fa-fw fa fa-home"></i><span> 说说</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间线</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">线性表（上）</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2022-07-27T00:00:00.000Z" title="发表于 2022-07-27 00:00:00">2022-07-27</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-06-09T02:57:26.202Z" title="更新于 2023-06-09 02:57:26">2023-06-09</time></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">2.6k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>9分钟</span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h1 id="一-定义"><a href="#一-定义" class="headerlink" title="一.定义"></a><code>一.定义</code></h1><p><strong>线性表（List）：零个或多个数据元素的有限序列。</strong></p>
<blockquote>
<p>线性表首先它是一个序列，也就是说元素之间是有先来后到的。</p>
<p>若元素存在多个，则第一个元素无前驱，而最后一个元素无后继，其他元素都只有一个直接前驱，和只有一个直接后继。</p>
<p>线性表元素的个数n(n>=0）定义为线性表的长度，当n=0时，称为空表。</p>
</blockquote>
<h1 id="二-线性表的存储结构"><a href="#二-线性表的存储结构" class="headerlink" title="二.线性表的存储结构"></a><code>二.线性表的存储结构</code></h1><p><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207272019351.png" alt="线性表"></p>
<h2 id="1-线性表的顺序存储结构"><a href="#1-线性表的顺序存储结构" class="headerlink" title="1. 线性表的顺序存储结构"></a>1. 线性表的顺序存储结构</h2><h3 id="（1）顺序存储："><a href="#（1）顺序存储：" class="headerlink" title="（1）顺序存储："></a>（1）顺序存储：</h3><p> <strong>用一组地址连续连续的存储单元来依次存放线性表中的数据。</strong></p>
<p><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207272032857.png" alt="在这里插入图片描述"></p>
<p> <strong>顺序存储结构示意图</strong></p>
<ul>
<li>顺序表是用一段<strong>物理地址连续的存储单元</strong>依次存储数据元素的线性结构，一般情况下采用数组存储。在数组<br>上完成数据的增删查改。</li>
<li>顺序表：<strong>可动态增长的数组，要求数据是连续存储的</strong></li>
</ul>
<h3 id="（2）顺序表的定义"><a href="#（2）顺序表的定义" class="headerlink" title="（2）顺序表的定义"></a>（2）顺序表的定义</h3><h4 id="1-静态顺序表：使用定长数组存储元素"><a href="#1-静态顺序表：使用定长数组存储元素" class="headerlink" title="1. 静态顺序表：使用定长数组存储元素"></a>1. 静态顺序表：使用定长数组存储元素</h4><p>缺陷：给小了不够用，给大了可能浪费，非常不实用</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> N 10</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">int</span> SLDataType;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">struct</span> <span class="title class_">SeqList</span></span><br><span class="line">{</span><br><span class="line"> SLDataType array[N]; <span class="comment">//定长数组</span></span><br><span class="line"> <span class="type">size_t</span> size; <span class="comment">//有效数据个数</span></span><br><span class="line">}SeqList;</span><br></pre></td></tr></table></figure>
<h4 id="2-动态顺序表：使用动态开辟的数组存储元素"><a href="#2-动态顺序表：使用动态开辟的数组存储元素" class="headerlink" title="2. 动态顺序表：使用动态开辟的数组存储元素"></a>2. 动态顺序表：使用动态开辟的数组存储元素</h4><p>动态顺序表可根据我们的需要分配空间大小<br>size 表示当前顺序表中已存放的数据个数<br>capacity 表示顺序表总共能够存放的数据个数<br>typedef int SLDataType; //类型重命名，后续要存储其它类型时方便更改</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="keyword">struct</span> <span class="title class_">SeqList</span></span><br><span class="line">{</span><br><span class="line"> SLDataType* a; <span class="comment">//指向动态开辟的数组</span></span><br><span class="line"> <span class="type">size_t</span> size; <span class="comment">//有效数据个数</span></span><br><span class="line"> <span class="type">size_t</span> capacity; <span class="comment">//容量大小</span></span><br><span class="line">}SeqList;</span><br></pre></td></tr></table></figure>
<h3 id="（3）顺序表的接口实现"><a href="#（3）顺序表的接口实现" class="headerlink" title="（3）顺序表的接口实现"></a>（3）顺序表的接口实现</h3><p>首先新建一个工程，此次用的是动态顺序表</p>
<ul>
<li>SeqList.h（顺序表的类型定义、接口函数声明、引用的头文件）</li>
<li>SeqList.cpp（顺序表接口函数的实现）</li>
<li>Test.cpp（主函数、测试顺序表各个接口功能）</li>
</ul>
<p><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207272137804.png" alt="image-20220727213733710"></p>
<h4 id="1-SeqList-h-头文件代码如下："><a href="#1-SeqList-h-头文件代码如下：" class="headerlink" title="1. SeqList.h 头文件代码如下："></a>1. SeqList.h 头文件代码如下：</h4><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">pragma</span> once <span class="comment">//防止头文件被二次引用</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string"><stdio.h></span> <span class="comment">/*perror, printf*/</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string"><assert.h></span> <span class="comment">/*assert*/</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string"><stdlib.h></span> <span class="comment">/*realloc*/</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">int</span> SLDataType; <span class="comment">//后续要存储其它类型时方便更改</span></span><br><span class="line"><span class="comment">//顺序表的动态存储</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">struct</span> <span class="title class_">SeqList</span></span><br><span class="line">{</span><br><span class="line"> SLDataType* a; <span class="comment">//指向动态开辟的数组</span></span><br><span class="line"> <span class="type">size_t</span> size; <span class="comment">//有效数据个数</span></span><br><span class="line"> <span class="type">size_t</span> capacity; <span class="comment">//容量大小</span></span><br><span class="line">}SeqList;</span><br><span class="line"></span><br><span class="line"><span class="comment">//初始化顺序表</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListInit</span><span class="params">(SeqList* psl)</span></span>;</span><br><span class="line"><span class="comment">//销毁顺序表</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListDestory</span><span class="params">(SeqList* psl)</span></span>;</span><br><span class="line"><span class="comment">//检查顺序表容量是否满了，好进行增容</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">CheckCapacity</span><span class="params">(SeqList* psl)</span></span>;</span><br><span class="line"><span class="comment">//顺序表尾插</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListPushBack</span><span class="params">(SeqList* psl, SLDataType x)</span></span>;<span class="comment">//O(1)</span></span><br><span class="line"><span class="comment">//顺序表尾删</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListPopBack</span><span class="params">(SeqList* psl)</span></span>;<span class="comment">//O(1)</span></span><br><span class="line"><span class="comment">//顺序表头插</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListPushFront</span><span class="params">(SeqList* psl, SLDataType x)</span></span>;<span class="comment">//O(n)</span></span><br><span class="line"><span class="comment">//顺序表头删</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListPopFront</span><span class="params">(SeqList* psl)</span></span>;<span class="comment">//O(n)</span></span><br><span class="line"><span class="comment">//打印顺序表</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListPrint</span><span class="params">(<span class="type">const</span> SeqList* psl)</span></span>;</span><br><span class="line"><span class="comment">//在顺序表中查找指定值</span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">SeqListFind</span><span class="params">(<span class="type">const</span> SeqList* psl, SLDataType x)</span></span>;</span><br><span class="line"><span class="comment">//在顺序表指定下标位置插入数据</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListInsert</span><span class="params">(SeqList* psl, <span class="type">size_t</span> pos, SLDataType x)</span></span>;</span><br><span class="line"><span class="comment">//在顺序表中删除指定下标位置的数据</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListErase</span><span class="params">(SeqList* psl, <span class="type">size_t</span> pos)</span></span>;</span><br><span class="line"><span class="comment">//查看顺序表中数据个数</span></span><br><span class="line"><span class="function"><span class="type">size_t</span> <span class="title">SeqListSize</span><span class="params">(<span class="type">const</span> SeqList* psl)</span></span>;</span><br><span class="line"><span class="comment">//修改指定下标位置的数据</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListAt</span><span class="params">(SeqList* psl, <span class="type">size_t</span> pos, SLDataType x)</span></span>;</span><br></pre></td></tr></table></figure>
<h4 id="2-SeqList-c-中各个接口函数的实现"><a href="#2-SeqList-c-中各个接口函数的实现" class="headerlink" title="2. SeqList.c 中各个接口函数的实现"></a>2. <strong>SeqList.c 中各个接口函数的实现</strong></h4><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//1、初始化顺序表</span></span><br><span class="line"><span class="comment">//记得一定要加上断言，防止传进来的指针为空</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListInit</span><span class="params">(SeqList* psl)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl != <span class="literal">NULL</span>); <span class="comment">//断言</span></span><br><span class="line"></span><br><span class="line"> psl->a = <span class="literal">NULL</span>; <span class="comment">//初始顺序表为空</span></span><br><span class="line"> psl->size = <span class="number">0</span>; <span class="comment">//初始数据个数为0</span></span><br><span class="line"> psl->capacity = <span class="number">0</span>; <span class="comment">//初始空间容量为0</span></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="number">2</span>、销毁（释放）顺序表</span><br><span class="line">记得一定要加上断言，防止传进来的指针为空</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListDestory</span><span class="params">(SeqList* psl)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl != <span class="literal">NULL</span>); <span class="comment">//断言</span></span><br><span class="line"></span><br><span class="line"> <span class="built_in">free</span>(psl->a); <span class="comment">//释放动态开辟的空间</span></span><br><span class="line"> psl->a = <span class="literal">NULL</span>; <span class="comment">//置空</span></span><br><span class="line"> psl->size = <span class="number">0</span>; <span class="comment">//数据个数置0</span></span><br><span class="line"> psl->capacity = <span class="number">0</span>; <span class="comment">//空间容量大小置0</span></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">//3、检查顺序表容量是否满了，好进行增容</span></span><br><span class="line"><span class="comment">//一般情况下，为了避免频繁的增容，当空间满了后，我们不会一个一个的去增，而是一次增容 2 倍，也避免增容太大浪费空间，2 倍是一个折中的选择。</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">CheckCapacity</span><span class="params">(SeqList* psl)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl != <span class="literal">NULL</span>); <span class="comment">//断言</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> (psl->size == psl->capacity) <span class="comment">//检查容量，满了则增容</span></span><br><span class="line"> {</span><br><span class="line"> <span class="type">size_t</span> newcapacity; <span class="comment">//新容量</span></span><br><span class="line"> <span class="keyword">if</span> (psl->capacity == <span class="number">0</span>)</span><br><span class="line"> newcapacity = psl->capacity = <span class="number">4</span>; <span class="comment">//原来容量为0，扩容为4</span></span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> newcapacity = <span class="number">2</span> * psl->capacity; <span class="comment">//原来容量不为0，扩容为原来的2倍</span></span><br><span class="line"> </span><br><span class="line"> SLDataType* p = (SLDataType*)<span class="built_in">realloc</span>(psl->a, newcapacity*<span class="built_in">sizeof</span>(SLDataType)); <span class="comment">//扩容</span></span><br><span class="line"> <span class="keyword">if</span> (p == <span class="literal">NULL</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">perror</span>(<span class="string">"realloc"</span>);</span><br><span class="line"> <span class="built_in">exit</span>(<span class="number">-1</span>);</span><br><span class="line"> }</span><br><span class="line"> psl->a = p; <span class="comment">// p 不为空，开辟成功</span></span><br><span class="line"> psl->capacity = newcapacity; <span class="comment">//更新容量</span></span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">//3、顺序表尾插</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListPushBack</span><span class="params">(SeqList* psl, SLDataType x)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl != <span class="literal">NULL</span>); <span class="comment">//断言</span></span><br><span class="line"></span><br><span class="line"> <span class="built_in">CheckCapacity</span>(psl); <span class="comment">//检查顺序表容量是否已满</span></span><br><span class="line"></span><br><span class="line"> psl->a[psl->size] = x; <span class="comment">//尾插数据</span></span><br><span class="line"> psl->size++; <span class="comment">//有效数据个数+1</span></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">//4、顺序表尾删</span></span><br><span class="line"><span class="comment">//不知道 SLDataType 是什么类型的数据，不能冒然的将顺序表最后一个数据赋值为 0，我们只需将有效数据个数 size 减 1 即可达到尾删的目的。</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListPopBack</span><span class="params">(SeqList* psl)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl != <span class="literal">NULL</span>); <span class="comment">//断言</span></span><br><span class="line"> <span class="built_in">assert</span>(psl->size > <span class="number">0</span>); <span class="comment">//顺序表不能为空</span></span><br><span class="line"></span><br><span class="line"> <span class="comment">//不知道SLDataType是什么类型的数据，不能冒然的赋值为0</span></span><br><span class="line"> <span class="comment">//psl->a[psl->size - 1] = 0;</span></span><br><span class="line"> psl->size--; <span class="comment">//有效数据个数-1</span></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">//5、顺序表头插</span></span><br><span class="line"><span class="comment">//因为顺序表是连续存储的，所以头插时要依次挪动数据</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> </span></span><br><span class="line"><span class="function"> <span class="title">SeqListPushFront</span><span class="params">(SeqList* psl, SLDataType x)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl); <span class="comment">//断言</span></span><br><span class="line"> <span class="built_in">CheckCapacity</span>(psl); <span class="comment">//检查顺序表容量是否已满</span></span><br><span class="line"> </span><br><span class="line"> <span class="type">int</span> i = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (i = psl->size - <span class="number">1</span>; i >= <span class="number">0</span>; i--) <span class="comment">//顺序表中[0,size-1]的元素依次向后挪动一位</span></span><br><span class="line"> {</span><br><span class="line"> psl->a[i + <span class="number">1</span>] = psl->a[i];</span><br><span class="line"> }</span><br><span class="line"> psl->a[<span class="number">0</span>] = x; <span class="comment">//头插数据</span></span><br><span class="line"> psl->size++; <span class="comment">//有效数据个数+1</span></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">//6、顺序表头删</span></span><br><span class="line"><span class="comment">//因为顺序表是连续存储的，所以头删时要依次挪动数据</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListPopFront</span><span class="params">(SeqList* psl)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl); <span class="comment">//断言</span></span><br><span class="line"> <span class="built_in">assert</span>(psl->size > <span class="number">0</span>); <span class="comment">//顺序表不能为空</span></span><br><span class="line"></span><br><span class="line"> <span class="type">int</span> i = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (i = <span class="number">1</span>; i < psl->size; i++) <span class="comment">//顺序表中[1,size-1]的元素依次向前挪动一位</span></span><br><span class="line"> {</span><br><span class="line"> psl->a[i - <span class="number">1</span>] = psl->a[i];</span><br><span class="line"> }</span><br><span class="line"> psl->size--; <span class="comment">//有效数据个数-1</span></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">//7、打印顺序表</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListPrint</span><span class="params">(<span class="type">const</span> SeqList* psl)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl != <span class="literal">NULL</span>); <span class="comment">//断言</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> (psl->size == <span class="number">0</span>) <span class="comment">//判断顺序表是否为空</span></span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"顺序表为空\n"</span>);</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="type">int</span> i = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (i = <span class="number">0</span>; i < psl->size; i++) <span class="comment">//打印顺序表</span></span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d "</span>, psl->a[i]);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"\n"</span>);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">//8、在顺序表中查找指定值</span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">SeqListFind</span><span class="params">(<span class="type">const</span> SeqList* psl, SLDataType x)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl); <span class="comment">//断言</span></span><br><span class="line"></span><br><span class="line"> <span class="type">int</span> i = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (i = <span class="number">0</span>; i < psl->size; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (psl->a[i] == x)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">return</span> i; <span class="comment">//查找到，返回该值在数组中的下标</span></span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">-1</span>; <span class="comment">//没有查找到</span></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">//9、在顺序表指定下标位置插入数据（要注意下int与size_t间的转换问题）</span></span><br><span class="line"><span class="comment">//将指定位置后的所有数据依次向后挪动一位，初始代码如下：</span></span><br><span class="line"></span><br><span class="line"><span class="type">int</span> i = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">for</span> (i = psl->size - <span class="number">1</span>; i >= pos; i--)</span><br><span class="line"> psl->a[i + <span class="number">1</span>] = psl->a[i];</span><br><span class="line"></span><br><span class="line"><span class="comment">/*原先这种写法，当顺序表为空 size = 0 时，会导致 i = -1，</span></span><br><span class="line"><span class="comment">执行 i >= pos 时，i 被算术转换成无符号数，而无符号数的 -1 是一个值很大的正数，</span></span><br><span class="line"><span class="comment">远大于 pos，满足条件进入循环，会造成越界访问</span></span><br><span class="line"><span class="comment">注：转换并不会改变 i 本身的值，而是执行 i >= pos 时，生成一个临时的值与 pos 比较</span></span><br><span class="line"><span class="comment">如果在顺序表头部插入数据 pos = 0，i 最终也会减减变成 -1，被算术转换后变成一个很大的数</span></span><br><span class="line"><span class="comment">总结：避免负数给到无符号数，或者避免有符号数变成负数后，被算术转换或整型提升后，变成一个很大的数</span></span><br><span class="line"><span class="comment">下面这样写就避免 i 变成 -1 负数了*/</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListInsert</span><span class="params">(SeqList* psl, <span class="type">size_t</span> pos, SLDataType x)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl); <span class="comment">//断言</span></span><br><span class="line"> <span class="built_in">assert</span>(pos >= <span class="number">0</span> && pos <= psl->size); <span class="comment">//检查pos下标的合法性</span></span><br><span class="line"></span><br><span class="line"> <span class="built_in">CheckCapacity</span>(psl); <span class="comment">//检查顺序表容量是否已满</span></span><br><span class="line"></span><br><span class="line"> <span class="type">size_t</span> i = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (i = psl->size; i > pos; i--) <span class="comment">//将pos位置后面的数据依次向后挪动一位</span></span><br><span class="line"> {</span><br><span class="line"> psl->a[i] = psl->a[i - <span class="number">1</span>];</span><br><span class="line"> }</span><br><span class="line"> psl->a[pos] = x; <span class="comment">//插入数据</span></span><br><span class="line"> psl->size++; <span class="comment">//有效数据个数+1</span></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">/*实现了此接口，顺序表头插相当于在下标为 0 位置处插入数据，可以改进下顺序表头插的代码：</span></span><br><span class="line"><span class="comment">void SeqListPushFront(SeqList* psl, SLDataType x)</span></span><br><span class="line"><span class="comment">{</span></span><br><span class="line"><span class="comment"> SeqListInsert(psl, 0, x); //改造头插接口</span></span><br><span class="line"><span class="comment">}*/</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//10、在顺序表中删除指定下标位置的数据</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListErase</span><span class="params">(SeqList* psl, <span class="type">size_t</span> pos)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl); <span class="comment">//断言</span></span><br><span class="line"> <span class="built_in">assert</span>(psl->size > <span class="number">0</span>); <span class="comment">//顺序表不能为空</span></span><br><span class="line"> <span class="built_in">assert</span>(pos >= <span class="number">0</span> && pos < psl->size); <span class="comment">//检查pos下标的合法性</span></span><br><span class="line"></span><br><span class="line"> <span class="type">size_t</span> i = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (i = pos + <span class="number">1</span>; i < psl->size; i++) <span class="comment">//将pos位置后面的数据依次向前挪动一位</span></span><br><span class="line"> {</span><br><span class="line"> psl->a[i - <span class="number">1</span>] = psl->a[i];</span><br><span class="line"> }</span><br><span class="line"> psl->size--; <span class="comment">//有效数据个数-1</span></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">/*实现了此接口，顺序表头删相当于删除下标为 0 位置处的数据，可以改进下顺序表头删的代码：</span></span><br><span class="line"><span class="comment">//顺序表头删</span></span><br><span class="line"><span class="comment">void SeqListPopFront(SeqList* psl)</span></span><br><span class="line"><span class="comment">{</span></span><br><span class="line"><span class="comment"> SeqListErase(psl, 0); //改造头删接口</span></span><br><span class="line"><span class="comment">}*/</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//11、查看顺序表中有效数据个数</span></span><br><span class="line"><span class="comment">//可能大家会有一个疑问，我在主函数里面直接通过定义的结构体变量直接访问就好了呀，为啥还要弄一个函数嘞</span></span><br><span class="line"><span class="comment">//在数据结构中有一个约定，如果要访问或修改数据结构中的数据，不要直接去访问，要去调用它的函数来访问和修改，这样更加规范安全，也更方便检查是否出现了越界等一些错误情况</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">size_t</span> <span class="title">SeqListSize</span><span class="params">(<span class="type">const</span> SeqList* psl)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl); <span class="comment">//断言</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> psl->size;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">//12、修改指定下标位置的数据</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">SeqListAt</span><span class="params">(SeqList* psl, <span class="type">size_t</span> pos, SLDataType x)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">assert</span>(psl); <span class="comment">//断言</span></span><br><span class="line"> <span class="built_in">assert</span>(psl->size > <span class="number">0</span>); <span class="comment">//顺序表不能为空</span></span><br><span class="line"> <span class="built_in">assert</span>(pos >= <span class="number">0</span> && pos < psl->size); <span class="comment">//检查pos下标的合法性</span></span><br><span class="line"></span><br><span class="line"> psl->a[pos] = x; <span class="comment">//修改pos下标处对应的数据</span></span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">magic-H</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://magic-h.top/27902.html">https://magic-h.top/27902.html</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://magic-H.top" target="_blank">magic-H</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E7%AE%97%E6%B3%95/">算法</a></div><div class="post_share"><div class="social-share" data-image="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/64644.html"><img class="prev-cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">线性表（下）</div></div></a></div><div class="next-post pull-right"><a href="/58601.html"><img class="next-cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">时间复杂度</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/2567.html" title="Java刷题笔记（三）"><img class="cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291555693.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-07-30</div><div class="title">Java刷题笔记（三）</div></div></a></div><div><a href="/62779.html" title="Java刷题笔记（二）"><img class="cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291555693.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-07-29</div><div class="title">Java刷题笔记（二）</div></div></a></div><div><a href="/58601.html" title="时间复杂度"><img class="cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-07-26</div><div class="title">时间复杂度</div></div></a></div><div><a href="/64644.html" title="线性表（下）"><img class="cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-07-28</div><div class="title">线性表（下）</div></div></a></div></div></div><hr/><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="fas fa-comments fa-fw"></i><span> 评论</span></div></div><div class="comment-wrap"><div><div id="waline-wrap"></div></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="https://s4.ax1x.com/2022/02/18/HT4dgI.png" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">magic-H</div><div class="author-info__description"></div></div><div class="card-info-data is-center"><div class="card-info-data-item"><a href="/archives/"><div class="headline">文章</div><div class="length-num">21</div></a></div><div class="card-info-data-item"><a href="/tags/"><div class="headline">标签</div><div class="length-num">9</div></a></div><div class="card-info-data-item"><a href="/categories/"><div class="headline">分类</div><div class="length-num">0</div></a></div></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/magic-H728"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/magic-H728" target="_blank" title="Github"><i class="fab fa-github"></i></a><a class="social-icon" href="mailto:[email protected]" target="_blank" title="Email"><i class="fas fa-envelope"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content">This is my Blog</div></div><div class="card-widget"><div class="item-headline"><i></i><span></span></div><div class="item-content"></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%B8%80-%E5%AE%9A%E4%B9%89"><span class="toc-text">一.定义</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C-%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84"><span class="toc-text">二.线性表的存储结构</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#1-%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84"><span class="toc-text">1. 线性表的顺序存储结构</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%EF%BC%881%EF%BC%89%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%EF%BC%9A"><span class="toc-text">（1）顺序存储：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%EF%BC%882%EF%BC%89%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E5%AE%9A%E4%B9%89"><span class="toc-text">（2）顺序表的定义</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#1-%E9%9D%99%E6%80%81%E9%A1%BA%E5%BA%8F%E8%A1%A8%EF%BC%9A%E4%BD%BF%E7%94%A8%E5%AE%9A%E9%95%BF%E6%95%B0%E7%BB%84%E5%AD%98%E5%82%A8%E5%85%83%E7%B4%A0"><span class="toc-text">1. 静态顺序表：使用定长数组存储元素</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2-%E5%8A%A8%E6%80%81%E9%A1%BA%E5%BA%8F%E8%A1%A8%EF%BC%9A%E4%BD%BF%E7%94%A8%E5%8A%A8%E6%80%81%E5%BC%80%E8%BE%9F%E7%9A%84%E6%95%B0%E7%BB%84%E5%AD%98%E5%82%A8%E5%85%83%E7%B4%A0"><span class="toc-text">2. 动态顺序表：使用动态开辟的数组存储元素</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%EF%BC%883%EF%BC%89%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E6%8E%A5%E5%8F%A3%E5%AE%9E%E7%8E%B0"><span class="toc-text">（3）顺序表的接口实现</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#1-SeqList-h-%E5%A4%B4%E6%96%87%E4%BB%B6%E4%BB%A3%E7%A0%81%E5%A6%82%E4%B8%8B%EF%BC%9A"><span class="toc-text">1. SeqList.h 头文件代码如下：</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2-SeqList-c-%E4%B8%AD%E5%90%84%E4%B8%AA%E6%8E%A5%E5%8F%A3%E5%87%BD%E6%95%B0%E7%9A%84%E5%AE%9E%E7%8E%B0"><span class="toc-text">2. SeqList.c 中各个接口函数的实现</span></a></li></ol></li></ol></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/25737.html" title="数据结构OJ"><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202301131413619.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="数据结构OJ"/></a><div class="content"><a class="title" href="/25737.html" title="数据结构OJ">数据结构OJ</a><time datetime="2023-01-13T00:00:00.000Z" title="发表于 2023-01-13 00:00:00">2023-01-13</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/48665.html" title="Notion知识体系管理工具"><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207311705467.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Notion知识体系管理工具"/></a><div class="content"><a class="title" href="/48665.html" title="Notion知识体系管理工具">Notion知识体系管理工具</a><time datetime="2022-07-31T00:00:00.000Z" title="发表于 2022-07-31 00:00:00">2022-07-31</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2567.html" title="Java刷题笔记（三）"><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291555693.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Java刷题笔记（三）"/></a><div class="content"><a class="title" href="/2567.html" title="Java刷题笔记（三）">Java刷题笔记（三）</a><time datetime="2022-07-30T00:00:00.000Z" title="发表于 2022-07-30 00:00:00">2022-07-30</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/62779.html" title="Java刷题笔记（二）"><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291555693.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Java刷题笔记（二）"/></a><div class="content"><a class="title" href="/62779.html" title="Java刷题笔记（二）">Java刷题笔记（二）</a><time datetime="2022-07-29T00:00:00.000Z" title="发表于 2022-07-29 00:00:00">2022-07-29</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/64644.html" title="线性表（下）"><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="线性表（下）"/></a><div class="content"><a class="title" href="/64644.html" title="线性表（下）">线性表（下）</a><time datetime="2022-07-28T00:00:00.000Z" title="发表于 2022-07-28 00:00:00">2022-07-28</time></div></div></div></div></div></div></main><footer id="footer" style="background-image: url('https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207182124785.png')"><div id="footer-wrap"><div class="copyright">©2022 - 2023 By magic-H</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><img src="https://gcore.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207181316087.png">
<a href="http://www.beian.miit.gov.cn/" style="color:#f72b07" target="_blank">粤ICP备2022027428号</a><div class="footer_custom_text">Hi, welcome to my <a href="magic-h.top">blog</a>!</div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><a id="to_comment" href="#post-comment" title="直达评论"><i class="fas fa-comments"></i></a><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">本地搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i><span> 数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div><hr/><div id="local-search-results"></div></div></div><div id="search-mask"></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="https://cdn.jsdelivr.net/npm/medium-zoom/dist/medium-zoom.min.js"></script><script src="https://cdn.jsdelivr.net/npm/instant.page/instantpage.min.js" type="module"></script><script src="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.js"></script><script>function panguFn () {
if (typeof pangu === 'object') pangu.autoSpacingPage()
else {
getScript('https://cdn.jsdelivr.net/npm/pangu/dist/browser/pangu.min.js')
.then(() => {
pangu.autoSpacingPage()
})
}
}
function panguInit () {
if (false){
GLOBAL_CONFIG_SITE.isPost && panguFn()
} else {
panguFn()
}
}
document.addEventListener('DOMContentLoaded', panguInit)</script><script src="/js/search/local-search.js"></script><div class="js-pjax"><script>(() => {
const $mermaidWrap = document.querySelectorAll('#article-container .mermaid-wrap')
if ($mermaidWrap.length) {
window.runMermaid = () => {
window.loadMermaid = true
const theme = document.documentElement.getAttribute('data-theme') === 'dark' ? 'dark' : 'default'
Array.from($mermaidWrap).forEach((item, index) => {
const mermaidSrc = item.firstElementChild
const mermaidThemeConfig = '%%{init:{ \'theme\':\'' + theme + '\'}}%%\n'
const mermaidID = 'mermaid-' + index
const mermaidDefinition = mermaidThemeConfig + mermaidSrc.textContent
mermaid.mermaidAPI.render(mermaidID, mermaidDefinition, (svgCode) => {
mermaidSrc.insertAdjacentHTML('afterend', svgCode)
})
})
}
const loadMermaid = () => {
window.loadMermaid ? runMermaid() : getScript('https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js').then(runMermaid)
}
window.pjax ? loadMermaid() : document.addEventListener('DOMContentLoaded', loadMermaid)
}
})()</script><script>function loadWaline () {
function initWaline () {
const waline = new Waline(Object.assign({
el: '#waline-wrap',
serverURL: 'https://magic-h-mr0qem8oh-magic-h728.vercel.app/',
path: location.pathname,
visitor: false,
dark: 'html[data-theme="dark"]'
}, null))
}
if (typeof Waline === 'function') initWaline()
else getScript('https://cdn.jsdelivr.net/npm/@waline/client/dist/Waline.min.js').then(initWaline)
}
if ('Waline' === 'Waline' || !false) {
if (false) btf.loadComment(document.getElementById('waline-wrap'),loadWaline)
else setTimeout(loadWaline, 0)
} else {
function loadOtherComment () {
loadWaline()
}
}</script></div><canvas class="fireworks" mobile="false"></canvas><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/fireworks.min.js"></script><script defer="defer" id="fluttering_ribbon" mobile="true" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/canvas-fluttering-ribbon.min.js"></script><script id="canvas_nest" defer="defer" color="200,100,255" opacity="0.7" zIndex="-1" count="118" mobile="true" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/canvas-nest.min.js"></script><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/activate-power-mode.min.js"></script><script>POWERMODE.colorful = true;
POWERMODE.shake = false;
POWERMODE.mobile = false;
document.body.addEventListener('input', POWERMODE);
</script><script src="https://cdn.jsdelivr.net/npm/pjax/pjax.min.js"></script><script>let pjaxSelectors = ["title","#config-diff","#body-wrap","#rightside-config-hide","#rightside-config-show",".js-pjax"]
var pjax = new Pjax({
elements: 'a:not([target="_blank"]):not([href="/music/"]):not([href="/no-pjax/"])',
selectors: pjaxSelectors,
cacheBust: false,
analytics: false,
scrollRestoration: false
})
document.addEventListener('pjax:send', function () {
// removeEventListener scroll
window.tocScrollFn && window.removeEventListener('scroll', window.tocScrollFn)
window.scrollCollect && window.removeEventListener('scroll', scrollCollect)
typeof preloader === 'object' && preloader.initLoading()
document.getElementById('rightside').style.cssText = "opacity: ''; transform: ''"
if (window.aplayers) {
for (let i = 0; i < window.aplayers.length; i++) {
if (!window.aplayers[i].options.fixed) {
window.aplayers[i].destroy()
}
}
}
typeof typed === 'object' && typed.destroy()
//reset readmode
const $bodyClassList = document.body.classList
$bodyClassList.contains('read-mode') && $bodyClassList.remove('read-mode')
})
document.addEventListener('pjax:complete', function () {
window.refreshFn()
document.querySelectorAll('script[data-pjax]').forEach(item => {
const newScript = document.createElement('script')
const content = item.text || item.textContent || item.innerHTML || ""
Array.from(item.attributes).forEach(attr => newScript.setAttribute(attr.name, attr.value))
newScript.appendChild(document.createTextNode(content))
item.parentNode.replaceChild(newScript, item)
})
GLOBAL_CONFIG.islazyload && window.lazyLoadInstance.update()
typeof chatBtnFn === 'function' && chatBtnFn()
typeof panguInit === 'function' && panguInit()
// google analytics
typeof gtag === 'function' && gtag('config', '', {'page_path': window.location.pathname});
// baidu analytics
typeof _hmt === 'object' && _hmt.push(['_trackPageview',window.location.pathname]);
typeof loadMeting === 'function' && document.getElementsByClassName('aplayer').length && loadMeting()
// prismjs
typeof Prism === 'object' && Prism.highlightAll()
typeof preloader === 'object' && preloader.endLoading()
})
document.addEventListener('pjax:error', (e) => {
if (e.request.status === 404) {
pjax.loadUrl('/404.html')
}
})</script></div></body></html>