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

《《C语言程序设计与数据结构》课件第13章.ppt》由会员分享，可在线阅读，更多相关《《C语言程序设计与数据结构》课件第13章.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十三章第十三章 线线 性性 表表C语言程序设计与数据结构本章学习内容本章学习内容线性表的定义线性表的定义线性表的基本运算线性表的基本运算线性表的基本操作线性表的基本操作线性表的链式存储线性表的链式存储 C语言程序设计与数据结构 线性表是最基本、最常用的一种数据结构。它线性表是最基本、最常用的一种数据结构。它在计算机内的存储方法有两种：顺序存储和链式存在计算机内的存储方法有两种：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。储，它的主要基本操作是插入、删除和检索等。C语言程序设计与数据结构13.1 13.1 线性表及其基本运算线性表及其基本运算 13.1.1 13.1.1 线性表的

2、定义线性表的定义 线性表是最常用和最简单的一种数据结构。特线性表是最常用和最简单的一种数据结构。特点是数据元素之间是一种线性关系，数据元素点是数据元素之间是一种线性关系，数据元素“一一个接一个的排列个接一个的排列”。英文字母表（英文字母表（A A，B B，Z Z）是线性表，表中）是线性表，表中每个字母是一个数据元素（结点）。每个字母是一个数据元素（结点）。扑克牌的点数（扑克牌的点数（2 2，3 3，1010，J J，Q Q，K K，A A）也是一个线性表，其中数据元素是每张牌的点数和也是一个线性表，其中数据元素是每张牌的点数和花色花色 。C语言程序设计与数据结构 线性表是具有相同数据类型的线性

3、表是具有相同数据类型的n(n=0)n(n=0)个数据元个数据元素的有限序列，通常记为：素的有限序列，通常记为：(a1 (a1，a2a2，ai-1 ai-1，ai ai，ai+1ai+1，an)an)其中其中n n为表长，为表长，n n0 0 时称为空表。时称为空表。特点：特点：表中相邻元素之间存在着顺序关系。将表中相邻元素之间存在着顺序关系。将 ai-1 ai-1 称称为为 ai ai 的直接前趋，的直接前趋，ai+1 ai+1 称为称为 ai ai 的直接后继。就是说：的直接后继。就是说：对于对于ai ai，当，当 i=2i=2，.，n n 时，有且仅有一个直接前趋时，有且仅有一个直接前趋

4、ai-1.ai-1.，当，当i=1i=1，2 2，.，n-1 n-1 时，有且仅有一个直接后时，有且仅有一个直接后继继 ai+1ai+1，而，而 a1 a1 是表中第一个元素，它没有前趋，是表中第一个元素，它没有前趋，an an 是最后一个元素，无后继。是最后一个元素，无后继。C语言程序设计与数据结构13.1.2 13.1.2 线性表的基本运算线性表的基本运算(1)InitList(L)(1)InitList(L)L L是没有初始化的线性表是没有初始化的线性表,为为L L开辟空间并将开辟空间并将L L置为空表。置为空表。(2)DestroyList(L)(2)DestroyList(L)线性表

5、线性表L L已存在已存在,将将L L的存储空间释放。的存储空间释放。C语言程序设计与数据结构(3)ClearList(L)(3)ClearList(L)线性表线性表L L已存在已存在,将表将表L L置为空表。置为空表。(4)emptyList(L)(4)emptyList(L)线性表线性表L L已存在已存在,如果如果L L为空表则返回真，否则返回假。为空表则返回真，否则返回假。(5)ListLength(L)(5)ListLength(L)线性表线性表L L已存在已存在,如果如果L L为空表则返回为空表则返回0 0，否则返回表中，否则返回表中的元素个数。的元素个数。C语言程序设计与数据结构(6

6、)Locate(L(6)Locate(L，e)e)表表L L已存在，已存在，e e为线性表中元素或与之同型元素为线性表中元素或与之同型元素,如果如果L L中存在元素中存在元素e e，则返回元素，则返回元素e e所在位置，如果所在位置，如果L L中不中不存在元素存在元素e e，则返回，则返回0 0。(7)Getelem(L(7)Getelem(L，i)i)表表L L存在，存在，ii为整数为整数,i,i值合法，即值合法，即1iListLength(L)1iListLength(L)。返。返回线性表回线性表L L中第中第ii个元素的值，否则提示出错。个元素的值，否则提示出错。C语言程序设计与数据结构

