《数据结构》第五版：上机题目之单链表的增删改查

循环单链表：

头文件：“clinklist.h”

#pragma once
#include<stdio.h>
#include<malloc.h>
typedef int Elemtype;
typedef struct LNode
{
	Elemtype data;
	struct LNode* next;
}LinkNode;
void InitList(LinkNode *&L)
{
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = L;
}
void CreatListF(LinkNode *&L,Elemtype a[],int n)
{
	LinkNode* s;
	int i;
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = L;
	for (i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = a[i];
		s->next = L->next;
		L->next = s;
	}
	s = L->next;
	while (s->next!=NULL)
	{
		s = s->next;
	}
	s->next = L;
}
void CreatListR(LinkNode *&L,Elemtype a[],int n)
{
	LinkNode* s,*r;
	int i;
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = L;
	r = L;
	for (i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = a[i];
		r->next = s;
		r = s;
	}
	r->next = L;
}
void DestoryList(LinkNode *&L)
{
	LinkNode* pre=L,*p=pre->next;
	while(p!=L)
	{
		free(pre);
		pre = p;
		p = p->next;
	}
	free(pre);
}
bool ListEmpty(LinkNode *L)
{
	return(L->next == L);
}
int ListLength(LinkNode *L)
{
	LinkNode* p = L;
	int n;
	while (L->next != L)
	{
		p = p->next;
		n++;
	}
	return n;
}
void DispList(LinkNode *L)
{
	LinkNode* p = L->next;
	while (p->next != L)
	{
		printf("%c", p->data);
		printf("\n");
	}
}
bool GetElem(LinkNode* L,int i,Elemtype &e)
{
	LinkNode *p = L->next;
	int j = 1;
	if (i <= 0 || L->next == L)
		return false;
	if (i == 1)
	{
		e = L->next->data;
		return true;
	}
	else
	{
		while (j <= i - 1 && p != L)
		{
			j++;
			p = p->next;
		}
		if (p == L)
			return false;
		else
		{
			e = p->data;
			return true;
		}
	}
}
bool LocateElem(LinkNode *L,Elemtype e)
{
	int j=1;
	LinkNode * p=L->next;
	while (p != L && p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p == L)
		return 0;
	else
		return j;
}
bool ListInsert(LinkNode *&L,int i,Elemtype e)
{  
	int j = 1;
	LinkNode*p=L,* s;
	if (i < 0) 
		return false;
	if (p->next == L || i == 1)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = e;
		s->next = p->next;
		p->next = s;
		return true;
	}
	else
	{
		p = L->next;
		while (j <=i - 2 && p != L)                  //找第i-1个节点
		{
			j++;
			p = p->next;
		}
		if (p == L)
			return false;
		else
		{
			s = (LinkNode*)malloc(sizeof(LinkNode));
			s->data = e;
			s->next = p->next;
			p->next = s;
			return true;
		}
	}
	
}
bool ListDelete(LinkNode *&L,int i,Elemtype &e)      //删除第i个节点
{
	int j = 1;
	LinkNode* p = L, * q;
	if (i < 0)
		return false;
	if (i == 1)
	{
		q = L ->next;
		e = q->data;
		L->next = q->next;
		free(q);
		return true;
	}
	else
	{
		while (j <= i - 2 && p != L)
		{
			j++;
			p = p->next;
		}
		if (p == NULL)
			return false;
		else
		{
			q = p->next;
			e = q->data;
			p->next = q->next;
			free(q);
			return true;
		}
	}
}

主函数：

