C语言实现静态链表的基本操作 - 枫叶的日志 - 网易博客

C语言实现静态链表的基本操作

C语言实现数据结构 2009-09-21 11:09:55 阅读435 评论0   字号：大中小 订阅

头文件c2_3.h

#include
#include

#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define NULL 0

#define MAX_SIZE 100//链表的最大长度
typedef int Status;

typedef int ElemType;
typedef struct SQ
{ ElemType data;
  int cur;
}component,SLinkList[MAX_SIZE];

//函数声明
int Malloc(SLinkList space);//若备用链表不为空，则返回分配的结点的下标
void Free(SLinkList space,int k);//将下标为K的空闲链表回收到备用链表中
void InitList(SLinkList L);//构造一个空链表
void ClearList(SLinkList L);//初使化线性表
Status ListEmpty(SLinkList L);//判断表是否为空
int ListLength(SLinkList L);//返回L中元素的个数
Status GetElem(SLinkList L,int i,ElemType &e);//用e返回线性表中第i个元素的值
int LocateElem(SLinkList L,ElemType e);//在静态链表中查找第1个值为e的元素
Status PriorElem(SLinkList L,ElemType cur_e,ElemType &pre_e);//返回前驱
Status NextElem(SLinkList L,ElemType cur_e,ElemType &next_e);//返回后继
Status ListInsert(SLinkList L,int i,ElemType e);//在L中第i个元素之前插入新的数据元素
Status ListDelete(SLinkList L,int i,ElemType &e);//删除第i个元素
void ListTraverse(SLinkList L,void(*visit)(ElemType));//依次对线性表L中的元素调用函数visit();

void print1(ElemType e);//输出函数

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

函数文件bo2_5.cpp

#include
#include"c2_3.h"

//静态链表
int Malloc(SLinkList space)//若备用链表不空，则返回分配的结点下标
{  int i=space[0].cur;//备用链表第1个结点的位置
  if(i)//备用链表不空
   space[0].cur=space[i].cur;//备用链表的头结点指向原备用链表的第2个结点
   return i;
}

