LinkList.cpp //链表相关操作的实现
//
// Created by leoxae on 19-11-5.
//
#include "LinkList.h"
/**
* [1]头插法建立单链表
* @return
*/
LinkList LinkListclass::HeadInsertCreateList(void) {
char ch;
LinkList head;
ListNode *p;
head = NULL;/*初始化为空*/
ch = getchar();
while (ch != '\n') {
p = (ListNode *) malloc(sizeof(ListNode));/*分配空间*/
p->data = ch;/*数据域赋值*/
p->next = head;/*指定后继指针*/
head = p;/*head指针指定到新插入的结点上*/
ch = getchar();
}
return (head);
}
/**
* [2]尾插法建立单链表
* @return
*/
LinkList LinkListclass::TailInsertCreateList() {
char ch;
LinkList head;
ListNode *p, *r;
head = NULL;
r = NULL;/*r为尾指针*/
while ((ch = getchar()) != '\n') {
p = (ListNode *) malloc(sizeof(ListNode));
p->data = ch;
if (head == NULL)
head = p;/*head 指向第一个插入结点*/
else
r->next = p;/*插入到链表尾部*/
r = p;/*r指向最新结点，即最后结点*/
}
if (r != NULL)
r->next = NULL;/*链表尾部结点的后继指针指定为空*/
return (head);
}
/**
* [3]按序号查找单链表
* @param head
* @param i
* @return
*/
ListNode *LinkListclass::getnode(LinkList head, int i) {
int j;
ListNode *p;
p = head;
j = 0;
while (p->next && j < i) {/*遍历第i个结点前的所有结点*/
p = p->next;
j++;
}
if (i == j) {
printf("%c\n", p->data);
return p;
} else
return NULL;
}
/**
* [4]按值查找单链表
* @param head
* @param key
* @return
*/
ListNode *LinkListclass::locatenode(LinkList head, char key) {
ListNode *p = head;
while (p->next && p->data != key)
p = p->next;
if (p != NULL)
printf("%c\n", p->data);
return p;
}
/**
* []插入元素e到表L
* @param head
* @param x
* @param i
*/
void LinkListclass::insertnode(LinkList head, char x, int i) {
int j = 0;
ListNode *p, *s;
p = head;
while (p && j < i - 1) {
p = p->next;
++j;
}
if (!p || j > i - 1)
exit(1);
s = (LinkList) malloc(sizeof(ListNode));
s->data = x;
s->next = p->next;
p->next = s;
}
/**
* [6]从表L中删除元素e
* @param head
* @param i
*/
void LinkListclass::deletelist(LinkList head, int i) {
int j = 0;
ListNode *p, *r;
p = head;
while (p && j < i - 1) {
p = p->next;
++j;
}
if (!p->next || j > i - 1)
exit(1);
r = p->next;
p->next = r->next;
free(r);
}
/**
* [7]合并两个链表
* @param list1
* @param list2
* @return
*/
LinkList LinkListclass::concatenate(LinkList list1, LinkList list2) {
ListNode *temp;
if (list1 == NULL)
return list2;
else {
if (list2 != NULL) {
for (temp = list1; temp->next; temp = temp->next); /*遍历到list1的末尾*/
temp->next = list2;/*将list2链接到list1末尾*/
}
}
return list1;
}
//----------------------------[单循环链表LoopList基本操作]-----------------------------
/**
* [1]初始化表L
* @param L
* @return
*/
Status LinkListclass::InitList_CL(LoopLinkList *L) { /* 操作结果：构造一个空的线性表L */
*L = (LoopLinkList) malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */
if (!*L) /* 存储分配失败 */
exit(ERROR);
(*L)->next = *L; /* 指针域指向头结点 */
return OK;
}
/**
* [2]插入元素e到表L
* @param L
* @param i
* @param e
* @return
*/
Status LinkListclass::ListInsert_CL(LoopLinkList *L, int i, ElemType e) /* 改变L */
{ /* 在L的第i个位置之前插入元素e */
LoopLinkList p = (*L)->next, s; /* p指向头结点 */
int j = 0;
if (i <= 0 || i > ListLength_CL(*L) + 1) /* 无法在第i个元素之前插入 */
return ERROR;
while (j < i - 1) /* 寻找第i-1个结点 */
{
p = p->next;
j++;
}
s = (LoopLinkList) malloc(sizeof(struct LNode)); /* 生成新结点 */
s->data = e; /* 插入L中 */
s->next = p->next;
p->next = s;
if (p == *L) /* 改变尾结点 */
*L = s;
return OK;
}
/**
* [3]删除表中的元素
* @param L 线性表
* @param i
* @param e
* @return
*/
Status LinkListclass::ListDelete_CL(LoopLinkList *L, int i, ElemType *e) /* 改变L */
{ /* 删除L的第i个元素,并由e返回其值 */
LoopLinkList p = (*L)->next, q; /* p指向头结点 */
int j = 0;
if (i <= 0 || i > ListLength_CL(*L)) /* 第i个元素不存在 */
return ERROR;
while (j < i - 1) /* 寻找第i-1个结点 */
{
p = p->next;
j++;
}
q = p->next; /* q指向待删除结点 */
p->next = q->next;
*e = q->data;
if (*L == q) /* 删除的是表尾元素 */
*L = p;
free(q); /* 释放待删除结点 */
return OK;
}
/**
* [4]返回表L的前驱
* @param L
* @param cur_e
* @param pre_e
* @return
*/
Status LinkListclass::PriorElem_CL(LoopLinkList L, ElemType cur_e, ElemType *pre_e) { /* 初始条件：线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */
/* 否则操作失败，pre_e无定义 */
LoopLinkList q, p = L->next->next; /* p指向第一个结点 */
q = p->next;
while (q != L->next) /* p没到表尾 */
{
if (q->data == cur_e) {
*pre_e = p->data;
return TRUE;
}
p = q;
q = q->next;
}
return FALSE;
}
/**
* [5]返回表L的后继
* @param L
* @param cur_e
* @param next_e
* @return
*/
Status LinkListclass::NextElem_CL(LoopLinkList L, ElemType cur_e, ElemType *next_e) { /* 初始条件：线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继， */
/* 否则操作失败，next_e无定义 */
LoopLinkList p = L->next->next; /* p指向第一个结点 */
while (p != L) /* p没到表尾 */
{
if (p->data == cur_e) {
*next_e = p->next->data;
return TRUE;
}
p = p->next;
}
return FALSE;
}
/**
* [6]返回L中数据元素个数
* @param L
* @return
*/
int LinkListclass::ListLength_CL(LoopLinkList L) { /* 初始条件：L已存在。操作结果：返回L中数据元素个数 */
int i = 0;
LoopLinkList p = L->next; /* p指向头结点 */
while (p != L) /* 没到表尾 */
{
i++;
p = p->next;
}
return i;
}
/**
* [7]返回L中数据元素的位序
* @param L
* @param e
* @param compare
* @return
*/
int LinkListclass::LocateElem_CL(LoopLinkList L, ElemType e,
Status(*compare)(ElemType, ElemType)) { /* 初始条件：线性表L已存在，compare()是数据元素判定函数 */
/* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int i = 0;
LoopLinkList p = L->next->next; /* p指向第一个结点 */
while (p != L->next) {
i++;
if (compare(p->data, e)) /* 满足关系 */
return i;
p = p->next;
}
return 0;
}
/**
* [8]列表遍历
* @param L
* @param vi
* @return
*/
Status LinkListclass::ListTraverse_CL(LoopLinkList L, void(*vi)(ElemType)) {
/* 初始条件:L已存在。操作结果:依次对L的每个数据元素调用函数vi()。
* 一旦vi()失败,则操作失败 */
LoopLinkList p = L->next->next;
while (p != L->next) {
vi(p->data);
p = p->next;
}
printf("\n");
return OK;
}
/**
* [9]两个元素比较
* @param c1
* @param c2
* @return
*/
Status LinkListclass::compare(ElemType c1, ElemType c2) {
if (c1 == c2)
return TRUE;
else
return FALSE;
}
/**
* [10]访问元素并打印
* @param c
*/
void LinkListclass::visit(ElemType c) {
printf("%d ", c);
}
/**
* [11]获取元素值
* @param L
* @param i
* @param e
* @return
*/
Status LinkListclass::GetElem_CL(LoopLinkList L, int i, ElemType *e) { /* 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
int j = 1; /* 初始化,j为计数器 */
LoopLinkList p = L->next->next; /* p指向第一个结点 */
if (i <= 0 || i > ListLength_CL(L)) /* 第i个元素不存在 */
return ERROR;
while (j < i) { /* 顺指针向后查找,直到p指向第i个元素 */
p = p->next;
j++;
}
*e = p->data; /* 取第i个元素 */
return OK;
}
/**
* [12]判断是否为空
* @param L
* @return
*/
Status LinkListclass::ListEmpty_CL(LoopLinkList L) { /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
if (L->next == L) /* 空 */
return TRUE;
else
return FALSE;
}
/**
* [13]重置L为空表
* @param L
* @return
*/
Status LinkListclass::ClearList_CL(LoopLinkList *L) /* 改变L */
{ /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */
LoopLinkList p, q;
*L = (*L)->next; /* L指向头结点 */
p = (*L)->next; /* p指向第一个结点 */
while (p != *L) /* 没到表尾 */
{
q = p->next;
free(p);
p = q;
}
(*L)->next = *L; /* 头结点指针域指向自身 */
return OK;
}
/**
* [14]销毁线性表L
* @param L
* @return
*/
Status LinkListclass::DestroyList_CL(LoopLinkList *L) { /* 操作结果：销毁线性表L */
LoopLinkList q, p = (*L)->next; /* p指向头结点 */
while (p != *L) /* 没到表尾 */
{
q = p->next;
free(p);
p = q;
}
free(*L);
*L = NULL;
return OK;
}
/**
* [15]仅设表尾指针循环链表的合并
* @param La
* @param Lb
*/
void LinkListclass::MergeList_CL(LoopLinkList *La, LoopLinkList Lb) {
LoopLinkList p = Lb->next;
Lb->next = (*La)->next;
(*La)->next = p->next;
free(p);
*La = Lb;
}
//----------------------------[双向链表DuLinkList基本操作]-----------------------------
/**
* [1]初始化双向链表
* @param L
* @return
*/
Status LinkListclass::InitDuList(DuLinkList *L) { /* 产生空的双向循环链表L */
*L = (DuLinkList) malloc(sizeof(DuLNode));
if (*L) {
(*L)->next = (*L)->prior = *L;
return OK;
} else
return ERROR;
}
/**
* [2]求双向链表表长
* @param L
* @return
*/
int LinkListclass::DuListLength(DuLinkList L)
{ /* 初始条件：L已存在。操作结果：返回L中数据元素个数 */
int i=0;
DuLinkList p=L->next; /* p指向第一个结点 */
while(p!=L) /* p没到表头 */
{
i++;
p=p->next;
}
return i;
}
/**
* [3]在双向链表L中返回第i个元素的位置指针
* @param L
* @param i
* @return
*/
DuLinkList LinkListclass::GetElemP(DuLinkList L,int i) /* 另加 */
{
int j;
DuLinkList p=L;
for(j=1;j<=i;j++)
p=p->next;
return p;
}
/**
* [4]在带头结点的双链循环线性表L中第i个位置之前插入元素e,
* i的合法值为1≤i≤表长+1
* @param L
* @param i
* @param e
* @return
*/
Status LinkListclass::DuListInsert(DuLinkList L,int i,ElemType e)
{
DuLinkList p,s;
if(i<1||i>DuListLength(L)+1) /* i值不合法 */
return ERROR;
p=GetElemP(L,i-1); /* 在L中确定第i-1个元素的位置指针p */
if(!p) /* p=NULL,即第i-1个元素不存在 */
return ERROR;
s=(DuLinkList)malloc(sizeof(DuLNode));
if(!s)
return ERROR;
s->data=e; /* 在第i-1个元素之后插入 */
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
return OK;
}
/**
* [5]双向链表正向遍历访问元素
* @param L
* @param visit
*/
void LinkListclass::DuListTraverse(DuLinkList L,void(*visit)(ElemType))
{ /* 由双链循环线性表L的头结点出发,正序对每个数据元素调用函数visit() */
DuLinkList p=L->next; /* p指向头结点 */
while(p!=L)
{
visit(p->data);
p=p->next;
}
printf("\n");
}
/**
* [6]双向链表正向遍历访问元素
* @param L
* @param visit
*/
void LinkListclass::ListTraverseBack(DuLinkList L,void(*visit)(ElemType))
{ /* 由双链循环线性表L的头结点出发,逆序对每个数据元素调用函数visit()。另加 */
DuLinkList p=L->prior; /* p指向尾结点 */
while(p!=L)
{
visit(p->data);
p=p->prior;
}
printf("\n");
}
/**
* [7]双向链表访问元素并打印
* @param c
*/
void LinkListclass::vd(ElemType c) /* ListTraverse()调用的函数(类型一致) */
{
printf("%d ",c);
}
/**
* [8]双向链表元素的删除
* @param L
* @param i
* @param e
* @return
*/
Status LinkListclass::DuListDelete(DuLinkList L,int i,ElemType *e)
{ /* 删除带头结点的双链循环线性表L的第i个元素,i的合法值为1≤i≤表长+1 */
DuLinkList p;
if(i<1||i>DuListLength(L)) /* i值不合法 */
return ERROR;
p=GetElemP(L,i); /* 在L中确定第i个元素的位置指针p */
if(!p) /* p=NULL,即第i个元素不存在 */
return ERROR;
*e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return OK;
}
/**
* [9]双向链表重置为空表
* @param L
* @return
*/
Status LinkListclass::ClearDuList(DuLinkList L) /* 不改变L */
{ /* 初始条件：L已存在。操作结果：将L重置为空表 */
DuLinkList q,p=L->next; /* p指向第一个结点 */
while(p!=L) /* p没到表头 */
{
q=p->next;
free(p);
p=q;
}
L->next=L->prior=L; /* 头结点的两个指针域均指向自身 */
return OK;
}
/**
* [10]双向链表判空
* @param L
* @return
*/
Status LinkListclass::DuListEmpty(DuLinkList L)
{ /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
if(L->next==L&&L->prior==L)
return TRUE;
else
return FALSE;
}
/**
* [11]双向链表元素赋值
* 当第i个元素存在时,其值赋给e并返回OK,
* 否则返回ERROR
* @param L
* @param i
* @param e
* @return
*/
Status LinkListclass::GetDuElem(DuLinkList L,int i,ElemType *e)
{ /* 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
int j=1; /* j为计数器 */
DuLinkList p=L->next; /* p指向第一个结点 */
while(p!=L&&j<i) /* 顺指针向后查找,直到p指向第i个元素或p指向头结点 */
{
p=p->next;
j++;
}
if(p==L||j>i) /* 第i个元素不存在 */
return ERROR;
*e=p->data; /* 取第i个元素 */
return OK;
}
LinkList.h
//
// Created by leoxae on 19-11-5.
//
#ifndef ALGORITHMSLIBRARY_LINKLIST_H
#define ALGORITHMSLIBRARY_LINKLIST_H
#include "stdio.h"
#include "string"
#include "iostream"
using namespace std;
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef int ElemType;
//单链表数据结构定义
typedef char datatype;
typedef struct Node{
datatype data;
struct Node *next;
} ListNode;
typedef ListNode *LinkList;
//单循环链表数据结构定义
struct LNode {
ElemType data;
struct LNode *next;
};
typedef struct LNode *LoopLinkList; /* 另一种定义LinkList的方法 */
//双向链表数据结构定义
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior,*next;
} DuLNode,*DuLinkList;
class LinkListclass{
public:
//-------------------[单链表LinkList基本操作]-------------------
//[1]头插法建立单链表
LinkList HeadInsertCreateList(void);
//[2]尾插法建立单链表
LinkList TailInsertCreateList();
//[3]按序号查找单链表
ListNode * getnode(LinkList head, int i);
//[4]按值查找单链表
ListNode *locatenode(LinkList head, char key);
//[5]插入元素e到表L
void insertnode(LinkList head, char x, int i);
//[6]从表L中删除元素e
void deletelist(LinkList head, int i);
//[7]合并两个链表
LinkList concatenate(LinkList list1, LinkList list2);
//-------------------[单循环链表LoopList基本操作]-------------------
//[1]初始化,构造空表L
Status InitList_CL(LoopLinkList *L);
//[2]插入元素
Status ListInsert_CL(LoopLinkList *L, int i, ElemType e);
//[3]删除元素
Status ListDelete_CL(LoopLinkList *L, int i, ElemType *e);
//[4]返回表L的前驱
Status PriorElem_CL(LoopLinkList L, ElemType cur_e, ElemType *pre_e);
//[5]返回表L的后继
Status NextElem_CL(LoopLinkList L, ElemType cur_e, ElemType *next_e);
//[6]求表长度
int ListLength_CL(LoopLinkList L);
//[7]返回L中数据元素的位序
int LocateElem_CL(LoopLinkList L, ElemType e, Status(*compare)(ElemType, ElemType));
//[8]列表遍历
Status ListTraverse_CL(LoopLinkList L, void(*vi)(ElemType));
//[9]比较元素大小
static Status compare(ElemType c1, ElemType c2);
//[10]访问元素并打印
static void visit(ElemType c);
//[11]获取元素值
Status GetElem_CL(LoopLinkList L,int i,ElemType *e);
//[12]判断是否为空
static Status ListEmpty_CL(LoopLinkList L);
//[13]重置为空表
Status ClearList_CL(LoopLinkList *L);
//[14]销毁表
Status DestroyList_CL(LoopLinkList *L);
//[15]仅设表尾指针循环链表的合并
void MergeList_CL(LoopLinkList *La, LoopLinkList Lb);
//-------------------[双向链表DuLinkList基本操作]-------------------
//[1]初始化双向链表
Status InitDuList(DuLinkList *L);
//[2]求双向链表表长
int DuListLength(DuLinkList L);
//[3]在双向链表L中返回第i个元素的位置指针
DuLinkList GetElemP(DuLinkList L, int i);
//[4]双向链表插入元素
Status DuListInsert(DuLinkList L, int i, ElemType e);
//[5]双向链表正向遍历访问元素
void DuListTraverse(DuLinkList L, void (*visit)(ElemType));
//[6]双向链表逆向遍历访问元素
void ListTraverseBack(DuLinkList L, void (*visit)(ElemType));
//[7]双向链表访问元素并打印
static void vd(ElemType c);
//[8]双向链表元素的删除
Status DuListDelete(DuLinkList L, int i, ElemType *e);
//[9]双向链表重置为空表
Status ClearDuList(DuLinkList L);
//[10]双向链表判空
Status DuListEmpty(DuLinkList L);
//[11]双向链表元素赋值
Status GetDuElem(DuLinkList L, int i, ElemType *e);
};
#endif //ALGORITHMSLIBRARY_LINKLIST_H
LinkListManager.cpp //链表相关实现函数的调用
//
// Created by leoxae on 19-11-6.
//
#include "LinkListManager.h"
//------------------[单链表的操作]------------------
/**
* 头插法建立单链表
*/
void LinkListManager::headinsertcreateList() {
LinkListclass List;
cout << "请输入元素建立单链表:" << endl;
LinkList newlist = List.HeadInsertCreateList();
do {
printf("%c\n", newlist->data);
newlist = newlist->next;
} while (newlist != NULL);
printf("\n");
}
/**
* 尾插法建立单链表
*/
void LinkListManager::tailinsertcreateList() {
LinkListclass List;
cout << "请输入元素建立单链表:" << endl;
LinkList newlist = List.TailInsertCreateList();
do {
printf("%c", newlist->data);
newlist = newlist->next;
} while (newlist != NULL);
printf("\n");
}
/**
* 按序号查找单链表
*/
void LinkListManager::numGetElem() {
LinkListclass List;
LinkList list;
ListNode *node;
int i = 0;
cout << "请输入元素建立单链表:" << endl;
list = List.TailInsertCreateList();
node = List.getnode(list, i);
}
/**
* 按值查找单链表
*/
void LinkListManager::keyGetElem() {
LinkListclass List;
LinkList list;
ListNode *node;
char key = 'c';
cout << "请输入元素建立单链表:" << endl;
list = List.TailInsertCreateList();
node = List.locatenode(list, key);
}
/**
* 插入元素e到表L
*/
void LinkListManager::insertElem() {
LinkListclass List;
LinkList list;
int i = 1;
char x = 'c';
cout << "请输入元素建立单链表:" << endl;
list = List.TailInsertCreateList();
List.insertnode(list, x, i);
do {
printf("%c", list->data);
list = list->next;
} while (list != NULL);
printf("\n");
}
/**
* 从表L中删除元素e
*/
void LinkListManager::deleteElem() {
LinkListclass List;
LinkList list;
int i = 1;
char x = 'c';
cout << "请输入元素建立单链表:" << endl;
list = List.TailInsertCreateList();
List.deletelist(list, i);
do {
printf("%c", list->data);
list = list->next;
} while (list != NULL);
printf("\n");
}
/**
* 合并两个链表
*/
void LinkListManager::mergeList() {
LinkListclass List;
LinkList list1, list2, list3;
cout << "请输入元素分别建立单链表1和单链表2:" << endl;
list1 = List.TailInsertCreateList();
list2 = List.TailInsertCreateList();
list3 = List.concatenate(list1, list2);
do {
printf("%c", list3->data);
list3 = list3->next;
} while (list3 != NULL);
printf("\n");
}
//------------------[单循环链表的操作]------------------
/**
* 删除单循环链表元素
*/
void LinkListManager::DeleteSingleLoopLinkedList() {
LinkListclass List;
LoopLinkList L;
ElemType e;
int j;
Status i;
i = List.InitList_CL(&L); /* 初始化单循环链表L */
printf("依次在单循环链表中插入3,5\n");
List.ListInsert_CL(&L, 1, 3); /* 在L中依次插入3,5 */
List.ListInsert_CL(&L, 2, 5);
j = List.LocateElem_CL(L, 5, LinkListclass::compare);
if (j)
printf("L的第%d个元素为5。\n", j);
else
printf("不存在值为5的元素\n");
i = List.ListDelete_CL(&L, 2, &e);
printf("删除L的第2个元素：\n");
if (i) {
printf("删除的元素值为%d,现在L中的数据元素依次为：", e);
List.ListTraverse_CL(L, LinkListclass::visit);
} else
printf("删除不成功！\n");
}
/**
* 销毁和清空表
*/
void LinkListManager::DestroyLinkList() {
LinkListclass List;
LoopLinkList L;
ElemType e;
int j;
Status i;
i = List.InitList_CL(&L); /* 初始化单循环链表L */
printf("依次在单循环链表中插入3,5\n");
List.ListInsert_CL(&L, 1, 3); /* 在L中依次插入3,5 */
List.ListInsert_CL(&L, 2, 5);
printf("清空L：%d(1: 成功)\n", List.ClearList_CL(&L));
printf("清空L后，L是否空：%d(1:空 0:否)\n", LinkListclass::ListEmpty_CL(L));
printf("销毁L：%d(1: 成功)\n", List.DestroyList_CL(&L));
}
/**
* 查询元素的前驱和后继
*/
void LinkListManager::GetNextandPrior() {
LinkListclass List;
LoopLinkList L;
ElemType e;
int j;
Status i;
i = List.InitList_CL(&L); /* 初始化单循环链表L */
printf("初始化单循环链表L i=%d (1:初始化成功)\n", i);
i = List.ListEmpty_CL(L);
printf("L是否空 i=%d(1:空 0:否)\n", i);
List.ListInsert_CL(&L, 1, 3); /* 在L中依次插入3,5 */
List.ListInsert_CL(&L, 2, 5);
printf("依次插入元素3和5\n");
List.PriorElem_CL(L, 5, &e); /* 求元素5的前驱 */
printf("5前面的元素的值为%d。\n", e);
List.NextElem_CL(L, 3, &e); /* 求元素3的后继 */
printf("3后面的元素的值为%d。\n", e);
}
/**
* 初始化单循环链表
*/
void LinkListManager::InitLoopList() {
LinkListclass List;
LoopLinkList L;
ElemType e;
int j;
Status i;
i = List.InitList_CL(&L); /* 初始化单循环链表L */
printf("初始化单循环链表L i=%d (1:初始化成功)\n", i);
i = List.ListEmpty_CL(L);
printf("L是否空 i=%d(1:空 0:否)\n", i);
List.ListInsert_CL(&L, 1, 3); /* 在L中依次插入3,5 */
List.ListInsert_CL(&L, 2, 5);
i = List.GetElem_CL(L, 1, &e);
j = List.ListLength_CL(L);
printf("L中数据元素个数=%d,第1个元素的值为%d。\n", j, e);
printf("L中的数据元素依次为：");
List.ListTraverse_CL(L, LinkListclass::visit);
}
/**
* 仅设表尾指针循环链表的合并
*/
void LinkListManager::mergeLoopLinklist() {
LinkListclass List;
int n = 5, i;
LoopLinkList La, Lb;
List.InitList_CL(&La);
for (i = 1; i <= n; i++)
List.ListInsert_CL(&La, i, i);
printf("La="); /* 输出链表La的内容 */
List.ListTraverse_CL(La, LinkListclass::visit);
List.InitList_CL(&Lb);
for (i = 1; i <= n; i++)
List.ListInsert_CL(&Lb, 1, i * 2);
printf("Lb="); /* 输出链表Lb的内容 */
List.ListTraverse_CL(Lb, LinkListclass::visit);
List.MergeList_CL(&La, Lb);
printf("La+Lb="); /* 输出合并后的链表的内容 */
List.ListTraverse_CL(La, LinkListclass::visit);
}
//-------------------[双向链表DuLinkList基本操作]-------------------
/**
* 正序输出双向链表
*/
void LinkListManager::outDuLinkList() {
LinkListclass List;
DuLinkList L;
int i;
List.InitDuList(&L);
for (i = 1; i <= 5; i++)
List.DuListInsert(L, i, i); /* 在第i个结点之前插入i */
printf("正序输出链表：");
List.DuListTraverse(L, LinkListclass::vd); /* 正序输出 */
}
/**
* 逆向输出双向链表
*/
void LinkListManager::reverseoutDuLinkList() {
LinkListclass List;
DuLinkList L;
int i;
List.InitDuList(&L);
for (i = 1; i <= 5; i++)
List.DuListInsert(L, i, i); /* 在第i个结点之前插入i */
printf("逆序输出链表：");
List.ListTraverseBack(L, LinkListclass::vd); /* 逆序输出 */
}
/**
* 双向链表删除元素
*/
void LinkListManager::deleteDuLinkList() {
LinkListclass List;
DuLinkList L;
int i, n = 2;
ElemType e;
List.InitDuList(&L);
printf("初始化链表依次输入1，2，3，4，5\n");
for (i = 1; i <= 5; i++)
List.DuListInsert(L, i, i); /* 在第i个结点之前插入i */
List.DuListDelete(L, n, &e); /* 删除并释放第n个结点 */
printf("删除第%d个结点，值为%d，其余结点为：", n, e);
List.DuListTraverse(L, LinkListclass::vd); /* 正序输出 */
}
/**
* 返回双向链表的长度(即元素个数)
*/
void LinkListManager::getDuLinkListLength() {
LinkListclass List;
DuLinkList L;
int i, n = 2;
ElemType e;
List.InitDuList(&L);
printf("初始化链表依次输入1，2，3，4，5\n");
for (i = 1; i <= 5; i++)
List.DuListInsert(L, i, i); /* 在第i个结点之前插入i */
printf("链表的元素个数为%d\n", List.DuListLength(L));
}
/**
* 双向链表判空
*/
void LinkListManager::judgeDuListEmpty() {
LinkListclass List;
DuLinkList L;
int i, n = 2;
ElemType e;
List.InitDuList(&L);
printf("初始化链表依次输入1，2，3，4，5\n");
for (i = 1; i <= 5; i++)
List.DuListInsert(L, i, i); /* 在第i个结点之前插入i */
printf("链表是否空：%d(1:是 0:否)\n", List.DuListEmpty(L));
List.ClearDuList(L); /* 清空链表 */
printf("清空后，链表是否空：%d(1:是 0:否)\n", List.DuListEmpty(L));
}
/**
* 双向链表元素值的查询
*/
void LinkListManager::GetDuElem() {
LinkListclass List;
DuLinkList L;
int i, n, j;
ElemType e;
List.InitDuList(&L);
printf("初始化链表依次输入1，2，3，4，5\n");
for (i = 1; i <= 5; i++)
List.DuListInsert(L, i, i); /* 在第i个结点之前插入i */
n = 3;
j = List.GetDuElem(L, n, &e); /* 将链表的第n个元素赋值给e */
if (j)
printf("链表的第%d个元素值为%d\n", n, e);
else
printf("不存在第%d个元素\n", n);
}
LinkListManager.h
//
// Created by leoxae on 19-11-6.
//
#ifndef ALGORITHMSLIBRARY_LINKLISTMANAGER_H
#define ALGORITHMSLIBRARY_LINKLISTMANAGER_H
#include "LinkList.h"
class LinkListManager {
public:
//------------------[单链表的操作]------------------
//头插法建立单链表
void headinsertcreateList();
//尾插法建立单链表
void tailinsertcreateList();
//按序号查找单链表
void numGetElem();
//按值查找单链表
void keyGetElem();
//插入元素e到表L
void insertElem();
//从表L中删除元素e
void deleteElem();
//合并两个链表
//------------------[单循环链表的操作]------------------
void mergeList();
//删除单循环链表元素
void DeleteSingleLoopLinkedList();
//销毁和清空表
void DestroyLinkList();
//查询元素的前驱和后继
void GetNextandPrior();
//初始化单循环链表
void InitLoopList();
//仅设表尾指针循环链表的合并
void mergeLoopLinklist();
//-------------------[双向链表DuLinkList基本操作]-------------------
//正序输出双向链表
void outDuLinkList();
//逆向输出双向链表
void reverseoutDuLinkList();
//双向链表删除元素
void deleteDuLinkList();
//返回双向链表的长度(即元素个数)
void getDuLinkListLength();
//双向链表判空
void judgeDuListEmpty();
//双向链表元素值的查询
void GetDuElem();
};
#endif //ALGORITHMSLIBRARY_LINKLISTMANAGER_H
main.cpp
#include "globals.h" //全局变量
#include "c++/DataStructure/LinkList.h" //链表相关
#include "c++/DataStructure/LinkListManager.h"//链表相关函数调用
#include "c++/DataStructure/BTree.h"//树相关
int main() {
LinkListManager Linkm;
//------------------[单链表LinkList的操作]------------------
/* Linkm.headinsertcreateList();//头插法建立单链表
Linkm.tailinsertcreateList();//尾插法建立单链表
Linkm.numGetElem();//按序号查找单链表
Linkm.keyGetElem();//按值查找单链表
Linkm.insertElem();//插入元素e到表L
Linkm.deleteElem();//从表L中删除元素e
Linkm.mergeList();//合并两个链表*/
//------------------[单循环链表的操作]------------------
/* Linkm.DeleteSingleLoopLinkedList();//删除单循环链表的元素
Linkm.DestroyLinkList();//销毁和删除表L
Linkm.GetNextandPrior();//查询元素的前驱和后继
Linkm.InitLoopList();//初始化单循环链表
Linkm.mergeLoopLinklist();//仅设表尾指针循环链表的合并*/
//-------------------[双向链表DuLinkList基本操作]-------------------
/*Linkm.outDuLinkList();//正序输出双向链表
Linkm.reverseoutDuLinkList();//逆向输出双向链表
Linkm.deleteDuLinkList();//双向链表删除元素
Linkm.getDuLinkListLength();//返回双向链表的长度
Linkm.judgeDuListEmpty();//双向链表判空
Linkm.GetDuElem();//双向链表元素值的查询*/