单链表

文件:	linklist.rar
大小:	190KB
下载:	下载

在单链表中，每个节点只有一个指针域指向下一个节点的地址，因此每个节点包括数据域和一个节点域。

typedef int datatype;
typedef int* pdatatype;

typedef struct _Linklist
{
 datatype data;
 struct _Linklist *next;
}Linklist, *pLinklist;

 

对链表的操作主要有：

int Length(pLinklist head);   //有效节点的个数
pLinklist FindByIndex(pLinklist head, int i); //按序号查找
int FindByValue(pLinklist head, datatype data); // 按值查找
int ListInsert(pLinklist head, datatype x, int i); // 插入节点
int ListDelete(pLinklist head, int i); //删除节点

 

主要函数的算法以及注意点：

//-----------------------------------------------------------
//Function: FindByIndex
//    find one of the elements'value of the linklist.the index is com from 1;
//
//Parameters:
//    head: the linklist to be dealed with.
//    i: the index of the element; it come from 0;
//
//Returns:
//    if successed, return the point of the element.else return NULL;
//-----------------------------------------------------------
pLinklist FindByIndex(pLinklist head, int i)
{
 int j = 0;
 pLinklist p;
 if (NULL == head)
 {
  printf("\nError: The linklist is invalid\n");
  return NULL;
 }
 if (i <1)
 {
  printf("\nError:The index is invalid\n");
  return NULL;
 }

 p = head->next;

//注意在查找的过程中，变量j和节点p是有关联的，p是查找的当前节点，而j为当前节点的序号（有效节点从1算起）。

 while(p != NULL)
 {
  if ((++j) == i)
  {
   break;
  }
  else
  {
   p = p->next;
  }
 }
 
 if (j == i)
 {
  return p;
 }
 else
 {
  printf("\nError: cannot find the element\n");
  return NULL;
 }
}

 

//----------------------------------------------------------
//Function: ListInsert
//    insert one element into the linklist
//
//Parameters:
//    head: the linklist to be dealed with
//    x: the data to be input.
//    i: the index of the x to be insert in the linklist.
//        and the index come from 1;
//
//Returns:
//    if successed, return 1, else return 0;
//------------------------------------------------------------
int ListInsert(pLinklist head, datatype x, int i)
{
    pLinklist p, node;
 int j = 0;  //j is used to record the location of the current p;

 if (NULL ==head)
 {
  printf("\nThe linklist is invalid");
  return 0;
 }

 p = head;

 

//要插入节点，首先要找到要插入位置之前的那个节点。同样p为当前节点，j为当前节点的序号。 最后判断的条件为得到的j是否为i-1;
 while((j < i-1) && p->next != NULL)
 {
  j++;
  p = p->next;
 }

 if (j != i-1)
 {
  printf("\nCannot insert");
  return 0;
 }
 else
 {
  node = (pLinklist)malloc(sizeof(Linklist));
  node ->data = x;
  node->next = p->next;
  p->next = node;
  return 1;
 }
}

 

//-----------------------------------------------------------
//Function:ListDelete
//    Delete one of the elements of the linklist;
//
//Parameters:
//    head: the linklist to be dealed with;
//    i: the index of the element to be deleted, it come from 1;
//
//Returns:
//    if successed, return 1, else return 0;
//------------------------------------------------------------
int ListDelete(pLinklist head, int i)
{
 int j = 0; //the index of the current selected element.
 pLinklist p; //point to the element before the node that is to be deleted.
 pLinklist s; //the element that is to be deleted.

 if (NULL == head)
 {
  printf("\n The linklist is invalid");
  return 0;
 }

 p = head;

 while(j < i-1 && p->next != NULL)
 {
  j++;
  p = p->next;
 }

 if (j != i-1 || p->next == NULL)
 {
  printf("\n Cannot delete the element");
  return 0;
 }

 s = p->next;
 p->next = s->next;
 free(s);
 
 return 1;
}