搜索
第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、将顺序表的另外几个函数实现：（参见工程：SqList）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语言部分的最后文件部分。elem*length=6listsize=100SqList5749721928830123456...989936ei=33、练习书试卷12.3线性表的链序表示和实现顺序表的主要优点：1）随机存取元素比较方便，如要第5个元素，可直接取：L.elem[5]，其时间复杂度为O(1)。2）查找：如果将顺序表中的元素按照某种方法排列（如排序），则使用二分查找等方法，效率非常高。缺点：1）每插入或删除一个元素，都需要移动大量的元素。如，目前整个顺序表中有10个元素，现在要在第3个位置上插入一个元素，则必须从第4—第9个元素向后面移动一个位置，如果要删除第3个元素，则从第4—9个元素需要向前移动。总之，平均起来，需要n/2个元素。时间复杂度为O(n)。计算方法：（1）插入，假设原表中已经有n个元素，现在要插入一个元素。最坏情况下，这个元素可能要插到第0个位置，则需要移动元素n个；最好情况下，也可能是要插到最末尾，则移动元素个数为0个，平均起来(n+0)/2＝n/2（2）删除，最坏情况下，要删除的是第0个元素，则共需要移动n-1个；最好的情况下，要删除的是第n-1个（最后一个），则不需要移动元素，所以平均起来，(n-1+0)/2=(n-1)/22）事先很难准确地估计空间的大小，如果设得太小，后面不断地插入，使得空间不够，需要用realloc函数来扩大空间（这个函数效率非常地低）。如果事先设得太大，又浪费了空间。线性表的链式表示，也就俗称的“链表”，LinkList2.3.1线性链表在顺序表中，元素都是存放在连续的空间中，所以才能够用L.elem[5]这种方法进行随机存取，因为它们的地址可以通过简单的运算得出。链表是这样构成的：数据在内存中的位置不连续，可以乱七八糟。但是，前面的一个元素都记住了后面一个元素的位置（地址），这样，第1个元素记住了第2个元素，第2个记住了第3个，……，这样，只要从第1个元素出发，就能找出所有元素，就像是一个链条一样，。typedefstructLNode{ElemTypedata;//数据项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;}A2001010000B3024020010C3069030240D030690L=100003、插入元素在指定的位置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)L4927892618^12345qj=2e=3pi=3L4927892618^L^1data*next234537pqj=3i=312带头结点的单链表空表{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个元素。1）尾插法（向尾生长）：将有n个元素的数组a创建为一个链表，使用尾插法：StatusCreate_LinkList_Tail(LinkList&L,ElemTypea[],intn){L^L574972361928830123456...9899aps57^1t57s=malloc(...)s-data=57;s-next=NULL;t-next=s;t=s;49^sInit_LinkList(L);t=L;//t始终指向表尾，s就插入到t的后面for(i=0;in;i++){s=(LinkList)malloc(sizeof(LNode));s-data=a[i];s-next=NULL;t-next=s;t=s;}returnOK;}2）头插法（向头生长）：每个元素都插在表头，作为第一个元素StatusCreate_LinkList_Head(LinkList&L,ElemTypea[],intn){Init_LinkList(L);//初始化L，得到空表Lfor(i=0;in;i++){s=(LinkList)malloc(sizeof(LNode));s-data=a[i];s-next=L-next;L-next=s;}returnOK;}L57^L^574972361928830123456...9899as=malloc(...)s-data=72s-next=L-next;L-next=s;49s726、销毁链表StatusDestroy_LinkList(LinkList&L){LinkListp;p=L-next;while(p!=NULL){L-next=p-next;//绕过pfree(p);p=L-next;}free(L);returnOK;}6、遍历链表StatusTraverse_LinkList(LinkListL){LinkListp=L-next;while(p!=NULL){printf(p-data);p=p-next;}returnOK;}课后练习：1）写一个算法，将数组a中的元素插入到L中去，使得L中的元素有序。LA1827364958^12345p7、连接链表有两个链表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