数据结构第2章线性表.ppt

数据结构数据结构讲义讲义第二章第二章 线性表线性表目录：n2.1 线性表的类型定义线性表的类型定义n2.2 线性表的顺序表示和实现线性表的顺序表示和实现n2.3 线性表的链式表示和实现线性表的链式表示和实现n2.4 线性表实现方法的比较线性表实现方法的比较n2.5 循环链表循环链表n2.6 双链表双链表n2.7 静态链表静态链表2.1 线性表的类型定义线性表的类型定义n1、线性表的概念、线性表的概念n2、线性表的抽象数据类型、线性表的抽象数据类型n3、线性表的例子、线性表的例子1、线性表的概念、线性表的概念n线性表(Linear List) ：由n(n≧1)个数据元素(结点)a1，a2， …an组成的有限序列其中数据元素的个数n定义为表的长度当n=0时称为空表，常常将非空的线性表(n>0)记作： (a1，a2，…an) 线性表的表示线性表的表示n这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同n符号表示法：符号表示法：L＝（e1,e2,…en）n图形表示法：图形表示法：线性表的逻辑特征线性表的逻辑特征 n在非空的线性表，有且仅有一个开始结点在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继，它没有直接前趋，而仅有一个直接后继a2；；n有且仅有一个终端结点有且仅有一个终端结点an，它没有直接后，它没有直接后继，而仅有一个直接前趋继，而仅有一个直接前趋an-1；；n其余的内部结点其余的内部结点ai(2≦ ≦i≦ ≦n-1)都有且仅有一都有且仅有一个直接前趋个直接前趋ai-1和一个直接后继和一个直接后继ai+1。

线性表的逻辑特征线性表的逻辑特征线性表是一种最简单的线性结构线性表是一种最简单的线性结构.线性结构的基本特征为:是一个数据元素的有序（次序）集1．集合中必存在唯一的一个“第一元素第一元素”；；2．集合中必存在唯一的一个 “最后元素最后元素” ；3．除最后元素在外，均有 唯一的后继唯一的后继；4．除第一元素之外，均有 唯一的前驱唯一的前驱2、线性表的抽象数据类型、线性表的抽象数据类型数据结构的操作是定义在逻辑结构层次上的，而操作的具体实现是建立在存储结构上的，因此，线性表的基本操作作为逻辑结构的一部份定义在抽象数据类型中，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成线性表的主要操作有插入、删除、检索等抽象数据类型描述抽象数据类型描述ADT List{ 数据对象：D={ai | ai ∈ElemSet，i=1,2,3,…,n n≥0} 数据关系：R={|ai-1,ai ∈D, i=2,3,…,n} 基本操作：}基本操作基本操作n线性表初始化线性表初始化 ListInit(L)n线性表的长度线性表的长度 ListLength(L)n取表元素取表元素ListGet(L，，i)n按值查找按值查找 ListLocate(L，，x)n线性表清空线性表清空 ListClear(L)n线性表判空线性表判空 ListEmpty(L)n求前驱求前驱 ListPrior(L，，x)n求后驱求后驱 ListNext(L，，x)n插入插入 ListInsert(L，， i，，x)n删除删除 ListDelete(L，，i)3、线性表的例子、线性表的例子n例1、26个英文字母组成的字母表 （A，B，C、…、Z）n例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。

（6，17，28，50，92，188）n例3、一副扑克的点数（2，3，4，…，J，Q，K，A）3、线性表的例子、线性表的例子姓 名学 号性 别年龄健康情况王小林790631男18健康陈 红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….线性表示例线性表示例 例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B void union(List &La，List Lb) { La_len=listlength(La); Lb_len=listlength(Lb); for(i=1;i<=lb_len;i++) { getelem(lb，i，e); if(!locateelem(la，e，equal)) listinsert(la，++la_len，e); } } 线性表示例线性表示例 n例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。

