程序设计基础作业

/*bo2-2.c单链表线性表(存储结构由c2-2.h定义)的基本操作(12个)*/StatusInitList(LinkList*L){/*操作结果：构造一个空的线性表L*/*L=(LinkList)malloc(sizeof(structLNode));/*产生头结点,并使L指向此头结点*/构造空的线性表L构造空的线性表L构造一个空的线性表，并使L指向头结点exit(OVERFLOW);(*L)->next=NULL;/*指针域为空*/returnOK;}StatusDestroyList(LinkList*L){/*初始条件：线性表L已存在。操作结果：销毁线性表L*/LinkListq;while(*L){销毁线性表L销毁线性表L当线性表L存在时，使用指针依次释放L的内存，将其销毁free(*L);*L=q;}returnOK;}StatusClearList(LinkListL)/*不改变L*/{/*初始条件：线性表L已存在。操作结果：将L重置为空表*/LinkListp,q;p=L->next;/*p指向第一个结点*/置空线性表L置空线性表L当线性表L存在时，用P指针记录头结点的位置，将后面内存释放，将P指针域置空{q=p->next;free(p);p=q;}L->next=NULL;/*头结点指针域为空*/returnOK;}StatusListEmpty(LinkListL){/*初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE*/判断线性表L是否为空如果为空返回TRUE判断线性表L是否为空如果为空返回TRUE不为空则放回FALSEreturnFALSE;elsereturnTRUE;}intListLength(LinkListL){/*初始条件：线性表L已存在。操作结果：返回L中数据元素个数*/inti=0;LinkListp=L->next;/*p指向第一个结点*/while(p)/*没到表尾*/{计算线性表L中元素个数当没到表尾时指针每次后移一位，并记录数据计算线性表L中元素个数当没到表尾时指针每次后移一位，并记录数据p=p->next;}returni;}StatusGetElem(LinkListL,inti,ElemType*e)/*算法2.8*/{/*L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR*/intj=1;/*j为计数器*/LinkListp=L->next;/*p指向第一个结点*/while(p&&j<i)/*顺指针向后查找,直到p指向第i个元素或p为空*/{p=p->next;将L链表中的第i个元素值赋给eP指针指向第一个结点，向后查找，直到p指向第i个元素或p为空时结束，将i值的地址给e指针将L链表中的第i个元素值赋给eP指针指向第一个结点，向后查找，直到p指向第i个元素或p为空时结束，将i值的地址给e指针}if(!p||j>i)/*第i个元素不存在*/returnERROR;*e=p->data;/*取第i个元素*/returnOK;}intLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType)){/*初始条件:线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0)*//*操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。*//*若这样的数据元素不存在,则返回值为0*/找到中第1个与e满足compare（）的数据元素的位序指针从表头向后查找，直到找到满足条件的元素，记录位置找到中第1个与e满足compare（）的数据元素的位序指针从表头向后查找，直到找到满足条件的元素，记录位置LinkListp=L->next;while(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返回cur_e的前驱当*p（指向第一个结点）有后继时，用q指向p的后继，如果q->data等于cur_e，则用pre_e返回其值用pre_e返回cur_e的前驱当*p（指向第一个结点）有后继时，用q指向p的后继，如果q->data等于cur_e，则用pre_e返回其值returnOK;}p=q;/*p向后移*/}returnINFEASIBLE;}StatusNextElem(LinkListL,ElemTypecur_e,ElemType*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返回cur_e的后继当*p（指向第一个结点）有后继时，如果p->data等于cur_e，则用next_e返回cur_e的后继用next_e返回cur_e的后继当*p（指向第一个结点）有后继时，如果p->data等于cur_e，则用next_e返回cur_e的后继*next_e=p->next->data;returnOK;}p=p->next;}returnINFEASIBLE;}StatusListInsert(LinkListL,inti,ElemTypee)/*算法2.9。不改变L*/{/*在带头结点的单链线性表L中第i个位置之前插入元素e*/intj=0;LinkListp=L,s;while(p&&j<i-1)/*寻找第i-1个结点*/{p=p->next;j++;}if(!p||j>i-1)/*i小于1或者大于表长*/returnERROR;s=(LinkList)malloc(sizeof(structLNode));/*生成新结点*/在L中第i个位置之前插入元素e先找到第i-1个结点，将i结点及后面的元素依次后移，生成新节点，将e插入新结点中在L中第i个位置之前插入元素e先找到第i-1个结点，将i结点及后面的元素依次后移，生成新节点，将e插入新结点中s->next=p->next;p->next=s;returnOK;}StatusListDelete(LinkListL,inti,ElemType*e)/*算法2.10。不改变L*/{/*在带头结点的单链线性表L中，删除第i个元素,并由e返回其值*/intj=0;LinkListp=L,q;while(p->next&&j<i-1)/*寻找第i个结点,并令p指向其前趋*/{p=p->next;j++;}if(!p->next||j>i-1)/*删除位置不合理*/returnERROR;删除第i个元素并由e返回其值找到第i个结点，判断其位置是否超出范围，如果位置合理，释放它删除第i个元素并由e返回其值找到第i个结点，判断其位置是否超出范围，如果位置合理，释放它p->next=q->next;*e=q->data;free(q);returnOK;}StatusListTraverse(LinkListL,void(*vi)(ElemType))/*vi的形参类型为ElemType，与bo2-1.c中相应函数的形参类型ElemType&不同*/{/*初始条件：线性表L已存在*//*操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败*/LinkListp=L->next;while(p){依次对L中的元素调用函数vi（）P指向L的首结点，当p不为0时，调用函数vi（）依次对L中的元素调用函数vi（）P指向L的首结点，当p不为0时，调用函数vi（）p=p->next;}printf("\n");returnOK;}/*algo2-5.c实现算法2.11、2.12的程序*/#include"c1.h"typedefintElemType;#include"c2-2.h"#include"bo2-2.c"voidCreateList(LinkList*L,intn)/*算法2.11*/{/*逆位序(插在表头)输入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));/*生成新结点*/输入链表数据，以逆序建立链表L建立一个带头结点的链表，输入数据，每次都在表头插入输入链表数据，以逆序建立链表L建立一个带头结点的链表，输入数据，每次都在表头插入p->next=(*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);for(i=1;i<=n;i++){p=(LinkList)malloc(sizeof(structLNode));输入链表数据，以位序建立链表L建立一个带头结点的链表，输入数据，每次都在表尾插入输入链表数据，以位序建立链表L建立一个带头结点的链表，输入数据，每次都在表尾插入q->next=p;q=q->next;}p->next=NULL;}voidMergeList(LinkListLa,LinkList*Lb,LinkList*Lc)/*算法2.12*/{/*已知单链线性表La和Lb的元素按值非递减排列。*//*归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列*/LinkListpa=La->next,pb=(*Lb)->next,pc;*Lc=pc=La;/*用La的头结点作为Lc的头结点*/while(pa&&pb)if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{归并La和Lb为Lc，使Lc递增顺次比较La和Lb中元素的大小，将小的放在Lc中，当La或Lb其中一个为空时将另一个表的剩余段插在Lc的最后归并La和Lb为Lc，使Lc递增顺次比较La和Lb中元素的大小，将小的放在Lc中，当La或Lb其中一个为空时将另一个表的剩余段插在Lc的最