数据结构数据结构第二章第二章 线性表线性表第1页数据结构第二章目目 录录2.1 线性表的逻辑结构线性表的逻辑结构2.2 线性表的顺序存储结构线性表的顺序存储结构2.3 线性表的链式存储结构线性表的链式存储结构2.4 顺序表与链表的比较顺序表与链表的比较2.5 案例实现案例实现通讯录管理通讯录管理2.0 案例导引案例导引知识目标：知识目标：理解线性表的逻辑结构特征掌握顺序表的含义、特点、基本运算和相关算法分析掌握链表的含义、特点、基本运算和相关算法分析理解循环链表、双链表的逻辑结构特征及基本运算理解顺序表和链表的比较技能目标：技能目标：能应用顺序表的理论设计算法，解决实际问题能应用链表的理论设计算法，解决实际问题第2页数据结构第二章2.0 2.0 案例导引案例导引案例：案例：通讯录管理 编写一个用于通讯录管理的程序，实现对联系人信息的插入、删除、查找等功能要求记录每位联系人的姓名、性别、号码、住宅号码和邮箱信息案例探析：案例探析： 对于通讯录中的联系人需要管理其姓名、性别、、邮箱等信息，每位联系人所需要存储的信息类型是相同的，也就是说各个结点应该具有相同的结构同时，各位联系人的信息记录之间按顺序排列，形成了线性结构。
线性结构是最简单最常用的数据结构第3页数据结构第二章数据结构第二章第4 页2.1 2.1 线性表的逻辑结构线性表的逻辑结构2.1.1 2.1.1 线性表的定义线性表的定义 线性表（Linear List）：是由n个性质相同的数据元素组成的有限序列表中数据元素的个数n定义为线性表的长度n=0的表称为空表，即该线性表不包含任何数据元素n0时，线性表记为： L=(a1,a2,a3,an) 其中ai (1in)称为表中的第i个数据元素，下标i表示该元素性表中的位置任意一对相邻的数据元素ai-1， ai (2in)存在着序偶关系（ai-1，ai)，且ai-1称为ai的直接前驱，ai称为ai-1的直接后继数据结构第二章第 5页线性表的逻辑结构为：线性表的逻辑结构为：l存在唯一的数据元素a1，或称首结点，它没有直接前驱，只有一个直接后继； l存在唯一的数据元素an，或称尾结点，它没有直接后继，只有一个直接前驱； l除第一个结点（首结点）之外，集合中的每个数据元素均只有一个直接前驱； l除最后一个结点（尾结点）之外，集合中每个数据元素均只有一个直接后继 线性表中的数据元素之间是一对一的关系，数据元素可以是简单数据类型，如整型、字符型等，也可以是用户自定义的任何类型如记录类型等。
数据结构第二章第6 页 线性表是一种典型的线性结构，用二元组表示为：S=(A,R)A=a1,a2, , ai,an R=, 线性表的逻辑结构如图2-1所示： 图2-1 线性表的逻辑结构图数据结构第二章第7 页 在日常生活中有许多线性表的例子，比如一副扑克牌的点数可以表示为（2,3,4,5,6,7,8,9,10,J,Q,K,A）；再如图书目录、银行排队叫号等都是线性表的例子 学生信息表就是一例典型的线性结构，如表2-1表2-1 学生信息表学号学号姓名姓名性别性别号码号码邮箱邮箱10001李平男10002王芳女10003吴冰女10004李清男数据结构第二章第 8页2.1.2 2.1.2 线性表的抽象数据类型定义线性表的抽象数据类型定义 线性表的长度可以随着数据元素的插入、删除等操作而增加或减少，它是一种灵活的数据结构线性表的抽象数据类型定义如下：ADT List 数据对象：数据对象：D=ai|ai为DataType类型，1in，n0 /*DataType为自定义类型*/ 数据关系：数据关系：R=|ai-1, aiD, 2in 在非空表中，除了首结点，每个结点都有且只有一个前驱结点；除了尾结点，每个结点都有且只有一个后继结点。
基本操作：基本操作： InitList(&L)：构造一个空的线性表L，即表的初始化 ListLength(L)：求线性表L中的结点个数，即求表长 GetNode(L,i)：取线性表L中的第i个结点，要求1iListLength(L) 数据结构第二章第9 页LocateNode(L,x)：在L中查找值为x的结点，并返回该结 点在L中的位置若L中有多个结点的值和x相同，则返回首次找到的结点位置；若L中没有结点的值为x，则返回一个特殊值表示查找失败 InsertList(&L,x,i)：性表L的第i个位置上插入一个值为x的新结点，使得原编号为i，i+1，n的结点变为编号为i+1，i+2，n+1的结点这里1in+1，n是原表L的长度插入操作成功后表L的长度加1 DeleteList(&L,i)：删除线性表L的第i个结点，使得原编号为i+1，i+2，n的结点变成编号为i，i+1，n-1的结点这里1in，n是原表L的长度删除操作成功后表L的长度减1ADT List数据结构第二章第 10页2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构2.2.12.2.1顺序表的结构顺序表的结构 线性表的顺序存储结构又称顺序表（Sequential list）。
顺序表是用一组地址连续的存储单元依次存放线性表的数据元素，即保持元素同构且无缺项 若每个数据元素占用c个存储单元，并以所占的第一个存储单元地址作为这个数据元素的存储位置，设表的最大长度为MaxSize，如图2-2，则表中任一元素ai的存储地址为： LOC(ai)=LOC(a1)+(i-1)*c（1in） 顺序表中为相邻的元素ai和ai+1赋予相邻的存储位置LOC(ai)和LOC(ai+1)，即性表中逻辑关系相邻的数据元素在内存中的物理位置也是相邻的对于这种存储方式，只要确定表头结点的首地址，线性表中任一数据元素都可以随机存取，所以顺序表是一种随机的存储结构数据结构第二章第 11页图2-2 顺序表逻辑结构图数据结构第二章第12 页2.2.2 2.2.2 顺序表上实现的基本运算顺序表上实现的基本运算 在C语言中，可以采用结构体类型来定义顺序表类型，如下：/*顺序表的定义：*/#define MaxSize 80 /*表空间大小应根据实际需要设定，这里假设为80 */typedef int DataType; /* DataType为数据元素的类型，可以是任何类型*/typedef struct DataType dataMaxSize; /* data用于存放表结点 */ int length; /* 当前的表长度 */SeqList; 顺序表的存储结构如图2-3。
图2-3 顺序表存储结构图数据结构第二章第13 页1.建表 输入给定的数组元素作为线性表的数据元素，将其传入顺序表中，将传入的元素个数作为顺序表的长度建立顺序表算法2-1】：void CreateList(SeqList *L,DataType a,int n) /* 建立顺序表 */ int i; if(nMaxSize) printf(overflow); /* 如果n大于MaxSize，出现上溢 */ exit(0); for(i=0;idatai=ai; L-length=n; /* 设置表中元素个数 */ 该算法的问题规模是表的长度n，基本语句是for循环中执行元素赋值的语句，故时间复杂度为O(n)数据结构第二章第14 页 在日常工作中，根据实际情况可以设计多种建表方式，比如通过键盘输入数据或通过文件读取数据等等下面为读者提供从键盘输入数据建立顺序表的算法：【算法2-2】：void CreateListB(SeqList *L) /*从键盘输入数据，建立顺序表*/ int i,value; i=0; printf(“请输入数据，输入9999时结束：n”); scanf(“value=%d”,&value);数据结构第二章第15 页 while(value!=9999) if(iMaxSize-1) printf(overflow); /*如果i大于MaxSize-1，出现上溢 */ exit(0); L-datai=value; /*为线性表的元素赋值 */ i+; scanf(“value=%d”,&value); L-length=i; /*设置表中元素个数 */数据结构第二章第16 页2.插入 线性表的插入运算是指性表的第i个(1in+1)位置上，插入一个新元素x，使长度为n的线性表（a1,a2, , ai,an）变成长度为n+1的线性表（a1,a2, , ai-1, x, ai,an）。
顺序表中要保持元素同构且无缺项因此在表中进行插入运算时，必须将表尾结点至待插入位置的结点依次后移，空出第i个位置，如图2-4 (b)图（由内存的特性知，此时该物理单元的内容仍为ai，记为（ai），然后将新元素插入该位置，完成插入运算仅当在原表尾结点后插入新结点时，即插入位置为i=n+1时，无需移动结点 在C语言中，数组下标从0开始依次存放数据元素，其完整插入过程如图2-4数据结构第二章第17 页图2-4 顺序表插入运算示意图数据结构第二章第18 页【算法2-3】：void InsertList(SeqList *L,DataType x,int i)/*将新结点x插入L所指的顺序表的第i个结点的位置上*/ int j; if (L-length=MaxSize) /*表空间已满，不能插入元素，退出运行 */ printf(表空间已满，不能插入元素，退出运行); exit(0); if (iL-length+1) /*插入位置错误，退出运行 */ printf(插入位置非法); exit(0); for (j=L-length-1;j=i-1;j-) /*从表尾结点至第i个结点依次后移 */ L-dataj+1=L-dataj; L-datai-1=x; /*新元素赋值 */ L-length+; /*表长加1 */数据结构第二章第 19页 该算法的问题规模是表的长度n，基本语句是for循环中执行元素后移的语句。
当i=1时，即新插入的元素为表头结点，需要移动表中所有的元素，元素后移语句将执行n次，这是最坏的情况，时间复杂度为O(n)；当i=n+1时，即新插入的结点为表尾结点，元素不需要执行后移，这是最好的情况，时间复杂度为O(1)表长为n的线性表中，在第i个位置插入一个新元素，元素后移语句的执行次数为n-i+1假设i是一个随机值，即在多次插入运算中取值分布是均匀的，则概率 为 ，需要移动的元素平均次数为 也就是说，在顺序表上实现插入操作，等概率情况下，平均要移动表中一半的数据元素，算法的平均时间复杂度为O(n)数据结构第二章第 20页3.删除 线性表的删除运算是指将线性表的第i个(1in)位置上的元素删除，使长度为n的线性表（a1,a2, , ai,an）变成长度为n-1的线性表（a1,a2, , ai-1, ai+1,an） 顺序表中应保持元素同构且无缺项在表中进行删除运算时，将待删除结点之后的结点至表尾结点依次前移，顺次覆盖前一个位置的元素，实现删除第i个元素的操作仅当删除原表尾结点时，即删除位置为i=n时，无需移动结点其删除过程如图2-5数据结构第二章第 21页图2-5 顺序表删除运算示意图数据结构第二章第 22页【算法2-4】：void DeleteList(SeqList *L,int i) /*从L所指的顺序表中删除第i个结点*/ int j; if (L-length=0) printf(线性表为空，退出运行n); exit(0); if (iL-length) printf(删除位置非法n); exit(0); for (j=i;jlength-1;j+) L-dataj-1=L-dataj; /*将自第i个元素之后的所有元素向前移动*/ L-length-; /*表长减1*/数据结构第二章第 23页 该算法的问题规模是表长n，基本语句为for循环中元素前移的语句。
当i=1时，即删除表头结点，。