数据结构与算法课件02 线性表VIP

数据结构与算法第二章线性表唐懿芳

目录线性表的定义顺序线性表线性表的链式存储第一节第二节第三节CONTENTS循环单链表和双向链表第四节实训第五节目录线性表的定义顺序线性表线性表的链式存储第一节第二节第三节CONTENTS循环单链表和双向链表第四节实训第五节线性表的定义定义由n(n≧)个相同类型数据元素(结点)a1，a2，…an组成的有限序列。

(a1，a2，…an)

其中：

n：数据元素的个数，也称表的长度。

空表：n=0，记为（）举例由26个英文字母构成的表（a,b,c,…,z）是一个线性表；由全体职工的基本工资构成的表（1236.60,1669.80,900.00,890.00,…,1842.00）是线性表。我们常常玩的扑克牌，其数据元素——牌，是由牌点、花色两项组成的，是复合数据类型，这种类型的线性表称为复合线性表。数据结构与算法线性表的定义数据结构与算法在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表的特征线性表的定义求表长——求线性表中元素的个数。遍历——从左到右（或从右到左）扫描（或读取）表中的各元素。按编号查找——找出表中第i个元素。按特征查找——按某个特定值查找线性表。插入——在第i个位置上（即原第i个元素前）插入一新元素。删除——删除原表中的第i个元素。排序——按元素某特征值的递增（或递减）排序，重排表中各元素。线性表的基本运算数据结构与算法目录线性表的定义顺序线性表线性表的链式存储第一节第二节第三节CONTENTS循环单链表和双向链表第四节实训第五节顺序表的定义数据结构与算法顺序表：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。特点：逻辑上相邻的数据元素，其物理（存储）位置也是相邻的。a1

a2

…ai-1

ai…an存储首址bb+k…b+(i-2)kb+(i-1)k…b+(n-1)kLOC(ai)=LOC(ai-1)+kLOC(ai)=b+(i-1)k顺序表的定义数据结构与算法由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。顺序表的定义a1a2an内存0MaxSize-1备用空间有效结点顺序表的定义数据结构与算法GetLength()：求顺序表中元素的个数

PrintList()：遍历一个顺序表

GetElem(inti)：按编号查找Locate(objecte)：按特征查找

InsertList(inti,objecte)：在顺序表中插入一个元素DeleteList(inti)：从顺序表中删除一个元素基于顺序表的运算的实现顺序表的定义数据结构与算法基于顺序表的运算的实现查找运算intLocate(SeqListl，ElemTypee)/*在顺序表l中查找元素e，若l.elem[i]=e，则找到该元素，并返回i，若找不到，返回-1*/{i=0;while((i<=l.listlength-1)&&(l.elem[i]!=e))/*顺序扫描表，直到找到值为e元素,或扫到表尾而没找到*/i++;if(i<=l.listlength-1)return(i);elsereturn(-1);}/*Locate*/顺序表的定义数据结构与算法基于顺序表的运算的实现插入算法a1 … ai-1

ai … an

a1 … ai-1 e ai … an

插入之前移动元素插入之后图2.2在第i个元素前插入e顺序表的定义数据结构与算法基于顺序表的运算的实现插入算法/*在顺序表l中第i（i应视作数组的下标）个数据元素之前插入元素e*/

voidInsList(SeqList*l,inti,ElemTypee){

if((i<0)||(i>=l->listlength))/*判断插入位置是否合法*/

printf(“Error”)；

if(l->listlength>=MaxSize-1)/*判断表是否已满*/

{printf(“Overflow”)；

return;

}

for(k=l->listlength-1;k>=i;k--)/*将元素elem[listlength-1..i]依次向后移动一个单元*/l->elem[k+1]=l->elem[k];

l->elem[i]=e;

l->listlength++;}顺序表的定义数据结构与算法基于顺序表的运算的实现删除算法删除l中的第i个数据元素（DelList(l,i)），使得线性表(a1,…,ai-1,ai,…,an)改变为(a1,…，ai-1,ai+1,…,an)。即：改变了线性表中元素之间的关系，使<ai-1,ai>和<ai,ai+1>改变为<ai-1,ai+1>，同时表长减1。删除之前移动元素删除之后图2-3删除第i个元素a1 … ai-1

ai

ai＋1 … an

a1 … ai-1

ai … an

顺序表的定义数据结构与算法基于顺序表的运算的实现删除算法/*在顺序表l中删除第i（i应视作数组的下标）个数据元素*/voidDelList(SeqList*l,inti){if((i<0)||(i>l->listlength-1))/*判断删除位置是否合法*/{printf("Error")；

return;}for(k=i+1;i<=l->listlength-1;k++)l->elem[k-1]=l->elem[k];

/*将第i个数据元素后面的元素依次前移*/l->listlength--;}目录线性表的定义顺序线性表线性表的链式存储第一节第二节第三节CONTENTS循环单链表和双向链表第四节实训第五节线性表的链式表示和实现数据结构与算法1.单链表的结构单链表中构成链表的结点只有一个指向直接后继结点的指针域。其结构特点：

