线性表的顺序存储结构

线性表的基本概念

线性结构习惯称为线性表，线性表是n(n>=0)个数据元素构成的有限序列，表中除第一个元素外的每一个元素，有且只有一个一个前件；除最后一个元素外，有且只有一个后件。

非空数据表具有：

• 只有一个根节点，首元素无前件
• 有且只有一个终端节点，末尾元素无后件
• 除收尾节点外，其他所有节点有且只有一个前件和一个后件

线性表的顺序存储结构

通常，线性表可以采用顺序存储和链式存储两种存储结构

顺序存储是存储线性表最简单的结构，具体做法是将线性表中的元素一个接一个地存储在一片相邻的存储区域中。这种顺序存储的线性表也被称为顺序表

顺序表具有一下两个基本特征：

• 线性表中所有元素所占的存储空间是连续的
• 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的

在顺序表中，前件和后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面

顺序存储结构的插入和删除

主要思路：

插入

• 判断插入元素位置是否合理
• 在最后一个元素开始遍历，分别将元素往后移一位
• 修改指定位置的元素
  

删除

• 判断删除元素位置是否合理
• 在末尾开始遍历，分别向前移动一个位置
• 删除指定位置的元素

代码实现

#include <stdio.h>
#include <stdlib.h> //malloc()
#include <iso646.h> // or
#include <stdbool.h> // true false
#define MAXSIZE 10

typedef int ElemType;


// 定义线性表
typedef struct 
{
    /* data */
    ElemType *elem;
    int len;
}SqList;

// 初始化线性表
bool IniSqList(SqList *l)
{
    l->len=0;
    l->elem=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
    if(l->elem==NULL)
        return false;
    return true;
}


// 输出线性表内容
void ShowSqList(SqList *l)
{
    for(int i=0;i<l->len;i++)
        printf("%d ",l->elem[i]);
}

// 获取某个元素
int GetData(SqList *l,int index)
{
    if(index<0 or index>l->len)
        return false;
    return l->elem[index];
}

// 插入数据
bool InsertData(SqList *l,int index,ElemType a)
{
    if(l->len==MAXSIZE)  // 判断表是否满
        return false;
    if(index<1 or index >l->len+1) // 判断表插入位置是否合理
        return false;
    
    if(index<=l->len)
    {
        for(int i=l->len;i>=index;i--)
        {
            l->elem[i]=l->elem[i-1];
        }
        l->len++; // 长度+1
        l->elem[index-1]=a; // 插入新元素
    }
    return true;
}

// 删除指定数据
bool DeleteData(SqList *l,int index)
{
    if(index<0 or index>l->len) // 判断表删除位置是否合理
        return false;
    for(int i=index-1;i<l->len-1;i++)
    {
        l->elem[i]=l->elem[i+1];
    }
    l->elem[l->len-1]=NULL; // 删除末尾元素
    l->len--;   // 长度-1
}

// 加载数据
void LoadSqList(SqList *l,int index)
{
    for(int i=0;i<index;i++)
    {
        l->elem[i]=i+1;
        l->len++;
    }
}

int main(void)
{
    SqList list;
    IniSqList(&list);
    LoadSqList(&list,7);
    ShowSqList(&list);
    printf("\n");
    // InsertData(&list,1,9);
    DeleteData(&list,1);
    ShowSqList(&list);

    getchar();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

实现效果