7、(8)InsertList(L(8)InsertList(L，ii，e)e)表表L L已存在，已存在，e e的数据类型同线性表中数据元素，且的数据类型同线性表中数据元素，且1iListLength(L)+l1iListLength(L)+l，在，在L L中第中第ii个位置前插入新的数据个位置前插入新的数据元素元素e e，现行表，现行表L L的长度加的长度加1 1。(9)DeleteList(L(9)DeleteList(L，ii，e)e)表表L L已存在且非空，已存在且非空，ii为整数为整数,如果如果1iListLength(L)1iListLength(L)，删，删除线性表中的第除线性表中的

8、第ii个数据元素，并用个数据元素，并用e e返回其值，函返回其值，函数值返回真，线性表的长度减数值返回真，线性表的长度减1 1；否则函值返回假。；否则函值返回假。C语言程序设计与数据结构13.2 13.2 线性表的顺序表示及基本操作线性表的顺序表示及基本操作 13.2.1 13.2.1 线性表的顺序表示线性表的顺序表示 线性表的顺序存储是指在内存中用地址连续的线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表储形式存储的线性表称为顺序表 。C语言程序设计与数据结构13.2.2 13.2.2

9、 顺序表的基本操作实现顺序表的基本操作实现 1.1.初始化初始化Status InitList_sq(SqList&L)Status InitList_sq(SqList&L)L.elem=(ElemType L.elem=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType);/*)malloc(INIT_SIZE*sizeof(ElemType);/分配空间分配空间 if(!L.elem)exit(OVERFLOW);/if(!L.elem)exit(OVERFLOW);/若分配空间不成功，若分配空间不成功，返回返回OVERFLOWOVERFLOW L.l

10、ength=0;/L.length=0;/将当前线性表长度置将当前线性表长度置0 0L.listsize=INIT_SIZE;L.listsize=INIT_SIZE;return OK;/return OK;/成功返回成功返回OKOK/InitList_sq/InitList_sqC语言程序设计与数据结构2.2.插入运算插入运算 在线性表在线性表L L中第中第ii个数据元素之前插入数据元素个数据元素之前插入数据元素e e，插入后使原表长为插入后使原表长为n n的表：的表：(a1(a1，a2a2，.，ai-1ai-1，ai ai，ai+1ai+1，.，an)an)成为表长为成为表长为 n+1

11、n+1 表：表：(a1(a1，a2a2，.，ai-1ai-1，e e，ai ai，ai+1ai+1，.，anan)其中其中 i i 的取值范围为的取值范围为1=i=n+1 1=i=n+1。C语言程序设计与数据结构用类用类C C语言实现顺序表的插入：语言实现顺序表的插入：Status ListInsert_sq(SqList&L,int i,ElemType x)Status ListInsert_sq(SqList&L,int i,ElemType x)if(i L.length+1)/if(i L.length+1)/判断输入是否合法判断输入是否合法return ERROR;return E

12、RROR;if(L.length=L.Listsize)if(L.length=L.Listsize)/判断空间是否足够判断空间是否足够 newbase=(ElemType*)realloc(L.elem,newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.elem

13、=newbase;/修改顺序表的参数修改顺序表的参数 L.listsize+=INCREMENT;L.listsize+=INCREMENT;q=&(L.elemi-1);/qq=&(L.elemi-1);/q为插入位置为插入位置,C,C语言数组下标从语言数组下标从0 0开始开始 for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/移动元素并插入移动元素并插入 *q=x;q=x;L.length+;L.length+;return OK;return OK;/ListIns

14、ert_sq/ListInsert_sqC语言程序设计与数据结构3.3.删除运算删除运算 线性表的删除运算是指将表中第线性表的删除运算是指将表中第 i i 个元素从线个元素从线性表中去掉，删除后使原表长为性表中去掉，删除后使原表长为 n n 的线性表成为表的线性表成为表长为长为 n-1 n-1 的线性表：的线性表：C语言程序设计与数据结构用类用类C C语言实现顺序表的删除运算语言实现顺序表的删除运算int ListDelete(SQ_LIST*L,int i,EntryType*e)int ListDelete(SQ_LIST*L,int i,EntryType*e)if(IsEmpty(L)

15、return ERROR;/if(IsEmpty(L)return ERROR;/检测线性表是否为空检测线性表是否为空 if(iL-length)return ERROR;/if(iL-length)return ERROR;/检查检查ii值是否合理值是否合理 *e=L-itemi-1;/e=L-itemi-1;/将欲删除的数据元素内容保留在将欲删除的数据元素内容保留在e e所指示的存储单元中所指示的存储单元中 for(j=i;jlength-1;j+)/for(j=i;jlength-1;j+)/将线性表第将线性表第i+1i+1个元素之后个元素之后的所有元素向前移动的所有元素向前移动 L-i

16、temj-1=L-itemj;L-itemj-1=L-itemj;L-length-;L-length-;/线性表长度减线性表长度减1 1return OK;return OK;/ListDelete/ListDeleteC语言程序设计与数据结构13.3 13.3 线性表的链式存储线性表的链式存储 线性表的链式存储结构不需要用地址连续的存线性表的链式存储结构不需要用地址连续的存储单元来实现，因为它不要求逻辑上相邻的两个数储单元来实现，因为它不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过据元素物理上也相邻，它是通过“链链”建立起数据建立起数据元素之间的逻辑关系，因此对线性表的插入、删除元素

17、之间的逻辑关系，因此对线性表的插入、删除不需要移动数据元素。不需要移动数据元素。C语言程序设计与数据结构13.3.1 13.3.1 单链表单链表 链表是通过一组任意的存储单元来存储线性表链表是通过一组任意的存储单元来存储线性表中的数据元素的。为建立起数据元素之间的线性关中的数据元素的。为建立起数据元素之间的线性关系，对每个数据元素系，对每个数据元素ai ai，除了存放数据元素的自身，除了存放数据元素的自身的信息的信息 ai ai 之外，还需要和之外，还需要和ai ai一起存放其后继一起存放其后继 ai+1 ai+1 所所在的存贮单元的地址，这两部分信息组成一个在的存贮单元的地址，这两部分信息组

18、成一个“结结点点”C语言程序设计与数据结构链表是由一个个结点构成的，结点定义如下：链表是由一个个结点构成的，结点定义如下：typedef struct LNodetypedef struct LNodeElemType data;ElemType data;/数据域数据域struct LNode *next;struct LNode *next;/指针域指针域 LNode,*LinkList;LNode,*LinkList;C语言程序设计与数据结构 通常我们用通常我们用“头指针头指针”来标识一个单链表，如来标识一个单链表，如单链表单链表L L、单链表、单链表H H等，是指某链表的第一个结点的等

19、，是指某链表的第一个结点的地址放在了指针变量地址放在了指针变量 L L、H H 中，中，头指针为头指针为“NULL”NULL”则表示一个空表。则表示一个空表。C语言程序设计与数据结构1.1.查找操作查找操作用类用类C C语言实现单链表上的查询语言实现单链表上的查询(查找第查找第 i i 个元素个元素)：Status GetElem_L(LinkList L,int i,ElemType&e)Status GetElem_L(LinkList L,int i,ElemType&e)/L/L是带头结点是带头结点的单链表的头指针，当第的单链表的头指针，当第ii个元素存在时，将该元素的值赋给个元素存在

20、时，将该元素的值赋给e e并返回并返回OKOK，否则返回，否则返回ERRORERRORp=L-next;k=1;/p=L-next;k=1;/初始化，初始化，p p指向第一个结点，指向第一个结点，k k为计数器为计数器while(p&k i)/while(p&k next;p=p-next;+k;+k;/循环的退出条件为循环的退出条件为k=ik=i或到达单链表结尾或到达单链表结尾(p(p为空为空)if(!p|k i)return ERROR;/if(!p|k i)return ERROR;/第第ii个元素不存在个元素不存在e=p-data;e=p-data;return OK;return O

21、K;/GetElem_L /GetElem_LC语言程序设计与数据结构2.2.插入操作插入操作Status ListInsert_L(LinkList&L,int i,ElemType e)Status ListInsert_L(LinkList&L,int i,ElemType e)/在带头结点的单链在带头结点的单链表表L L中第中第ii个位置之前插入元素个位置之前插入元素e e p=L;k=0;p=L;k=0;/初始化，初始化，p p指向头结点，指向头结点，k k为计数器为计数器 while(p&k i-1)while(p&k next;p=p-next;+k;+k;if(!p|k i-1

22、)return ERROR;/if(!p|k i-1)return ERROR;/无法插入无法插入 if(!(s=(LinkLinst)malloc(sizeof(LNode)/if(!(s=(LinkLinst)malloc(sizeof(LNode)/申请元素申请元素e e的结点空间的结点空间 return OVERFLOW;/return OVERFLOW;/内存无空闲单元，无法申请到空间内存无空闲单元，无法申请到空间 s-data=e;s-data=e;s-next=p-next;s-next=p-next;/插入元素插入元素e e的结点的结点 p-next=s;p-next=s;re

23、turn OK;return OK;/LinstInsert_L/LinstInsert_LC语言程序设计与数据结构3.3.删除操作删除操作Status ListDelete_L(LinkList&L,int i,ElemType&e)/Status ListDelete_L(LinkList&L,int i,ElemType&e)/在带头结点的在带头结点的单链表单链表L L中，删除第中，删除第ii个元素，并由个元素，并由e e返回其值返回其值 p=L;k=0;p=L;k=0;/初始化，初始化，p p指向头结点，指向头结点，k k为计数器为计数器 while(p-next&k next&k n

24、ext;p=p-next;+k;+k;if(!p-next|j i-1)return ERROR;/if(!p-next|j i-1)return ERROR;/无法删除无法删除 q=p-next;q=p-next;/令令q q指向待删除的元素结点指向待删除的元素结点 p-next=q-next;/p-next=q-next;/修改结点修改结点p p的指针域，指向第的指针域，指向第i-1i-1个结点个结点 e=q-data;free(q);/e=q-data;free(q);/删除结点删除结点q q，释放内存空间，释放内存空间 return OK;return OK;/ListDelete_L

25、 /ListDelete_L C语言程序设计与数据结构13.3.2 13.3.2 循环链表循环链表 对于单链表而言，最后一个结点的指针域是空对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。链表头尾结点相连，就构成了单循环链表。C语言程序设计与数据结构 单循环链表可以从表中任意结点开始遍历整个单循环链表可以从表中任意结点开始遍历整个链表，有时对链表常做的操作是在表尾、表头进行，链表，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而此时可以改变一

26、下链表的标识方法，不用头指针而用一个指向尾结点的指针用一个指向尾结点的指针R R来标识，可以使得操作来标识，可以使得操作效率得以提高。效率得以提高。C语言程序设计与数据结构p=R1 next;/*p=R1 next;/*保存保存R1 R1 的头结点指针的头结点指针*/R1-next=R2-next-next;/*R1-next=R2-next-next;/*头尾连接头尾连接*/free(R2-next);/*free(R2-next);/*释放第二个表的头结点释放第二个表的头结点*/R2-next=p;/*R2-next=p;/*组成循环链表组成循环链表*/C语言程序设计与数据结构13.3.3

