线性表的链式存储----单链表

单链表

 typedef int datatype;
 typedef struct link_node{
   datatype info;
   struct link_node *next;
 }node;
typedef node *linklist;

建立单链表

• 头插法

linklist creatbystack()
{  linklist  head,s;
    datatype x;
    head=NULL;
    printf("请输入若干整数序列:\n");
    scanf("%d",&x);
    while (x!=0)        /*以0结束输入*/
    {   s=(linklist)malloc(sizeof(node));  /*生成待插入结点*/
        s->info=x;
        s->next=head;           /*将新结点插入到链表最前面*/
        head=s;
        scanf("%d",&x);
    }
    return head;                /*返回建立的单链表*/
}

• 尾插法

linklist creatbyqueue()
{
    linklist head,r,s;
    datatype x;
    head=r=NULL;
    printf("请输入若干整数序列:\n");
    scanf("%d",&x);
    while (x!=0) /*以0结束输入*/
    {    s=(linklist)malloc(sizeof(node));
         s->info=x;
         if (head==NULL)        /*将新结点插入到链表最后面*/
            head=s;
         else
            r->next=s;
        r=s;
        scanf("%d",&x);
   }
    if (r)  r->next=NULL;
    return head;                    /*返回建立的单链表*/
}

插入结点

• 表头插入
• 表尾插入
• 表内插入
• 指定位置插入(如下)

 /**********************************/
/*函数名称：insert()              */
/*函数功能：在第i个点插入x      */
/**********************************/
node *insert(node *head,datatype x,int i)
{
  node *p,*q;
  q=find(head,i);
  if(!q&&i!=0)
    printf("找不到第%d个结点，没办法插入%d",i,x);
  else
  {
    p=(node*)malloc(sizeof(node));
    p->info=x;
    if(i==0)
    {
      p->next=head;
      head=p;
    }
    else
    {
      p->next=q->next;
      q->next=p;

    }
  }
  return 0;

}

删除结点

linklist delx(linklist head,datatype x)
{
    linklist pre=NULL,p;
    if(!head){printf("链表为空\n");}
    p=head;
    while(p&&p->info!=x){pre=p;p=p->next;}
    if(p)
    {
        if(!pre) head=head->next;
        else pre->next=p->next;
    }
    free(p);
    return head;
}