《数据结构》的全部代码实现C语言.doc

io、h>/* eof() */
#include/* floor(),ceil(),abs() */
#include/* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math、h中已定义OVERFLOW得值为3,故去掉此行 */
typedef int Status; /* Status就是函数得类型,其值就是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean就是布尔类型,其值就是TRUE或FALSE */
/* algo2-1、c 实现算法2、1得程序 */
#include"c1、h"
typedef int ElemType;
#include"c2-1、h"
/*c2-1、h 线性表得动态分配顺序存储结构 */
#define LIST_INIT_SIZE 10 /* 线性表存储空间得初始分配量 */
#define LISTINCREMENT 2 /* 线性表存储空间得分配增量 */
typedef struct
{
  ElemType *elem; /* 存储空间基址 */
  int length; /* 当前长度 */
  int listsize; /* 当前分配得存储容量(以sizeof(ElemType)为单位) */
}SqList;
#include"bo2-1、c"
/* bo2-1、c 顺序表示得线性表(存储结构由c2-1、h定义)得基本操作(12个) */
Status InitList(SqList *L) /* 算法2、3 */
{ /* 操作结果：构造一个空得顺序线性表 */
  (*L)、elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
  if(!(*L)、elem)
    exit(OVERFLOW); /* 存储分配失败 */
  (*L)、length=0; /* 空表长度为0 */
  (*L)、listsize=LIST_INIT_SIZE; /* 初始存储容量 */
  return OK;
}
Status DestroyList(SqList *L)
{ /* 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L */
  free((*L)、elem);
  (*L)、elem=NULL;
  (*L)、length=0;
  (*L)、listsize=0;
  return OK;
}
Status ClearList(SqList *L)
{ /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
  (*L)、length=0;
  return OK;
}
Status ListEmpty(SqList L)
{ /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
  if(L、length==0)
    return TRUE;
  else
    return FALSE;
}
int ListLength(SqList L)
{ /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
  return L、length;
}
Status GetElem(SqList L,int iElemType *e)
{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
  /* 操作结果：用e返回L中第i个数据元素得值 */
  if(i<1||i>L、length)
    exit(ERROR);
  *e=*(L、elem+i-1);
  return OK;
}
int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* 初始条件：顺序线性表L已存在，compare()就是数据元素判定函数(满足为1,否则为0) */
  /* 操作结果：返回L中第1个与e满足关系compare()得数据元素得位序。 */
  /*           若这样得数据元素不存在，则返回值为0。算法2、6 */
  ElemType *p;
  int i=1; /* i得初值为第1个元素得位序 */
  p=L、elem; /* p得初值为第1个元素得存储位置 */
  while(i<=L、length&amp;!compare(*p++,e))
    ++i;
  if(i<=L、length)
    return i;
  else
    return 0;
}
Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e)
{ /* 初始条件：顺序线性表L已存在 */
  /* 操作结果：若cur_e就是L得数据元素，且不就是第一个，则用pre_e返回它得前驱， */
  /* &nbsp;         否则操作失败，pre_e无定义 */
  int i=2;
  ElemType *p=L、elem+1;
  while(i<=l、length&&*p!=cur_e) i="">L、length)
    return INFEASIBLE;
  else
  {
    *pre_e=*--p;
    return OK;
&nbsp; }
}
Status NextElem(SqList L,ElemType cur_e,ElemType *next_e)
{ /* 初始条件：顺序线性表L已存在 */
  /* 操作结果：若cur_e就是L得数据元素，且不就是最后一个，则用next_e返回它得后继， */
  /*           否则操作失败，next_e无定义 */
  int i=1;
  ElemType *p=L、elem;
  while(i<L、length&amp;*p!=cur_e)
  {
    i++;
    p++;
  }
  if(i==L、length)
    return INFEASIBLE;
  else
  {
    *next_e=*++p;
    return OK;
  }
}
Status ListInsert(SqList *L,int i,ElemType e) /* 算法2、4 */
{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1 */
  /* 操作结果：在L中第i个位置之前插入新得数据元素e，L得长度加1 */
  ElemType *newbase,*q,*p;
  if(i<1||i>(*L)、length+1) /* i值不合法 */
    return ERROR;
  if((*L)、length>=(*L)、listsize) /* 当前存储空间已满,增加分配 */
  {
    newbase=(ElemType *)realloc((*L)、elem,((*L)、listsize+LISTINCREMENT)*sizeof(ElemType));
    if(!newbase)
      exit(OVERFLOW); /* 存储分配失败 */
    (*L)、elem=newbase; /* 新基址 */
    (*L)、listsize+=LISTINCREMENT; /* 增加存储容量 */
  }
  q=(*L)、elem+i-1; /* q为插入位置 */
  for(p=(*L)、elem+(*L)、length-1;p>=q;--p) /* 插入位置及之后得元素右移 */
    *(p+1)=*p;
  *q=e; /* 插入e */
  ++(*L)、length; /* 表长增1 */
  return OK;
}
Status ListDelete(SqList *L,int i,ElemType *e) /* 算法2、5 */
{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
  /* 操作结果：删除L得第i个数据元素，并用e返回其值，L得长度减1 */
  ElemType *p,*q;
  if(i<1||i>(*L)、length) /* i值不合法 */
    return ERROR;
  p=(*L)、elem+i-1; /* p为被删除元素得位置 */
  *e=*p; /* 被删除元素得值赋给e */
  q=(*L)、elem+(*L)、length-1; /* 表尾元素得位置 */
  for(++p;plt;=q;++p) /* 被删除元素之后得元素左移 */
    *(p-1)=*p;
  (*L)、length--; /* 表长减1 */
  return OK;
}
Status ListTraverse(SqList L,void(*vi)(ElemType*))
{ /* 初始条件：顺序线性表L已存在 */
  /* 操作结果：依次对L得每个数据元素调用函数vi()。一旦vi()失败，则操作失败 */
  /*           vi()得形参加'&'，表明可通过调用vi()改变元素得值 */
  ElemType *p;
  int i;
  p=L、elem;
  for(i=1;i<=L、length;i++)
    vi(p++);
  printf("\n");
  return OK;
}
Status equal(ElemType c1,ElemType c2)
{ /* 判断就是否相等得函数，Union()用到 */
  ifc1==c2)
    return TRUE;
  else
    return FALSE;
}
void Union(SqList *La,SqList Lb) /* 算法2、1 */
{ /* 将所有在线性表Lb中但不在La中得数据元素插入到La中 */
  ElemType e;
  int La_len,Lb_len;
  int i;
  La_len=ListLength(*La); /* 求线性表得长度 */
  Lb_len=ListLength(Lb);
  for(i=1;i<=Lb_len;i++)
  {
    GetElem(Lb,i,&e); /* 取Lb中第i个数据元素赋给e */
    if(!LocateElem(*La,e,equal)) /* La中不存在与e相同得元素,则插入之 */
      ListInsert(La,++La_len,e);
  }
}
void print(ElemType *c)
{
  printfquot;%d ",*c);
}
void main()
{
  SqList La,Lb;
  Status i;
  int j;
  i=InitList(&La);
  if(i==1) /* 创建空表La成功 */
    for(j=1;j<=5;j++) /* 在表La中插入5个元素 */
      i=ListInsert(&La,j,j);
  printf("La= &quot;); /* 输出表La得内容 */
  ListTraverse(La,print);
  InitList(&Lb); /* 也可不判断就是否创建成功 */
  for(j=1;j<=5;j++) /* 在表Lb中插入5个元素 */
    i=ListInsert(&Lb,j,2*j);
  printf("Lb= "); /* 输出表Lb得内容 */
  ListTraverse(Lb,print);
  Union(&La,Lb);
  printf("new La= "); /* 输出新表La得内容 */
  ListTraverse(La,print);}
/* algo2-2、c 实现算法2、2得程序 */
#include"c1、h"
typedef int ElemType;
#include"c2-1、h"
#include"bo2-1、c"
void MergeList(SqList La,SqList Lb,SqList *Lc) /* 算法2、2 */
{ /* 已知线性表La与Lb中得数据元素按值非递减排列。 */
  /* 归并La与Lb得到新得线性表Lc,Lc得数据元素也按值非递减排列 */
  int i=1,j=1,k=0;
  int La_len,Lb_len;
  ElemType ai,bj;
  InitList(Lc); /* 创建空表Lc */
  La_len=ListLength(La);
  Lb_len=ListLength(Lb);
  while(i<=La_len&&j<=Lb_len) /* 表La与表Lb均非空 */
  {
    GetElem(La,i,&ai);
    GetElem(Lb,j,&bj);
    if(ai<=bj)
    {
      ListInsert(Lc,++k,ai);
      ++i;
    }
    else
    {
  &nbsp;   ListInsert(Lc,++k,bj);
      ++j;
    }
  }
  while(i<=La_len) /* 表La非空且表Lb空 */
  {
    GetElem(La,i++,&ai);
    ListInsert(Lc,++k,ai);
  }
  while(j<=Lb_len) /* 表Lb非空且表La空 */
  {
nbsp;   GetElem(Lb,j++,&bj);
    ListInsert(Lc,++k,bj);
  }
}
void print(ElemType *c)
{
  printf("%d ",*c);
}
void main()
{
  SqList La,Lb,Lc;
  int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
  InitList(&La); /* 创建空表La */
  for(j=1;j<=4;j++) /* 在表La中插入4个元素 */
    ListInsert(&La,j,a[j-1]);
  printf("La= "); /* 输出表La得内容 */
  ListTraverse(La,print);
  InitList(&Lb); /* 创建空表Lb */
  for(j=1;j<=7;j++) /* 在表Lb中插入7个元素 */
    ListInsert(&amp;Lb,j,b[j-1]);
  printf("Lb= "); /* 输出表Lb得内容 */
  ListTraverse(Lb,print);
  MergeList(La,Lb,&Lc);
  printf("Lc= "); /* 输出表Lc得内容 */
  ListTraverse(Lc,print);
}

/* algo2-3、c 实现算法2、7得程序 */
#include"c1、h"
typedef int ElemType;
#include"c2-1、h"
#include"bo2-1、c"
void MergeList(SqList La,SqList Lb,SqList *Lc) /* 算法2、7 */
{ /* 已知顺序线性表La与Lb得元素按值非递减排列。 */
  /* 归并La与Lb得到新得顺序线性表Lc,Lc得元素也按值非递减排列 */
  ElemType *pa,*pa_last,*pb,*pb_last,*pc;
  pa=La、elem;
  pb=Lb、elem;
&nbsp; (*Lc)、listsize=(*Lc)、length=La、length+Lb、length;/*不用InitList()创建空表Lc */
  pc=(*Lc)、elem=(ElemType *)malloc((*Lc)、listsize*sizeof(ElemType));
  if(!(*Lc)、elem) /* 存储分配失败 */
    exit(OVERFLOW);
  pa_last=La、elem+La、length-1;
  pb_last=Lb、elem+Lb、length-1;
  while(pa<=pa_last&&pb<=pb_last) /* 表La与表Lb均非空 */
  { /* 归并 */
    if(*pa<=*pb)
      *pc++=*pa++;
    else
      *pc++=*pb++;
  }
  while(pa<=pa_last) /* 表La非空且表Lb空 */
    *pc++=*pa /* 插入La得剩余元素 */
  while(pb<=pb_last) /* 表Lb非空且表La空 */
    *pc++=*pb++; /* 插入Lb得剩余元素 */
}
void print(ElemType *c)
{
  printf("%d ",*c);
}
void main()
{
  SqList La,Lb,Lc;
  int j;
  InitList(&La); /* 创建空表La */
  for(j=1;j<=5;j++) /* 在表La中插入5个元素 */
    ListInsert(&La,j,j);
  printf("La= "); /* 输出表La得内容 */
  ListTraverse(La,print);
  InitList(&Lb); /* 创建空表Lb */
  for(j=1;j<=5;j++) /* 在表Lb中插入5个元素 */
    ListInsert(&Lb,j,2*j);
  printf("Lb= "); /* 输出表Lb得内容 */
  ListTraverse(Lb,print);
  MergeList(La,Lb,&Lc);
  printf("Lc= "); /* 输出表Lc得内容 */
  ListTraverse(Lc,print);
}
/* algo2-4、c 修改算法2、7得第一个循环语句中得条件语句为开关语句，且当 */
/* *pa=*pb时，只将两者中之一插入Lc。此操作得结果与算法2、1相同 */
#include&quot;c1、h"
typedef int ElemType;
#include"c2-1、h"
#include"bo2-1、c"
int comp(ElemType c1,ElemType c2)
{
  int i;
  if(c1<c2)
    i=1;
  else if(c1==c2)
    i=0;
  else
    i=-1;
  return i;
}
void MergeList(SqList La,SqList Lb,SqList *Lc)
{ /* 另一种合并线性表得方法（根据算法2、7下得要求修改算法2、7） */
  ElemType  *pa,*pa_last,*pb,*pb_last,*pc;
  pa=La、elem;
  pb=Lb、elem;
  (*Lc)、listsize=La、length+Lb、length; /* 此句与算法2、7不同 */
  pc=(*Lc)、elem=(ElemType *)malloc((*Lc)listsize*sizeof(ElemType));
  if(!(*Lc)、elem)
    exit(OVERFLOW);
  pa_last=La、elem+La、length-1;
  pb_last=Lb、elem+Lb、length-1;
  while(pa<=pa_last&&pb<=pb_last) /* 表La与表Lb均非空 */
    switch(comp(*pa,*pb)) /* 此句与算法2、7不同 */
  &nbsp; {
      case  0: pb++;
      case  1: *pc++=*pa++;
               break;
      case -1: *pc++=*pb++;
    }
  while(pa<=pa_last) /* 表La非空且表Lb空 */
    *pc++=*pa
  while(pb<=pb_last) /* 表Lb非空且表La空 */
    *pc++=*pb++;
  (*Lc)、length=pc-(*Lc)、elem; /* 加此句 */
}
void print(ElemType *c)
{
  printf("%d ",*c);
}
void main()
{
  SqList La,Lb,Lc;
  int j;
  InitList(&La); /* 创建空表La */
  for(j=1;j<=5;j++) /* 在表La中插入5个元素 */
    ListInsert(&La,j,j);
  printf("La= "); /* 输出表La得内容 */
  ListTraverse(La,print);
  InitList(&Lb); /* 创建空表Lb */
  for(j=1;j<=5;j++) lb="); /* 输出表Lb得内容 */
  ListTraverse(Lb,print);
  MergeList(La,Lb,&Lc);
  printf(" lc="); /* 输出表Lc得内容 */
  ListTraverse(Lc,print);
}
/* algo2-5、c 实现算法2、11、2、12得程序 */
#include" typedef="" int="" h="" struct="" lnode="" elemtype="" c=&quot;" status="" linklist="" l="(LinkList)malloc(sizeof(struct" -="">next=NULL; /* 指针域为空 */
  return OK;
}
Status DestroyList(LinkList *L)
{ /* 初始条件：线性表L已存在。操作结果：销毁线性表L */
  LinkList q;
  while(*L)
  {
    q=L)->next;
    free(*L);
    *L=q;
  }
  return OK;
}
Status ClearList(LinkList L) /* 不改变L */
{ /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */
  LinkList p,q;
  p=L->next; /* p指向第一个结点 */
  while(p) /* 没到表尾 */
  {
    q=p->next;
    free(p);
    p=q;
  }
  L->next=NULL; /* 头结点指针域为空 */
  return OK;
}
Status ListEmpty(LinkList L)
{ /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
  if(L->next) /* 非空 */
    return FALSE;
  else
  &nbsp; return TRUE;
}
int ListLength(LinkList L)
{ /* 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 */
  int i=0;
  LinkList p=L->next; /* p指向第一个结点 */
  while(p) /* 没到表尾 */
  {
    i++;
    p=p->next;
  }
  return i;
}
Status GetElem(LinkList L,int i,ElemType *e) /* 算法2、8 */
{ /* L为带头结点得单链表得头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
  int j=1; /* j为计数器 */
  LinkList p=L->next; /* p指向第一个结点 */
  while(p&&jnext;
    j++;
  }
  if(!p||j>i) /* 第i个元素不存在 */
  &nbsp; return ERROR;
  *e=p->data; /* 取第i个元素 */
  return OK;
}
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* 初始条件: 线性表L已存在,compare()就是数据元素判定函数(满足为1,否则为0) */
  /* 操作结果: 返回L中第1个与e满足关系compare()得数据元素得位序。 */
  /*           若这样得数据元素不存在,则返回值为0 */
  int i=0;
  LinkList p=L->next;
  while(p)
  {
    i++;
    if(compare(p->data,e)) /* 找到这样得数据元素 */
      return i;
    p=p->next;
  }
  return 0;
}
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 初始条件: 线性表L已存在 */
  /* 操作结果: 若cur_e就是L得数据元素,且不就是第一个,则用pre_e返回它得前驱, */
  /*           返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE */
  LinkList q,p=L->next; /* p指向第一个结点 */
  while(p->next) /* p所指结点有后继 */
  {
    q=p->next; /* q为p得后继 */
    if(q->data==cur_e)
    {
      *pre_e=p->data;
      return OK;
    }
    p=q; /* p向后移 */
  }
  return INFEASIBLE;
}
Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
{ /* 初始条件：线性表L已存在 */
  /* 操作结果：若cur_e就是L得数据元素，且不就是最后一个，则用next_e返回它得后继， */
  /*           返回OK;否则操作失败，next_e无定义，返回INFEASIBLE */
  LinkList p=L->next; /* p指向第一个结点 */
  while(p->next) /* p所指结点有后继 */
  {
    if(p->data==cur_e)
    {
      *next_e=p->next->data;
      return OK;
    }
    p=p->next;
  }
  return INFEASIBLE;
}
Status ListInsert(LinkList L,int i,ElemType e) /* 算法2、9。不改变L */
{ /* 在带头结点得单链线性表L中第i个位置之前插入元素e */
  int j=0;
  LinkList p=L,s;
  while(p&&jnext;
    j++;
  }
  if(!p||j>i-1) /* i小于1或者大于表长 */
    return ERROR;
  s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
  s->data=e; /* 插入L中 */
  s->next=p->next;
  p->next=s;
  return OK;
}
Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2、10。不改变L */
{ /* 在带头结点得单链线性表L中，删除第i个元素,并由e返回其值 */
  int j=0;
  LinkList p=L,q;
  while(p->next&amp;jnext;
    j++;
  }
  if(!p->next||j>i-1) /* 删除位置不合理 */
    return ERROR;
  q=p->next; /* 删除并释放结点 */
  p->next=q->next;
  *e=q->data;
  free(q);
  return OK;
}
Status ListTraverse(LinkList L,void(*vi)(ElemType))
/* vi得形参类型为ElemType，与bo2-1、c中相应函数得形参类型ElemType&不同 */
{ /* 初始条件：线性表L已存在 */
  /* 操作结果:依次对L得每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
  LinkList p=L->next;
  while(p)
  {
    vi(p->data);
    p=p->next;
  }
&nbsp; printf("\n");
  return OK;
}
void CreateList(LinkList *L,int n) /* 算法2、11 */
{ /* 逆位序(插在表头)输入n个元素得值，建立带表头结构得单链线性表L */
  int i;
  LinkList p;
  *L=(LinkList)malloc(sizeof(struct LNode));
  (*L)->next=NULL; /* 先建立一个带头结点得单链表 */
  printfquot;请输入%d个数据\n",n);
  for(i=n;i>0;--i)
  {
    p=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
    scanf("%d",&p->data); /* 输入元素值 */
    p->next=(*L)->next; /* 插入到表头 */
    (*L)->next=p;
  }
}
void CreateList2(LinkList *L,int n)
{ /* 正位序(插在表尾)输入n个元素得值，建立带表头结构得单链线性表 */
  int i;
  LinkList p,q;
  *L=(LinkList)malloc(sizeof(struct LNode)); /* 生成头结点 */
  (*L)->next=NULL;
  q=*L;
  printf("请输入%d个数据\n",n);
  for(i=1;i<