单链表的各类操做

2021年09月15日 阅读数:1
这篇文章主要向大家介绍单链表的各类操做,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
	char data;
	struct Node * next;
}Node, *LinkList;

void meau();
LinkList CreateFromHead();
void ListLength(LinkList L);
void printLink(LinkList L);
LinkList inversePermutation(LinkList L);
LinkList sortAscend(LinkList L);
LinkList MergeLinkList(LinkList LA, LinkList LB);
LinkList MergeCreateLink(LinkList L, char ch);
LinkList MergeDeleteLink(LinkList L, char ch);

int main()
{
	LinkList L,head;
	printf("请输入您要插入的单链表 L 的元素:> ");
	L = CreateFromHead();

	int inter;
	do
	{
		meau();
		printf("请输入您要执行的功能:> ");
		scanf_s("%d", &inter);
		switch (inter)
		{
			case 1:
			{
				 ListLength(L);
				 break;
			}
			case 2:
			{
				 L = inversePermutation(L);
				 printLink(L);
				 break;
			}
			case 3:
			{
				 L = sortAscend(L);
				 printLink(L);
				 break;
			}
			case 4:
			{
				printf("请输入您要插入的单链表 head 的元素:> ");
				getchar();		/*消除回车的影响*/
				head = CreateFromHead();
				L = MergeLinkList(L, head);
				printLink(L);
				break;
			}
			case 5:
			{
				printf("请输入您要插入的元素:>");
				char ch;
				getchar();	  /*消除回车的影响*/
				ch = getchar();
				L = MergeCreateLink(L, ch);
				printLink(L);
				break;
			}
			case 6:
			{
					  printf("请输入您要删除的元素:> ");
					  char ch;
					  getchar();   /*消除回车的影响*/
					  ch = getchar();
					  L = MergeDeleteLink(L, ch);
					  printLink(L);
					  break;
			}
			case 0:
			{
					  printf("感谢使用本系统,欢迎您的下次使用!\n");
					  break;
			}
			default:
			{
					   printf("请输入正确的功能编号!\n");
					   break;
			}
		}
	} while (inter);
	
	
	system("pause");
	return 0;
}

void meau()
{
	printf("一、单链表遍历,求链表长度\n");
	printf("二、单链表元素逆置\n");
	printf("三、创建非递减有序单链表\n");
	printf("四、合并成非递减链表\n");
	printf("五、在非递减有序单链表中插入元素\n");
	printf("六、在非递减有序链表中删除值为x的结点\n");
	printf("0、退出系统\n");
}

/*输出单链表*/
void printLink(LinkList L)
{
	Node *p;
	p = L->next;
	printf("执行完后单链表为:> ");
	while (p != NULL)
	{
		printf("->%c", p->data);
		p = p->next;
	}
	printf("\n");
}

/*尾插法*/
LinkList CreateFromHead()
{
	char c;
	int flag = 1;
	Node *s;
	Node *L, *r;
	L = (LinkList)malloc(sizeof(Node));
	L->next = NULL;
	r = L;
	while (flag)
	{
		c = getchar();
		if (c != '\n')
		{
			s = (Node *)malloc(sizeof(Node));
			s->data = c;
			r->next = s;
			r = s;
		}
		else
		{
			flag = 0;
			r->next = NULL;
		}
	}
	return L;
}

/*经过求链表的长度遍历链表*/
void ListLength(LinkList L)
{
	int len = 0;
	Node *p;
	p = L->next;
	while (p != NULL)
	{
		len++;
		p = p->next;
	}
	printf("\n此单链表的长度为:len=%d\n", len);
}

/*头插法实现单链表逆置*/
LinkList inversePermutation(LinkList L)
{
	Node *p, *s;
	p = L->next;
	L->next = NULL;
	while (p != NULL)
	{
		s = p->next;
		p->next = L->next;
		L->next = p;
		p = s;
	}
	return L;
}

/*实现单链表元素升序排列*/
LinkList sortAscend(LinkList L)
{
	Node *p, *q;
	char ch;
	p = L->next;
	while (p->next != NULL)
	{
		q = p->next;
		while (q != NULL)
		{
			if (p->data > q->data)
			{
				ch = p->data;
				p->data = q->data;
				q->data = ch;
			}
			q = q->next;
		}
		p = p->next;
	}
	return L;
}

/*合并有序单链表*/
LinkList MergeLinkList(LinkList LA, LinkList LB)
{
	LinkList LC;
	Node *pa, *pb, *pc;
	pa = LA->next;
	pb = LB->next;
	LC = LA;
	LC->next = NULL;
	pc = LC;
	while (pa != NULL&&pb != NULL)
	{
		if (pa->data <= pb->data)
		{
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else
		{
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	if (pa != NULL)
	{
		pc->next = pa;
	}
	else
	{
		pc->next = pb;
	}
	free(LB);
	sortAscend(LC);
	return LC;
}

/*在有序单链表中插入元素*/
LinkList MergeCreateLink(LinkList L, char ch)
{
	Node *p, *q, *s;
	p = L;
	q = p->next;
	s = (Node *)malloc(sizeof(Node));
	s->data = ch;
	while ((q != NULL) && (q->data < ch))
	{
		p = p->next;
		q = p->next;
	}
	s->next = p->next;
	p->next = s;
	return L;
}

/*删除有序单链表中的某个元素*/
LinkList MergeDeleteLink(LinkList L, char ch)
{
	Node *p, *q, *s;
	int flag = 0;
	p = L;
	q = p->next;
	while (q != NULL)
	{
		if (q->data == ch)
		{
			flag = 1;
			p->next = q->next;
		}
		else
		{
			p = p->next;
		}
		q = q->next;
	}
	if (flag == 0)
		printf("没找到您要删除的元素!\n");
	return L;
}

执行代码部分截屏:ide

单链表的各类操做_单链表的各类操做


单链表的各类操做_单链表的各类操做_02


单链表的各类操做_单链表的各类操做_03


单链表的各类操做_单链表的各类操做_04


单链表的各类操做_单链表的各类操做_05


单链表的各类操做_单链表的各类操做_06


单链表的各类操做_单链表的各类操做_07


单链表的各类操做_单链表的各类操做_08