27、 13.3.3 双向链表双向链表 单链表的结点中只有一个指向其后继结点的指单链表的结点中只有一个指向其后继结点的指针域针域nextnext，因此若已知某结点的指针为，因此若已知某结点的指针为p p，其后继结，其后继结点的指针则为点的指针则为p-next p-next，而找其前驱则只能从该链表，而找其前驱则只能从该链表的头指针开始，顺着各结点的的头指针开始，顺着各结点的nextnext域进行，每个结域进行，每个结点再加一个指向前驱的指针域，用这种结点组成的点再加一个指向前驱的指针域，用这种结点组成的链表称为双向链表。链表称为双向链表。C语言程序设计与数据结构双向链表结点的定义如下：双向链表结点的

28、定义如下：typedef struct DuLnode *pointer;typedef struct DuLnode *pointer;typedef struct DuLNodetypedef struct DuLNode datatype data;datatype data;pointer prior,next;pointer prior,next;/DuLNode;/DuLNode;C语言程序设计与数据结构 双向链表通常也是用头指针标识，通过某结点的双向链表通常也是用头指针标识，通过某结点的指针指针p p即可以直接得到它的后继结点的指针即可以直接得到它的后继结点的指针p-nextp-

29、next，也，也可以直接得到它的前驱结点的指针可以直接得到它的前驱结点的指针p-priorp-prior。这样在有。这样在有些操作中需要找前驱时，则勿需再用循环。图些操作中需要找前驱时，则勿需再用循环。图13.813.8是带是带头结点的双向循环链表示意图头结点的双向循环链表示意图 C语言程序设计与数据结构 1.1.双向链表中结点的插入：双向链表中结点的插入：设设p p指向双向链表中某结点，指向双向链表中某结点，s s指向待插入的值指向待插入的值为为x x的新结点，将的新结点，将*s s插入到插入到*p p的前面，插入示意图的前面，插入示意图如图如图13.913.9所示。所示。操作如下：操作如下

