数据结构-链表篇
程序员文章站
2022-03-23 09:19:48
...
链表的优点:
- 插入和删除速度快
- 内存利用率高
- 可以随时扩展,不必担心存储满
链表的缺点:
- 不能随机查找,只能通过从头一个一个找,查找效率低
实现如下:
#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;
}