1、本章主要介绍线性表的定义、运算和线性表的几种存储结构等内容 重点重点：线性表的定义、线性表的基本操作，线性表的存储结构难点：难点：线性表的基本操作，线性表的存储结构教学目标 线性表是最简单常用的数据结构，顺序存储结构 链式存储结构也是应用中最常用的存储方法，这一部分内容和方法掌握了，有助于理解和掌握后续章节的内容，如栈队列串是特殊的线性表，数组和广义表是线性表的扩展；有助于理解和掌握树和图等复杂的数据结构 存储结构和图等复杂结构的操作算法，因为树和图的存储结构大多或是这两种存储结构的扩充，或是它们的组合，因此这一章的内容非常重要，同学们要很好地学习理解和掌握。第二章 线性表 第二章第二章 线性
2、表线性表2.1 线性表概念及基本操作2.2 线性表的顺序存储和实现2.3 线性表的链式存储和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表2.4 一元多项式的表示及相加第二章 线性表 在本课程介绍的几种数据结构中，线性表是最常简单的，也是最常用的数据结构，线性表在实际应用大量使用，并不是一个陌生的概念。线性表是线性表是n 个类型相同数据元素的有限序列，个类型相同数据元素的有限序列，通常记作（通常记作（a1,a2,a3,an）。）。姓名 电话号码 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555 .
3、2.1 线性表的概念例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,E Z）。例3、某单位的电话号码簿。一一 线性表的逻辑结构线性表的逻辑结构 2.1 线性表的概念说明：设说明：设 A=（a1,a2,.,ai-1,ai,ai+1,an）是一线性表是一线性表1）线性表的数据元素可以是各种各样的，但同一线性表中的元线性表的数据元素可以是各种各样的，但同一线性表中的元素必须素必须是同一类型的；是同一类型的；2）在表中在表中 ai-1 领先于领先于ai，ai 领先于领先于ai+1，称称ai-1 是是ai 的直接前驱，的直接前驱，ai+1 是是ai 的直接后继；
4、的直接后继；3）在线性表中，除第一个元素和最后一个元素之外，其他元素在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；构特征的数据结构称为线性结构。线性表是一种线性数据结构；4）线性表中元素的个数线性表中元素的个数n 称为线性表的长度，称为线性表的长度，n=0 时称为空表；时称为空表；5）ai是线性表的第是线性表的第i 个元素，称个元素，称i 为数据元素为数据元素ai 的序号，每一个的序号，每一个元素在线性表中的位置，仅取决于
5、它的序号；元素在线性表中的位置，仅取决于它的序号；2.1 线性表的概念 线性表的其他表示方式 二元组表示 L=，其中D=a1,a2,a3,.an S=R R=,图示表示a ai i+1a a1a ai-i-1a a2 2a ai ia an n顶点：表示数据边：表示是数据间的顺序结构关系2.1 线性表的概念2线性表的基本操作线性表的基本操作1 存取操作：存取线性表中第存取操作：存取线性表中第i 个数据元素个数据元素；2 查找操作查找操作：在线性表中查找满足条件元素；：在线性表中查找满足条件元素；3 插入操作插入操作：在线性表的第：在线性表的第i个元素之前插入个元素之前插入 一个新元素一个新元素
6、;4 删除操作删除操作：删除线性表的第：删除线性表的第i个元素；个元素；5 分解操作分解操作：将一个线性表拆分为多个线性表：将一个线性表拆分为多个线性表；6 合并操作合并操作:7 排序排序 2.1 线性表的概念说明1 上面列出的操作，只是线性表的一些常用的基本操作；2 不同的应用，基本操作可能是不同的；3 线性表的复杂操作可通过基本操作实现；为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；2）线性表中数据元素的顺序关系；如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？2.2 2.2 线性表的线性表的顺序存储顺序存储和实现和实现 一 线性表的顺序存储结构顺序表 二 顺序
7、表的基本操作算法 三 效率分析 线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an n 线性表（a1,a2,a3,.an）的顺序存储结构用顺序存储结构存储的线性表称为顺序表 2.2 线性表的顺序存储和实现一一 线性表的顺序存储结构线性表的顺序存储结构顺序顺序表表 线性表的顺序存储结构2.2 线性表的顺序存储和实现说明：说明：在顺序存储结构下，线性表元素在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺之间的逻辑关系，通过元素的存储顺序反映（表示）出来；序反映（表示）出来；假设线性表中
8、每个数据元素占用假设线性表中每个数据元素占用 t 个存储单元，那么，在顺序存储结构个存储单元，那么，在顺序存储结构中，线性表的第中，线性表的第i个元素的存储位置与个元素的存储位置与第第1个元素的存储位置的关系是：个元素的存储位置的关系是：Loc(ai)=Loc(a1)+(i 1)ta a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an nt t个单元个单元Loc(a1)Loc(ai)2.2 线性表的顺序存储和实现怎样在计算机上实现线性表的顺序存储结构？可用C语言中的一维数组来表示,但数组不是线性表,数组存放的是线性表,数组的类型由线性表中的数据元素的性质决定.如:#d
9、efine MAX 100 int vMAX;2.2 线性表的顺序存储和实现顺序表的类型定义顺序表的类型定义#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配线性表存储空间的初始分配量量#define LISTINCREMENT 10 /线性表存储空间的分配增量线性表存储空间的分配增量typedef structElemType *elem;/线性表存储空间基址线性表存储空间基址int length;/当前线性表长度当前线性表长度int listsize;/当前分配的线性表存储空间大小当前分配的线性表存储空间大小 /（以（以sizeof(ElemType)为单位）
10、为单位）SqList;SqList：类型名，SqList类型的变量是结构变量，它的三个域分别是：*elem：存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配；length：存放线性表的表长；listsize：用于存放当前分配（存放线性表元素）的存储空间的大小。2.2 线性表的顺序存储和实现存放线性表元素 的一维数组设设 A=（a1,a2,a3,.an）是一线性表，是一线性表，L是是SqList 类型的结构类型的结构变量，用于存放线性表变量，用于存放线性表A，则则L在内存中的状态如图所示：在内存中的状态如图所示：顺序表通过顺序表通过元素的存储顺序元素的存储顺序反映线性表元
11、素间的逻辑关系反映线性表元素间的逻辑关系 a1a1 a2 a2ai-1ai-1 aiaiai+1ai+1 an an0 01 1i-2i-2i-1i-1i in-1n-19999L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsizen n99992.2 线性表的顺序存储和实现二、顺序表的基本操作算法1.插入 insert(v,x,i)功能：在顺序表v 中的第 i(1=i=n+1)个数据元素之前插入一个新元素x,插入前线性表为 (a1,a2,a3,ai-1,ai,an)插入后,线性表长度为n+1,线性表为 (a1,a2,a3,ai-1,x,ai,an)2
12、.2 线性表的顺序存储和实现插入前插入后插入操作示意图：插入操作示意图：a1a1 a2 a2ai-1ai-1 aiaiai+1ai+1 an an01i-2i-1in-1MAX-1n nP_lenP_len a1a1 a2 a2 ai-1 ai-1 x x aiai an an01i-2i-1n-2n-1nMAX-1n+1n+1P_lenP_len2.2 线性表的顺序存储和实现int insert(int v ,int i,int x,int*p_len)int j;if(i*p_len)return(0);/*i 值不值不合法合法 for(j=*p_len,j=i;j-)vj=v j-1;v
13、i-1=x;*p_len+;/*插入插入x,表长增表长增1 return(1);插入操作算法插入操作算法删除算法的主要步骤删除算法的主要步骤1）若）若i 不合法或表不合法或表L空，算法结束，并返回空，算法结束，并返回 0；否则转否则转2）2）将第将第i个元素之后的元素（不包括第个元素之后的元素（不包括第i个元素）依次向前移动个元素）依次向前移动一个位置一个位置;3）表长）表长-1 2.2 线性表的顺序存储和实现2.2 线性表的顺序存储和实现int delete(int v ,int i,int*p_len)int j;if(i*p_len)return(0);/*i 值不值不合法合法 for(
14、j=i,jnext=null;Return(head);1）初始化操作 功能：建空线性链表参数：head 为线性链表的头指针主要步骤：调用malloc()分配一结点的空间,并将其地址赋值给head；建立链表 NODE*create_next(n)/*建立有n个结点的线性单链表的算法 NODE*head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE);head=p;for(i=I;Idata=i;q-next=NULL;p-next=q;p=q;return(head);插入结点 q=(NODE*)malloc(sizeof(NODE);q-deta=a;q-n
15、ext=p-next;p-next=q;heahead dzyxp pyxzp pheahead da13 插入操作 Insert_next(NODE*head,int x,int i)功能：在线性链表的第i个元素结点之前插入一个新元素结点x；插入操作图示：2.3.1 线性链表插入前插入后 ai-1aia2a1ai+1nanheahead dai-1aia2a1ai+1nanxheahead d2.3.1 线性链表插入操作主要步骤：1）查找链表L的第 i-1个元素结点；2）为新元素建立结点；3）修改第 i-1个元素结点的指针和新元素结点指针完成插入；Int insert_next(NODE*h
16、ead,int x,int i)NODE*p,*s;int j;p=head;j=0;while(p!=NULL)&(jnext;j+;if(p=NULL)return(0);s=(NODE*(malloc(sizcof(NODE);s-data=x;s-next=p-next;p-next=s;return(1);删除结点 q=p-next;p-next=q-next;free(q);heahead dzyxq qyxzq qheahead dp pp p2.3.1 线性链表删除操作主要步骤：1）查找链表的第 i-1个元素结点,使指针p指向它,将指针q指向第i个结点；2）修改第 i-1个元素
17、结点指针，使其指向第i个元素结点的后继；3)回收q指针所指的第i个结点空间；2.3.1 线性链表删除前删除后ai-1aia2a1ai+1nanheadheadai-1aia2a1ai+1nanheadp pp pq qq q 在线性链表中删除第i个结点 Int delete_next(NODE*head,int i)NODE*p,*q;int j;p=head;j=0;while(p!=NULL)&(jnext;j+;if(p=NULL)return(0);q=p-next;p-next=q-next;free(q);return(1);2.3.1 线性链表 三三 线性链表的其他操作的实现线性
18、链表的其他操作的实现例：将两个递增有序线性链表归并成一个递减有序例：将两个递增有序线性链表归并成一个递减有序表。表。设线性表设线性表A、B分别用头指针为分别用头指针为head_a、head_b 的的两个带头结点的线性链表存储两个带头结点的线性链表存储,归并后的递减有序表归并后的递减有序表头指针为头指针为head,将两表数据较小的结点依次取出插入将两表数据较小的结点依次取出插入到新表到新表利用基本操作直接对链表进行操作2.3.1 线性链表线性链表归并操作图示73n952n7head_ahead_b79n2head38785NODE*merge_next(NODE*head_a,NODE*head
19、_b)NODE*p,*q,*head;head=(NODE*)malloc(sizeof(NODE);head-next=NULL;p=head_a-next;q=head_b-next;while(p!=NULL)&(q!=NULL)If(p-datadata)head_a-next=p-next;p-next=head-next;head-next=p;p=head_a-next;else head_b-next=q-next;q-next=head-next;head-next=q;q=head_b-next;while(p!=NULL)head_a-next=p-next;p-next
20、=head-next;head-next=p;p=head_a-next;while(q!=NULL)head_b-next=q-next;q-next=head-next;head-next=q;q=head_b-next;free(head_a);free(head_b);return(head);2.3.1 线性链表小结线性链表是线性表的一种链式存储结构 线性链表的特点 1 通过保存直接后继元素的存储位置来表示 数据元素之间的逻辑关系；2 插入删除操作通过修改结点的指针实现；3 不能随机存取元素；1 循环链表的概念循环链表的概念 循环链表是线性表的另一种链式存储结构，它的特循环链表是线性
21、表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一点是将线性链表的最后一个结点的指针指向链表的第一个结点个结点2 循环链表图示循环链表图示2.4 单向循环链表(a)非空表 （b）空表headheadheadheada1an2.4 单向 循环链表说明 在解决某些实际问题时循环链表可能要比线性链表方便些。在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；如将一个链表链在另一个链表的后面；循环链表与线性链表操作的主要差别是算法中循环结束的循环链表与线性链表操作的主要差别是算法中循环结束的条件不是条件不是p或或p-next是否为是否为NU
22、LL,而是它们是否等于首指而是它们是否等于首指针；针；对循环链表，有时不给出头指针，而是给出尾指针对循环链表，有时不给出头指针，而是给出尾指针a aa1an给出尾指针的循环链表2.4 单向 循环链表b ba aa1anb bb1bna aa1anb1bnq qq qp pp pp=a-next;q=b-next;a-next=q-next;b-next=p;free(q);1 双向链表的概念双向链表的概念 2.5 双向链表(a)a)结点图示结点图示数据域指针域指针域结点结点存储数据元素存储数据元素存储后继结点存储后继结点 的地址的地址存储前趋结点存储前趋结点 的地址的地址 双向链表中，每个结点
23、有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。2.5 双向链表2 双向链表图示双向链表图示headhead(b)空的双向循环链表（c）非空的双向循环链表headheadabStruct node int data struct node*lnext,*rnext;在双向链表中删除结点时指针在双向链表中删除结点时指针变化情况变化情况在双向链表中插入一在双向链表中插入一个结点时指针的变化个结点时指针的变化情况情况pai-1xaipaiai+1ai-12.5 双向链表3、双向链表的基本操作算法2.5 双向链表1）插入操作算法）插入操作算法 (在在p 所指结点之后插入所指结点之后
24、插入q 结点的过程结点的过程)q=(NODE*)malloc(sizeof(NODE);q-data=x;q-rnext=p-rnext;q-lnext=p;p-rnext=q;(q-rnext)-lnext=q;2.5 双向链表2）删除操作算法）删除操作算法(p-lnext)-rnext=p-rnext;(p-rnext)-lnext=p-lnext;free(p);aiai+1pai-1 第二章 线性表小结 本章学习了线性表的顺序存储结构本章学习了线性表的顺序存储结构顺序表，链式存储结构顺序表，链式存储结构,线性链表线性链表,循环链表循环链表,双向链表，以及在这两种存储结构下如何实现线双向
25、链表，以及在这两种存储结构下如何实现线性表的基本操作。这里再一次需要强调：本课程不仅要从概念和方性表的基本操作。这里再一次需要强调：本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储线性表，如何在计习如何在计算机上实现，即如何在计算机上存储线性表，如何在计算机上实现线性表的操作。我们已经看到，在不同的存储结构下，算机上实现线性表的操作。我们已经看到，在不同的存储结构下，线性表的同一操作的算法是不同的，在顺序表存储结构下，线性表线性表的同一操作的算法是不同的，在顺序表
26、存储结构下，线性表的插入删除操作，通过移动元素实现，在线性链表存储结构下，线的插入删除操作，通过移动元素实现，在线性链表存储结构下，线性表的插入删除操作，通过修改指针实现。对于某一实际问题，如性表的插入删除操作，通过修改指针实现。对于某一实际问题，如何选择合适的存储结构，如何在某种存储结构下实现对数据对象的何选择合适的存储结构，如何在某种存储结构下实现对数据对象的操作，我们要通过数据结构课程的学习，很好地理解各种存储结构操作，我们要通过数据结构课程的学习，很好地理解各种存储结构是如何存储和表达数据对象的有关信息的，各种存储结构下操作的是如何存储和表达数据对象的有关信息的，各种存储结构下操作的特
27、点。为实际问题的程序设计打下坚实的基础。特点。为实际问题的程序设计打下坚实的基础。上机实验题 上机验证第一、二章的算法例子和习题#define NULL 0 struct node int data;struct node*next;typedef struct node NODE;NODE*create_next(n)NODE*head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE);head=p;for(i=1;idata=i;q-next=NULL;p-next=q;p=q;return(head);上机实例 int insert_next(NODE*head,int x,int i)NODE*p,*s;int j;p=head;j=0;while(p!=NULL)&(jnext;j+;if(p=NULL)return(0);s=(NODE*)malloc(sizeof(NODE);s-data=x;s-next=p-next;p-next=s;return(1);上机实例上机实例 main()int j;NODE*t;t=create_next(10);for(j=1;jnext;printf(%3d,t-data);insert_next(t,99,6);for(j=1;jnext;printf(%3d,t-data);
