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

数据结构之线性表(顺序存储结构)

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

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

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> 有的编译器是加别的,请百度 - -#

 

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

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

优:

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

缺:

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

 

 

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

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