/*-------------------------------------------------------------------------------------------------------------
all by chenge
1.初始化链表
2.创建链表，返回头指针
3.打印链表
4.获取长度
5.清空链表（这里有问题，清空之后表头地址变了，待改善）
6.获取第n个结点的data
7.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回1，否则返回0
8.排序单链表,降序,(算法慢，待优化)
其他操作基本上以此类推可得
------------------------------------------------------------------------------------------------------------------*/
#include <stdio.h>
#include<stdlib.h>
typedef int type;
#define LEN sizeof(struct node)
typedef struct node
{
type data;
struct node *next;
}node;
/*------------------------------------------------------------------------------------------------------------
-------------------------------------初始化链表---------------------------------------------------------*/
void initList(node ** phead){
*phead = NULL;
printf("initList函数执行，初始化成功\n");
}
/*------------------------------------------------------------------------------------------------------------------
-------------------------------------创建链表，返回头指针-------------------------------------------------*/
node * creatList(node * head){
node *p, *pl;
head=p=(node * )malloc(LEN);
printf("creatList函数执行,请输入链表数据成员,以0结束\n");
scanf("%d",&p->data);/*头结点的数据成员*/
while(p->data!=0) /*给出0结束条件,退出循环*/
{
pl=p;
p=(node * )malloc(LEN);
scanf("%d",&p->data);/*中间结点数据成员*/
if(p->data!=0){
pl->next=p;/*中间结点的指针成员值*/
}else{
break;
}
}
pl-> next=NULL;/*尾结点的指针成员值*/
return head;
}
/*--------------------------------------------------------------------------------------------------------
-----------------------------------------------打印链表------------------------------------------------*/
void printList(node *head){
if(NULL == head) //链表为空
{
printf("printList函数执行，链表为空\n");
}
else
{
while(NULL != head)
{
printf("%d ",head->data);
head = head->next;
}
printf("\n");
}
}
/*------------------------------------------------------------------------------------------------------------
-------------------------------------------------获取长度-------------------------------------------------*/
int getLength(node * head){
int length = 0;
if(NULL == head) //链表为空
{
printf("链表为空\n");
}
else
{
while(NULL != head)
{
length ++ ;
head = head->next;
}
}
printf("length is : %d\n",length);
return length;
}
/*------------------------------------------------------------------------------------------------------------
-------------------------------------------------清空链表-------------------------------------------------*/
void cleanList(node **phead)
{
node *pNext; //定义一个与phead相邻节点
if(*phead == NULL)
{
printf("clearList函数执行，链表为空\n");
return;
}
while(*phead != NULL)
{
pNext = (*phead)->next;//保存下一结点的指针
free(*phead);
*phead = pNext; //表头下移
}
printf("clearList函数执行，链表已经清除\n");
}
/*------------------------------------------------------------------------------------------------------------
----------------------------------------获取第n个结点的data-----------------------------------------*/
type getdatabyN(node * head,int n){
int i=0;
if(n <= 0)
{
printf("getdatabyN函数执行，n值非法\n");
return 0;
}
if(head == NULL)
{
printf("getdatabyN函数执行，链表为空\n");
return 0;
//exit(1);
}
while(head !=NULL)
{
++i;
if(i == n)
{
break;
}
head = head->next; //移到下一结点
}
if(i < n) //链表长度不足则退出
{
printf("getElement函数执行，pos值超出链表长度\n");
return 0;
}
return head->data;
}
/*---------------------------------------------------------------------------------------------------------------
--向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回1，否则返回0 ---*/
int insertList(node **pNode, int pos, type elemInserted)
{
int i = 0;
node *pInserted,*pTemp, *pLast;
if(NULL == *pNode)
{
printf("insertList函数执行，链表为空\n");
return 0;
}
if(elemInserted < 1)
{
printf("insertList函数执行，elemInserted值非法\n");
return 0;
}
if(pos < 1)
{
printf("insertList函数执行，pos值非法\n");
return 0;
}
pTemp = *pNode; //把*pNode先赋值给pTemp，后面的操作（例如循环链表到最后一个节点）主要是对pTemp进行操作，否则返回*pNode的时候，将返回链表*pNode在当前指针后面的部分，而不是整个链表。
//因为pTemp与*pNode指向同一个链表，所以对pTemp进行节点改动即是对*pNode作改动
pInserted = (node *)malloc(sizeof(node));
pInserted->data = elemInserted;
pInserted->next = NULL; //先赋值为null
//循环链表至pos节点
while(pTemp != NULL)
{
i++;
if(i == pos)
{
pLast->next = pInserted; //让上一个节点的next指向插入节点
pInserted->next = pTemp; //让插入节点的next指向下一节点
break;
}
pLast = pTemp; //记住上一个节点的位置
pTemp = pTemp->next;
}
printf("在%d插入%d得到",pos,elemInserted);
return 1;
}
/*------------------------------------------------------------------------------------------------------------
--------------------------------------------排序单链表,降序--------------------------------------------*/
int sortList(node **pnode)
{
int p,k,i,Listsize;
node *pTemp;
node *pCurr, *pLast;
if(NULL == *pnode)
{
printf("sortList函数执行，链表为空\n");
return 0;
}
pTemp = *pnode;
Listsize = getLength(*pnode);
//循环: 用for循环来取代指针循环，因为指针循环一次后，下次起始的指针将自动转到下一节点，而我们还想从第一个元素开始
for( i=0; i < Listsize; i++)
{
pCurr = pLast = pTemp;
for(k=0; k < Listsize-i; k++)
{
p = 0;
if(pLast->data < pCurr->data)
{
p = pLast->data;
pLast->data = pCurr->data;
pCurr->data = p;
}
pLast = pCurr;
pCurr = pCurr->next;
}
}
printf("sortList函数执行,排序成功");
}
/*--------------------------------------*/
/*-----------------主函数：测试---------------*/
int main()
{
node * head;
initList(&head); //初始化
head = creatList(head); //建表
printList(head); //印表
getLength(head); //多长
insertList(&head,3,15); //插数
printList(head); //印表
sortList(&head); //排序
printList(head); //印表
cleanList(&head); //清空
printList(head); //印表
}