线性表
静态分配的顺序表
如果数组存满则无法更改
头文件：
#pragma once
#include <iostream>
#include <stdio.h>
#define MaxSize 50
using namespace std;
//静态分配的顺序表大小无法更改
struct Sqlist {
int data[MaxSize]; //用静态的数组存放数据元素
int length; //顺序表的长度
}; //顺序表的类型定义
void InitSqList(Sqlist& L);
bool ListInsert(Sqlist& L, int i, int e);
bool ListDelete(Sqlist& L, int i, int& e);
int GetElem(Sqlist L, int i);
int LocateElem(Sqlist L, int i);
源文件：
#include<iostream>
#define MaxSize 50
#include<stdio.h>
using namespace std;
#include "SqList.h"
void InitSqList(Sqlist& L);
bool ListInsert(Sqlist& L, int i, int e);
bool ListDelete(Sqlist& L, int i, int& e);
int GetElem(Sqlist L, int i);
int LocateElem(Sqlist L, int i);
//初始化一个顺序表
//在静态分配时，一旦空间占满，再加入会益处
void InitSqList(Sqlist& L) {
for (int i = 0; i < MaxSize; i++) {
L.data[i] = 0; //顺序表初始长度为0
}
L.length = 0;
cout << "Finished Initiation" << endl;
}
//插入数据元素 在L的位序i处插入元素e
/*
时间复杂度
1）最好情况：表尾插入O（1）
2）最坏情况:表头插入O（n）
3）平均情况：插入到任意位置的概率为O（n）
*/
bool ListInsert(Sqlist& L, int i, int e) {
if (i<1 || i >L.length + 1) //判断i的范围是否有效
{
cout << "i 越界;i" << i << "Length：" << L.length << endl;
return false;
}
if (L.length >= MaxSize) //当前存储空间已满，不能插入
{
return false;
}
for (int j = L.length; j >= i; j--) //在队尾多加一个空的，第i个元素及之后的元素后移
{
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e; //在位置i处放入e
L.length++; //长度加1
cout << "插入成功,第" << i << "个位置，值为" << e << "，length为" << L.length << endl;
return true;
}
//删除顺序表里第i个位置的元素，并返回删除元素的值e
/*
时间复杂度
1）最好情况：删表尾O（1）
2）最坏情况：删表头O（n）
3）平均情况：O(n)
*/
bool ListDelete(Sqlist& L, int i, int& e) {
if (i<1 || i >L.length + 1) //判断i的范围是否有效
{
cout << "i 越界;i" << i << "Length：" << L.length << endl;
return false;
}
e = L.data[i - 1]; //将被删除的元素赋给e
for (int j = i; j < L.length; j++) //将第i个位置后的元素赋值给前一个结点
{
L.data[j - 1] = L.data[j];
}
L.length--; //线性表长度减一
cout << "成功删除第" << i << "个元素" << endl;
return true;
}
//按位查找L中第i个位置的元素
//时间复杂度：O（1）
int GetElem(Sqlist L, int i) {
if (i<1 || i >L.length + 1) //判断i的范围是否有效
{
cout << "i 越界" << endl;
return false;
}
return L.data[i - 1];
}
//按值查找
/*
*
最好情况：表头就是，O(1)
最坏情况：表尾才是，或者不存在，O(n)
*/
int LocateElem(Sqlist L, int i) {
int e;
for (e = 0; e < L.length; e++)
{
if (L.data[e] == i)
{
return i + 1;
}
}
return 0;
}
动态分配的顺序表
表长可以动态扩大
头文件：
#pragma once
#include <iostream>
#include <stdio.h>
#define InitSize 10 //默认的最大长度
typedef struct {
int* data; //指向动态分配数组的指针
int Maxsize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList;
void InitList(SeqList& L);
void IncreaseSize(SeqList& L, int length);
int GetElem(SeqList L, int i);
int LocateElem(SeqList L, int e);
源文件：
#include <stdarg.h>
#include <stdlib.h>
#include "SeqList.h"
using namespace std;
void InitList(SeqList& L) {
//用malloc函数申请一片连续的存储空间
L.data = (int*)malloc(InitSize * sizeof(int));
L.length = 0;
L.Maxsize = InitSize;
}
//增加动态数组的长度
void IncreaseSize(SeqList& L, int length) {
int* p = L.data;
if (length > 0 && L.Maxsize > 0)
{
int resizelength = L.Maxsize + length;
L.data = (int*)malloc(resizelength * sizeof(int));
}
//L.data = new int[(L.Maxsize + length) * sizeof(int)];
if (L.data != NULL) //该指针的值无效，则结果是未定义的,保证该值有效
{
for (int i = 0; i < L.length; i++) {
L.data[i] = p[i]; //将数据复制到新的区域
}
}
L.Maxsize = L.Maxsize + length;
free(p);
}
//按位查找L中第i个位置的元素
int GetElem(SeqList L, int i) {
return L.data[i - 1];
}
//按值查找
/*
时间复杂度
1）最好情况：O（1）
2）最坏情况：O（n）
3）平均情况：O(n)
*/
int LocateElem(SeqList L, int e) {
for (int i = 0; i < L.length; i++)
{
if (L.data[i] == e) {
return i + 1;
}
}
return 0;
}
单链表
链表的形式，通过指针指向下一项的地址，存储空间可以不连续
头文件：
#pragma once
#include <iostream>
#include <stdio.h>
using namespace std;
//typedef 数据类型重命名
typedef struct LNode //链表结点
{
int data; //数据域
struct LNode* next; //指针域
}LNode, * LinkList;
//带头节点的操作
bool InitList(LinkList& L);
bool isEmpty(LinkList L);
LinkList List_HeadInsert(LinkList& L);
LinkList List_TailInsert(LinkList& L);
LNode* GetElem(LinkList L, int i);
LNode* LocateElem(LinkList L, int e);
bool InsertLNode(LinkList& L, int i, int e);
bool InsertNextNode(LNode* p, int e);
bool InsertPriorNode(LNode* p, int e);
bool ListDelete(LinkList& L, int i, int& e);
bool DeleteNode(LNode* p);
int Length(LinkList L);
bool ListInsertWithOutHead(LinkList& L, int i, int e);
bool InitListwithoutHead(LinkList& L);
bool WhitOutisEmpty(LinkList L);
源文件：
#include <stdlib.h>
#include <iostream>
#include "LinkList.h"
using namespace std;
bool InitList(LinkList& L);
bool isEmpty(LinkList L);
LinkList List_HeadInsert(LinkList& L);
LinkList List_TailInsert(LinkList& L);
LNode* GetElem(LinkList L, int i);
LNode* LocateElem(LinkList L, int e);
bool InsertLNode(LinkList& L, int i, int e);
bool InsertNextNode(LNode* p, int e);
bool InsertPriorNode(LNode* p, int e);
bool ListDelete(LinkList& L, int i, int& e);
bool DeleteNode(LNode* p);
int Length(LinkList L);
bool ListInsertWithOutHead(LinkList& L, int i, int e);
bool InitListwithoutHead(LinkList& L);
bool WhitOutisEmpty(LinkList L);
//初始化不带头结点
bool InitListwithoutHead(LinkList& L) {
L = NULL;
return true;
}
//初始化带头结点
bool InitList(LinkList& L) {
L = new LNode[sizeof(LNode)];
if (L)
{
L->next = NULL;
return true;
}
else
{
return false;
}
}
//判断带头结点的单链表是否为空
bool isEmpty(LinkList L) {
if (L->next == NULL)
{
cout << "The linklist is empty" << endl;
return true;
}
else
{
return false;
}
}
//判断不带头结点的单链表是否为空
bool WhitOutisEmpty(LinkList L) {
if (L == NULL)
{
cout << "The linklist is empty" << endl;
return true;
}
else
{
return false;
}
}
/*
* @author : F G Y
* @function :头插法建立单链表
* 时间复杂度为O(n)
* 重要应用！！！
* 单链表的逆置
* @param :LinkList &L
* @return :L
*/
LinkList List_HeadInsert(LinkList& L) { //逆向建立单链表
LNode* s;
int x;
L = (LNode*)malloc(sizeof(LNode)); //创建头结点
scanf_s("%d", &x);
if (L)
{
while (x != 99) {
s = new LNode[sizeof(LNode)]; //create a new node
s->data = x; //新结点的数据为x
s->next = L->next; //新结点连接到头节点的后一结点
L->next = s; //头结点的指针域指向新结点
scanf_s("%d", &x);
}
}
return L;
}
/*
* @author : F G Y
* @function :尾插法建立单链表
* 时间复杂度为O(n)
* @param :LinkList &L
* @return :L
*/
LinkList List_TailInsert(LinkList& L) { //正向建立单链表
int x;
L = new LNode[sizeof(LNode)]; //创建单链表的表头
LNode* s, * r = L; //r为表尾指针，s为新结点
scanf_s("%d", &x);
while (x != 99) //输入99的话该程序跳出循环
{
s = new LNode[sizeof(LNode)]; //创建新的结点
s->data = x;
r->next = s; //将s插入到尾结点之后
r = s; //将s作为尾结点
scanf_s("%d", &x);
}
r->next = NULL; //尾结点指针置空
return L;
}
/*
* @author : F G Y
* @function :按序号查找节点值，从第一个结点出发，顺着指针next域逐个向下搜索
* 时间复杂度为O(n)
* @param :LinkList L，int i
* @return :LNode * p
*/
LNode* GetElem(LinkList L, int i) {
int j = 1; //计数，初始值为1
LNode* p = L->next; //头结点指针赋给p
if (i == 0) //如果i = 0 ，则返回头节点
{
return L;
}
if (i < 1) //i< 1说明i无效，返回Null
{
return NULL;
}
while (p && j < i) //从第一个结点开始找，查找第i个结点
{
p = p->next;
j++;
}
/*
第二种写法
if (i<0)
{
return NULL;
}
LNode* p;
int j = 0;
p = L;
while (p != NULL && j < i)
{
p = p->next;
j++
};
*/
return p; //返回第i个结点的指针，若i大于表长，则返回null
}
/*
* @author : F G Y
* @function :按值查找表结点
* 时间复杂度为O(n)
* @param :LinList L，int e；
* @return :LNode * p；
*/
LNode* LocateElem(LinkList L, int e) {
LNode* p = L->next;
while (p != NULL && p->data != e) //从第一个结点开始查找data域为e的结点
{
p = p->next;
}
return p; //找到后返回该结点指针，否则返回null；
}
/*
* @author : F G Y
* @function :求表长
* O(n)
* @param :LinkList L
* @return :len
*/
int Length(LinkList L) {
int len = 0;
LNode* p = L;
while (p->next != NULL)
{
p = p->next;
len++;
}
return len;
}
/*
* @author : F G Y
* @function :插入节点，将值为x的新结点插入到单链表的第i个位置
* 先找到第i-1个结点（即插入结点前一结点）为 *p ，将插入结点的的指针域指向*p的后继结点，在再令结点*p的指针域
* 指向新插入的节点
时间复杂度 O(n)
* @param :LinkList &L,int i,int e
* @return :bool
*/
bool InsertLNode(LinkList& L, int i, int e) {
if (i < 1)
{
return false;
}
LNode* p; //指针p指向当前扫描的结点
int j = 0; //当前p指向的第几个结点
p = L; //L指向头节点，头结点是第0个结点（不存放数据）
while (p != NULL && j < i - 1)//循环找到第i-1个结点，使p为第i-个结点
{
p = p->next;
j++;
}
if (p == NULL) //i值不合法
{
return false;
}
//也可以直接 LNode* p = GetElem(L, i-1);
//retrun InsertNextNode(p, e);
else
{
LNode* s = (LNode*)malloc(sizeof(LNode));
if (s && s->data) //保证指针的值有效
{
s->data = e;
s->next = p->next; //①把s结点的指针域指向p+1的结点
p->next = s; //②把p结点的指针域指向s结点
/*
①②的位置不能互换，若②先，则s结点的无法指向p结点的下一个结点
*/
return true;
}
}
return false;
}
/*
* @author : F G Y
* @function :指定结点的后插
* 时间复杂度为O(1)
* @param :LNode *p, int e;
* @return :bool
*/
bool InsertNextNode(LNode* p, int e) {
if (p == NULL)
{
return false;
}
LNode* s = new LNode[sizeof(LNode)];
if (s)
{
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
else
{
return false;
}
}
/*
* @author : F G Y
* @function : 前插操作 O（1）
* @param :LNode *p，int e
* @return :bool
*/
bool InsertPriorNode(LNode* p, int e) {
if (p)
{
LNode* s = new LNode[sizeof(LNode)];
if (s)
{ //向p后面插入一个，将p的数据给s，将e赋值给p的数据域
s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;
}
else {
return false;
}
}
else {
return false;
}
return false;
}
bool InsertPriorNode(LNode* p, LNode* s) {
if (p == NULL || s == NULL)
{
return false;
}
else {
s->next = p->next;
p->next = s;
int temp = p->data;
p->data = s->data;
s->data = temp;
return true;
}
}
/*
* @author : F G Y
* @function : 按位序删除（带头结点）,并用e返回删除元素的值
* 最好为O(1),平均和最坏为O（n）;
* @param :LinkList &L,int i,int &e
* @return :bool
*/
bool ListDelete(LinkList& L, int i, int& 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* p = GetElem(L, i - 1);
LNode* q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}
/*
* @author : F G Y
* @function : 指定节点（除表尾）的删除,后继结点的值传给p，然后把后继结点给释放
* 时间复杂都为O(1)
* @param :LNode *p
* @return :bool
*/
bool DeleteNode(LNode* p) {
if (p == NULL)
{
return false;
}
LNode* q = p->next;
p->data = p->next->data; //此处有BUG，如果p为表尾结点，则该处为空指针错误，只能从表头开始以此向后寻找表尾结点的前一结点
p->next = q->next;
free(q);
return true;
}
//不带头结点插入，对i=1时要特殊处理，此时j从1开始
bool ListInsertWithOutHead(LinkList& L, int i, int e) {
if (i < 1)
{
return false;
}
else if (i == 1) //输入第一个结点时与其他结点操作不同
{
LNode* s = (LNode*)malloc(sizeof(LNode));
if (s)
{
s->data = e;
s->next = L;
L = s; //头指针指向新的节点
return true;
}
}
else
{
LNode* p; //指针p指向当前扫描的结点
int j = 1; //当前p指向的第几个结点
p = L; //L指向头节点，头结点是第0个结点（不存放数据）
while (p != NULL && j < i - 1)//循环找到第i-1个结点，使p为第i-个结点
{
p = p->next;
j++;
}
if (p == NULL) //i值不合法
{
return false;
}
else
{
LNode* s = (LNode*)malloc(sizeof(LNode));
if (s && s->data) //保证指针的值有效
{
s->data = e;
s->next = p->next; //①把s结点的指针域指向p+1的结点
p->next = s; //②把p结点的指针域指向s结点
/*
①②的位置不能互换，若②先，则s结点的无法指向p结点的下一个结点
*/
return true;
}
}
}
return false;
}
带头结点的双链表
头文件：
#pragma once
#include <stdio.h>
#include <iostream>
using namespace std;
typedef struct DNode {
int data;
struct DNode* prior, * next;
}DNode, * DLinkList;
//初始化
bool InitDLinkList(DLinkList& L);
//判断双链表是否为空
bool Empty(DLinkList L);
//在p结点之后插入s结点
bool InsertNextDNode(DNode* p, DNode* s);
//删除p的后继结点
bool DeleteNextDNode(DNode* p);
//销毁双链表
void DestroyList(DLinkList& L);
//遍历双链表
void ErgodicDoubleLinkList(DLinkList& L);
源文件：
#include <stdio.h>
#include "DNode.h"
//初始化
bool InitDLinkList(DLinkList& L) {
L = (DNode*)malloc(sizeof(DNode));//分配一个头结点
if (L == NULL) //内存不足，分配失败
{
return false;
}
L->prior = NULL; //头节点的prior永远指向NULL
L->next = NULL;
return true;
}
//判断双链表是否为空
bool Empty(DLinkList L) {
if (L->next == NULL)
{
return true;
}
else
{
return false;
}
}
//在p结点之后插入s结点
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;
}
//删除p的后继结点
bool DeleteNextDNode(DNode* p) {
if (p == NULL)
{
return false;
}
DNode* q = p->next; //找到p的后继结点
if (q == NULL)
{
return false; //p没有后继
}
p->next = q->next;
if (q->next != NULL) //q结点不是最后一个节点
{
q->next->prior = p;
}
free(q);
return true;
}
//销毁双链表
void DestroyList(DLinkList& L) {
while (L->next != NULL)
{
DeleteNextDNode(L);
}
free(L);
L = NULL;
}
//遍历双链表 O（n）
void ErgodicDoubleLinkList(DLinkList& L) {
DNode* p = L;
if (p)
{
while (p != NULL) //后向遍历
{
p = p->next;
}
while (p != NULL) //前向遍历
{
p = p->prior;
}
}
if (p && p->prior)
{
while (p->prior != NULL) //前向遍历（跳过头结点）
{
p = p->prior;
}
}
}
循环单链表
头文件：
#pragma once
#include <stdio.h>
#include <iostream>
using namespace std;
/*
* @author : F G Y
* @function :循环单链表
* 在对表头表尾操作比较多的时候，可以让L指向表尾元素
* @param :
* @return :
*/
typedef struct CLNode {
int data;
struct CLNode* next;
}CLNode, * CLinkList;
/*
* @author : F G Y
* @function : 初始化一个循环单链表
* @param :CLinkList &CL
* @return :bool
*/
bool InitList(CLinkList& CL);
/*
* @author : F G Y
* @function : 判断循环单链表为空
* @param : CLinkList C
* @return :bool
*/
bool Empty(CLinkList C);
/*
* @author : F G Y
* @function :判断结点p是否为循环单链表的表尾结点
* @param :CLinkList CL，CLNode *p
* @return :bool
*/
bool isTail(CLinkList CL, CLNode* p);
源文件：
#include "CLNode.h"
bool InitList(CLinkList& CL);
bool Empty(CLinkList C);
bool InitList(CLinkList& CL) {
CL = new CLNode[sizeof(CLNode)]; //分配头结点
if (CL)
{
CL->next = CL; //头结点next指针指向头结点
return true;
}
return false;
}
bool Empty(CLinkList CL) {
if (CL->next == CL)
{
return true;
}
return false;
}
bool isTail(CLinkList CL, CLNode* p) {
if (p->next == CL)
{
return true;
}
else
{
return false;
}
}
循环双链表
头文件：
#pragma once
typedef struct CDNode {
int data;
struct CDNode* prior, * next;
}CDNode, * CDLinkList;
/*
* @author : F G Y
* @function :初始化空的循环双链表
* @param :
* @return :
*/
bool InitList(CDLinkList& L);
/*
* @author : F G Y
* @function :循环双链表判空操作
* @param :
* @return :
*/
bool Empty(CDLinkList L);
/*
* @author : F G Y
* @function :p是否为循环双链表的尾结点
* @param :
* @return :
*/
bool isTail(CDLinkList L, CDNode* p);
/*
* @author : F G Y
* @function :在p结点之后插入s结点
* @param :CDNode* p, CDNode* s
* @return :bool
*/
bool InsertNextDNode(CDNode* p, CDNode* s);
/*
* @author : F G Y
* @function :删除结点
* @param :CDNode* p
* @return :bool
*/
bool DeleteNextDNode(CDNode* p);
源文件：
#include <stdio.h>
#include <iostream>
#include "CDNode.h"
bool InitList(CDLinkList& L);
bool Empty(CDLinkList L);
bool isTail(CDLinkList L, CDNode* p);
bool InsertNextDNode(CDNode* p, CDNode* s);
bool DeleteNextDNode(CDNode* p);
bool InitList(CDLinkList& L) {
L = (CDNode*)malloc(sizeof(CDNode));
if (L == NULL)
{
return false;
}
L->next = L;
L->prior = L;
return true;
}
bool Empty(CDLinkList L) {
if (L->next == L)
{
return true;
}
else
{
return false;
}
}
bool isTail(CDLinkList L, CDNode* p) {
if (p->next == L)
{
return true;
}
else
{
return false;
}
}
bool InsertNextDNode(CDNode* p, CDNode* s) {
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
return true;
}
bool DeleteNextDNode(CDNode* p) {
CDNode* q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);
return true;
}
静态链表
用数字代替指针
#pragma once
#include <stdio.h>
#include <iostream>
#define MaxSize 10
using namespace std;
struct Node
{
int data;
int next;
};
typedef struct {
int data;
int next;
}SLinkList[MaxSize];
/*
静态链表：用数组的方式实现链表
优点：增删操作不需要大量移动元素
缺点：不能随即存储、只能从头结点开始查找，容量固定不可变
适用场景：不支持指针的低级语言；数据元素数量固定不变
*/
/*
* @author : F G Y
* @function :初始化，把空的结点的next值设为特殊值，如-2
* O（n）
* @param :
* @return :
*/
bool InitList(SLinkList& SL);
/*
* @author : F G Y
* @function :查找结点
* O(n)
* @param :
* @return :
*/
/*
* @author : F G Y
* @function :插入为序为i的结点
* ①找到一个空的结点，存入数据元素
* ②从头结点出发到位序为i-1的结点
* ③修改新结点的next
* ④修改i-1号结点的next
* @param :
* @return :
*/
|