站点图标

C语言链表实现

2018-11-12折腾记录Develop / C
本文最后更新于 607 天前,文中所描述的信息可能已发生改变

先放代码,开一波坑,以后慢慢填ヾ(≧▽≦*)o

由于我在上传的时候未进行完整测试,导致排序部分有些问题,现已修改完成。

另外排序部分只弄了 int 型的排序

改指针相关的东西真头真疼,特别是链表,折腾了一个多小时。〒 ▽ 〒

重写升级完成,这个算法目前除了排序还有用其他就没有用了,可以点这里直接跳转到重制版


_242
#include <stdio.h>
_242
#include <malloc.h>
_242
//链表结构
_242
typedef struct Test
_242
{
_242
int data;
_242
struct Test *next;
_242
}Test,*pTest;
_242
_242
//头插法-创建
_242
pTest Create_Head(int n/*链表包含节点个数*/)
_242
{
_242
int i,data;
_242
pTest list,node;
_242
//创建头节点
_242
list = (pTest)malloc(sizeof(Test));
_242
list->next = NULL;
_242
for(i=0;i<n;i++)
_242
{
_242
//创建临时节点
_242
node = (pTest)malloc(sizeof(Test));
_242
//读入数据
_242
printf("请输入第%d个数据\n",i+1);
_242
scanf("%d",&data);
_242
//将数据存入临时节点的数据域中
_242
node->data = data;
_242
//将list头节点的next指针复制到node头节点的next指针
_242
node->next = list->next;
_242
//将node链表指针结合到list头节点的next指针
_242
list->next = node;
_242
}
_242
//初始化头节点数据
_242
list->data = 0;
_242
return list;
_242
}
_242
_242
//尾插法-创建
_242
pTest Create_End(int n/*链表包含节点个数*/)
_242
{
_242
int i,data;
_242
pTest list,node,p;
_242
//创建头节点
_242
list = (pTest)malloc(sizeof(Test));
_242
list->next = NULL;
_242
//将副本链表指向list用来间接为list指针域赋值
_242
p = list;
_242
for(i=0;i<n;i++)
_242
{
_242
//创建临时节点
_242
node = (pTest)malloc(sizeof(Test));
_242
//读入数据
_242
printf("请输入第%d个数据\n",i+1);
_242
scanf("%d",&data);
_242
//将数据存入临时节点数据域
_242
node->data = data;
_242
//将副本最后的指针域指向临时节点
_242
p->next = node;
_242
//将临时节点的指针域置NULL
_242
node->next = NULL;
_242
//移动副本节点使最新的指针域成为副本链表的最后一个
_242
while(p->next != NULL)
_242
{
_242
p = p->next;
_242
}
_242
}
_242
//初始化头节点数据
_242
list->data = 0;
_242
return list;
_242
}
_242
_242
//添加节点至指定位置
_242
pTest Insert_pos(int i/*要添加到什么位置*/,pTest list/*要进行添加节点的链表*/)
_242
{
_242
int data;
_242
pTest node,p,temp;
_242
//创建list链表的副本
_242
p = list;
_242
//修改位置为实际位置
_242
i = i - 1;
_242
//调整链表指针域位置,临时链表的头节点到达要添加的节点的上一个节点
_242
for(int u = 0; u < i; u++)
_242
{
_242
p = p->next;
_242
}
_242
//创建临时节点
_242
node = (pTest)malloc(sizeof(Test));
_242
temp = (pTest)malloc(sizeof(Test));
_242
//读入数据
_242
printf("请输入第%d个数据\n",i+1);
_242
scanf("%d",&data);
_242
//读入数据到临时节点的数据域
_242
node->data = data;
_242
//将目前节点的next即下一个节点的地址临时存起来
_242
temp->next = p->next;
_242
//把目前节点的next改为node节点,即进行插入
_242
p->next = node;
_242
//将node的next改为之前没修改时的下一个节点地址
_242
node->next = temp->next;
_242
//返回修改好的链表
_242
return list;
_242
}
_242
_242
//添加已经拥有数据的节点
_242
pTest Insert_pos_own(int i/*要添加到什么位置*/,pTest list/*要进行添加节点的链表*/,pTest node)
_242
{
_242
int data;
_242
pTest p,temp;
_242
//创建list链表的副本
_242
p = list;
_242
//修改位置为实际位置
_242
i = i - 1;
_242
//调整链表指针域位置,临时链表的头节点到达要添加的节点的上一个节点
_242
for(int u = 0; u < i; u++)
_242
{
_242
p = p->next;
_242
}
_242
//创建临时节点
_242
temp = (pTest)malloc(sizeof(Test));
_242
//将目前节点的next即下一个节点的地址临时存起来
_242
temp->next = p->next;
_242
//把目前节点的next改为node节点,即进行插入
_242
p->next = node;
_242
//将node的next改为之前没修改时的下一个节点地址
_242
node->next = temp->next;
_242
//返回修改好的链表
_242
return list;
_242
}
_242
_242
//删除指定位置的节点
_242
pTest Delete_pos(int i/*要删除第几个节点*/,pTest list/*要进行删除节点的链表*/)
_242
{
_242
pTest p,temp;
_242
//创建临时节点
_242
temp = (pTest)malloc(sizeof(Test));
_242
p = list;
_242
//调整实际位置
_242
i = i - 1;
_242
//调整链表指针域位置,临时链表的头节点到达要删除的节点的上一个节点
_242
for(int u = 0; u < i; u++)
_242
{
_242
p = p->next;
_242
}
_242
//将要删除的节点的下一个节点的地址存入temp的指针域
_242
temp = p->next->next;
_242
//将temp的指针域赋给要删除节点的指针域
_242
p->next = temp;
_242
//free(temp);
_242
//返回修改后的链表
_242
return list;
_242
}
_242
_242
//清空链表,保留头节点
_242
pTest Clear_List(pTest list)
_242
{
_242
pTest p = list->next; //移动到第一个结点
_242
pTest q;
_242
while(p) {
_242
//printf("%d\t", p->data);
_242
q = p;
_242
p = p->next;
_242
free(q);
_242
}
_242
list->next = NULL;
_242
return list;
_242
}
_242
_242
//遍历链表
_242
pTest Print_List(pTest list)
_242
{
_242
pTest p;
_242
p = list->next; //移动到存放真实数据的第一个结点
_242
while(p) {
_242
printf("%d\t", p->data);
_242
p = p->next;
_242
}
_242
printf("\n");
_242
return 0;
_242
}
_242
_242
//链表逆置
_242
pTest Resever(pTest list)
_242
{
_242
pTest p, q, r;
_242
p = list;//P指向头结点
_242
q = p->next; //q指向第一个结点
_242
while(q->next) {
_242
r = q->next;
_242
q->next = p;
_242
p = q;
_242
q = r;
_242
}
_242
q->next = p; //连上最后一个结点
_242
p = list->next;
_242
p->next = NULL; //收尾
_242
list->next = q; //赋头
_242
return list;
_242
}
_242
_242
//链表排序-从小到大
_242
pTest Bubble_Sort(pTest list)
_242
{
_242
//定义排序个数和下标的变量
_242
int n = 0, i, j, k;
_242
//定义判断链表个数的链表和用来判断大小的链表
_242
pTest p = list, temp;
_242
//判断链表的个数
_242
for(;p->next!=NULL;p = p->next)
_242
{
_242
n++;
_242
}
_242
//外层循环控制循环轮数
_242
for(i = 0; i < n; i++)
_242
{
_242
//内层循环控制每轮比较次数
_242
for(j = 0; j < n; j++)
_242
{
_242
//遍历比较相邻链表数据的大小
_242
temp = list;
_242
//移动比较用的链表
_242
for(k=0;k<j;k++)
_242
{
_242
temp = temp->next;
_242
}
_242
if(temp->data > temp->next->data)
_242
{
_242
//交换的方式是先删除大数据的节点,然后在添加回链表
_242
//删除大数据的节点
_242
list = Delete_pos(j,list);
_242
//将删除后的节点添加会链表的下一个节点
_242
list = Insert_pos_own(j+1,list,temp);
_242
};
_242
}
_242
}
_242
return list;
_242
}
_242
_242
int main()
_242
{
_242
pTest list = Create_End(5);
_242
list = Bubble_Sort(list);
_242
return 0;
_242
}

C语言链表实现

https://blog.ixk.me/post/c-linked-list-implementation
  • 许可协议

    BY-NC-SA

  • 发布于

    2018-11-12

  • 本文作者

    Otstar Lin

转载或引用本文时请遵守许可协议,注明出处、不得用于商业用途!

C 归并排序VSCode配置Java调试环境[Windows]