数据结构；单向链表 查找倒数第n个，单向链表的排序；顺序表和链表的区别；双向链表 尾删 按位置插入 按位置删除 按位置修改 按位置查找；0724
·
思维导图
双向链表
尾删 按位置插入 按位置删除 按位置修改 按位置查找
代码如下
头文件
#ifndef __doublelink_HEAD_H_
#define __doublelink_HEAD_H_ 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
enum A
{
FALUSE=-1, //运行失败返回
SUCCESS //运行成功返回
};
//给普通节点的数据域 数据类型 起别名
typedef int datatype;
//定义节点的结构体
typedef struct Node
{
union //数据域
{
datatype data;//普通节点的数据域;数据元素
int len;//头节点的数据域;链表长度
};
struct Node *next;//指针域:存储下一个节点的地址
struct Node *prev;//指针域:存储下一个节点的地址
}*doublelink;
doublelink creat_node(int flag);
int insert_head(datatype element,doublelink head);
int output(doublelink head);
int reverse_output(doublelink head);
int insert_rear(datatype element,doublelink head);
int del_head(doublelink head);
int del_rear(doublelink head);
int insert_pos(int pos,datatype element,doublelink head);
int del_pos(int pos,doublelink head);
int change_pos(int pos,datatype element,doublelink head);
datatype search_pos(int pos,doublelink head);
#endif
函数定义
#include "doublelink_head.h"
//创建头节点
//flag=1 头节点初始化
//flag=0 普通节点初始化
//return 返回值 返回新节点
doublelink creat_node(int flag)
{
doublelink s=(doublelink)malloc(sizeof(struct Node));
if(NULL==s)
{
return NULL;
}
//内存申请成功
if(flag==1)//头节点 初始化len
s->len=0;
else if(flag==0)//普通节点 初始化data
s->data=0;
s->next=s->prev=NULL;
//返回新节点
return s;
}
//双向链表头插
int insert_head(datatype element,doublelink head)
{
//判断头节点是否存在
if(NULL==head)
{return FALUSE;}
//头插入
//创建一个新节点
doublelink s=creat_node(0);
if(NULL==s)
return FALUSE;
//节点创建成功
//如果只有head
s->data=element;//对新节点数据 赋值 插入的元素
s->next=head->next;//插入新节点
s->prev=head;
if (head->next!=NULL)//如果只有head,就不执行下面的
{head->next->prev=s;}
head->next=s;
//链表长度增加
head->len++;
return SUCCESS;
}
//循环输出正向打印 双向链表
int output(doublelink head)
{
//判断头节点是否存在
if(NULL==head||head->next==NULL)
{return FALUSE;}
//循环输出
doublelink p=head->next;//p获取 head->next的值 head不可以动 p可以动
while(p!=NULL)
{
printf("%d ",p->data); //循环输出p的data
p=p->next;//p后移
}
putchar(10);
return SUCCESS;
}
//循环输出逆向打印 双向链表
int reverse_output(doublelink head)
{
//判断头节点是否存在
if(NULL==head||head->next==NULL)
{return FALUSE;}
//循环输出
doublelink p=head->next;//p获取 head->next的值 head不可以动 p可以动 p去找最后一个节点
while(p->next!=NULL)
{p=p->next;}//p后移
while(p!=head)
{
printf("%d ",p->data); //循环输出p的data
p=p->prev;//p后移
}
putchar(10);
return SUCCESS;
}
//双向链表尾部插入
int insert_rear(datatype element,doublelink head)
{
//判断头节点是否存在
if(NULL==head)
{return FALUSE;}
doublelink s=creat_node(0);//创建新节点
if(NULL==s)
{return FALUSE;}
s->data=element;//新节点的数据 是要插入的数据
doublelink p=head;//head不能动 新建p 去找到最后一个节点
while(p->next!=NULL)
{
p=p->next;//p向后移动
}
p->next=s;//在最后节点的后面 插入新元素
s->prev=p;//最后的节点的前一个是p
head->len++;//插入一个元素 链表长度+1
return SUCCESS;
}
//双向链表 头删
int del_head(doublelink head)
{
//判断头节点是否存在
//判断链表中 头节点除外 还有没有其他节点
if(NULL==head||head->next==NULL)
{return FALUSE;}
//创建一个新节点
doublelink del=head->next;//保存 头节的下一个节点 要删除的节点
head->next=del->next;//head指向 下下个节点
if(del->next!=NULL)//要考虑只有一个普通节点的情况
{del->next->prev=head;}
free(del);//释放del的空间
del=NULL;//del指向NULL 防止野指针
head->len--;
return SUCCESS;
}
//双向链表 尾删
int del_rear(doublelink head)
{
//判断头节点是否存在
//判断链表中 头节点除外 还有没有其他节点
if(NULL==head||head->next==NULL)
{return FALUSE;}
//创建一个新节点
doublelink p=head;//头节点不可移动 用p去找倒数第二个节点
while(p->next->next!=NULL)
{
p=p->next;
}
doublelink del=p->next;
//指针域连接 删除节点
p->next=NULL;
del->prev=NULL;
free(del);//删除del节点 释放空间
head->len--;
return SUCCESS;
}
//双向链表 按位置插入
int insert_pos(int pos,datatype element,doublelink head)
{
//判断头节点是否存在
//判断 插入的位置是否合法
if(NULL==head||pos<1||pos>head->len+1)
{return FALUSE;}
//创建一个新节点
doublelink p=head;//头节点不可移动 用p去找倒数第pos-1个节点
for(int i=0;i<pos-1;i++)//用p去找第pos-1个节点
{
p=p->next;
}
doublelink s=creat_node(0);//创建新节点
if(NULL==s) //建议做判断NULL=s 那就照做
{return FALUSE;}
s->data=element;//新节点数据 赋值要插入的数据
//指针域连接 插入新节点 插入到p的前面
s->next=p->next;
s->prev=p;
if(p->next!=NULL)//考虑 p的后继节点是NULL
{
p->next->prev=s;
}
p->next=s;
head->len++;
return SUCCESS;
}
//按位置删除
int del_pos(int pos,doublelink head)
{
//判断头节点是否存在
//判断 有其他节点
//判断 删除的位置是否合法
if(NULL==head||head->len<1||pos<1||pos>head->len)
{return FALUSE;}
//实现指定位置删除
//创建一个新节点
doublelink p=head;//用p去找第pos-1个位置
for(int i=0;i<pos-1;i++)
{
p=p->next;
}
doublelink del=p->next;//新建del 保留要被删除的p->next
//指针域连接 删除后继节点
p->next=del->next;
del->prev=NULL;
del->next->prev=p;
del->next=NULL;
free(del);//删除del节点 释放空间
head->len--;
return SUCCESS;
}
//按位置修改
int change_pos(int pos,datatype element,doublelink head)
{
//判断头节点是否存在
//判断 有其他节点
//判断 修改的位置是否合法
if(NULL==head||head->len<=1||pos<1||pos>head->len)
{return FALUSE;}
//实现指定位置修改
//创建一个新节点
doublelink p=head;//用p去找第pos个位置
for(int i=0;i<pos;i++)
{
p=p->next;
}
p->data=element;//赋值p的数据为 element
return SUCCESS;
}
//按位置查找
datatype search_pos(int pos,doublelink head)
{
//判断头节点是否存在
//判断 有其他节点
//判断 删除的位置是否合法
if(NULL==head||head->len<1||pos<0||pos>head->len)
{return FALUSE;}
//实现按位置查找
//创建一个新节点
doublelink p=head;//用p去找第pos个位置
for(int i=0;i<pos;i++)
{
p=p->next;
}
return p->data;
}
主函数
#include "doublelink_head.h"
int main()
{
//创建头节点
doublelink head=creat_node(1);
//创建一个变量element 输入数据用
datatype element;
//双向链表头插 在头节点的后面插入数据元素嘛
for(int i=0;i<3;i++)
{
printf("please enter insert head element:");
scanf("%d",&element);
insert_head(element,head);
}
//循环输出 正向打印 双向链表
printf("doublelink after head insert\n");
output(head);
//循环输出 逆向打印 双向链表
printf("doublelink after head insert revese output\n");
reverse_output(head);
//双向链表尾插
//双向链表尾插 在最后节点的后面插入数据元素嘛
for(int i=0;i<3;i++)
{
printf("please enter insert rear element:");
scanf("%d",&element);
insert_rear(element,head);
}
//循环输出 正向 双向链表
printf("doublelink after rear insert\n");
output(head);
//双向链表 头删 删除头节点的后一个嘛
del_head(head);
printf("doublelink after head delete element\n");
output(head);
//双向链表 尾删 删除最后一个节点
del_rear(head);
printf("doublelink after rear delete element\n");
output(head);
//双向链表 按位置插入
int pos;
printf("enter insert postiton:");
scanf("%d",&pos);
printf("enter insert element:");
scanf("%d",&element);
insert_pos(pos,element,head);
printf("doublelink after position insert elements\n");
output(head);
//按位置删除
printf("please enter delete postition:");
scanf("%d",&pos);
del_pos(pos,head);
printf("doublelink after delete position elements\n");
output(head);
//按位置修改
printf("please enter change postition:");
scanf("%d",&pos);
printf("please enter change element:");
scanf("%d",&element);
change_pos(pos,element,head);
printf("doublelink after change position elements\n");
output(head);
//按位置查找
printf("please enter search postition:");
scanf("%d",&pos);
printf("doublelink search opsition element:%d\n",search_pos(pos,head));
return 0;
}
单向链表 0723重点补完
查找倒数第n个，单向链表的排序
代码如下
头文件
#ifndef __linklist_HEAD_H_
#define __linklist_HEAD_H_ 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
enum A
{
FALUSE=-1, //运行失败返回
SUCCESS //运行成功返回
};
//给普通节点的数据域 数据类型 起别名
typedef int datatype;
//定义节点的结构体
typedef struct Node
{
union //数据域
{
datatype data;//普通节点的数据域;数据元素
int len;//头节点的数据域;链表长度
};
struct Node *next;//指针域:存储下一个节点的地址
}*linklist;
linklist creat_node(int flag);
int insert_head(datatype element,linklist head);
int output(linklist head);
int insert_rear(datatype element,linklist head);
int del_head(linklist head);
int del_rear(linklist head);
int insert_pos(int pos,datatype element,linklist head);
int reverse(linklist head);
int del_pos(int pos,linklist head);
int change_pos(int pos,datatype element,linklist head);
datatype search_pos(int pos,linklist head);
int search_element(datatype element,linklist head);
int change_element(datatype element,datatype celement,linklist head);
int delete_element(datatype element,linklist head);
int countdown_pos_search(int n,linklist head);
int bubbing_sort_linklist(linklist head);
int simple_sort_linklist(linklist head);
#endif
函数定义
#include "linklist_head.h"
//创建头节点
//flag=1 头节点初始化
//flag=0 普通节点初始化
//return 返回值 返回新节点
linklist creat_node(int flag)
{
linklist s=(linklist)malloc(sizeof(struct Node));
if(NULL==s)
{
return NULL;
}
//内存申请成功
if(flag==1)//头节点 初始化len
s->len=0;
else if(flag==0)//普通节点 初始化data
s->data=0;
s->next=NULL;
//返回新节点
return s;
}
int insert_head(datatype element,linklist head)
{
//判断头节点是否存在
if(NULL==head)
{return FALUSE;}
//头插入
//创建一个新节点
linklist s=creat_node(0);
if(NULL==s)
return FALUSE;
//节点创建成功
s->data=element;//对新节点数据 赋值 插入的元素
//插入新节点
s->next=head->next;
head->next=s;
//链表长度增加
head->len++;
return SUCCESS;
}
//循环输出链表
int output(linklist head)
{
//判断头节点是否存在
if(NULL==head)
{return FALUSE;}
//循环输出
linklist p=head->next;//p获取 head->next的值 head不可以动 p可以动
while(p!=NULL)
{
printf("%d ",p->data); //循环输出p的data
p=p->next;//p后移
}
putchar(10);
return SUCCESS;
}
//尾部插入
int insert_rear(datatype element,linklist head)
{
//判断头节点是否存在
if(NULL==head)
{return FALUSE;}
linklist s=creat_node(0);//创建新节点
if(NULL==s)
{return FALUSE;}
s->data=element;//新节点的数据 是要插入的数据
linklist p=head;//head不能动 新建p 去找到最后一个节点
while(p->next!=NULL)
{
p=p->next;//p向后移动
}
p->next=s;//在最后节点的后面 插入新元素
head->len++;//插入一个元素 链表长度+1
return SUCCESS;
}
//头删
int del_head(linklist head)
{
//判断头节点是否存在
//判断链表中 头节点除外 还有没有其他节点
if(NULL==head||head->next==NULL)
{return FALUSE;}
//创建一个新节点
linklist del=head->next;//保存 头节的下一个节点 要删除的节点
head->next=del->next;//head指向 下下个节点
free(del);//释放del的空间
del==NULL;//del指向NULL 防止野指针
head->len--;
return SUCCESS;
}
//尾删
int del_rear(linklist head)
{
//判断头节点是否存在
//判断链表中 头节点除外 还有没有其他节点
if(NULL==head||head->next==NULL)
{return FALUSE;}
//创建一个新节点
linklist p=head;//头节点不可移动 用p去找倒数第二个节点
while(p->next->next!=NULL)
{
p=p->next;
}
free(p->next);//删除p的后继节点 释放倒数第一个节点的空间
p->next=NULL;//倒数第二个指针 指向空 NULL
head->len--;
return SUCCESS;
}
//按位置插入
int insert_pos(int pos,datatype element,linklist head)
{
//判断头节点是否存在
//判断 插入的位置是否合法
if(NULL==head||pos<1||pos>head->len+1)
{return FALUSE;}
//创建一个新节点
linklist p=head;//头节点不可移动 用p去找倒数第pos-1个节点
for(int i=0;i<pos-1;i++)
{
p=p->next;
}
linklist s=creat_node(0);//创建新节点
if(NULL==s) //建议做判断NULL=s 那就照做
{return FALUSE;}
s->data=element;//新节点数据 赋值要插入的数据
s->next=p->next;//插入到指定位置
p->next=s;
head->len++;
return SUCCESS;
}
//逆置
int reverse(linklist head)
{
//判断头节点是否存在
//判断 有其他节点 有1个以上的节点
if(NULL==head||head->len<=1)
{return FALUSE;}
//创建一个新节点
linklist p=head->next;//头节点要断开 用p保留head->next
head->next=NULL;
for(int i=0;i<head->len;i++)
{
linklist temp=p;//用temp暂存要被头插的元素
p=p->next;
temp->next=head->next;
head->next=temp;//把temp插入在head后面
}
return SUCCESS;
}
//按位置删除
int del_pos(int pos,linklist head)
{
//判断头节点是否存在
//判断 有其他节点 有1个以上的节点
//判断 删除的位置是否合法
if(NULL==head||head->len<=1||pos<1||pos>head->len)
{return FALUSE;}
//实现指定位置删除
//创建一个新节点
linklist p=head;//用p去找第pos-1个位置
for(int i=0;i<pos-1;i++)
{
p=p->next;
}
linklist del=p->next;//新建del 保留要被删除的p->next
p->next=del->next;//p->next指向下下个
free(del);//释放del的空间
del=NULL;//指向NULL
head->len--;//删除一个指定元素 链表长度-1
return SUCCESS;
}
//按位置修改
int change_pos(int pos,datatype element,linklist head)
{
//判断头节点是否存在
//判断 有其他节点
//判断 修改的位置是否合法
if(NULL==head||head->len<=1||pos<1||pos>head->len)
{return FALUSE;}
//实现指定位置修改
//创建一个新节点
linklist p=head;//用p去找第pos个位置
for(int i=0;i<pos;i++)
{
p=p->next;
}
p->data=element;//赋值p的数据为 element
return SUCCESS;
}
//按位置查找
datatype search_pos(int pos,linklist head)
{
//判断头节点是否存在
//判断 有其他节点
//判断 删除的位置是否合法
if(NULL==head||head->len<1||pos<0||pos>head->len)
{return FALUSE;}
//实现按位置查找
//创建一个新节点
linklist p=head;//用p去找第pos个位置
for(int i=0;i<pos;i++)
{
p=p->next;
}
return p->data;
}
//按元素查找
int search_element(datatype element,linklist head)
{
//判断头节点是否存在
//判断 有其他节点
if(NULL==head||head->len<1)
{return FALUSE;}
//实现按元素查找
//创建一个新节点
linklist p=head->next;//用p的数据域和element比较
for(int i=1;i<=head->len+1;i++)
{
if(i==head->len+1)//没找到 i=pos+1
{
printf("search element error...\n");
return FALUSE;
}
if(p->data==element)
{return i;}
p=p->next;
}
}
//按元素修改
int change_element(datatype element,datatype celement,linklist head)
{
//判断头节点是否存在
//判断 有其他节点
if(NULL==head||head->len<1)
{return FALUSE;}
//实现按元素修改
//先 调用 按元素查找 得到元素的位置
int t=search_element(element,head);
//再 调用 按位置修改
change_pos(t,celement,head);
return SUCCESS;
}
//按元素删除
int delete_element(datatype element,linklist head)
{
//判断头节点是否存在
//判断 有其他节点
if(NULL==head||head->len<1)
{return FALUSE;}
//实现按元素删除
//先 调用 按元素查找 得到元素的位置
int t=search_element(element,head);
//再 调用 按位置删除
del_pos(t,head);
return SUCCESS;
}
//查找倒数第n个节点
//传参数 n 头节点head
//
//返回值 成功 返回节点的地址 失败 返回NULL
int countdown_pos_search(int n,linklist head)
{
//判断头节点是否存在
//判断 有其他节点
//判断 查找的倒数位置是否合法
if(NULL==head||head->len<1||n>head->len)
{return FALUSE;}
//实现查找倒数第n个元素
//先 新建p=>head ,q向后移动n步
linklist p=head;
linklist q=head;
for(int i=0;i<n;i++)
{
q=q->next;
}
//再 同时向后移动
int ct=0;
while(q!=NULL)
{
p=p->next;
q=q->next;
ct++;
}
return ct;
}
//单链表冒泡排序
int bubbing_sort_linklist(linklist head)
{
//判断头节点是否存在
//判断 有一个以上节点
if(NULL==head||head->len<=1)
{return FALUSE;}
//实现单链表 冒泡 升序
for(int i=1;i<head->len;i++)
{
linklist p=head->next;
for(int j=0;j<head->len-i;j++)
{
if(p->data>p->next->data)
{
int t=p->data;
p->data=p->next->data;
p->next->data=t;
}
p=p->next;
}
}
return SUCCESS;
}
//单链表选择排序
int simple_sort_linklist(linklist head)
{
//判断头节点是否存在
//判断 有一个以上节点
if(NULL==head||head->len<=1)
{return FALUSE;}
//实现单链表 简单选择排序 降序
for(linklist i=head->next;i->next!=NULL;i=i->next)
{
linklist max=i;
for(linklist j=i->next;j!=NULL;j=j->next)
{
if(max->data<j->data)
{
max=j;
}
}
int t=max->data;
max->data=i->data;
i->data=t;
}
return SUCCESS;
}
主函数
#include "linklist_head.h"
int main()
{
//创建头节点
linklist head=creat_node(1);
//链表头插 在头节点的后面插入数据元素嘛
datatype element;
for(int i=0;i<5;i++)
{
printf("please enter insert head element:");
scanf("%d",&element);
insert_head(element,head);
}
//循环输出单链表
printf("linklist after head insert\n");
output(head);
//尾插 调用还没实现 还是输出有问题
//链表尾插 在最后节点的后面插入数据元素嘛
for(int i=0;i<5;i++)
{
printf("please enter insert rear element:");
scanf("%d",&element);
insert_rear(element,head);
}
//循环输出单链表
printf("linklist after rear insert\n");
output(head);
//按位置插入
int pos;
printf("enter insert postiton:");
scanf("%d",&pos);
printf("enter insert element:");
scanf("%d",&element);
insert_pos(pos,element,head);
printf("linklist after position insert elements\n");
output(head);
//单链表的逆置
reverse(head);
printf("linklist after reverse\n");
output(head);
//按位置删除
printf("please enter delete postition:");
scanf("%d",&pos);
del_pos(pos,head);
printf("linklist after delete position elements\n");
output(head);
//按位置修改
printf("please enter change postition:");
scanf("%d",&pos);
printf("please enter change element:");
scanf("%d",&element);
change_pos(pos,element,head);
printf("linklist after change position elements\n");
output(head);
//按位置查找
printf("please enter search postition:");
scanf("%d",&pos);
printf("linklist search opsition element:%d\n",search_pos(pos,head));
//按元素查找
printf("please enter search element:");
scanf("%d",&element);
printf("linklist search element opsition:%d\n",search_element(element,head));
//按元素修改
printf("please enter target element to change:");
scanf("%d",&element);
int celement;
printf("please enter change element:");
scanf("%d",&celement);
change_element(element,celement,head);
printf("linklist after change target elements\n");
output(head);
//按元素删除
printf("please enter delete element:");
scanf("%d",&element);
delete_element(element,head);
printf("linklist after delete target element\n");
output(head);
//查找倒数第n个
int n;
printf("please enter count down position:");
scanf("%d",&n);
printf("linklist search element opsition:%d\n",countdown_pos_search(n,head));
//单链表冒泡排序
bubbing_sort_linklist(head);
printf("linklist after bubbing sort:");
output(head);
//单链表选择排序
simple_sort_linklist(head);
printf("linklist after simple sort:");
output(head);
//单链表内存释放 要一个一个释放
int L=head->len;
for(int i=0;i<L;i++)
{
del_head(head);//遍历删除单链表
}
free(head);//释放head空间
head==NULL;//防止野指针
return 0;
}
开源鸿蒙跨平台开发社区汇聚开发者与厂商，共建“一次开发，多端部署”的开源生态，致力于降低跨端开发门槛，推动万物智联创新。
更多推荐
3
0- 0
已为社区贡献1条内容
所有评论(0)