002-线性表及其顺序结构存储实现

moc

1、线性表的基本概念
1.定义
    线性表（list）是由0个或多个元素组成的集合；
    线性表中的数据元素之间是有顺序的；
    线性表的数据元素个数是有限的；
    线性表中数据元素的类型必须相同。
数学描述：
    线性表是具有相同类型的n(n≥0)个数据元素的有限序列（a1, a2, a3, ... , an）,其中ai是表项，n是表的长度。

2.性质
    a0为线性表的第一个元素，只有一个后继；
    an为线性表的最后一个元素，只有一个前驱；
    除了a0和an以外的元素，既有前驱又有后继；
    线性表能够逐项访问和顺序存取。
3.线性表的操作
    创建线性表；
    销毁线性表；
    清空线性表；
    将元素插入到线性表；
    将元素从线性表中删除；
    获取线性表某个位置的元素；
    获取线性表的长度等。
2、线性表的顺序存储结构
顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。
  这种存储结构需要提前根据存入元素的最大容量分配空间，一旦分配好，容量是固定的。
设计与实现：

#ifndef _MY_SEQLIST_H__
#define _MY_SEQLIST_H__
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

typedef void SeqList;
typedef void SeqListNode;

// 根据容量创建并返回一个空的线性表
SeqList* SeqList_Create(int capacity);

// 销毁一个线性表
void SeqList_Destroy(SeqList* list);

// 清空一个线性表
void SeqList_Clear(SeqList* list);

// 获取线性表的长度
int SeqList_Length(SeqList* list);

// 获取线性表的容量
int SeqList_Capacity(SeqList* list);

// 在线性表的pos位置插入元素node
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);

// 获取线性表pos位置的元素
SeqListNode* SeqList_Get(SeqList* list, int pos); 

// 删除线性表pos位置的元素
SeqListNode* SeqList_Delete(SeqList* list, int pos);

#endif

1. 插入元素算法
        判断线性表是否合法；
        判断插入位置是否合法；
        容错修正  插入位置大于当前长度但小于链表容量，自动添加到尾部；
        把最后一个元素到插入位置的元素一次向后移一个位置；
        将新元素插入；
        线性表长度加1.

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
        int i = 0, ret = 0;
        TseqList* tlist = NULL;
        tlist = (TseqList*)list;
        if (list == NULL || node == NULL || pos < 0)
        {
                ret = -1;
                printf("Fun SeqList_Insert() error: %d \n", ret);
                return ret;
        }

        if (pos >= tlist->capacity)
        {
                ret = -2;
                printf("链表已满: %d \n", ret);
                return ret;
        }

        // 容错修正  插入位置大于当前长度但小于链表容量，自动添加到尾部
        if (pos >= tlist->length)
        {
                pos = tlist->length;
        }

        //1.元素后移
        for (i = tlist->length; i > pos; i--)
        {
                tlist->node[i] = tlist->node[i - 1];
        }
        //2. 插入元素
        tlist->node[i] = node;
        tlist->length++;

        return 0;
}

2. 获取元素操作
        判断线性表是否合法；
        判断位置是否合法；
        直接通过数组下标的方式获取数组元素。

SeqListNode* SeqList_Get(SeqList* list, int pos)
{
        int i = 0, ret = 0;
        TseqList* tlist = NULL;
        tlist = (TseqList*)list;
        if (list == NULL || pos < 0 || pos > tlist->length)
        {
                ret = -1;
                printf("Fun SeqList_Get() error: %d \n", ret);
                return ret;
        }
        return tlist->node[pos];
}

3. 删除元素算法
        判断线性表是否合法；
        判断删除位置是否合法；
        将要删除的元素取出；
        把删除位置后的元素分别向前移一个位置；
        线性表长度减1.       
注意：线性表的容量和实际长度是两个不同的概念。

SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
        int i = 0, ret = 0;
        SeqListNode* tmp;
        TseqList* tlist = NULL;
        tlist = (TseqList*)list;
        if (list == NULL || pos < 0)
        {
                ret = -1;
                printf("Fun SeqList_Insert() error: %d \n", ret);
                return NULL;
        }
    // 缓存删除的结点
        tmp = (SeqListNode*)tlist->node[pos]; 
        // 结点前移
        for (i = pos + 1; i < tlist->length; i++)
        {
                tlist->node[i - 1] = tlist->node[i];
        }
        tlist->length--;
        return tmp;
}

3、顺序存储优点和缺点
优点：
        无需为线性表中的逻辑关系增加额外的空间；
        可以快速获取表中合法位置的元素。
缺点：
        插入和删除操作需要移动大量的元素；
        当线性表长度变化较大时难以确定存储空间的容量。

完整代码： 线性表顺序存储.zip (1.97 KB, 下载次数: 12)

2018-9-23 11:41 上传

点击文件名下载附件
线性表顺序存储