数据结构-线性表家族

By lx | Mar 8, 2023 | Category: 默认分类,一些学习 | 共 7423 个字符

基本特点：

具有相同的数据类型
有限序列，i表示位序，1是表头，n是表尾（数组下标从0开始）
n=0规定为空
除首尾项，有且仅有一个直接前驱和一个直接后继。首项没有前驱，末项没有后继
基本操作——创销增删检

顺序表 SqList

特点：顺序存储方式实现的线性表，即逻辑结构和物理结构都相邻。

实现方式

静态分配根据数据类型分配内存空间，以及顺序表长度。然后进行初始化，设置默认值。

注：尽量使用基本操作访问数据，获取准确的数据信息，防止脏数据的干扰。

#define MaxSize 10
typedef struct{
      Elemtype data[MaxSize];
      int length;
}SqList;

动态分配

 #include <stdlib.h>
 #define InteSize 10
 typedef struct{
     int *date;
     int MaxSize;
     int lenth;
 }SeqList;
 void InitList(SeqList &L){
     L.date=(int*)malloc(InitSize*sizeof(int))//动态分配内存
 }

特点：

随机访问
密度高
拓展容量不方便
插入，删除数据元素不方便

基本操作

初始化

InitList(L);

插入

ListIntert(&L,i,e);

bool ListInsert(Sqlist &L,int i,int e){//i-插入元素 e-插入位置
    if(i<1||i>L.lenth+1)//判断长度是否有效
        return  false;
    if(L.lenth>=MaxSize)//判断储存空间是否充足
        return  false;
    for(int j=L.lenth;j>=i;j--)//i之后的元素后移
        L.date[j]=L.date[j-1];
     L.date[j-1]=e;//i处放入e
     L.length++;//长度+1
     return ture;
}

时间复杂度问题规模n=L.lenth i=(1,L.lenth+1) T(n)=(o(1),o(n)) E(T)=o(n/2)=o(n)

删除

ListDelete(&L,i,&e)

bool ListDelete(SqList &L,int i,int &e){//i-插入元素 e-插入位置
 if(i<1||i>L.lenth+1)//判断长度是否有效
      return 0;
 e=L.data[i-1];
 for(int j=i;j<L.length;j++)//i之后的元素前移
      L.date[j-1]=L.date[j];
 L.length--;
 return 1;
 }

时间复杂度问题规模n=L.lenth i=(n，1) T(n)=(o(1),o(n)) E(T)=o((n-1)/2)=o(n)

查找

GetElem(L,i)按位查找

int GetElem(SqList L,int i){
    return L.data[i-1];
}

注意：动态分配按位查找时，根据指针的数据类型长度取数据
时间复杂度:o(1)
LocalElem(L.e)按值查找

int LocalElem(SqListL,ElemType e){
for(int i=0;i<L.length;i++)
    if(L.data[i]==e)
        return i+1;//下标是i，返回位序是i+1
    return 0;
}

注意：C中结构体不可以直接用"=="，通过函数比较结构体成员定义"=="
时间复杂度：问题规模n=L.lenth i=(1，n) T(n)=(o(1),o(n)) E(T)=o((n+1)/2)=o(n)

链表-单链表

定义

typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkLsit;

初始化

不带头节点

bool InitLink(LinkLsit &L){
L=NULL;//空表，防止脏数据
return true;
}

void test(){
    LinkList L;
    InitLink(L);
}

bool Empty(LinkLsit L){
    if(L==Null)
        return true;
    else
        return false;
}//return (L==NULL);

带头结点

bool InitLink(LinkList &L) {
L = (LNode *) malloc(sizeof(LNode));
if (L == NULL)
    return false;
L->next = NULL;
return true;
}//带头结点

插入

按位序插入
ListInsert(&L,i,e)

带头节点

bool ListInsert(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;
 LNode *s=(LNode*)malloc(sizeof(LNode));
 s->data=e;
 s->next=p->next;
 p->next=s;
 return true;
 }

时间复杂度：问题规模n=L.lenth i=(1，n) T(n)=(o(1),o(n)) E(T)=o(n)

不带头节点

需要多考虑第一个结点的前面插入即可

if(i==1){
    LNode *s=(LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=L;
    L=s;
    return true;
 }

指定节点的后插操作(可用于替换前面的插入操作）
InsertNextNode(p,e);

bool InsertNextNode(LNode *p,ElemType e){
if(p==NULL)
    return false;
LNode *s = (LNode *)malloc(sizeof (LNode));
if(s==NULL)
    return false;
s->date=e;
s->next=p->next;
p->next=s;
return true;
}

指定结点的前插操作
bool InsertPrior(LNode *p,ElemType e)
没有头节点就通过后插，然后交换前后结点，实现前插操作 T(n)=o(n)
有头节点就往后循环直到找到结点再插入 T(n)=o(1)

删除

ListDelete(LinkList &L,int i,ElemType &e)
按位序删除

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->data;
p->next=q->next;
free(q);
return true;
}

DeleteNode(LNode *p)
指定结点删除

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<1){
    p=p->next;
    j++;
}
return p;

}
平均时间复杂度：o(n)
封装代码：避免重复代码，简洁易维护。

按值查找
LocateElem(LinkList L,ElemType e)

LNode *LocateElem(LinkList L, int e){
LNode  *p=L->next;
while (p!=NULL&& p->data!=e)
    p=p->next;
return p;

}

求表长
Length(LinkList L)

int Length(InitLink L){
int len=0;
LNode *p=L;
while(p->next!=NULL){
    p=p->next;
    len|++;
}
return len

}

建立

尾插法——对表尾进行后插操作

LinkList List_TailInsert(LinkList &L){
int x;
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){
LNode *s;
int x;
L=(LNode*)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;
}

双链表 Double Linked List

typedef struct DNode{
ElemType date;
struct DNode *prior,*next;
}DNode, *DLinklist;

初始化

bool InitDLinklist(DLinklist &L){
L=(DNode*)malloc(sizeof(DNode));
if(L==NULL)
    return false;
L->prior=NULL;
L->next=NULL;
return true;
}

插入

后插——InsertNextDNod(DNode p,DNode s)

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;
}//*s插到*p之后

按位序插入——扫描到p，实现后插

前插——实现后插然后交换

删除——后删一位

查找——依次扫描

循环链表 circular Linked List

循环单链表

一个结点可以找到所有的结点

初始化

bool InitList(InitDLinklist &L){
L=(LNode*)malloc(sizeof(LNode));
if(L==NULL)
    return false;
L->next=L;
return true;
}

判断是否为空

bool Empty(LinkList L){
if(L->next == L)
    return true;
else
    return false;
}

头找尾只需要o(n)，尾找头只需要o(1)

循环双链表

操作大部分和双链表类似，对于尾结点的处理不容易出现空指针现象。

静态链表

#define MaxSize 10
typedef struct {
ElemType  data;
int next;
}SLinkList[MaxSize];//直接表示静态链表

等价于

struct Node {
ElemType  data;
int next;
};
typedef struct Node SLinkList[MaxSize];

初始化
a[0]->next=-1;
查找从头结点挨个往后遍历
插入i 找一个空结点从头找到i-1 修改新的next 修改i-1的next
0号结点充当头节点-1表示表尾游标充当指针用一个特殊的数值标记空闲结点
容量固定不变（FAT）

总结：
链表的扩容性和增加删除都更方便顺序表查找方便
对比的时候，从逻辑结构到储存结构最后是基本操作答题，分析各自优劣