欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构-链表篇

程序员文章站 2022-03-23 09:19:48
...

链表的优点:

  1. 插入和删除速度快
  2. 内存利用率高
  3. 可以随时扩展,不必担心存储满

链表的缺点:

  1. 不能随机查找,只能通过从头一个一个找,查找效率低

实现如下:

#include <stdio.h>
#include <malloc.h>

typedef struct Node
{
	int data;            //数据域
	struct Node *pNext;  //指针域,存储下一个节点的地址
}Node;

//函数声明
Node* head_create_list();  //头插法创建链表
Node* end_create_list();   //尾插法创建链表
void insert(Node *phead, int address, int val);  //插入节点
void removes(Node *phead, int address, int *removeItem);  //删除节点
void sort(Node *phead);   //排序
void show(Node *head);  //输出链表的所有元素
int number(Node *head);  //判断链表里面元素的个数


void main()
{
	int choose;
	int address, val, removeItem;
	Node *phead = NULL;      //声明头指针,指向头节点
	while(1)
	{
		printf("为链表提供以下功能选项:\n");
		printf("1. 使用头插法建立链表\n");
		printf("2. 使用尾插法建立链表\n");
		printf("3. 插入元素\n");
		printf("4. 删除元素\n");
		printf("5. 排序\n");
		printf("6. 输出所有元素\n");
		printf("请输入选项(输入0退出): ");
		scanf("%d", &choose);
		switch(choose)
		{
			case 1:
				phead = head_create_list();
				break;
			case 2:
				phead = end_create_list();
				break;
			case 3:
				printf("请输入要插入的位置: ");
				scanf("%d", &address);
				printf("请输入要插入的元素: ");
				scanf("%d", &val);
				insert(phead, address, val);
				printf("插入成功!!\n\n");
				break;
			case 4:
				printf("请输入要删除的位置: ");
				scanf("%d", &address);
				removes(phead, address, &removeItem);
				printf("删除成功, 删除的元素为%d\n\n", removeItem);
				break;
			case 5:
				printf("正在排序中...\n");
				sort(phead);
				break;
			case 6:
				show(phead);
				break;
			default:
				exit(-1);
		}
	}
}

//头插法
Node* head_create_list()
{
	int i, size, val;
	Node *phead = (Node*)malloc(sizeof(Node));    //为头节点分配空间
	phead->pNext = NULL;
	printf("请输入元素的个数:");
	scanf("%d", &size);
	if(size <= 0)
	{
		printf("值无效!\n\n");
		free(phead);
		return NULL;
	}
	for(i=1; i<=size; i++)
	{
		Node *pnew = (Node*)malloc(sizeof(Node));
		printf("输入第%d个节点的值: ", i);
		scanf("%d", &val);
		if(pnew == NULL)
		{
			printf("分配空间失败!");
			exit(-1);
		}
		pnew->data = val;
		pnew->pNext = phead->pNext;
		phead->pNext = pnew;
	}
	printf("头插法链表建立成功!\n\n");
	return phead;
}

//尾插法
Node* end_create_list()
{
	int i, size, val;
	Node *phead = (Node*)malloc(sizeof(Node));
	Node *p = phead;        //声明一个指针,用来指向最末尾的节点
	phead->pNext = NULL;
	printf("请输入元素的个数:");
	scanf("%d", &size);
	if(size <= 0)
	{
		printf("值无效!\n\n");
		free(phead);
		return NULL;
	}
	for(i=1; i<=size; i++)
	{
		Node *pnew = (Node*)malloc(sizeof(Node));
		printf("请输入第%d个节点的值: ", i);
		scanf("%d", &val);
		if(pnew == NULL)
		{
			printf("分配空间失败!");
			exit(-1);
		}
		pnew->data = val;
		p->pNext = pnew;
		pnew->pNext = NULL;
		p = pnew;
	}
	printf("尾插法链表建立成功!\n\n");
	return phead;
}

//插入节点
void insert(Node *phead, int address, int val)
{
	Node *p = phead;
	Node *pnew = (Node*)malloc(sizeof(Node));
	int i;
	if(address>number(phead)+1 || address<=0)
	{
		printf("不在范围内!\n\n");
		return;
	}
	else
	{
		for(i=0; i<address-1; i++)
		{
			p = p->pNext;
		}
		pnew->data = val;
		pnew->pNext = p->pNext;
		p->pNext = pnew;
	}
}

//删除节点
void removes(Node *phead, int address, int *removeItem)
{
	int i;
	Node *p1, *p2;
	p1 = phead;
	p2 = phead;
	if(number(phead) == 0)
	{
		printf("链表无元素!\n\n");
		return;
	}
	else if(address>number(phead) || address <=0)
	{
		printf("不在范围内!\n\n");
		return;
	}
	for(i=0; i<address; i++)
	{
		if(i == address-1)
		{
			p2 = p2->pNext;
		}
		else
		{
			p1 = p1->pNext;
			p2 = p2->pNext;
		}
	}
	p1->pNext = p2->pNext;
	p2->pNext = NULL;
	*removeItem = p2->data;
	free(p2);
}

//排序
void sort(Node *phead)
{
	if(number(phead) == 0)
	{
		printf("链表无元素!\n\n");
		return;
	}
	else
	{
		Node *p = phead;
		Node *p1;
		int i, j;
		int temp;
		int all = number(phead);
		for(i=0,p=p->pNext; i<all-1; i++,p=p->pNext)
		{
			for(j=i+1,p1=p->pNext; j<all; j++,p1=p1->pNext)
			{
				if(p->data > p1->data)
				{
					temp = p->data;
					p->data = p1->data;
					p1->data = temp;
				}
			}
		}
		printf("排序成功!\n\n");
	}
}

//输出链表的所有元素
void show(Node *phead)
{
	Node *p = phead;
	if(p == NULL)
	{
		printf("链表无元素!\n\n");
		return;
	}
	else
	{
		while(p->pNext != NULL)
		{
			printf("%d ",p->pNext->data);
			p = p->pNext;
		}
		printf("\n\n");
	}

}

//返回当前链表中节点的个数
int number(Node *phead)
{
	Node *p = phead;
	int num = 0;
	if(phead == NULL)
	{
		return 0;
	}
	while(p->pNext != NULL)
	{
		num++;
		p = p->pNext;
	}
	return num;
}