数据结构与算法——编程实践

数据结构与算法课程团队,全力打造


1. 顺序表的操作(10题)

<h1>1. 构建并初始化一个顺序表</h1> <p>为了简化问题,这里假设顺序表存储的是整数,最大容量是100:</p> <pre><code class="language-c">#include&amp;lt;stdio.h&amp;gt; // 包含标准输入输出库,用于进行输入输出操作。 #include&amp;lt;stdlib.h&amp;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-&amp;gt;curNum = 0; // 设置集合的最大容量 seq-&amp;gt;size = 100; // 如果所有内存分配都成功,则返回Seq结构体的指针 return seq; } </code></pre> <pre><code class="language-python">class Seq: def __init__(self, size=100): &amp;quot;&amp;quot;&amp;quot; 初始化Seq类的实例 :param size: 序列的初始大小,默认为20 &amp;quot;&amp;quot;&amp;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-&amp;gt;curNum == 0; } int isfull(Seq* s){ // 检查传入的Seq结构体指针s是否指向一个有效的Seq结构体 // 返回s-&amp;gt;curNum == s-&amp;gt;size的结果,即检查当前元素数量是否等于最大容量 // 如果相等,返回1表示集合已满,否则返回0表示集合未满 return s-&amp;gt;curNum == s-&amp;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-&amp;gt;curNum == s-&amp;gt;size){ // 如果已满,返回1表示操作失败 return 1; } // 将传入的值m追加到Seq结构体的元素数组的当前位置 s-&amp;gt;element[s-&amp;gt;curNum] = m; // 更新Seq结构体的当前元素数量 s-&amp;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 &amp;lt; 0 || i &amp;gt; s-&amp;gt;curNum) { return 1; } // 检查Seq结构体是否已满,如果已满则打印信息并返回1表示失败 if(s-&amp;gt;curNum == s-&amp;gt;size) { printf(&amp;quot;满了&amp;quot;); return 1; } // 定义一个整型变量j,用于在循环中作为索引 int j; // 从当前最后一个元素开始,向后移动元素,为新元素腾出空间 // 循环直到达到要插入新元素的位置i for(j = s-&amp;gt;curNum; j &amp;gt; i; j--) { s-&amp;gt;element[j] = s-&amp;gt;element[j-1]; } // 在位置i插入新元素m s-&amp;gt;element[i] = m; // 更新Seq结构体的当前元素数量 s-&amp;gt;curNum += 1; // 返回0表示插入操作成功 return 0; }</code></pre> <pre><code class="language-python">class Seq:     def insert(self, i, m):         if i &amp;lt; 0 or i &amp;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-&amp;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-&amp;gt;curNum == 0){ // 如果Seq结构体为空,则返回1表示操作失败 return 1; } // 检查索引i是否在有效范围内 if(i &amp;lt; 0 || i &amp;gt;= s-&amp;gt;curNum){ // 如果索引i无效,则返回1表示操作失败 return 1; } // 定义一个整型变量j,用于在循环中作为索引 int j; // 从索引i开始,将索引i之后的元素向前移动一位,覆盖索引i处的元素 for(j = i; j &amp;lt; s-&amp;gt;curNum - 1; j++){ s-&amp;gt;element[j] = s-&amp;gt;element[j + 1]; } // 将Seq结构体的当前元素数量curNum减1,实现弹出索引i处元素的效果 s-&amp;gt;curNum -= 1; // 返回0表示弹出操作成功 return 0; }</code></pre> <pre><code class="language-python">class Seq:     def popi(self, i):         if i &amp;lt; 0 or i &amp;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-&amp;gt;curNum(当前元素数量)之间 if(i &amp;lt; 0 || i &amp;gt;= s-&amp;gt;curNum) { // 如果索引i无效,返回1表示操作失败 return 1; } // 将索引i处的元素值设置为n s-&amp;gt;element[i] = n; // 返回0表示设置操作成功 return 0; }</code></pre> <pre><code class="language-python">class Seq:     def set(self, i, n):         if i &amp;lt; 0 or i &amp;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-&amp;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&amp;lt;s-&amp;gt;curNum; i++){ // 遍历整个序列,从第一个元素到最后一个元素 if(s-&amp;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-&amp;gt;curNum == 0){ // 检查序列是否为空 return -1; // 如果序列为空,则返回-1 } int max = s-&amp;gt;element[0]; // 初始化最大值为序列的第一个元素 int index = 0; // 初始化最大值的索引为0 int i; // 声明一个循环计数器变量i for(i=1; i&amp;lt;s-&amp;gt;curNum; i++){ // 遍历从第二个元素到最后一个元素 if(s-&amp;gt;element[i] &amp;gt; max){ // 如果当前元素大于已知的最大值 max = s-&amp;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] &amp;gt; res:                 res = self.element[i]         return res</code></pre>

页面列表

ITEM_HTML