顺序表学习笔记1
本帖最后由 威斯布鲁特 于 2017-6-29 17:49 编辑线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1个元素。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
假定线性的类型为ElemType,线性表的顺序存储类型用C语言描述为：
#define MaxSize 50// 定义线性表的最大长度
typedef struct{
ElemType data ;// 顺序表的元素
int length;// 顺序表的当前长度
}SqList;// 顺序表的类型定义
这个顺序表结构用静态分配的一维数组表示的，也可以用动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将产生溢出，就会导致程序崩溃。
我以前一直以为动态分配就不是线性表的顺序表示，是链式表示。但后来我发现“动态分配并不是链式存储，同样还是属于顺序存储结构，其物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。”我想先研究静态分配的表示，所以动态分配后面再继续。
补充点干货，顺序表的特点：
[*]顺序表最主要的特点是可以进行随机访问特性，即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。
[*]顺序表的存储密度高，每个结点只存储数据元素。
[*]顺序表逻辑上相邻的元素物理上也相邻，所以，插入和删除操作需要移动大量元素。
本帖最后由 威斯布鲁特 于 2017-7-12 21:53 编辑
实现了顺序表的初始化操作，发现自己对pSq->data与pSq.data根本不了解，得回去填坑了{:10_266:}。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <memory.h>
#define MaxSize 50
#define ElemType int
//定义顺序表的静态数组表示
typedefstruct{
ElemType data;
int length;
}SqList,*pSqList;
void InitSq(pSqList pSq);
void test();
int main()
{
SqList s;
InitSq(&s);
return 0;
}
//初始化顺序表
void InitSq(pSqList pSq)
{
int i;
assert(pSq);//判断是否开辟结构体空间
//把线性表的每个元素初始化为0
//方法1
//memset(pSq->data, 0, sizeof(ElemType)*MaxSize);
//方法2
for(i=0; i<sizeof(pSq->data)/4; i++)
{
pSq->data = 0;
}
pSq->length = 0;
}
补充下用到的库函数：
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)中的"*"高。
页:
[1]