/*-------------------------------------------------------------------------------------------------------------
all by chenge
1.初始化鏈表
2.創(chuàng)建鏈表，返回頭指針
3.打印鏈表
4.獲取長度
5.清空鏈表（這里有問題，清空之后表頭地址變了，待改善）
6.獲取第n個(gè)結(jié)點(diǎn)的data
7.向單鏈表中第pos個(gè)結(jié)點(diǎn)位置插入元素為x的結(jié)點(diǎn)，若插入成功返回1，否則返回0
8.排序單鏈表,降序,(算法慢，待優(yōu)化)
其他操作基本上以此類推可得
------------------------------------------------------------------------------------------------------------------*/
#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函數(shù)執(zhí)行，初始化成功\n");
}
/*------------------------------------------------------------------------------------------------------------------
-------------------------------------創(chuàng)建鏈表，返回頭指針-------------------------------------------------*/
node * creatList(node * head){
node *p, *pl;
head=p=(node * )malloc(LEN);
printf("creatList函數(shù)執(zhí)行,請(qǐng)輸入鏈表數(shù)據(jù)成員,以0結(jié)束\n");
scanf("%d",&p->data);/*頭結(jié)點(diǎn)的數(shù)據(jù)成員*/
while(p->data!=0) /*給出0結(jié)束條件,退出循環(huán)*/
{
pl=p;
p=(node * )malloc(LEN);
scanf("%d",&p->data);/*中間結(jié)點(diǎn)數(shù)據(jù)成員*/
if(p->data!=0){
pl->next=p;/*中間結(jié)點(diǎn)的指針成員值*/
}else{
break;
}
}
pl-> next=NULL;/*尾結(jié)點(diǎn)的指針成員值*/
return head;
}
/*--------------------------------------------------------------------------------------------------------
-----------------------------------------------打印鏈表------------------------------------------------*/
void printList(node *head){
if(NULL == head) //鏈表為空
{
printf("printList函數(shù)執(zhí)行，鏈表為空\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; //定義一個(gè)與phead相鄰節(jié)點(diǎn)
if(*phead == NULL)
{
printf("clearList函數(shù)執(zhí)行，鏈表為空\n");
return;
}
while(*phead != NULL)
{
pNext = (*phead)->next;//保存下一結(jié)點(diǎn)的指針
free(*phead);
*phead = pNext; //表頭下移
}
printf("clearList函數(shù)執(zhí)行，鏈表已經(jīng)清除\n");
}
/*------------------------------------------------------------------------------------------------------------
----------------------------------------獲取第n個(gè)結(jié)點(diǎn)的data-----------------------------------------*/
type getdatabyN(node * head,int n){
int i=0;
if(n <= 0)
{
printf("getdatabyN函數(shù)執(zhí)行，n值非法\n");
return 0;
}
if(head == NULL)
{
printf("getdatabyN函數(shù)執(zhí)行，鏈表為空\n");
return 0;
//exit(1);
}
while(head !=NULL)
{
++i;
if(i == n)
{
break;
}
head = head->next; //移到下一結(jié)點(diǎn)
}
if(i < n) //鏈表長度不足則退出
{
printf("getElement函數(shù)執(zhí)行，pos值超出鏈表長度\n");
return 0;
}
return head->data;
}
/*---------------------------------------------------------------------------------------------------------------
--向單鏈表中第pos個(gè)結(jié)點(diǎn)位置插入元素為x的結(jié)點(diǎn)，若插入成功返回1，否則返回0 ---*/
int insertList(node **pNode, int pos, type elemInserted)
{
int i = 0;
node *pInserted,*pTemp, *pLast;
if(NULL == *pNode)
{
printf("insertList函數(shù)執(zhí)行，鏈表為空\n");
return 0;
}
if(elemInserted < 1)
{
printf("insertList函數(shù)執(zhí)行，elemInserted值非法\n");
return 0;
}
if(pos < 1)
{
printf("insertList函數(shù)執(zhí)行，pos值非法\n");
return 0;
}
pTemp = *pNode; //把*pNode先賦值給pTemp，后面的操作（例如循環(huán)鏈表到最后一個(gè)節(jié)點(diǎn)）主要是對(duì)pTemp進(jìn)行操作，否則返回*pNode的時(shí)候，將返回鏈表*pNode在當(dāng)前指針后面的部分，而不是整個(gè)鏈表。
//因?yàn)閜Temp與*pNode指向同一個(gè)鏈表，所以對(duì)pTemp進(jìn)行節(jié)點(diǎn)改動(dòng)即是對(duì)*pNode作改動(dòng)
pInserted = (node *)malloc(sizeof(node));
pInserted->data = elemInserted;
pInserted->next = NULL; //先賦值為null
//循環(huán)鏈表至pos節(jié)點(diǎn)
while(pTemp != NULL)
{
i++;
if(i == pos)
{
pLast->next = pInserted; //讓上一個(gè)節(jié)點(diǎn)的next指向插入節(jié)點(diǎn)
pInserted->next = pTemp; //讓插入節(jié)點(diǎn)的next指向下一節(jié)點(diǎn)
break;
}
pLast = pTemp; //記住上一個(gè)節(jié)點(diǎn)的位置
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函數(shù)執(zhí)行，鏈表為空\n");
return 0;
}
pTemp = *pnode;
Listsize = getLength(*pnode);
//循環(huán): 用for循環(huán)來取代指針循環(huán)，因?yàn)橹羔樠h(huán)一次后，下次起始的指針將自動(dòng)轉(zhuǎn)到下一節(jié)點(diǎn)，而我們還想從第一個(gè)元素開始
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函數(shù)執(zhí)行,排序成功");
}
/*--------------------------------------*/
/*-----------------主函數(shù)：測(cè)試---------------*/
int main()
{
node * head;
initList(&head); //初始化
head = creatList(head); //建表
printList(head); //印表
getLength(head); //多長
insertList(&head,3,15); //插數(shù)
printList(head); //印表
sortList(&head); //排序
printList(head); //印表
cleanList(&head); //清空
printList(head); //印表
}