第N号垃圾站

large picture of the cover

线性表之顺序表

线性表的定义

    线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，即线性表是由n个元素组成的有限序列,同时，在存在多个元素时，除了第一个只元素没有前驱，最后一个没有后继之外，其他的元素都有一个前驱和一个后继。即线性表存储的是具有一对一关系的数据元素，且元素之间是有序的。线性表的存储形式有两种：顺序存储和链式存储。

线性表的顺序存储结构

    线性表的顺序存储结构是指用一段地址连续的存储单元按照元素的逻辑顺序依次存储线性表的数据元素，使得逻辑上相邻的两个数据元素在物理位置上也相邻。

顺序存储结构的优缺点

优点：

  1. 无须为表示表中元素的相对位置而增加额外的存储开销(即不需要存储额为指向下一个节点的指针)；
  2. 可以快速地访问表中任意一个位置的元素；
  3. 利用数组的特性，可以方便地实现各种运算操作。

缺点：

  1. 当插入和删除操作频繁时，需要移动大量的元素，效率较低；
  2. 当线性表长度变化较大时，难以确定存储空间的容量，容易造成存储“溢出”或“分配不足”。

顺序存储结构的实现

    顺序存储结构的实现通常使用数组来实现(静态就用固定大小的数组，动态用指针动态申请)。

数据类型定义

    sqlist.h文件

#ifndef __SQLIST_H__                /*确保这个头文件只定义一次*/
#define __SQLIST_H__

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define INIT_SIZE 5

typedef int ElemType; /*定义数据类型,这里定义为int型，
                        也可以定义为其他类型，比如char、float等。*/

typedef struct sqlist
{
    ElemType *elem; // 存储空间基址，数组的起始位置
    size_t length; // 当前长度
    size_t listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位)
}Sqlist;

void InitList(Sqlist *L);//初始化顺序表
void DestroyList(Sqlist *L);//销毁顺序表
void PrintList(Sqlist *L);//打印顺序表
int EnsureCapacity(Sqlist *L);//确保顺序表容量足够
void InsertListFront(Sqlist *L, ElemType e);//在顺序表头部插入元素
void InsertListRear(Sqlist *L, ElemType e);//在顺序表尾部插入元素
void DeleteListFront(Sqlist *L);//删除顺序表头部元素
void DeleteListRear(Sqlist *L); //删除顺序表尾部元素
int *SearchElement(Sqlist *L,ElemType element);//查找元素，返回指向该元素的指针
int SearchUniqueElement(Sqlist *L,ElemType element);//查找唯一元素，返回元素在顺序表中的位置
void InsertElementByPos(Sqlist *L,size_t pos, ElemType element);//在指定位置插入元素
void DeleteElementByPos(Sqlist *L,size_t pos);//删除指定位置的元素
void ModifyElementByPos(Sqlist *L,size_t pos,ElemType element);//修改指定位置的元素


#endif // !__SQLIST_H__

函数实现

    初始化操作主要是为顺序存储结构分配空间，并设置初始长度。

