一、简介

学习数据结构的第一个程序，手写实现顺序表。

实现功能

• 创建表
• 清空表中元素
• 判断表中数据是否为空
• 求表中有效数据长度
• 指定数据元素定位
• 指定位置插入元素
• 释放空间
• 打印顺序表的内容
• 删除指定位置上的元素

二、完整代码

sqlist.h

#ifndef __SQLIST_H
#define __SQLIST_H

#include <stdio.h>
#define N 128

typedef int dataType; // 表内元素的类型
typedef struct
{
    int last;
    dataType arr[N];
} *pSqlist, Sqlist;

// 函数
pSqlist CreateSqlisst(void);
int ClearSqlist(pSqlist list);
int SqlistIsEmpty(pSqlist list);
int LengthOfSqlist(pSqlist list);
int LocateElement(pSqlist list, dataType val);
int InsertElement(pSqlist list, int pos, dataType val);
int SqlistFree(pSqlist list);
void ShowList(pSqlist list);
int DeleteElement(pSqlist list, int pos);

#endif

sqlist.c

#include "sqlist.h"
#include <stdlib.h>
#include <string.h>

pSqlist CreateSqlisst(void)
{
    pSqlist list;
    list = (pSqlist)malloc(sizeof(Sqlist));

    if (list == NULL)
    {
        printf("list malloc failed\n");
        return list;
    }

    // initialize
    memset(list, 0, sizeof(Sqlist));
    list->last = -1;

    return list;
}

/**
 * @brief Clear all elements in the list
 *
 * @param list
 * @return int 0:success -1:failed
 */
int ClearSqlist(pSqlist list)
{
    if (list == NULL)
    {
        return -1;
    }

    memset(list, 0, sizeof(Sqlist));
    list->last = -1;

    return 0;
}

/**
 * @brief
 *
 * @param list
 * @return int 1£ºempty 0£ºnot empty
 */
int SqlistIsEmpty(pSqlist list)
{
    if (list->last == -1)
    {
        return 1;
    }

    return 0;
}

/**
 * @brief return the length of the list
 *
 * @param list
 * @return int
 */
int LengthOfSqlist(pSqlist list)
{
    if (list == NULL)
    {
        return -1;
    }

    return list->last + 1;
}

/**
 * @brief return the pos of specific element
 *
 * @param list
 * @param val
 * @return int -1:failed
 */
int LocateElement(pSqlist list, dataType val)
{
    if (list == NULL)
    {
        return -1;
    }

    for (size_t i = 0; i <= list->last; i++)
    {
        if (list->arr[i] == val)
        {
            return i;
        }
    }

    return -1;
}

/**
 * @brief Insert element into specific pos of the list
 *
 * @param pos
 * @param val
 * @return int
 */
int InsertElement(pSqlist list, int pos, dataType val)
{
    // full
    if (list->last == N - 1)
    {
        printf("list is full\n");
        return -1;
    }

    // check para    0<=pos<=Last+1   [0, last+1]
    if (pos < 0 || pos > list->last + 1)
    {
        printf("Pos is invalid\n");
        return -1;
    }

    // move
    for (int i = list->last; i >= pos; i--)
    {
        list->arr[i + 1] = list->arr[i];
    }

    // update value last
    list->arr[pos] = val;
    list->last++;

    return 0;
}

void ShowList(pSqlist list)
{
    if (list == NULL)
    {
        printf("Show list error,the list is null\n");
        return;
    }

    if (list->last == -1)
    {
        printf("There is no element in the list\n");
        return;
    }

    for (size_t i = 0; i <= list->last; i++)
    {
        printf("%d ", list->arr[i]);
    }
    printf("\n");
}

int SqlistFree(pSqlist list)
{
    if (list == NULL)
        return -1;
    free(list);
    list = NULL;
    return 0;
}

int DeleteElement(pSqlist list, int pos)
{
    if (list->last == -1 || list == NULL)
    {
        printf("The list is null or empty\n");
        return -1;
    }

    if (pos > list->last || pos < 0)
    {
        printf("The pos is invalid\n");
        return -1;
    }

    for (int i = pos + 1; i <= list->last; i++)
    {
        list->arr[i - 1] = list->arr[i];
    }

    list->last--;
    return 0;
}

三、总结

待实现的接口

1. 给两个顺序表求并集
2. 去掉顺序表的相同元素
3. 为表内元素进行排序

程序缺陷

1. 插入元素时不能够动态扩展数据区的大小
2. 顺序存储方式需要连续的内存空间
3. 插入或删除操作需要更多的时间移动元素，效率低下

调试总结

/**
 * @brief Insert element into specific pos of the list
 *
 * @param pos
 * @param val
 * @return int
 */
int InsertElement(pSqlist list, int pos, dataType val)
{
    // full
    if (list->last == N - 1)
    {
        printf("list is full\n");
        return -1;
    }

    // check para    0<=pos<=Last+1   [0, last+1]
    if (pos < 0 || pos > list->last + 1)
    {
        printf("Pos is invalid\n");
        return -1;
    }

    // move
    for (int i = list->last; i >= pos; i--)
    {
        list->arr[i + 1] = list->arr[i];
    }

    // update value last
    list->arr[pos] = val;
    list->last++;

    return 0;
}

该函数的第一个版本在move那一步循环的遍历变量选择了编辑器默认的 size_t 为 i 的类型，该类型是一种可以指类型，其本质是unsigned long long。所以该循环不能够遍历到负数，由于顺序表初始化时将list->last的值初始化为 -1 ，导致程序运行时产生了段错误。