数据结构与算法的代码实现（C++版）

1. 线性表的顺序表示和实现

1.1 线性表的初始化

// 线性表的定义
// 其实就是构造结构体：数组+长度
struct SqList
{ElemType* elem;  //顺序线性表的表头// 也可以这样定义，但是是数组静态分配，上述是动态的，因为可以使用指针指向数组首地址//ElemType elem[MAX_SIZE];  int length;      //顺序线性表的长度
};
// 线性表的初始化
bool InitList(SqList& L)
{L.elem = new ElemType[MAXSIZE];  // //在堆区开辟内存if (!L.elem){return false;}L.length = 0;  //设定空表长度为0return 1;
}

1.2 线性表的销毁

// 线性表的销毁
void DestroyList(SqList& L)
{if (L.elem){delete L.elem;}
}

1.3 线性表的清空

// 线性表的清空
void CLearList(SqList& L)
{L.length = 0;
}

1.4 线性表的长度

// 线性表的长度
int GetLength(SqList& L)
{return L.length;
}

1.5 判断线性表是否为空

// 判断线性表是否为空
bool IsEmpty(const SqList& L)
{// static_cast<bool>(L.length) 的作用是将 L.length 的值转换为布尔值 (bool)。return static_cast<bool>(L.length);
}

1.6 线性表的线性表取值

// 线性表取值
// 随机存取的时间复杂度是：O(1)
bool GetELem(const SqList &L, const size_t i, ElemType &e)
{if (i < 1 || i > MAXSIZE){cerr<<"out of range"<<endl;return false;}e = L.elem[i-1];return true;
}

1.7 线性表的顺序查找

