单链表
1 单链表的定义
单链表是用一组任意的存储单元来存放线性表的元素。存储单元可以连续，也可以不连续
为了正确的表示元素之间的逻辑关系，每个存储单元除了存储元素外 ，还需要存储后继元素的位置，这个地址信息用指针表示，称为指针；这两个元素组成了数据元素的存储映像，称为结点
也就是说节点有两个部分组成的
- 数据域
- 指针域
2 单链表结点c++实现
struct Node{ //Node 可以自己随便起名
int data;//这是数据域
Node *next;//这是指针域
}3 单链表的构造
为了避免其他对单链表的操作造成的bug,我们需要在构造单链表的时候构建一个头结点
怎么理解这个头结点呢，我是这么理解的就是不给他的数据域赋值，同时其他的操作不针对头结点，仅仅是个标识
插入某个节点
删除某个节点
CODE：
struct Node{
int data;
Node *next;
};
class LinkList{
public:
LinkList(){
first = new Node; //申请一个Node类型的结点/存储空间
//因为是作为头结点，所以不需要给数据域赋值
first->next = NULL; //建立一个只有头结点的空链表 所以next指向NULL
}
//头插法给链表赋初值
LinkList(int a[],int n){ //数组形参数作为给单链表赋值
first = new Node;
first->next = NULL; //立一个只有头结点的空链表
for(int i = 0;i < n;i++ ){
Node *s = new Node;
s->data = a[i]; //赋值
s->next = first->next; //每个新建的结点都要链接之前头结点所指向的结点
first->next = s; //头插法，每个元素结点都插在头结点后
}
}
//尾插法给单链表赋初值
void AddFromLast(int a[],int n){
Node *p = first; //设立工作指针，使他始终指向单链表的尾部
for(int i = 0;i < n;i++){
Node *s = new Node; //申请新的结点
p->next = s; //原链表的尾部next指针执行新的结点
s->data = a[i]; //赋值
p = s; //尾指针后移
}
p->next = NULL; //尾指针的next指向空
}
void AddData(int a,int position){
Node *s =new Node; //申请Node类型的空间
Node *p; //工作指针
p = first;
s->data = a;
int count = 0;
//下面这个循环的结果就是工作指针p指向了第position-1个结点
while(count != position-1){
p = p->next;
count++;
}
//开始执行插入
s->next = p->next; //先让s->next值向第position 个结点，顺序不能乱
p->next = s; //第position-1个结点的next指向新添加的结点
//给结点赋值
s->data = a;
}
//析构函数 单链表的空间是用new申请的，只能用delete删除
~LinkList(){
while(first->next != NULL){
Node *p = first;
first = first->next;
delete p;
}
}
//删除指定的结点
int DeleteData(int i){
Node *p = first;
Node *r;
int count = 0;
while(count != i-1){
p = p->next;
count++;
}
r = p->next;
p->next = r->next;
int x = r->data;
delete r;
return x;
}
//遍历所有的数据
void ShowAll(){
Node *p =first->next;
while(p != NULL){
cout<<p->data<<endl;
p = p->next;
}
}
//按位查找
int SelectByPosition(int position){
Node *p = first;
int count = 0;
while(count != position){
p = p->next;
count++;
}
return p->data;
}
private:
Node *first;//头指针
};
int main(){
int a[10] = {1,2,3,4,5,6,7,8,9,0};
LinkList link(a,10);
link.ShowAll();
cout<<endl;
link.AddData(111,5);
link.ShowAll();
cout<<endl;
link.DeleteData(5);
link.ShowAll();
cout<<endl;
link.AddFromLast(a,10);
link.ShowAll();
cout<<endl;
cout<<link.SelectByPosition(5);
cout<<endl;
}单向链表结构与顺序存储结构的优缺点
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。
查找：顺序存储结构O(1)，单链表O(n)。
插入和删除：顺序存储结构O(n)，单链表O(1)。
顺序存储结构需要预先分配存储空间，分大了浪费空间，分小了容易造成内存溢出；单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。
循环链表
单链表有一定的缺陷，就是单向性，只能从一个结点到下一个节点，而不能访问到上一个结点，而循环链表就可以解决这一问题，当然，用双向链表更加方便
Code：
struct node
{
int data;
struct node *next;//指针域
int size;//循环链表的长度
}node,*linklist;//linklist为定义的指针结构体变量
void create_list_head(linklist *l)//头插法建立循环链表
{
int i,j,x;
linklist p,q;
printf("please input length");
scanf("%d",&j);
(*l)=(node*)malloc(sizeof(node));
(*l)->next=NULL;//必须定义，缺少error
(*l)->size=j;
for(i=0;i<j;i++)//头插法输入数据
{
scanf("%d",&x);
p=(node*)malloc(sizeof(node));
p->data=x;
p->next=(*l)->next;
(*l)->next=p;
}
//q=(node*)malloc(sizeof(node));
q=(*l)->next;
while(q->next!=NULL)//找到最后一个结点
{
q=q->next;
}
//printf("%d",q->data);
q->next=(*l)->next;//将最后一个结点指向第一个结点
}
void create_list_tail(linklist *l)//尾插法建立循环链表
{
int i,j,x;
linklist p,r,t;
printf("please input the length");
scanf("%d",&j);
(*l)=(node*)malloc(sizeof(node));
(*l)->next=NULL;
(*l)->size=j;
t=(*l);
for(i=0;i<j;i++)
{
scanf("%d",&x);
p=(node*)malloc(sizeof(node));
p->data=x;
t->next=p;
t=p;//每新建一个结点在结束时都为最后一个结点，下一个节点在这个结点后面插入
}
t->next=NULL;
r=(*l)->next;
while(r->next!=NULL)
{
r=r->next;
}
r->next=(*l)->next;
}
void print_list_he(linklist *l)//打印输出
{
int i;
linklist p;
p=(*l)->next;
for(i=0;i<(*l)->size;i++)
{
printf("%d\n",p->data);
p=p->next;
}
}
int main()
{
linklist a;
create_list_head(&a);
create_list_tail(&a);
print_list_he(&a);
return 0;
}
标签：Node,结点,单链,线性表,int,储存,next,链接,first From： https://blog.51cto.com/u_15952369/6035570