#include<stdio.h>
#include<malloc.h>
#include <stdio.h>
#include <stdlib.h> typedef struct Node{
int data;//数据源
struct Node* pNext;//指针域
}NODE,*PNODE; // NODE等价于struct Node,PNODE等价于struct Node*;
//函数的声明
//创建一个非循环的链表
PNODE create_list(void){
int len;//存放结果的数目
int val;
//创建头结点，该头结点不存储数据
PNODE pHead = (PNODE)malloc(sizeof(NODE));
PNODE pTail = pHead; //保证PTail永远指向链表的尾结点
pTail->pNext = NULL;
if(NULL == pHead){
printf("程序内存分配失败");
exit(-);
}
printf("请输入你要创建节点的数目：");
scanf("%d",&len);
for(int i = ;i < len;i++){
printf("请输入第%d节点的值：",i+);
scanf("%d",&val);
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if(NULL == pNew){
printf("程序内存分配失败");
exit(-);
}
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead; } /*
判断链表是否为null
*/ bool isEmpty(PNODE pHead){
if(pHead->pNext == NULL){//说明链表为空
return true;
}else{
return false;
}
} /*
获得链表的长度
*/ int length_list(PNODE pHead){
int count = ;
PNODE p = pHead->pNext; // 第一个节点不存储数据，所以要移动下一个节点
while(NULL != p){//说明该节点不为null
int val = p->data; //得到数据
p=p->pNext;//p移动到下一个节点
count=count+;
}
return count;
} /*
输出该链表的所有值
*/
void printf_list(PNODE pHead){
PNODE p = pHead->pNext; // 第一个节点不存储数据，所以要移动下一个节点
while(NULL != p){//说明该节点不为null
int val = p->data; //得到数据
printf("%d\n",val);
p=p->pNext;//p移动到下一个节点
} }
/*
对链表进行排序
仿造对数组的排序
for(int i = 0 ; i< len -1 ;i++){
for( int j = i+ 1; j< len ;j++){ } } */
//单链表的排序
void sort_list(PNODE pHead)
{
int i,j,t;
PNODE p=pHead->pNext; for(i=;i<length_list(pHead)-;i++)
{
p=pHead->pNext;
for(j=;j<length_list(pHead)-i-;j++)
{
if(p->data < p->pNext->data) //冒泡法，将最小的冒泡到最后，降序排列；
{
t=p->data;
p->data = p->pNext->data ;
p->pNext->data = t ;
}
p=p->pNext;
}
}
} /*
for(i=0;i<n-1;i++) for(j=i+1;j<n;j++)
**/
void sort_array(int*arr,int len){ int i = ;
int j = ;
int temp;
for(i = ;i< len-;i++){ //p要执行当前节点的下一个节点
for(j = i+;j<len;j++){
if(arr[i]>arr[j]) {
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
} }
void print_array(int*arr,int len){
for(int k = ; k<len;k++){
printf("a[%d]=%d\n",k,*(arr+k));
}
} /*
在链表的pos下标插入值val ，并且pos的值必须大于1
*/ void insert(PNODE pHead,int pos,int val){
int i=;
PNODE p=pHead; //不需判断链表是否为空，不需判断pos是否满足链表长度要求等。。此部分用while和if全部搞定
while(NULL!=p&&i<pos-) //不能写成<=，否则出错
{
i++;
p=p->pNext;
}
if(i>pos- || NULL==p)
return false; PNODE pNew=(PNODE)malloc(sizeof(NODE));
if(NULL==pNew)
{
cout<<"分配失败，程序终止！"<<endl;
exit(-);
} pNew->data =val;
PNODE q=p->pNext;
p->pNext =pNew;
pNew->pNext =q; return true;
} /*
将链表的pos位置的数据删除 ，删除的数据保存到 int*val变量中
*/ bool delete_list(PNODE pHead,int pos,int *pVal)
{
int i=;
PNODE p=pHead; //不需判断链表是否为空，不需判断pos是否满足链表长度要求等。。此部分用while和if全部搞定
while(NULL!=p->pNext &&i<pos-) //不能写成<=，否则出错
{
i++;
p=p->pNext;
}
if(i>pos- || NULL==p->pNext )
return false; PNODE q=p->pNext ;
*pVal=q->data ; //删除p后面的节点
p->pNext =p->pNext->pNext;
free(q);
q=NULL; return true;
} int main(){
PNODE pHead = NULL;//定义一个结构体指针变量
pHead = create_list();
printf("排序之前的数据是：\n");
printf_list(pHead);
sort_list(pHead);
//int arr[5] = {10,80,100,20,50};
// print_array(arr,5);
//sort_array(arr,5);
//sort_list(pHead);
printf("排序之后的数据是：\n");
printf_list(pHead);
//print_array(arr,5);
return ;
}