// 线性表的查找
// 顺序查找的时间复杂度是：O(n)
int LocateList(const SqList& L, const ElemType& e)
{for (int i = 0; i < L.length; i++){if (L.elem[i] == e){return i + 1;  //查找成功，返回下标值}}return 0;  // 查找失败，返回0
}

1.8 线性表的插入

// 线性表的插入
// 顺序存储的插入的时间复杂度是：O(n)
bool InsertList(SqList& L, const ElemType& e, const int& i)
{if (i < 1 || i > L.length){return false;  // i值不合法}if (L.length == MAXSIZE){return false;  // 当前存储空间已满}// 将位于插入位置之后的元素依次向后挪动一位for (int j = L.length - 1; j >= i - 1; j--){L.elem[j + 1] = L.elem[j];}// 插入元素L.elem[i - 1] = e;// 线性表长度+1L.length++;return true;
}

1.9 线性表的删除

// 线性表的删除
// 顺序存储的删除的时间复杂度是：O(n)
bool EraseList(SqList& L, const int& i)
{if (i < 1 || i > L.length){return false;  // i值不合法}// 从要删除的i位置开始遍历// 也就是将位于删除位置之后的元素依次向前移一位for (int j = i; j < L.length; j++){L.elem[j - 1] = L.elem[j];}// 线性表长度-1L.length--;return true;
}

总结

(1)利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致
(2）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等
这种存取元素的方法被称为随机存取法
时间复杂度
1.查找、插入、删除算法的平均时间复杂度为O(n)
就是求次数，比如查找，就是在第几个位置需要的查找次数的累加和 / 元素个数。
比如插入，就是在第几个位置插入需要移动元素个数的累加和 / n种可能。
比如删除，就是在第几个位置删除需要移动元素个数的累加和 / n种可能。
空间复杂度
2.显然，顺序表操作算法的空间复杂度S(n)=O(1) (没有占用辅助空间)
优点：
1.存储密度大(结点本身所占存储量 / 结点结构所占存储量，是1：1)
2.可以随机存取表中任一元素
缺点：
1.在插入、删除某一元素时，需要移动大量元素
2.浪费存储空间
3.属于静态存储形式，数据元素的个数能自由扩充

2. 线性表的链式表示和实现

2.1 单链表

2.1.1 单链表的初始化（带头结点的单链表）

// 单向链表的定义
struct Lnode
{ElemType data;  //结点的数据域 Lnode* next;    //结点的指针域, 因为指针还是指向下一结点，结点类型就是Lnode
};
// typedef 都是常用来创建类型别名的工具。
// 将 Lnode * 这个指针类型定义为 LinkList，使得代码更简洁易读。
typedef Lnode* LinkList;  // 链表的初始化
bool InitList(LinkList& L)
{// LinkList& L = Lnode* L，L其实是Lnode类型的指针// 表示头指针L = new Lnode;  // 在堆区开辟一个头结点，结点的数据类型为Lnode//L->next = NULL;  // 空表，也就是说头结点的指针指向为空L->next = nullptr;  // // 使用 C++11 的 nullptr，类型安全return 1;
}

2.1.2 判断单链表为空

// 判断链表是否为空
bool IsEmpty(const LinkList& L)
{if (L->next){// 非空return false;}else{// 为空return true;}
}

2.1.3 单链表的销毁

// 单链表的销毁
void DestroyList(LinkList& L)
{LinkList p;while (L){// 就是定义1个指针p指向头结点，然后将头指针指向下一个结点，并删除当前p指向的结点p = L;L = L->next;delete p;}
}

2.1.4 单链表的清空

// 单链表的清空
void CLearList(LinkList& L)
{LinkList p, q;p = L->next;while (p)  // p非空，表示还没到表尾{q = p->next;delete p;p = q;}L->next = nullptr;  // 头结点指针域为空
}

2.1.5 单链表的表长

// 单链表的长度
int GetLength(LinkList& L)
{LinkList p;p = L->next;  // 将p指向首元结点 int i = 0;  // 计数while (p){// 遍历单链表,统计结点数i++;p = p->next;}return i;
}

2.1.6 单链表的取值

// 单链表的取值
bool GetElem(const LinkList& L, const int& i, const ElemType& e)
{LinkList p = L->next; int j = 1; // 计数器while (p && i > j){p = p->next;j++;}if (!p || j > i) return false; // 第i个元素不存在e = p->data;return true;
}

2.1.7 单链表的按值查找

// 单链表的按值查找，返回L中值为e的数据元素的地址
// 时间复杂度：0(n)
LinkList LocateElem(LinkList& L, ElemType& e)
{// 在线性表L中查找值为e的数据元素// 找到，则返回L中值为e的数据元素的地址，查找失败返回NULLLinkList p = L->next;while (p && p->data != e){p = p->next;}return p;
}// 单链表的按值查找，返回L中值为e的位置序号
int LocateElem(LinkList& L, ElemType& e)
{// 返回L中值为e的数据元素的位置序号，查找失败返回LinkList p = L->next;int j = 1;while (p && p->data != e){p = p->next;j++;}if (p){return j;}else{return 0;}
}

2.1.8 单链表的插入

// 单链表的插入
// 时间复杂度：0(1)
bool InsertList(LinkList& L, const int& i, const ElemType& e)
{LinkList p = L;int j = 0;while (p && j < i -1)  // 寻找第i - 1个结点, p指向i - 1结点{p = p->next;j++;}if (!p || j > i - 1){return 0;  // i大于表长+1或者小于1，插入位置非法}// 生成新结点s，将结点s的数据域置为eLinkList s = new Lnode;s->data = e;// 将结点s插入L中s->next = p->next;p->next = s;
}

2.1.9 单链表的删除第i个结点

// 单链表的删除
// 将单链表L中第i个数据元素删除
// 时间复杂度：0(1)
bool EraseList(LinkList& L, const int& i, const ElemType& e)
{LinkList p = L, q;int j = 0;while (p && j < i - 1)  // 寻找第 i 个结点的前驱{p = p->next;j++;}if (!(p->next) || j > i - 1){return 0;  // 删除位置不合理}q = p->next;  // 临时保存被删结点的地址以备释放p->next = q->next; // 改变删除结点前驱结点的指针域e = q->data;delete q;return true;
}

2.1.10 单链表的头插法

头插法是倒序插入，先插入An，再是An-1，直到A1；而尾插法是正序，先插A1，再一直到An。

// 单链表的头插
// n表示结点个数
// 算法时间复杂度：O(n)
void CreatListHead(LinkList& L, int n)
{L = new Lnode;L->next = nullptr;  // 先建立一个带头结点的单链表for (int i = 0; i < n; i++){LinkList p = new Lnode;cin >> p->data; // 输入元素值p->next = L->next;  // 插入到表头L->next = p;}
}

2.1.11 单链表的尾插法

// 单链表的尾插
// 算法时间复杂度：O(n)
void CreatListTail(LinkList& L, int n)
{L = new Lnode;L->next = nullptr;LinkList r = L;  // 尾指针r指向头结点for (int i = 0; i < n; i++){LinkList p = new Lnode;cin >> p->data;  // 生成新结点，输入元素值p->next = nullptr;r->next = p; // 插入到表尾r = p; // r指向新的尾结点}
}

总结

2.2 循环链表

2.2.1 循环链表的合并

 // 两个链表的合并// 算法时间复杂度：O(1)
LinkList ConnectList(LinkList& Ta, LinkList& Tb)
{// 假设Ta、Tb都是非空的单循环链表LinkList p = Ta->next;  // ①p存表头结点Ta->next = Tb->next->next;  // ②Tb表头连结Ta表尾delete Tb->next;  // ③释放Tb表头结点Tb->next = p;  // ④修改指针return Tb;
}

总结

1.单链表使用头指针，比较方便；而单循环链表中，使用尾指针，比较方便。
2.单链表必须通过头指针逐个遍历访问每个结点，而单循环链表可以通过任意一个结点出发。

2.3 双向链表

2.3.1 双向链表的插入

// 双向链表的定义
// 首先定义了一个结构体 DuLnode，然后通过 typedef 定义了一个指向该结构体的指针类型 DuLinkList。
// 这里 typedef 的部分只定义了 DuLnode* 的别名 DuLinkList，而 DuLnode 是单独的结构体定义。
typedef struct DuLnode
{ElemType data;  //结点的数据域 DuLnode* prior, * next;    
}*DuLinkList;// 双向链表的初始化
void InitList(DuLinkList& L)
{L = new DuLnode;  L->prior = nullptr;  L->next = nullptr;  
}// 双向链表的第i个位置插入元素
bool InsertList(DuLinkList& L, const int& i, const ElemType& e)
{// 在带头结点的双向循环链表L中第i个位置之前插入元素eDuLinkList p = L->next;int j = 1;while (p->next && j < i)  // 移动指针到i处{p = p->next;j++;}if (j < i || j < 1){return 0;  // i大于表长插入位置非法}//在堆区创建要插入的结点DuLinkList s = new DuLnode;s->data = e;// 重新建立链接关系, 将结点s插入链表中s->prior = p->prior;  //第一步：s的前趋等于p的前趋p->prior->next = s;  //第二步，用p的前趋结点的next指向插入元素s，更改了第一条链s->next = p;        //第三步：s的后继指向pp->prior = s;       //第四步：p的前趋改为指向s，更改了第二条链return true;}

2.3.2 双向链表的删除

// 双向链表的删除某个元素
bool ListErase_DuL(DuLinkList& L, const int& i, const ElemType& e)
{DuLinkList p = L->next;int j = 1;while (p && j < i)  // 寻找第i个结点，并令p指向其前驱{p = p->next;j++;}if (j < i || j < 1){return 0;  // i大于表长插入位置非法}p->prior->next = p->next;p->next->prior = p->prior;delete p;return true;
}