线性表(二)--链式存储 (C语言实现)

我要吐槽一下markdown的格式转换。。。代码的格式搞了好久。上传的时候一直出错。。不得已又去看了看它的语法。。就很烦。。

好了,吐槽完了就来说正事了,接上一章的顺序结构,这章我们讲讲链式储存结构,所谓链式存储,就是采用链式方式将结点链接起来的存储结构称为链表。不同于顺序结构,链表只需要改变节点地址就可以实现动态操作。

线性表的链式存储又可以分为五种:1、单链表结构 2、循环链表结构 3、双向链表结构 4、静态链表结构(这个有些不同。。)

首先我们来了解单链表结构

关于单链表结点,我们一般设置成包含数据域和指针域,也就是后一个结点的指针域存放了前一个结点的地址,而数据域则是每个节点中包含的内容。类似于火车的车厢。为了方便表的运算处理,一般还有一个头结点和尾节点。头结点的指针域存放第一个结点的地址,而数据域可以不放,也可以储存线性表的长度附加信息。至于尾节点,则要求指针域指向null。貌似还是蛮好理解的。。

那么单链表类型的 C 语言定义 描述如下:

typedef struct Node / * 结点类型定义 * / 
{ ElemType data; 
  struct Node  * next; 
}Node, *LinkList;  /* LinkList 为结构指针类型*/ 

LinkList 与 Node 同为结构指针类型,这两种类型是等价的。通常我们习惯上用LinkList说明指针变量,强调它是某个单链表的头指
针变量,用 Node
来定义指向单链表中节点的指针

单链表的操作必须从头指针开始依次访问表中结点,所以一般以头结点表示一个单链表

知道了单链表的定义和结点结构,我们就可以对单链表进行基本运算了,和顺序结构一样,基本操作无外乎1、求长度 2、初始化 3、查找 4、插入 5、删除。

那就从求长度开始(我偏不要先初始化。。)
求长度其实很简单,只需要从头到尾遍历一次即可。
代码如下:

int ListLength(LinkList L)  /*求带头结点的单链表 L 的长度*/
{   
   Node *p; 
   p=L->next;  
   j=0;   /*用来存放单链表的长度*/ 
   while(p!=NULL) {
   p=p->next; 
   j++; 
   }
   return j; /*j 为求得的单链表长度*/   
}  /* ListLength */ 

然后是初始化单链表
事实上,建立单链表没有想象中那么简单,有三种方法:1、建立空表 2、头插法建表 3、尾插法建表。知道我为什么先求长度了把。。

首先,建立空表。

InitList(LinkList *L) 
{  
  *L = (LinkList)malloc(sizeof(Node)); /*建立头结点*/  
 (*L)->next = NULL; /*建立空的单链表 L*/  
} 

emmm。。lyjgod对malloc有那么一点点阴影阿。。不过这个代码已经写的很明白了。

然后是头插法建表,这种建表方式需要我们先建立一个空链表。
已知空链表 L,依次读入结点数据头插入,直到读入结
束标志为止。

每插入一个结点到表头的步骤:
1.生成新结点 s 并赋值;
2.将结点 s 插入到首元结点之前,即表头结点之后;
3.重复以上过程,生成并插入第 i 个结点,直到读取到结束字符为$时,
结束读取数据,建表完毕。

 void CreateFromHead(LinkList  L) /* L 是已经初始化好的空链表的头指针,通过键盘输入表中元素值,利用头 插法建单链表 L */   
 {  
    Node* s;
    char c; 
    int  flag=1;  
    while(flag) /* flag 初值为 1,当输入“$”时,置 flag 为 0, 建表结束*/ 
    {   
       c=getchar();
       if(c!=’$’)   
       { 
          s=(Node*)malloc(sizeof(Node));  /*建立新结点 s*/  
          s->data=c; 
          s->next=L->next;  /*将 s 结点插入表头*/ 
          L->next=s;   
    } 
    else 
       flag=0; 
    } 
} 

头插法得到的单链表的逻辑顺序与输入的顺序相反,所以也称为逆序建表法。这个有点点难理解,需要仔细思考思考,最好拿纸和笔自己演示演示。如果能理解好这一点,对后面的尾插法理解也很有帮助。

好了,我们来讲一讲尾插法。其实差不多

已知空链表 L,设置尾指针 r 指向当前表尾 r=L
依次读入结点数据尾插入,直到读入结束标志时将表尾结点链域置空

每插入一个结点到表尾的步骤:
1.生成新结点 s;
2.将结点 s 插入到表尾 r 结点之后;该结点作为当前表尾结点

