线性表的顺序存储
线性表的顺序存储一般表现为数组的方式，每个存储单元之间是连续的。
首先我们来定义一个线性表的结构体
typedef struct SqList {
ElemType elem[MAXSIZE]; // 线性表占用的空间
int length; // 当前数组长度（有效长度）
}SqList;
顺序表初始化
定义好之后，我们首先要做的是初始化一个顺序表
# define MAXSIZE 100 // 数组的最大长度
Status InitSqList(SqList &L){
L.elem = new ElemType[MAXSIZE];
if(!L.elem){ // 若内存空间分配失败
reutrn exit(OVERFLOW);
}
L.length = 0; // 数组长度初始化为0
return OK;
}
调用上面的函数后，一个线性表就初始化完成了，ElemType是任意的数据类型，在初始化的时候是什么改成什么就行。
在定义了一个ADT后我们需要为其提供一些常用的方法，如：取值、查找、删除、遍历等等，接下来我们就一一实现这些操作。
顺序表取值
我们知道顺序表其实相当于是一个数组，所以我们可以使用数组下标的方式来实现
Status GetItem(SqList L,int i,ElemType &e){
if(1 < 1||i>L.length){
return ERROR; // 若i小于1或大于数组长度，返回ERROR
}
e = L[i-1]; // 将第i-1个元素赋给e
return OK;
}
顺序表查找
查找这里指的是给定一个元素，在顺序表中查找第1个与其相等的元素
- 若成功，返回该元素下标+1（因为数组的下标是0开始的，不符合一般的计数习惯）
- 若失败，即没有元素与给定元素相等，则返回0
int FindElemLocation(SqList L,elemType e){
for (int i=0;i<L.length;i++){
if(L[i] == e){
return ++i;
}
}
return 0;
}
顺序表插入
顺序表的插入可能是顺序表最大的缺点了，因为顺序表的数据都是顺序存储的，如果要在第i的位置插入元素，那么i后面的元素都得依次后移，实现算法如下：
Status SqlListInsert(SqList L,int i,elemType e){
if(i<1||i>L.length){
return ERROR;
}
if (i==MAXSIZE){ // 若数组已满
return ERROR;
}
if(i>L.length){ // 若在当前数组末尾元素后添加
L.elem[i-1] = e;
return OK;
}
for (int j=L.length-1;j>=i-1;j--){
L.elem[j+1] = L.elem[j] // 第i个位置之后的元素统一后移
}
L.elem[i-1] = e;
++ L.length;
return OK;
}
有插入那么肯定就有删除，我们下面来实现删除的算法，和插入刚好相反，再删除一个数据元素后，这个数据元素之后的数据元素都需向前移动一个位置。
Status SqListDelete(SqList L,int i){
if(i<1||i>L.length){
return ERROR;
}
for (int j=i;j<=L.length-1;j++){
L.elem[j-1] = L.elem[j];
}
-- L.length;
return OK;
}
至此顺序表的基本操作就已经实现了。
线性表的链式存储
链表和顺序表最大的区别是，数据元素在物理上不是顺序存储的，只是在逻辑上是顺序连在一起的，这就意味着必须有个链条将每个数据元素都连接起来，没错，这个链条就是指针。
链表又分为单向链表和双向链表，我们先来看单向链表。
首先来看链表的ADT定义：
typedef struct LNode {
ElemType data;
LinkList *next;
}LNode,*LinklList;
由结构体可知，一个单链表的数据元素（又称结点）有两个属性，一个是data，是这个结点的数据元素对应的值，另外一个是next指针变量，用于存放下一个结点的地址。
所以当一堆LNode变量依次指向的时候，就形成了单链表。
但是这样连起来的结点，我们只知道下一个结点（后继结点）的位置，如果我们想要知道上一个结点（前驱结点）的位置就有点困难了，所以我们有了双向链表的概念。
typedef struct DuLNode {
ElemType data;
DuLNode *prior; // 直接前驱
DuLNode *next; // 直接后继
}DuLNode,*LinkList; //LinkList 为指向结构体 LNode 的指针类型
和顺序表一样，链表也有着类似的基本操作。
单链表初始化
#include <stdlib.h>
Status InitList(LinkList &L){
L = new Node; // 伪代码，真实代码参考下方
L = (DuLNode *)malloc(sizeof(DuLNode));
L -> next = NULL;
return OK;
}
单链表取值
和顺序表不同是，链表不能通过数组下标来取值了，针对无需单链表，只能从头遍历，通过计数器来取第i位置的元素
假设链表有头结点
Status GetElem(LinkList L,int i,ElemType &e){
LinkList *p = (LinkList *)malloc(sizeof(LinkList));
p = L -> next;
j = 1;
while(p&&j<i){
p = p -> next;
j++;
}
if(!p||j>i){ // 若此时P指向NULL，即链表长度小于i
return ERROR;
}
e = p -> data;
return OK;
}
单链表取值
和链表的取值一样，只是多了比较的步骤
LNode getElemLocation(LinkList L,ElemType e){
p = p -> next; // 让p指向首元结点
while(p){
if(p -> data == e){
return p;
}
}
return NULL;
}
单链表的插入
链表的插入和删除都是链表的优点，因为不是顺序存储的，在插入时我们只需要让第i-1个元素的next指针指向即将插入的元素，让即将插入元素的next指针指向原本第i个指针即可。
#include<stdlib.h>
Status ListInsert(LinkList &L,int i,ElemType e){
LNode *p = (LNode *)malloc(sizeof(LNode));
p = L;
int j = 0; // 计数器
while (p && j < (i - 1) ){ // 通过循环让p指向第i-1个元素
p = p -> next;
++j;
}
LNode *ENode = (LNode *)malloc(sizeof(LNode)); // 为e创建结点
ENode -> data = e;
ENode -> next = p -> next; // e结点的next指针指向第i-1个结点的下一个结点，也就是原本第i个结点
p -> next = ENode; // 第i-1个结点的next指针指向e结点
return OK;
}
单链表的删除
删除与插入一个道理，删除第i个结点时，我们只需要将第i-1个结点的next指针指向第i+1也就是指向第i个结点的next就行。
Status ListDelete(LinkList &L,int i){
int j=0; // 计数器
LNode *p = (LNode *)malloc(sizeof(LNode));
p = L;
while(p -> next && j < ( i -1 )){
p = p -> next;
++j;
}
if(!p || j > ( i - 1 )){
return ERROR;
}
LNode *q = (LNode *)malloc(sizeof(LNode)); // 临时结点
q = p -> next; // q中保存第i+1个结点的位置
p -> next = q -> next; // 第i-1个结点指向第i+1个结点
free(q);
return OK;
}
双向链表的插入和删除操作与单链表相同，只是需要改变双向的指针。
链表拓展
上面说的单链表和双链表最后一个结点的next都指向了NULL，意味着链表的结束
但是如果我们将最后一个结点指向头结点，这样就形成了一个环，这种链表叫做循环链表。
循环单链表的操作和单链表基本一致，差别仅在于：当链表遍历时，判别当前指针p是否 指向表尾结点的终止条件不同。在单链表中，判别条件为p!=NULL或p->next!=NULL, 而循环 单链表的判别条件为p!=L或p->next!=L。
Python版权声明：如无特殊说明，文章均为本站原创，转载请注明出处
本文链接：https://www.yangyingqi.com/50.html
