/*
?? ?2021年11月17日20:49:52
?? ?目的:鏈表的創(chuàng)建與實(shí)現(xiàn)
*/


#include<stdio.h>
#include<malloc.h>

typedef struct node
{
?? ?int data;
?? ?node* pNext;
};

node* inint();
void append(node*, int);
bool insert(node*, int, int);
bool delte(node*, int, int*);
void traverse(node*);
int length(node*);
void sort(node*);

int main(void)
{
?? ?node* pHead = inint();
?? ?append(pHead, 0);
?? ?append(pHead, 1);
?? ?append(pHead, 21);
?? ?append(pHead, 12);
?? ?append(pHead, 96);
?? ?append(pHead, 54);
?? ?
?? ?traverse(pHead);
?? ?
?? ?insert(pHead, 2, 108);
?? ?traverse(pHead);
?? ?
?? ?int val;
?? ?if (delte(pHead, 3, &val))
?? ??? ?printf("鏈表取出成功，取出元素為%d\n", val);
?? ?else
?? ??? ?printf("fail\n");
?? ?
?? ?sort(pHead);
?? ?traverse(pHead);
?? ?
?? ?return 0;
}

node* inint()
{
?? ?node* pHead = (node*)malloc(sizeof(node));
?? ?pHead->pNext = NULL;
?? ?return pHead;
}

void append(node* pHead, int val)
//要把元素新節(jié)點(diǎn)掛在最后一個(gè)結(jié)點(diǎn)的后面，
//就是要求得，最后一個(gè)結(jié)點(diǎn)，的地址，
//最后一個(gè)結(jié)點(diǎn)就是指針域?yàn)镹ULL的結(jié)點(diǎn)，當(dāng)指針域?yàn)镹ULL時(shí)停止。
//那么p = pHead 是否需要pHead->pNext,
//不可以,否則p = p1,如果p1不存在,那么一直就掛不上去,
{
?? ?node* p = pHead;
?? ?while (NULL != p->pNext)
?? ??? ?p = p->pNext;
?? ?node* pNew = (node*)malloc(sizeof(node));
?? ?pNew->data = val;
?? ?pNew->pNext = NULL;
?? ?p->pNext = pNew;
?? ?return;
}

void traverse(node* pHead)
{
?? ?node* p = pHead->pNext;
?? ?while (NULL != p)
?? ?{
?? ??? ?printf("%d\t", p->data);
?? ??? ?p = p->pNext;
?? ?}
?? ?printf("\n");
?? ?return;
}

bool insert(node* pHead, int ins, int val)
{
?? ?int i = 0;
?? ?node* p = pHead;
?? ?// i = 0 , p = p0, i = 1,
?? ?//可以得到,i = ins-2,
?? ?//要理解,為啥,ins-2就是ins前面的一個(gè)結(jié)點(diǎn).
?? ?//i = 0,p0,n = 0, i = 1
?? ?while (NULL != p && i < ins - 1)
?? ?{
?? ??? ?p = p->pNext;
?? ??? ?i++;
?? ?}
?? ?
?? ?if (NULL == p || i > ins - 1)
?? ??? ?return false;

?? ?node* pNew = (node*)malloc(sizeof(node));
?? ?pNew->pNext = p->pNext;
?? ?pNew->data = val;
?? ?p->pNext = pNew;
?? ?return true;
}

bool delte(node* pHead, int del,int* val)
{
?? ?int i = 0;
?? ?node* p = pHead;
?? ?//與ins相同得到的均是該位置前面的結(jié)點(diǎn)的位置,
?? ?//不同之處在于,delte需要判斷,該結(jié)點(diǎn)的指針域是否為NULL;
?? ?//為啥在i =? del-2處為del-1位置的元素.
?? ?//i = 0 時(shí)為p1?
?? ?//del = 1 ,i = 0 , p = p0,
?? ?//i = 0, p 0,i = n , p (n),
?? ?//i = 0, p 0,i = n ,p(n),
?? ?//del = 2,i <1,
?? ?//i = del-1,停止運(yùn)行,p(del-1);
?? ?while (NULL != p->pNext && i < del- 1)//i = del-1,p = p(del-1)
?? ?{
?? ??? ?p = p->pNext;// p
?? ??? ?i++;//i = del-2
?? ?}

?? ?if (NULL == p || i > del - 1)
?? ??? ?return false;

?? ?node* pDel = p->pNext;
?? ?*val = pDel->data;
?? ?p->pNext = pDel->pNext;
?? ?free(pDel);
?? ?pDel = NULL;
?? ?return true;
}

int length(node* pHead)
{
?? ?int num = 0;//num = 0;
?? ?node* p = pHead->pNext;//p = p0;
?? ?while (NULL != p)//
?? ?{
?? ??? ?p = p->pNext;
?? ??? ?num++;
?? ?}
?? ?printf("%d\n", num);
?? ?return num;
}

void sort(node* pHead)
{
?? ?int i, j;
?? ?node* t1;
?? ?node* t2;
?? ?int len = length(pHead);
?? ?//i = 0,那么為啥不是 t1 = p0;
?? ?for(i = 0,t1 = pHead->pNext;i<len-1;i++,t1= t1->pNext)
?? ??? ?//i= 0,t1 = p1,
?? ??? ?// i = len-2,t1 = p(len-1),
?? ??? ?//i = len-1,t1 = p(len);//最后一個(gè)值.
?? ??? ?//與數(shù)組一樣,下標(biāo)為0,指向p1.
?? ??? ?for(j = 0,t2 = pHead->pNext;j<len-i-1;j++,t2 = t2->pNext)
?? ??? ??? ?if (t2->data < t2->pNext->data)
?? ??? ??? ?{
?? ??? ??? ??? ?int t = t2->pNext->data;
?? ??? ??? ??? ?t2->pNext->data = t2->data;
?? ??? ??? ??? ?t2->data = t;
?? ??? ??? ?}
?? ?return;

}

/*
?? ?————————————————————————————
?? ?0?????? 1?????? 21????? 12????? 96????? 54
?? ?0?????? 108???? 1?????? 21????? 12????? 96????? 54
?? ?鏈表取出成功，取出元素為1
?? ?6
?? ?108???? 96????? 54????? 21????? 12????? 0
?? ?————————————————————————————
*/

感謝郝斌老師