顺序表

顺序线性表是指用一组地址连续的存储单元一次存储数据元素的线性结构。

#define MAX_SIZE 1000
typedef struct {
    int data[MAX_SIZE];  // 存储元素的数组
    int length;  // 长度
}SqList;

引用类型做参数传地址

void main(){
    int i = 1;
    int &j = i;
    i = 2;
    cont<<"i="<<i<<"j="<<j;  // i=2 j=2
}

事例中j是i的引用，代表i的一个替代名，i值改变时j也跟着改变

#include <iostream>
using namespace std;
void swap(int &m, int &n){
    int temp = m;
    m = n;
    n = temp;
}
void main(){
	int a = 1,b = 2;
    swap(a,b);
    cout<<a<<endl<<b<<endl; // 2 1
}

与传递指针的效果一样
引用类型做形参，在内存中并没有产生实参的副本，直接对实参进行操作，因此使用引用传递参数的时间空间效率都很好

主要操作的实现

Insert

// e为要插入的值，n为要插入的位置
void Insert(SqList &L, int e, int n) {
    if (n < 0 || n > L.length) {
        return;
    } else {
        for (int i=L.length-1; i>=n; i--) {
            L.data[i+1] = L.data[i];  // 插入位置及之后的元素右移
        }
        L.data[n] = e;  // 将新元素e放入第i个位置
    }
    L.length++;
}

Delete

// n为删除的序列号
void Delete(SqList &L, int n) {
    if (n < 0 || n >= L.length) {
        return;
    }
    for (int i=n; i<L.length-1;i++) {
        L.data[i] = L.data[i+1];
    }
    L.length--;
}

总结

优点

存储密度大
可以随机存取表中任一元素

缺点

在插入、删除时需要移动大量元素
浪费存储空间
属于静态存储形式，数据元素的个数不能自由扩充

链表

链表用一组物理位置任意的存储单元来存放线性表，链表中逻辑次序与物理次序不一定相同。

概念

链表由若干个结点构成，每一个结点包括数据域与指针域，数据域存储数据本身，指针域存储下一个元素的地址，用来表示逻辑次序。只要记录第一个元素的指针(头指针)即可找到其他元素的存储位置

单链表：结点只有一个指针域的链表
双链表：结点有两个指针域的链表，一个存储前驱的地址，一个存储后继的地址
循环链表：首尾相接的链表为循环链表

头结点与首元结点

头结点是在链表的首元结点之前附设的一个结点
首元结点为存储第一个元素的结点

typedef struct Lnode {
    int data;
    Lnode *next;
}Lnode, *LinkList;  // LinkList为指针类型的结构体的别名

定义链表L通常用LinkList L;，定义结点通常用Lnode *p;

对链表的操作

Init

链表初始化

void Init(LinkList &L) {
    L = new Lnode;  // 从内存中分配一个节点空间，用头指针L指向这个节点
    L->data = 0;  // 头结点的data用来存放链表的长度
    L->next = NULL;
}

Destory

销毁链表

void Destroy(LinkList &L) {
    while (L) {
        LinkList p = L;
        L = L->next;
        delete p;
    }
}

GetData

获取第n位的数据

int GetData(LinkList &L, int n) {
    Lnode *p = L;
    for (int i=0;i<n;i++) {
        p = p->next;
    }
    return p->data;
}

Search

查找链表中数据为e的结点的位置并返回

int Search(LinkList &L, int e) {
    Lnode *p = L->next;
    for (int i=1; i<=L->data; i++) {
        if (p->data == e) {
            return i;
        }
        p = p->next;
    }
    return 0;
}

Insert

在链表的第n位插入新元素e

void Insert(LinkList &L, int n, int e) {
    if (n < 1 || n > L->data + 1) {
        return;
    }
    Lnode *p = L;  
    Lnode *newdata = new Lnode;
    newdata->data = e;
    for (int i=1;i<n;i++) {
        p = p->next;  // 用p来指向第n-1位的元素
    }
    Lnode *q = p->next;  // 用q指向原来第n位的元素
    p->next = newdata;  // 使第n-1位元素的后继为newdata
    newdata->next = q;  // 使原来第n位元素的前驱为newdata
    L->data++;
}

Delete

删除链表第n位的数据

void Delete(LinkList &L, int n) {
    if (n < 1 || n > L->data) {
        return;
    }
    Lnode *p = L;
    for (int i=1;i<n;i++) {
        p = p->next;  // 使p指向第n-1位的元素
    }
    Lnode *q = p->next;  // 使p指向第n位的元素
    p->next = q->next;  // 使原来第n+1位的元素成为第n-1位的后继
    delete q;  // 释放内存
    L->data--;
}

头插法建立单链表

将新建的结点接在头结点的后面

void Create(LinkList &L, int n) {
    L = new Lnode;
    L->data = n;
    L->next = NULL;
    for (int i = 0; i < n; i++) {
        Lnode *p = new Lnode;  // 生成新节点
        cin >> p->data;  // 输入元素值,等于scanf("%d", &p->data);
        p->next = L->next;  // 插入到表头
        L->next = p;  // 插入到表头
    }
}

尾插法建立单链表

将新建的结点插在尾指针后

void Create(LinkList &L, int n) {
    L = new Lnode;
    L->data = n;
    L->next = NULL;
    Lnode *r = L;  // 创建尾指针
    for (int i = 0; i < n; i++) {
        Lnode *p = new Lnode;  // 生成新结点
        cin >> p->data;
        r->next = p;  // 插入到尾指针后
        r = p;  // 更新尾指针
    }
}

循环链表

链表中最后一个结点的next指向头结点，由于表的操作通常是在首尾位置上执行，若用头指针表示单循环链表，查找最后一位元素时需要遍历整个链表，较为麻烦，但如果使用尾指针表示单循环链表，第一位元素可表示为R->next->next，最后一位为R，更为方便

循环链表的合并

LinkList Hebing(LinkList &R1, LinkList &R2) {
    Lnode *L1 = R1->next;  // R1的头指针
    Lnode *L2 = R2->next;  // R2的头指针
    R1->next = L2->next;  // 连接R1的尾指针与R2的首元结点
    R2->next = L1;  // 连接R2的尾指针与R1的头结点
    delete L2;  // 释放R2头结点内存
    return R2;
}

双向链表

双链表结点结构为

typedef struct Lnode {
    int data;
    Lnode *prior;
    Lnode *next;
}Lnode, *LinkList;

Insert

双链表的插入操作，在第n位插入数据为e的结点

void Insert(LinkList &L, int n, int e) {
    if (n < 1 || n > L->data + 1) {
        return;
    }
    Lnode *p = L;
    Lnode *newdata = new Lnode;
    newdata->data = e;
    for (int i = 1; i < n; i++) {
        p = p->next;  // 找到第n-1位的节点
    }
    newdata->next = p->next;  // 新节点的next指向原来第n位的节点
    newdata->prior = p;  // 新节点的prior指向第n-1位的节点
    p->next = newdata;  // p的next指向新节点
    if (newdata->next) newdata->next->prior = newdata;  // 原来第n位的节点的prior指向新节点
    L->data++;
}

Delete

双链表的删除操作，删除第n位的结点

void Delete(LinkList &L, int n) {
    if (n < 1 || n > L->data) {
        return;
    }
    Lnode *p = L;
    for (int i=0;i<n;i++) {
        p = p->next;  // 找到第n位的节点
    }
    p->prior->next = p->next;  // 第n-1位的节点的next指向第n+1位的节点
    if (p->next) p->next->prior = p->prior;  // 第n+1位的节点的prior指向第n-1位的节点
    delete p;
    L->data--;
}