7.3.1 链表的概念
1、链表的结构
struct node{
typename data; //数据域
node* next ; //指针域
};
又分为带头结点和不带头结点，头结点一般称为head,data不存放任何内容，next指向第一个数据域有内容的东西
7.3.2使用malloc函数或new运算符为节点分配内存空间
1、使用malloc函数或new运算符为链表节点分配空间（推荐用new)
(1)maloc是c语言中stdlib.h用于申请动态内存的函数，返回类型是申请void类型的指针，参数是size_t，所以需要sizeof(int)之类的，然后再强制转换
申请失败返回空指针null
一般不会失败，申请太大以及无限申请的情况除外
2、new运算符
c++用来申请动态空间的运算符，返回类型同样是申请的同变量类型的指针；
写法：int *p = new int; 即 new + 类型名；
如果失败会启动异常机制，而不是返回NULL，同样，失败可能是申请太大空间
3、内存泄漏
（1）free(p) 同样在stdlib.h头文件下
实现两个效果：将指针变量p所指空间释放，同时将p指向Null
(2) delete(p)
实现效果与free一样
切记，必须成对出现，在一般考试例，分配的空间在程序结束时即被释放，并且内存大小一般够一道题使用，但是，从编程习惯上！一定要成对出现
4、链表的基本操作
1、创建链表
struct node{
int date;
node *next; // 指针域
};
记忆：三个指针，头指针，循环复制
//创建链表
void create(int array[]){
node *p, *pre, *head; // pre保存当前节点的前驱节点，head为头结点
head = new node; // 创建头结点
head->next = null; //头结点不需要数据域，指针域置为null
pre = head; //记录pre为head
for(int i = 0;i < 5;i++){
p = new head; //创建节点
//将array[i]赋值给新建的节点作为数据域，也可以scanf输入
p -> data = array[i];
p->next = null; //将新节点的指针域设置为null
pre->next = p; //前驱节点的指针域设为当前节点的地址
p = pre; //将pre设为p，作为下个节点的前驱节点
}
return head; //返回头结点指针
}
2、查找元素
查找有多少个x
记忆：计算器+while循环
int search(node *head,int x){
int count = 0; //计数器
node *p = head->next; //从第一个节点开始
while(p != null){ //只要没到链表结尾
if(p->date == x){ //当前节点的数据域为x，则count++
count++;
}
p = p->next； //指针移动到下一个节点
}
return count;
}
3、插入元素
x插入第3个位置，其实就是插入完成后，第三个元素位置是x
记忆：head开始，for循环找前位，创节点，改指针
void insert(node *head, int pos,int x){
node *p = head;
for(int i = 0;i < pos - 1;++I){
p = p->next; //pos - 1是为了到前一个节点
}
node *q = new node;
p->data = x; //新节点的数据域为x
q->next = p->next; //新节点的下一个节点指向原先插入位置的节点
p->next = q; //前一个位置的节点指向新节点
}
4、删除元素
思想：
第一点，存前驱，while循环，改指针；（否则移）
void del(node* head, int x){
node *p = head->next; //从第一个结点开始
node *pre = head; //per始终保存p的前驱节点的指针
while(p != null){
if(p->data == x){
pre->next = p->next;
delete(p);
p = pre->next;
}else{
pre = p;
p = p->next;
}
}
}
7.3.4 静态链表
静态链表
struct Node{
typename data;
int next; //指针域
}node;
注意：next是一个int型整数，存放下一个节点的地址
结构体类型名和结构体名字设成了不同，一般是可以相同的，但是有可能对他们排序，这时候相同sort就会编译错，所以不同
网友评论