用什么做视频网站比较好的,网页设计基础填空题及答案,蛋糕店网页设计免费模板,遵化市有做奇麟网站的吗链表基础
1、链表的理论基础
1#xff09;基础#xff1a;
链表#xff1a;通过指针串联在一起的线性结构#xff0c;每个节点由两部分组成#xff0c;一个是数据域#xff0c;一个是指针域#xff08;存放指向下一个节点的指针#xff09;#xff0c;最后一个指针…链表基础
1、链表的理论基础
1基础
链表通过指针串联在一起的线性结构每个节点由两部分组成一个是数据域一个是指针域存放指向下一个节点的指针最后一个指针域指向null(空指针的意思)。
链表的入口节点称为链表的头结点也就是head。 2)链表类型
链表包括单链表、双链表、循环链表
单链表指针域只能指向节点的下一个节点。
双链表既可以向前查询也可以向后查询。 循环链表链表首尾相连循环链表可以解决约瑟夫环的问题。 3链表的存储方式
数组在内存中是连续分布的但是链表在内存中并不是连续分布的链表通过指针域的指针连接在内存中的各个节点。例如这个链表起始节点为2 终止节点为7 各个节点分布在内存的不同地址空间上通过指针串联在一起。 4链表的定义
这个单向链表中正是因为我们定义了节点的构造函数指明了可以把x丢给val才可以在初始化的时候直接赋值。
//单链表
struct ListNode{int val;//数据ListNode* next;//指向下一个节点的指针ListNode(int x):val(x),next(NULL){} //节点构造函数
};
//为什么要自己写构造函数呢c可以自己生成构造函数
//通过自己定义构造函数初始化节点
ListNode* head new ListNode(5);
//使用默认构造函数初始化节点不能直接给变量赋值!!
ListNode* head new ListNode;
head-val 5;
5链表的操作
链表中要注意的就是是否更改原来指针由项目引发的思考不得不引入值传递和指针传递
**传递值**如果传递的是基本数据类型或结构体而不是指针则函数内对形参的修改不会影响外部的实际参数。
#include stdio.hvoid modifyValue(int x) {x x 1; // 修改的是 x 的副本不会影响外部的实际参数
}int main() {int a 5;modifyValue(a);printf(%d\n, a); // 输出 5a 没有被修改return 0;
}
**传递指针**如果传递的是指针函数内对指针所指向的数据的修改会影响到外部的实际参数。但修改指针本身的值不会影响外部的指针。
#include stdio.hvoid modifyPointer(int* ptr) {*ptr *ptr 1; // 修改指针所指向的数据会影响外部的实际参数ptr ; // 修改指针本身的值不会影响外部的实际参数
}int main() {int b 10;int* p b;modifyPointer(p);printf(%d\n, *p); // 输出 11p 所指向的数据被修改return 0;
} 递值时函数内的修改不会影响外部的实际参数。 传递指针时函数内对指针所指向的数据的修改会影响外部的实际参数但修改指针本身的值不会影响外部的指针。
1.打印链表
为了保险起见还是可以在函数里面用临时变量保存链表值
void SlistPrint(ListNode *phead){ListNode *cur phead;while(!cur){printf(%d-, cur-data);cur cur- next;}printf(NULL\n);
}2.清空链表
好家伙不传入**pehead就要报错 //一个结点的定义
typedef struct ListNode{int val;ListNode* next;//ListNode(int x):val(x),next(NULL){};//重构函数
}ListNode;//因为要改变外部链表头的值所以要传入**
//pphead 表示一个 ListNode 结构体的对象而不是一个指针。在你的 SListClear 函数中*pphead NULL; 尝试将一个结构体对象设置为 NULL这是不合法的。
//如果你的目的是通过函数清空链表并将外部传递的链表头指针设置为 NULL你应该使用指向指针的指针即 ListNode** pphead并在函数内部通过解引用两次来修改外部传递的链表头指针的值。
void SListClear(ListNode **pphead)//**PPhead指向指针的指针
{ListNode *cur *pphead;while(!cur){ListNode* temp cur-next;free(cur);cur temp;}*pphead NULL;
}int main(){ListNode* head (ListNode*)malloc(sizeof(ListNode));head-val 1;head-next (ListNode*)malloc(sizeof(ListNode));head-next-val 2;head-next-next NULL;SListClear(head);//注意这里是相当于 **head// 在这里 head 已经被设置为 NULL链表被清空if (head NULL) {printf(List is empty\n);}system(pause); return 0;
}
3.创建结点
typedef struct ListNode{int val;ListNode* next;ListNode(int x):val(x),next(NULL){};//重构函数 C可以直接写重构函数
}ListNode;//等效于直接 ListNode* node new ListNode(val);
ListNode* CreateListNode(int x){ListNode* NewNode (ListNode*)malloc(sizeof(ListNode));ListNode-val x;ListNode-next NULL;return NewNode;
}
3.删除节点
比如删除D节点
首先将C节点的next指针指向E然后再手动释放D节点py有自己的内存回收机制不用手动释放但是c/c最好手动释放特别注意因为单链表的只能指向下一个节点删除某个节点的时候指针是在这个节点前一个节点的位置的。 typedef struct ListNode{int val;ListNode* next;ListNode(int x):val(x),next(NULL){};
}ListNode;ListNode* delete(ListNode * node){if(node-next!NULL node-next-next!NULL){node-next node-next-next;}return node;
}4、添加节点
在C和D中添加节点让C的指针域指向F再把F的指针域指向D。添加不需要释放内存
链表的增添和删除都是O1操作也不会影响到其他的节点但是查找的时间复杂度可能是O(n)(一个一个next指针进行查找)。
typedef struct ListNode{int val;ListNode* next;ListNode(int x):val(x),next(NULL){};
}ListNode;ListNode* add(ListNode * node,int val){ListNode* tmp new ListNode(val);temp-next node-next;node-next temp;return node;
}4.数组和链表的对比
