7.3.1 链表的概念

struct node
{typename data;  //数据域node *next;   	//指针域
};  

带头结点的链表，链表实际的存储方式

7.3.2 使用new运算符为链表结点分配内存空间

其结构为:new+类型名

typename *p=new typename; 	//typenam类型的指针
int *p=new int;			//int类型的指针
node *p=new node;   //node类型的指针

如果new申请失败，则使用c++异常处理机制

int *p=new int[100000000000000000];  //new申请长度较大的数组，会直接退出程序

内存泄漏：

delete函数

delete(p);

使用delete的两个作用：

7.3.3 链表的基本操作：

1.创建链表：

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
struct node   //链表结点
{int data;node* next;
};node* Create(int Array[])  //创建链表函数
{node *p,*pre,*head;   //pre为先驱结点，head为头结点head = new node;   //创建头结点head->next=NULL;        //头结点不需要数据域，指针域设为NULLpre=head;   //记录pre为headfor(int i=0; i<5; i++){p=new node;  //新建结点,不要忘记设置新的结点p->data=Array[i];p->next=NULL;pre->next=p;pre=p;}return head;
}
int main()
{int Array[5]={5,2,3,42,2};node *L=Create(Array);L=L->next;while(L!=NULL){cout << L->data << " ";L=L->next;}return 0;
}

查找元素：

int search(node* head,int x)
{  //在以head为头结点的链表上查找元素x的个数int count=0;  //计数器node *p=head->next;while(p!=NULL)  //只要没有达到链表结尾{if(p->next==x){count++;}p=p->next;}return count;  //返回计数器个数
}

插入元素：

//在pos这个位置加入x，在以head为头结点的链表中
void insert(node *head, int pos, int x)
{node *p=head;for(int i=0; i<pos-1; i++)p=p->next;node *q=new node;q->next=x;q->next=p->next;p->next=q;}

删除元素：

//删除以head为头结点，所有值为x的元素
void del(node *head, int x)
{node *p=head->next;     //p从第一个结点开始枚举node *pre=head;      //pre保存p的前驱结点的指针while(p!=NULL){if(p->data==x)         //数据域恰好为x，说明要删除该结点{pre->next=p->next;delete(p);p=pre->next;}else{pre=p;p=p->next;}}
}

静态链表：

不要把结构体变量名和结构体类型名设置为同一个名称

struct Node  //N大写
{int data;node *next;
}node[100];   //n小写node[1111]=2222;   //数组元素存放的是下一个数组元素的下标
node[2222]=3333;
node[3333]=-1;