30、：s-prior=p-prior;s-prior=p-prior;p-prior-next=s;p-prior-next=s;s-next=p;s-next=p;p-prior=s;p-prior=s;C语言程序设计与数据结构2.2.双向链表中结点的删除：双向链表中结点的删除：设设p p指向双向链表中某结点，删除指向双向链表中某结点，删除*p p。操作示意。操作示意图如图图如图13.1013.10所示。所示。操作如下：操作如下：p-prior-next=p-next;p-prior-next=p-next;p-next-prior=p-prior;p-next-prior=p-prior;C语

31、言程序设计与数据结构13.4 13.4 典型典型习题习题分析解答分析解答1 1、在单链表、双链表和单循环链表中，若仅知道指、在单链表、双链表和单循环链表中，若仅知道指针针P P指向某结点，不知道头指针，能否将结点指向某结点，不知道头指针，能否将结点*P P从从相应的链表中删去？相应的链表中删去？分析：分析：在单链表中，由于无法找到结点在单链表中，由于无法找到结点*P P的直接前驱的直接前驱的位置，所以无法删除该结点；在双链表中，结点的位置，所以无法删除该结点；在双链表中，结点*P P的前驱位置是的前驱位置是P-PRIORP-PRIOR；因此可直接将；因此可直接将*P P删除掉。删除掉。在单循环

