线性表
定义
- 线性表是具有相同特征的数据元素的一个有限序列
- a1,a2,a3·····,ai-1,ai,ai+1,······,an
- 上面元素称为数据元素
- a1 称为线性起点 an是线形终点，n为元素总个数，即表长
- ai-1是ai的直接前趋， ai+1是ai的直接后续
- 当n=0时，称为空表
- 线性表：
- 由n（n>=0）个数据元素（节点）a1,a2,a3,a4····an组成的有限序列
- 其中数据元素的个数n定义为表的长度
- 当n= 0时称为空表
- 当非空的线性表（n>0）记作：（a1,a2····an）
- 这里的数据元素ai(1<=i<=n)只是一个抽象的符号，其具体含义在不同情况下可以不同
逻辑特征
- 在非空线性表，有且仅有一个开始节点a1，他没有直接前趋，而仅有一个直接后续a2
- 有且仅有一个终端节点an,他没有直接后续，而且仅有一个直接前趋an-1
- 其余的内部节点ai(2<=i<=n-1)都有且仅有一个直接前趋ai-1和一个直接后续ai+1
案例
-
一元多项式的计算
-
当表达式为p0 + p1x^1 + p2x^2 + p3x^3 + ····pn*x^n;
-
可以使用以为数组来表示
Pn(x)
-
0 1 2 3 n p0 p1 p2 p3 pn Qn(x)
0 1 2 3 n q0 q1 q2 q3 qn 则线性表Rn(x) = Pn(x) + Qn(x) 为
0 1 2 3 n p0+q0 p1+q1 p2+q2 p3+q3 pn+qn
-
-
当我们遇见系数多项式的时候
S(x) = 1 + 3X10000+2X20000
这时候在使用上面的的方法未免有点太浪费空间了
所以我们应只是记录系数不为零的项
0 1 2 1 3 2 0 10000 20000 第二行表示多项式的系数
第三行表示多项式的指数
线性表 A = ((7,0),(3,1),(9,8),(5,17))
线性表 B = ((8,1),(22,7),(-9,8))
-
创建一个数组c
-
分别从头遍历比较a和b的每一项
指数相同，对应系数相加，若其和不为零，则在c中增加一个新项
指数不同，则将指数较小的项复制到c中
-
当一个多项式遍历完毕后，将另一个剩余的项依次复制到c中即可
-
-
顺序存储结构存在的问题
-
存储空间分配不灵活
-
运算的空间复杂度高
解决方法： 采用链式存储结构，动态分配内存
-
-
总结
- 线性表中数据元素的类型可以是简单类型（单纯的数字），也可以是复杂类型（有字符串）
- 许多实际应用问题所涉及的基本操作有很大的相似性，不应为每个具体单位单独编写一个程序
- 从具体应用中抽象出共性的逻辑结构和基本操作（抽象类型），然后实现其存储结构和基本操作
抽象数据类型线性表
-
定义
ADT liet
{
? 数据对象：D = {ai | ai 属于Elemset，（i = 1,2,3,····n,n>=0）}
? 数据关系：R = {<ai-1, ai>| ai-1, ai属于D(i = 1,2,····，n)}
? 基本操作：
? initlist（&l）；
? DestroyList（&l）;
? ClearList(&l);
? ListEmpty(L);
}ADT list
initlist（&l)
? 操作结果：构造一个空的线性表
DestroyList（&l）
? 初始条件：线性表L已经存在
? 操作结果：销毁线性表L；
ClearList(&l)
? 初始条件：线性表L已经存在
? 操作结果：将线性表L重置为空表
ListEmpty(L)
? 初始条件：线性表L已经存在。
? 操作结果： 若线性表L为空表，则返回True，否则返回False
顺序表
第二周第八节
顺序表的顺序存储表示
- 地址连续
- 依次存放
- 随机存取
- 类型相同
- 所以我们可以使用一维数组来表示顺序表
- 但是顺序表和链表都属于线性表，而线性表长度可以变换，但是数组长度不可以动态定义，所以我们需要使用一变量来表示顺序表的长度
#define LIST_LENGTH 100
typedef struct
{
int realpart;
int imagpart;
}ElemType;
typedef struct
{
ElemType elem[LIST_LENGTH];
int length;
}Sqlist;
- 上述代码可以表示线性表的模板， ElemType 可以变化你需要的数据类型， LIST_LENGTH表示动态的数组的长度，length表示实际的数组的长度
- 有两种顺序表的定义形式，一种是上面的直接定义，数据静态分配，还有一种是下面的
typedef struct
{
ElemType *data;
int length;
}Sqlist;
- 这种定义形式，在定义的时候没有给数组分配内存，需要在使用的时候静态分配一下
Sqlist L;
L.data = (ElemType*)malloc(sizeof(Elemtype)*MaxSize);
补充（顺序表的操作）
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
// Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char ElemType;
// 线性表的初始化
Status InitList_Sq(SqList &L)
{
L.elem = new ElemType[MAXSIZE];
if(!L.elem)exit(OVERFLOW);
L.lengh = 0;
return OK;
}
// 销毁
void DsetroyList(SqList &L)
{
if(L.elem)
delete L.elem; // 释放空间
}
// 清空线性表L
void ClearList(SqList &L)
{
L.length = 0; // 将线性表的长度置为零
}
// 得到i位置上的元素
int GetElem(SqList L, int i, ElemType &e)
{
// 判断i的值是否合理，若不合理，返回ERROR
if(i < 1 || i < L.length)
return ERROR;
e = L.elem[i-1];
return OK;
}
顺序表的查找算法分析
顺序查找法：
? 将表中元素进行遍历，依次比较如果查找出来则返回对应的记录， 如果没找到则返回0；
? 例如一个长度为7的数组进行查找，最少找一次，最多找7次，那么平均一共找4次即可。
-
平均查找长度ASL（Average Search Length）
- 为了确定记录在表中的位置，需要与给定值进行比较的冠军字的个数的期望值叫做查找算法的平均查找长度
-
对含有n个记录的表，查找成功时：
? ASL = （i从1到n加）PiCi = （n+1）/2；
? Pi第i个记录被查找的概率
? Ci找到第i个记录需要比较的次数
? 例如上面的长度为7的数组查找到平均长度为1/7乘1 + 1/7乘2 + ····1/7乘7 每一个的查找的概率都是1/7， 只是查找到需要的次数不同。
顺序表的插入算法分析
-
插入位置在最后：这接放在最后即可
-
插入位置在中间：让别插入的位置的后面的元素依次向后移
-
插入位置在最前面： 让所有位置依次往后移，给这个位置移出来地方
-
算法思想
-
插入位置的判断（0-数组长度）
-
判断顺序表的存储空间是否已满，若已经满了则返回ERROR
-
将第n至i为的元素依次向后移动一个位置，空出第i个位置
-
将要插入的新元素e放入第i个位置
-
表长加一
Status ListInsert_Sq(SqList &L, int i,ElemType e) { if( i < 1 || i > L.length + 1)return ERROR; if(L.length == MAXSIZE) return ERROR; for(j = L.length-1; j >= i-1; j--) { L.elem[j+1] = L.elem[j]; } L.elem[i-1] = e; L.length++; return OK; }-
时间分析
-
若插入在为节点则无需移动（特别快）
-
若插入在首节点。则表中元素都向后移（特别慢）
-
若要考虑在各种位置插入（共n+1种情况）
E(ins) = 1/(n+1)(从1到n+1)[n-i+1] = 1/(n+1) *(0+1+2+3+·····n) = 1/（n+1） * n(n+1)/2 = n/2;
-
时间复杂度O(n);
-
-
-
顺序表删除
- 删除位置在最后：直接删除即可，length-1；
- 删除位置在中间：需要删除该位置的元素，并将该位置后面的元素依次前移
- 删除位置在最前面：删除完毕后依次前移即可
- 算法思想
- 判断删除位置i是否合法（合法值为1<=i<=n）
- 将欲删除的元素保留在e中
- 将第i+1至第n位的元素依次前移一个位置
- 表长减一，删除成功后返回OK
- 算法的实现
Status ListDelete_Sq(SqList &L, int i, int e)
{
if((i<1)||(i>L.length))return ERROR;
e = L.elem[i-1];
for(j = i;j <=L.length-1; j++)
L.elem[j-1] = L.elem[j];
L.length--;
return e;
}
-
时间消耗分析
i=1 i=2 i=3 ···· i = n n-1 n-2 n-3 ···· 0 E(del) = 1/n (i从1到n)（n-i） = 1/n * (n-1)*n/2 = (n-1)/2;
时间复杂度为O(n);
顺序表总结
- 顺序表的特点：
- 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系即线性表的逻辑结构与存储结构一致
- 在访问线性表时，可以快速的计算出任何一个数据元素的存储地址，因此可以粗略的认为，访问每个元素所化的时间相等
- 这种存取元素的方法称为随机存取法
- 顺序表的操作算法分析
- 时间复杂度
- 查找，插入，删除，算法的平均时间复杂度为O(n)
- 空间复杂度
- S(n) = O(1)
- 没有辅助空间
- 时间复杂度
类c语言补充（c语言版）
- 其中Elemtype表示该数据类型的长度， MaxSize表示数组的长度；
- sizeof(Elemtype)*MaxSize 表示需要从内存中获取这么大的地址，而这么大的地址将要去干什么，是存除整形，浮点型，还是结构体，这就需要我们前面括号里的（ElemType *）来表示
- 使用ElemType*除了表示为这些内存空间需要存放的数据类型， 还能进行数据类型的强制转换，因为L.data 应该存储数组的首地址
- malloc（m）开辟m字节长度的地址空间，并返回这段空间的首地址
- sizeof（x），计算变量x的长度
- free（p），释放指针p所指变量的内存，彻底删除一个变量
- 都需要加载头文件 <stdlib.h>
类c语言补充（c++版）
-
使用new来代替c语言中malloc的臃长代码
new 类型名T(初始值表)
? 功能： 申请用于存放T类型对象的内存空间，并依初值列表来赋初值
? 结果值：
? 成功：T类型的指针，指向新分配的内存
? 失败： 0（NULL）
-
delete 指针p
功能：
? 释放指针p所指向的内存，p必须是new操作的返回值
-
函数调用时传送给形参表的实参必须是形参三个一致
? 类型，个数，顺序
-
参数传递时有两种方式
-
传值方式：参数为整型，实型，字符型等；
-
传地址
-
参数为指针变量
-
参数为引用类型
这个是c++中的语法
void main() { int i = 5; int &j = i; i = 7; }则j也等于7； 其中第二个步骤的含义就是j 是 i 的别名，他们俩是同一个东西，改一动二
- 以下是交换a,b值的方法
// 第一种 int main() { float a,b; swap(&a,&b); } void swap(float *m, float *n) { float temp; temp = *m; *m = *n; *n = temp; } // 第二种 c++方法 int main() { float a,b; swap(a,b); } // 这里就是交换ab的值， 使用c++中的语法 & 来给a,b取别名，从而交换mn的值来交换ab的值 void swap(float &m, float &n) { float temp; temp = m; m = n; n = temp; }
-
-
-
参数为数组名
-
引用类型做形参的三点说明
- 传递引用给参数与传递指针的效果是一样的，形参变换实参也发生变化
- 引用类型作为形参，在内存中并没有产生实参的副本，它直接对实参操作；而一般变量作为参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本，因此，当参数传递数据量较大时，用引用比用一般变量传递参数的时间和空间效率都好
- 指针参数虽然也能达到与使用引用的效果，但在被调函数中需要重复使用“*指针变量名”的形式进行运算，者恒容易产生错误且程序阅读性较差，另一方面，再主调函数的调用点出，必须使用变量的地址作为实参
链表
链表的链式表示和实现
- 链式存储结构
- 节点在存储器中的位置是任意的，即逻辑上相邻的数据元素，在物理上不一定相邻
- 线性表的链式表又称为非顺序映像或链式映像
- 用一组物理位置任意的存储单元来存放链表的元素
- 这组存储单元可以是连续的，也可以是分散的，
- 链表中元素的逻辑次序和物理次序不一定相同
- 与链式存储有关的术语
- 节点：
- 数据元素的存储映像，由数据域和指针域组成
- 链表：
- n个节点由指针链组成一个链表
- 他是线性表的链式存储映像，称为线性表的链式存储结构
- 节点：
链表形式
-
单链表
- 结点只有一个指针域的链表，称为单链表，或线性链表
-
双链表
- 节点有两个指针域的链表称为双链表
-
循环链表
- 首位相接的链表称为循环链表
-
头指针，头结点，首元节点
- 头指针：指向链表中的第一个结点的指针
- 首元节点：是指向链表中存储第一个数据元素a1的节点
- 头结点：是在链表中的首元节点之前附设的一个节点
-
链表的两种形式
-
带头结点的
-
不带头结点的
-
讨论：在链表中设置头结点有什么好处
-
便于首元节点的处理
首元节点的地址保存在头结点的指针域中，所以在链表中第一个位置操作和其他位置相同，无需进行任何处理
-
便于空表和非空表的统一处理
无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就同一了
-
-
讨论：头结点的数据域内装的是什么
? 头结点的数据域可以为空，可以存放表的长度等附加信息，但是此节点不能计入链表长度值
-
-
如何表示空表
- 无头结点的时候： 头指针为空时表示空表
- 有头结点的时候：头结点的指针域为空表示空表
-
链表的特点
- 节点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
- 访问时只能通过头指针进入链表，并通过每一个节点的指针域依次向后顺序扫描其余节点，所以寻找第一个，和最后一个所花费的时间不同顺序存取法
单链表
-
单链表的命名
- 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名，若头指针名是L，则把链表称为表L
-
单链表基本操作的实现
-
单链表的初始化
- 即构造一个空表
-
算法步骤
- 生成新节点作头结点，用头指针L指向头结点
- 将头结点的指针域置空
-
算法描述
// 初始化 Status LnitList_L(LinkList &L) { L = new LNode; // 或者 L = (LNode*)malloc(sizeof(LNode)); L->next = NULL; return OK; } -
补充算法------判断链表是否为空
-
空表： 链表中无元素，称为空链表（头指针和头结点仍然存在）
-
算法思路：判断头结点的指针域是否为空
int ListEmpty(LinkList L) { if(L->next) return 0; else return 1; } -
补充算法-------单链表的销毁，链表销毁后不存在（头结点，头指针都不存在）
-
算法思路：从头指针开始，依次释放所有的结点，这里需要有两个指针变量，一个指向头结点，另一个指向头结点的下一个
-
循环结束条件 头指针为空
Status DeleteList_L(LinkList *L)//销毁单链表L { Londe *p; p = (LNode*)malloc(sizeof(LNode)); while(L)//循环结束条件L不为空 { p = L;//先将头结点地址赋值给临时变量 L = L->next;//再将头指针指向下一个 free(p);//释放该节点 } return OK; }-
补充算法 ------ 清空链表
-
链表仍然存在，但链表中无元素，成为空链表（头结点，头指针依然存在）
-
算法思路，依次释放所有结点，并将头结点指针域设置成空
-
循环结束条件 指向最后一个元素
Status ClearList_L(LinkList *L)//清空单链表L { Londe *p,*q; p = L->next; while(p)//循环结束条件指向最后一个了 { q = p->next; free(p);//释放该节点 p = q; } L->next == NULL; return OK; }-
补充算法 ---- 求单链表的表长
-
思路：从首元节点开始，依次计数所有结点
int ListLength_L(LinkList L) // 返回值中数据元素的个数 { int i = 0; LNode *p; p = L->next; while(p) { i++; p = p->next; } return i; } -
取值-----取单链表中第i个元素的内容
-
思路：从链表的头指针出发顺着链域next逐个结点往下搜索，知道索搜到第i个结点为止，因此，链表不是随机存取结构
-
步骤：
-
从第一个结点（L->next）顺链扫描用指针p记录当前所扫描到的结点，p的初值为p=L->next
-
.j做计数器，累计当前扫描过的节点数，j的初值为1
-
当p指向扫描到的下一节点的时候，计数器j+1
-
当j === i时找到，退出程序
Status GetElem_L(LinkList L, int i, ElemType &e) // 获取线性表中的某个数据元素，通过变量e返回 { p = L->next; while(p&&j<i) { p = p->next; j++; } if( j == i) { e = p->data } else { return ERROR; } }
-
查找：
- 按值查找：根据指定数据获取该数据所在的位置（该数据的地址）
- 按值查找：根据指定数据获取该数据所在的位置序号（是第几个数据元素）
-
插入：在第i个结点前插入新结点
Lnode *LocateElem_L(LinkList L, Elemtype e) // 在线性表中查找值为e的数据元素 // 找到，则返回L中值为e的数据元素的地址，查找失败返回NULL { LinkList p; p = L->next; while(p&&p->data!=e) { p = p->next; } // 返回地址 return p; } Lnode *LocateElem_L(LinkList L, Elemtype e) // 在线性表中查找值为e的数据元素 // 找到，则返回L中值为e的数据元素的位置，查找失败返回NULL { int i = 1; LinkList p; p = L->next; while(p&&p->data!=e) { p = p->next; i++ } // 返回地址 if( p!=NULL) { return i; } else { return 0; } } -
插入：在第i个结点前插入新节点
Status ListInsert_L(LinkList &L, int i, Elemtype e) // 在L中第i个元素之前插入数据元素e { int a = 0; LinkList p, q; p = L; while(a < i-1 && p) { p = p->next; a++; } if( a == i-1 ) { q = (LNode*)malloc(sizeof(LNode)) q->data = e; p->next = q->next; p->next = q; // 这两步交换位置的算法不能颠倒先后位置，否则会导致，数据丢失，交换失败 return OK; } else { return ERROR } } -
删除 删除第i个结点
Status ListDelete_L(LinkList &L, int i, Elemptype &e) // 在L中删除第i个元素 { int a = 0; LinkList p, q; p = L; while(p->next && a <i-1) { p=p->next; a++; } if( !(p->next) || a >i-1) return ERROR; q = p->next; e = q->data;//保存要删除的元素的位置 p->next = q->next; free(q); return OK; }
-