2021-08-19 2 分钟 0.4 k0次访问

头插法和尾插法建立单链表

线性表结点结构

typedef struct LNode {	 //定义单链表结构类型
  ElemType data;		 //数据域
  struct LNode *next;	 //指针域
}LNode, *LinkList;

头插法

核心：新结点的指针域指向头结点下一个结点的数据域。头结点的指针域指向新结点的数据域。
s->next = L->next;
L->next = s;

算法如下：

LinkList List_HeadInsert(LinkList &L)
{
  LNode *s; int x;
  L = (LInkList)malloc(sizeof(LNode));                //创建头结点
  L->next = NULL;                //初始为空链表
  scanf("%d", &x);                //输入结点的值
  while(x != 9999)                //输入9999表示结束
  {
    s = (LNode*)malloc(sizeof(LNode));                //创建新结点
    s->data = x;			   //新结点赋值
    s->next = L->next;		    //将新结点指向头结点的下一个结点
    L->next = s;                //将新结点插入表中，L为头指针
    scanf("%d", &x);
  }                //while结束
  return L;
}

尾插法

核心：尾结点的指针域指向新结点的数据域。尾结点指向新结点的数据域。尾结点（此时为新结点）的指针域指向空。
r->next = s;
r = s;
r->next = NULL;

算法如下：

LinkList CreatList2(LinkList &L)
{
  int x;						//设元素类型为整型
  L = (LinlList)malloc(sizeof(LNode));
  LNode *s, *r = L;                //r为表尾指针
  scanf("%d", &x);                //输入结点的值
  while(x != 9999)                //输入9999表示结束
  {
    s = (LNode *)malloc(sizeof(LNode));
    s->data = x;		 //新结点赋值
    r->next = s;		 //将尾结点指向新结点
    r = s;                //将r指向新的表尾结点
    scanf("%d", &x);
  }
  r->next = NULL;         //尾结点指针置空
  return L;
}