32、链表中，可从在单循环链表中，可从P P结点依次扫描到其前驱结结点依次扫描到其前驱结点，故也能删除掉该结点。点，故也能删除掉该结点。C语言程序设计与数据结构2 2、试试分分别别用用顺顺序序表表和和单单链链表表作作为为存存储储结结构构，实实现现线线性表的就地逆置。性表的就地逆置。分析：分析：顺序表顺序表 VOID REVERSELIST(SQLIST*L)VOID REVERSELIST(SQLIST*L)DATATYPE T;DATATYPE T;INT I,J;INT I,J;FOR(I=0;ILENGTH/2-1;I+)FOR(I=0;ILENGTH/2-1;I+)J=L-LENGTH-1-

33、I;J=L-LENGTH-1-I;T=L-ELEMI;T=L-ELEMI;L-ELEMI=L-ELEMJ;L-ELEMI=L-ELEMJ;L-ELEMJ=T;L-ELEMJ=T;C语言程序设计与数据结构分析：分析：单链表单链表 VOID REVERSELIST(LINKLIST*L)VOID REVERSELIST(LINKLIST*L)LNODE*P,*Q;LNODE*P,*Q;P=L-NEXT;P=L-NEXT;L-NEXT=NULL;L-NEXT=NULL;WHILE(P)WHILE(P)Q=P-NEXT;Q=P-NEXT;P-NEXT=L-NEXT;P-NEXT=L-NEXT;L-NE

34、XT=P;L-NEXT=P;P=Q;P=Q;C语言程序设计与数据结构3 3、已已知知L1L1和和L2L2分分别别指指向向两两个个单单链链表表的的头头结结点点，且且已已知知其其长长度度分分别别为为M M和和N N，试试写写一一算算法法将将两两个个链链表表连连接在一起。接在一起。C语言程序设计与数据结构分析：分析：LINKLIST CONNECT(LINKLIST L1,LINKLIST L2,INT M,INT N)LINKLIST CONNECT(LINKLIST L1,LINKLIST L2,INT M,INT N)LISTNODE*P,*Q;LISTNODE*P,*Q;INT K;INT K;IF(MN)IF(MN)K=N;P=L2;Q=L1;K=N;P=L2;Q=L1;ELSE ELSE K=M;P=L2;Q=L2;K=M;P=L2;Q=L2;WHILE(K0)WHILE(K0)P=P-NEXT;K-;P=P-NEXT;K-;P-NEXT=Q-NEXT;P-NEXT=Q-NEXT;FREE(Q);FREE(Q);IF(MN)RETURN L2;IF(MN)RETURN L2;ELSE RETURN L1;ELSE RETURN L1;C语言程序设计与数据结构