数据结构(二) -- 数组和链表 (3)

创建头节点，首先要创建一个没有存储值的头节点，我们本身定义了 NODE 结构体，可以根据NODE类型动态分配一块内存空间

// 创建一个值域为空的头结点,给头指针分配内存 PNODE pHead = (PNODE)malloc(sizeof(PNODE)); // 头指针

创建新节点，需要根据定义的长度循环，这里的难点就是如何把新节点挂到链表尾部【这里还是要明确指针和指针变量的概念，这样会更好理解一些】
为了能让新创建的节点挂到尾部，我们直接使用pHead->pNext = pNew;
是不行的，这样只能最后添加一个，并且其他的都会被泄漏。这里我们使用一个站位尾节点来表示尾节点

PNODE pTail = pHead; // 站位尾节点,直接赋值给 pTail,这是栈内存分配； pTail->pNext = NULL; for循环{ // 1.保存值和指针，变成完整新节点 pNew->data = val; pNew->pNext = NULL; // 2.当前新节点追加到原来尾节点后面 pTail->pNext = pNew; // 3.新节点变成原来尾节点 pTail = pNew; }

为了便于理解，请先弄清楚，指针和指针变量区别，下图逐步讲解


 

2 遍历链表

遍历链表思路：
遍历链表只能通过头结点的 pNext 指针找到下一个节点，并循环到 pNext == NULL 为止，分别打印 值域的值即可。

// 通过头节点遍历后面节点 PNODE p = pHead->pNext; //获得首节点 while (p != NULL) { printf("data = %d \n",p->data); p = p->pNext; } printf("遍历完毕，退出\n"); return;

3 判断是否为空链表

判断是够为空链表，直接拿头结点的 pNext 指针取值判断是否为 NULL 即可

bool isEmpty_list(PNODE pHead) { if ((*pHead).pNext == NULL) { return false; }else{ return true; } }

4 求链表长度

求链表长度类似于遍历链表，这里主要是计算有效节点的个数，这个个数就是长度

int length_list(PNODE pHead) { PNODE p = pHead->pNext; int len = 0; while (p->pNext == NULL) { len++; p = p->pNext; } return len; }

5 插入节点



 

其实思路很简单，主要是吧 p指向节点的的pNext 指向 q, 然后q所指向的下个节点直接指向原来p所指向的节点。 伪代码如下： temp = p->pNext; p->pNext -> q; q->pNext = temp; 或者直接 q->pNext = P->pNext; P->pNext = q;

本方法代码实现

bool insert_list(PNODE pHead , int pos , int val){ // 判断位置是否合法 PNODE q = pHead; // 要插入的位置，如果是 <= 0,则直接插到最前面，如果是 pos = 1 就插入第一个后面,pos = n,就插到第 n 个后面 int i = 0; while (i < pos) { if (q->pNext == NULL) { printf("要插入的位置不合法;大于链表长度\n"); break; }else{ q = q->pNext; //要被插入的节点 i++; } } // 插入操作 PNODE p = (PNODE)malloc(sizeof(NODE)); if (p == NULL) { printf("动态分配内存失败\n"); exit(0); } p->data = val; // 前一个节点为q， 直接添加到 q 后面。 p->pNext = q->pNext; q->pNext = p; return true; }

6 删除节点

 



// 思路： // 想要删除后面的节点，直接让 p 的指针域指向下下个节点就完成了 // 这里的删除其实很方便，但是有个容易造成内存泄漏的误区 // 因为直接删除之后，我们就无法在拿到 p 后面的节点的地址，然后无法释放，最终内存泄漏 // 最终实现： temp = p->pNext; // 临时变量保存要删除节点地址 p->pNext = p->pNext-pNext; // p 的指针域指向下下个节点 free(temp); // 释放被删除节点内存

代码实现

bool delete_list(PNODE pHead , int pos , int * val){ // 找到要被删除的元素保存起来 PNODE p = pHead; int i = 0; while (i < pos - 1) { // 找到被删除节点的前一个节点 if (p->pNext == NULL) { break; } p = p->pNext; i++; } if (i < pos && p->pNext == NULL) { printf("你要删除的位置非法，此位置不在链表长度范围之内\n"); return false; } // 找到了要被删除的那个节点 PNODE t = p->pNext;; *val = t->data; // 把被删除节点的值传给外面 p->pNext = t->pNext; // 直接指向后面一个节点 free(t); // 释放被删除节点内存，防止内存泄漏 return true; }

7 链表排序

链表排序同数组不同，但很相似，都是把所有元素遍历然后找到相邻或者相反的值互换位置。