线性表的基本概念
线性表的定义
定义：
线性表是零个或多个(n >= 0)具有相同数据类型的数据元素的有限序列.
通常记作：(a1,a2,…,ai-1,ai,ai+1,…,an)。n是表长，n = 0的线性表被称为空表
举个例子
特点：
在线性表中相邻元素之间存在顺序关系。即，对于元素ai而言，ai-1称为ai的直接前驱，ai+1称为ai的直接后继。
故，除了开始结点(a1)和终端结点(an)以外，其余所有结点都有且仅有一个直接前驱和一个直接后继
线性表的基本操作
- 初始化线性表InitList(L)
- 求线性表长度GetLength(L)
- 按位置查找操作GetElem(L,i,x)
- 按值查找操作Locate(L,x)
- 插入操作InsElem(L,i,x)
- 删除操作DelElem(L,i,x)
- 显示操作DispList(L)
线性表的顺序存储
顺序表
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表中的数据元素
顺序表基本运算的实现
顺序表类型定义
简单来说，线性表的顺序存储结构就是在内存中找一块地儿，把它占了，然后把相同数据类型的数据元素依次存放在这块空地中，所以可以直接用一个一维数组实现线性表的顺序存储结构
#define MAXLEN 100 //定义常量MAXLEN = 100用于表示存储空间的总量 typedef int DataType; //定义DataType为int型 typedef struct{ //顺序表存储类型 DataType data[MAXLEN]; //存放线性表的数组 int Length; //Length表示当前线性表的中长度 }SeqList; SeqList L; //定义一个顺序表，名字是L，同时它也是全局变量
顺序表SeqList是一个结构体类型，它由两个成员组成：data表示存储数据的数据和表示线性表当前实际的长度的Length
顺序表的初始化
初始化也就把线性表回到最初表长是0的状态，通过将记录线性表实际长度的Length置为0实现
void InitList(SeqList *L) { L->Length = 0; //初始化顺序表为空 }
顺序表的建立
从键盘录入n个数据，并将这些数据存入到顺序表中，修改表长
void CreateList(SeqList *L,int n) { int i; printf("请输入%d个整数：",n) ; for(i = 0; i < n;i++) scanf("%d",&L->data[i]); L->Length = i; //更新表长 }
查找操作
注意:顺序表中的位置是从1开始计数的，联系到日常生活中，说的是第1个位置，第2个位置，也没有说第0个位置的说法吧~。
但是用来记录顺序表的数组是0开始计数的
按位置查找
查找顺序表中第i个位置元素的值，在i无效时返回出错，有效是返回成功，并用指针x所指向的变量传回第i个元素的值
int GetElem(SeqList *L,int i,DataType *x) { //异常处理 if(i < 1 || i >L->Length) return 0; else { *x = L->data[i-1];//顺序表中的位置是从1开始计算的 return 1; } }
按值查找
在顺序表中查找与给定的x相等的数据元素的位置的所在位置。
int Locate(SeqList *L,DataType x) { int i = 0; while(i < L->Length && L->data[i] != x) i++; if(i >= L->Length) return 0; else return i+1; }
插入操作
实现思路：
- 特判。当插入的位置不合理了，抛出异常
- 将ai~an之间的所有结点依次后移，为新元素让出第i个位置
- 将新结点x插入到第i个位置
- 修改表长
参考实现代码：
int InsElem(SeqList *L,int i,DataType x) { int j; //异常处理 //表满了，不能插入了 if(L->Length >= MAXLEN) { printf("顺序表已满,无法插入"); return -1; } //提供的插入位置不合法 if(i < 1 || i > L->Length+1) { printf("插入位置出错，无法插入"); return 0; } //插入位置在表尾，直接插入即可 if(i == L->Length+1) { L->data[i-1] = x; L->Length++; return 1; } //插入到表中某个位置，则插入点后各个结点后移。 //可以取巧从末尾开始移动，那么每次都只用移动一位，不用每次都移动n-i位 for(j = L->Length-1;j >= i-1;j--) { L->data[j+1] = L->data[j]; L->data[i-1] = x; L->Length ++; return 1; } }
删除操作
实现思路：
- 将要删除的元素值，赋值给指针x所指的变量，需要这数据时就可以及时获得
- 将ai+1~an之间的结点依次向前移动
- 顺序表长度减1
参考实现代码：
int DelElem(SeqList *L,int i,DataType *x) { int j; // 异常处理 //顺序表为空 if(L->Length == 0) { printf("顺序表为空，无法删除"); return 0; } //给定删除位置不合法 if(i < 1 ||i > L->Length) { printf("不存在第i个元素"); return 0; } *x = L->data[i-1];// 用指针变量*x存储删除元素的值，用于返回 //移动数组，覆盖要删除的元素 for(j = i; j < L->Length;j++) L->data[j-1] = L->data[j]; //更新线性表长度 L->Length--; return 1; }
输出顺序表中数据
因为顺序表本质是数组，所以输出数据就是简单遍历数组就可以啦~
void DispList(SeqList *L) { int i = 0; for(i =0;i< L->Length;i++) printf("%d ",L->data[i]); }
