清华严蔚敏《数据结构》的全部代码实现C语言Word格式文档下载.docx
《清华严蔚敏《数据结构》的全部代码实现C语言Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《清华严蔚敏《数据结构》的全部代码实现C语言Word格式文档下载.docx（89页珍藏版）》请在冰点文库上搜索。
#include"
c2-1.h"
/*c2-1.h线性表的动态分配顺序存储结构*/
#defineLIST_INIT_SIZE10/*线性表存储空间的初始分配量*/
#defineLISTINCREMENT2/*线性表存储空间的分配增量*/
typedefstruct
{
ElemType*elem;
/*存储空间基址*/
intlength;
/*当前长度*/
intlistsize;
/*当前分配的存储容量（以sizeof（ElemType）为单位）*/
}SqList;
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）.listsize=0;
StatusClearList（SqList*L）
将L重置为空表*/
StatusListEmpty（SqListL）
若L为空表，则返回TRUE，否则返回FALSE*/
if（L.length==0）
returnTRUE;
else
returnFALSE;
intListLength（SqListL）
返回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）;
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;
=L.length）
returni;
return0;
StatusPriorElem（SqListL,ElemTypecur_e,ElemType*pre_e）
顺序线性表L已存在*/
若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，*/
/*否则操作失败，pre_e无定义*/
inti=2;
ElemType*p=L.elem+1;
*p!
=cur_e）
p++;
i++;
if（i>
returnINFEASIBLE;
*pre_e=*--p;
StatusNextElem（SqListL,ElemTypecur_e,ElemType*next_e）
若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，*/
/*否则操作失败，next_e无定义*/
ElemType*p=L.elem;
L.length&
if（i==L.length）
*next_e=*++p;
StatusListInsert（SqList*L,inti,ElemTypee）/*算法2.4*/
顺序线性表L已存在，1≤i≤ListLength（L）+1*/
在L中第i个位置之前插入新的数据元素e，L的长度加1*/
ElemType*newbase,*q,*p;
（*L）.length+1）/*i值不合法*/
returnERROR;
if（（*L）.length>
=（*L）.listsize）/*当前存储空间已满,增加分配*/
newbase=（ElemType*）realloc（（*L）.elem,（（*L）.listsize+LISTINCREMENT）*sizeof（ElemType））;
newbase）
（*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*/
StatusListDelete（SqList*L,inti,ElemType*e）/*算法2.5*/
删除L的第i个数据元素，并用e返回其值，L的长度减1*/
ElemType*p,*q;
（*L）.length）/*i值不合法*/
p=（*L）.elem+i-1;
/*p为被删除元素的位置*/
*e=*p;
/*被删除元素的值赋给e*/
q=（*L）.elem+（*L）.length-1;
/*表尾元素的位置*/
for（++p;
p<
++p）/*被删除元素之后的元素左移*/
*（p-1）=*p;
（*L）.length--;
/*表长减1*/
StatusListTraverse（SqListL,void（*vi）（ElemType*））
依次对L的每个数据元素调用函数vi（）。
一旦vi（）失败，则操作失败*/
/*vi（）的形参加'
'
，表明可通过调用vi（）改变元素的值*/
inti;
for（i=1;
i<
=L.length;
i++）
vi（p++）;
printf（"
\n"
）;
Statusequal（ElemTypec1,ElemTypec2）
{/*判断是否相等的函数，Union（）用到*/
if（c1==c2）
voidUnion（SqList*La,SqListLb）/*算法2.1*/
{/*将所有在线性表Lb中但不在La中的数据元素插入到La中*/
ElemTypee;
intLa_len,Lb_len;
La_len=ListLength（*La）;
/*求线性表的长度*/
Lb_len=ListLength（Lb）;
=Lb_len;
GetElem（Lb,i,&
e）;
/*取Lb中第i个数据元素赋给e*/
LocateElem（*La,e,equal））/*La中不存在和e相同的元素,则插入之*/
ListInsert（La,++La_len,e）;
voidprint（ElemType*c）
%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）;
La="
/*输出表La的内容*/
ListTraverse（La,print）;
InitList（&
Lb）;
/*也可不判断是否创建成功*/
j++）/*在表Lb中插入5个元素*/
Lb,j,2*j）;
Lb="
/*输出表Lb的内容*/
ListTraverse（Lb,print）;
Union（&
La,Lb）;
newLa="
/*输出新表La的内容*/
}
/*algo2-2.c实现算法2.2的程序*/
voidMergeList（SqListLa,SqListLb,SqList*Lc）/*算法2.2*/
{/*已知线性表La和Lb中的数据元素按值非递减排列。
/*归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列*/
inti=1,j=1,k=0;
ElemTypeai,bj;
InitList（Lc）;
/*创建空表Lc*/
La_len=ListLength（La）;
=La_len&
=Lb_len）/*表La和表Lb均非空*/
GetElem（La,i,&
ai）;
GetElem（Lb,j,&
bj）;
if（ai<
=bj）
ListInsert（Lc,++k,ai）;
ListInsert（Lc,++k,bj）;
++j;
=La_len）/*表La非空且表Lb空*/
GetElem（La,i++,&
while（j<
=Lb_len）/*表Lb非空且表La空*/
GetElem（Lb,j++,&
SqListLa,Lb,Lc;
intj,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
/*创建空表La*/
=4;
j++）/*在表La中插入4个元素*/
ListInsert（&
La,j,a[j-1]）;
/*创建空表Lb*/
=7;
j++）/*在表Lb中插入7个元素*/
Lb,j,b[j-1]）;
MergeList（La,Lb,&
Lc）;
Lc="
/*输出表Lc的内容*/
ListTraverse（Lc,print）;
/*algo2-3.c实现算法2.7的程序*/
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））;
（*Lc）.elem）/*存储分配失败*/
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++;
*pc++=*pb++;
=pa_last）/*表La非空且表Lb空*/
/*插入La的剩余元素*/
while（pb<
=pb_last）/*表Lb非空且表La空*/
/*插入Lb的剩余元素*/
/*algo2-4.c修改算法2.7的第一个循环语句中的条件语句为开关语句，且当*/
/**pa=*pb时，只将两者中之一插入Lc。
此操作的结果和算法2.1相同*/
intcomp（ElemTypec1,ElemTypec2）
if（c1<
c2）
i=1;
elseif（c1==c2）
i=0;
i=-1;
voidMergeList（SqListLa,SqListLb,SqList*Lc）
{/*另一种合并线性表的方法（根据算法2.7下的要求修改算法2.7）*/
（*Lc）.listsize=La.length+Lb.length;
/*此句与算法2.7不同*/
（*Lc）.elem）
switch（comp（*pa,*pb））/*此句与算法2.7不同*/
case0:
pb++;
case1:
break;
case-1:
（*Lc）.length=pc-（*Lc）.elem;
/*加此句*/
/*algo2-5.c实现算法2.11、2.12的程序*/
c2-2.h"
/*c2-2.h线性表的单链表存储结构*/
structLNode
ElemTypedata;
structLNode*next;
};
typedefstructLNode*LinkList;
/*另一种定义LinkList的方法*/
bo2-2.c"
/*bo2-2.c单链表线性表（存储结构由c2-2.h定义）的基本操作（12个）*/
StatusInitList（LinkList*L）
构造一个空的线性表L*/
*L=（LinkList）malloc（sizeof（structLNode））;
/*产生头结点,并使L指向此头结点*/
*L）/*存储分配失败*/
exit（OVERFLOW）
升级会员 