结点：
包括数据域和一个指针域
结点
单链表：
n个结点通过指针域将线性表的数据元素连接在一起
链表
1.有时，为了更加方便地对链表进行操作，会在单链表的第一个节点前附设一个结点，称为头结点，其数据域一般无意义（也可存放链表的长度）
2.有了头结点，对在第一元素结点前插入结点和删除第一结点的操作就可以与其他结点相统一（具体见后文）
3.对于有头结点的链表，通常使用LinkList定义指向头结点的头指针，而不使用LNode,指向其他结点使用LNode定义
4.头指针是指向链表第一个结点的指针，若链表有头结点，则是指向头结点的指针
5.默认情况下通常指的是带有头结点的链表，如下图
有头结点的链表
LinkList.h
#pragma once
// 函数结果状态代码
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
//数据类型
typedef int ElemType;
typedef struct LNode //链表节点
{
ElemType data; //数据域
struct LNode* next; //指针域
}LNode, * LinkList;
//初始化链表
Status InitList(LinkList& L);
//判断链表是否为空
bool ListEmpty(LinkList L);
//销毁单链表
Status DestroyList(LinkList& L);
//清空单链表（头指针和头结点仍然存在）
Status ClearList(LinkList& L);
//求单链表表长
int ListLength(LinkList L);
//取单链表中第i个元素的内容
int GetElem(LinkList L, int i, ElemType& e);
//根据指定数据获取数据所在位置
LNode* LocateElem(LinkList L, ElemType e);
//在链表中查找值为e的数据元素的位置序号
int LocateElem_L(LinkList L, ElemType e);
//插入：在第i个结点前插入值为e的新结点
Status ListInsert(LinkList& L, int i, ElemType e);
//删除：删除第i个结点
Status ListDelete(LinkList& L, int i, ElemType& e);
//遍历
void ListTraverse(LinkList L);
//头插法建立单链表
void CreateList_H(LinkList& L, int n);
//尾插法建立单链表
void CreateList_T(LinkList& L, int n);
//尾插插入单个元素
void ListInsert_T(LinkList& L, ElemType e);
//链表合并
void ListUnion(LinkList& L1, LinkList L2);
//有序表合并
void ListMerge_Sq(LinkList& L1, LinkList L2);
LinkList.cpp
#include "LinkList.h"
#include <iostream>
using namespace std;
//初始化链表
Status InitList(LinkList& L)
{
L = new LNode; //或L(LinkList)malloc(sizeof(LNode))
L->next = NULL;
cout << "初始化链表成功" << endl;
return OK;
}
//判断链表是否为空
bool ListEmpty(LinkList L)
{
if (L)
{
if (L->next == NULL)
{
cout << "链表为空" << endl;
return true;
}
else
{
cout << "链表不为空" << endl;
return false;
}
}
else
{
cout << "链表不存在" << endl;
}
}
销毁：
销毁单链表
需要销毁头结点在内的所有结点
1.p开始与L都指向头结点
2.将L后移并销毁p指向的头结点
3.p与L都指向下一个结点，再回到第二步，如此循环
//销毁单链表(包括头结点在内的所有结点销毁)
Status DestroyList(LinkList& L)
{
LNode* p; //或LinkList p;
while (L)
{
p = L; //p也指向头结点
L = L->next; //L后移
delete p; //释放p
}
cout << "销毁成功" << endl;
return OK;
}
清空：保留头结点，其他结点清空
清空单链表
1.开始，p指向第一个结点，即头结点的下一个结点，q指向第二个结点（类似于销毁，将p,q分别看做销毁过程的p和L结点）
2.删除p结点
3.p和q结点各后移一个，再回到第二步，如此循环
//清空单链表（头指针和头结点仍然存在）
Status ClearList(LinkList& L)
{
LNode* p = L->next; //p存放第一个结点
LNode* q;
while (p)
{
q = p->next; //q指向p的下一个结点
delete p; //释放p
p = q; //p后移
}
L->next = NULL; //头结点指针域为空
cout << "清空成功" << endl;
return OK;
}
//求单链表表长
int ListLength(LinkList L)
{
if (ListEmpty(L)) //是否为空
{
cout << "表长为0" << endl;
return 0;
}
LNode* p = L->next;
int length = 0;
while (p)
{
p++;
p = p->next;
}
return length;
}
//取单链表中第i个元素的内容
int GetElem(LinkList L, int i, ElemType& e)
{
LNode* p = L->next;
int j = 1;
while (p && j < i) //p一直后移，当j==i时找到
{
j++;
p = p->next;
}
if (!p || j > i) //未找到或i不合法
{
cout << "第i个元素不存在" << endl;
return ERROR;
}
e = p->data;
return OK;
}
//根据指定数据获取数据所在位置（第一个位置，可能该数据在链表中有重复）
LNode* LocateElem(LinkList L, ElemType e)
{
LNode* p = L->next;;
while (p && (p->data != e))
{
p = p->next;
}
return p; //找到后返回L中数据为e的数据元素地址，未找到返回NULL
}
//在链表中查找值为e的数据元素的位置序号
int LocateElem_L(LinkList L, ElemType e)
{
LNode* p = L->next;
int j = 1;
while (p && (p->data != e))
{
p = p->next;
j++;
}
if (p) //找到返回j
{
return j;
}
else
{
return 0; //未找到返回0
}
}
插入：
插入
1.找到要插入位置的前驱结点p
2.生成新结点s
3.新结点next域指向结点p的next域原来指向的结点
4.结点p的next域指向新结点s
//插入：在第i个结点前插入值为e的新结点
Status ListInsert(LinkList& L, int i, ElemType e)
{
LNode* p = L;
int j = 0;
while (p && (j < i - 1)) //一直后移到表尾结束或者到插入位置前一个结点结束
{
p = p->next;
j++;
}
if (!p || (j > i - 1)) //表长为n，插入位置的范围为1至n+1,故p最多到最后一个结点，
//如果p为空表示i大于表长加1或者链表不存在,j>i-1表示插入位置小于1，插入位置非法
{
cout << "插入失败" << endl;
return ERROR;
}
//生成新结点
LNode* s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
cout << "插入成功" << endl;
return OK;
}
删除：
删除
1.找到要删除的结点q和它的前驱结点p
2.前驱结点p的next域指向删除结点q的next域，即完成了删除
//删除：删除第i个结点
Status ListDelete(LinkList& L, int i, ElemType& e)
{
LNode* p = L;
int j = 0;
while (p->next && (j < (i - 1))) //找到p的前驱
{
p = p->next;
j++;
}
if (!p->next || j > i - 1) //删除位置不合理，只能删除1至n的数据元素
{
cout << "删除失败" << endl;
return ERROR;
}
LNode* q = p->next; //q为要删除的结点
e = q->data; //保存删除结点的数据域
p->next = q->next; //删除操作
return OK;
}
//遍历
void ListTraverse(LinkList L)
{
if (ListEmpty(L) || !L)
{
cout << "链表为空或者不存在" << endl;
return;
}
LNode* p = L->next;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
下面的头插法和尾插法建立单链表参考前面的插入单个元素的算法
//头插法建立单链表
void CreateList_H(LinkList& L, int n)
{
L = new LNode;
L->next = NULL; //开始头结点的next置为NULL
for (int i = n; i > 0; i--)
{
LNode* p = new LNode; //建立新结点
p->data = i;
p->next = L->next; //执行插入操作
L->next = p;
}
}
//尾插法建立单链表
void CreateList_T(LinkList& L, int n)
{
L = new LNode;
L->next = NULL;
LNode* r = L; //开始时尾指针指向头结点
for (int i = 1; i <= n; i++)
{
LNode* p = new LNode; //建立新结点
p->data = i;
p->next = NULL; //新结点作为尾部，则next域为NULL
r->next = p; //插入新结点
r = p; //r指向新结点，即为尾部
}
}
//尾插插入单个元素
void ListInsert_T(LinkList& L, ElemType e)
{
LNode* p = L;
while (p->next)
{
p = p->next;
}
LNode* s = new LNode;
s->data = e;
s->next = NULL;
p->next = s;
}
//链表合并
void ListUnion(LinkList& L1, LinkList L2)
{
LNode* p = L2->next;
while (p)
{
if (!LocateElem_L(L1, p->data))
{
ListInsert_T(L1, p->data);
}
p = p->next;
}
}
有序表合并
让合并的新链表与L1共用一个头结点，且p3指向新链表的末尾结点
1.比较p1和p2的数据域大小
2.p3的next域指向p1或者p2(较小)
3.原来指向较小的结点的指针后移
4.指向新链表的末尾结点的指针p3后移
5.回到第一步，直到其中一个链表的数据全部被插入到新链表中
6，将另一个链表中剩下的数据插入到新链表中
//有序表合并，合并到L1中
void ListMerge_Sq(LinkList& L1, LinkList L2)
{
LNode* p1 = L1->next; //第一个结点
LNode* p2 = L2->next;
LNode* p3 = L1; //p3指向合并的链表最后一个结点
while (p1 && p2)
{
if (p1->data > p2->data) //如果p2小，
{
p3->next = p2; //将p2加入到合并链表
p2 = p2->next; //p2后移
}
else
{
p3->next = p1;
p1 = p1->next;
}
p3 = p3->next; //添加一个，p3后移一个，保持始终指向末尾结点
}
p3->next = p1 ? p1 : p2; //p1或者p2中未合并完的加入到合并链表
}
main.cpp
测试：
#include <iostream>
#include "LinkList.h"
using namespace std;
int main(int argc, char** argv)
{
LinkList L = new LNode;
InitList(L); //初始化
ListEmpty(L); //判空
ListLength(L); //求链表长度
ListTraverse(L); //遍历
ListInsert(L, 1, 1); //第一个位置插入1
ListInsert(L, 2, 2);
ListInsert(L, 3, 3);
ListTraverse(L); //遍历
ElemType x;
GetElem(L, 3, x);
cout << "链表中第三个元素为：" << x << endl;
LNode* p;
p = LocateElem(L, 1);
cout << "链表中数据为1的结点：" << p->data << endl;
int i = LocateElem_L(L, 1);
cout << "链表中数据为1的结点为第" << i << "个结点" << endl;
ElemType e;
ListDelete(L, 3, e);
cout << "删除了链表中第三个结点：" << e << endl;
ClearList(L); //清空
ListEmpty(L); //判空
DestroyList(L); //销毁
ListEmpty(L); //判空
ListInsert(L, 1, 1); //插入
cout << "***********************************" << endl;
LinkList L_H;
CreateList_H(L_H, 5);
ListTraverse(L_H);
LinkList L_T;
CreateList_T(L_T, 5);
ListTraverse(L_T);
//-----------链表合并--------------
LinkList L1, L2;
InitList(L1);
InitList(L2);
ListInsert_T(L1, 7);
ListInsert_T(L1, 5);
ListInsert_T(L1, 3);
ListInsert_T(L1, 11);
ListInsert_T(L2, 2);
ListInsert_T(L2, 6);
ListInsert_T(L2, 3);
ListTraverse(L1);
ListTraverse(L2);
//合并
ListUnion(L1, L2);
ListTraverse(L1);
//-----------有序表合并-----------
LinkList L3, L4;
InitList(L3);
InitList(L4);
ListInsert_T(L3, 1);
ListInsert_T(L3, 7);
ListInsert_T(L3, 8);
ListInsert_T(L4, 2);
ListInsert_T(L4, 4);
ListInsert_T(L4, 6);
ListInsert_T(L4, 8);
ListInsert_T(L4, 10);
ListInsert_T(L4, 11);
ListMerge_Sq(L3, L4);
ListTraverse(L3);
return 0;
}
网友评论