链表是线性结构的离散存储方式。

定义：n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。

郝斌

专业术语：

首节点（第一个有效节点，首节点的数据类型和头节点是一样的）

尾节点（最后一个有效节点）

头节点（在首节点之前，不存储有效数据、目的是为了方便对链表进行操作）、

头指针（指向头节点的指针变量）

尾指针（指向尾节点的指针变量）

只需要一个参数，头指针，通过头指针可以推算出链表的所有信息，就可以通过这一个参数使用函数对链表进行操作。

链表的优缺点：

优点：空间没有限制；插入删除元素很快。

缺点：存取速度很慢。

链表节点定义的方式，链表结构体中包含的指针域类型和节点类型相同，指向一个链表节点的整体。

typedef struct Node{int data;struct Node *pNext;}NODE, *PNODE;//为了统一链表的操作，我们可以这样定义链表typedef struct Data{char num[8];char name[8];int score;}ElemType;typedef struct Node{ElemType data;struct Node *pNode;}Node, *pNode;

分类：

单链表，双链表（每一个节点有两个指针域）

循环链表（能通过任何一个节点找到其他所有的节点），非循环链表

下面进行算法实现：遍历，查找，清空，销毁，求长度，排序，删除节点，插入节点。

p->pNext 表示p所指向结构体变量中的pNext成员变量。

/*在指针p指向的链表节点后面插入指针q指向的链表节点的两种方式*///方法1r = p -> pNext;p -> pNext = q;q -> pNext = r;//方法2q -> pNext = p -> pNext;p -> pNext = q;

删除指针p指向的链表节点之后的下一个链表节点，也就是把指针p指向的链表节点中的指针域指向下下一个节点，但是注意删除的节点要及时释放，否则会导致内存泄漏，C语言不会自动释放。。

//错误的写法p -> pNext = p -> pNext -> pNext;//错误的写法，释放了p指针指向的链表节点的下一个节点之后，下下一个节点同样找不到了。free(p->pNext);//正确的写法，先将需要释放的节点保存一下，删除操作之后再释放。r = p->pNext;p -> pNext = r->pNext;free (r);

我们对单链表进行相应功能函数的实现：

