数据结构线性表分析

第二章 线性表,线性表是一种线性数据结构一、线性表的定义 1. 特点： （1）相同类型的数据组成 （2）有穷序列 （3）只有一个初始点无前驱，称为表头（元素） （4）只有一个终端点无后继，称为表尾（元素） （5）相邻数据之间满足1：1的关系 2.举例 （1）一年12个月（1，2，3，12） （2）26个字母（a,b,c,z),3. 线性表的描述方式 例如：一年12个月 （1）（1，2，3，12） （2） （3）month=(M,R) M=5，4，6，9 R=r r=,12,结点/节点,表示有方向的关系,称为序偶，不能互换 （数据1，数据2）表示无方向的关系，称为无序偶，可以互换,也可以用二元组表示线性表的数据结构： linear_list =(A,R) A= ai | 1 i n, n o, ai ElemType R=r r= | 1 i n-1,一个线性表可以用一个标识符来命名，如A=(a1,a2, ,ai,ai+1, ,an),4. 说明： （1）线性表的长度：所含元素的个数 （2）允许线性表为空 在一个线性表中若存在着按值的升序或降序排列的字段，则称该字段为有序字段，该线性表为有序表，否则若不存在任何有序字段，则为无序表。,由一组数据结构和在该数据结构上的一组操作组成定义ADT的格式： ADT is Data: Operations: end ,二、抽象数据类型（ADT）,抽象数据类型线性表的定义如下：ADT LinearList is:Data: 一个具有ListType类型的线性表LOperation: void InitList(ListType L); /初始化为空 void CIearList(ListType L); /清除L中的所有元素 int ListSize (ListType /返回L中第pos个元素的值,线性表类型，是通用类型,元素类型，是通用类型,void TraverseList (ListType /对L中的所有元素重新按给定条件排序end LinearList,例2-1 L1=(25,38,19,42,33), i=2,x=60,y=42,对L1的一组操作结果: ListSize (L1); ListEmpty(L1); GetElem(L1, i); InsertList (L1, x,6); InsertList (L1,54,1); DeleteList (L1,y,0); Delete(L1, y,3); SortList (L1); InsertList (L1, 35,0);,2.1.3 操作举例,/38,/false,/5,/ (25,38,19,42,33,60),/(54,25,38,19,42,33,60),/ (54,25,38,19,33,60),/(54,25,19,33,60),/(19,25,33,54,60),/(19,25,33,35,54,60),例2 假定课程(course)记录的结构为: struct course char Cname20; /课程名称 int Chour; /开课学时 int Cterm; /开课学期 ,线性表L2,course x=“ “,72;course y=“程序设计基础”;course z=“英语”,80,1;course w=“数据结构”,72,4;GetList(L2, 3); /返回“英语”,72,1FindList (L2, x); /找学时为72的记录“离散数学”,72,2FindList (L2, y); /找课程为“程序设计基础”的记录UpdateList (L2,z); /修改“英语”记录为80学时InsertList (L2,w,6); /尾部插入一条记录wDeleteList (L2,y,0); /删除“程序设计基础”记录SortList (L2); /按开课学时升序排列,80,vjn,1. 顺序存储 线性表中各元素(数据)的逻辑地址与物理地址保持一致,并且要连续。,2.2 线性表的顺序存储和操作实现,l表示一个元素所占用的存储空间 sizeof (ElemType)整个线性表所占用的存储空间 n * sizeof (ElemType),LOC ( i ) = LOC ( i -1 ) + l =a + (i-1)*l,定义线性表的顺序存储类型 struct List ElemType list MaxSize; int size; ;,静态分配-编译阶段系统就知道该数组的大小，并分配好存储空间。,动态分配-定义线性表的存储类型时只定义了一个指针，并没有分配数组空间，程序运行中通过new运算操作得到空间，首地址赋给指针。,struct List ElemType* list; /存线性表元素的动态存储空间的指针 int size; /存线性表的长度 int MaxSize; /规定list数组的长度;,2. 顺序存储下的线性表操作的实现(1)初始化线性表,void InitList (List,(2)删除线性表中所有的元素,使之成为一个空表 void ClearList(List ,void ClearList(List ,3. 得到线性表的长度 int LenthList(List ,5. 得到线性表中指定序号为pos的元素 ElemType GetList(List,6. 遍历一个线性表 void TraverseList(List ,7. 查找给定值的第一个元素bool FindList(List ,/strcmp(L.listi,item)=0,8. 更新线性表中具有给定值的第一个元素 bool UpdateList(List ,/strcmp(L.listi,item)=0,9. 向线性表中按给定条件插入一个元素bool InsertList (List& L, ElemType item,int pos)(1)pos=0(2) pos=-1注意:(1)插入新元素前要检查动态数组空间是否具有空闲位置(2)为了在第pos各元素的位置插入新元素,要将从该位置开始的气候所有元素均后移一个位置(3)完成插入后,使线性表的长度增1,bool InsertList (List ,int i;if(pos=0) for(i=0;iL.size;i+) if(itemL.listi) break; pos=i+1;else if(pos=-1) pos=L.size+1;,(19,25, 33, 38, 60)35 (19,25, 33, 38, 60) (19,25, 33, 35, 38, 60),if(L.size=L.MaxSize) int k=sizeof(ElemType); L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k); if(L.list=NULL) cout“动态可分配的存储空间用完,退出运行!”=pos-1; i-) /留出插入的位置 L.listi + 1 = L.listi; /移动 L.listpos-1 =item; /插入 L.size+;/长度加1 return true;,时间复杂度？,10. 从线性表中删除符合给定条件的第1个元素bool DeleteList (List& L, ElemType& item,int pos)(1)pos=0(2) pos=-1注意:(1)删除元素前要检查线性表是否为空(2)得到待删除元素的值后,将其后元素从前向后依次前移一个位置 (3)完成删除后,使线性表的长度减1,bool DeleteList (List ,int i;if(pos=0) for(i=0; iL.size; i+) if(item=L.listi) break; /查找给定的元素 if (i =L.size) return false; pos=i+1;else if(pos=-1) pos=L.size;item=L.sizepos-1;,for(i=pos; inext=p-next;p-next=q;,在表头和表尾该如何插入？,(2)删除结点,p-next=q-next; delete q;,21,30,45,P,q,在表头和表尾该如何插入？,只用一个指针变量删除43结点,16,28,H,43,60,P,p-next=p-next-next;,/程序 2-2.cpp#include typedef int ElemType; /指定ElemType 为int struct LNode ElemType data; LNode * next;,从键盘上输入三个整型数，建立单链表，然后输出他们。,void main ( ) LNode x,y,z; /静态建立结点 Lnode* p=,由动态结点构造单链表的方法,尾插法 L(7,16,20,28,32),（插入16） （插入20）,7,H,16,p,q,p-next=q;p=p-next;,p,7,H,20,p,q,16,头插法 L(7,16,20,28,32),(插入16) (插入20),7,H,16,p,H,p-next=H;H=p;,16,H,20,p,7,#include struct LNode ElemType data; LNode * next;Typedef int ElemType; void main ( ) int n,i; LNode *p,*q,*H; H=p=new Lnode; /动态建立结点 cin n;,从键盘上送n个整型数，建立单链表，然后输出他们。,cinp-data;for( i=1; i q-data; p-next=q; p=q; p-next= NULL;,p=H; /p是第一个元素结点，H是头结点 while (p!=NULL) coutdatanext; coutp-data; p-next=NULL; cin n; for( i=1; i p-data; p-next=H; H=p; ,1.在下面链表中按顺序插入结点q，写出核心程序段,16,28,H,43,60 ,52,q,设计算法,使用两个指针 if(H-data q-data) q-next=H;H=q; P1=P2=H; while(q-data p2-data ,只用一个指针（没有考虑表头和表尾结点） p=H; while(q-next p-next-data) p=p-next; q-next=p-next; p-next=q;,使用一个指针，插入后交换（没有考虑表尾结点） p=H; while(q-data p-data) p=p-next; q-next=p-next; p-next=q; int temp; temp=p-data; p-data=q-data; q-data=temp;,2.将单链表中所有重复的结点删除，只保留第一个,P=H; while(p!=NULL) q=p;t=p-next; while(t!=NULL) if(t-data=p-data) q-next=t-next; delete t; t=q-next; else q=q-next;t=t-next; p=p-next;,struct ALNode ElemType data; int next; ;typedef ALNode ALinkListMaxSize;数组类型为ALinkList，包含MaxSize个元素，元素类型为ALNode。下标为0的元素的指针域保存非空单元组成链表的首结点的下标；下标为1的元素的指针域保存空闲单元组成链表的首结点的下标；,单链表的顺序存储,初始状态,struct DNode ElemType data; DNode * left; DNode * right;,struct ADNode ElemType data; int left; int right;,数组中的元素结点：,5.双向链表中的结点类型和插入与删除操作,q-right = p-right; -(1) p-right-left = q; -(2)q-left = p;-(3) p-right = q; -(4),双向链表的插入操作,a,b,c,p,q,2,1,3,4,b,a,c,p,p-left-right = p-right;p-right-left = p-left;delete p;,双向链表的删除操作,6. 带表头附加结点的线性链表,表头附加结点位于表的最前端，本身不带数据，指针域指向表头结点。表头指针指向表头附加结点。,非空表 空表,an,a1,H,H,设计算法,1.删除带表头附加结点的单链表中data值与给定item值相等的所有结点 p=H;q=H-next; while(q!=NULL) if(q-data=item) p-next=q-next; delete q; q=p-next; else p=p-next; q=q-next; ,2.逆置一个单链表，即原单链表中存储元素次序为a1,a2,.an,则逆序为an, . a2, a1。,a1,a2,a4,H,a3,(a1,a2,a3,a4) - (a4,a3,a2,a1),H,算法1：void Contrary(LNode* ,带表头附加结点的单链表的算法：void Contrary(LNode* ,7.循环链表,循环链表最后一个结点的指针域不为NULL，而是指向了表的最前端。循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。,2.5 线性表操作在单链表上的实现,假定表头指针HL，结点类型为LNode，无表头附加结点。1.初始化单链表 void InitList(LNode* ,an,a1,HL,2.删除单链表中的所有结点，使之成为一个空表 void ClearList(LNode* ,3. 得到单链表的长度 int LenthList(LNode* HL) int i=0; while (HL!=NULL) i+; HL=HL-next; return i; ,4. 检查单链表是否为空 bool EmptyList (LNode* HL) return HL=NULL; 5.得到单链表中第pos个结点中的元素 ElemType GetList(LNode* HL, int pos) if (pos1) cerr“pos is out ramge!”next; if (HL!=NULL) return HL-data;else cerr“pos is out range!”endl; exit(1); ,6. 遍历一个单链表 void TraverseList(LNode* HL) while (HL!=NULL) coutdatanext; coutnext; ,else if(pos=-1) while(cp!=NULL) ap=cp; cp=cp-next; ,else int i=0; while(cp!=NULL) i+; if(i=pos) break; else ap=cp; cp=cp-next; if(cp=NULL ,if(ap=NULL) newptr-next =HL; HL=newptr; ,else newptr-next=cp; /其他位置 ap-next=newptr; return true;,10. 从单链表中删除符合给定条件的第1个元素bool DeleteList (LNode* /ahead,if(pos=0) while (cp!=NULL) if (item =cp-data) break; /找到被删除元素 else ap=cp; cp=cp-next; if(cp=NULL) cout“ 单链表中没有相应的结点可删除!”next!=NULL) ap=cp;cp=cp-next; ,else int i=0; while(cp!=NULL) i+; if(i=pos) break; else ap=cp; cp=cp-next; if(cp=NULL) cout“pos值无效！”next;/第一个else ap-next=cp- next; /其他delete cp; return true; ,1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 2.线性表的顺序存储结构中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （A）110 （B）108 （C）100 （D）1203.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素（A）8 （B）63.5 （C）63 （D）7,C,B,B,4.链接存储的存储结构所占存储空间：（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针（B）只有一部分，存放结点值（C）只有一部分，存储表示结点间关系的指针（D）分两部分，一部分存放结点值，另一部分存放结点所占单元数5 线性表在 情况下适用于使用链式结构实现。（）需经常修改中的结点值 （）需不断对进行删除插入 （）中含有大量的结点 （）中结点结构复杂,A,B,6.下述哪一条是顺序存储结构的优点？（ ）A 存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示7若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表,A,A,8.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表9.下面的叙述不正确的是（ ）A线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值