1.单链表
1.1.单链表的定义
- 优点：离散存放（不需要连续的存储空间），改变容量方便
- 缺点：不支持随机存储，需要额外空间存放指针
typedef struct LNode{ //定义单链表节点类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下个节点 }LNode, *linkList;
要表示单链表的时候，只需申明一个头指针L，指向单链表的第一个节点
//*Lnode L; //强调是一个节点 linkList L; //强调是一个链表，代码可读性更强
1.2.不带头结点的单链表
typedef struct LNode { //定义单链表节点类型 Elemtype data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode, *linkList; //初始化单链表 bool initList(linkList &L) { //将表置空，防止脏数据 L = NULL; return true; } //判断表空 bool empty(linkList L){ if (L == NULL) return true; else return false; } void main() { //申明一个指向单链表的指针 linkList L; //初始化单链表 initList(L); //后续代码 }
1.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; //当前表空，因此将头结点的next指针置空 L->next = NULL; return true; } //判断表空 bool empty(linkList L){ if (L->next == NULL) return true; else return false; } void main() { //申明一个指向单链表的指针 linkList L; //初始化单链表 initList(L); //后续操作 }
1.4.单链表的插入
1.4.1. 带头结点
bool listInsert(linkList& L, Elemtype e, int i) { //判断i值是否合法（判断是否过小） if (i < 1) return false; //申明一个LNode类型的指针*p，并使其指向linkList的头结点L LNode *p = L; //遍历单链表，找到要插入的位序 for (int j = 0; p != NULL && j < i - 1; j++) p = p->next; //判断i值是否合法（判断是否过大） if (p == NULL) return false; //申明一个节点s，并为它分配内存空间和数据 LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; //在单链表中插入s s->next = p->next; p->next = s; return true; }
1.4.2.不带头结点
bool listInsert(linkList& L, int e, int i) { //判断i值是否合法 if (i < 1) return false; //i=1时为特殊情况，在表头插入元素 if (i == 1) { //申明一个节点s，并为其分配空间和输入数据 LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; //将s插入表头，并且把L的指向改为s s->next = L; L = s; return true; } //申明一个LNode*类型的指针p指向第一个节点，并使用其遍历单链表 LNode *p = L; for (int j = 1; p != NULL && j < i - 1) p = p->next; //i值不合法 if (p == NULL) return false; //申明一个节点s，并为其分配空间和输入数据 LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; //将s插入单链表中 s->next = p->next; p->next = s; return true; }
1.4.3.尾插法
//尾插法 bool insertNextNode(LNode *p, int e) { //i值不合法 if (p == NULL) return false; LNode *s = (LNode*)malloc(sizeof(LNode)); //内存分配失败 if (s == NULL) return false; s->data = e; //插入s s->next = p->next; p->next = s; return true; } bool listInsert(linkList& L, int e, int i) { if (i < 1) return false; LNode *p = L; for (int j = 0; p != NULL && j < i - 1) p = p->next; //调用尾插法函数插入元素 return insertNextNode(p, e); }
1.4.4.前插法
//前插法 bool insertPriorNode(LNode *p, int e) { //i值不合法 if (p == NULL) return false; LNode* s = (LNode*)malloc(sizeof(LNode)); //在p后插入一个新节点s s->next = p->next; p->next = s; //将p的数据赋值给s，再将e赋值给p s->data = p->data; p->data = e; return true; }
1.5.单链表的删除
1.5.1.按位序删除（带头结点）
//按位序删除 bool listDelete(linkList& L, int i, Elemtype& e) { //i值不合法 if (i < 1) return false; //申明一个LNode类型的指针指向头结点 LNode* p = L; //将指针指向第i - 1个元素 for (int j = 0; p != NULL && j < i - 1; j++) p = p->next; //i值不合法 if (p == NULL) return false; //第i个元素为空 if (p->next == NULL) return false; //取回第i个元素的值 LNode* q = p->next; e = q->data; p->next = q->next; free(q); return true; }
1.5.2.指定节点删除
//指定节点删除 bool deleteNode(LNode* p) { //i值不合法 if (p == NULL) return false; //申明一个节点q，并使其指向p-> LNode* q = p->next; //将q的数据赋值给q p->data = q->data; //q的nxet指针赋值给q p->next = q->next; //释放q free(q); return true; }
1.6.单链表按值查找
//按值查找 LNode* locateElem(linkList L, Elemtype e) { LNode* p = L->next; //从第一个元素遍历查找值为e的结点 for (int i = 1; p != NULL && p->data != e) p = p->next; return p; //找到后返回该节点指针，否则返回NULL }
1.7.求单链表长
//求表长 int length(linkList L) { //申明一个LNode*类型的指针p，使其指向表中第一个节点 LNode* p = L->next; //标记长度 int length = 0; //遍历单链表 while (p != NULL) { p = p->next; length++; } return length; }
1.8.单链表的建立
1.8.1.尾插法
linkList listTailInsert(linkList& L) { Elemtype x; //为单链表L开辟一个新的内存空间，作为头结点 L = (linkList)malloc(sizeof(linkList)); //申明两个指针，并让它们指向头结点 LNode* i = L, * j = L; //输入数据 cin >> x; //停止输入（0可以改为任意值） while (x != 0) { //开辟一个大小为LNode的内存空间，并让j指向它 j = (LNode*)malloc(sizeof(LNode)); //为j输入数据 j->data = x; //将j插入单链表中 i->next = j; //i后移至j i = j; //循环输出数据 cin >> x; } //将最后一个节点的next置空 i->next = NULL; return L; }
1.8.2.头插法
linkList listHeadInsert(linkList& L) { //为头结点分配内存空间 L = (linkList)malloc(sizeof(linkList)); L->next = NULL; LNode* i; Elemtype x; cin >> x; whil(x != 0) { //为节点i分配内存空间，并输入数据 i = (LNode*)malloc(sizeof(LNode)); i->data = x; //将i插入表中 i->next = L->next; L->next = i; cin >> x; } return L; }
2.双链表
2.1.双链表的初始化
typedef struct DNode { Elemtype data; struct DNode* prior, * next; }DNode, *DLinkList; //初始化双链表 bool initDLinkList(DLinkList& L) { //为头结点分配空间 L = (DLinkList)malloc(sizeof(DLinkList)); //内存分配失败 if (L == NULL) return false; //头结点的前后指针置空 L->prior = NULL; L->next = NULL; return true; } void testDLinkList() { //申明一个双链表 DLinkList L; //初始化双链表 initDLinkList(L); //后续操作 }
2.2.双链表的插入
bool insertNode(DNode* p, DNode* s) { //插入操作非法 if (p == NULL && s == NULL) return false; s->next = p->next; //特殊情况：p为双链表中最后一个节点 if (p->next != NULL) p->next->prior = s; s->prior = p; p->next = s; return true; }
2.3.双链表的删除、销毁
//删除双链表当前节点的下个节点 bool deleteNextDNode(DNode* p) { //删除操作非法 if (p == NULL) return false; //申明一个DNode*类型的指针q指向p的下一个节点 DNode* q = p->next; //删除操作非法 if (q == NULL) return false; //改变前后指针，并且释放p的下一个节点q的内存空间 p->next = q->next; //q不是最后一个节点 if (q->next != NULL) q->next->prior = p; free(q); return true; } //销毁双链表 void destroyDLinkList(DLinkList &L){ //遍历双链表，并且释放下个节点 while(L->next != NULL) deleteNextDNode(L); //释放头结点 free(L); //头指针L置空 L = NULL; }
2.3.双链表的删除、销毁
1.
//删除双链表当前节点的下个节点 bool deleteNextDNode(DNode* p) { //删除操作非法 if (p == NULL) return false; //申明一个DNode*类型的指针q指向p的下一个节点 DNode* q = p->next; //删除操作非法 if (q == NULL) return false; //改变前后指针，并且释放p的下一个节点q的内存空间 p->next = q->next; //q不是最后一个节点 if (q->next != NULL) q->next->prior = p; free(q); return true; } //销毁双链表 void destroyDLinkList(DLinkList &L){ //遍历双链表，并且释放下个节点 while(L->next != NULL) deleteNextDNode(L); //释放头结点 free(L); //头指针L置空 L = NULL; }
3.循环链表
typedef struct LNode { Elemtype data; struct LNode *next; }LNode, *linkList; //初始化循环链表 bool initList(linkList& L) { L = (linkList)malloc(sizeof(linkList)); //内存分配失败 if (L == NULL) return false; //将L的next指针指向自己 L->next = L; return true; } //判断表空 bool isEmpty(linkList L) { if (L->next = L) return true; else return false; } //判断表尾 bool isTail(LNode* p) { if (p->next == L) return true; else return false; }
4.循环双链表
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->next = L; L->prior = L; return true; } //判断表空 bool isEmpty(DLinkList L) { if (L->next == L) return true; else return false; } //判断表尾 bool isTail(DLinkList L, DNode *p) { if (p->next == L) return true; else return false; } void testDLinkList() { DLinkList L; initDLinkList(L); }
5.链表和顺序表的区别
5.1.逻辑结构
顺序表和链表都属于线性表
5.2.存储结构
- 顺序表
- 优点：存储密度大，支持随机存储
- 缺点：需要一片连续的存储空间，改变容量不方便
- 链表
- 优点：支持离散存储，可以动态的修改容量
- 缺点：存储密度小（需要存放指针），不支持随机存储
5.3.基本操作
5.3.1.创建
- 顺序表：预分配一片连续的存储空间
- 静态分配：容量不可更改
- 动态分配：容量可以更改，但需要大量移动
- 链表：仅分配一个头结点（也可以仅声明一个头指针）
5.3.2.销毁
- 顺序表：修改length = 0，逻辑上销毁
- 静态分配：由系统自动回收
- 动态分配：需要手动free
- 链表：逐个free节点
5.3.3.增加/删除
- 顺序表：在增加/删除的位置后方逐一移动元素，时间复杂度为O(n)
- 链表：需找到该元素的所在位置，然后修改指针，时间复杂度为O(n)
- 虽然顺序表和链表的时间复杂度都为O(n)，但是顺序表的操作为移动元素，链表的操作为查找元素，因此，顺序表所需时间远大于链表
5.3.4.查找
- 按位序查找
- 顺序表：由于有随机存储特性，因此，时间复杂度为O(1)
- 链表：需要按序遍历链表，因此，时间复杂度为O(n)
2.按值查找
- 顺序表：按序遍历顺序表，因此，时间复杂度为O(n)，如果有序，可为O(lon2n)
- 链表：按序遍历链表，因此，时间复杂度为O(n)
