1、单链表的排序
示例代码如下：
#include<iostream>
using namespace std;
///单链表结构体：结点
typedef struct student
{
int data; //结点中的数据
struct student *next; //指向链表下一个结点的指针
}node;
node *head; //头结点指针
int index; //链表长度
///建立单链表
void *create()
{
node *p,*s; //增加结点的位置指针、要增加结点的指针
int x,cycle=1; //x是结点中的数据，若为0代表创建结束;cycle是循环控制变量
head=(node*)malloc(sizeof(node)); //动态分配，建立头节点
p=head;
while(cycle)
{
printf("Please input the data:");
scanf("%d",&x);
if(x!=0)
{
s=(node*)malloc(sizeof(node)); //动态分配，每次新建一个节点
s->data=x; //将数据存入该结点
// printf("%d\n",s->data); //查看该结点中的数据是否正确
p->next=s; //连接头指针与当前结点
p=s; //并将头指针指向当前结点的指针，即下一个结点的地址
}
else
{
cycle=0;
}
}
p->next=NULL; //最后一个结点为空指针（必须）
// head=head->next; //创建完毕单链表，头结点指针回去
// printf("\n yyy %d",head->data); //打印第一个结点中的数据，用于验证
return head; //返回根结点
}
///遍历单链表（单链表打印），同时测长
//注：链表无法从反方向进行遍历
void traverse(node *head)
{
node *p;
index=0;
if(head->next==NULL)
{
printf("Link is empty!\n");
return;
}
p=head->next;
while(p!=NULL)//遍历链表
{
printf("The %dth node is:%d\n",++index,p->data);//打印元素，亦可计算链表长度(index)
p=p->next;//进入下一个结点
}
printf("\n该链表长度为：%d\n\n",index);
}
///单链表的排序
void *sort(node *head)
{
node *p;
int n=index; //链表长度
int temp;
if(head==NULL || head->next==NULL)
return head;
p=head->next; //p指向结点1，可以得到结点1的数据
for(int j=1;j<n;j++) //冒泡排序
{
p=head->next; //每次冒泡过程完毕后，必须返回结点1
for(int i=n-1;i>=j;i--) //一次冒泡过程
{
if( (p->data) > (p->next->data) ) //从小到大排序
{
temp=p->data;
p->data=p->next->data;
p->next->data=temp;
}
p=p->next;
}
}
p=head->next; //要打印排序好的链表，必须从头开始打印，也是遍历的一个过程
//打印出排好序的链表(从小到大)
for(int m=0;m<n;m++)
{
printf(" %d",p->data);
p=p->next;
}
cout<<endl;
}
int main()
{
cout<<"/***** 单链表的创建 *****/"<<endl;
create(); //单链表的创建
cout<<endl<<"/***** 单链表的遍历与测长 *****/"<<endl;
traverse(head); //单链表的遍历与测长
cout<<endl<<"/***** 单链表的排序 *****/"<<endl;
sort(head); //单链表的排序
return 0;
}
测试结果如图：
2、单链表的逆置（逆序）
单链表的逆置有2种方法，分别如下。
方法一：
基本思想：类似于冒泡法，但是不用比较数据大小，即可。
方法二：
基本思想：
（1）、单链表的模型如下图：
（2）、进行单链表的逆序，首先要让p2的next指向p1，如下图：
（3）、再由p1指向p2，p2指向p3，如下图：
然后重复p2的next指向p1，p1指向p2，p2指向p3。
完整的示例代码如下：
#include<iostream>
using namespace std;
///单链表结构体：结点
typedef struct student
{
int data; //结点中的数据
struct student *next; //指向链表下一个结点的指针
}node;
node *head; //头结点指针
int index; //链表长度
///建立单链表
void *create()
{
node *p,*s; //增加结点的位置指针、要增加结点的指针
int x,cycle=1; //x是结点中的数据，若为0代表创建结束;cycle是循环控制变量
head=(node*)malloc(sizeof(node)); //动态分配，建立头节点
p=head;
while(cycle)
{
printf("Please input the data:");
scanf("%d",&x);
if(x!=0)
{
s=(node*)malloc(sizeof(node)); //动态分配，每次新建一个节点
s->data=x; //将数据存入该结点
// printf("%d\n",s->data); //查看该结点中的数据是否正确
p->next=s; //连接头指针与当前结点
p=s; //并将头指针指向当前结点的指针，即下一个结点的地址
}
else
{
cycle=0;
}
}
p->next=NULL; //最后一个结点为空指针（必须）
// head=head->next; //创建完毕单链表，头结点指针回去
// printf("\n yyy %d",head->data); //打印第一个结点中的数据，用于验证
return head; //返回根结点
}
///遍历单链表（单链表打印），同时测长
//注：链表无法从反方向进行遍历
void traverse(node *head)
{
node *p;
index=0;
if(head->next==NULL)
{
printf("Link is empty!\n");
return;
}
p=head->next;
while(p!=NULL)//遍历链表
{
printf("The %dth node is:%d\n",++index,p->data);//打印元素，亦可计算链表长度(index)
p=p->next;//进入下一个结点
}
printf("\n该链表长度为：%d\n\n",index);
}
///单链表的排序
void *sort(node *head)
{
node *p;
int n=index; //链表长度
int temp;
if(head==NULL || head->next==NULL)
return head;
p=head->next; //p指向结点1，可以得到结点1的数据
for(int j=1;j<n;j++) //冒泡排序
{
p=head->next; //每次冒泡过程完毕后，必须返回结点1
for(int i=n-1;i>=j;i--) //一次冒泡过程
{
if( (p->data) > (p->next->data) ) //从小到大排序
{
temp=p->data;
p->data=p->next->data;
p->next->data=temp;
}
p=p->next;
}
}
p=head->next; //要打印排序好的链表，必须从头开始打印，也是遍历的一个过程
//打印出排好序的链表(从小到大)
for(int m=0;m<n;m++)
{
printf(" %d",p->data);
p=p->next;
}
cout<<endl;
}
///单链表的逆置：方法一
/*
注：链表无法从反方向进行遍历
方法一的基本思想：类似于冒泡法，但是不用比较数据大小即可。
*/
void *reverse1(node *head)
{
node *p;
int n=index; //链表长度
int temp;
if(head==NULL || head->next==NULL)
return head;
p=head->next; //p指向结点1，可以得到结点1的数据
for(int j=1;j<n;j++)
{
p=head->next;
for(int i=n-1;i>=j;i--)
{
temp=p->data;
p->data=p->next->data;
p->next->data=temp;
p=p->next;
}
}
p=head->next;
//打印出逆置后的链表
for(int m=0;m<index;m++)
{
printf(" %d",p->data);
p=p->next;
}
}
///单链表的逆置：方法二
void *reverse2(node *head)
{
node *p1,*p2,*p3;
if(head==NULL || head->next==NULL)
return head;
p1=head; //初始化p1是根结点
p2=p1->next;//初始化p2是结点1
while(p2)//当前结点的下一个结点是否为空
{
p3=p2->next;
p2->next=p1;
p1=p2;
p2=p3;
}
head->next=NULL;
head=p1;
//打印出逆置后的链表
for(int m=0;m<index;m++)
{
printf(" %d",p1->data);
p1=p1->next;
}
cout<<endl;
}
int main()
{
cout<<"/***** 单链表的创建 *****/"<<endl;
create(); //单链表的创建
cout<<endl<<"/***** 单链表的遍历与测长 *****/"<<endl;
traverse(head); //单链表的遍历与测长
// cout<<endl<<"/***** 单链表的排序 *****/"<<endl;
// sort(head); //单链表的排序
cout<<endl<<"/***** 单链表的逆置：方法一 *****/"<<endl;
reverse1(head); //单链表的逆置：方法一
cout<<endl<<"/***** 单链表的逆置：方法二 *****/"<<endl;
reverse2(head); //单链表的逆置：方法二
return 0;
}
测试结果如下图：
时间： 2024-10-26 05:42:57