数据结构-链表（未完整）

目录

• 数据结构-链表
  • 链表
    • 1.结点
      • 组成成分
    • 2.头指针
    • 3.尾指针
• 静态链表
  • 建立静态链表
    • 1.头
    • 2.中间的结点
    • 3.尾巴
  • 静态链表的操作
    • 1.更新
    • 2.遍历
    • 3.其他
  • 静态链表和动态链表的差别
• 动态链表
  • 建立操作
  • 插入操作(已经给定位置的)
    • 代码
  • 删除操作
    • 代码
  • 输出操作
• 其他
  • 空间管理函数
    • 1.分配内存空间函数malloc
    • 2.分配内存空间函数calloc
    • 3.释放内存空间函数free
    • 来源
  • sizeof
    • 总结

数据结构-链表

链表

1.结点

组成成分

1. 数据域
2. 指针域

struct 结构体名称
{
    数据域
    //指针域
    sturct 结构体名称*  next;
}

2.头指针

指向链表头

3.尾指针

指向空指针（NULL）

静态链表

建立静态链表

1.头

head=&头指针;

2.中间的结点

上结点.next=下结点的地址

3.尾巴

尾指针.next=NULL;

静态链表的操作

1.更新

``p=p->next`

2.遍历

while(p->next!=NULL)
{
    操作；
    p=p->next;
}

3.其他

放到动态链表里

静态链表和动态链表的差别

动态链表

建立操作

struct student  *creat( )
{
  	struct student  *head=NULL, *p1,*p2;
        int n=1;
  	p1=p2=(struct student *)malloc(LEN);
        scanf("%ld,%f",&p1->num,&p1->score);
  	while(p1->num!=0) 
  	{
    		if(n==1) head=p1;
		else   p2->next=p1;

    		p2=p1;
		p1=(struct student *)malloc(LEN);
		scanf("%ld,%f",&p1->num,&p1->score);
		n++;
  	}
  	
  	p2->next=NULL;
  	return(head);
} 

插入操作(已经给定位置的)

• 统一：q是新指针，p是插入位置前一个位置的指针

• 申请空间：q=（类型转化）malloc(大小)

  1. 大小可以等于sizeof(变量类型)
  2. 要做强制类型转化，因为malloc函数返回的是一个void类型的。

• 对q赋值：q->成员=变量;

• 插入位置

  • 插入到表头

  如果新内容是插到表头的话，相当于表头伸出一根线去连接新内容，同时要记得更新头指针。

  q->next=head;
  head=q;
  

  • 在中间插入

  找到要插入位置的前一位，进行插入（为什么不是后一位呢？因为指针不记得上一位是谁）

  for(i=1;i<=n-2;i++)
  {
      p=p->next;
  }
  q->next=p-next;
  p->next=q;
  

  • 插入到尾巴

  其实可以合并到从中间插入（把空指针看成只是一个特殊的指针）

• 要返回head，万一删去的是头指针呢？

代码

struct node *insert(struct node *head, int i)
{
  	struct node *p,*q;
  	p=head;//p指向头指针
    q=(struct student *)malloc(LEN);//创建新指针
  	scanf("%ld,%f",&q->num,&q->score);
  	//如果新内容是插到表头的话，相当于表头伸出一根线去连接新内容，同时要记得更新头指针。
    if(i==1){q->=head; head=q;}
    else
  	{
    	        for(j=1;j<i-1;j++)
                  p=p->next;
                 q->next=p->next;
                 p->next=q;
  	}
  	return head;//注意头指针有可能被改变
} 

删除操作

• 两个指针p1,p2

  • 为什么需要两个指针？

  • 我们删去一个指针不单是需要找到我们要删掉的指针，而且还需要处理好删去的指针与相邻指针的关系，也就是说需要把要删去的指针的前一个指针连接到要删去指针的下一个指针的位置，不然会出现断链的情况

  • p2保留好p1的数据,p1再去前方探路,这样就能时刻保持好一种前后的关系

  • p2=p1;
    p1=p1->next;
    

• 寻找要删除的对象

  • 停止条件：碰到底或者p1->num==x;

• 搜寻要删除的对象

  1. 找得到

     1. “跳过”

     p2->next=p1->next;
     

     2. 删除,free掉

        free(p1);

  2. 找不到

     1. 输出

• 返回值：返回头指针

代码

struct node *del(struct node *head, int d )
{
  	struct node *p1,*p2;
  	p1=head;
  	while(p1!=NULL && p1->num!=d ) //查找要删除的结点
  	{
    		p2=p1;
    		p1=p1->next;
  	}
  	if(p1->num==d)   //删除结点
  	{
    		if(p1==head) head=p1->next;
   		else        p2->next=p1->next;
    		free(p1);          //释放所删除结点的空间
  	}
  	else printf("找不到该结点
");
  	return(head);
} 

输出操作

void print (struct student *head)
{ 
	struct student *p;
   	p=head;
   	if (head !=NULL)
      	do    
		{ 
			printf("%ld,%f",p->num,p->score);
                	p=p->next;
            } while (p!=NULL);
}

其他

空间管理函数

1.分配内存空间函数malloc

函数原型： void *malloc(unsigned size)

void只管接收申请到的值（需要做数据类型强制转换）

char *pc;
 pc = (char *)malloc(100);

2.分配内存空间函数calloc

函数原型： void *calloc(unsigned size)

3.释放内存空间函数free

函数原型： void free(unsigned size)

来源

include<stdlib.h>

sizeof

#include<iostream>
#include<stdio.h>
using namespace std;
struct node{
	int left;
	int right;
};
int main()
{
	double a=3.1415926;
	cout<<sizeof(int)<<" "<<sizeof(node)<<" "<<sizeof(a);
	return 0;
}

• output

4 8 8

总结

sizeof()函数能获取数据类型，结构体和一般变量的内存大小