定义:n个节点离散分配,彼此通过指针相连,每个节点只有一个前驱节点,每个节点只有一个后续节点,首节点没有前驱节点,尾节点没有后续节点。
专业术语:
首节点(第一个有效节点,首节点的数据类型和头节点是一样的)
尾节点(最后一个有效节点)
头节点(在首节点之前,不存储有效数据、目的是为了方便对链表进行 *** 作)、
头指针(指向头节点的指针变量)
尾指针(指向尾节点的指针变量)
只需要一个参数,头指针,通过头指针可以推算出链表的所有信息,就可以通过这一个参数使用函数对链表进行 *** 作。
链表的优缺点:优点:空间没有限制;插入删除元素很快。
缺点:存取速度很慢。
链表节点定义的方式,链表结构体中包含的指针域类型和节点类型相同,指向一个链表节点的整体。
typedef struct Node { int data; struct Node *pNext; }NODE, *PNODE;
分类:
单链表,双链表(每一个节点有两个指针域)
循环链表(能通过任何一个节点找到其他所有的节点),非循环链表
下面进行算法实现:遍历,查找,清空,销毁,求长度,排序,删除节点,插入节点。
p->pNext 表示p所指向结构体变量中的pNext成员变量。
//方法1 r = p -> pNext; p -> pNext = q; q -> pNext = r; //方法2 q -> 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#include #include 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; 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); } //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; 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 0 int 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 // 1 return 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)) { 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循环中使用逗号表达式注意第二个条件,循环执行判断条件中慎用逗号运算符,表达式顺序的不同会导致不同的判定结果。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)