逻辑上相邻的数据元素在物理上不一定相邻。

指针域数据域

nextdata或存储元素数值数据存储直接后继的存储位置线性表的链式表示和实现数据结构与算法2.基本操作·在带头结点单链表第一个数据元素前插入结点

pa0a1an-1∧…headdatanextx∧s(a)插入前pa0a1an-1∧…headDatanextx∧s(b)插入后线性表的链式表示和实现数据结构与算法2.基本操作·删除带头结点单链表第一个数据元素结点

pa0a1an-1∧…headdatanext线性表的链式表示和实现数据结构与算法2.基本操作·在不带头结点单链表第一个数据元素前插入结点

a0a1an-1∧…headx∧s(a)插入前a0a1an-1∧…headxs(b)插入后线性表的链式表示和实现数据结构与算法2.基本操作·在不带头结点单链表其他数据元素前插入结点

pai-1a0aian-1∧…headdatanextxs…×线性表的链式表示和实现数据结构与算法2.基本操作·删除不带头结点单链表第一个数据元素结点

a0a1an-1∧…headdatanext×线性表的链式表示和实现数据结构与算法2.基本操作·删除不带头结点单链表其他数据元素结点

pai-1a0aian-1∧…headdatanext…×ai+1线性表的链式表示和实现数据结构与算法2.基本操作·结论

（1）带头结点单链表无论在第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，操作方法不一样（2）删除操作和插入操作类似（3）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表的算法时，头指针参数必须设计成输出型参数（4）带头结点单链表的算法设计简单线性表的链式表示和实现数据结构与算法3.结点结构代码描述

/*线性表的单链表存储结构*/typedefintElemType;//ElemType根据实际情况确定//这里为了简单，假设为inttypedefstructNode{ElemTypedata;structNode*next;}Node;typedefstructNode*LinkList;//定义单链表LinkList线性表的链式表示和实现数据结构与算法4.单链表的基本运算·求单链表中元素的个数/*初始条件：以head表示单链表，假设单链表head已存在*//*操作结果：返回head中数据元素个数*/intLength(LinkListhead){inti=0;LinkListp=head->next;

/*p指向第一个结点*/while(p){i++;p=p->next;}returni;}线性表的链式表示和实现数据结构与算法4.单链表的基本运算·求遍历单链表/*初始条件：单链表head已存在*//*操作结果：输出head中的数据元素*/voidPrint(LinkListhead){LinkListp=head->next;/*p指向第一个结点*/

while(p){printf(“%d”,p->data);//输出单链表中的数据元素

p=p->next;}printf(”\n”);}线性表的链式表示和实现数据结构与算法4.单链表的基本运算

·按编号查找要找到第i个元素，必须从表头一步步查找//初始条件：单链表head已存在，1≤i≤Length(head)//操作结果：用e返回head中第i个数据元素的值voidGetElem(LinkListhead,inti,ElemType*e){ intj; LinkListp; /*声明一结点p*/ p=head->next;/*让p指向链表head的第一个结点*/

j=1;

/*j为计数器*/ while(p&&j<i)

/*p不为空或者计数器j还没有等于i时，循环继续*/ { p=p->next;/*让p指向下一个结点*/ j++; } if(!p||j>i) return;

/*第i个元素不存在*/ *e=p->data;

/*取第i个元素的数据*/ return;}线性表的链式表示和实现数据结构与算法4.单链表的基本运算

·按特征查找/*初始条件：顺序线性表L已存在*//*操作结果：返回L中第1个与e满足关系的数据元素的位序。*//*若这样的数据元素不存在，则返回值为0*/intLocateElem(LinkListL,ElemTypee){inti=0;LinkListp=L->next;while(p){i++;if(p->data==e)/*找到这样的数据元素*/returni;p=p->next;}

return0;}

线性表的链式表示和实现数据结构与算法4.单链表的基本运算·在单链表中插入一个结点单链表的插入可以直接修改指针域，不用移动其它元素，比线性表的顺序存储的插入简单很多。单链表在第i个数据插入结点的算法思路如下：声明一个指针pre指向链表头结点，初始化j从1开始；当j<i-1时，就遍历链表，让pre的指针向后移动，目的就是让pre指向第i个元素的前一个指针，如图2.8所示；若到链表末尾pre为空，则说明第i个结点不存在；若查找成功，在系统分配一个空间给新结点s，如图2.9所示；将数据元素x赋值给s->data；结点s插入单链表第i个位置如图2.10所示，单链表的插入语句s->next=pre->next;pre->next=s;程序结束。

线性表的链式表示和实现数据结构与算法4.单链表的基本运算·单链表插入元素的实现/*初始条件：顺序线性表head已存在,1≤i≤ListLength(head)，*//*操作结果：在head中第i个位置之前插入新的数据元素x，链表长度加1*/voidInsert(LinkList*head,inti,ElemTypex){ intj; LinkListpre,s; pre=*head; j=0; while(pre&&j<i-1)

/*寻找第i个结点*/

{ pre=pre->next; j++; } if(!pre||j!=i-1) {printf(“第i个元素不存在\n”);return;

/*第i个元素不存在*/}

s=(LinkList)malloc(sizeof(Node));/*生成新结点(C语言标准函数)*/ s->data=x; s->next=pre->next;/*将p的后继结点赋值给s的后继*/ pre->next=s;/*将s赋值给p的后继*/ return;}

