指针与链表

存储空间的分配和释放

函数malloc（）-动态分配一段内存空间

函数calloc（）-动态分配连续内存空间

函数realloc（）-改变指针指向空间的大小

链式存储结构-链表

理解：动态分配方式的数据结构

动态链表

静态链表

单链表

1

• 特点

单链表的初始化

LinkList Initlist()//单链表的初始化函数
{
	Linklist head;
	head=(Node*)malloc(sizeof(Node));
	head->next=NULL;
	return head;
}

单链表的建立

• 在头部插入新节点建立单链表

  (1)有头节点

  void CreatByHead(LinkList head)//头插法创建单链表
  {
  	Node*s;
  	char name[20];
  	int number;
  	printf("请输入学生的姓名和学号：\n");
  	while(1)
  	{
  		scanf("%s",name);
  		scanf("%d",number);
  		if(number==0)
  		break;
  		s=(Node*)malloc(sizeof(Node));
  		strcpy(s->name,name);
  		s->number=number;
  		s->next=head->next;
  		head->next=s
  	}
  	
  }
  

  （2）无头节点

  LinkList creatbyhead1(LinkList head)//头插法（无结点）
  {
  
      int number;
      char name[20];
      LinkList s;
      while(1)
      {
          scanf("%s",name);
          scanf("%d",&number);
          if(number==0)
          break;
          s=(Node*)malloc(sizeof(Node));
          strcpy(s->name,name);
          s->number-number;
          if(head==NULL)
          {
              head=s;
              s->next=NULL;
          }
          else
          {
              s->next=head;
              head=s;
              
          }
          
      }
      return head;
      
  }
  

  sum up

  总结

  区别：

  有了头节点 形式可以保持一致

  而没有头节点 需要另外考虑head==NULL的情况

• 在单链表的尾部插入新结点

  （1）有头点

  LinkList creatnodebyrear(LinkList head)//尾插法
  {
      int number;
      char name[20];
      LinkList r,s;
      r=head;
      while(1)
      {
          printf("请输入信息，名字和序号：\n");
          scanf("%s",name);
          scanf("%d",&number);
          if(number==0)
          break;
          s->number=number;
          strcpy(s->name,name);
          r->next=s;
          r=s;
          
      }
      r->next=NULL;
  }
  

  （2）无头结点

  LinkList creatlist2()//尾插法（无头结点）
  {
      LinkList head=NULL;
      int number;
      char name[20];
      LinkList r,s;
      printf("请输入序号和姓名");
      while(1)
      {
          scanf("%d",&number);
          scanf("%s",name);
          if(number==0)
          break;
          s=(Node*)malloc(sizeof(Node));
          strcpy(s->name,name);
          s->number=number;
          s->next=NULL;
          if(head==NULL)
          {
              head=s;
              r=head;
          }
          else
          {
              r->next=s;
              r=s;
          }
          
          
      }
      return head;
  
  
  }
  

单链表的遍历

• OutPut函数

单链表的插入

• 设计函数 在单链表的第i个位置插入新结点
• 在链表的表首位置后添加结点
• 在链表的最后添加结点

单链表的删除

void deletenode(LinkList head,int pos)//删除结点（有头节点）
{
    int j=0;
    LinkList p,q;
    p=head;
    if(j<pos-1&&p)
    {
        p=p->next;
        j++;
    }
    if(p==NULL||p->next==NULL)
    printf("Error!");
    else
    {
        q=p->next;
        p->next=q->next;
        free(q);
    }
    
    
}

单链表的查询

单链表的长度

• 遍历所有结点，同时统计节点个数

不带头结点的单链表

• 不带头结点单链表的插入

  • 插入链表的首位置

    • 新节点的指针s指向首结点head 再让s成为新head

  • 其他位置与带头结点的一样

    LinkList Delete(LinkList head,int i)
    {
        int j=1;
        Node *p,*q;
        if(i==1)
        {
            q=head;
            head=head->next;
            free(q);
        }
        else
        {
            while(j<i-1&&p)
            {
                p=p->next;
                j++;
            }
            if(p==NULL||p->next==NULL)
            if(p)
            {
                q=p->next;
                p->next=q->next;
                free(q);
            }
        }
        return head;
    }
    

• 不带头结点单链表的删除

  • 删除链表的首结点

    • 把让q指向head 再让head指向第二个结点成为新节点 free((q)) 这种情况需要返回新头指针

  • 其他位置与带头结点相同

    LinkList Insert(LinkList head,int i)
    {
        Node *s;
        Node *p;
        s=(Node*)malloc(sizeof(Node));
        scanf("%s",s->name);
        scanf("%d",s->number);
        int j=1;
        Node *p;
        if(i==1)
        {
            s->next=head;
            head=s;
        }
        else 
        {
            while(j<i-1&&p)
            {
                p=p->next;
                j++;
            }
            if(p)
            {
                s->next=p->next;
                p->next=s;
                
            }
        }
        return head;
    }