C语言程序设计与数据结构课件第13章.ppt

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为表长，n0 时称为空表。特点：表中相邻元素之间存在着顺序关系。将 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为整数,如果1iListLength(L)，删除线性表中的第i个数据元素，并用e返回其值，函数值返回真，线性表的长度减1；否则函值返回假。,C语言程序设计与数据结构,13.2 线性表的顺序表示及基本操作,13.2.1 线性表的顺序表示 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。,C语言程序设计与数据结构,13.2.2 顺序表的基本操作实现 1.初始化Status InitList_sq(SqList/成功返回OK/InitList_sq,C语言程序设计与数据结构,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语言实现顺序表的插入：Status ListInsert_sq(SqList/ListInsert_sq,C语言程序设计与数据结构,3.删除运算 线性表的删除运算是指将表中第 i 个元素从线性表中去掉，删除后使原表长为 n 的线性表成为表长为 n-1 的线性表：,C语言程序设计与数据结构,用类C语言实现顺序表的删除运算int ListDelete(SQ_LIST*L,int i,EntryType*e)if(IsEmpty(L)return ERROR;/检测线性表是否为空 if(iL-length)return ERROR;/检查i值是否合理*e=L-itemi-1;/将欲删除的数据元素内容保留在e所指示的存储单元中 for(j=i;jlength-1;j+)/将线性表第i+1个元素之后的所有元素向前移动 L-itemj-1=L-itemj;L-length-;/线性表长度减1return OK;/ListDelete,C语言程序设计与数据结构,13.3 线性表的链式存储,线性表的链式存储结构不需要用地址连续的存储单元来实现，因为它不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系，因此对线性表的插入、删除不需要移动数据元素。,C语言程序设计与数据结构,13.3.1 单链表 链表是通过一组任意的存储单元来存储线性表中的数据元素的。为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息 ai 之外，还需要和ai一起存放其后继 ai+1 所在的存贮单元的地址，这两部分信息组成一个“结点”,C语言程序设计与数据结构,链表是由一个个结点构成的，结点定义如下：typedef struct LNodeElemType data;/数据域struct LNode*next;/指针域 LNode,*LinkList;,C语言程序设计与数据结构,通常我们用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量 L、H 中，头指针为“NULL”则表示一个空表。,C语言程序设计与数据结构,1.查找操作用类C语言实现单链表上的查询(查找第 i 个元素)：Status GetElem_L(LinkList L,int i,ElemType/GetElem_L,C语言程序设计与数据结构,2.插入操作Status ListInsert_L(LinkList/LinstInsert_L,C语言程序设计与数据结构,3.删除操作Status ListDelete_L(LinkList/ListDelete_L,C语言程序设计与数据结构,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语言程序设计与数据结构,双向链表结点的定义如下：typedef struct DuLnode*pointer;typedef struct DuLNode datatype data;pointer prior,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-PRIOR；因此可直接将*P删除掉。在单循环链表中，可从P结点依次扫描到其前驱结点，故也能删除掉该结点。,C语言程序设计与数据结构,2、试分别用顺序表和单链表作为存储结构，实现线性表的就地逆置。,分析：顺序表 VOID REVERSELIST(SQLIST*L)DATATYPE T;INT I,J;FOR(I=0;ILENGTH/2-1;I+)J=L-LENGTH-1-I;T=L-ELEMI;L-ELEMI=L-ELEMJ;L-ELEMJ=T;,C语言程序设计与数据结构,分析：单链表 VOID REVERSELIST(LINKLIST*L)LNODE*P,*Q;P=L-NEXT;L-NEXT=NULL;WHILE(P)Q=P-NEXT;P-NEXT=L-NEXT;L-NEXT=P;P=Q;,C语言程序设计与数据结构,3、已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为M和N，试写一算法将两个链表连接在一起。,C语言程序设计与数据结构,分析：LINKLIST CONNECT(LINKLIST L1,LINKLIST L2,INT M,INT N)LISTNODE*P,*Q;INT K;IF(MN)K=N;P=L2;Q=L1;ELSE K=M;P=L2;Q=L2;WHILE(K0)P=P-NEXT;K-;P-NEXT=Q-NEXT;FREE(Q);IF(MN)RETURN L2;ELSE RETURN L1;,