首页 > 代码库 > 数据结构之线性表（顺序存储结构）

数据结构之线性表（顺序存储结构）

2024-07-04 12:52:10   236人阅读

小学生放学都是要按顺序排队的，一个接一个，每个小学生的前后位置是固定的，这样便于迅速清点。

其实这就是一个线性表，从这件事里我们就可以找到很多关于线性表的特性，如

1、线性表是一个序列，它是有顺序的（排队）

2、第一个元素无前驱，最后一个无后继，其他每个元素都有一个前驱和后继（一个接一个）

3、元素是有限的（小学生的个数是有限的）

4、数据类型都相同（都是小学生在排队）

 

说明白线性表示什么，下面我们直接看线性表的实现

线性表的实现分顺序存储结构和链式存储结构


顺序存储结构：

#define LIST_INIT_SIZE  100 //存储空间的初始分配量
#define LISTINCREMENT   10  //分配增量
#define ElemType int        //数据类型
typedef struct{
    ElemType *elem;         //基址
    int length;             //当前长度
    int listsize;           //当前分配的存储容量

}SqList;
顺序存储结构

 上述只是顺序存储结构的一种写法，最后我还会贴一个用数组实现的写法，这不是主要的问题。

下面我们来看如何初始化一个线性表

1 int InitList(SqList &L){
2     L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//申请一块连续的内存
3     if(!L.elem){
4         return 0;
5     }
6     L.length = 0;                                               //初始化为空表，长度为0
7     L.listsize = LIST_INIT_SIZE;                                //初始化存储容量
8 }
初始化线性表

我上课用的课本是严蔚敏的《数据结构》（C语言版），在上课听老师讲初始化线性表的代码的时候，当时没看明白，后来才知道，原来课本省略了几行宏定义的代码就是西面这些

1 #define OK 1
2 #define OVERFLOW 0
3 #define Status  int
课本省略代码

我觉得加上上述三行代码，大家看起来就应该明白了。

 

到这里我们会发现，咦，还有一个变量没有使用，那就是分配增量LISTINCREMENT ，下面我们要介绍的操作就会用到它

这个操作就是线性表的插入

顺序结构的插入就好像我们日常在学校体育锻炼签到，我们正在排队，这时候舍友来了，队伍特别长呀，你就悄悄地把他拉到你的前面了，这时候队伍的位置就会发生改变，你和你身后的人都需要往后退一个人的位置。

特意用黑体标注出来的就是插入的重点，插入之后的元素要往后移动一个位置。

下面看具体的代码实现

 1 //在i前插入元素e
 2 int ListInsert(SqList &L,int i,ElemType e){
 3     ElemType *newbase;
 4     ElemType *q;                        //用来表示插入的位置
 5     ElemType *p;                        //移动元素的辅助变量
 6 
 7     if(i<1||i>L.length){
 8         return 0;
 9     }                                   //判断插入位置的合理性
10 
11     if(L.length >= L.listsize){
12         newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
13                                         //判断原先申请的内存大小是否还能插进元素，若不能，则申请增加内存
14         if(!newbase){
15             return 0;
16         }                               //申请内存失败
17 
18         L.elem = newbase;               //改变原来的存储空间基址
19         L.listsize = L.listsize + LISTINCREMENT;
20                                         //增加存储增量
21     }
22 
23     //下面终于到了该插入新元素的时刻了 - -#
24     q = &(L.elem[i-1]);                 //插入元素之前要先找准位置，注意这边是-1
25     //接下来一步就是我们上面所说的重点了，插入位置之后的元素往后移一步
26     for(p = &(L.elem[L.length-1];p>=q;--p)){
27         *(p+1) = *p;
28     }                                   //这里和我们的正常思维有一点区别，正常来说，我们都是从插队的位置一点一点移动的，
29                                         //但是，这里为了代码的简便性，我们选择从最后一个开始移动。
30                                         //这里大家一定要注意的就是，一定要好好理解-1 和+1
31     //循环过后，q以及q身后的元素都已经往后移动了一个位置，此时的q+1即为原先的q，我们只需将现在的q的值覆盖掉即可
32     *q = e;
33     ++L.length;                         //表长加1
34     return 1;                           //插入完成
35 }
插入操作

 

既然说到了插入操作，那么肯定要缺不了线性表的删除操作

这个的重点和插入的类似，不过恰好反了过来，删除之后的元素要往前移动一个位置。

下面看具体代码的实现

 1 int ListDelete(SqList &L,int i,ElemType &e){
 2     //删除第i个元素，并赋值给e
 3     ElemType *p;
 4     ElemType *q;
 5 
 6     if(i<1 || i>L.length){
 7         return 0;
 8     }                           //判断i是否在合理范围内
 9     p = &(L.elem[i-1]);         //要删除的位置
10     e = *p;                     //将要删除的元素的值赋值给e
11 
12     q = L.elem + L.length -1;   //获得表尾元素位置，这里要理解指针所指向的内存的操作
13 
14     for(;p<=q;++p){
15         *p = *(p+1);            //将删除之后的元素向后前移动一个位置
16     }
17 
18     --L.length;                 //表长减1
19     return 1;                   //删除成功
20 }
删除操作

 

增删改查，4个操作，我们已经介绍了两个，另外两个我是在是不知道该讲点什么，就直接贴代码了。

这两个操作的代码相对于增删个人感觉要简单些

 1 int ListChange(SqList L,int i,ElemType e){
 2     //将第i个元素的数据内容改为e
 3     ElemType *p;
 4 
 5     if(i<1 || i > L.length){
 6         return 0;
 7     }                           //老规矩，先判断i的合理性
 8 
 9     p = &(L.elem[i-1]);         //获得要改变的值得位置
10 
11     *p = e;                     //将值进行修改
12 
13     return  1;                  //修改成功
14 }
修改操作
 1 int ListSearch(SqList L,int i,ElemType &e){
 2     //查找第i个元素赋值给e
 3     ElemType *p;
 4 
 5     if(i<1 || i > L.length){
 6         return 0;
 7     }                           //老规矩，先判断i的合理性
 8 
 9     p = &(L.elem[i-1]);         //获得要查找的值得位置
10 
11     e = *p;                     //将值进行传递
12 
13     return  1;                  //查找成功
14 }
查找方法

 

补充一点东西，就是两个函数，分别是malloc函数和realloc函数

malloc不是一个单词，而是一个缩写，原型是memory allocation，翻译过来意思就是动态分配内存的意思

它的原型应该是void *malloc(size)

void*表示未确定类型的指针，也就是这个函数我们在调用的时候一定要进行强转

失败的时候返回null

realloc函数

作用是改变原有内存的大小

原型void *malloc(要改变的内存的指针名,改变的大小)

使用的时候也一定要强转

失败的时候也是返回null

malloc 和realloc 使用的时候要记得加头文件 #include <stdib.h> 有的编译器是加别的，请百度 - -#

 

到这里，线性表的顺序存储结构就算是讲完了

最后我们总结下它的优缺点

优：

  • 可以快速的存取表中的任一位置的元素 

缺：

  • 插入和删除操作需要移动大量元素
  • 如果线性表的长度变化较大的话，存储空间的容量的大小设置难以确定，同时也有可能造成一定的空间碎片

 

 

第一次这样系统的写一个知识点的博客，存在不少问题，大家多多见谅，若发现有问题，请第一时间帮忙给指出，谢谢。

解析来会贴线性表的链式存储结构。

 

 


联系
我们