//#include"clinklist.h"
//#pragma once
#include<stdio.h>
#include<malloc.h>
typedef int Elemtype;
typedef struct LNode
{
	Elemtype data;
	struct LNode* next;
}LinkNode;
void InitList(LinkNode*& L)
{
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = L;
}
void CreatListF(LinkNode*& L, Elemtype a[], int n)
{
	LinkNode* s; int i;
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = L;
	for (i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = a[i];
		s->next = L->next;
		L->next = s;
	}
	s = L->next;
	while (s->next != NULL)
	{
		s = s->next;
	}
	s->next = L;
}
void CreatListR(LinkNode*& L, Elemtype a[], int n)
{
	LinkNode* s, * r;
	int i;
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = L;
	r = L;
	for (i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = a[i];
		r->next = s;
		r = s;
	}
	r->next = L;
}
void DestoryList(LinkNode*& L)
{
	LinkNode* pre = L, * p = pre->next;
	while (p != L)
	{
		free(pre);
		pre = p;
		p = p->next;
	}
	free(pre);
}
bool ListEmpty(LinkNode* L)
{
	return(L->next == L);
}
int ListLength(LinkNode* L)
{
	LinkNode* p = L;
	int n=0;
	while (p->next != L)
	{
		p = p->next;
		n++;
	}
	return n;
}
void DispList(LinkNode* L)
{
	LinkNode* p = L->next;
	while (p!= L)
	{
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}
bool GetElem(LinkNode* L, int i, Elemtype& e)
{
	LinkNode* p = L->next;
	int j = 1;
	if (i <= 0 || L->next == L)
		return false;
	if (i == 1)
	{
		e = L->next->data;
		return true;
	}
	else
	{
		while (j <= i - 1 && p != L)
		{
			j++;
			p = p->next;
		}
		if (p == L)
			return false;
		else
		{
			e = p->data;
			return true;
		}
	}
}
int LocateElem(LinkNode* L, Elemtype e)
{
	int j = 1;
	LinkNode* p = L->next;
	while (p != L && p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p == L)
		return 0;
	else
		return j;
}
bool ListInsert(LinkNode*& L, int i, Elemtype e)
{
	int j = 1;
	LinkNode* p = L, * s;
	if (i < 0)
		return false;
	if (p->next == L || i == 1)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = e;
		s->next = p->next;
		p->next = s;
		return true;
	}
	else
	{
		p = L->next;
		while (j <= i - 2 && p != L)                  //找第i-1个节点
		{
			j++;
			p = p->next;
		}
		if (p == L)
			return false;
		else
		{
			s = (LinkNode*)malloc(sizeof(LinkNode));
			s->data = e;
			s->next = p->next;
			p->next = s;
			return true;
		}
	}

}
bool ListDelete(LinkNode*& L, int i, Elemtype& e)      //删除第i个节点
{
	int j = 1;
	LinkNode* p = L, * q;
	if (i < 0||L->next==L)
		return false;
	if (i == 1)
	{
		q = L->next;
		e = q->data;
		L->next = q->next;
		free(q);
		return true;
	}
	else
	{
		while (j <= i - 2 && p != L)
		{
			j++;
			p = p->next;
		}
		if (p == NULL)
			return false;
		else
		{
			q = p->next;
			e = q->data;
			p->next = q->next;
			free(q);
			return true;
		}
	}
}

int main()
{
	LinkNode* h;
	Elemtype e;
	printf("循环单链表的基本算法如下：\n");
	printf("   (1)初始化循环单链表h\n");
	InitList(h);
	printf("  (2)依次采用尾插法插入a、b、c、d、e元素\n");
	ListInsert(h, 1, 'a');
	ListInsert(h, 2, 'b');
	ListInsert(h, 3, 'c');
	ListInsert(h, 4,  'd');
	ListInsert(h, 5, 'e');
	printf("   (3)输出循环单链表h:\n");
	DispList(h);
	printf("   (4)循环单链表的长度是：\n");
	ListLength(h);
	printf("   (5)循环单链表为（空or非空？)%s\n", (ListEmpty(h) ? "空" : " 非空"));
	GetElem(h,3,e);
	printf("  (6)循环单链表的第三个元素%c\n",e);
	printf("  (7)求元素b的位置：%d\n",LocateElem(h,'b'));
	printf("  (8)在第四个元素的位置上插入f元素：\n");
	ListInsert(h, 4, 'f');
	printf("   (9)输出循环单链表h:\n");
	DispList(h);
	printf("    (10)删除h第三个元素；\n");
	ListDelete(h,3,e);
	printf("   (11)输出循环单链表h:\n");
	DispList(h);
	printf("   (12)释放循环单链表h；\n");
	DestoryList(h);
	return 1;
}