《C语言程序设计与数据结构》第13章 线性表

C语言程序设计与数据结构第十三章线性表C语言程序设计与数据结构本章学习内容线性表的定义线性表的基本运算线性表的基本操作线性表的链式存储C语言程序设计与数据结构线性表是最基本、最常用的一种数据结构。它在计算机内的存储方法有两种：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。C语言程序设计与数据结构13.1线性表及其基本运算13.1.1线性表的定义线性表是最常用和最简单的一种数据结构。特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。英文字母表（A，B，…，Z）是线性表，表中每个字母是一个数据元素（结点）。扑克牌的点数（2，3，…，10，J，Q，K，A）也是一个线性表，其中数据元素是每张牌的点数和花色。C语言程序设计与数据结构线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为：(a1，a2，…ai-1，ai，ai+1，…an)其中n为表长，n＝0时称为空表。特点：表中相邻元素之间存在着顺序关系。将ai-1称为ai的直接前趋，ai+1称为ai的直接后继。就是说：对于ai，当i=2，...，n时，有且仅有一个直接前趋ai-1.，当i=1，2，...，n-1时，有且仅有一个直接后继ai+1，而a1是表中第一个元素，它没有前趋，an是最后一个元素，无后继。C语言程序设计与数据结构13.1.2线性表的基本运算(1)InitList(L)L是没有初始化的线性表,为L开辟空间并将L置为空表。(2)DestroyList(L)线性表L已存在,将L的存储空间释放。C语言程序设计与数据结构(3)ClearList(L)线性表L已存在,将表L置为空表。(4)emptyList(L)线性表L已存在,如果L为空表则返回真，否则返回假。(5)ListLength(L)线性表L已存在,如果L为空表则返回0，否则返回表中的元素个数。C语言程序设计与数据结构(6)Locate(L，e)表L已存在，e为线性表中元素或与之同型元素,如果L中存在元素e，则返回元素e所在位置，如果L中不存在元素e，则返回0。(7)Getelem(L，i)表L存在，i为整数,i值合法，即1iListLength(L)。返回线性表L中第i个元素的值，否则提示出错。C语言程序设计与数据结构(8)InsertList(L，i，e)表L已存在，e的数据类型同线性表中数据元素，且1iListLength(L)+l，在L中第i个位置前插入新的数据元素e，现行表L的长度加1。(9)DeleteList(L，i，e)表L已存在且非空，i为整数,如果1≤i≤ListLength(L)，删除线性表中的第i个数据元素，并用e返回其值，函数值返回真，线性表的长度减1；否则函值返回假。C语言程序设计与数据结构13.2线性表的顺序表示及基本操作13.2.1线性表的顺序表示线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。C语言程序设计与数据结构13.2.2顺序表的基本操作实现1.初始化StatusInitList_sq(SqList&L){L.elem=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));//分配空间if(!L.elem)exit(OVERFLOW);//若分配空间不成功，返回OVERFLOWL.length=0;//将当前线性表长度置0L.listsize=INIT_SIZE;returnOK;//成功返回OK}//InitList_sqC语言程序设计与数据结构2.插入运算在线性表L中第i个数据元素之前插入数据元素e，插入后使原表长为n的表：(a1，a2，...，ai-1，ai，ai+1，...，an)成为表长为n+1表：(a1，a2，...，ai-1，e，ai，ai+1，...，an)其中i的取值范围为1=i=n+1。C语言程序设计与数据结构用类C语言实现顺序表的插入：StatusListInsert_sq(SqList&L,inti,ElemTypex){if(i1||iL.length+1)//判断输入是否合法returnERROR;if(L.length=L.Listsize){//判断空间是否足够newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;//修改顺序表的参数L.listsize+=INCREMENT;}q=&(L.elem[i-1]);//q为插入位置,C语言数组下标从0开始for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;//移动元素并插入*q=x;L.length++;returnOK;}//ListInsert_sqC语言程序设计与数据结构3.删除运算线性表的删除运算是指将表中第i个元素从线性表中去掉，删除后使原表长为n的线性表成为表长为n-1的线性表：C语言程序设计与数据结构用类C语言实现顺序表的删除运算intListDelete(SQ_LIST*L,inti,EntryType*e){if(IsEmpty(L))returnERROR;//检测线性表是否为空if(i1||iL-length)returnERROR;//检查i值是否合理*e=L-item[i-1];//将欲删除的数据元素内容保留在e所指示的存储单元中for(j=i;j=L-length-1;j++)//将线性表第i+1个元素之后的所有元素向前移动L-item[j-1]=L-item[j];L-length--;//线性表长度减1returnOK;}//ListDeleteC语言程序设计与数据结构13.3线性表的链式存储线性表的链式存储结构不需要用地址连续的存储单元来实现，因为它不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系，因此对线性表的插入、删除不需要移动数据元素。C语言程序设计与数据结构13.3.1单链表链表是通过一组任意的存储单元来存储线性表中的数据元素的。为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继ai+1所在的存贮单元的地址，这两部分信息组成一个“结点”C语言程序设计与数据结构链表是由一个个结点构成的，结点定义如下：typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList;C语言程序设计与数据结构通常我们用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量L、H中，头指针为“NULL”则表示一个空表。C语言程序设计与数据结构1.查找操作用类C语言实现单链表上的查询(查找第i个元素)：StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的单链表的头指针，当第i个元素存在时，将该元素的值赋给e并返回OK，否则返回ERRORp=L-next;k=1;//初始化，p指向第一个结点，k为计数器while(p&&ki){//顺指针向后查找，直到p指向第i个元素或p为空p=p-next;++k;}//循环的退出条件为k=i或到达单链表结尾(p为空)if(!p||ki)returnERROR;//第i个元素不存在e=p-data;returnOK;}//GetElem_LC语言程序设计与数据结构2.插入操作StatusListInsert_L(LinkList&L,inti,ElemTypee){//在带头结点的单链表L中第i个位置之前插入元素ep=L;k=0;//初始化，p指向头结点，k为计数器while(p&&ki-1){//逐步移动指针p，直到p指向第i-1个元素或p为空p=p-next;++k;}if(!p||ki-1)returnERROR;//无法插入if(!(s=(LinkLinst)malloc(sizeof(LNode))))//申请元素e的结点空间returnOVERFLOW;//内存无空闲单元，无法申请到空间s-data=e;s-next=p-next;//插入元素e的结点p-next=s;returnOK;}//LinstInsert_LC语言程序设计与数据结构3.删除操作StatusListDelete_L(LinkList&L,inti,ElemType&e){//在带头结点的单链表L中，删除第i个元素，并由e返回其值p=L;k=0;//初始化，p指向头结点，k为计数器while(p-next&&ki-1){//逐一移动指针p，直到p指向第i-1个元素或p为空p=p-next;++k;}if(!p-next||ji-1)returnERROR;//无法删除q=p-next;//令q指向待删除的元素结点p-next=q-next;//修改结点p的指针域，指向第i-1个结点e=q-data;free(q);//删除结点q，释放内存空间returnOK;}//ListDelete_LC语言程序设计与数据结构13.3.2循环链表对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。C语言程序设计与数据结构单循环链表可以从表中任意结点开始遍历整个链表，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，可以使得操作效率得以提高。C语言程序设计与数据结构p=R1–next;/*保存R1的头结点指针*/R1-next=R2-next-next;/*头尾连接*/free(R2-next);/*释放第二个表的头结点*/R2-next=p;/*组成循环链表*/C语言程序设计与数据结构13.3.3双向链表单链表的结点中只有一个指向其后继结点的指针域next，因此若已知某结点的指针为p，其后继结点的指针则为p-next，而找其前驱则只能从该链表的头指针开始，顺着各结点的next域进行，每个结点再加一个指向前驱的指针域，用这种结点组成的链表称为双向链表。C语言程序设计与数据结构双向链表结点的定义如下：typedefstructDuLnode*pointer;typedefstructDuLNode{datatypedata;pointerprior,next;}//DuLNode;C语言程序设计与数据结构双向链表通常也是用头指针标识，通过某结点的指针p即可以直接得到它的后继结点的指针p-next，也可以直接得到它的前驱结点的指针p-prior。这样在有些操作中需要找前驱时，则勿需再用循环。图13.8是带头结点的双向循环链表示意图C语言程序设计与数据结构1.双向链表中结点的插入：设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面，插入示意图如图13.9所示。操作如下：s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;C语言程序设计与数据结构2.双向链表中结点的删除：设p指向双向链表中某结点，删除*p。操作示意图如图13.10所示。操作如下：①p-prior-next=p-next;②p-next-prior=p-prior;C语言程序设计与数据结构13.4典型习题分析解答1、在单链表、双链表和单循环链表中，若仅知道指针P指向某结点，不知道头指针，能否将结点*P从相应的链表中删去？分析：在单链表中，由于无法找到结点*P的直接前驱的位置，所以无法删除该结点；在双链表中，结点*P的前驱位置是P-