第2章线性表1

第2章线性表线性结构的特点：1）存在着一个头（第一个元素）；2）存在着一个尾（最后一个元素）；3）除了第一个元素外，其它的都有前驱（前面的那个元素）；4）除了最后一个元素外，其它的都有后继。2.1线性表的类型定义1、什么是线性表：n个数据元素存在着前后关系的元素序列。线性表有两种：顺序结构（数组）、链式结构（链表）。2、线性表的抽象数据类型：ADTList{数据对象：数据关系：基本操作：};2.2线性表的顺序表示和实现2.2.1顺序表顺序表示：就是数组，但是与C语言中定义数组的方法略有不同。在C中，定义一个100个元素的数组：inta[100];缺陷：将数组的长度写死，就只能装100个，多余的放不下。现在我们可以定义一个可变长度的顺序表，可以随着要求的增加而变长，要求减少而变短，必须使用C语言中malloc、realloc、free函数实现。int*pa,*pb;pa=(int*)mallc(100*sizeof(int));pb=(int*)realloc(pa,200*sizeof(int));//注意：此函数非常耗时free(pa);free(pb);另外，malloc和realloc都可能失败，所以需要在程序中进行判别：if((pa=(int*)mallc(100*sizeof(int))==NULL){printf(申请空间失败);exit(1);//直接退出程序}另外，一个可变长数组，当其变长后，其长度我们应该掌握，还需要掌握里面现在已经存放了多少个数据，从而可以形成一个结构体：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefintElemType;typedefstruct{ElemType*elem;//指向将要申请空间的首地址，其中ElemType就是用户所需要的数据类型，此处可假设为intintlength;//目前该顺序表中已经装了多少个元素，初始时为0个intlistsize;//申请到的空间的大小，一开始为100}SqList;第一个算法：初始化顺序表InitList_Sq函数，InitList_Sq(SqList&L)，用来初始化L，使得L有真实的空间。SqListL;//定义变量L，但是L中的elem没有空间。L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));L.length=0;L.listsize=LIST_INIT_SIZE;2.2.2课堂练习1、将顺序表的另外几个函数实现：1）LocateElemList_Sq：定位元素，从L中查找元素e所在的位置，如果存在返回TRUE，如果不存在，返回FALSE2）ClearList_Sq：将L清空3）DestroyList_Sq：销毁L4）ListEmpty_Sq：判断L是否是空顺序表5）ListInsert_Sq：将元素e插入到线性表L的第i个位置6）ListDelete_Sq：从线性表L中删除第i个位置的元素7）ListTraverse_Sq：遍历线性表L，从第0个元素到第L.length-1个元素，一一输出。2.2.3课后练习1、MergeList_Sq：已知LA和LB均为非递减排列的顺序表，将其合并到LC中，并使LC的结果也是非递减排列的。（参照书P26）2、练习书C语言部分的最后文件部分。3、练习书试卷12.3线性表的链序表示和实现顺序表的主要优点：随机存取元素比较方便，如要第5个元素，可直接取：L.elem[5]，其时间复杂度为O(1)。缺点：1）每插入或删除一个元素，都需要移动大量的元素。如，目前整个顺序表中有10个元素，现在要在第3个位置上插入一个元素，则必须从第4—第9个元素向后面移动一个位置，如果要删除第3个元素，则从第4—9个元素需要向elem*length=6listsize=100SqList574972192883830123456...989936ei=3前移动。总之，平均起来，需要n/2个元素。时间复杂度为O(n)。2）事先很难准确地估计空间的大小，如果设得太小，后面不断地插入，使得空间不够，需要用realloc函数来扩大空间（这个函数效率非常地低）。如果事先设得太大，又浪费了空间。线性表的链式表示，也就俗称的“链表”，LinkList2.3.1线性链表在顺序表中，元素都是存放在连续的空间中，所以才能够用L.elem[5]这种方法进行随机存取，因为它们的地址可以通过简单的运算得出。链表是这样构成的：数据在内存中的位置不连续，可以乱七八糟。但是，前面的一个元素都记住了后面一个元素的位置（地址），这样，第1个元素记住了第2个元素，第2个记住了第3个，……，这样，只要从第1个元素出发，就能找出所有元素，就像是一个链条一样，。typedefstructLNode{A2001010000B3024020010C3069030240D030690L=10000L4927892618^L^1data*next234537pqj=2i=312ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListL;操作：1、初始化StatusInit_LinkList(LinkList&L){L=(LinkList)malloc(sizeof(LNode));if(L==NULL)exit(1);//申请空间失败L－next=NULL;returnOK;}2、判空操作给定一个链表L，判断它是否为空表，实际上就是判断L-next是否为NULL。StatusLinkList_Empty(LinkListL){if(L-next==NULL)returnTRUE;elsereturnFALSE;returnL-next==NULL;}3、插入元素在指定的位置i上，插入一个元素e。StatusInsert_LinkList(LinkList&L,inti,ElemTypee){intj=0;LinkListq=L;while(ji-1&&q!=NULL){q=q-next;j++;}if(q==NULL||ji-1)//i的值太大或太小，均不合法returnERROR;p=(LinkList)malloc(sizeof(LNode));p-data=e;p-next=q-next;q-next=p;returnOK;}4、删除元素StatusDelete_LinkList(LinkList&L,inti,ElemType&e){intj=0;LinkListq=L;while(ji-1&&q!=NULL){q=q-next;j++;}if(q==NULL||ji-1)//i的值太大或太小，均不合法returnERROR;p=q-next;q-next=p-next;e=p-data;free(p);returnOK;}5、由一个没有初始化的L，创建一个完整的链表，元素在一个数组a中，共有n个元素。L4927892618^12345qj=2i=3pL57^L574972361928830123456...9899aps57^1497236s1）尾插法：将有n个元素的数组a创建为一个链表，使用尾插法：StatusCreate_LinkList_Tail(LinkList&L,ElemTypea[],intn){LinkListL;Init_LinkList(L);p=L;for(i=0;in;i++){s=(LinkList)malloc(sizeof(LNode));s-data=a[i];s-next=NULL;p-next=s;p=s;}returnOK;}2）头插法：每个元素都插在表头，StatusCreate_LinkList_Head(LinkList&L,ElemTypea[],intn){LinkListL;Init_LinkList(L);for(i=0;in;i++){s=(LinkList)malloc(sizeof(LNode));s-data=a[i];s-next=L-next;L-next=s;}returnOK;}6、遍历链表StatusTraverse_LinkList(LinkListL){LinkListp=L-next;while(p!=NULL){printf(p-data);p=p-next;}returnOK;}7、连接链表有两个链表LA和LB，现在要将他们合并到LA中，将LB接到LA的后面。StatusConnect_LinkList(LinkList&LA,LinkList&LB){LinkListp=LA;while(p-next!=NULL){p=p-next;}p-next=LB-next;free(LB);LB=NULL;returnOK;}8、合并链表1）合并后，LA和LB还存在有两个非递减有序的链表LA、LB，现在要将他们合并到LC中去，并使LC也非递减有序。StatusMerge_LinkList(LinkListLA,LinkListLB,LinkList&LC){LC=(LinkList)malloc(sizeof(LNode));LC-next=NULL;p=LA-next;LA4927892618^12345p5617234552^LBLA13^27364552^1234519^27334549^LBpqLCtq=LB-next;t=LC;while(p&&q)//p!=NULL&&q!=NULL{if(p-dataq-data){s=(LinkList)malloc(sizeof(LNode));s-next=NULL;s-data=p-data;p=p-next;}else{s=(LinkList)malloc(sizeof(LNode));s-next=NULL;s-data=q-data;q=q-next;}t-next=s;t=s;}if(p==NULL)//LA先结束，将LB拷贝到LC中{while(q!=NULL){s=(LinkList)malloc(sizeof(LNode));s-next=NULL;s-data=q-data;q=q-next;t-next=s;t=s;}}else{while(p!=NULL){s=(LinkList)malloc(sizeof(LNode));s-next=NULL;s-data=p-data;p=p-next;t-next=s;t=s;}}returnOK;}2）合并后，LA和LB不存在，LC也是按非递减有序排列。作为今天的课后练习9、将链表逆置StatusInverse_LinkList(LinkList&L){M=(LinkList)malloc(sizeof(LNode));M-next=NULL;p=L-next;while(p!=NULL){L-next=p-next;p-next=M-next;M-next=p;p=L-next;}returnOK;}10、课后练习：1）合并后，LA和LB不存在，LC也是按非递减有序排列。2）判断一个链表L是否对称。L49^27892618^12345Mp2.3.2几种特殊的线性链表1、不带头结点的链表1）初始化：LinkListL=NULL;2）判空：if(L==NULL)这就是空3）插入元素e到第i个位置上去if(L==NULL)returnERROR;//空表if(i==1)//要插入到最前面去。{p=malloc(...);p-data=e;p-next=L;L=p;}j=1;LinkListp=L;while(...){}4）删除第i个位置的元素：5）栈、队列，都可以用链表来实现，如果使用不带头结点的链表，十分麻烦。2、单循环链表1）初始化：对比：单