void  CreateFromTail(LinkList L) /* L 是已经初始化好的空链表的头指针,通过键盘输入元素值,利用尾插法建 单链表 L */ 
{
   Node *r, *s; 
   int flag =1; /*设置一个标志,初值为 1,当输入“$”时,flag 为 0, 建表结束*/ 
   r=L; /* r 指针动态指向链表的当前表尾,以便于做尾插入,其初值指 向头结点*/ 

   while(flag)/*循环输入表中元素值,将建立新结点 s 插入表尾*/ 
   {
       c=getchar(); 
       if(c!=’$’)  
       {
          s=(Node*)malloc(sizeof(Node));
          s->data=c; 
          r->next=s; 
          r=s;   
       } 
       else  
       {   
          flag=0;  
          r->next=NULL;   /*将最后一个结点的 next 链域置为空,表示 链表的结束*/  
       } 
   }   /*while*/ 
 } /*CreateFromTail*/ 

能建立表之后。就要对表进行操作,首先看看查找。单链表查找可分为按序号查找和按值查找的两种方式。 这两种方式其实都比较容易理解,我就直接上代码了。

 按序号查找。
 Node * Get (LinkList  L, int i) / * 在带头结点的单链表 L 中查找第 i 个结点,若找到(1≤i≤n),则返回 该结点的存储位置;  否则返回 NULL * / 
{  
     int j;
     Node  *p;
     p=L;j=0;  / * 从头结点开始扫描 * /
     while ((p->next!=NULL)&&(j<i))
     { 
          p=p->next;/ * 扫描下一结点 * /
          j++;   / * 已扫描结点计数器 * /
     } 
     if(i= =j)
          return p;   / * 找到了第 i 个结点 
     else   
          return NULL;/ * 找不到,i≤0 或 i>n* / 

}/ * Get * /

这里需要注意的是我们无法直接查找第i个结点,因为每个结点的地址仅存在于上一个结点。

按值查找
Node *Locate( LinkList L,ElemType key) / * 在带头结点的单链表 L 中查找其结点值等于 key 的结点,若找到则返 回该结点的位置 p,否则返回 NULL * /
{ 
   Node *p;
   p=L->next;   / * 从表中第一个结点开始 * /

   while (p!=NULL)
   {
   if (p->data!=key)
       p=p->next; 
   else  
       break; / * 找到结点值=key 时退出循环 * /
   }
   return p; 
}  / * Locate * / 

这里直接返回p是因为如果找不到会直接返回尾节点的指针域,而尾节点的指针域即为null,因此不需要特别判定。

最后就是插入和删除了(快了。快了。。这章终于要讲完了),事实上在创建单链表的时候,我们已经做过插入这个操作了,现在要注意的就是节点位置。比如说我们现在要在第i个结点之前插入一个结点。
步骤如下:
1.确定第 i-1 个结点的位置 (同按序号查找算法)
2.申请新结点 s

  1. 插入挂链:新结点 s 插至第 i-1 个结点之后
    S 结点的后继指向第 i 个结点 s->next=pre->next
    第 i-1 个结点的指针指向 s pre->next=s

那么代码是这样的:

void InsList(LinkList L,int i,ElemType e) 
/*在带头结点的单链表L中第i个位置插入值为e的新结点s*/ 
{   
    Node *pre,*s;  int k; 
    pre=L;  k=0;/*从“头”开始,查找第i-1个结点*/ while(pre!=NULL&&k<i-1)  /*表未查完且未查到第i-1个时重复,找到pre指向第i-1个*/  
    { 
       pre=pre->next; 
       k=k+1;  
    } /*查找第i-1结点*/ 

    if(!pre)  /*如当前位置pre为空表已找完还未数到第i个,说明插入位置不合理*/  
    { 
       printf(“插入位置不合理!”);   
       return ERROR; 
    }   
    s=(Node*)malloc(sizeof(Node));   /*申请一个新的结点S */   
    s->data=e;   /*值e置入s的数据域*/ 

    s->next=pre->next;/*修改指针,完成插入操作*/   pre->next=s; return OK; 
} 

是不是和头插法尾插法差不多。。
那么删除也是异曲同工。话不多说放上本章最后的代码。

int DelList(LinkList L,int i,ElemType *e) 
/*在带头结点的单链表L中删除第i个元素,并将删除的元素保存到变量*e中
*/ 
{ Node *pre,*r;   int k; 
  pre=L;k=0; 
  while(pre->next!=NULL&&k<i-1) /*寻找被删除结点i的前驱结点i-1使p指向它*/ 
  { 
     pre=pre->next;  
     k=k+1; 
  }/*查找第i-1个结点*/ 

  if(!(pre->next)) /* 即while循环是因为p>next=NULL或i<1而跳出的,而是因为没有找到合法的前驱位置,说明删除位置i不合法。*/ 
  { 
     printf(“删除结点的位置i不合理!”); 
     return ERROR; 
  } 
  r=pre->next; 
  pre->next=r->next;/*修改指针,删除结点r*/ 
  *e=r->data; 

  free(r);/*释放被删除的结点所占的内存空间*/ 
  return OK; 
} 

第一次写这样的文章,其实自己也在学习中,希望能够加深自己对于数据结构的理解。也可以分享自己的学习经验。继续努力吧!lyjgod!