1. 顺序表的操作(10题)
<h1>1. 构建并初始化一个顺序表</h1>
<p>为了简化问题,这里假设顺序表存储的是整数,最大容量是100:</p>
<pre><code class="language-c">#include&lt;stdio.h&gt; // 包含标准输入输出库,用于进行输入输出操作。
#include&lt;stdlib.h&gt; // 包含标准库,用于使用动态内存分配和其它标准函数。
// 定义一个结构体 Seq,用于表示顺序存储的集合。
typedef struct Seq{
int size; // 表示集合的最大容量。
int curNum; // 表示当前集合中元素的数量。
int element[100]; // 指向一个数组,用于存储集合中的元素。
}Seq;
Seq* init() {
// 动态分配内存空间给Seq结构体,并将其地址赋值给seq指针
Seq* seq = (Seq*)malloc(sizeof(Seq));
// 初始化当前元素数量为0
seq-&gt;curNum = 0;
// 设置集合的最大容量
seq-&gt;size = 100;
// 如果所有内存分配都成功,则返回Seq结构体的指针
return seq;
}
</code></pre>
<pre><code class="language-python">class Seq:
def __init__(self, size=100):
&quot;&quot;&quot;
初始化Seq类的实例
:param size: 序列的初始大小,默认为20
&quot;&quot;&quot;
self.size = size # 序列的大小
self.curNum = 0 # 当前已存储的元素数量
self.element = [None] * size # 初始化一个固定大小的列表,用于存储元素</code></pre>
<h1>2. 判断顺序表是不是空的和慢的</h1>
<pre><code class="language-c">int isempty(Seq* s){
// 检查传入的Seq结构体指针s是否为空
// 如果Seq结构体的curNum成员等于0,即没有元素,则返回1(真),表示集合为空
// 否则返回0(假),表示集合不为空
return s-&gt;curNum == 0;
}
int isfull(Seq* s){
// 检查传入的Seq结构体指针s是否指向一个有效的Seq结构体
// 返回s-&gt;curNum == s-&gt;size的结果,即检查当前元素数量是否等于最大容量
// 如果相等,返回1表示集合已满,否则返回0表示集合未满
return s-&gt;curNum == s-&gt;size;
}</code></pre>
<pre><code class="language-python">class Seq:
def isempty(self):
return self.curNum == 0
def isfull(self):
return self.curNum == self.size</code></pre>
<h1>3. 顺序表中添加一个元素</h1>
<pre><code class="language-c">int append(Seq* s, int m) {
// 检查传入的Seq结构体s是否已满
if(s-&gt;curNum == s-&gt;size){
// 如果已满,返回1表示操作失败
return 1;
}
// 将传入的值m追加到Seq结构体的元素数组的当前位置
s-&gt;element[s-&gt;curNum] = m;
// 更新Seq结构体的当前元素数量
s-&gt;curNum += 1;
// 返回0表示操作成功
return 0;
}</code></pre>
<pre><code class="language-python">class Seq:
def append(self, m):
if self.curNum == self.size:
return 1
self.element[self.curNum] = m
self.curNum += 1
return 0</code></pre>
<h1>4. 顺序表中插入一个元素</h1>
<pre><code class="language-c">int insert(Seq* s, int i, int m) {
// 检查插入位置i是否在有效范围内,如果不在则返回1表示失败
if(i &lt; 0 || i &gt; s-&gt;curNum) {
return 1;
}
// 检查Seq结构体是否已满,如果已满则打印信息并返回1表示失败
if(s-&gt;curNum == s-&gt;size) {
printf(&quot;满了&quot;);
return 1;
}
// 定义一个整型变量j,用于在循环中作为索引
int j;
// 从当前最后一个元素开始,向后移动元素,为新元素腾出空间
// 循环直到达到要插入新元素的位置i
for(j = s-&gt;curNum; j &gt; i; j--) {
s-&gt;element[j] = s-&gt;element[j-1];
}
// 在位置i插入新元素m
s-&gt;element[i] = m;
// 更新Seq结构体的当前元素数量
s-&gt;curNum += 1;
// 返回0表示插入操作成功
return 0;
}</code></pre>
<pre><code class="language-python">class Seq:
def insert(self, i, m):
if i &lt; 0 or i &gt; self.curNum:
return 1
if self.curNum == self.size:
return 1
for j in range(self.curNum, i, -1):
self.element[j] = self.element[j-1]
self.element[i] = m
self.curNum += 1
return 0
</code></pre>
<h1>5. 顺序表中删除最后一个元素</h1>
<pre><code class="language-c">int pop(Seq* s) {
// 检查传入的Seq结构体s是否为空
if(isempty(s)){
// 如果Seq结构体为空,则返回1表示操作失败
return 1;
}
// 将Seq结构体的当前元素数量curNum减1,实现弹出最后一个元素的效果
s-&gt;curNum -= 1;
// 返回0表示弹出操作成功
return 0;
}</code></pre>
<pre><code class="language-python">class Seq:
def pop(self):
if self.curNum == 0:
return 1
res = self.element[self.curNum-1]
self.element[self.curNum - 1] = None
self.curNum -= 1
return res</code></pre>
<h1>6. 顺序表中删除第i个元素</h1>
<pre><code class="language-c">int popi(Seq* s, int i) {
// 检查传入的Seq结构体s是否为空
if(s-&gt;curNum == 0){
// 如果Seq结构体为空,则返回1表示操作失败
return 1;
}
// 检查索引i是否在有效范围内
if(i &lt; 0 || i &gt;= s-&gt;curNum){
// 如果索引i无效,则返回1表示操作失败
return 1;
}
// 定义一个整型变量j,用于在循环中作为索引
int j;
// 从索引i开始,将索引i之后的元素向前移动一位,覆盖索引i处的元素
for(j = i; j &lt; s-&gt;curNum - 1; j++){
s-&gt;element[j] = s-&gt;element[j + 1];
}
// 将Seq结构体的当前元素数量curNum减1,实现弹出索引i处元素的效果
s-&gt;curNum -= 1;
// 返回0表示弹出操作成功
return 0;
}</code></pre>
<pre><code class="language-python">class Seq:
def popi(self, i):
if i &lt; 0 or i &gt;= self.curNum:
return 1
for j in range(i, self.curNum-1):
self.element[j] = self.element[j+1]
self.element[self.curNum-1] = None
self.curNum -= 1</code></pre>
<h1>7. 顺序表中修改第i个元素为n</h1>
<pre><code class="language-c">int set(Seq* s, int i, int n) {
// 检查给定的索引i是否在有效范围内,即是否在0到s-&gt;curNum(当前元素数量)之间
if(i &lt; 0 || i &gt;= s-&gt;curNum) {
// 如果索引i无效,返回1表示操作失败
return 1;
}
// 将索引i处的元素值设置为n
s-&gt;element[i] = n;
// 返回0表示设置操作成功
return 0;
}</code></pre>
<pre><code class="language-python">class Seq:
def set(self, i, n):
if i &lt; 0 or i &gt;= self.curNum:
return 1
self.element[i] = n</code></pre>
<h1>8. 获取顺序表的长度</h1>
<pre><code class="language-c">int length(Seq* s){ // 定义一个名为length的函数,接受一个指向Seq结构的指针作为参数
return s-&gt;curNum; // 返回Seq结构中表示当前元素数量的成员变量curNum的值
}
</code></pre>
<pre><code class="language-python">class Seq:
def length(self):
return self.curNum</code></pre>
<h1>9. 查找某个值第一次出现的位置</h1>
<pre><code class="language-c">int index_(Seq* s, int n){ // 定义一个名为index_的函数,接受一个指向Seq结构的指针和一个整数n作为参数
int i; // 声明一个循环计数器变量i
for(i=0; i&lt;s-&gt;curNum; i++){ // 遍历整个序列,从第一个元素到最后一个元素
if(s-&gt;element[i] == n){ // 如果当前元素等于目标值n
return i; // 则返回当前元素的索引
}
}
return -1; // 如果循环结束都没有找到目标值,则返回-1,表示序列中不存在目标值
}</code></pre>
<pre><code class="language-python">class Seq:
def index(self, x):
for i in range(self.curNum):
if self.element[i] == x:
return i
return -1
</code></pre>
<h1>10. 查找顺序表中最大值的索引</h1>
<pre><code class="language-c">int getMax(Seq* s){ // 定义一个名为getMax的函数,接受一个指向Seq结构的指针作为参数
if(s-&gt;curNum == 0){ // 检查序列是否为空
return -1; // 如果序列为空,则返回-1
}
int max = s-&gt;element[0]; // 初始化最大值为序列的第一个元素
int index = 0; // 初始化最大值的索引为0
int i; // 声明一个循环计数器变量i
for(i=1; i&lt;s-&gt;curNum; i++){ // 遍历从第二个元素到最后一个元素
if(s-&gt;element[i] &gt; max){ // 如果当前元素大于已知的最大值
max = s-&gt;element[i]; // 更新最大值为当前元素
index = i; // 更新最大值的索引为当前元素的索引
}
}
return index; // 返回找到的最大值的索引
}</code></pre>
<pre><code class="language-python">class Seq:
def max(self):
if self.curNum == 0:
return None
res = self.element[0]
for i in range(1, self.curNum):
if self.element[i] &gt; res:
res = self.element[i]
return res</code></pre>