Part 1.完成單向鏈表，并完成下面功能

1.單鏈表節點創建

鏈表是物理空間上不連續的一個結構，需要創建一個next作為指向下一個節點的指針，所以需要建立一個結構體包含數據域，next指針域，記錄長度的數據域。因為長度只有頭節點可以儲存，所以需要建立一個聯合體，head訪問len，普通節點訪問data。

typedef struct Node
{//結構體嵌套共用體union{//普通節點數據域datatype data;//頭結點數據域：鏈表長度int len;};//指針域struct Node *next;
}*linklist;linklist create_node(int flag)
{linklist s = (linklist)malloc(sizeof(struct Node));if(NULL == s){return NULL;}if(flag == 1)//頭節點s->len = 0;else if(flag == 0)//普通節點s->data = 0;s->next = NULL;return s;
}

2.單鏈表的頭插

鏈表的插入需要檢查鏈表是否創建完成，因為每個節點空間不連續，所以得單獨創建。

頭插只需要將需要插入的數據的next指向原第一個節點，再將頭節點的next指向新節點即可。

int head_insert(linklist head,datatype element)
{if(NULL == head)//檢查鏈表是否創建完成return Faulse;linklist s = create_node(0);//創建普通數據節點if(NULL == s)return Faulse;s->data = element;s->next = head->next;head->next = s;head->len++;return Success;
}

3.單鏈表頭刪

需要將頭節點指向第二個節點（p->next->next)即可，然后釋放p->第一個節點

int head_delete(linklist head)
{if(NULL == head || head->len == 0)return Faulse;linklist del = head->next;head->next = del->next;free(del);del = NULL;head->len--;return Success;
}

4.單鏈表的尾插

因為鏈表的最后一個節點都是指向NULL，所以只需要循環尋找最后一個節點，然后將最后一個節點指向新節點，新節點指向NULL即可

int rear_insert(linklist head,datatype element)
{if(NULL == head)return Faulse;linklist s = create_node(0);if(NULL == s)return Faulse;s->data = element;linklist p = head;while(p->next != NULL)//循環尋找原最后節點p=p->next;p->next = s;head->len++;return Success;
}

5.單鏈表遍歷

只需要循環輸出p->data(數據域)，然后p = p->next往下一個節點即可完成循環輸出遍歷

int output(linklist head)
{if(NULL == head)return Faulse;linklist p = head->next;while(p != NULL){printf("%d\t",p->data);p=p->next;}printf("\n");
}

6.單鏈表按位置查找

需要判斷給的值是否大于長度，然后循環從0到輸入的位置，進行p=p->next下移，然后輸出即可

int position_select(linklist head,int position)
{if(NULL == head || position > head->len+1 || position < 1)return Faulse;linklist p = head;for(int i = 0; i < position; i++)p = p->next;printf("%d個位置是：%d\n",position,p->data);return Success;
}

7.單鏈表按位置刪除

和按位置查找一樣，然后循環從0到輸入的位置，進行p=p->next下移，然后使用尾刪即可。

int position_delete(linklist head,int position)
{if(NULL == head || position > head->len+1 || position < 1)return Faulse;linklist p = head;for(int i = 0; i < position-1; i++)p=p->next;linklist del = p->next;p->next = del->next;free(del);head->len--;return Success;
}

8.單鏈表按位置修改

和按位置查找一樣，然后循環從0到輸入的位置，進行p=p->next下移，然后修改p->data修改數據域即可。

int position_change(linklist head,int position,datatype element)
{if(NULL == head || position > head->len+1 || position < 1)return Faulse;linklist p = head;for(int i = 0; i < position; i++)p = p->next;p->data = element;return Success;
}

9.單鏈表按元素查找

通過for循環，從第一個節點到最后一個節點進行和輸入值對比，在每次循環記得將p下移，找到輸入值的時候，輸出i即可，既是第i個節點。

int element_select(linklist head,datatype element)
{if(NULL == head)return Faulse;linklist p = head;for(int i = 1; i <= head->len; i++){p = p->next;if(p->data == element)return i;else if(i == head->len+1)printf("沒有這個數\n");}
}

10.單鏈表按元素修改

和按元素查找相似，從第一個節點到最后一個節點進行和輸入值對比，然后找到后，將data數據域修改即可。

int element_change(linklist head,datatype element,datatype changeelement)
{if(NULL == head)return Faulse;linklist p = head;for(int i = 1; i <= head->len; i++){p = p->next;if(p->data == element)		p->data = changeelement;		else if(i == head->len+1)printf("沒有這個數\n");}return Success;
}

11.單鏈表按元素刪除

可以直接在函數里調用元素尋找函數，將返回的地址值，然后賦給按位置刪除函數，刪除即可。

int element_delete(linklist head,datatype element)
{if(NULL == head)return Faulse;int i = element_select(head,element);position_delete(head,i);return Success;
}

12.單鏈表逆置

int reverse(linklist head)
{if(NULL == head)return Faulse;linklist p = head->next;head->next = NULL;for(int i = 0; i < head->len; i++){linklist temp = p;p = p->next;temp->next = head->next;head->next = temp;}return Success;
}

13.單鏈表排序

運用了冒泡排序的基礎模板，只不過內部的交換變成了節點之間的互相連接。交換原理是：1.定義一個s指向p->next(記錄第二個節點)

2.p就能指向p->next->next(第一個節點指向第三個節點)

3.s->next = p（將第二個節點指向第一個節點）

4.p的上一個節點需要指向第二個節點

按上面四步可以完成交換值，但是因為單項鏈表沒辦法調用上一個節點，所以需要定義p（原上一個節點），p->next（原p節點），s = p->next->next（原第二個節點），即每個節點往前移一個節點進行提前比較，換值即可。然后在每次換之后將p往下移（p = p->next）即可（因為鏈表沒使用到循環的i和j，所以步長需要自己增加）。

int sort(linklist head)
{if(NULL == head || head->len <= 1)return Faulse;linklist p = head;printf("%d\n",head->len);for(int i = 1; i < head->len; i++){p = head;for(int j = 0; j < head->len-i; j++){if(p->next->data > p->next->next->data){linklist s = p->next->next;//交換p->next->next = s->next;s->next = p->next;p->next = s;p = p->next;//步增}elsep = p->next;}}return Success;
}

14.單鏈表查找倒數第n個節點

尋找倒數第n個值，需要定義兩個指針，指針之間相差n個節點距離，然后兩個一起后移，當后面一個指針到末尾了，前一個指針就指向倒數第n個值了

int rearnum_select(linklist head,int num)
{	if(NULL == head)return Faulse;linklist p = head;linklist q = head;for(int i = 0; i < num; i++)//令兩個指針相隔n{q = q->next;}while(q != NULL)//一起后移，到底輸出前一個指針{p = p->next;q = q->next;}printf("倒數第%d個數是:%d\n",num,p->data);
}