《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源02 线性表》由会员分享，可在线阅读，更多相关《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源02 线性表（46页珍藏版）》请在金锄头文库上搜索。
1、,数据结构与算法,第二章 线性表,唐懿芳,目 录,线性表的定义,顺序线性表,线性表的链式存储,第一节,第二节,第三节,CONTENTS,循环单链表和双向链表,第四节,实训,第五节,目 录,线性表的定义,顺序线性表,线性表的链式存储,第一节,第二节,第三节,CONTENTS,循环单链表和双向链表,第四节,实训,第五节,线性表的定义,定义,由n(n)个相同类型数据元素(结点)a1，a2， an组成的有限序列。 (a1，a2，an) 其中： n：数据元素的个数，也称表的长度。 空表：n=0，记为（）,举例,由26个英文字母构成的表（a,b,c,z）是一个线性表； 由全体职工的基本工资构成的表（123
2、6.60,1669.80,900.00,890.00,1842.00）是线性表。 我们常常玩的扑克牌，其数据元素牌，是由牌点、花色两项组成的，是复合数据类型，这种类型的线性表称为复合线性表 。,数据结构与算法,线性表的定义,数据结构与算法,在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1； 其余的内部结点ai(2in-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。,线性表的特征,线性表的定义,求表长求线性表中元素的个数。 遍历从左到右（或从右到左）扫描（或读取）表中的各元素。 按
3、编号查找找出表中第i个元素。 按特征查找按某个特定值查找线性表。 插入在第i个位置上（即原第i个元素前）插入一新元素。 删除删除原表中的第i个元素。 排序按元素某特征值的递增（或递减）排序，重排表中各元素。,线性表的基本运算,数据结构与算法,目 录,线性表的定义,顺序线性表,线性表的链式存储,第一节,第二节,第三节,CONTENTS,循环单链表和双向链表,第四节,实训,第五节,顺序表的定义,数据结构与算法,顺序表：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 特点：逻辑上相邻的数据元素，其物理（存储）位置也是相邻的。,LOC(ai) = LOC
4、(ai-1) + k,LOC(ai) =b+(i-1)k,顺序表的定义,数据结构与算法,由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。,顺序表的定义,MaxSize -1,备用空间,有效结点,顺序表的定义,数据结构与算法,GetLength()： 求顺序表中元素的个数 PrintList()：遍历一个顺序表 GetElem(int i)：按编号查找 Locate(object e)：按特征查找 InsertList( int i, object e)：在顺序表中插入一个元素 DeleteList(int i)：从顺序表中删除一个元素,基于顺序表的运算的实现,顺序表的
5、定义,数据结构与算法,基于顺序表的运算的实现,int Locate(SeqList l，ElemType e) /*在顺序表l中查找元素e，若 l.elemi=e，则找到该元素，并返回i，若找不到，返回-1*/ i=0 ; while (i=l.listlength-1) /* Locate */,顺序表的定义,数据结构与算法,基于顺序表的运算的实现,顺序表的定义,数据结构与算法,基于顺序表的运算的实现,/*在顺序表l中第i（i应视作数组的下标）个数据元素之前插入元素e*/ void InsList(SeqList *l, int i, ElemType e) if(i=l- listleng
6、th) /*判断插入位置是否合法*/ printf(“Error”)； if(l- listlength = MaxSize-1) /*判断表是否已满*/ printf(“Overflow”)； return; for(k=l- listlength-1; k=i; k-) /*将元素elemlistlength-1i依次向后移动一个单元*/ l-elemk+1=l-elemk; l-elemi=e; l- listlength+; ,顺序表的定义,数据结构与算法,基于顺序表的运算的实现,删除l中的第i个数据元素（DelList(l,i)），使得线性表(a1, ai-1, ai, , an)
7、改变为(a1,，ai-1, ai+1, ,an)。 即： 改变了线性表中元素之间的关系，使和改变为，同时表长减1。,顺序表的定义,数据结构与算法,基于顺序表的运算的实现,/*在顺序表l中删除第i（i应视作数组的下标）个数据元素*/ void DelList(SeqList *l,int i) if(il-listlength-1) /*判断删除位置是否合法*/ printf(“Error“)； return; for(k=i+1; ilistlength-1; k+) l-elemk-1= l-elemk; /*将第i个数据元素后面的元素依次前移*/ l-listlength-; ,目 录,线
8、性表的定义,顺序线性表,线性表的链式存储,第一节,第二节,第三节,CONTENTS,循环单链表和双向链表,第四节,实训,第五节,线性表的链式表示和实现,数据结构与算法,1. 单链表的结构,线性表的链式表示和实现,数据结构与算法,2. 基本操作 在带头结点单链表第一个数据元素前插入结点,线性表的链式表示和实现,数据结构与算法,2. 基本操作 删除带头结点单链表第一个数据元素结点,线性表的链式表示和实现,数据结构与算法,2. 基本操作 在不带头结点单链表第一个数据元素前插入结点,线性表的链式表示和实现,数据结构与算法,2. 基本操作 在不带头结点单链表其他数据元素前插入结点,线性表的链式表示和实现
9、,数据结构与算法,2. 基本操作 删除不带头结点单链表第一个数据元素结点,线性表的链式表示和实现,数据结构与算法,2. 基本操作 删除不带头结点单链表其他数据元素结点,线性表的链式表示和实现,数据结构与算法,2. 基本操作 结论,（1）带头结点单链表无论在第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，操作方法不一样 （2）删除操作和插入操作类似 （3）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表的算法时，头指针参数必须设计成输出型参数 （4）带头结点单链表的算法设计简单,线性表的
10、链式表示和实现,数据结构与算法,3. 结点结构代码描述,/*线性表的单链表存储结构*/ typedef int ElemType; / ElemType根据实际情况确定 /这里为了简单，假设为int typedef struct Node ElemType data; struct Node *next; Node; typedef struct Node *LinkList; /定义单链表LinkList,线性表的链式表示和实现,数据结构与算法,4. 单链表的基本运算 求单链表中元素的个数,/*初始条件：以head表示单链表，假设单链表head已存在*/ /*操作结果：返回head中数据元素
11、个数 */ int Length(LinkList head) int i=0; LinkList p=head-next; /* p指向第一个结点 */ while(p) i+; p=p-next; return i; ,线性表的链式表示和实现,数据结构与算法,4. 单链表的基本运算 求遍历单链表,/*初始条件：单链表head已存在*/ /*操作结果：输出head中的数据元素 */ void Print(LinkList head) LinkList p=head-next; /* p指向第一个结点 */ while(p) printf(“%d ”,p-data); /输出单链表中的数据元素
12、 p=p-next; printf(”n”); ,线性表的链式表示和实现,数据结构与算法,4. 单链表的基本运算 按编号查找,要找到第i个元素，必须从表头一步步查找 /初始条件：单链表head已存在，1iLength(head) /操作结果：用e返回head中第i个数据元素的值 void GetElem(LinkList head,int i,ElemType *e) int j; LinkList p; /* 声明一结点p */ p = head-next; /* 让p指向链表head的第一个结点 */ j = 1; /* j为计数器 */ while (p ,线性表的链式表示和实现,数据结
13、构与算法,4. 单链表的基本运算 按特征查找,/* 初始条件：顺序线性表L已存在 */ /* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */ /* 若这样的数据元素不存在，则返回值为0 */ int LocateElem(LinkList L,ElemType e) int i=0; LinkList p=L-next; while(p) i+; if(p-data=e) /* 找到这样的数据元素 */ return i; p=p-next; return 0; ,线性表的链式表示和实现,数据结构与算法,4. 单链表的基本运算 在单链表中插入一个结点,单链表的插入可以直接修改指针
14、域，不用移动其它元素，比线性表的顺序存储的插入简单很多。单链表在第i个数据插入结点的算法思路如下： 声明一个指针pre指向链表头结点，初始化j从1开始； 当jdata； 结点s插入单链表第i个位置如图2.10所示，单链表的插入语句s-next=pre-next;pre-next=s; 程序结束。,线性表的链式表示和实现,数据结构与算法,4. 单链表的基本运算 单链表插入元素的实现,/* 初始条件：顺序线性表head已存在,1iListLength(head)， */ /* 操作结果：在head中第i个位置之前插入新的数据元素x，链表长度加1 */ void Insert(LinkList *h
15、ead,int i,ElemType x) int j; LinkList pre,s; pre = *head; j = 0; while (pre /* 第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. 当jnext=p-next; 6. 将p结点的数据赋值给e; 7. 释放p结点，程序结束。,线性表的链式表示和实现,数据结构与算法,4. 单链表的基本运算 单链表删除结点的实现,/* 初始条件：顺序线性表head已存在，1iListLength(head) */ /* 操作结果：删除head的第i个数据元素，并用e返回其值，head的长度减1 */ void Delete(LinkList *h