#include<stdio.h>#include<malloc.h>#include<stdbool.h>typedef struct Node{int data;struct Node * pNext;}NODE, *PNODE;PNODE create_list(void);void show_list(PNODE phead);bool is_emptylist(PNODE phead);int length_list(PNODE phead);//节点个数统计bool append_list(PNODE phead, int val);//追加bool insert_list(PNODE phead, int val, int port);//插入bool delete_list(PNODE phead, int* returnVal, int port);void sort_list(PNODE phead, bool mode);int main(void){PNODE pNode = NULL;int lengNum = 0;// int returnNum =0; /*关于指针的使用，直接初始化一个int值而不是int *去接受被删除的值 。*/pNode = create_list();show_list(pNode);if( is_emptylist(pNode) ){printf("链表为空！\n");}else{printf("链表不为空！\n");lengNum = length_list(pNode);printf("the Number of the link is %d \n", lengNum);}/*if(insert_list(pNode, 88, 3)){printf("插入成功！\n");}else{printf("插入失败！\n");}*///delete_list(pNode, &returnNum, 3);sort_list(pNode, 0);show_list (pNode);sort_list(pNode, 1);show_list (pNode);//printf("the delete number is %d \n", returnNum);// append_list(pNode, 7);return 0;}PNODE create_list(void){int nodeNum = 0;int fornum = 0;int val = 0;/* pNew 每次循环分配空间作为新的链表节点*//* pTail 一直指向链表的最后一个节点，初始化时pTail的指针域赋NULL*/PNODE phead = (PNODE)malloc(sizeof(NODE));if(phead == NULL){printf("链表头申请失败! \n");return 0;}PNODE pTail = phead;pTail ->pNext = NULL;printf("please enter the number of Node: ");scanf(" %d", &nodeNum);for(fornum = 1; fornum <= nodeNum; fornum++){printf("please enter the data of this node %d :", fornum);scanf(" %d", &val);PNODE pNew = (PNODE)malloc(sizeof(NODE));if(pNew == NULL){printf("新链表节点申请失败! \n");return 0;}pTail ->pNext = pNew;pNew ->data = val;pNew ->pNext = NULL;pTail = pNew;}return phead;}void show_list(PNODE phead){PNODE pShow = phead ->pNext;int nodenum = 1;while(pShow != NULL){printf("The data of Node %d is: %d \n", nodenum, pShow->data);pShow = pShow ->pNext;nodenum ++;}printf("\n");}bool is_emptylist(PNODE phead){PNODE pShow = phead ->pNext;if(pShow == NULL){return true;}else{return false;}}int length_list(PNODE phead){PNODE pShow = phead ->pNext;int lengthNum = 0;while(pShow != NULL){lengthNum ++;pShow= pShow->pNext;}return lengthNum;}bool insert_list(PNODE phead, int val, int port){/*插入操作要考虑插入到第一个节点之前的情况，一开始要指向头节点*/PNODE pShow = phead;#if 0int nodeNum = 0;int i = 0;if(is_emptylist(phead)){printf("链表为空！\n");return false;}nodeNum = length_list(phead);if(nodeNum < port-1){printf("参数错误！\n");return false;}while(i < port-1 ){pShow = pShow->pNext;i ++;}PNODE pNew = (PNODE)malloc(sizeof(NODE));pNew ->pNext = pShow ->pNext;pShow ->pNext = pNew;pNew ->data = val;#endif // 0#if 1/*******郝斌版本*这种方式是不需要判断列表为空，也不需要求出列表长度******/PNODE pSwap = NULL;PNODE pNew = (PNODE)malloc(sizeof(NODE));int j = 0;while ((pShow != NULL) && (j < port -1)){pShow = pShow->pNext;j++;}if(j > port -1|| pShow==NULL){return false;}pSwap = pShow ->pNext;pShow ->pNext = pNew;pNew -> pNext = pSwap;pNew ->data = val;#endif // 1return true;}bool append_list(PNODE phead, int val){PNODE pShow = phead;PNODE pTail = NULL;PNODE pNew = (PNODE)malloc(sizeof(NODE));if (pNew == NULL){printf("append_list 新节点申请失败！\n");return false;}while (pShow != NULL){pTail = pShow;pShow = pShow ->pNext;}pTail ->pNext = pNew;pNew->data = val;pNew->pNext = NULL;return true;}bool delete_list(PNODE phead, int *returnVal, int port){PNODE pShow = phead ->pNext;int fornum = 1;PNODE pDeleteNode = NULL;while( (pShow != NULL) &&(fornum < port-1 ) ){pShow = pShow->pNext;fornum ++;}if ((fornum > port - 1) || (pShow->pNext == NULL)) /*将指针指向将要删除的节点的前一个节点，判断目标节点pShow->pNext是不是空节点*/{return false;}pDeleteNode = pShow->pNext;*returnVal = pDeleteNode ->data;pShow ->pNext = pDeleteNode ->pNext;free(pDeleteNode);pDeleteNode = NULL;return true;}void sort_list(PNODE phead, bool mode){int nodeNum = length_list(phead);int i = 0;int j = 0;int swapNum = 0;PNODE pnode = NULL;PNODE qnode = NULL;if(mode == 0)/* 从小到大排列 */{for(i = 0, pnode = phead ->pNext; i < nodeNum - 1; i++, pnode = pnode ->pNext){for(j = i + 1, qnode = pnode ->pNext; j < nodeNum; j++, qnode = qnode ->pNext){if((pnode->data) > (qnode ->data)){swapNum = pnode->data;pnode ->data = qnode ->data;qnode ->data = swapNum;}}}}else if(mode == 1) /*从大到小排列*/{for(i = 0, pnode = phead ->pNext; i < nodeNum - 1; i++, pnode = pnode ->pNext){for(j = i + 1, qnode = pnode ->pNext; j < nodeNum; j++, qnode = qnode ->pNext){if((pnode->data) < (qnode ->data)){swapNum = pnode->data;pnode ->data = qnode ->data;qnode ->data = swapNum;}}}}return;}

注意排序函数中使用了逗号运算符，其作用是将若干表达式连接起来。它的优先级是所有运算符中最低的，结合方向是自左至右。 逗号表达式： 一般形式：表达式1，表达式2，表达式3，......表达式n ​ 求解过程：先计算表达式1的值，再计算表达式2的值，......一直计算到表达式n的值。最后整个表达式的值是表达式n的值。

在for循环中使用逗号表达式注意第二个条件，循环执行判断条件中慎用逗号运算符，表达式顺序的不同会导致不同的判定结果。

王卓