顺序表学习笔记1

威斯布鲁特

线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1个元素。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

假定线性的类型为ElemType,线性表的顺序存储类型用C语言描述为：

1. #define MaxSize 50  // 定义线性表的最大长度
   
2. typedef struct{
   
3.     ElemType data [MaxSize] ;  // 顺序表的元素
   
4.     int length;  // 顺序表的当前长度
   
5. }SqList;  // 顺序表的类型定义

复制代码

这个顺序表结构用静态分配的一维数组表示的，也可以用动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将产生溢出，就会导致程序崩溃。

我以前一直以为动态分配就不是线性表的顺序表示，是链式表示。但后来我发现“动态分配并不是链式存储，同样还是属于顺序存储结构，其物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。”我想先研究静态分配的表示，所以动态分配后面再继续。

补充点干货，顺序表的特点：

顺序表最主要的特点是可以进行随机访问特性，即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。

顺序表的存储密度高，每个结点只存储数据元素。

顺序表逻辑上相邻的元素物理上也相邻，所以，插入和删除操作需要移动大量元素。

威斯布鲁特

实现了顺序表的初始化操作，发现自己对pSq->data与pSq.data根本不了解，得回去填坑了。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <assert.h>
   
4. #include <memory.h>
   
5. 
   
6. #define MaxSize 50
   
7. #define ElemType int
   
8. 
   
9. //定义顺序表的静态数组表示
   
10. typedef  struct{
    
11. ElemType data[MaxSize];
    
12. int length;
    
13. }SqList,*pSqList;
    
14. 
    
15. void InitSq(pSqList pSq);
    
16. void test();
    
17. 
    
18. int main()
    
19. {
    
20.     SqList s;
    
21.     InitSq(&s);
    
22.     return 0;
    
23. }
    
24. 
    
25. //初始化顺序表
    
26. void InitSq(pSqList pSq)
    
27. {
    
28.     int i;
    
29. 
    
30.     assert(pSq);  //判断是否开辟结构体空间
    
31. 
    
32. //把线性表的每个元素初始化为0
    
33. 
    
34. //方法1
    
35. //  memset(pSq->data, 0, sizeof(ElemType)*MaxSize);
    
36. 
    
37. //方法2
    
38.     for(i=0; i<sizeof(pSq->data)/4; i++)
    
39.     {
    
40.         pSq->data[i] = 0;
    
41.     }
    
42.     pSq->length = 0;
    
43. }
    

复制代码

威斯布鲁特

补充下用到的库函数：
c语言诊断_断言库函数#include<assert.h>
assert

#include <assert.h>
void assert(int exp);
assert宏用于为程序增加诊断功能。当assert(exp)执行时，如果exp为bool值false，则在标准出错输出流stderr输出一条如下所示的信息：

Assertion failed: expression, file filename, line nnn

然后调用abort终止执行。其中的源文件名filename和行号nnn来自于预处理宏__FILE__和__LINE__。

如果<assert.h>被包含时定义了宏NDEBUG，那么宏assert被忽略。

威斯布鲁特

威斯布鲁特 发表于 2017-7-2 00:18
实现了顺序表的初始化操作，发现自己对pSq->data与pSq.data根本不了解，得回去填坑了。

pSq->data中pSq是一个指针，pSq->data表示该指针所指向结构的一个成员
pSq.data中的pSq是一个结构体，“.”是结构成员运算符，优先级比(*p)中的"*"高。