链表操作

时间:2022-03-24 01:02:59

自己根据老师布置的习题写的一些代码,有很多不足,希望指正

#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
typedef struct node
{
	int data;
	struct node* next;
}Node,*LinkList;
LinkList creat();
void print(LinkList h);

LinkList creat()
{
	LinkList h, r, s;
	h = (LinkList)malloc(sizeof(Node));
	h = r = NULL;
	int num;
	printf("请输入一组数据,以-1为结束标志:\n");
	scanf_s("%d", &num);
	while (num != -1)
	{
		s = (LinkList)malloc(sizeof(Node));
		s->data = num;//将输入的数据存储到新结点的数据域中
		s->next = NULL;
		if (h == NULL)
			h = s;
		else
			r->next = s;
		r = s;
		scanf_s("%d", &num);
		
	}
	return h;
}
void print(LinkList h)
{
	LinkList p;
	p = h;
	if (h == NULL)
	{
		printf("链表为空\n");
	}
	else
	{
		printf("链表如下:\n");
		while (p != NULL)
		{
			printf("%d ", p->data);
			p = p->next;
		}
	}
	printf("\n");
}

int fun1(LinkList h) {
	LinkList p = h->next;
	int sum = 0, n = 0, m = 0;
	for (; p; p = p->next) 
	{
		sum = sum + p->data;
		n++;
	}
	p = h->next;
	while (p) 
	{
		if (p->data < (sum *1.0)/n)
			m++;
		p = p->next;
	}
	return m;
}
//求结点最大值和最小值
void fun2(LinkList h, int& max, int& min)
{
	LinkList p = h->next;
	max = min = p->data;
	for(p=h->next;p;p=p->next)
	{
		if (max < p->data)
			max = p->data;
		if (min > p->data)
			min = p->data;
	}
}
//查找结点
LinkList find(LinkList h, ElemType x)
{
	LinkList p = h->next;
	LinkList pfind = NULL;
	for (p = h; p->next != NULL; p = p->next)
		if (p->data == x)
			pfind = p;
	return pfind;
}
////查找结点的前导
//LinkList find_pre(LinkList h, ElemType x)
//{
//	LinkList p = h->next, q = h;
//	while (p && p->data != x)
//	{
//		q = p;
//		p = p->next;
//	}
//	return q;
//}
//链表的插入
//将“我”插入在p所指的结点之后,把p的后继变为我的后继,把我变为p的后继,s->next=p->next;p->next=s;
//若p指向的是尾结点,不断在尾部插入,则可在空表的基础上建立新的链表,循环结束后,r->next=0,始终在尾部插入,数据存储顺序与输入顺序一致
//若p指向的是头结点,不断在头部插入,也可在空表的基础上建立新的链表,始终在头部插入,数据存储顺序与输入顺序相反




//已知整型链表,设计算法,在所有结点值为x的结点前插入结点值为y的结点,插入的结点个数通过函数值返回
int insert(LinkList h, int x, int y) {
	LinkList p = h->next, q = h, s; int n = 0;
	while (p) 
	{
		if (p->data == x) {
			s = (LinkList)malloc(sizeof(Node));
			s->data = y;
			s->next = q->next;
			q->next = s;
			n++;
		}
		q = p;
		p = p->next;
	}
	return n;
}
//已知整型链表,设计算法,删除所有结点值为x的结点,删除的结点个数通过形参返回
//链表的删除操作,把前导的后继变为我,把我的后继变为我前导的后继。q=p->next;p->next=q->next;
void del(LinkList h, int x, int* count)
{
	LinkList p = h->next, q = h, s;
	while (p)
	{
		if (p->data == x)
		{
			s = (LinkList)malloc(sizeof(Node));
			s = p;
			q->next = p->next;
			p = p->next;
			free(s);
			(*count)++;
		}
		
		else
		{
			q = p;
			p = p->next;
		}
	}
}

int main()
{
	LinkList head,p;
	head = creat();
	int x=0;//要查找的结点
	int max = 0;
	int min = 0;
	int n = 0;
	int count = 0;
	print(head);
	printf("结点值小于平均结点值的个数为%d\n", fun1(head));
	printf("\n");
	fun2(head, max, min);
	printf("最大值为%d,最小值为%d\n", max, min);
	printf("请输入要查找的结点:\n");
	scanf_s("%d", &x);
	p = find(head, x);
	if (p)
		printf("所查找的结点为%d\n",x);
	else
		printf("您查找的数值不存在!\n");
	int m = 0;
	int y = 0;
	printf("请输入在结点x插入y的x、y的值:\n");
	scanf_s("%d %d", &m, &y);
	n = insert(head, m, y);
	for (p = head->next; p; p = p->next)
		printf("%d ", p->data);
	printf("\n共插入了%d个结点", n);
	int s = 0;
	printf("\n请输入要删除的结点值:");
	scanf_s("%d", &s);
	del(head, s, &count);
	for (p = head->next; p; p = p->next)
		printf("%d ", p->data);
	printf("\n共删除了%d个结点", count);
	return 0;
}