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

线性表是最基本、最常用的一种数据结构。它在计算机内的存储方法有两种：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。第1页/共34页13.1 线性表及其基本运算线性表及其基本运算 13.1.1 线性表的定义 线性表是最常用和最简单的一种数据结构。特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。英文字母表（A，B，Z）是线性表，表中每个字母是一个数据元素（结点）。扑克牌的点数（2，3，10，J，Q，K，A）也是一个线性表，其中数据元素是每张牌的点数和花色。第2页/共34页 线性表是具有相同数据类型的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 是最后一个元素，无后继。第3页/共34页13.1.2 线性表的基本运算(1)InitList(L)L是没有初始化的线性表,为L开辟空间并将L置为空表。(2)DestroyList(L)线性表L已存在,将L的存储空间释放。第4页/共34页(3)ClearList(L)线性表L已存在,将表L置为空表。(4)emptyList(L)线性表L已存在,如果L为空表则返回真，否则返回假。(5)ListLength(L)线性表L已存在,如果L为空表则返回0，否则返回表中的元素个数。第5页/共34页(6)Locate(L，e)表L已存在，e为线性表中元素或与之同型元素,如果L中存在元素e，则返回元素e所在位置，如果L中不存在元素e，则返回0。(7)Getelem(L，i)表L存在，i为整数,i值合法，即1iListLength(L)。返回线性表L中第i个元素的值，否则提示出错。第6页/共34页(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；否则函值返回假。第7页/共34页13.2 13.2 线性表的顺序表示及基本操作线性表的顺序表示及基本操作 13.2.1 线性表的顺序表示 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。第8页/共34页13.2.2 顺序表的基本操作实现 1.初始化Status InitList_sq(SqList&L)L.elem=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType);/分配空间 if(!L.elem)exit(OVERFLOW);/若分配空间不成功，返回OVERFLOW L.length=0;/将当前线性表长度置0L.listsize=INIT_SIZE;return OK;/成功返回OK/InitList_sq第9页/共34页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。第10页/共34页用类C语言实现顺序表的插入：Status ListInsert_sq(SqList&L,int i,ElemType x)if(i L.length+1)/判断输入是否合法return ERROR;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.elemi-1);/q为插入位置,C语言数组下标从0开始 for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/移动元素并插入 *q=x;L.length+;return OK;/ListInsert_sq第11页/共34页3.删除运算 线性表的删除运算是指将表中第 i 个元素从线性表中去掉，删除后使原表长为 n 的线性表成为表长为 n-1 的线性表：第12页/共34页用类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-item j-1=L-item j;L-length-;/线性表长度减1return OK;/ListDelete第13页/共34页13.3 13.3 线性表的链式存储线性表的链式存储 线性表的链式存储结构不需要用地址连续的存储单元来实现，因为它不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系，因此对线性表的插入、删除不需要移动数据元素。第14页/共34页13.3.1 单链表 链表是通过一组任意的存储单元来存储线性表中的数据元素的。为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息 ai 之外，还需要和ai一起存放其后继 ai+1 所在的存贮单元的地址，这两部分信息组成一个“结点”第15页/共34页链表是由一个个结点构成的，结点定义如下：typedef struct LNodeElemType data;/数据域struct LNode *next;/指针域 LNode,*LinkList;第16页/共34页 通常我们用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量 L、H 中，头指针为“NULL”则表示一个空表。第17页/共34页1.查找操作用类C语言实现单链表上的查询(查找第 i 个元素)：Status GetElem_L(LinkList L,int i,ElemType&e)/L是带头结点的单链表的头指针，当第i个元素存在时，将该元素的值赋给e并返回OK，否则返回ERRORp=L-next;k=1;/初始化，p指向第一个结点，k为计数器while(p&k next;+k;/循环的退出条件为k=i或到达单链表结尾(p为空)if(!p|k i)return ERROR;/第i个元素不存在e=p-data;return OK;/GetElem_L第18页/共34页2.插入操作Status ListInsert_L(LinkList&L,int i,ElemType e)/在带头结点的单链表L中第i个位置之前插入元素e p=L;k=0;/初始化，p指向头结点，k为计数器 while(p&k next;+k;if(!p|k i-1)return ERROR;/无法插入 if(!(s=(LinkLinst)malloc(sizeof(LNode)/申请元素e的结点空间 return OVERFLOW;/内存无空闲单元，无法申请到空间 s-data=e;s-next=p-next;/插入元素e的结点 p-next=s;return OK;/LinstInsert_L第19页/共34页3.删除操作Status ListDelete_L(LinkList&L,int i,ElemType&e)/在带头结点的单链表L中，删除第i个元素，并由e返回其值 p=L;k=0;/初始化，p指向头结点，k为计数器 while(p-next&k next;+k;if(!p-next|j i-1)return ERROR;/无法删除 q=p-next;/令q指向待删除的元素结点 p-next=q-next;/修改结点p的指针域，指向第i-1个结点 e=q-data;free(q);/删除结点q，释放内存空间 return OK;/ListDelete_L 第20页/共34页13.3.2 循环链表 对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。第21页/共34页 单循环链表可以从表中任意结点开始遍历整个链表，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，可以使得操作效率得以提高。第22页/共34页p=R1 next;/*保存R1 的头结点指针*/R1-next=R2-next-next;/*头尾连接*/free(R2-next);/*释放第二个表的头结点*/R2-next=p;/*组成循环链表*/第23页/共34页13.3.3 双向链表 单链表的结点中只有一个指向其后继结点的指针域next，因此若已知某结点的指针为p，其后继结点的指针则为p-next，而找其前驱则只能从该链表的头指针开始，顺着各结点的next域进行，每个结点再加一个指向前驱的指针域，用这种结点组成的链表称为双向链表。第24页/共34页双向链表结点的定义如下：typedef struct DuLnode *pointer;typedef struct DuLNode datatype data;pointer prior,next;/DuLNode;第25页/共34页 双向链表通常也是用头指针标识，通过某结点的指针p即可以直接得到它的后继结点的指针p-next，也可以直接得到它的前驱结点的指针p-prior。这样在有些操作中需要找前驱时，则勿需再用循环。图13.8是带头结点的双向循环链表示意图 第26页/共34页 1.双向链表中结点的插入：设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面，插入示意图如图13.9所示。操作如下：s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;第27页/共34页2.双向链表中结点的删除：设p指向双向链表中某结点，删除*p。操作示意图如图13.10所示。操作如下：p-prior-next=p-next;p-next-prior=p-prior;第28页/共34页13.4 典型习题分析解答1、在单链表、双链表和单循环链表中，若仅知道指针P指向某结点，不知道头指针，能否将结点*P从相应的链表中删去？分析：分析：在单链表中，由于无法找到结点在单链表中，由于无法找到结点*P的直接前驱的直接前驱的位置，所以无法删除该结点；在双链表中，结点的位置，所以无法删除该结点；在双链表中，结点*P的前驱位置是的前驱位置是P-PRIOR；因此可直接将；因此可直接将*P删除掉。删除掉。在单循环链表中，可从在单循环链表中，可从P结点依次扫描到其前驱结结点依次扫描到其前驱结点，故也能删除掉该结点。点，故也能删除掉该结点。第29页/共34页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;第30页/共34页分析：单链表 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;第31页/共34页3、已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为M和N，试写一算法将两个链表连接在一起。第32页/共34页分析：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;第33页/共34页C语言程序设计与数据结构感谢您的欣赏！第34页/共34页