单链表

本文主要是介绍单链表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

不带头节点

.h文件部分

#ifndef LIST_H
#define LIST_H

#include <stdbool.h>
typedef int Elemtype;
typedef int Rank;
typedef struct ListNode
{
	Elemtype data;
	struct ListNode *next;
}ListNode, *List;

void Init(List *L);
bool Empty(List L);
int Length(List L);
ListNode *GetElem(List L, Rank i);
ListNode *LocateElem(List L, Elemtype e);
ListNode *Insert(List *L, int i, Elemtype e);
ListNode *InsertAsSucc(ListNode *p, Elemtype e);
ListNode *InsertAsPred(ListNode *p, Elemtype e);
ListNode *InsertAsFirst(List *L, Elemtype e);
ListNode *InsertAsLast(List *L, Elemtype e);
Elemtype Delete(ListNode *p);
Elemtype DeleteByRank(List *L, Rank i);
void Traverse(List L, void (*Visit)(Elemtype e));
void Clear(List *L);
void Destroy(List *L);
void Reverse(List *L);

#endif

.c文件部分

#include <stdlib.h>
#include <assert.h>

static ListNode *NewNode()
{
	ListNode *new_node = (ListNode *)malloc(sizeof(ListNode));
	assert(new_node);
	return new_node;
}

void Init(List *L)
{
	*L = NULL;
}

bool Empty(List L)
{
	return !L;
}

int Length(List L)
{
	int len = 0; ListNode *p = L;
	while (p)
	{
		p = p->next;
		len++;
	}
	return len;
}

ListNode *GetElem(List L, Rank i)
{
	int j = 0; ListNode *p = L;
	while (j < i && p)
	{
		p = p->next;
		j++;
	}
	if (j == i)
		return p;
	else
		return NULL;
}

ListNode *LocateElem(List L, Elemtype e)
{
	ListNode *p = L;
	while (p && p->data != e)
		p = p->next;
	return p;
}

ListNode *Insert(List *L, int i, Elemtype e)
{
	if (i < 0)
		exit(EXIT_FAILURE);
	else if (i == 0)
	{
		ListNode *new_node = NewNode();
		new_node->data = e;
		new_node->next = *L;
		*L = new_node;
		return new_node;
	}
	else
	{
		ListNode *p = GetElem(*L, i - 1);
		assert(p);
		ListNode *new_node = NewNode();
		new_node->data = e;
		new_node->next = p->next;
		p->next = new_node;
		return new_node;
	}
}

ListNode *InsertAsSucc(ListNode *p, Elemtype e)
{
	assert(p);
	ListNode *new_node = NewNode();
	new_node->data = e;
	new_node->next = p->next;
	p->next = new_node;
	return new_node;
}

ListNode *InsertAsPred(ListNode *p, Elemtype e)
{
	ListNode *newNode = InsertAsSucc(p, e);
	newNode->data = p->data;
	p->data = e;
	return newNode;
}

ListNode *InsertAsFirst(List *L, Elemtype e)
{
	///* 方法一 */
	//InsertAsPred(*L, e);

	/* 方法二 */
	ListNode *new_node = NewNode();
	new_node->data = e;
	new_node->next = *L;
	*L = new_node;
	return new_node;
}

ListNode *InsertAsLast(List *L, Elemtype e)
{
	ListNode *new_node = NewNode();
	new_node->data = e;
	if (!*L)
		*L = new_node;
	else
	{
		ListNode *p = *L;
		while (p->next)
			p = p->next;
		p->next = new_node;
	}
	new_node->next = NULL;
	return new_node;
}

Elemtype Delete(ListNode *p)
{
	assert(p);
	ListNode *q = p->next; Elemtype e = p->data;
	p->data = q->data;
	p->next = q->next;
	free(q);
	return e;
}

Elemtype DeleteByRank(List *L, Rank i)
{
	if (i < 0)
		exit(EXIT_FAILURE);
	else if (i == 0)
	{
		if (!*L)
			exit(EXIT_FAILURE);
		ListNode *p = *L; Elemtype e = (*L)->data;
		*L = (*L)->next;
		free(p);
		return e;
	}
	else
	{
		ListNode *p = GetElem(*L, i-1);
		assert(p); assert(p->next);
		ListNode *q = p->next; Elemtype e = (*L)->next->data;
		p->next = q->next;
		free(q);
		return e;
	}
}

void Traverse(List L, void (*Visit)(Elemtype e))
{
	ListNode *p = L;
	while (p)
	{
		Visit(p->data);
		p = p->next;
	}
}

void Clear(List *L)
{
	ListNode *p = *L;
	while (p)
	{
		*L = (*L)->next;
		free(p);
		p = *L;
	}
}

void Destroy(List *L)
{
	Clear(L);
	free(*L);
}

void Reverse(List *L)
{
	ListNode *p = *L, *q;
	*L = NULL;
	while (p)
	{
		q = p->next;
		p->next = *L;
		*L = p;
		p = q;
	}
}

这篇关于单链表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！