n 此问题的算法如下：void mergelist(list la，list lb，list &lc) { initlist(lc); i=j=1;k=0; la_len=listlength(la); lb_len=listlength(lb);线性表示例线性表示例while((i<=la_len)&&(j<=lb_len)) { getelem(la，i，ai); getelem(lb，j，bj); if(ai<=bj) { listinsert(lc，++k，ai); ++i ; } else { listinsert(lc，++k，bj) ; ++j; } } while(i<=la_len) { getelem((la，i++，ai); listinsert(lc，++k，ai); }while(j<=lb_len) { getelem((lb，j++，bj); listinsert(lc，++k，bi); } }2.2 线性表的顺序表示和实现线性表的顺序表示和实现1、线性表的顺序表示2、线性表操作的实现1、线性表的顺序表示、线性表的顺序表示线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。

因为内存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单，又自然的1、线性表的顺序表示、线性表的顺序表示如图 2.1 所示设 a１１的存储地址为Loc(a1)，每个数据元素占d个存储地址，则第i个数据元素的地址为： Loc(ai)=Loc(a1)+(i-1)*d 1<=i<=n这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点顺序存储图示顺序存储图示 顺序表的顺序表的C描述描述由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型 #define MAXSIZE 100 typedef int DataType; typedef stru { DataType data[MAXSIZE]; int length; } SeqList;顺序表上实现的基本操作顺序表上实现的基本操作在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。

注意：C语言中的数组下标从“0”开始，因此，若L是SeqList类型的顺序表，则表中第i个元素是L .data[i-1]1、顺序表的初始化、顺序表的初始化顺序表的初始化即构造了一个空的顺序表，设置顺序表的初始化即构造了一个空的顺序表，设置length域为域为0，表示表中没有数据元素，算法如下：，表示表中没有数据元素，算法如下： SeqList InitList { SeqList L; L.length=0; return L; }2、线性表的插入运算、线性表的插入运算线性表的插入运算是指在表的第i(1≦i≦n+1个位置上，插入一个新结点x，使长度为n的线性表 (a1，…ai-1，ai，…，an)变成长度为n+1的线性表 (a1，…ai-1，x，ai，…，an)线性表的插入运算代码线性表的插入运算代码int InsertList(Sqlist *L，DataType x，int i) { int j; if(i<1 || i > L.length+1) { printf(“Position error”); return ERROR; } if(L.length>=ListSize) { printf(“overflow”); exit(overflow); } for(j=L.length-1;j>=i-1;j--) L.data[j+1]=L.data[j]; L.data[i-1]=x; L.length++; }算法复杂性算法复杂性n对于顺序表上的插入，其基本操作是移动数据n位置0 – 移动n 位置n – 移动1 位置i – 移动n-i+1 不失一般性，假设在表中任何位置(1≦i≦n+1)上插入结点的机会是均等的，则 p1=p2=p3=…=p n+1=1/(n+1) n Ein=∑Pi * (n-i+1) =n/2 为在i个位置上平均移 i=1 动元素的次数（期望值） 算法复杂性为O(n) 3、线性表的删除运算、线性表的删除运算线性表的删除运算是指将表的第i(1≦i≦n)结点删除，使长度为n的线性表： (a1，…ai-1，ai，ai+1…，an)变成长度为n-1的线性表 (a1，…ai-1，ai+1，…，an)线性表的删除运算代码线性表的删除运算代码int deleteList(Sqlist*L，int i) { int j; if(i<1 || i>L.length) { printf(“Position error”); return ERROR ; } for(j=i;j<=L.length-1;j++) L.data[j-1]=L.data[j]; L.length--; }算法复杂性算法复杂性n对于顺序表上的删除，其基本操作是移动数据n位置0 – 移动n-1 位置n – 移动0 位置i – 移动n-i 不失一般性，假设在表中任何位置(1≦i≦n)上删除结点的机会是均等的，则 p1=p2=p3=…=p n=1/n n Ein=∑Pi * (n-i) =(n-1)/2 为在i个位置上平均移 i=1 动元素的次数（期望值） 算法复杂性为O(n) 4、线性表的按值查找、线性表的按值查找线性表中的按值查找是指性表中查找与给定值x相等的数据元素，从第一个元素a1起依次和x比较，直到找到一个与x相等的数据元素，则返回它在顺序表中的位置，没找到，则返回0线性表的按值查找算法线性表的按值查找算法nint ListLocate(SeqList L,ElemType x) { i=1; while(i<=L.length && L.data[i-1]!=x ) i++; if (i<=L.length) return i; else return 0; }算法复杂性算法复杂性n对于顺序表上的查找，其基本操作是比较数据n位置0 – 比较1 位置n –比较n 位置i –比较i 不失一般性，假设在表中任何位置(1≦i≦n)上比较结点的机会是均等的，则 p1=p2=p3=…=p n=1/n n Ein=∑Pi * i =(n+1)/2 为在i个位置上平均比较 i=1 元素的次数（期望值） 算法复杂性为O(n) 2.3 线性表的链式表示和实现线性表的链式表示和实现1、单链表的表示2、线性链表操作的实现线性链表线性链表线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的数据元素。

对线性表中的每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，我们把这种存储单元称为结点1、单链表的表示、单链表的表示单链表是最简单的一种链式结构单链表结点结构：DataNext此种形式的链表因只含有一个指针域，为单向链表，简称单链表单链表图示单链表图示a0a1an-1　 head head… (a) (b)图 线性链表的存储结构带头结点的单链表带头结点的单链表(a)为一个空线性链表 Head=Null(b)为一个非空线性链表（a0，a1，a2，…， an-1）单链表示例单链表示例例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat) 的单链表示意图如下：单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名例如：若头指针名是head，则把链表称为表head单链表的单链表的C语言描述语言描述 用C语言描述的单链表如下：Typedef char ElemType;Typedef struct node { ElemType data; struct node *next; } ListNode,*LinkedList; ListNode *linklist; ListNode *p; ListNode head;单链表的动态管理单链表的动态管理n注意区分指针变量和结点变量这两个不同的概念。

nP为动态变量，它是通过标准函数生成的，即 p=(ListNode *)malloc(sizeof(ListNode));n函数malloc分配了一个类型为ListNode的结点变量的空间，并将其首地址放入指针变量p中一旦p所指的结点变量不再需要了，又可通过标准函数 free(p) 释放所指的结点变量空间2、线性链表操作的实现、线性链表操作的实现单链表的初始化单链表的初始化课本上的示例:LinkedList *LinkedListInit(){ L=(ListNode*)malloc(sizeof(ListNode)); if(L==NULL) { printf(“没有足够空间”);exit(0);} L->next=NULL; return L; }实际程序实际程序int Initiate(ListNode * *h){*h=(ListNode*)malloc(sizeof(ListNode)); if(*h==NULL) return FALSE; (*h)->next=NULL; return TRUE; }注意：形参h定义为指针的指针类型，若定义为指针类型，将无法带回函数中建立的头指针值。

#define FALSE -1 #define TRUE 1 Typedef char ElemType;Typedef struct node { ElemType data; struct node *next; } ListNode,*LinkedList;求表长Int LinkedListLength(LinkedList L){ p=L->Next; j=0; while(p) { j++;p=p->next;} return j;}改进的单链表的改进的单链表的C语言描述语言描述 通过求表长；须一个一个进行计算，麻烦！而每一个链表都有一个头结点，因此在改进链表结构：Typedef struct node { ElemType data; int Length; struct node *next; } ListNode,*LinkedList;单链表初始化单链表初始化int Initiate(ListNode * *h){*h=(ListNode*)malloc(sizeof(ListNode)); if(*h==NULL) return FALSE; (*h)->next=NULL; (*h)->length=0;return TRUE; }单链表其他操作单链表其他操作1.插入2.删除3.按序号查找4.按数值查找单链表插入操作单链表插入操作在单链表中的实现：有序对有序对 改变为改变为 和和ai-1 eaiai-1单链表插入操作代码单链表插入操作代码 Status ListInsert (LinkedList L, int i, ElemType e) { // L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 // 在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e p = L; j = 0; while (p && j < i-1) { p = p->next; ++j; } // 寻找第寻找第 i-1 个结点个结点 if (!p || j > i-1) return ERROR; // i 大于表长或者小于大于表长或者小于1 …… } // LinstInsert 算法的算法的时间复杂度时间复杂度为:O(ListLength(L))单链表插入操作示意单链表插入操作示意s = (ListNode *) malloc ( sizeof (ListNode)); // 生成新结点s->data = e; s->next = p->next; p->next = s; // 插入return OK; eai-1aiai-1spP->next单链表删除操作单链表删除操作线性表的操作ListDelete (&L, i, &e)在链表中的实现:有序对有序对< > 和和 < > 改变为改变为 < >ai-1aiai+1ai-1单链表删除操作示意单链表删除操作示意 在单链表中删除第删除第 i i 个结点个结点的基本操作基本操作为:找到线性表中第找到线性表中第i-1i-1个结点，修改其指向个结点，修改其指向后继的指针。

后继的指针ai-1aiai+1ai-1q = p->next; p->next = q->next; e = q->data; free(q); L->Length++; pq单链表删除操作代码单链表删除操作代码 int ListDelete (LinkedList L, int i, ElemType &e) { // 删除以 L 为头指针(带头结点)的单链表中第 i 个结点} // ListDelete算法的算法的时间复杂度时间复杂度为: O(ListLength(L))p = L; j = 0;while (p->next && j < i-1) { p = p->next; ++j; } // 寻找第寻找第 i 个结点，并令个结点，并令 p 指向其前趋指向其前趋if (!(p->next) || j > i-1) return FALSE; // 删除位置不合理删除位置不合理q = p->next; p->next = q->next; // 删除并释放结点e = q->data; free(q); L->Length--;return TRUE;2.4 线性表实现方法的比较线性表实现方法的比较n实现方法不同：数组、指针n存储空间的占用和分配不同n线性表操作的实现不同 随机访问 插入、删除 2.5 循环链表循环链表 最后一个结点的指针域的指针又指回第一个结点的链表 a1 a2 … ... an 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。

2.6 双链表双链表n在单链表的每个结点中只有一个指示后继的指针域，因此从任何一个结点都能通过指针域找到它的后继结点；若需找出该结点的前驱结点，则此时需从表头出发重新查找换句话说，在单链表中，查找某结点的后继结点的执行时间为O(1)，而查找其前驱结点的执行时间为O(n)n我们可用双向链表来克服单链表的这种缺点n在双向链表中，每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点双链表结构描述双链表结构描述Typedef struct node { ElemType data; struct node *prior; struct node *next; } ListNode,*LinkedList;双向循环链表双向循环链表空表空表非空表非空表 a1 a2 … ... an2.7 静态链表静态链表。