数据结构学习——线性表

2024-02-01 18:37:58

一、何为线性表

线性表，即为具有相同数据类型的n个数据元素的有限序列

相同数据类型：每个数据元素所占空间一样大
序列：有次序

tip:C++程序函数传入参数中引用“&”——>对参数的修改结果需要“带回来”，例：

void test1(int x) {
    x = 1024;
}

void test2(int & x) {
    x = 1024;
}

int main() {
    int x = 1;
    test1(x);  //x=1
    test2(x);  //x=1024
}

二、顺序表

1. 顺序表定义：用顺序存储的方式实现线性表，逻辑上相邻，物理位置上也相邻

C语言小知识：获取数据元素大小sizeof(ElemType)

eg:sizeof(int) = 4B

2. 顺序表的实现——静态分配

#define MaxSize 10               //定义最大长度
typedef struct{
    ElemType data[MaxSize];      //用静态的“数组存放数据元素”
    int length;                  //顺序表的当前长度
}SqList;                         //顺序表的类型定义

上述代码存储空间是静态的，顺序表的大小容量是不可以变的

3. 顺序表的实现——动态分配

#define InitSize 10             //顺序表的初始长度
typedef struct{
    ElemType *data;             //指示动态分配数组的指针
    int MaxSize;                //顺序表的最大容量
    int length;                 //顺序表的类型定义（动态分配方式）
} SeqList;

具体实现：

#include <stdlib.h>
#define InitSize 10          //默认的最大长度

typedef struct{
    int *data;               //指示动态分配数组的指针
    int MaxSize;             //顺序表的最大容量
    int length;              //顺序表的当前长度
} SeqList;

void InitList(SeqList &L) {
    //用malloc函数动态申请一片连续的存储空间
    L.data = (int *)malloc(InitSize*sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

//增加动态数组的长度
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);
}

4. 顺序表的特点

随机访问：可以在O(1)的时间内找到第i个元素
存储密度高
拓展容量不方便
插入、删除数据元素不方便

5. 顺序表的按位查找

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

时间复杂度：O(1)

6. 顺序表的按值查找

typedef struct{
    int *data;
    int MaxSize;
    int length;
}SeqList;

int LocateElem(SeqList L,int e){
    for(int i=0; i<L.length; i++){
        if(L.data[i]==e)
            return i+1;
    }
    return 0;
}

时间复杂度：

①最好情况：目标元素在表头，O(1)

②最坏情况：目标元素在表尾，O(n)

③平均情况：假设目标元素出现在任何一个位置的概率相同，都是1/n，平均循环次数=1*(1/n)+2*(1/n)+...+n*(1/n)=(n+1)/2，O(n)

三、单链表

1. 单链表每个结点处理存放数据元素外，还要存储指向下一个节点的指针

//typedef的作用：数据类型重命名
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

tip: 使用LinkList，强调这是一个单链表；使用LNode，强调这是一个结点

2. 不带头结点的单链表

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

//初始化一个空的单链表
bool InitList(LinkList &L) {
    L = NULL;         //空表，暂时还没有如何结点，防止脏数据
    return true;
}

void test() {
    LinkList L;       //声明一个指向单链表的指针
    //初始化一个空表
    InitList(L);
    //后续代码
}

3. 带头结点的单链表

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;
}

void test() {
    LinkList L;       //声明一个指向单链表的指针
    //初始化一个空表
    InitList(L);
    //后续代码
}

4. 按位序插入（带头结点）

头结点可以看作第0个结点

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

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1) return false;
    LNode *p;       //指针p指向当前扫描到的结点
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存数据）
    while (p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL) return false;    //i值不合法
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

平均时间复杂度：O(n)

5. 指定结点的后插操作

//后插操作：在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->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

6. 指定结点的前插操作

//前插操作：在p结点之前插入元素e
//思路：先在p结点后插入元素e，交换e与p的值
bool InsertPriorNode(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;
    s->data = p->data;
    p->data = e;
    return true;
}

7. 按位序删除（带头结点）

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

//在第i个位置删除元素e（带头结点）
bool ListDelete(LinkList &L, int i, ElemType &e){
    if(i<1) return false;
    LNode *p;       //指针p指向当前扫描到的结点
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存数据）
    while (p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL) return false;    //i值不合法
    if(p->next==NULL) return false;    //第i-1个结点之后已无其他结点
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q)
    return true;
}

时间复杂度：O(n)

8. 指定结点的删除

//删除指定结点p
bool DeleteNode(LNode *p){
    if(p==NULL) return false;
    p->data = p->next->data;
    LNode q = p->next;
    p->next = q->next;
    free(q);
    return true;
}

9. 单链表的按位查找

//按位查找，返回第i个元素（带头结点）
LNode * GetElem(LinkList L, int i){
    if(i<0) return NULL;
    int j = 0;
    LNode *p;
    p = L;
    while(p!=NULL&&j<i){
        p = p->next;
        j++;
    }
    return p;
}

10. 单链表的建立（尾插法）

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

11. 单链表的建立（头插法）

LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    L=(LinkList) malloc(sizeof(LNode));    //创建头结点
    L->next = NULL;
    int x;
    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;
}

应用：逆置单链表

四、双链表

1. 双链表的初始化（带头结点）

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;
    L->next = NULL;
    return true;
}

2. 双链表的插入

//在p结点之后插入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;
    return true;
}

五、循环链表

1. 初始化循环单链表

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 = L;            //头结点next指向头结点
    return true;
}

2. 初始化循环双链表

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

bool InitList(DLinkList &L) {
    L = (DNode *)malloc(sizeof(DNode));
    if(L==NULL) return false;
    L->prior=L;
    L->next = L;            //头结点next指向头结点
    return true;
}

六、静态链表

1. 静态链表与单链表对比

单链表：各个结点在内存中不连续存储

静态链表：分配一整片连续的内存空间，各个结点集中安置

2. 创建静态链表

#define MaxSize 10
struct Node{
    ElemType data;
    int next;
};

void testSLinkList() {
    struct Node a[MaxSize];
}

3. 静态链表插入元素

步骤：

①找到一个空的结点，存入数据元素；

②从头结点出发找到位序为i-1的结点；

③修改新节点的next;

④修改i-1号结点的next。

七、线性表与链表的对比

优点

缺点

创建

销毁

增删

查找

顺序表

支持随机存取、存储密度高

大片连续空间分配不方便，改变容量不方便

需要预分配大片连续空间。分配过小，不便于拓展容量；分配过大，浪费内存资源

静态分配：静态数组(系统自动回收空间)

动态分配：动态数组（malloc,free）

增/删元素需要将后续元素后移/前移（时间复杂度为O(n)，时间开销主要为移动元素）

按位查找：O(1)

按值查找：O(n)，若顺序表有序，则可在O(log2n)时间内找到

链表

离散的小空间分配方便，改变容量方便

不可随机存取，存储密度低

只需要分配一个头结点（也可以不要头结点，只声明头指针），之后方便拓展

依次删除各个结点（free）

增/删元素只需要修改指针（时间复杂度为O(n)，时间开销主要为查找目标元素，相比之下链表效率更高，因为如果数据元素很大，则顺序表移动的时间代价跟高）

按位查找：O(n)

按值查找：O(n)

码农公寓