大数据结构(C语言)-2

实用文案第二章 线性表本章的重点：掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析；难点：使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。要求达到“识记”的内容：线性表的逻辑结构特征，线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。要求达到“综合应用”的内容：顺序表的含义及特点，顺序表上的插入、删除操作，解决简单应用问题。链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。要求达到“领会”的内容：顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。线性结构的特点：在数据元素的非空有限集中，⑴存在唯一的一个被称做“第一个”的数据元素；⑵存在唯一的一个被称做“最后一个”的数据元素；⑶除第一个之外，集合中的每个数据元素均只有一个前驱；⑷除最后一个之外，集合中每个数据元素均只有一个后继。2.1线性表的逻辑结构一、线性表的定义线性表是最常用且最简单的一种数据结构。一个线性表是 n个数据元素的有限序列。数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。线性表例：1、1 2 3 4 5 6 7标准文档第二章 线性表2、3、学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004...数据元素也可由若干个数据项组成（如上例3）。这时常把数据元素称为记录。含有大量记录的线性表又称文件。线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。a1 ... ai-1 ai ai+1 ... anai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。线性表中元素的个数 n定义为线性表的长度，为 0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素，把i称为数据元素ai在线性中的位序。二、线性表的类型定义⒈抽象数据类型线性表的定义如下：ADTList{数据对象:D={ai|ai(-ElemSet,i=1,2,...,n,n>=0}数据关系:R1={<ai-1,ai>|ai-1,ai(-D,i=2,...,n}基本操作：InitList(&L)DestroyList(&L)ClearList(&L)ListEmpty(L)ListLength(L)GetElem(L,i,&e)LocateElem(L,e,compare())PriorElem(L,cur_e,&pre_e)-2实用文案NextElem(L,cur_e,&next_e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListTraverse(L,visit())}ADTList2、部分操作的类 C实现：InitList(&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}//InitListGetElem(L,i,&e){*e=L.lem[i]}//GetElemListInsert(List&L,inti,ElemTypee){if(i<1||i>L.length+1)returnERROR;q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}//ListInsertvoidunion(List&La,List&Lb)//利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);}//unionvoidMergeList(ListLa,ListLb,List&Lc)//巳知线性表 LA和线性表 LB中的数据元素按值非递减有序排列，现要求将 LA和LB归并为一个新的线性表 LC，且LC中的元素仍按值非递减有序排列。{InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);标准文档第二章 线性表while((i<=La_len)&&(j<Lb_len)){GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(k<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//MergeList3、部分操作的C语言实现,#include#include#include#defineERROR0#defineOK1#defineEQUAL1structSTU{charname[20];charstuno[10];intage;intscore;}stu[50];typedefstructSTUElemType;structLIST{ElemTypeelem[50];intlength;};typedefstructLISTList;intinit(List**L){*L=(List*)malloc(sizeof(List));(*L)->length=0;-4实用文案}intListLength(List*L){returnL->length;}voidGetElem(ListL,inti,ElemType*e){*e=L.elem[i];}intEqualList(ElemType*e1,ElemType*e2){if(strcmp(e1->name,e2->name))return0;if(strcmp(e1->stuno,e2->stuno))return0;if(e1->age!=e2->age)return0;if(e1->score!=e2->score)return0;return1;}intLocateElem(List*La,ElemTypee,inttype){inti;switch(type){caseEQUAL:for(i=0;ilength;i++)if(EqualList(&La->elem[i],&e))return1;break;default:break;}return0;}voidUnionList(List*La,List*Lb){intLa_len,Lb_len;inti;ElemTypee;标准文档第二章 线性表La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=0;iL->length+1)returnERROR;q=&(L->elem[i-1]);for(p=&L->elem[L->length-1];p>=q;--p)*(p+1)=*p;*q=e;++L->length;returnOK;}/*ListInsertBeforei*/main(){structSTUe;List*La,*Lb;clrscr();printf("\n\n-------------------ListDemoisrunning...----------------\n\n");printf("FirstisInsertListfunction.\n");init(&La);strcpy(,"stu1");strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(La,1,e);strcpy(,"stu2");strcpy(e.stuno,"100002");e.age=80;e.score=1000;ListInsert(La,2,e);printlist(*La);printf("ListAlengthnowis%d.\n\n",La->length);getch();strcpy(,"stu3");strcpy(e.stuno,"100003");e.age=80;e.score=1000;ListInsert(La,3,e);printlist(*La);printf("ListAlengthnowis%d.\n\n",La->length);getch();init(&Lb);strcpy(,"zmofun");-6实用文案strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(Lb,1,e);strcpy(,"bobjin");strcpy(e.stuno,"100002");e.age=80;e.score=1000;ListInsert(Lb,2,e);strcpy(,"stu1");strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(Lb,3,e);printlist(*Lb);printf("ListBlengthnowis%d.\n\n",Lb->length);getch();printf("SecondisUnionListfunction.\n");printf("NowunionListAandListB.....\n");UnionList(La,Lb);printlist(*La);printf("ListAlengthnowis%d.\n\n",La->length);getch();clrscr();}2.2 线性表的顺序表示和实现⑴存储结构“数据结构”定义中的“关系”指数据间的逻辑结构逻辑关系，故也称数据结构为逻辑结构。顺序数据结构在计算机中的表示称为物理结构。存储结构链式 又称存储结构。⑵线性表的类型定义一、线性表的顺序表示用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。标准文档第二章 线性表2000:0001000000000000000112000:0003000000000000001022000:0005000000000000001132000:0007000000000000010042000:0009000000000000010152000:0011000000000000011062000:00130000000000000111a[9]72000:0015000000000000100082000:001700000000000010019...2000:10012000:1003假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系：LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)*l式中LOC(a1)是线性表的第一个数据元素的存储位置，通常称做线性表的起始位置或基地址。常用b表示。线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。称顺序存储结构的线性表为顺序表。顺序表的特点是以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。二、顺序存储结构的线性表操作及 C语言实现：线性表的动态分配顺序存储结构#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;// 存储空间基址intlength;// 当前长度intlistsize;// 当前分配的存储容量以一数据元素存储长度为单位}SqList;-8实用文案顺序表的插入与删除操作：序号数据元素序号数据元素序号数据元素序号数据元素1121121121122132132132133213213->24321<-25214244244244285285255285306306286306427427307427778778428778997799插入前n=8;插入后n=9; 删除前n=8;删除后n=7;顺序表的插入算法statusListInsert(List*L,inti,ElemTypee){structSTU*p,*q;if(i<1||i>L->length+1)returnERROR;q=&(L->elem[i-1]);for(p=&L->elem[L->length-1];p>=q;--p)*(p+1)=*p;*q=e;++L->length;returnOK;}/*ListInsertBeforei*/顺序表的合并算法voidMergeList(List*La,List*Lb,List*Lc){ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=La->elem;pb=Lb->elem;Lc->listsize=Lc->length=La->length+Lb->length;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){标准文档第二章 线性表if(Less_EqualList(pa,pb))*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;}顺序表的查找算法intLocateElem(List*La,ElemTypee,inttype){inti;switch(type){caseEQUAL:for(i=0;i<length;i++)if(EqualList(&La->elem[i],&e))return1;break;default:break;}return0;}顺序表的联合算法voidUnionList(List*La,List*Lb){intLa_len,Lb_len;inti;ElemTypee;La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=0;i<Lb_len;i++){GetElem(*Lb,i,&e);if(!LocateElem(La,e,EQUAL))ListInsert(La,++La_len,e);}}三、C语言源程序范例#include<stdio.h>#include<malloc.h>#include<conio.h>#defineERROR0#defineOK1#defineEQUAL1#defineOVERFLOW-1#defineLIST_INIT_SIZE100#defineLISTINCREMENT10structSTU{-10实用文案charname[20];charstuno[10];intage;intscore;}stu[50];typedefstructSTUElemType;structLIST{ElemType*elem;intlength;intlistsize;};typedefstructLISTList;intinit(List*L){L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L->elem)exit(OVERFLOW);L->length=0;L->listsize=LIST_INIT_SIZE;returnOK;}/*init*/intListLength(List*L){returnL->length;}voidGetElem(ListL,inti,ElemType*e){*e=L.elem[i];}intEqualList(ElemType*e1,ElemType*e2){if(strcmp(e1->name,e2->name)==0)return1;else标准文档第二章 线性表return0;}intLess_EqualList(ElemType*e1,ElemType*e2){if(strcmp(e1->name,e2->name)<=0)return1;elsereturn0;}intLocateElem(List*La,ElemTypee,inttype){inti;switch(type){caseEQUAL:for(i=0;i<La->length;i++)if(EqualList(&La->elem[i],&e))return1;break;default:break;}return0;}voidMergeList(List*La,List*Lb,List*Lc){ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=La->elem;pb=Lb->elem;Lc->listsize=Lc->length=La->length+Lb->length;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){if(Less_EqualList(pa,pb)) *pc++=*pa++;else*pc++=*pb++;}-12实用文案while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;}voidUnionList(List*La,List*Lb){intLa_len,Lb_len;inti;ElemTypee;La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=0;i<Lb_len;i++){GetElem(*Lb,i,&e);if(!LocateElem(La,e,EQUAL))ListInsert(La,++La_len,e);}}intprintlist(ListL){inti;printf("name stuno age score\n");for(i=0;i<L.length;i++)printf("%-10s%s\t%d\t%d\n",L.elem[i].name,L.elem[i].stuno,L.elem[i].age,L.elem[i].score);printf("\n");}intListInsert(List*L,inti,structSTUe){structSTU*p,*q;if(i<1||i>L->length+1)returnERROR;q=&(L->elem[i-1]);for(p=&L->elem[L->length-1];p>=q;--p)*(p+1)=*p;*q=e;++L->length;returnOK;}/*ListInsertBeforei*/标准文档第二章 线性表main(){structSTUe;ListLa,Lb,Lc;clrscr();printf("\n\n-------------------ListDemoisrunning...----------------\n\n");printf("FirstisInsertListfunction.\n");init(&La);strcpy(,"stu1");strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(&La,1,e);strcpy(,"stu3");strcpy(e.stuno,"100002");e.age=80;e.score=1000;ListInsert(&La,2,e);printlist(La);printf("ListAlengthnowis%d.\n\n",La.length);getch();strcpy(,"stu5");strcpy(e.stuno,"100003");e.age=80;e.score=1000;ListInsert(&La,3,e);printlist(La);printf("ListAlengthnowis%d.\n\n",La.length);getch();init(&Lb);strcpy(,"stu2");-14实用文案strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(&Lb,1,e);strcpy(,"stu4");strcpy(e.stuno,"100002");e.age=80;e.score=1000;ListInsert(&Lb,2,e);strcpy(,"stu6");strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(&Lb,3,e);printlist(Lb);printf("ListBlengthnowis%d.\n\n",Lb.length);getch();MergeList(&La,&Lb,&Lc);printlist(Lc);getch();printf("SecondisUnionListfunction.\n");printf("NowunionListAandListB.....\n");UnionList(&La,&Lb);printlist(La);printf("ListAlengthnowis%d.\n\n",La.length);getch();}2.3 线性表的链式表示和实现一、线性链表的概念：线性链表：以链式结构存储的线性表。特点：该线性表中的数据元素可用任意的存储单元来存储。线性表中逻辑相邻的两元素的存储空间可以是不连续的。标准文档第二章 线性表为表示逻辑上的顺序关系，对表的每个数据元素除存储本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素的存储映象，称为结点。例:下图是若干抽屉，每个抽屉中放一个数据元素和一个指向后继元素的指针，一号抽屉中放线性表的第一个元素，它的下一个即第二个元素的位置标为5，即放在第5个抽屉中，而第三个放在2号抽屉中。第三个元素即为最后一个，它的下一个元素的指针标为空，用 0表示。2000:1000头指针2000:10062000:10302000:1010a32000:10402000:1020a6NULL2000:1030a1<-数据域+指针域2000:10402000:1060a42000:10502000:10502000:1060a52000:1020...a22000:10102000:4000数据域指针域用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的二、线性链表的存储实现-16实用文案structLNODE{ElemTypedata;structLNODE*next;};typedefstructLNODELNode;typedefstructLNODE*LinkList;注意：区分指针变量和结点变量这两个不同的概念；区别头指针与头结点。头指针：只相当于结点的指针域；头结点：整个线性链表的第一个结点，它的数据域可以放数据元素，也可以放线性表的长度等附加信息，也可以不存储任何信息。三、线性表的操作实现(类C语言)为动态变量，它是通过标准函数生成的，即p=(listnode*)malloc(sizeof(listnode));函数malloc分配了一个类型为listnode的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数 free(p) 释放所指的结点变量空间。⒈初始化操作StatusInit_L(LinkListL){if(L=(LinkList*)malloc(sizeof(LNode))){L->next=NULL;return1;}elsereturn0;}⒉插入操作插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，具体算法如下：标准文档第二章 线性表StatusListInsert_L(LinkList&L,inti,ElemTypee){p=L,j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;returnOK;}//ListInsert_L设链表的长度为n，合法的插入位置是1≦i≦n+1。注意当i=1时，getnode找到的是头结点，当i=n+1时，getnode找到的是结点an。因此，用i-1做实参调用getnode时可完成插入位置的合法性检查。算法的时间主要耗费在查找操作 getnode上，故时间复杂度亦为 O(n)。⒊删除操作-18实用文案删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点aai-1的指针域next中，所以必须首先找到。StatusListDelete_L(LinkList&L,inti,ElemType&e){p=L,j=0;while(p&&j<i-1){p=p->next;++j;}if(!p->next||j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q);returnOK;}//ListDelete_L设单链表的长度为n，则删去第i个结点仅当1≦i≦n时是合法的。注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋 *p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=NULL）且*p不是终端结点，（即p–>next!=NULL）时，才能确定被删结点存在。显然此算法的时间复杂度也是 O(n)标准文档第二章 线性表从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。⒋取某序号元素的操作在链表中，即使知道被访问结点的序号 i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。设单链表的长度为 n，要查找表中第i个结点，仅当1≦i≦n时，i值是合法的。但有时需找头结点的位置，故将头结点看做是第 0个结点，StatusGetElem_L(LinkList&L,inti,ElemType&e){p=L->next,j=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)returnERROR;e=p->data;returnOK;}//GetElem_L⒌归并两个单链表的算法voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){已知单链线性表La和Lb的元素按值非递减排列归并后得到新的单链线性表Lc,元素也按值非递减排列pa=La->next;pb=Lb->next;Lc=pc=La;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);}//MergeList_L⒍建立单链表假设线性表中结点的数据类型是字符，逐个输入这些字符型的结点，并以换行符‘\n’为输入结束标记。动态地建立单链表的常用方法有：⑴头插法建表-20实用文案该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。linklistcreatelistf(void){charch;linklisthead;listnode*p;head=null;ch=getchar();while(ch!= ‵\n′){p=(listnode*)malloc(sizeof(listnode));p –>data=ch;p –>next=head; head=p;ch=getchar();}return(head);}listlinkcreatelist(intn){intdata;linklisthead;listnode*phead=null;for(i=n;i>0;--i){p=(listnode*)malloc(sizeof(listnode));scanf(( 〝%d〞，&p–>data);p –>next=head; head=p;}return(head);}⑵尾插法建表头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例：linklistcreater( ){charch;linklisthead;listnode*p ，*r; //( ，*head;)标准文档第二章 线性表head=NULL;r=NULL;while((ch=getchar()!= ‵\n′){p=(listnode*)malloc(sizeof(listnode));–>data=ch;if(head=NULL)head=p;else r –>next=p;r=p;}if(r!=NULL)r –>next=NULL;return(head);}说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个if 语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表 head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。如果在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点：①由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；②无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。linklistcreatelistr1(){charch;linklisthead=(linklist)malloc(sizeof(listnode));listnode*p ，*rr=head;while((ch=getchar())!= ‵\n′{p=(listnode*)malloc(sizeof(listnode));–>data=ch;p–>next=p;r=p;-22实用文案}–>next=NULL;return(head);}上述算法里动态申请新结点空间时未加错误处理，可作下列处理：p=(listnode*)malloc(sizeof(listnode))if(p==NULL)error( 〝Nospacefornodecanbeobtained 〞);returnERROR;以上算法的时间复杂度均为 O(n)。⒎按值查找按值查找是在链表中，查找是否有结点值等于给定值 key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下：Listnode*locatenode(linklisthead ，intkey){listnode*p=head –>next;while(p&&p –>data!=key)p=p –>next;returnp;}该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。四、C语言实现的例子：#include<stdio.h>#include<malloc.h>#include<conio.h>#defineERROR0#defineOK1#defineEQUAL1#defineOVERFLOW-1#defineLIST_INIT_SIZE100#defineLISTINCREMENT10structSTU{标准文档第二章 线性表charname[20];charstuno[10];intage;intscore;}stu[50];typedefstructSTUElemType;structLNODE{ElemTypedata;structLNODE*next;};typedefstructLNODELNode;typedefstructLNODE*LinkList;intinit(LinkList*L){*L=(LNode*)malloc(sizeof(LNode));if(!L) exit(ERROR);(*L)->next=NULL;returnOK;}/*init*/intListLength(LinkListL){intj=0;while(L->next) {L=L->next;j++;}returnj;}intGetElem(LinkListL,inti,ElemType*e){LinkListp;intj;p=L->next;j=1;while(p&&j<I){p=p->next;++j;}if(!p||j>1)returnERROR;*e=p->data;returnOK;}intEqualList(ElemType*e1,ElemType*e2){if(strcmp(e1->name,e2->name)==0)return1;-24实用文案elsereturn0;}intLess_EqualList(ElemType*e1,ElemType*e2){if(strcmp(e1->name,e2->name)<=0)return1;elsereturn0;}intLocateElem(LinkListLa,ElemTypee,inttype){inti;LinkListp;p=La;switch(type) {caseEQUAL:while(p->next){p=p->next;if(EqualList(&p->data,&e))return1;}return0;break;default:break;}return0;}voidMergeList(LinkListLa,LinkListLb,LinkList*Lc){LinkListpa,pb,pc;pa=La->next;pb=Lb->next;*Lc=pc=La;while(pa&&pb) {if(Less_EqualList(&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);}intprintlist(LinkListL){inti;LinkListp;p=L;printf("name stuno age score\n");while(p->next) {p=p->next;printf("%-10s%s\t%d\t%d\n",p->,p->data.stuno,p->data.age,p->data.score);}printf("\n");}intListInsert(LinkListL,inti,ElemTypee){LinkListp,s;intj;p=L;j=0;while(p&&jnext;++j;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;returnOK;}/*ListInsertBeforei*/main(){structSTUe;LinkListLa,Lb,Lc;clrscr();printf("\n\n------------------ListDemoisrunning...----------------\n\n");printf("FirstisInsertListfunction.\n");-26实用文案init(&La);strcpy(,"stu1");strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(La,1,e);strcpy(,"stu3");strcpy(e.stuno,"100002");e.age=80;e.score=1000;ListInsert(La,2,e);printlist(La);getch();strcpy(,"stu5");strcpy(e.stuno,"100003");e.age=80;e.score=1000;ListInsert(La,3,e);printlist(La);getch();init(&Lb);strcpy(,"stu2");strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(Lb,1,e);strcpy(,"stu4");strcpy(e.stuno,"100002");e.age=80;e.score=1000;ListInsert(Lb,2,e);strcpy(,"stu6");strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(Lb,3,e);printlist(Lb);getch();MergeList(La,Lb,&Lc);printlist(Lc);getch();strcpy(,"stu2");strcpy(e.stuno,"100001");标准文档第二章 线性表e.age=80;e.score=1000;ListInsert(Lb,1,e);strcpy(,"stu4");strcpy(e.stuno,"100002");e.age=80;e.score=1000;ListInsert(Lb,2,e);strcpy(,"stu6");strcpy(e.stuno,"100001");e.age=80;e.score=1000;ListInsert(Lb,3,e);printlist(Lb);getch();MergeList(La,Lb,&Lc);printlist(Lc);getch();}五、循环链表⒈循环链表的存储结构线性链表的存储结构循环链表是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便，如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储-28实用文案位置分别是(rear–>next)—>next和rear，显然，查找时间都是 O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。例在链表上实现将两个线性表(a1，a2，a3，⋯an)和(b1，b2，b3，⋯bn)链接成一个线性表的运算。linklistconnect(linklistheada ，linklistheadb){ linklistp=heada —>next;heada —>next=(headb—next)—>nextfree(headb —>next);headb —>next=p;return(headb);}⒉双向链表的存储结构单向链表的缺点是什么？如何寻找结点的直接前趋。双向链表(Doublelinkedlist) 可以克服单链表的单向性的缺点。在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链。⑴线性表的双向链表存储结构typedefstructDulNode{structDulNode*prior;ElemTypedata;structDulNode*next;}DulNode,*DuLinkList;双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。对指向双向链表任一结点的指针 d，有下面的关系：d->next->prior=d->prior->next=d标准文档第二章 线性表即：当前结点后继的前趋是自身，当前结点前趋的后继也是自身。⑵双向链表的删除操作StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){if(!(p=GetElemP_DuL(L,i)))returnERROR;e=p->data;p->prior->next=p->next;p->next->prior=p->pror;free(p);returnOK;}//ListDelete_DuL⑶双向链表的插入操作注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为O(1)。StatusListInsert_DuL(DuLinkList&L,inti,ElemType&e){if(!(p=GetElemP_DuL(L,i)))returnERROR;if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))returnERROR;s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;-30实用文案returnOK;}//ListInsert_DuL六、一个完整的带头结点的线性链表类型定义：typedefstructLNode{ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct{Linkhead,tail;intlen;}LinkList;StatusMakeNode(Link&p,ElemTypee);//分配由 p指向的值为 e的结点，并返回 OK；若分配失败，则返回 ERRORvoidFreeNode(Link&p);//释放p所指结点StatusInitLinst(LinkList&L);//构造一个空的线性链表 LStatusDestroyLinst(LinkList&L);销毁线性链表L，L不再存在StatusClearList(LinkList&L);将线性链表L重置为空表，并释放原链表的结点空间StatusInsFirst(Linkh,Links);//已知h指向线性链表的头结点，将 s所指结点插入在第一个结点之前StatusDelFirst(Linkh,Link&q);//已知h指向线性链表的头结点，删除链表中的第一个结点并以 q返回StatusAppend(LinkList&L,Links);//将指针 s所指(彼此以指针相链 )的一串结点链接在线性链表 L的最后一个结点之后，并改变链表L的尾指针指向新的尾结点StatusRemove(LinkList&L,Link&q);删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点StatusInsBefore(LinkList&L,Link&p,Links);//已知p指向线性链表 L中的一个结点，将 s所指结点插入在 p所指结点之前，并修改指针p指向新插入的结点StatusInsAfter(LinkList&L,Link&p,Links);//已知p指向线性链表 L中的一个结点，将 s所指结点插入在 p所指结点之后，并修改指针p指向新插入的结点StatusSetCurElem(Link&p,ElemTypee);//已知p指向线性链表中的一个结点，用 e更新p所指结点中数据元素的值标准文档第二章 线性表ElemTypeGetCurElem(Linkp);//已知p指向线性链表中的一个结点，返回 p所指结点中数据元素的值StatusListEmpty(LinkListL);若线性链表L为空表，则返回TRUE,否则返回FALSEintListLength(LinkListL);返回线性链表L中的元素个数PositionGetHead(LinkListL);返回线性链表L中头结点的位置PositionGetLast(LinkListL);返回线性链表L中最后一个结点的位置PositionPriorPos(LinkListL,Linkp);//已知p指向线性链表 L中的一个结点，返回 p所指结点的直接前趋的值若无前趋，返回NULLPositionNextPos(LinkListL,Linkp);//已知p指向线性链表 L中的一个结点，返回 p所指结点的直接后继的值若无后继，返回NULLStatusLocatePos(LinkListL,inti,Link&p);//返回p指示线性链表 L中第i个结点的位置并返回 OK,i值不合法时返回 ERRORPositionLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));//返回线性链表 L中第1个与e满足函数 compare()判定关系的元素的位置，//若下存在这样的元素，则返回 NULLStatusListTraverse(LinkListL,Status(*visit)());//依次对L的每个元素调用函数 visit() 。一旦 visit() 失败，则操作失败。七、线性表的链式存储结构小结与顺序表不同，链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可分布在内存中任何位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息（即指针或链）。这两部分信息组成链表中的结点结构。一个单链表由头指针的名字来命名。对于单链表，其操作运算主要有建立单链表(头插法、尾插法和在链表开始结点前附加一个头结点的算法)、查找(按序号和按值)、插入运算、删除运算等。以上各运算的平均时间复杂度均为O(n).其主要时间是耗费在查找操作上。循环链表是一种首尾相接的链表。也就是终端结点的指针域不是指向NULL空而是指向开始结点(也可设置一个头结点)，形成一个环。采用-32实用文案循环链表在实用中多采用尾指针表示单循环链表。这样做的好处是查找头指针和尾指针的时间都是O(1)，不用遍历整个链表了。判别链表终止的条件也不同于单链表，它是以指针是否等于某一指定指针如头指针或尾指针来确定。双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,这样形成的链表就有两条不同方向的链。使得从已知结点查找其直接前趋结点可以和查找其直接后继结点的时间一样缩短为O(1)。双链表一般也由头指针head惟一确定。双链表也可以头尾相链接构成双(向)循环链表。关于顺序表和链表的比较，请看下表：具体要求 顺序表适于线性表长度变化基于空间不大，易于事先确定其大小时采用。由于顺序表是一种随机存储结构，当线性基于时间表的操作主要是查找时，宜采用。

链表适于当线性表长度变化大，难以估计其存储规模时采用。链表中对任何位置进行插入和删除都只需修改指针，所以这类操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。2.4 一元多项式的表示和相加表处理的典型应用：符号多项式的操作。一个一元多项式Pn(x)可记作：Pn(x)=p0+p1X+p2X2+⋯⋯+pnXn它由n+1个系数唯一确定，在计算机里，可用一个线性表表示：P=(p0，p1，p2，⋯⋯，pn)每一项的指数i隐含在其系数pi的序号里。若Qm(x)是一元多项式，则：Q=(q0，q1，q2，⋯⋯，qm)不失一般性，设 m<n，则Rn(x)=Pn(x)+Qm(x),即：R=(p0+q0,p1+q1,p2+q2,⋯⋯,pm+qm,pm+1,⋯⋯,pn)标准文档第二章 线性表若采用顺序存储结构，则多项式表示和相加问题似乎已经解决。然而，在通常的应用中，多项式的次数可能很高且变化很大，如：S(x)=1+3x1000+2x20000就要用一长度为20001的线性表来表示，表中仅有三个非零元素，造成内存空间的极大浪费，但是如果只存储非零系数项，则显然必须同时存储相应的指数：P=((p0，e0),(p1，e1),(p2，e2),⋯⋯，(pn,en))该多项式也可以有两种存储表示方法：顺序存储结构适合只对多项式进行“求值”等不改变多项式的系数和指数的运算；其他运算多采用链式存储结构。ADTPolynomial(P40)typedefstruct{floatcoef;int expn;}term,ElemType;typedefLinkListpolynomial;// 用带头结点的有序链表表示多项式 voidCreatPolyn(polynomial&P,intm){InitList(P);h=GetHead(P);e.coef=0.0;e.expn=-1;SetOurElem(h,e);for(i=1;i<=m;++i){scanf(e.coef,e.expn);if(!LocateElem(P,e,q,(*cmp)())){if(MaleNode(s,e))InsFirst(q,s);}}}//CreatPolynvoidAddPolyn(polynomial&Pa,polynomial&Pb){ha=GetHead(Pa);hb=GetHead(Pb);qa=NextPos(Pa,ha);qb=NextPos(Pb,hb);while(qa&&qb){a=GetCurElem(qa);b=GetCurElem(qb);switch(*cmp(a,b)){case –1;//PA 中当前结点的指数值小ha=qa;qa=NextPos(Pa,qa);break;case0;// 两者的指数值相等sum=a.coef+b.coef;if(sum!=0.0){// 修改PA中当前结点的系数值-34实用文案SetCurElem(qa,sum);ha=qa;}else{// 删除PA中当前结点DelFirst(ha,qa);FreeNode(qa);}DelFirst(hb,qb);FreeNode(qb);qb=NextPos(Pb,qb);qa=NextPos(Pa,qa);break;case1://PB 中当前结点的指数值小DelFirst(hb,qb);InsFirst(ha,qb);Qb=NextPos(Pb,hb);ha=NextPos(Pa,ha);break;}//switch}//whileif(!ListEmpty(Pb))Append(Pa,qb);// 链接Pb中剩余结点FreeNode(hb);}//AddPolyn标准文档第二章 线性表习题二2.1试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。2.2何时选用顺序表、何时选用链表作为线性表的存储结构为宜 ?在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：⑴基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。⑵基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2.4为什么在单循环链表中设置尾指针比设置头指针更好 ?尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为 O(n)。2.5在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?分别讨论三种链表的情况。-36实用文案⑴单链表。当我们知道指针 p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。⑵双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。⑶单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为 O(n)。2.6 下述算法的功能是什么?Demo(LinkListL){//L 是无头结点单链表 ListNode*Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}returnL;}//Demo该算法的功能：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。2.8 试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1) 就地逆置的操作，所谓"就地"指辅助空间应为 O(1)。⒈顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：顺序表结构定义同上题voidReverseList(Seqlist*L) {DataTypetemp;// 设置临时空间用于存放 datainti;for(i=0;i<=L->length/2;i++)//L->length/2 为整除运算{temp=L->data[i];// 交换数据L->data[i]=L->data[L->length-1-i];L->data[L->length-1-i]=temp;}}⒉链表：标准文档第二章 线性表可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下：⑴当链表为空表或只有一个结点时，该链表的逆置链表与原表相同。⑵当链表含2个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的：结点结构定义如下：typedefcharDataType;// 假设结点的数据域类型的字符typedefstructnode{// 结点类型定义DataTypedata;// 结点的数据域structnode*next;// 结点的指针域}ListNode;typedefListNode*LinkList;ListNode*p;LinkListhead;LinkListReverseList(LinkListhead){将head所指的单链表(带头结点)逆置ListNode*p,*q;// 设置两个临时指针变量if(head->next&&hea