数据结构第二章——线性表的定义和特点
线性表的定义和特点
线性表是具有相同特性的数据元素的一个有限序列
- 其中数据元素的个数n定义为表的长度
- 当n = 0时称为空表
线性表的逻辑特征：
- 在非空的线性表，有且仅有一个开始结点a1,他没有直接前驱，儿仅有一个直接后继a2
- 有且仅有一个终端结点an,它没有直接后继，而仅有一个直接前驱an-1
- 其余的内部结点ai(2 <= i <= n - 1)都仅有一个直接前驱ai-1和一个直接后继ai+1
线性表的顺序存储表示
线性表的顺序表示又称为顺序存储结构或顺序影响
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储结构。简言之，逻辑上相邻的数据，物理上也相邻
线性表的定义：
#define MAXSIZE 100 //顺序表可能达到的最大的长度
#define OK 1
#define TRUE 1
#define ERROR 0
#define OVERFLOW -2
typedef struct{
ElemType elem [MAXSIZE] //存储空间的基地址
int length; //当前长度
}SqList; //定义顺序表类型
SqList L;//定义变量L，L是SqList这种类型的，L是个顺序表
//线性表L的初始化
Statu InitList(SqList &L){
//构建一个空的顺序表L
L.elem = new ElemType[MAXSIZE];//为顺序表分配空间
if(!L.elem) exit(OVERFLOW);//存储分配失败
L.length = 0;//空表长度为0
return OK;
}
//销毁线性表
void Destory(SqList &L){
if(L.elem) delete L.elem;//释放存储空间
}
//清空线性表
void ClearList(SqList &L){
L.length = 0;
}
//判断线性表L是否为空
int IsEmpty(SqList L){
if(L.length == 0) return 1;
else return 0;
}
//求线性表的长度
int GetLength(SqList L){
return (L.length);
}
//顺序表的取值
Status GetElem(SqlList L, int i, ElemType &e){
if(i<1 || i > L.length) return ORRER;//判断i值是否合理，若不合理，返回ERROR
e = L.elem[i-1];//第i-1的单元存储这第i个数据
return e;
}
//顺序表的查找
//从表的一端开始，逐个进行记录的关键字和给定值的比较。找到，返回该元素的位置序号，未找到返回0
int LocateElem(SqList L, ElemType e){
//在顺序表L中查找值为e的数据元素，返回其序号
for(int i = 0l i < L.length; i++)
if(L.elem[i] == e) return i + 1;//查找成功，返回序号i+1
return 0;//查找失败，返回0
}
补充：C语言的内存动态分配
- malloc(m)函数，开辟m字节长度的地址空间，并返回这段空间的首地址
- sizeof(x)运算，计算变量x的长度
- free§函数，释放指针p所指变量的存储空间，即彻底删除一个变量
- 需要加载头文件<stdlib.h>
补充:C++的动态存储分配
new 类型名T（初值列表）
功能：申请用于存放T类型对象的内存空间，并依初值列表赋以初值结果值：
例如 int *p1 = new int 或 int *p1 = new int(10);
delete 指针p
功能：释放指针p所指向的内存，p必须是new操作的返回值。
补充:C++中的参数传递
函数调用时传送给形参列表的实参必须与参数三个一致：类型、个数、顺序。
参数传递有两种方式：
-
传值方式（参数为整型、实型、字符型等）：把实参的值传送给函数局部工作区相应的副本中，函数使用这个副本执行必要的功能，函数修改的是副本的值，实参的值不变
-
#include <iostream.h> void swap(float m, float n){ float temp; temp = m; m = n; n = temp; } void main(){ int a, b; cin >> a >> b; swap(a, b); cout << a << b << endl; }
-
-
传地址
- 参数为指针变量
- 参数为引用类型
- 引用就是给一个名字取一个代名词
- 参数为数组名
引用类型做形参的三点说明：
- 传递引用个函数与传递指针的效果是一样的，形参变化实参也发生变化
- 引用类型作形参，在内存中并没有产生实参的副本，它直接怼实参操作，儿一般变量作参数，形参与实参就占用不同的存储单元，所以形参 变量的值就是实参变量的副本。因此，当参数传递的数据量较大时，用引用比用一般变量传递参数的时间和空间效率逗号
- 指针参数虽然也能达到与使用引用的效果一样，但在被调函数中需要重复使用“*指针变量名”的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用变量的地址作为实参
顺序表的插入
线性表的插入运算是指在表的第i(1 <= i <= n + 1)个位置上，插入一个新结点e，使长度为n的线性表（a1, a2, a3,ai-1,ai……，an）变成长度为n + 1的线性表
算法思想：
- 判断插入位置i是否合法
- 判断顺序表的存储空间是否已满，若已满返回ERROR。
- 将第n至第i位的元素一次向后移动一个位置，空出第i个位置
- 将要插入的新元素e放入第i个位置
- 将表长+1
算法实现：
int ListInsert_Sq(SqList &L, int i, int 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;
}
顺序表插入的平均时间复杂度是O(n)
顺序表的删除
线性表的删除运算是指将表的第i（1 <= i <=n）个元素删除，使长度为n的线性表变成长度为n - 1的线性表
算法思想
- 判断删除位置i是否合法（合法值为1 <= i <= n）
- 将欲删除的元素保留在e中
- 将第i + 1至第n位的元素一次向前移动一个位置
- 表长减1，删除成功返回OK。
算法实现
int ListDelete_Sq(SqList &L, int i){
if(i < 1 || i > L.length) return ERROR;//i值不合法
for(j = i; i <= L.length - 1; j++){
L.elem[j - 1] = L.elem[j];//被删除元素之后的元素前移
L.length--;//表长减1
return OK;
}
}
顺序表删除算法的平均时间复杂度为O(n)
顺序表优缺点：
优点：
- 存储密度大（结点本身所占存储量/结点结构所占存储量）
- 可以随机存取表中任一元素
缺点：
- 在插入、删除某一元素时，需要移动大量元素
- 浪费存储空间
- 属于静态存储形式，数据元素的个数不能自由扩充
链表的链式表示和实现
- 用一组物理位置任意的存储单元来存放线性表的数据元素
- 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中id任意位置上的
- 链表中元素的逻辑次序和物理次序不一定相同。
与链式存储有关的术语
1、结点：数据元素的存储映像。由数据域和指针域两部分组成
链表：n个结点由指针链组成一个链表。它是线性表的链式存储影响，称为线性表的链式存储结构
单链表、双链表、循环链表
- 结点只有一个指针域的链表，称为单链表或线性链表
- 结点由两个指针域的链表，称为双链表
- 首尾相接的链表称为循环链表
头指针、头结点和首元结点
头指针：是指向链表的第一个结点的指针
首元结点：是指链表中存储第一个数据元素a1的节点；
头结点：是在链表的首元结点之前附设的一个结点；
如何表示空表
- 无头结点时，头指针为空时表示空表
- 有头结点，当头结点的指针域为空时表示空表
在链表中设置头结点的好处
- 便于首元结点的处理：首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一直，无须进行特殊处理
- 便于空表和非空表的统一处理：无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了
头结点的数据域内装的是什么
头结点的数据域可以为空，也可以存放线性表等的附加信息，但此结点不能计入链表长度值
链表（链式存储结构的）特点
- 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
- 访问时只能通过头指针进入链表，并通过每个结点的指针域一次向后顺序扫描其余节点，所以寻找第一个结点和最后一个结点所花费的时间不等
单链表的定义和表示
typedef struct Lnode{//声明结点的类型和指向结点的指针类型
ElemType data;//结点的数据域
struct Lnode *next;//结点的指针域
}Lnode, *LinkList;//LinkList为指向结构体Lnode的指针类型
定义链表：Lnode L;
定义结点指针p:LNode *p《=》LinkList p
举例：存储学生学号、姓名、成绩的单链表结点类型定义如下：
typedef Struct student{
char num[8];//数据域
char name[8];//数据域
int score;//数据域
struct student *netx;//指针域
}Lnode, *LinkList;
为了统一链表的操作，通常这样定义：
typedef Struct{
char num[8];//数据域
char name[8];//数据域
int score;//数据域
}Elemtype;
typedef struct Lnode{
ElemType data;//数据域
strcut Lnode *next;//指针域
}Lnode, *LinkList;
单链表的初始化（带头结点的单链表）
步骤：
- 生成新结点作头结点，用头指针L指向头结点
- 将头结点的指针域置为空。
typedef struct Lnode{
ElemType data;
struct Lnode *next;
}LNode, *LinkList;
Status InitList(LinkList &L){
L = new Lnode;//或L = （LinkList） malloc(sizeof(Lnode))
L->next = NULL;
return OK;
}
//判断链表是否为空
//空表：链表中无元素，称为空链表（头指针和头结点仍然在）
int ListEmpty(LinkList L){//若L为空表，则返回1，否则返回0
if(L->next)//非空
return 0;
else
return 1;
}
//单链表的销毁：销毁后的链表不存在
//算法思路：从头指针开始，依次释放所有结点
Status DestoryList_L(LinkList &L){
Lnode *p;
while(L){
p = L;
L = L->next;
delete p;
}
return OK;
}
//清空链表
//链表仍然存在，但链表中无元素，称为空链表
//算法思路：依次释放所有结点，并将头结点指针域设置为空
Status ClearList_L(LinkList &L){//将L重置为空表
Lnode *p, *q;
p = L -> next;
while(p){
q = p -> next;
delete p;
p = q;
}
L->next = NULL;//头结点指针域为空
return OK;
}
//求单链表的表长
int getListLength(LinkList L){//返回L中数据元素的个数
LinkList p;
int length = 0;
p = L->next;
while(p){
length++;
p = p->next;
}
return length;
}
取值——取单链表中第i个元素的内容
算法步骤：
- 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p = L -> next
- j做计数器，累计当前扫描过的结点数，j初值为1
- 当p 指向扫描到的下一结点时，计数器j 加1
- 当j == i时，p所指的结点就是要找的第i个结点
算法实现
int getElem_L(LinkList L, int i, int &e){
//获取线性表L中的某个元素的内容，通过变量e返回
LinkList p;
p = L->next;
j = 1;
while(p&&j<i){
p = p -> next;
++j;
}
if(!p || j > i) return ERROR;//第i个元素不存在
e = p->data;
return e;
}
按值查找——根据指定数据获取该数据所在的位置（地址）
算法步骤：
- 从第一个结点起，依次和e相比较
- 如果找到一个其值与e相等的数据元素，则返回其链表中的位置或地址
- 如果查边整个链表都没找到其值和e相等的元素，则返回0或NULL
Lnode *LocateElem_L(LinkList L, int e){
//在线性表L中查找值为e的数据元素
//找到，则返回L中值为e的数据元素的地址，查找失败就返回NULL
LinkList L;
p = L->next;
while(p && p->data != e){
p = p->next;
}
return p;
}
按值查找——根据指定数据获取数据位置序号
//在线性表L中查找值为e的数据元素的位置序号
int LocateElem_L(LinkList L, int e){
//返回L中值为e的数据元素的位置序号,查找失败返回0
LinkList p;
p = L->next;
j = 1;
while(p && p->data != e){
p = p->next;
j++;
}
if(p)
return j;
else
return 0;
}
插入——在第i个结点前插入值为e的新结点
算法步骤：
- 首先找到ai-1的存储位置p
- 生成数据域为e的新结点s
- 插入新结点
- 新结点的指针域指向ai
- 结点ai-1的指针域指向新结点
//在L中的第i个元素之前插入数据元素e
int ListInsert_L(LinkList &L, int i, int e){
LinkList p;
int j = 0;
while(p && j < j - 1){
p = p->next;
++j;
}
if(!p || j > i - 1) return ERROR;
s = new LNode;
s -> data = e;
s -> next = p -> next;
p -> next = s;
return OK;
}
删除——删除第i个结点
算法步骤
- 先找到第i-1个结点的存储位置p，保存要删除的ai的值
- 令p->next指向ai+1
- 释放结点ai的空间
算法描述
//将线性表L中的第i个数据元素删除
int ListDelete_L(LinkList &L, int i, int &e){
LinkList p, q;
int j = 0;
while(p -> next && j < i - 1){
p = p -> next;
++j;
}//寻找第i个结点，并令p指向其前驱
if(!(p->next) || j > i - 1) return ERROR;//删除位置不正确
q = p -> next;//临时保存被删除结点的地址以备
p -> next = q -> next;//改变删除结点前驱结点的指针域
e = q -> data;//保存删除结点的数据域
delete q;//释放删除结点的空间你
return OK;
}
建立单链表：头插法——元素在链表头部，也叫前插法
void CreateList_H(LinkList &L, int n){
L = new LNode;
L->next = NULL;//先建立一个带头结点的单链表
for(int i = n; i > 0; --i){
p = new LNode;//生成结点p
cin >> p->data;输入元素值
p->next = L -> next;//插入到表头
L->next = p;
}
}
建立单链表：尾插法——原数插入在链表 尾部，也叫后插法
步骤
- 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点
- 初始时，r同L均指向头结点，每读入一个数据元素则申请一个新结点，将新结点插入到尾结点多厚，r指向新结点
void CreateList_R(LinkList &L, int n){
L = new LNode;
L -> next = NULL;
r = L;//尾插法r指向头结点
for(int i = 0; i < n; i++){
p = new LNode;//生成新结点，输入元素值
cin >> p -> data;
p->next = NULL;
r->next = p;//插入到表尾
r = p;//r指向新的尾结点
}
}
循环链表：
是一种头尾详解的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）
优点
从表中任一结点出发均可找到表中其他结点。
注意
由于循环链表没有NULL指针，故设计遍历操作时，其中其终止条件就不再像非循环链表那样判断p或p->next是否为空，而是判断它们是否等于头指针
循环条件：
LinkList Connect(LinkList Ta,LinkList Tb){//假设Ta\tb都是非空的单循环链表
LinkList p;
p = Ta -> next;//p存放表头结点
Ta -> next = Tb -> next -> next;//Tb表头连接Ta表尾
delete Tb -> next;//释放Tb表头结点
Tb->next = p;//修改指针
return Tb;
}
双向链表
在单链表的每个结点在增加一个指向其直接前驱的指针域Prior，这样链表就形成了有两个方向不同的链，故称为双向链表
双向链表的结构可定义如下
typedef struct DuLNode{
Elemtype data;
struct DiLNode *prior, *next;
}DuLNode, *DuLinkList;
双向循环链表
和单链表的循环表类似，双向链表也可以有循环表
- 让头结点的前驱指针指向链表的最后一个结点
- 让最后一个结点的后继指针指向头结点
双向链表结构的对称性（设指针p指向某一节点）
p -> prior ->next = p = p -> next -> prior
双向链表的插入
int ListInsert_DuL(DuLinkList &L, int i, int e){
//在带头结点的双向循环链表L中的第i个位置之前插入元素e
if(!(p = GetElemP_DuL(L,i))) return ERROR;
s = new DuLNode;
s -> data = e;
s -> prior = p -> prior;
p -> prior -> next = s;
s -> next = p;
p -> prior = s;
return OK
}
双向链表的删除(时间复杂度O（n）)
int ListDelete_Dul(DuLink &L, int i, int &e){
//删除带头结点的双向循环链表L的第i个元素,并用e返回
if（!( p = GetElemP_DuL(L,i))） return ERROR;
e = p -> data;
p -> prior -> next = p->next;
p -> next -> prior = p -> prior
free(p);
return OK;
}
单链表、循环链表和双向链表的时间效率比较
顺序表和链表的比较
链式存储结构的优点：
- 结点空间可以动态申请和释放
- 数据元素的逻辑次序依靠结点的指针来表示，插入和删除时不需要移动数据元素
链式存储结构的缺点：
- 存储密度小，每个结点的指针域需额外占用存储空间，当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显然很大。
- 链式存储结构是非随机存储结构。对任意结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度。
线性表的应用
线性表的合并
假设利用两个线性表La和Lb分别表示两个结合A和B，现要求一个新的集合A∪B
La = (7, 5, 3, 11) Lb = (2, 6, 3) => La = (7, 5, 3, 11, 2, 6)
算法步骤
- 依次取出Lb中的每个元素，执行以下步骤
- 在La中查找该元素
- 如果找不到，则将其插入La的最后
void union(List &La, List Lb){
La_Len = ListLength(La);
Lb_Len = ListLength(Lb);
for(int i = 1; i < Lb_Len; i++){
GetElem(Lb,i,e);
if(!LocateElem(La, e)) ListInsert(&La, ++La_Len, e);
}
}
有序表的合并
已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素按值非递减有序排列
La = (1, 7, 8) Lb = (2, 4, 5, 6, 8, 10, 11) => Lc = (1, 2, 4, 6, 7, 8, 8, 10, 11)
算法步骤
-
创建一个空表Lc
-
依次从La或Lb中“摘取”元素值较小的节点插入到Lc表的最后，直至其中一个表变空位置
-
继续讲La或Lb其中一个表的剩余节点插入在Lc表的最后
void MergeList_Sq(SqList LA, SqList Lb, SqList &Lc){
pa = LA.elem;//指针pa和pb的初值分别指向两个表的第一个元素
pb = Lb.elem;
Lc.length = LA.length + Lb.length;//新表长度为待合并两个表的长度之和
Lc.elem = new ElemType[Lc.length];//为合并后的新表分配一个数组空间
pc = LC.elem;//指针pc指向新表的第一个元素
pa_last = LA.elem + LA.length - 1;//指针pa_last指向LA表的最后一个元素
pb_last = Lb.elem + Lb.length - 1;//指针pb_last指向Lb表的最后一个元素
while(pa <= pa_last && pb <= pb_last){//两个表都非空
if(*pa <= *pb) *pc++ = *pa++;
else *pc++ = *pb++;
}
while(pa <= pa_last) *pc++ = *pa++;//Lb表已经到达表尾，将LA中剩余元素加入Lc
while(pb <= pb_last) *pc++ = *pb++;//LA表已到达表尾，将LB剩余元素加入LC
}
有序表的合并——用链表实现
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){
pa = La -> next;
pb = Lb -> next;
while(pa && pb){
if(pa -> data <= pb -> data){
pc -> next = pa;
pc = pa;
pa = pa -> next;
}
else{
pc -> next = pb;
pc = pb;
pb = pb -> next;
}
}
pc -> next = pa ? pa : pb;//插入剩余段
delete Lb;//释放Lb的头结点
}
ast指向LA表的最后一个元素
pb_last = Lb.elem + Lb.length - 1;//指针pb_last指向Lb表的最后一个元素
while(pa <= pa_last && pb <= pb_last){//两个表都非空
if(*pa <= *pb) *pc++ = *pa++;
else *pc++ = *pb++;
}
while(pa <= pa_last) *pc++ = *pa++;//Lb表已经到达表尾，将LA中剩余元素加入Lc
while(pb <= pb_last) *pc++ = *pb++;//LA表已到达表尾，将LB剩余元素加入LC
}
### 有序表的合并——用链表实现
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){
pa = La -> next;
pb = Lb -> next;
while(pa && pb){
if(pa -> data <= pb -> data){
pc -> next = pa;
pc = pa;
pa = pa -> next;
}
else{
pc -> next = pb;
pc = pb;
pb = pb -> next;
}
}
pc -> next = pa ? pa : pb;//插入剩余段
delete Lb;//释放Lb的头结点
}