清华严蔚敏数据结构的全部代码实现C语言知识

s

cl・h(程序名)*/

#include<string.h>

#include<ctype.h>

#include<malloc.h>/*malloc。等*/

#include<limits.h>/*INT_MAX等*/

#include<stdio.h>/*EOF(=AZ或F6),NULL*/

#include<stdlib.h>/*atoi()*/

#include<io.h>/*eof()*/

#include<math.h>/*floor(),ceil(),abs()*/

#include<process.h>/*exit()*/

/*函数结果状态代码*/

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/

typedefintStatus;/*Status是函数的类型，其值是函数结果状态代码，如OK等*/

typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE刃

/*algo2-l.c实现算法2.1的程序*/

#includencl.hM

typedefintElemType;

#includeMc2-l.hH

/*c2-l.h线性表的动态分配顺序存储结构*/

#defineLIST_INIT_SIZE10/*线性表存储空间的初始分配量*/

#defineLISTINCREMENT2/*线性表存储空间的分配增量*/

typedefstruct

(

ElemTypeclem;/*存储空间基址*/

intlength;/*当前长度*/

intlistsize;/*当前分配的存储容量(以sizeof(ElemType)为单位)*/

JSqList;

#include"

/*bo2-l.c顺序表示的线性表(存储结构由c2-l.h定义)的基本操作(12个)*/

StatusInitList(SqList*L)/*算法2.3*/

{/*操作结果：构造一个空的顺序线性表*/

(}:L).elem=(ElemType:(c}malloc(LIST_INlT_SlZE*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;

(：i：L).length=0;

(*L).listsize=O;

returnOK;

StatusClearList(SqList*L)

｛六初始条件：顺序线性表L已存在。操作结果：将L重置为空表*/

(*L)』englh=0;

returnOK;

StatusListEmpty(SqListL)

{/*初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE,否则返回

FALSE*/

if(L.length==O)

returnTRUE;

else

returnFALSE;

intListLength(SqListL)

{/*初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数*/

returnL.length;

)

StatusGetElem(SqListL,inti,ElemType*e)

{/*初始条件：顺序线性表L已存在，iWiWListLength(L)*/

/*操作结果：用e返回L中第i个数据元素的值*/

if(i<l||i>L.length)

exil(ERROR);

*e=*(L.elem+i-l);

returnOK;

)

intLocateElem(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType))

{/*初始条件：顺序线性表L已存在，compare。是数据元素判定函数(满足为1,否则为0)*/

/*操作结果：返回L中第1个与e满足关系compare。的数据元素的位序。*/

/*若这样的数据元素不存在，则返回值为00算法2.6*/

ElemType*p;

inli=l;/*i的初值为第1个元素的位序*/

p=L.elem;/*p的初值为第1个元素的存储位置*/

while(i<=L.length&&!compare(*p4-+,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.lenglh&&:1: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返回它的后继,

7

/*否则操作失败，next_e无定义*/

inti=l;

ElemType*p=L.elem;

while(i<L.length&&*p!=cur_e)

(

i++；

P++；

)

if(i==L.length)

returnINFEASIBLE;

else

(

*next_e=*++p;

returnOK;

StatusListInsert(SqList*L,inti,ElemTypee)/*算法2.4*/

{/*初始条件：顺序线性表L已存在，l<i<ListLength(L)+l*/

/*操作结果：在L中第i个位置之前插入新的数据元素e,L的长度加1*/

ElemType*newbase,*q,*p;

if(i<l||i>(*L).length+l)/*i值不合法*/

returnERROR;

if((：:：L).length>=(：!：L).listsize)/*当前存储空间已满，增加分配*/

{

newbase=(ElemType

*)reanoc((:::L),elem,(("L)Jistsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)

exit(OVERFLOW);/*存储分配失败*/

(::L).elem=newbase;/*新基址*/

(*L)Jislsize+二LISTINCREMENT;/*增加存储容量*/

)

q=(*L).elem+i-l;/*q为插入位置*/

for(p=(1L).elem+(:'L).length-l;p>=q;-p)/*插入位置及之后的元素右移*/

*(p+l)=*p;

*q=e;/*插入e*/

++(：i：L),length;/*表长增1*/

returnOK;

StatusListDelete(SqList：KL,inti,ElemType*e)/*算法2.5*/

{/*初始条件：顺序线性表L已存在，iWiWListLength(L)*/

/*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1*/

ElemType*p,*q;

if(i<l||i>(*L).length)/*i值不合法*/

returnERROR;

p=(：i：L).elem+i-l;/*p为被删除元素的位置*/

*e=*p;/*被删除元素的值赋给e*/

q=(*L).ftlem+(*L).length-1;/*表尾元素的位置*/

for(++p;p<=q;++p)/*被删除元素之后的元素左移*/

*(p-l)=*p;

(：1：L).length—;/*表长减1*/

returnOK;

StatusListTraverse(SqListL,void(*vi)(ElemType*))

{/*初始条件：顺序线性表L已存在*/

/*操作结果：依次对L的每个数据元素调用函数vi()。一旦vi()失败，则操作失败*/

/*vi()的形参加表明可通过调用vi()改变元素的值*/

ElemType*p;

inti;

p=L.elem;

for(i=l;i<=L.length;i++)

vi(p++);

printf(n\n");

returnOK;

Statusequal(ElemTypecl,ElemTypec2)

{/*判断是否相等的函数,Union。用到*/

if(cl==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=l;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(n%du,*c);

voidmain()

(

SqListLa,Lb;

Statusi;

intj；

i=InitList(&La);

if(i==l)/*创建空表La成功*/

for(j=l;j<=5;j++)/*在表La中插入5个元素*/

i=ListInsert(&La,jj);

prmtf(MLa=H);/*输出表La的内容*/

ListTraverse(La,print);

InitList(&Lb);/*也可不判断是否创建成功*/

for(j=l；j<=5;j++)/*在表Lb中插入5个元素*/

i=ListInsert(&Lb,j,2*j);

prmtf(MLb=°);/*输出表Lb的内容*/

ListTraverse(Lb,print);

Union(&La,Lb);

printf(nnewLa=M);/*输出新表La的内容*/

ListTraverse(La,print);}

/*algo2-2.c实现算法2.2的程序*/

#includencl.h"

typedefintElemType;

#include"c2-l.hn

#

voidMergeList(SqListLa,SqListLb,SqListLc)/*算法2.2*/

{/*已知线性表La和Lb中的数据元素按值非递减排列。*/

/*归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列号

inti=l,j=l,k=O;

intLa」en,Lb_len;

ElemTypeai,bj;

InitList(Lc);/*创建空表Lc*/

LaJen=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(n%d",*c);

)

voidmain()

(

SqListLa,Lb,Lc;

intj,a[4]={3,5,8,ll},b[7]={2,6,8,9,11,15,20);

InitList(&La);/*创建空表La*/

for(j=l;j<=4;j++)/*在表La中插入4个元素*/

ListInsert(&La,j,a[j-1]);

printf(nLa=H);/*输出表La的内容*/

ListTraverse(La,print);

InitList(&Lb);/*创建空表Lb*/

for(j=l;j<=7;j++)/*在表Lb中插入7个元素*/

ListInsert(&Lb,j,b[j-l]);

printf(nLb=H);/*输出表Lb的内容*/

ListTraverse(Lb,print);

MergeList(La,Lb,&Lc);

printf(MLc=H);/*输出表Lc的内容*/

ListTraverse(Lc,print);

/*algo2-3.c实现算法2.7的程序*/

#includencl.hn

typedefintElemType;

#includenc2-l.hM

#include,,

voidMergeList(SqListLa,SqListLb,SqList•Lc)/*算法2.7*/

{/*已知顺序线性表La和Lb的元素按值非递减排列。*/

/求归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列*/

ElemType*pa,*pa」ast,*pb,*pb」ast,*pc;

pa=La.elem;

pb=Lb.elem;

(*Lc)[istsize=(*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+LbJength-l;

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(H%d”/c);

voidmain()

(

SqListLa,Lb,Lc;

intj;

InitList(&La);/*创建空表La*/

for(j=l；j<=5;j++)/*在表La中插入5个元素*/

ListInsert(&La,j,j);

printf(',La=");/*输出表La的内容*/

ListTraverse(La,print);

InitList(&Lb);/*创建空表Lb*/

for(j=l;j<=5;j++)/*在表Lb中插入5个元素*/

ListInsert(&Lb,j,2*j);

printf(HLb=M);/*输出表Lb的内容*/

ListTraverse(Lb,print);

MergeList(La,Lb,&Lc);

printf(nLc=");/*输出表Lc的内容*/

ListTraverse(Lc,print);

)

/*algo2-4.c修改算法2.7的第一个循环语句中的条件语句为开关语句，且当*/

/**pa=*pb时，只将两者中之一插入Lc。此操作的结果和算法2.1相同*/

#includencl.hH

lypedefintElemType;

#includeHc2-l.h"

#includeH

intcomp(ElemTypecl,ElemTypec2)

inti;

if(cl<c2)

i=l；

elseif(cl==c2)

i=0;

else

i=-l；

returni;

}

voidMergeList(SqListLa,SqListLb,SqListLc)

{/*另一种合并线性表的方法(根据算法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=(Ix).elem=(ElemType*)malloc((:Lc).listsize*sizeof(ElemType));

if(!(Lc).elem)

exit(OVERFLOW);

pa_last=La.elem+La.length-1;

pb_last=Lb.eleiTi+LbJength-l;

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(M%dH,*c);

voidmain()

SqListLa,Lb,Lc;

intj;

InitList(&La);/*创建空表La*/

f0r(j=l;j<=5;j++)/*在表La中插入5个元素*/

ListInsert(&Laj,j);

printf(MLa=");/*输出表La的内容*/

ListTraverse(La,print);

InitList(&Lb);/*创建空表Lb*/

for(j=l;j<=5;j++)/*在表Lb中插入5个元素*/

ListInsert(&Lb,j,2*j);

printf(nLb=n);/*输出表Lb的内容*/

ListTraverse(Lb,print);

MergeList(La,Lb,&Lc);

printf(MLc=");/*输出表Lc的内容*/

ListTraverse(Lc,print);

/*algo2-5.c实现算法2.11、2.12的程序*/

#includencl.h"

typedefintElemType;

#includeHc2-2.hM

/*c22h线性表的单链表存储结构*/

structLNode

(

Elemiypedata;

structLNode*next;

)；

typedefstructLNode"LinkList;/*另一种定义LinkList的方法*/

#includenbo2-2.cM

/*bo2-2.c单链表线性表(存储结构由c2-2.h定义)的基本操作(12个)*/

StatusInitList(LinkList*L)

{/*操作结果：构造一个空的线性表L*/

:：:I=(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;

)

StatusClearList(LinkListL)/*不改变L*/

{/*初始条件：线性表L已存在。操作结果：将L重置为空表号

LinkListp,q;

p=L->next;/*p指向第一个结点*/

vvhile(p)/*没到表尾*/

{

q=p->next;

free(p);

p=q;

)

L->next=NULL;/*头结点指针域为空*/

returnOK;

)

StatusListEmpty(LinkListL)

{/*初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE,否则返回FALSE

/

if(L->next)/*非空*/

returnFALSE;

else

returnTRUE;

intListLength(LinkListL)

{/*初始条件：线性表L已存在。操作结果：返回L中数据元素个数*/

inti=0;

LinkListp=L->next;/*p指向第一个结点*/

while(p)/*没到表尾*/

{

i++；

p=p->next;

)

returni;

)

StatusGetElem(LinkLi$tL,inti,ElemType*e)/*算法2.8*/

{/*L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK,否则返

回ERROR*/

intj=l;/*j为计数器*/

LinkListp=L->next;/*p指向第一个结点*/

while(p&&j<i)/*顺指针向后查找，直到p指向第i个元素或p为空*/

{

p=p->next;

j++；

)

if(!plU>i)/*第i个元素不存在*/

returnERROR;

*e=p->data;/*取第i个元素*/

returnOK;

intLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType))

{/*初始条件：线性表L已存在,compare。是数据元素判定函数(满足为1,否则为0)*/

/*操作结果：返回L中第1个与e满足关系compare。的数据元素的位序。东/

/*若这样的数据元素不存在，则返回值为0*/

inti=0;

LinkListp=L->next;

vvhile(p)

(

i++；

if(compare(p->data,e))/*找到这样的数据元素列

returni;

p=p->next;

)

return0;

StatusPriorElem(LinkListL,ElemTypecur_e,ElemType*pre_e)

{/*初始条件：线性表L已存在*/

/*操作结果：若cur_e是L的数据元素,且不是第一个，则用pre_e返回它的前驱,*/

/*返回OK;否则操作失败,pre_e无定义，返回INFEASIBLE*/

LinkListq,p=L->next;/*p指向第一个结点*/

while(p->next)/*p所指结点有后继*/

{

q=p->next;/*q为p的后继*/

if(q->data==cur_e)

(

*pre_e=p->data;

returnOK;

)

p=q；/*p向后移*/

)

returnINFEASIBLE;

StatusNextElem(LinkListL,ElemTypecur_e,Elemiype*next_e)

{/*初始条件：线性表L已存在*/

/*操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继,

/

/*返回OK;否则操作失败，next_e无定义，返回INFEASIBLE*/

LinkListp=L->next;/*p指向第一个结点*/

while(p->next)/*p所指结点有后继*/

(

if(p->data==cur_e)

*next_e=p->next->data;

returnOK;

p=p->next;

)

returnINFEASIBLE;

StatusListInsert(LinkListL,inti,ElemTypee)/*算法2.9。不改变L*/

{/*在带头结点的单链线性表L中第i个位置之前插入元素e*/

intj=O;

LinkListp=L,s;

while(p&&j<i-l)/*寻找第i・l个结点

(

p=p->next;

j++；

)

if(!pllj>i-l)/*i小于1或者大于表长*/

returnERROR;

s=(LinkList)malloc(sizeof(structLNode));/*生成新结点*/

s->data=e;/*插入L中*/

s->next=p->next;

p->next=s;

returnOK;

)

StatusListDelete(LinkListL,inti,ElemType*e)/*算法2.10。不改变L*/

{/*在带头结点的单链线性表L中，删除第i个元素，并由e返回其值*/

intj=O;

LinkListp=L,q;

while(p->next&&j<i-l)/*寻找第i个结点，并令p指向其前趋*/

(

p=p->next;

j++；

)

if(!p->next||j>i-l)/*删除位置不合理*/

returnERROR;

q=p->next;/*删除并释放结点*/

p->next=q->next;

*e=q->data;

free(q);

returnOK;

StatusListTraverse(LinkListL,void(*vi)(ElemType))

/*vi的形参类型为ElemType，与bo2-l.c中相应函数的形参类型Elem］，pe&不同*/

{/*初始条件：线性表L已存在*/

/*操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败，则操作失败*/

LinkListp=L->next;

while(p)

(

vi(p->data);

p=p->next;

)

prmtf(,,\nH);

returnOK;

)

voidCreateList(LinkList*L,intn)/*算法CU*/

{/*逆位序(插在表头)输入n个元素的值，建立带表头结构的单链线性表L*/

inti;

LinkListp;

::L=(LinkList)malloc(sizeof(structLNode));

(*L)・>next=NULL;/*先建立一个带头结点的单链表为

printf("请输入％d个数据\n”,n);

for(i=n;i>0;-i)

(

p=(LinkList)malloc(sizeof(structLNode));/*生成新结点*/

scanf(u%d",&p->data);/*输入元素值*/

p->next=(：i：L)->next;/*插入到表头*/

(L)->next=p;

)

)

voidCreateList2(LinkList*L,intn)

{/*正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表*/

inti;

LinkListp,q;

::L=(LinkList)malloc(sizeof(structLNode));/*生成头结点*/

(L)->next=NULL;

q=*L;

printf("请输入％d个数据\n”,n);

fdr(i=l;i<=n;i++)

(

p=(LinkList)malloc(sizeof(structLNode));

scanf(u%d",&p->data);

q->next=p;

q=q->next;

p->next=NULL;

)

voidMergeList(LinkListLa,LinkList*Lb,LinkList*Lc)/*算法2.12*/

{/*己知单链线性表La和Lb的元素按值非递减排列6*/

/*归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列*/

LinkListpa=La->next,pb=(:Lb)->next,pc;

：i：Lc=pc=La;/*用La的头结点作为Lc的头结点刃

while(pa&&pb)

if(pa->data<=pb->data)

(

pc->next=pa;

pc=pa;

pa=pa->next;

)

else

(

pc->next=pb;

pc=pb;

pb=pb->next;

}

pc->next=pa?pa:pb;/*插入剩余段*/

free。：Lb);/*释放Lb的头结点*/

Lb=NULL;

)

voidvisit(ElemTypec)/*ListTraverse()调用的函数(类型要一致)*/

(

printf(H%d",c);

)

voidmain()

(

intn=5;

LinkListLa,Lb,Lc;

printf("按非递减顺序,

CreateList2(&La,n);/*正位序输入n个元素的值*/

printf(MLa=u);/*输出链表La的内容*/

ListTraverse(La,visit);

printf("按非递增顺序,")；

CreateList(&Lb,n);/*逆位序输入n个元素的值*/

printf("Lb=");/*输出链表Lb的内容*/

ListTraverse(Lb,visit);

MergeLisl(La,&Lb,&Lc);/*按非递减顺序归并La和Lb,得到新表Lc*/

printf(nLc=u);/*输出链表Lc的内容*/

ListTraverse(Lc,visit);

/*algo2-6.c利用单链表结构处理教科书图2.1(学生健康登记表)*/

#includencl.hn

#defineNAMELEN8/*姓名最大长度*/

#defineCLASSLEN4/*班级名最大长度刃

structstud/*记录的结构*/

(

charname[NAMELEN+l];

longnum;

charsex;

intage;

charClass[CLASSLEN+l];

inthealth;

)；

typedefstructstudElemType;/*链表结点元素类型为结构体*/

#include"c2-2.hn

charsta[3][9]={“健康一般神经衰弱”};/*健康状况(3类)*/

FILE*fp;

StatusInilLisl(LinkList*L)/*拷自bo2-2.c*/

{/*操作结果：构造一个空的线性表L*/

•：:L=(LinkList)malloc(sizeof(structLNode));/*产生头结点，并使L指向此头结点*/

if(!*L)/*存储分配失败刃

exit(OVERFLOW);

(*L)->next=NULL;/*指针域为空*/

returnOK;

)

StatusListTraverse(LinkListL,void(*vi)(ElemType))/*拷自bo2-2.c*/

{/*初始条件：线性表L已存在*/

/*操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败，则操作失败为

LinkListp=L->next;

while(p)

(

vi(p->data);

p=p->next;

printf("\nn);

returnOK;

voidInsertAscend(LinkListL,ElemTypee)/*此函数是由bo2-9.c中的同名函数改写*/

{/*按学号非降序插入*/

LinkListq=L,p=L->next;

while(p&&e.num>p->data.num)

(

q=p;

p=p->next;

)

q->next=(LinkList)malloc(sizeof(structLNode));/*插在q后*/

q->next->data=e;

q->next->next=p;

)

voidPrint(structstude)

{/*显示记录e的内容*/

printf(n%-8s%61d",,e.num);

if(e.sex==,m')

printf(H男)

else

printf(H女)

printf(H%5d%-4s",e.age,e.Class);

printf(M%9s\nu,sta[e.health]);

)

voidReadln(structstud*e)

{/*由键盘输入结点信息*/

prinlf(”请输入姓名(v=%d个字符):[NAMELEN);

scanf("%sn,e->name);

printf("请输入学号：");

scanf(,'%ld,',&e->num);

printf("请输入性别(m:男f:女):");

scanf(,,%*c%c,\&e->sex);

printf(”请输入年龄:");

scanf(n%d",&e->age);

printf(”请输入班级(v=%d个字符):n,CLASSLEN);

scanf("％s”,e4class);

printf("请输入健康状况(0:%sl:%s2:%s):n,sta[0],sta[l],sta[2]);

scanf("%d",&e->health);

voidWriteToFile(struclstude)

{/*将结点信息写入fp指定的文件*/

fwrite(&e,sizeof(struclstud),l,fp);

StatusReadFromFile(structstud*e)

{/*由fp指定的文件读取结点信息到e*/

inti;

i=fread(e,sizeof(structstud),l,fp);

if(i==l)/*读取文件成功*/

returnOK;

else

returnERROR;

StatusFindFromNum(LinkListL,longnum,LinkList*p,LinkList*q)

{/*查找表中学号为num的结点，如找到,q指向此结点,p指向q的前驱,*/

/*并返回TRUE;如无此元素,则返回FALSE*/

*p=L;

while(*p)

{

*q=(*p)->next;

if(*q&&(*q)->data.num>num)/*因为是按学号非降序排列*/

break;

if(*q&&(*q)->data.num==num)/*找到该学号*/

returnTRUE;

*p二*q;

)

returnFALSE;

StatusFindFromName(LinkListL,charname[],LinkList*p,LinkList*q)

{/*查找表中姓名为name的结点，如找到,q指向此结点,p指向q的前驱,*/

/*并返回TRUE;如无此元素,则返回FALSE*/

*p=L;

while(*p)

{

*q=(*p)->next;

if(*q&&!strcmp((*q)->,name))/*找到该姓名*/

returnTRUE;

*p=*q;

)

returnFALSE;

StatusDeleteElemNum(LinkListL,longnum)

{/*删除表中学号为num的元素，并返回TRUE；如无此元素，则返回FALSE*/

LinkListp,q;

if(FindFromNum(L,num,&p,&q))/*找到此结点，且q指向其,p指向其前驱*/

p->next=q->next;

free(q);

returnTRUE;

)

returnFALSE;

StatusDeleteElemName(LinkListL,charname[])

{/*删除表中姓名为name的元素，并返回TRUE；如无此元素，则返回FALSE*/

LinkListp,q;

if(FindFromName(L,name,&p,&q))/*找到此结点，且q指向其,p指向其前驱*/

(

p->next=q->next;

free(q);

returnTRUE;

)

returnFALSE;

voidModify(ElemType*e)

{/*修改结点内容*/

chars[80];

Print(*e);/*显示原内容*/

printf("请输入待修改项的内容，不修改的项按回车键保持原值:\n");

prinlf(”请输入姓名(v=%d个字符):[NAMELEN);

gets(s);

if(strlen(s))

strcpy(e->name,s);

printf("请输入学号:")；

gets(s);

if(strlen(s))

e->num=atol(s);

printf("请输入性别(m:男f:女):")；

gets(s);

if(strlen(s))

e->sex=s[0];

printff请输入年龄:");

gets(s);

if(strlen(s))

e->age=atoi(s);

prinlf(”请输入班级(<二%d个字符):",CLASSLEN);

gets(s);

if(strlen(s))

strcpy(e->Class,s);

printf("请输入健康状况(0:%sl:%s2:%s):",sta[0],sta[l],sta[2]);

gets(s);

if(strlen(s))

e->health=atoi⑸;/*修改完毕*/

}

#defineN4/*sludent记录的个数*/

voidmain()

(

structstudstudent[N]={{"王小林”,790631,'m',18,"计91”,0},

{"陈红”,790632,f,20,“计91",1),

{"刘建平”,790633；m',21，"计91",0),

{"张立立",790634,17,"计91”,2}};/*表的初始记录*/

inti,j,flag=l;

longnum;

charfilename[13],name[NAMELEN+1];

ElemTypee;

LinkListT,p,q;

InitList(&T);/*初始化链表*/

while(flag)

(

printf(”l:将结构体数组student中的记录按学号非降序插入链表\n")；

prinlf("2:将文件中的记录按学号非降序插入链表\n");

printf("3:键盘输入新记录，并将其按学号非降序插入链表\n")；

printf("4:删除链表中第一个有给定学号的记录\n")；

printf("5:删除链表中第一个有给定姓名的记录\n")；

printf("6:修改链表中第一个有给定学号的记录\n”)；

printf(”7:修改链表中第一个有给定姓名的记录\n")；

printf("8:查找链表中第一个有给定学号的记录\n)

printf("9:查找链表中第一个有给定姓名的记录\n")；

printf("10:显示所有记录11:将链表中的所有记录存入文件12:结束\n")；

printf("请选择操作命令:");

scanf(H%d",&i);

switch(i)

(

case1:for(j=0;j<N;j++)

InsertAscend(T,student[j]);

break;

case2:printf(”请输入文件名：");

scanf(,'%su,filename);

if((fp=fopen(filename,,'rb',))==NULL)

printf("打开文件失败!\n”);

else

(

while(ReadFromFile(&e))

InsertAscend(T,e);

fclose(fp);

)

break;

case3:Readln(&e);

InsertAscend(T,e);

break;

case4:prinlf("请输入待删除记录的学号:")；

scanf(,'%ld,,,&num);

if(!DeleteElemNum(T,num))

printf("没有学号为％旧的记录\n”,num);

break;

case5:printf("请输入待删除记录的姓名：");

scanf("%su,name);

if(!DeleteElemName(T,name))

printf("没有姓名为％s的记录\n”,name);

break;

case6:primf("请输入待修改记录的学号：”)；

scanf(',%ld%*c,,,&num);/*%*c吃掉回车符

if(!FindFromNum(T,num,&p,&q))

printf("没有学号为％旧的记录\n\num);

else

(

Modify(&q->data);

if(q->data.num!=num)/*学号被修改*/

(

p->next=q->next;/*把q所指的结点从L中删除*/

InsertAscend(T,q->data);/*把元素插入L*/

free(q);/*删除q*/

)

)

break;

case7:printf("请输入待修改记录的姓名：”)；

scanf(n%s%*cn,name);/*%*c吃掉回车符*/

if(!FindFromName(T,name,&p,&q))

primf("没有姓名为％$的记录\n”,name);

else

(

num=q->data.num;/*学号存入num*/

Modify(&q->data);

if(q->data.num!=num)/*学号被修改*/

p->next=q->next;/*把q所指的结点从L中删除*/

InsertAscend(T,q->data);/*把元素插入L*/

free(q);/*删除q*/

)

)

break;

case8:printf("请输入待查找记录的学号：”)；

scanf("%ld",&num);

if(!FindFromNum(T,num,&p,&q))

printf("没有学号为％出的记录\n”,num);

else

Print(q->data);

break;

case9:prinlf("请输入待查找记录的姓名：”)；

scanf(',%s,',naine);

if(!FindFromName(T,name,&p,&q))

printf("没有姓名为％§的记录\n”,name);

else

Print(q->data);

break;

case10:printf(n姓名学号性别年龄班级健康状况\n")；

ListTraverse(T,Print);

break;

casell:printf(”请输入文件名:");

scanf("%su,filename);

if((fp=fopen(filename,"wb"))==NULL)

printf("打开文件失败!\n)

else

ListTraverse(T,WriteToFile);

fclose(fp);

break;

case12:flag=0;

/*algo2-7.c教科书中图2.10静态链表示例*/

/*第一个结点的位置在[0].cur中，成员cur的值为0,则到链表尾*/

#include"cl.h"

#defineN6/*字符串长度*/

typedefcharElemType[N];

#includeMc2-3.hM

信c2-3.h线性表的静态单链表存储结构*/

#defineMAXSIZE100/*链表的最大长度刃

typedefstruct

(

ElemTypedata;

intcur;

}component,SLinkList[MAXSIZE];

voidmain()

(

SLinkList

s={{"",1},{“ZHAO”,2},{“QIAN”,3},{“SUN”,4},{“LI”,5},{“ZHOU”,6},{“WU”,7},{“ZHENG”,8}

,{“WANG”,0}};

inti;

i=s[0].cur;

while(i)/*输出教科书中图2.10(a)的状态*/

(

printf(H%s\s[i].data);/*输出链表的当前值*/

i=s[i].cur;/*找到下一个*/

)

printf(,'\nn);

s[4].cur=9;/*按教科书中图2.10(b)修改*/

s[6].cur=8;

s[9].cur=5;

strcpy(s[9].data；,SHIH);

i=s[0].cur;

while(i)/*输出教科书中图2.10(b)的状态*/

(

printf(n%s\s[i].data);/*输出链表的当前值*/

i=s[i].cur;/*找到下一个*/

}

printf(n\nn);

)

/*algo2-8.c实现算法2.17的程序*/

#includencl.hn

#defineN2

typedefcharElemType;

#includeMc2-3.hM

#indudenbo2-3.cM

/*bo2-3.c实现算法2.15、2.16的程序(数据结构由c2-3.h定义)(3个)*/

intMalloc(SLinkListspace)/*算法2.15*/

{/*若备用链表非空，则返回分配的结点下标(备用链表的第一个结点)，否则返回0*/

inti=space[O].cur;

if(i)/*备用链表非空刃

space[O].cur=space[i].cur;/*备用链表的头结点指向原备用链表的第二个结点*/

returni;/*返回新开辟结点的坐标*/

voidFree(SLinkListspace,intk)/*算法2.16*/

{译将下标为k的空闲结点回收到备用链表(成为备用链表的第一个结点)*/

space[k].cur=space[O].cur;P回收结点的“游标”指向备用链表的第一个结点*/

space[O]