线性表的链式表示和实现数据结构与算法4.单链表的基本运算·从单链表中删除一个结点从单链表中删除第i个结点的算法思路：1.声明工作指针pre指向链表的头指针，初始化j从0开始；2.当j<i-1时，遍历链表，让pre的指针不断向后移动，j累加1，如图2.11所示；3.若到链表末尾pre为空，则说明第i个结点不存在；4.若查找成功，则利用pre定位欲删除的结点p，如图2.12所示；5.单链表的删除语句pre->next=p->next;6.将p结点的数据赋值给e;7.释放p结点，程序结束。

线性表的链式表示和实现数据结构与算法4.单链表的基本运算·单链表删除结点的实现/*初始条件：顺序线性表head已存在，1≤i≤ListLength(head)*//*操作结果：删除head的第i个数据元素，并用e返回其值，head的长度减1*/voidDelete(LinkList*head,inti,ElemType*e){ intj; LinkListpre,p; pre=*head; j=0; while(pre->next&&j<i-1) /*遍历寻找第i个元素*/ {pre=pre->next;j++; } if(!(pre->next)||j!=i-1) {printf(“第i个元素不存在\n”);return;

/*第i个元素不存在*/} p=pre->next; pre->next=p->next;

/*将p的后继赋值给pre的后继*/ *e=p->data;

/*将p结点中的数据给e*/ free(p);

/*让系统回收此结点，释放内存*/}

线性表的链式表示和实现数据结构与算法5.单链表的创建单链表的基本操作都是建立在单链表已经存在于内存的基础上，但事实上在程序开始，如果自己不创建，这个单链表是不存在的。我们需要先创建单链表。

创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态开始，依次建立各元素结点，并逐个插入链表。这种方法创建链表，就是在建立头结点之后，反复地调用插入算法。

单链表创建的算法思路如下：(1)声明一个指针和循环变量i；(2)初始化一个空链表head;(3)让head的头结点的指针指向NULL，即建立一个带头结点的单链表；(4)循环：①生成一新结点赋值给s；②随机生成1-100之间的数字赋值给s的数据域s->data;③将s插入到头结点与前一新结点之间线性表的链式表示和实现数据结构与算法5.单链表的创建·头插法的实现代码/*随机产生n个元素的值，建立带表头结点的单链线性表head（头插法）*/voidCreateHead(LinkList*head,intn){ LinkLists; inti; srand(time(0));

/*初始化随机数种子*/ *head=(LinkList)malloc(sizeof(Node)); (*head)->next=NULL;

/*先建立一个带头结点的单链表*/ for(i=0;i<n;i++) { s=(LinkList)malloc(sizeof(Node));/*生成新结点*/ s->data=rand()%100+1;

/*随机生成100以内的数字*/ s->next=(*head)->next; (*head)->next=s;

/*插入到表头*/ }}线性表的链式表示和实现数据结构与算法5.单链表的创建·尾插法的实现代码尾插法为产生的新结点插入链表的尾端，/*随机产生n个元素的值，建立带表头结点的单链线性表head（尾插法）*/voidCreateTail(LinkList*head,intn){ LinkLists,r; inti; srand(time(0));

/*初始化随机数种子*/ *head=(LinkList)malloc(sizeof(Node));/*head为整个线性表*/ r=*head;

/*r为指向尾部的结点*/ for(i=0;i<n;i++) { s=(Node*)malloc(sizeof(Node));/*生成新结点*/ s->data=rand()%100+1;

/*随机生成100以内的数字*/ r->next=s;

/*将表尾终端结点的指针指向新结点*/ r=s;

/*将当前的新结点定义为表尾终端结点*/ } r->next=NULL;

/*表示当前链表结束*/}线性表的链式表示和实现数据结构与算法6.单链表操作的效率分析单链表的插入和删除操作不需移动数据元素，只需比较数据元素。因此，当在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：删除一个数据元素时比较数据元素的平均次数为：另外，单链表求数据元素个数操作的时间复杂度为O(n)。线性表的链式表示和实现数据结构与算法7.单链表VS顺序表单链表主要优点是不需要预先确定数据元素的最大个数，插入和删除操作不需要移动数据元素；单链表主要缺点是查找数据元素时需要顺序进行，不能像顺序表那样随机查找任意一个数据元素。另外，每个结点中要有一个指针域，因此空间单元利用率不高。而且单链表操作的算法也较复杂。目录线性表的定义顺序线性表线性表的链式存储第一节第二节第三节CONTENTS循环单链表和双向链表第四节实训第五节循环单链表和双向链表数据结构与算法1.循环单链表单链表主要优点是不需要预先确定数据元素的