线性表基本操作
2021-08-06
7分钟阅读时长
线性表的基本操作如下：
void InitList(&L);//初始化表，构造一个空的线性表
int Length(L);//求表长
ElemType LocateElem(L,e);//按值查找
ElemType GetElem(L,e);//按位查找
bool ListInsert(&L,i,e);//插入操作
bool ListDelete(&L,i,&e);//删除操作
void PrintList(L);//输出操作
bool Empty(L);//判空操作
bool DestroyList(&L);//销毁操作
顺序表
定义
静态分配
static const int MaxSize=50;
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];//定义即开辟了存储空间
int length;
}SqList;
动态分配
static const int MaxSize=50;
typedef int ElemType;
typedef struct{
ElemType *data;
int MaxSize,length;//此处需要声明最大存储空间
}SqList;
初始化
静态分配
void InitList(SqList &L){
for(int i=0;i<MaxSize;i++)
L.data[i]=0;
L.length=0;
}
动态分配
void InitList(SqList &L){
//以下两种初始化内存空间方式分别对应C与C++
L.data=(ElemType*)malloc(sizeof(ElemType)*MaxSize);
L.data=new ElemType[InitSize];
for(int i=0;i<MaxSize;i++)
L.data[i]=0;
L.length=0;
}
插入
其中i是位序。
bool ListInsert(SqList &L,int i,ElemType e){
if(i<1||i>L.length+1)
return false;
if(L.length==MaxSize){//可以直接返回错误，理由是存储空间已满；或分配内存空间
MaxSize++;
ElemType *new;
new=(ElemType*)realloc(L.data,sizeof(ElemType)*(MaxSize+1));
if(!new) return false;//申请空间失败
L.data=new;
}
if(L.length>MaxSize) return false;
for(int j=L.length;j>=i;j--)
//位序从最后1位一直到第i个，插入向右移，因此最后需要额外的j=L.length，共L.length-i+1位
L.data[j]=L.data[j-1];
L.data[i-1]=e;
L.length++;
return true;
}
删除
bool ListDelete(SqList &L,int i,ElemType e){
if(i<1||i>L.length+1)
return false;
e=L.data[i-1];
for(int j=i;j<L.length;j++)
//位序从第i+1个到最后1位，删除向左移，因此不需要最后一个j=L.length，共L.length-i个
L.data[j-1]=L.data[j];
L.length--;
return true;
}
查找
按值查找
ElemType LocateElem(SqList L,ElemType e){
int i;
for(i=0;i<L.length;i++)
if(L.data[i]==e)
return i+1;
return 0;
}
按位查找
ElemType LocateElem(SqList L,int i){
if(i<1||i>L.length)
return NULL;
return L.data[i-1];
}
单链表
如无特殊说明，均指带头结点的单链表。
定义
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
初始化
不带头结点
bool InitList(LinkList &L){
L=NULL;//防止内存中的脏数据进入单链表
return true;
}
带头结点
bool InitList(LinkList &L){
L=(LNode*)malloc(sizeof(LNode));
if(L==NULL) return false;
L->next=NULL;
return true;
}
判空
bool Empty(LinkList L){
return (L==NULL);//不带头结点
return (L->next==NULL);//带头结点
}
查找
按位查找
带头结点的按位查找如下
LNode *GetElem(LinkList L,int i){
int j=0;//从0开始查找
LNode *p=L;
/*或改写成
int j=1;
LNode *p=L->next;
*/
if(i==0) return L;
if(i<1) return NULL;
while(p&&j<i){
p=p->next;
j++;
}
return p;//返回第i个结点的指针，若大于表长，返回的则是NULL
}
按值查找
LNode *LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while(p!=NULL&&p->data!=e)
p=p->next;
return p;//要么返回指针，要么返回NULL
}
插入
给定结点插入
对于给定的结点，向其前后插入。
向后插入
bool ListInsertNextNode(LNode *p,ElemType e){
if(p==NULL) return false;//待插入结点不合法
LNode *s=(LNode*)malloc(sizeof(LNode));
if(s==NULL) return false;//无法新插入结点
s->data=e;
s->next=p->next;
p->next=s;//注意上述三语句的顺序，此句和前句顺序不能颠倒
return true;
}
向前插入
方法有两种，一是传入头指针，找到第i-1个结点；二是转换为后插操作，即向后插入操作后将前驱结点p与插入结点s交换数据域。
如果给定的是待插入的值，则
bool ListInsertPriorNode(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;
s->data=p->data;
p->data=e;
return true;
}
如果给定的是待插入的结点，则
bool ListInsertPriorNode(LNode *p,LNode *s){
if(p==NULL) return false;//待插入结点不合法
LNode *s=(LNode*)malloc(sizeof(LNode));
if(s==NULL) return false;//无法新插入结点
s->next=p->next;
p->next=s;
ElemType temp;
temp=p->data;
p->data=s->data;
s->data=temp;
return true;
}
给定位序插入
对于给定的位序，向其前后插入如下。
向后按位序插入
带头结点
bool ListInsertNext(LinkList &L,int i,ElemType e){
p=GetElem(L,i);
return ListInsertNextNode(p,e);
}
不带头结点
bool ListInsertNext(LinkList &L,int i,ElemType e){
p=GetElem(L,i);
if(i!=1) return ListInsertNextNode(p,e);
if(i==1){
LNode *s=(LNode*)malloc(sizeof(LNode));
s->data=e;
s->next=L;
L=s;//注意体会此处的书写
return true;
}
}
向前按位序插入
bool ListInsertPrior(LinkList &L,int i,ElemType e){
p=GetElem(L,i);
return ListInsertPriorNode(p,e);
}
建表
尾插法
LinkList List_TailInsert(LinkList &L){
int x;
L=(LinkList)malloc(sizeof(LNode));
LNode *s,*r=L;//r是表尾指针
scanf("%d",&x);
while(x!=9999){//输入9999表示结束
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;
scanf("%d",&x);
}
r->next=NULL;
return L;
}
头插法
带头结点
LinkList List_HeadInsert(LinkList &L){
int x;
L=(LinkList)malloc(sizeof(LNode));
LNode *s;
L->next=NULL;//不带头结点则 L=NULL;
scanf("%d",&x);
while(x!=9999){//输入9999表示结束
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
s->next=L->next;//不带头结点则 s->next=L;
L->next=s;//不带头结点则 L=s;
scanf("%d",&x);
}
return L;
}
删除
按位序删除
bool ListDelete(LinkList &L,int i,ElemType &e){
LNode *p=GetElem(L,i-1);//寻找被删除结点的前驱结点
LNode *q=p->next;//q指向被删除的结点
p->next=q->next;
free(q);
}
按结点删除
删除某结点，方法有两种，一是传入头指针，找到第i-1个结点；二是该结点与其后继结点交换数据域。该方法不能删除最后一个结点。
bool ListDeleteNode(LNode *p){
if(p==NULL) return false;
LNode *q=p->next;
if(q==NULL) return false;//不能删除最后一个结点
p->data=p->next->data;//被删除结点和后继结点交换数据域
p->next=q->next;//断链
free(q);
return true;
}
求表长
求表长的思想类似于按位序查找结点。
int Length(LinkList L){
int len=0;
LNode *p=L;
/*不带头结点
if(L==NULL) return len;
*/
while(p->next!=NULL){
p=p->next;
len++;
}
return len;
}
双链表
定义
tyepdef struct DNode{
ElemType data;
struct DNode *next,*prior;
}DNode,*LinkList;
初始化
bool InitDLinkList(DLinkList &L){
L=(DNode *)malloc(sizeof(DNode));//分配头结点
if(L==NULL) return false;//内存不足
L->prior=NULL;
L->next=NULL;
return true;
判空
bool Empty(DLinkList &L){
if(L->next==NULL) return true;//头结点
else return false;
}
插入
向后插入
bool InsertNextDNode(DNode *p,DNode *s){
if(p==NULL||s==NULL) return false;
s->next=p->next;
if(p->next!=NULL)//如果p结点有后继结点
p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}
向前插入
bool InsertPriorDNode(DNode *p,DNode *s){
if(p==NULL||s==NULL) return false;
if(p->prior==NULL){
s->next=p;
p->prior=s;
}
p=p->prior;//找到p的前驱结点，然后向后插入
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}
删除
删除p结点的后继结点
bool DeleteNextNode(DNode *p){
if(p==NULL) return false;
DNode *q=p->next;
if(q==NULL) return false;//p没有后继结点
p->next=q->next;
q->next->prior=p;
free(q);
return true;
}
销毁
void DestroyList(DLinkList &L){
while(L->next!=NULL)
DeleteNextNode(L);
free(L);
L=NULL;//头指针指向NULL
}
遍历
正向遍历
void Travere(DNode *p){
while(p!=NULL)
p=p->next;
}
反向遍历
void TravereBack(DNode *p){
while(p->prior!=NULL)//略过头结点，仅处理数据结点
p=p->prior;
}
循环链表
循环单链表
循环单链表和单链表的区别在于表中最后一个结点的指针指向头结点L。
定义
循环单链表的定义与单链表的定义完全相同。
初始化
bool InitList(LinkList &L){
L=(LNode*)malloc(sizeof(LNode));
if(L==NULL)
return false;
L->next=L;//头结点next指向头结点
return true;
}
判空与判尾
思想：判断当前结点是否指向头结点L。
//判空
bool Empty(LinkList L){
if(L->next==L) return true;
else return false;
}
//判尾
bool isTail(LinkList L,LNode *p){
if(p->next==L) return true;
else return false;
}
循环双链表
循环双链表与循环单链表的区别在于其头结点的prior指针指向表尾结点。
定义
循环双链表的定义与双链表的定义完全相同。
初始化
bool InitDLinkList(DLinkList &L){
L=(DNode*)malloc(sizeof(DNode));
if(L==NULL) return false;
L->next=L;
L->prior=L;
return true;
}
判空与判尾
思想：判断当前结点是否指向头结点L，与循环单链表完全相同。
//判空
bool Empty(DLinkList L){
if(L->next==L) return true;
else return false;
}
//判尾
bool isTail(LinkList L,LNode *p){
if(p->next==L) return true;
else return false;
}
插入
插入部分基本同双链表，区别在于后继结点是否存在不需要额外判断。
向后插入
bool InsertNextDNode(DNode *p,DNode *s){
if(p==NULL||s==NULL) return false;
s->next=p->next;
//if(p->next!=NULL)//普通双链表需要判断p结点后是否有后继结点
p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}
向前插入
bool InsertPriorDNode(DNode *p,DNode *s){
if(p==NULL||s==NULL) return false;
if(p==L)//不能在头结点之前插入
return false;
p=p->prior;//找到p的前驱结点，然后向后插入
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}
删除
删除p结点的后继结点，基本同双链表，区别在于后继结点是否存在不需要额外判断。
bool DeleteNextNode(DNode *p){
if(p==NULL) return false;
DNode *q=p->next;
//if(q==NULL) return false;//p一定有后继结点
p->next=q->next;
q->next->prior=p;
free(q);
return true;
}
静态链表
借助数组描述线性表的链式存储结构。
typedef struct{
ElemType data;
int next;//下一个元素的数组下标
}SLinkList[MaxSize],SNode;
SLinkList a;//等价于 struct SNode a[MaxSize];
游标next=-1表示到链表尾，next=-2表示该结点暂未使用。
顺序表和链表的比较
存取方式
存取方式又叫读写方式，顺序表可以顺序存取，也可以随机存取；链表只能顺序存取，因此有下面的结论：
线性表的顺序存储结构是一种随机存取的存储结构，线性表的链接存储结构是一种顺序存取的存储结构。
逻辑与物理结构
顺序存储：逻辑上相邻的元素物理上也相邻。
链式存储：逻辑上相邻的元素物理上不一定相邻。
增删改查操作
查改
按值查找，顺序表无序时，顺序表与链表时间复杂度均为O(n)，顺序表有序时顺序表时间复杂度为O(logn)；
按位序查找，顺序表时间复杂度为O(1)，链表时间复杂度为O(n)；
增删
顺序表的插入、删除操作时间复杂度O(n)，主要来自于移动元素；
链表的插入、删除操作时间复杂度O(n)，主要来自于查找元素。
选择
如果存储结构需要具有弹性、可扩容，选择链表；
如果存储结构需要具有频繁的增删操作，选择链表；
如果存储结构需要具有频繁的查找操作，选择顺序表；
如果存储结构需要易于实现，选择顺序表。
