数据结构-2:线性表
线性表
定义
线性表是具有相同数据类型的$n(n\geq0)$个数据元素的有限序列,其中$n$为表长,当$n$为$0$时线性表是一个空表。一般表示为$L=(a_1,a_2,\cdots,a_i,a_{i+1},\cdots,a_n)$ \
一些基本操作
- 线性表的位序从1开始,而不是像数组一样从0开始
顺序表
用顺序存储的方式来实现线性表
实现方式
静态分配
#define MaxSize 10
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
最大长度不可改变(静态)
初始化
void InitList(SqList &L){ for (int i=0; i<MaxSize; i++){ L.data[i]=0; } L.length=0;//初始长度为0 }
- 必须声明长度为0
- 访问时要求不超过长度,因此初始化成0可以省略(编译器一般会初始化)
动态分配
#define InitSize 10
typedef struct{
ElemType *data;
int MaxSize;
int length;
}SeqList;
动态申请和释放内存空间
C——malloc
free
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
申请一片连续的空间
malloc
返回一个指针,强制转换
C++——new
delete
- 增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
int* p = L.data;
L.data=(int*)malloc((L.Maxsize+len)*sizeof(int));
for(int i=0;i<L.length;i+=){
L.data[i]=p[i];
}
L.MaxSize=L.MaxSize+len;
free(p);
}
顺序表的特点
- 随机访问:可以在$O(1)$时间内找到第i个元素
- 存储密度高
- 拓展容量不方便(动态时需要复制,时间开销大)
- 插入等操作不方便
基本操作
插入
ListINsert(&L, i, e)
, 在表L的第i个位置插入元素e
#define MaxSize 10
typedef struct{
int data[MaxSize];
int length;
}SqList;
void ListInsert(SqList &L, int i, int e){
///⭐️
//从最后一位到插入点依次向后挪
for(int j=L.length;j>=i;j--){
L.data[j]=L.data[j-1];
}
L.data[i-1]=e;
L.length++;
}
为了使得代码具有「健壮性」,应该在⭐️处插入对i的判断,并返回bool型
bool ListInsert(SqList &L, int i, int e){
if (i<1 || i>L.length+1)
return false;
if (L.length>=MaxSize)
return false;
//...
return true
}
时间复杂度$O(n)$
删除
bool ListDelete(SqList &L, int i, int &e){
if (i<1 || i>L.length) //判断有效性
return false;
e=L.data[i-1]; //将被删除的元素赋值给e
for (int j=i;j<L.length;j++)
L.data[j-1]=L.data[j];
L.length--;
return true;
}
查找
按位查找
ElemType GetElem(SqList L, int i){
return L.data[i-1];
}
按值查找
int LocateElem(SeqList L, int e){
for (int i=0;i<L.length;i++)
if(L.data[i]==e)
return i+1;
return 0;
}
单链表
链式存储的线性表
定义
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
typedef <数据类型> <别名>
在这里,
LNode
强调结点而LinkList
强调链表声明一个指向单链表第一个结点的指针可以
LNode * L
; 或者LinkList L;
初始化
不带头结点
typedef struct LNode{
ElemType data;
struct LNode* next;
}LNode, *LinkList;
bool InitList(LinkList &L){
L=NULL;
return true;
}
空表判断:L==NULL
带头结点
typedef struct LNode{
ElemType data;
struct LNode* next;
}LNode, *LinkList;
bool InitList(linkList &L){
L = (LNode*)malloc(sizeof(LNode));
if(L==NULL)
return false;
L->next = NULL;
return true;
}
空表判断:L->next==NULL
基本操作
插入
按位序插入
带头结点
bool ListInsert(linkList &L, int i, ElemType e){ if(i<1) return false; LNode *p; int j=0; p = L; //循环找到第i-1个结点 while (p!=NULL && j<i-1){ p=p->next; j++; } if (p==NULL)//i值不合法(超出了) return false; LNode *s=(LNode*)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return true; }
不带头结点
对第一个结点进行处理
指定节点后插操作
bool InsertNextNode(LNode *p, ElemType e){
if (p==NULL)
return false;
LNode *s = (LNode*)molloc(sizeof(LNode));
if (s==NULL)
return false;
s->data=e;
s-next=p->next;
p->next=s;
return true;
}
指定结点的前插操作
bool InsertPriorNode (Lnode *p, ElemType e){
if (p==NULL)
return false;
LNode *s = (LNode*)malloc(sizeof(LNode));
if (s==NULL) //内存分配失败
return false;
s->next=p->next;
p->next=s; //新结点连到p之后
s->data=p->data; //将p中元素复制到s中
p->data=e; //p中元素覆盖为e
return true;
}
删除
按位序删除
bool ListDelete(LinkList &L, int i, ElemType &e){
if (i<1)
return false;
LNode *p;
int j=0;
p = L;
while (p!=NULL && j<i-1){
p=p->next;
j++;
}
if (p==NULL)
return false;
if (p->next==NULL)
return false;
LNode *q=p->next;
e=q->next;
p->next=q->next;
free(q);
return true;
}
指定结点删除
bool DeleteNode(LNode *p){
if (p==NULL)
return false;
LNode *q=p->next;
p->data=p->next->data;
p->next=q->next;
free(q);
return true;
}
代码不能删除最后一个结点(只能从前往后找)
查找
按位查找
LNode * GetElem(LinkList L, int i){
if (i<0)
return NULL;
LNode *p;
int j=0;
p = L;
while (p!=NULL && j<i){
p=p->next;
j++;
}
return p;
}
按值查找
LNode * LocateElem(LinkList L, ElemType e){
LNode *p = L->next;
while (p !=NULL && p->data != e)
p=p->next;
return p;
}
单链表的建立
初始化一个表
每次取一个数据元素,插入
尾插法
LinkList List_TailInsert(LinkList &L){
int x;
L=(LinkList)malloc(sizeof(LNode)); //建立头结点
LNode *s, *r=L; //r是表尾指针
scanf("%d", &x);
while(x!=9999){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s; //r指向新的表尾
scanf("%d", &x);
}
r->next=NULL; //r指针置空
return L;
}
头插法
LinkList List_HeadInsert(LinkList &L){
LNode *s;
int x;
L=(LinkList)malloc(sizeof(LNode)); //建立头结点
L->next=NULL; //!初始为空
scanf("%d", &x);
while(x!=9999){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
s->next=L->next;
L->next=s; //插入新结点
scanf("%d", &x);
}
return L;
}
主要应用于链表的逆置
双链表
初始化
typedef struct DNode{
ElemType data;
struct DNode *prior, *next;
}DNode, *DLinkList;
bool InitDLinkList(DLinkList &L){
L = (DNode *)malloc(sizeof(DNode));
if (L==NULL)
return false;
L->prior = NULL; //头结点的prior永远指向NULL
L->next = NULL;
return true;
}
bool Empty(DLinkList L){
return (L->next==NULL);
}
插入
bool errInsertNextDNode(DNode *p, DNode *s){
s->next=p-next;
p->next->prior=s; //!err
s->prior=p;
p->next=s;
}
后插是需要判断p结点后是否有结点
bool InsertNextDNode(DNode *p, DNode *s){
if (p==NULL || s==NULL)
return false;
s->next=p-next;
if (p->next != NULL)
p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}
删除
bool DeleteNextDNode(DNode *p){
if (p==NULL)
return false;
DNode *q = p->next;
if (q==NULL)
return false;
p->next = q->next;
if (q->next != NULL)
q->next->prior=p;
free(q);
return true;
}
void DestroryList(DLinkList &L){
while (L->next != NULL)
DeleteNextDNode(L);
free(L);
L=NULL;
}
遍历
while (p!=NULL)//p->prior!=NULL 到头结点停止
p=p->next;
//p=p->prior;
循环链表
循环单链表
最后一个指针指向头结点
bool InitList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode));
if(L==NULL)
return false;
L->next = L;//指向自己
return true;
}
判断是否为空(是否是表尾)也是判断是否指向自己(指向头结点)
初始化时:头结点的next指针指向自己
给定一个结点,可以找到所有的结点(可以循环遍历)
对表头表尾的操作比较方便
循环双链表
头结点prior指向尾结点,尾结点next指向头结点
初始化L->prior=L;L->next=L;
同样许多对表头表尾的处理比较方便
静态链表
分配连续一整片空间,各个结点集中安置
优化内存分配
struct Node{
ElemType data;
int cur;
};
typedef struct {
ElemType data;
int cur;
} SLinkList[MaxSize];
//用SLinkList定义一个长度为MaxSize的Node型数组
空闲结点的处理
游标设为-1表示表尾
游标设为-2表示空闲结点
设置备用链表
比较
逻辑结构:线性结构
存储结构:顺序存储 VS 链式结构
基本操作:
- 顺序表:
- 静态分配——系统自动回收
- 动态分配——需要手动free(
malloc
放在堆区)
- 顺序表: