清华严蔚敏《数据结构》的全部代码实现C语言之欧阳美创编.docx
《清华严蔚敏《数据结构》的全部代码实现C语言之欧阳美创编.docx》由会员分享，可在线阅读，更多相关《清华严蔚敏《数据结构》的全部代码实现C语言之欧阳美创编.docx（21页珍藏版）》请在冰点文库上搜索。
清华严蔚敏《数据结构》的全部代码实现C语言之欧阳美创编
/*c1.h（程序名）*/
时间：
2021.01.01
创作：
欧阳美
#include
#include
#include/*malloc（）等*/
#include/*INT_MAX等*/
#include/*EOF（=^Z或F6）,NULL*/
#include/*atoi（）*/
#include/*eof（）*/
#include/*floor（）,ceil（）,abs（）*/
#include/*exit（）*/
/*函数结果状态代码*/
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/
typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/
/*algo2-1.c实现算法2.1的程序*/
#include"c1.h"
typedefintElemType;
#include"c2-1.h"
/*c2-1.h线性表的动态分配顺序存储结构*/
#defineLIST_INIT_SIZE10/*线性表存储空间的初始分配量*/
#defineLISTINCREMENT2/*线性表存储空间的分配增量*/
typedefstruct
{
ElemType*elem;/*存储空间基址*/
intlength;/*当前长度*/
intlistsize;/*当前分配的存储容量（以sizeof（ElemType）为单位）*/
}SqList;
#include"bo2-1.c"
/*bo2-1.c顺序表示的线性表（存储结构由c2-1.h定义）的基本操作（12个）*/
StatusInitList（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;/*初始存储容量*/
returnOK;
}
StatusDestroyList（SqList*L）
{/*初始条件：
顺序线性表L已存在。
操作结果：
销毁顺序线性表L*/
free（（*L）.elem）;
（*L）.elem=NULL;
（*L）.length=0;
（*L）.listsize=0;
returnOK;
}
StatusClearList（SqList*L）
{/*初始条件：
顺序线性表L已存在。
操作结果：
将L重置为空表*/
（*L）.length=0;
returnOK;
}
StatusListEmpty（SqListL）
{/*初始条件：
顺序线性表L已存在。
操作结果：
若L为空表，则返回TRUE，否则返回FALSE*/
if（L.length==0）
returnTRUE;
else
returnFALSE;
}
intListLength（SqListL）
{/*初始条件：
顺序线性表L已存在。
操作结果：
返回L中数据元素个数*/
returnL.length;
}
StatusGetElem（SqListL,inti,ElemType*e）
{/*初始条件：
顺序线性表L已存在，1≤i≤ListLength（L）*/
/*操作结果：
用e返回L中第i个数据元素的值*/
if（i<1||i>L.length）
exit（ERROR）;
*e=*（L.elem+i-1）;
returnOK;
}
intLocateElem（SqListL,ElemTypee,Status（*compare）（ElemType,ElemType））
{/*初始条件：
顺序线性表L已存在，compare（）是数据元素判定函数（满足为1,否则为0）*/
/*操作结果：
返回L中第1个与e满足关系compare（）的数据元素的位序。
*/
/*若这样的数据元素不存在，则返回值为0。
算法2.6*/
ElemType*p;
inti=1;/*i的初值为第1个元素的位序*/
p=L.elem;/*p的初值为第1个元素的存储位置*/
while（i<=L.length&&!
compare（*p++,e））
++i;
if（i<=L.length）
returni;
else
return0;
}
StatusPriorElem（SqListL,ElemTypecur_e,ElemType*pre_e）
{/*初始条件：
顺序线性表L已存在*/
/*操作结果：
若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，*/
/*否则操作失败，pre_e无定义*/
inti=2;
ElemType*p=L.elem+1;
while（i<=L.length&&*p!
=cur_e）
{
p++;
i++;
}
if（i>L.length）
returnINFEASIBLE;
else
{
*pre_e=*--p;
returnOK;
}
}
StatusNextElem（SqListL,ElemTypecur_e,ElemType*next_e）
{/*初始条件：
顺序线性表L已存在*/
/*操作结果：
若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，*/
/*否则操作失败，next_e无定义*/
inti=1;
ElemType*p=L.elem;
while（i=cur_e）
{
i++;
p++;
}
if（i==L.length）
returnINFEASIBLE;
else
{
*next_e=*++p;
returnOK;
}
}
StatusListInsert（SqList*L,inti,ElemTypee）/*算法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值不合法*/
returnERROR;
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*/
returnOK;
}
StatusListDelete（SqList*L,inti,ElemType*e）/*算法2.5*/
{/*初始条件：
顺序线性表L已存在，1≤i≤ListLength（L）*/
/*操作结果：
删除L的第i个数据元素，并用e返回其值，L的长度减1*/
ElemType*p,*q;
if（i<1||i>（*L）.length）/*i值不合法*/
returnERROR;
p=（*L）.elem+i-1;/*p为被删除元素的位置*/
*e=*p;/*被删除元素的值赋给e*/
q=（*L）.elem+（*L）.length-1;/*表尾元素的位置*/
for（++p;p<=q;++p）/*被删除元素之后的元素左移*/
*（p-1）=*p;
（*L）.length--;/*表长减1*/
returnOK;
}
StatusListTraverse（SqListL,void（*vi）（ElemType*））
{/*初始条件：
顺序线性表L已存在*/
/*操作结果：
依次对L的每个数据元素调用函数vi（）。
一旦vi（）失败，则操作失败*/
/*vi（）的形参加'&'，表明可通过调用vi（）改变元素的值*/
ElemType*p;
inti;
p=L.elem;
for（i=1;i<=L.length;i++）
vi（p++）;
printf（"\n"）;
returnOK;
}
Statusequal（ElemTypec1,ElemTypec2）
{/*判断是否相等的函数，Union（）用到*/
if（c1==c2）
returnTRUE;
else
returnFALSE;
}
voidUnion（SqList*La,SqListLb）/*算法2.1*/
{/*将所有在线性表Lb中但不在La中的数据元素插入到La中*/
ElemTypee;
intLa_len,Lb_len;
inti;
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）;
}
}
voidprint（ElemType*c）
{
printf（"%d",*c）;
}
voidmain（）
{
SqListLa,Lb;
Statusi;
intj;
i=InitList（&La）;
if（i==1）/*创建空表La成功*/
for（j=1;j<=5;j++）/*在表La中插入5个元素*/
i=ListInsert（&La,j,j）;
printf（"La="）;/*输出表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（"newLa="）;/*输出新表La的内容*/
ListTraverse（La,print）;}
/*algo2-2.c实现算法2.2的程序*/
#include"c1.h"
typedefintElemType;
#include"c2-1.h"
#include"bo2-1.c"
voidMergeList（SqListLa,SqListLb,SqList*Lc）/*算法2.2*/
{/*已知线性表La和Lb中的数据元素按值非递减排列。
*/
/*归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列*/
inti=1,j=1,k=0;
intLa_len,Lb_len;
ElemTypeai,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
{
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空*/
{
GetElem（Lb,j++,&bj）;
ListInsert（Lc,++k,bj）;
}
}
voidprint（ElemType*c）
{
printf（"%d",*c）;
}
voidmain（）
{
SqListLa,Lb,Lc;
intj,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（&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"
typedefintElemType;
#include"c2-1.h"
#include"bo2-1.c"
voidMergeList（SqListLa,SqListLb,SqList*Lc）/*算法2.7*/
{/*已知顺序线性表La和Lb的元素按值非递减排列。
*/
/*归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列*/
ElemType*pa,*pa_last,*pb,*pb_last,*pc;
pa=La.elem;
pb=Lb.elem;
（*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的剩余元素*/
}
voidprint（ElemType*c）
{
printf（"%d",*c）;
}
voidmain（）
{
SqListLa,Lb,Lc;
intj;
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"c1.h"
typedefintElemType;
#include"c2-1.h"
#include"bo2-1.c"
intcomp（ElemTypec1,ElemTypec2）
{
inti;
if（c1i=1;
elseif（c1==c2）
i=0;
else
i=-1;
returni;
}
voidMergeList（SqListLa,SqListLb,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不同*/
{
case0:
pb++;
case1:
*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;/*加此句*/
}
voidprint（ElemType*c）
{
printf（"%d",*c）;
}
voidmain（）
{
SqListLa,Lb,Lc;
intj;
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-5.c实现算法2.11、2.12的程序*/
#include"c1.h"
typedefintElemType;
#include"c2-2.h"
/*c2-2.h线性表的单链表存储结构*/
structLNode
{
ElemTypedata;
structLNode*next;
};
typedefstructLNode*LinkList;/*另一种定义LinkList的方法*/
#include"bo2-2.c"
/*bo2-2.c单链表线性表（存储结构由c2-2.h定义）的基本操作（12个）*/
StatusInitList（LinkList*L）
{/*操作结果：
构造一个空的线性表L*/
*L=（LinkList）malloc（sizeof（structLNode））;/*产生头结点,并使L指向此头结点*/
if（!
*L）/*存储分配失败*/
exit（OVERFLOW）;
（*L）->next=NULL;/*指针域为空*/
returnOK;
}
StatusDestroyList（LinkList*L）
{/*初始条件：
线性表L已存在。
操作结果：
销毁线性表L*/
LinkListq;
while（*L）
{
q=（*L）->next;
free（*L）;
*L=q;
}
returnOK;
}
Status
升级会员 