线性表-顺序存储

道道悟 發表於 2025-7-25 15:09:00

<h1 id="顺序表的实现与测试-c语言版">顺序表的实现与测试-C语言版</h1>
<h2 id="一顺序表概念">一、顺序表概念</h2>
<blockquote>
<p>顺序表（Sequential List）是线性表的一种存储方式，指的是采用顺序存储结构的线性表。在顺序表中，数据元素按照它们的逻辑顺序依次存放在一段地址连续的存储单元中。这种存储方式允许通过数学计算快速定位到任何一个元素的位置，从而支持随机访问。但是，顺序表的插入和删除操作可能需要移动大量元素以保持数据元素的连续存放。</p>
<p>总结特点如下：</p>
<ul>
<li>元素在内存中连续存储</li>
<li>可以通过下标快速访问元素（时间复杂度 O (1)）</li>
<li>插入和删除元素可能需要移动大量元素（时间复杂度 O (n)）</li>
</ul>
</blockquote>
<hr>
<p><img src="https://img2024.cnblogs.com/blog/3677701/202507/3677701-20250725150635097-235380583.png" alt="image" loading="lazy"></p>
<h2 id="二顺序表实现代码">二、顺序表实现代码</h2>
<h3 id="顺序表的关键参数">顺序表的关键参数</h3>
<p>为了管理顺序表，需要记录三个参数：</p>
<ol>
<li>存储元素的数组地址（<code>Primary_Addr</code>）</li>
<li>顺序表的最大容量（<code>Size</code>）</li>
<li>最后一个元素的下标（<code>Last</code>，初始值为 - 1 表示空表）</li>
</ol>
<blockquote>
<p>我们用结构体封装这些参数：</p>
</blockquote>
<pre><code class="language-c">
// 定义元素类型（方便后续修改为其他类型，如float）
typedef int DataType_t;

// 顺序表管理结构体
typedef struct SequenceList
{
DataType_t *Primary_Addr; // 元素存储地址
unsigned int Size;    // 最大容量
int       Last;    // 最后一个元素下标
} SequenceList_t;
</code></pre>
<h3 id="初始化函数">初始化函数</h3>
<p>初始化是使用顺序表的第一步，作用是申请内存并初始化参数：</p>
<pre><code class="language-c">
// 初始化顺序表，参数为容量大小
SequenceList_t* SequenceList_init(unsigned int size)
{
// 1. 申请管理结构体的内存
SequenceList_t *SeqList_manager = (SequenceList_t *)calloc(1,sizeof(SequenceList_t));
if(SeqList_manager == NULL){
   perror("申请管理结构体失败！");
   exit(-1);
}

// 2. 申请存储元素的数组内存
SeqList_manager->Primary_Addr = (DataType_t *)calloc(size,sizeof(DataType_t));
if(SeqList_manager->Primary_Addr == NULL){
   perror("申请元素数组失败！");
   free(SeqList_manager); // 先释放已申请的结构体
   exit(-1);
}

// 3. 初始化参数
SeqList_manager->Size = size;
SeqList_manager->Last = -1; // 空表标记

return SeqList_manager;
}
</code></pre>
<h3 id="状态判断函数">状态判断函数</h3>
<p>插入 / 删除前需要先判断表是否满 / 空：</p>
<pre><code class="language-c">
// 判断顺序表是否已满
bool SeqListIsfull(SequenceList_t *SeqList_manager)
{
// 最后一个元素下标+1 等于容量时，表满
return (SeqList_manager->Last +1 == SeqList_manager->Size)?true:false;
}

