/*-------------------------------------------------------------------------------------------------------------
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); //印表
}