数据结构学习，单链表

数据结构学习，单链表

目录

预先要引用的头文件以及宏定义

所使用单链表的结构

其基本 *** 作接口

构造一个空的单链表（带头结点）

销毁单链表

将单链表L置为空链表

单链表L为空表时返回TRUE，否则返回FALSE

求单链表的表长

查找。返回单链表L中第一个数据域值为e的结点地址，若不存在则返回NULL

返回p结点的直接后继的指针，若p结点是尾结点则返回NULL

构造元素e的结点，返回指向该结点的指针

在p结点后插入结点q

删除p结点的直接后继结点，用e返回结点值，若p空或指向尾元结点则 *** 作失败

遍历单链表

一些接口的测试

---

预先要引用的头文件以及宏定义

#include
#include

using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int ElemType;
typedef int Status;

所使用单链表的结构

typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode,*linkList;

其基本 *** 作接口

Status InitList_L(linkList& L);				//构造一个空的单链表
Status DestroyList_L(linkList& L);			//销毁单链表
Status ClearList_L(linkList& L);			//将单链表L置为空链表
Status ListEmpty_L(linkList L);				//单链表L为空表时返回TRUE，否则返回FALSE
int ListLength_L(linkList L);				//求单链表的表长
LNode* Search_L(linkList L, ElemType e);	//查找。返回单链表L中第一个数据域值为e的结点地址，若不存在则返回NULL
LNode* NextElem_L(LNode* p);				//返回p结点的直接后继的指针，若p结点是尾结点则返回NULL
LNode* MakeNode_L(ElemType e);				//构造元素e的结点，返回指向该结点的指针
Status InsertAfter_L(LNode* p, LNode* q);	//在p结点后插入结点q
Status DeleteAfter_L(LNode* p, ElemType e);	//删除p结点的直接后继结点，用e返回结点值，若p空或指向尾元结点则 *** 作失败
void ListTraverse_L(linkList L);			//遍历单链表

构造一个空的单链表（带头结点）

Status InitList_L(linkList& L)
{
	L = (LNode*)malloc(sizeof(LNode));
	if (L == NULL)
	{
		return OVERFLOW;
	}
	else
	{
		L->next = NULL;
		return OK;
	}
}

销毁单链表

Status DestroyList_L(linkList& L)
{
	if (L != NULL)
	{
		LNode* p, * q;
		p = L->next;
		free(L);
		while (p != NULL)
		{
			q = p;
			p = p->next;
			free(q);
		}
		return OK;
	}
	else
	{
		return OVERFLOW;
	}
}

将单链表L置为空链表

Status ClearList_L(linkList& L)
{
	if (L != NULL)
	{
		LNode* p, * q;
		p = L->next;
		while (p != NULL)
		{
			q = p;
			p = p->next;
			free(q);
		}
		L->next = NULL;
		return OK;
	}
	else
	{
		return OVERFLOW;
	}
}

单链表L为空表时返回TRUE，否则返回FALSE

Status ListEmpty_L(linkList L)
{
	if (L != NULL)
	{
		if (L->next == NULL)
		{
			return TRUE;
		}
		else
		{
			return ERROR;
		}
	}
	else
	{
		return OVERFLOW;
	}
}

求单链表的表长

int ListLength_L(linkList L)
{
	if (L != NULL)
	{
		LNode* p, * q;
		p = L->next;
		int sum = 0;
		while (p != NULL)
		{
			sum++;
			p = p->next;
		}
		return sum;
	}
	else
	{
		return OVERFLOW;
	}
}

查找。返回单链表L中第一个数据域值为e的结点地址，若不存在则返回NULL

LNode* Search_L(linkList L, ElemType e)
{
	LNode* p;
	if (L == NULL)
	{
		return NULL;
	}
	else
	{
		p = L->next;
		while (p != NULL && p->data != e)
		{
			p = p->next;
		}
		return p;
	}
}

返回p结点的直接后继的指针，若p结点是尾结点则返回NULL

LNode* NextElem_L(LNode* p)
{
	if (p == NULL)
	{
		return NULL;
	}
	else
	{
		return p->next;
	}
}

构造元素e的结点，返回指向该结点的指针

LNode* MakeNode_L(ElemType e)
{
	LNode* p;
	p = (LNode*)malloc(sizeof(LNode));
	if (p != NULL)
	{
		p->data = e;
		p->next = NULL;
	}
	return p;	
}

在p结点后插入结点q

Status InsertAfter_L(LNode* p, LNode* q)
{
	if (p == NULL || q == NULL)
	{
		return ERROR;
	}
	else
	{
		q->next = p->next;
		p->next = q;
		return OK;
	}
}

删除p结点的直接后继结点，用e返回结点值，若p空或指向尾元结点则 *** 作失败

Status DeleteAfter_L(LNode* p, ElemType e)
{
	if (p == NULL || p->next == NULL)
	{
		return ERROR;
	}
	else
	{
		LNode* q;
		q = p->next;
		p->next = q->next;
		e = q->data;
		free(q);
		return OK;
	}
}

遍历单链表

void ListTraverse_L(linkList L)
{
	if (L != NULL)
	{
		LNode* p, * q;
		p = L->next;
		while (p != NULL)
		{
			cout << p->data;
			p = p->next;
		}
	}
}

一些接口的测试

int main()
{
	//单链表
	linkList L;
	InitList_L(L);
	cout << ListEmpty_L(L) << endl;
	LNode* p = L;
	for (int i = 0; i < 4; i++)
	{
		LNode* q;
		q = MakeNode_L(i);
		InsertAfter_L(p, q);
		p = q;
	}
	cout << ListEmpty_L(L) << endl;
	cout << ListLength_L(L) << endl;
	ListTraverse_L(L);
	cout << "n";
	DeleteAfter_L(L, 2);
	ListTraverse_L(L);
	ClearList_L(L);
	DestroyList_L(L);
}