// 判断顺序表是否为空
bool SeqListIsEmpty(SequenceList_t *SeqList_manager)
{
// 最后一个元素下标为-1时，表空
return (SeqList_manager->Last == -1)?true:false;
}
</code></pre>
<h3 id="插入功能">插入功能</h3>
<h4 id="1-尾部插入">1. 尾部插入</h4>
<p>尾部插入最简单，直接在最后一个元素后添加：</p>
<pre><code class="language-c">
// 尾部添加元素
bool SeqList_TailAdd(SequenceList_t *SeqList_manager,DataType_t data)
{
// 先判断是否已满
if(SeqListIsfull(SeqList_manager)){
   printf("顺序表已满，无法添加！\n");
   return false;
}

// Last先+1，再赋值（空表时Last从-1变为0）
SeqList_manager->Primary_Addr[++SeqList_manager->Last] = data;
return true;
}
</code></pre>
<h4 id="2-头部插入">2. 头部插入</h4>
<p>头部插入需要先将所有元素后移一位，再在头部插入：</p>
<pre><code class="language-c">
// 头部添加元素
bool SeqList_HeadAdd(SequenceList_t *SeqList_manager,DataType_t data)
{
if(SeqListIsfull(SeqList_manager)){
   printf("顺序表已满，无法添加！\n");
   return false;
}

// 所有元素后移一位（从最后一个元素开始）
for(int i = SeqList_manager->Last;i >= 0;i--){
   SeqList_manager->Primary_Addr = SeqList_manager->Primary_Addr;
}

// 头部插入新元素
SeqList_manager->Primary_Addr = data;
SeqList_manager->Last++; // 更新最后一个元素下标
return true;
}
</code></pre>
<h4 id="3-有序插入考研题目">3. 有序插入（考研题目）</h4>
<blockquote>
<p>原题目：已经知道一个顺序表，其中的元素递增有序排列，设计一个算法，插入一个元素x(x是int型)后保持该顺序表依然递增有序</p>
</blockquote>
<pre><code class="language-c">void SeqList_Insert(SequenceList_t *SeqList_manager,int x)
{
// 先判断是否已满
if (SeqListIsfull(SeqList_manager)) {
   printf("顺序表已满，无法插入！\n");
   return;
}
// 1. 找到插入位置（第一个比x大的元素下标）
int Temp = -1; // 初始为-1，表示x是最大元素
for(int i = 0;i <= SeqList_manager->Last;i++ ){
   if(SeqList_manager->Primary_Addr >= x){
         Temp = i;
         break;
   }
}
// 2. 如果x是最大元素，直接插在尾部
if(Temp == -1){
   SeqList_manager->Primary_Addr[++SeqList_manager->Last] = x;
   return ;
}
// 3. 否则，插入位置后的元素后移
for(int i= SeqList_manager->Last;i>= Temp;i--){
   SeqList_manager->Primary_Addr = SeqList_manager->Primary_Addr;
}
// 4. 插入元素并更新下标
SeqList_manager->Primary_Addr = x;
SeqList_manager->Last++;
}
</code></pre>
<h3 id="删除功能">删除功能</h3>
<h4 id="1-按值删除">1. 按值删除</h4>
<p>删除第一个匹配的值，需要先查找位置，再前移元素：</p>
<pre><code class="language-c">// 删除第一个值为DestVal的元素
bool SeqList_Del(SequenceList_t *SeqList_manager,DataType_t DestVal)
{
int Temp = -1; // 记录目标元素下标
// 先判断是否为空表
if(SeqListIsEmpty(SeqList_manager)){
   printf("顺序表为空，无法删除！\n");
   return false;
}
// 1. 查找目标元素
for(int i = 0;i <= SeqList_manager->Last;i++ ){
   if(SeqList_manager->Primary_Addr == DestVal){
         Temp = i;
         break;
   }
}
// 2. 未找到元素
if(Temp == -1){
   printf("未找到元素，删除失败！\n");
   return false;
}
// 3. 目标元素后的元素前移一位
for(int i = Temp;i < SeqList_manager->Last;i++){
   SeqList_manager->Primary_Addr = SeqList_manager->Primary_Addr;
}
// 4. 更新最后一个元素下标
--SeqList_manager->Last;
return true;
}
</code></pre>
<h4 id="2-按位置删除考研题目">2. 按位置删除（考研题目）</h4>
<blockquote>
<p>原题目：删除顺序表中下表为p(0≤p≤length-1)的元素，成功返回1，否则返回0 */</p>
</blockquote>
<pre><code class="language-c">int SeqList_Remove(SequenceList_t *SeqList_manager,int p)
{
// 1. 判断是否为空表
if(SeqListIsEmpty(SeqList_manager)){
   printf("顺序表为空，无法删除！\n");
   return 0;
}

// 2. 判断下标是否合法（0 ≤ p ≤ Last）
if (p < 0 || p > SeqList_manager->Last) {
   printf("下标不合法，删除失败！\n");
   return 0;
}

// 3. 下标p后的元素前移一位
for(int i = p;i < SeqList_manager->Last;i++){
   SeqList_manager->Primary_Addr = SeqList_manager->Primary_Addr;
}

// 4. 更新最后一个元素下标
SeqList_manager->Last--;
return 1;
}
</code></pre>
<h3 id="辅助功能">辅助功能</h3>
<h4 id="1-遍历打印">1. 遍历打印</h4>
<p>打印所有元素，方便查看顺序表状态：</p>
<pre><code class="language-c">// 打印所有元素
void SeqList_Print(SequenceList_t *SeqList_manager)
{
for(int i = 0;i <= SeqList_manager->Last;i++ ){
   printf("%d\n",SeqList_manager->Primary_Addr);
}
}
</code></pre>
<h4 id="2-内存释放">2. 内存释放</h4>
<p>使用完顺序表后必须释放内存，避免内存泄漏：</p>
<pre><code class="language-c">// 释放顺序表内存
void SeqList_Destroy(SequenceList_t *SeqList_manager)
{
if (SeqList_manager != NULL) {
   free(SeqList_manager->Primary_Addr); // 先释放元素数组
   free(SeqList_manager);             // 再释放管理结构体
}
}
</code></pre>
<h2 id="三完整测试代码">三、完整测试代码</h2>
<pre><code class="language-c">int main(int argc, char const *argv[])
{
// 1. 测试初始化
printf("===== 测试初始化 =====\n");
SequenceList_t *seqList = SequenceList_init(5); // 容量为5
if (seqList != NULL)
{
   printf("初始化成功！容量：%u，元素个数：%d\n",
            seqList->Size, seqList->Last + 1); // 空表个数为0
}

// 2. 测试尾部插入
printf("\n===== 测试尾部插入 =====\n");
SeqList_TailAdd(seqList, 10);
SeqList_TailAdd(seqList, 20);
SeqList_TailAdd(seqList, 30);
printf("插入10、20、30后元素：\n");
SeqList_Print(seqList); // 预期：10、20、30
printf("元素个数：%d（预期3）\n", seqList->Last + 1);

// 3. 测试头部插入
printf("\n===== 测试头部插入 =====\n");
SeqList_HeadAdd(seqList, 5); // 头部插入5
printf("插入5后元素：\n");
SeqList_Print(seqList); // 预期：5、10、20、30
printf("元素个数：%d（预期4）\n", seqList->Last + 1);

// 4. 测试有序插入
printf("\n===== 测试有序插入 =====\n");
SeqList_Insert(seqList, 15); // 插入15（应在10和20之间）
printf("插入15后元素：\n");
SeqList_Print(seqList); // 预期：5、10、15、20、30
printf("元素个数：%d（预期5）\n", seqList->Last + 1);

// 测试满表插入（容量5，已插入5个元素）
printf("\n尝试插入35（已满）：\n");
SeqList_Insert(seqList, 35); // 预期提示"已满"

// 5. 测试按值删除
printf("\n===== 测试按值删除 =====\n");
printf("删除15：\n");
bool delResult = SeqList_Del(seqList, 15);
if (delResult)
{
   printf("删除成功，剩余元素：\n");
   SeqList_Print(seqList); // 预期：5、10、20、30
   printf("元素个数：%d（预期4）\n", seqList->Last + 1);
}

// 测试删除不存在的元素
printf("\n删除99（不存在）：\n");
SeqList_Del(seqList, 99); // 预期提示"未找到"

// 6. 测试按位置删除
printf("\n===== 测试按位置删除 =====\n");
printf("删除下标1的元素（值为10）：\n");
int removeResult = SeqList_Remove(seqList, 1);
if (removeResult == 1)
{
   printf("删除成功，剩余元素：\n");
   SeqList_Print(seqList); // 预期：5、20、30
   printf("元素个数：%d（预期3）\n", seqList->Last + 1);
}

// 测试非法下标删除（当前最大下标为2）
printf("\n删除下标5（非法）：\n");
SeqList_Remove(seqList, 5); // 预期提示"不合法"

// 7. 测试边界情况
printf("\n===== 测试边界情况 =====\n");
SequenceList_t *emptyList = SequenceList_init(3); // 空表
printf("删除空表元素：\n");
SeqList_Del(emptyList, 10); // 预期提示"为空"
SeqList_Destroy(emptyList); // 及时释放

// 8. 释放内存
printf("\n===== 测试结束 =====\n");
SeqList_Destroy(seqList);
printf("内存释放完成！\n");
return 0;
}
</code></pre>
<h3 id="测试结果">测试结果</h3>
<p>运行程序后，输出如下:<br>
<img src="https://img2024.cnblogs.com/blog/3677701/202507/3677701-20250725150706629-1690079878.png" alt="image" loading="lazy"><br>
<img src="https://img2024.cnblogs.com/blog/3677701/202507/3677701-20250725150711504-553767086.png" alt="image" loading="lazy"></p><br><br>
来源：https://www.cnblogs.com/YueZone/p/19004650

頁: [1]

琼殿技术论坛's Archiver

线性表-顺序存储