初始化
#include "sqlist.h"
// 初始化顺序表
void InitList(Sqlist *L)
{
    assert(L != NULL);
    L->elem = (ElemType *)malloc(INIT_SIZE * sizeof(ElemType));
    if (L->elem == NULL)
    {
        fprintf(stderr, "内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    L->length = 0;
    L->listsize = INIT_SIZE;
}
销毁
// 销毁顺序表
void DestroyList(Sqlist *L)
{
    assert(L != NULL);
    if (L->elem != NULL)
    {
        free(L->elem);
        L->elem = NULL;
    }
    L->length = 0;
    L->listsize = 0;
    printf("链表已销毁!\n");
}
打印顺序表
// 打印顺序表
void PrintList(Sqlist *L)
{
    assert(L != NULL);
    if (L->length == 0)
    {
        printf("顺序表为空！\n");
        return;
    }
    for (size_t i = 0; i < L->length; i++)
    {
        printf("%d", L->elem[i]);
        printf(i==L->length-1 ? "\n":" ");
    }
}
容量检查
// 确保顺序表容量足够
int EnsureCapacity(Sqlist *L)
{
    assert(L != NULL);
    if (L->elem == NULL)
    {
        printf("顺序表未初始化！\n");
        return -1;
    }
    if (L->length == L->listsize)
    {
        size_t newsize = L->listsize == 0 ? 5 : L->listsize * 2;
        ElemType *newbase = (ElemType *)realloc(L->elem, newsize * sizeof(ElemType));
        if (newbase == NULL)
        {
            perror("realloc");
            return -1;
        }
        L->elem = newbase;
        L->listsize = newsize;
    }
    return 0;
}
头插
//头插
void InsertListFront(Sqlist *L, ElemType e)
{
    assert(L != NULL);
    if (EnsureCapacity(L) == -1)
    {
        printf("扩容失败！\n");
        return;
    }
    for (size_t i = L->length; i > 0; i--)
    {
        L->elem[i] = L->elem[i - 1];
    }
    L->elem[0] = e;
    L->length++;
}
尾插
//尾插
void InsertListRear(Sqlist *L, ElemType e)
{
    assert(L !=  NULL);
    if (EnsureCapacity(L) == -1)
    {
        printf("扩容失败！\n");
        return;
    }
    L->elem[L->length] = e;
    L->length++;
}
头删
//头删
void DeleteListFront(Sqlist *L)
{
    assert(L!=NULL);
    assert(L->length>0);
    for (size_t i = 0; i < L->length-1; i++)
    {
        L->elem[i] = L->elem[i+1];
    }
    L->length--;
}
尾删
//尾删
void DeleteListRear(Sqlist *L)
{
    assert(L!=NULL);
    assert(L->length>0);
    L->length--;
}
查找特定元素(有重复元素)
//查找特定元素(假设表中元素不唯一)
int* SearchElement(Sqlist *L, ElemType element)
{

    assert(L != NULL);
    int count = 0;
    int *p = (int *)malloc(L->length*sizeof(int)+1);
    int j = 1;
    for (size_t i = 0; i < L->length; i++)
    {
        if (L->elem[i]==element)
        {
            p[j++] = i;
            count++;
        }
    }
    p[0] = count;
    return p;
    
}
查找特定元素(无重复元素)
//查找特定元素(假设表中元素唯一)
int SearchUniqueElement(Sqlist *L, ElemType element)
{

    assert(L != NULL);
    int i = 0;
    for (i = 0; i < L->length; i++)
    {
        if (L->elem[i]==element)
        {
            return i;
        }
    }
    return -1;
}
在指定位置插入
//在指定位置插入元素

void InsertElementByPos(Sqlist *L, size_t pos, ElemType element)
{
    assert(L != NULL);
    assert(pos < L->length && pos >= 0);
    EnsureCapacity(L);
    for(size_t i = L->length; i > pos; i-- )
    {
        L->elem[i] = L->elem[i-1];
    }
    L->elem[pos] = element;
    L->length++;
}
删除指定位置元素
//删除指定位置的元素
void DeleteElementByPos(Sqlist *L, size_t pos)
{
    assert(L != NULL);
    assert(pos>=0&&pos<L->length);
    
    for (size_t i = pos; i < L->length-1; i++)
    {
        L->elem[i] = L->elem[i+1];
    }
    L->length--;
}
修改指定位置元素
//修改指定位置的元素值
void ModifyElementByPos(Sqlist *L, size_t pos, ElemType element)
{
    assert(L !=NULL);
    assert(L->length > 0);
    assert(pos>= 0&& pos < L->length);
    L->elem[pos] = element;
}

结语

    由于代码的存在，篇幅显得有点长了，不过问题不大，可以在main.c中进行测试。经过测试应该都是没有问题的。关于assert.h:这是 C 标准库中的一个头文件，用于提供断言（assertion）功能。断言是一种调试工具，用于在程序中检查某些条件是否为真。基本用法assert(expression)，其中expression是(条件)表达式如果条件为假（即断言失败），程序会终止并输出错误信息，帮助开发者快速定位问题。注意在发布版的代码中应该禁用断言，一些编译器在进行发布编译时会自动禁用。

宅懒一个

site logo

蓝天，白云，远山，田野......

© 2025 第N号垃圾站