1.线性表的定义
线性表是具有相同特性（每个数据元素所占空间一样大n）的数据元素的一个有限序列
例如：（a1,a2,a3,....ai,....an）
其中a1为起始节点（表头元素），an为终端节点（表尾元素）。每个元素都有且仅有一个直接前驱（第一个元素除外），每个元素都有且仅有一个直接后继（最后一个元素除外）。n为表长，n=0时为空表。
2.线性表的基本操作
InitList(&L):初始化表。构造一个空的线性表
Length(L):求表长。返回线性表L的长度，即L中数据元素的个数
LocateElem(L,e):按值查找。在L中查找给定值的元素
GetElem(L,i):按位查找。在L中查找第i个元素的值
ListInsert(&L,i,e):插入。在L中第i个位置插入e
ListDelete(&L,i,&e):删除。删除L中的第i个位置的元素e，并把e的值带回来
PrintList(L):输出。按顺序输出L的所有元素的值
Empty(L):判断表空。若空，返回True；若不空，返回False
DestroyList(&L):销毁。销毁线性表，并且释放该表的内存空间
3.线性表的顺序存储表示
把逻辑上相邻的元素存储在物理上也相邻的位置，依次存储，地址连续，可以实现随机存储。因此，所有元素的存储位置可以由第一个元素的存储位置计算而得：LOC(ai) = LOC(a1) + (i - 1) * 每个元素存储空间
逻辑位序和物理位序相差1（数组特性）
//线性表定义 #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 typedef struct{ Elemtype elem[LIST_INIT_SIZE];//数据类型 int length;//当前长度 }SqList;
#define MAXSIZE 10000 //图书表可能达到的最大长度 typedef struct { //图书信息定义 char no[20]; //图书ISBN char name[50]; //图书名字 float price; //图书价格 }Book; typedef struck { Book *elem; //存储空间的基地址 int length; //图书表中当前图书个数 }Sqlist; //图书表的顺序存储结构类型为SqList
4.顺序表
4.1.顺序表的定义
4.1.1.顺序表的静态分配
#include<stdio.h> #define Maxsize 10 //定义最大长度 typedef struct{ int data[Maxsize]; //用静态数组存放数据元素 int length; //顺序表的当前长度 }sqList; //顺序表的类型定义 //基本操作——初始化一个顺序表 void initList(sqList &L){ for (int i = 0; i < Maxsize; i++){ L.data[i] = 0; //将所有数据元素设置为默认初始值 L.length = 0; //顺序表初始长度为0 } int main(){ sqList L; //申明一个顺序表L inList(L); //初始化顺序表L //.....后续操作 return 0; }
需要对数组元素进行初始化，防止有脏数据
4.1.2.顺序表的动态分配
SqList L; //定义顺序表L L.data = (ElemType*)malloc(sizeof(Elemtype)*MaxSize); //申请内存空间
先用sizeof函数计算出Elemtype的单位空间，乘以MaxSize，即总数，得到总共所需的内存空间，再通过(ElemType*)强制转换为ElemType*类型的数据
#define initList 10 //顺序表的初始长度 typedef struct{ Elemtype *data; //指示动态分配数组的指针 int Maxsize; //顺序表的最大容量 int length; //顺序表的当前长度 }sqList; //用malloc函数申请一片连续的存储空间，返回的是首地址，用指针去接收它 sqList L; L.data = (ElemType*)malloc(sizeof(Elemtype)*initSize);
#define initSize 10 //默认的最大长度 typedef struct{ int* data; //指示动态分配的指针 int maxSize; //顺序表的最大容量 int length; //顺序表的当前长度 }sqList; void initList(sqList &L){ //用malloc申请一片连续的存储空间 L.data = (int*)malloc(initSize * sizeof(int)); L.length = 0; L.maxSize = initSize; } //增加动态数组长度 void increaseSize(sqList &L, int len){ int *p = L.data; L.data = (int*)malloc((L.Maxize + len) * sizeof(int)); for (int i = 0; i < L.len; i++){ L.data[i] = p[i]; //将数据复制到新区域 } L.maxSize = L.maxSize + len; //将顺序表最大长度增加len free(p); //释放原来的空间 } int main(){ sqList L; //申明一个顺序表L initList(L); //初始化顺序表L //往L中加入元素 increaseSize(L, 7); return 0; }
4.2.顺序表的基本操作
4.2.1.顺序表的插入操作
bool insertElem(sqList& L, int i, int e) { //插入位置非法返回false if (i < 1 || i > L.length + 1) return false; if (L.length >= maxSize) return false; //依次后移插入位置后的元素 for (int j = L.length; j >= i; j--) { L.data[j] = L.data[j - 1]; } //在第i个位置插入元素，但是因为是数组，所以第i个位置的数组下标为i - 1 L.data[i - 1] = e; //数组长度+1 L.length++; return true; }
4.2.2.顺序表的删除操作
bool deleteElem(sqList& L, int i, int& e) { //判断删除位置是否非法，不用判断是否顺序表是否为空表 //空表情况下L.length = 0 if (i < 1 || i > length + 1) return false; //通过引用方式取出元素 e = L.data[i - 1]; //从i开始遍历顺序表，并且依次向前移动 for (int j = i; j < L.length; j++) { L.data[j - 1] = L.data[j]; } //不用将最后一个元素归零，因为L.length--，使得最后一个元素不在访问范围之内 L.length--; return true; }
4.2.3.顺序表的按值查找操作
int locateElem(sqList L, int e) { //遍历数组元素，如果当前元素和e相等，返回它的位序，即下标+1 for (int i = 0; i < L.length; i++) { if (e == L.data[i]) return i + 1; } //如果没找到该元素，则return 0表示未找到 //因为正常情况下返回值只可能是1 ~ L.length的数字 return 0; }