void Free(SLinkList space,int k)
{ //将下标为k的空闲结点回收到备用链表中
 space[k].cur=space[0].cur;//回收结点的“游标”指向备用链表的第1个结点
 space[0].cur=k;//备用链表的头结点指向新回收的结点
}
void InitList(SLinkList L)
{ //构造一个空的链表L，表头为L的最后一个单元L[MAX_SIZE_1],其他单元链成一个备用链表，表头为L的第一个单元L[0],"0"表示空指针
 int i;
 L[MAX_SIZE-1].cur=0;//L的最后一个单元为空链表的表头
 for(i=0;i  L[i].cur=i+1;
 L[MAX_SIZE-2].cur=0;
}

void ClearList(SLinkList L)
{  //将表置空
 int j,k,i=L[MAX_SIZE-1].cur;//i指向链表的第1个结点的位序
 L[MAX_SIZE-1].cur=0;//链表为空
 k=L[0].cur;//备用链表第i个结点的位置
 L[0].cur=i;//把链表的结点连到备用链表的表头
 while(i)//未到表尾
 {j=i;//j指向当前结点的位置
   i=L[i].cur;
 }
 L[j].cur=k;//备用链表的第i个结点接到链表的尾部
}
Status ListEmpty(SLinkList L)
{ //判断表是否为空
 if(L[MAX_SIZE-1].cur==0)//空表
  return TRUE;
 else return FALSE;
}
int ListLength(SLinkList L)
{ //返回表的长度
 int j=0,i=L[MAX_SIZE-1].cur;//i指向链表的第1个结点的位序
 while(i)//未到链表的表尾
 {  i=L[i].cur;//i指向下一个结点
    j++;//计数器加1
    }
 return j;
}

Status GetElem(SLinkList L,int i,ElemType &e)
{ //用e返回L中第i个元素的值
 int m,k=MAX_SIZE-1;//k指向表头结点的位序
 if(i<1||i>ListLength(L)) //不存在第i个元素
  return ERROR;
 for(m=1;m<=i;m++)//k向后移动到第i个元素
  k=L[k].cur;//指向下一个元素
   e=L[k].data;
   return OK;
}

int LocateElem(SLinkList L,ElemType e)//在静态链表中找第1个值为e的元素，若找到返回其位序
{ int i=L[MAX_SIZE-1].cur;//i指向表中的第1个结点的位序
  while(i&&L[i].data!=e)//在表中查找
   i=L[i].cur;//指向下一个元素
  return i;
}

Status PriorElem(SLinkList L,ElemType cur_e,ElemType &pre_e)
{  //寻找前驱
 int j,i=L[MAX_SIZE-1].cur;//i指向链表第1个结点的位置
 do //向后移结点
 {  j=i;//j指向i所指元素
   i=L[i].cur;//i 指向下一个元素
 }while(i&&cur_e!=L[i].data);
if(i)//找到该元素
{ pre_e=L[j].data;
return OK;
}
else return ERROR;
}
Status NextElem(SLinkList L,ElemType cur_e,ElemType &next_e)
{ int j,i=LocateElem(L,cur_e);//在L中查找第1个值为cur_e的元素位置
  if(i)
  { j=L[i].cur;
   if(j)
   { next_e=L[j].data;
     return OK;
   }
  }
return ERROR;
}

Status ListInsert(SLinkList L,int i,ElemType e)
{ //在L中第i个元素之前插入数据元素e
      int m,j,k=MAX_SIZE-1;//k指示表头结点的位序
   if(i<1||i>ListLength(L)+1)
    return ERROR;
   j=Malloc(L);//申请新单元
   if(j)//申请成功
   {  L[j].data=e;
      for(m=1;m    k=L[k].cur;//指向下一个结点
   L[j].cur=L[k].cur;//新结点指向第i-1个元素后的元素
   L[k].cur=j;//第i-1个元素指向新单元
   return OK;
   }
   return ERROR;
}

Status ListDelete(SLinkList L,int i,ElemType &e)
{  //删除L中第i个元素，并返回其值
 int j,k=MAX_SIZE-1;//k指示表头结点的位置
 if(i<1||i>ListLength(L))//
  return ERROR;
 for(j=1;j  k=L[k].cur;//指向下一个元素
 j=L[k].cur;//待删除元素
 L[k].cur=L[j].cur;//使第i-1个元素指向待删除元素的后继元素
 e=L[j].data;
 Free(L,j);
 return OK;
}
void ListTraverse(SLinkList L,void(*visit)(ElemType))
{//依次对表中的元素调用函数visit()
 int i=L[MAX_SIZE-1].cur;//i指向第一个元素的位序
  while(i)
  { visit(L[i].data);//对当前元素调用visit()
    i=L[i].cur;//指向下一个元素
  }
  printf("\n");
}

void print1(ElemType e)
{ printf("%3d",e);
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

主函数main2_4.cpp

#include
#include"c2_3.h"

main()
{  SLinkList L;
   int i,k,j;
   ElemType e0,e1,e;
   InitList(L);//初始化一个我链表
  for(i=1;i<=5;i++)
    ListInsert(L,i,i);//向我链表插入元素
   printf("判断表是否为空\n");
  k=ListEmpty(L);
  printf("表为空?k=%d(1:是0:否)",k);
  printf("\n");
 ListTraverse(L,print1);
  printf("链表的长度:%d",ListLength(L));//输出链表元素的个数
  printf("\n");

  printf("清空链表\n");
  ClearList(L);
  printf("清空后:");
  ListTraverse(L,print1);
  printf("再次判断表是否为空\n");
  k=ListEmpty(L);
  printf("表为空?k=%d(1:是0:否)",k);
  printf("\n");

  printf("再次插入元素\n");
  for(i=1;i<=10;i++)
    ListInsert(L,i,i);
  ListTraverse(L,print1);
   printf("链表的长度:%d",ListLength(L));//输出链表元素的个数
   printf("\n");
 
printf("前驱判断\n");
  for(i=1;i<=10;i++)
  { GetElem(L,i,e0);//把L中的第i个元素的值赋给e0
    k=PriorElem(L,e0,e1);//求e0的前驱，成功的话赋给e1
 if(k==ERROR)
   printf("元素%d无前驱\n",e0);
 else
  printf("元素%d的前驱是%d\n",e0,e1);
  }
 
  printf("\n");
  printf("\n");
 
  printf("后继判断\n");
 
  for(i=1;i<=10;i++)
  { GetElem(L,i,e0);//把L中的第i个元素的值赋给e0
    k=NextElem(L,e0,e1);//求e0的前驱，成功的话赋给e1
 if(k==ERROR)
  printf("元素%d无后继\n",e0);
    else
  printf("元素%d的后继%d\n",e0,e1);
  }

  printf("\n删除元素\n");
  k=ListLength(L);
  for(j=k+1;j>0;j--)
  { i=ListDelete(L,j,e);//删除第j个元素
    if(i==ERROR)
  printf("删除第%d个元素失败\n",j);
 else
  printf("删除第%d个元素成功,其值为%d\n",j,e);
  }

}