线性表的链式表示和实现 .txt

数据结构是计算机学科的一门核心课程。数据结构课程的 任务是讨论现实世界中数据的各种逻辑结构、在计算机中的存 储结构以及实现各种操作的算法等问题。掌握如何组织数据、 如何存储数据和如何处理数据的基

线性表的链式表示和实现  


    链式存储结构存储线性表数据元素的方法，是用结点构造
链。指针是指向物理存储单元地址的变量，我们把由数据元素
域和一个或若干个指针域组成的一个结构体称为一个结点。其
中，数据域用来存放数据元素，指针域用来构造数据元素之间
的关联关系。链式存储结构的特点是数据元素间的逻辑关系表
现在结点的链接关系上。链式存储结构的线性表称为链表。根
据指针域的不同和结点构造链的方法不同，链表主要有单链表、
循环单链表和双向循环链表三种。
    
1  单链表的存储结构
   单链表是只有一个指向直接后继结点指针域的链表。
    
   1．单链表的表示方法
     我们可以定义单链表结点的结构体如下：
     typedef struct Node
     {
         DataType data；
         struct Node *next；
     }SLNode；

    单链表有带头结点结构和不带头结点结构两种。我们把指
向单链表的指针称为头指针，头指针所指的不存放数据元素的
第一个结点称作头结点。存放第一个数据元素的结点称作首元
结点，或第一个结点。首元结点在带头结点的单链表中是链表
中的第二个结点，在不带头结点的单链表中是第一个结点。
    在顺序存储结构中，用户向系统申请一块地址连续的有限
空间用于存储数据元素集合，这样任意两个在逻辑上相邻的数
据元素在物理上也必然相邻。但在链式存储结构中，由于链式
存储结构是初始时为空链，每当有新的数据元素需要存储时用
户才向系统动态申请所需的存储空间插人链中，而这些在不同
时刻向系统动态申请的存储空间在内存中很可能不连续，因此，
在链式存储结构中任意两个在逻辑上相邻的数据元素在物理上
不一定相邻，数据元素的逻辑次序是通过链中的指针链接实现
的。

    2．动态申请和释放内存空间
    链式存储结构要求动态申请和释放内存空间。所有高级程
序设计语言都提供了用户向系统动态申请和释放内存空间的函
数或方法。C语言提供了动态申请和释放内存空间的函数。其中
两个主要的函数是malloc()函数和free()函数。malloc()函数
用于向系统动态申请所需的存储空间，free()函数用于动态释
放利用动态申请函数所申请的存储空间。
    malloc()函数的原型是：
        void * malloc(unsigned size)
    free()函数的原型是：
        void free(p)
其中，p指向利用动态申请函数所申请的内存单元的首地址。
    在大多数C编译器中，malloc()函数和free()函数包含在头
文件malloc.h中，但某些C编译器把这些函数包含在头文件
stdlib.h中。

2  单链表的操作实现
    单链表是由一个个结点链接构成的，单链表中每个结点的
结构体定义如下：
   typedef struct Node
{
    DataType data;
    struct Node *next
}SLNode;

    在带头结点的单链存储结构下，线性表抽象数据类型的操
作集合中各个操作的具体实现方法如下。
    1．初始化ListInitiate(SLNode * *head)
void ListInitiate(SLNode * *head)    /*初始化*/
{
/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/
  if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL) exit(1);
  (*head)->next=NULL;       /*置链尾标记NULL*/
}

    2．求当前数据元素个数ListLength(SLNode *head)
       int ListLength(SLNode *head)
       {
          SLNode *p=head;           /*p指向头结点*/
          int size=0;               /*size初始为0*/

          while(p->next!=NULL)      /循环计数*/
          {
             p=p->next;
             size++;
          }
          return size;
       }
设计说明：在循环前，临时指针变量p指向头结点，临时计数
变量size等于o；循环的结束条件为p->next!=NULl，循环中
每次让指针p指向它的直接后继结点，让计数变量size加1；最
终函数返回计数值size。

    3．插入数据元素listInsert(SLNode *head，int i，DataType x)
    int ListInsert(SLNode *head,int i,DataType x)
/*在带头结点的单链表head的数据元素ai(o≤i≤size)结点前*/
/*插入一个存放数据元素x的结点*/
    {
      SLNode *p,*q;
      int j;

      p=head;
      j=-1;
      while(p->next!=NULL && j<i-1)
/*最终让指针p指向数据元素a(i-1)结点*/
      {
        p=p->next;
        j++;
      }
 
      if(j!=i-1)
      {
        printf("插入位置参数错！");
        return 0;
      }

/*生成新结点由指针q指示*/
      if((q=(SLNode *)malloc(sizeof(SLNode)))==NULL) exit(1);
      q->data =x;
 
      q->next=p->next;       /*给指针q->next赋值*/
      p->next=q;             /*给指针p->next重新赋值*/
      return 1;   
    }
   设计说明：要在带头结点的单链表数据元素ai(o≤i≤size)
结点前插入一个存放数据元素x的结点，首先需要在单链表中
寻找到存放数据元素a(i-1)的结点并由指针p指示，然后动态
申请一个结点存储空间并由指针q指示，并把数据元素x的值赋
予新结点的数据元素域(即q->data=x)，最后修改新结点的指
针域指向数据元素ai结点(即q->next＝p->next)，并修改数据
元素a(i-1)结点的指针域指向新结点q(即p一>next=q)。
    循环条件由两个子条件逻辑与组成，其中子条件p->next!=NULL
保证数据元素a(i-1)结点非空，子条件j<i一1保证最终让指针
p指向数据元素a(i-1)结点。

    4  删除数据元素ListDelete(SLNode *head，inti，DataType *x)
int ListDelete(SLNode *head, int i,DataType *x)
/*删除带头结点的单链表head的数据元素ai(0≤i≤size-1)结点*/
/*删除结点的数据元素域值由x带回。删除成功时返回1，失败返回o*/
{
  SLNode *p,*s;
  int j;

  p=head;
  j=-1;
    
    
  while(p->next!=NULL && p->next->next!=NULL && j<i-1)
/*最终让指针p指向数据元素a(i-1)结点*/
  {
     p=p->next;
     j++;
  }
 
  if(j!=i-1)
  {
     printf("插入位置参数错！");
     return 0;
  }

  s=p->next;        /*指针s指向数据元素ai结点*/
  *x=s->data;       /*把指针s所指结点的数据元素域赋予x*/
  p->next=p->next->next; /*把数据元素ai结点从单链表中删除*/
  free(s);          /*释放指针s所指结点的内存空间*/
  return 1;
}