数据结构60771

1、v教学目的教学目的1.了解线性表逻辑结构的基本特征了解线性表逻辑结构的基本特征;2.掌握线性表的顺序存储结构和链式存储结构，掌握线性表的顺序存储结构和链式存储结构，它们如何表达线性表中数据元素之间的结构关它们如何表达线性表中数据元素之间的结构关系；如何用系；如何用C语言描述它们的类型定义；语言描述它们的类型定义；3.掌握顺序表的基本操作的算法；掌握顺序表的基本操作的算法；4.掌握链表的建立及其基本操作的算法；掌握链表的建立及其基本操作的算法；5.能够从时间复杂度的角度，比较线性表两类存能够从时间复杂度的角度，比较线性表两类存储结构的不同特点及使用场合储结构的不同特点及使用场合.v教学重点难点教

2、学重点难点1.掌握顺序表的基本操作掌握顺序表的基本操作:查找、插入、删除。查找、插入、删除。 2.在掌握链表的建立与遍历的基础上，能够实现在掌握链表的建立与遍历的基础上，能够实现链表的基本操作：插入与删除、查找。链表的基本操作：插入与删除、查找。教学内容教学内容 2.1.1 线性表的定义线性表的定义 线性表线性表是由是由n（n0）个类型相同的数据元素组）个类型相同的数据元素组成的有限序列。通常表示成下列形式：成的有限序列。通常表示成下列形式： L=( a1, a2,.,ai-1,ai,ai+1,.,an) 其中：其中：L为线性表名称，习惯用大写书写；为线性表名称，习惯用大写书写； ai为组成该

3、线性表的数据元素，习惯用小写书写；为组成该线性表的数据元素，习惯用小写书写； 特点：除了特点：除了a1 ， an 外，外，ai（2=ilast=-1; return L;6. 2.在数组在数组a第第i个数据元素之（个数据元素之（ai-1）前插入数据）前插入数据元素元素Xinsert (int a ,int n,int i, int x) int j; for(j=n-1;j=i-1;j-) aj+1=aj; /* 结点移动结点移动 */ ai-1=x;/*新元素插入新元素插入*/ n+; /*修改长度修改长度*/ 3.在数组在数组a中检索（查找）值为中检索（查找）值为X的数据元素的数据元素 i

4、nt locate (int a ,int n, int x) int i; i=0; while(i=n-1)&(ai!=x) i+; if(i=n-1) return (i); /*返回的是存储位置返回的是存储位置*/ else return (0); 4.删除数组删除数组a第第i个数据元素（个数据元素（ai-1）delete (int a ,int n,int i) int j; for(j=i;j=n;j+) aj-1=aj; /* 结点移动结点移动 */n-; /*修改长度修改长度*/ 顺序表的插入顺序表的插入：在表中第在表中第4个元素之前插入个元素之前插入“21”。顺序表中插入元素

5、顺序表中插入元素 491528303042516249152830304251624915283030425162序号移动元素插入元素21图图 顺序表中删除元素顺序表中删除元素 顺序表的删除顺序表的删除：删除第：删除第5个元素，个元素， 插入算法的分析插入算法的分析 假设线性表中含有假设线性表中含有n个数据元素，在进行插入个数据元素，在进行插入操作时，若假定在操作时，若假定在n+1个位置上插入元素的可能个位置上插入元素的可能性均等，则平均移动元素的个数为：性均等，则平均移动元素的个数为：1n1iis2n1)i(n1n1E 删除算法的分析删除算法的分析 在进行删除操作时，若假定删除每个元素的可能

6、在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：性均等，则平均移动元素的个数为： 分析结论分析结论 顺序存储结构表示的线性表，在做插入或删除操顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。作时，这一点需要值得考虑。n1idl21ni)(nn1E1. 在一个长度为在一个长度为n的顺序表中向第的顺序表中向第i(0=i=n)个元素位置个元素位置插入一个新元素时间插入一个新

7、元素时间,需要移动需要移动( )元素元素.2. 在一个长度为在一个长度为n的顺序表删除第的顺序表删除第i个元素个元素i(0=idata=x; s-next=L; L=s; scanf (%d,&x); return L;2. 求表长求表长(带头结点的带头结点的) ) int Length_LinkList1 (LinkList L) Lnode * p=L; /* p指向头结点指向头结点*/ int j=0; while (p-next) p=p-next; j+ /* p所指的是第所指的是第 j 个结点个结点*/ return j;3. 查找操作查找操作 (1) (1) 按序号查找按序号查找

8、 Get_Linklist(L,i) Lnode * Get_LinkList(LinkList L, Int i);/*在单链表在单链表L中查找第中查找第i个元素结点，找到返回其指针，否则个元素结点，找到返回其指针，否则返回空返回空*/ Lnode * p=L; int j=0;while (p-next !=NULL & jnext; j+; if (j=i) return p; else return NULL; (2)(2)按值查找即定位按值查找即定位 Locate_LinkList(L,x)Lnode * Locate_LinkList( LinkList L, datatype x

9、) /*在单链表在单链表L中查找值为中查找值为x的结点，找到后的结点，找到后返回其指针，否则返回空返回其指针，否则返回空*/ Lnode * p=L-next; while ( p!=NULL & p-data != x) p=p-next; return p; Sxxs插入pp4.插入操作插入操作(后插结点后插结点)注意:两个指针的操作顺序不能交换4.插入操作插入操作void Insert_LinkList( LinkList L, int i, datatype x) /*在单链表在单链表L的第的第i个位置上插入值为个位置上插入值为x的元素的元素*/ Lnode * p,*s; p=Get

10、_LinkList(L,i-1); /*查找第查找第i-1个结点个结点*/ if (p=NULL) printf(参数参数i错错);exit( 0); /*第第i-1个不存在不能插入个不存在不能插入*/ else s=malloc(sizeof(LNode); /*申请、填装结点申请、填装结点*/ s-data=x; s-next=p-next; /*新结点插入在第新结点插入在第i-1个结点的后面个结点的后面*/ p-next=s; xs在*p之前插入*sq/* 给给q赋初值赋初值, 即让即让q指向头指针变量指向头指针变量*/4.插入操作插入操作(前插结点前插结点)/*查找查找*p的前驱结点的

11、前驱结点*/ps = p-next; p-next = s-next;free(s); 删除前删除前L(非空表）非空表）Lps删除后删除后5. 5. 删除操作删除操作 void Del_LinkList(LinkList L，int i) /*删除单链表删除单链表L上的第上的第i个数据结点个数据结点*/ LinkList p,s; p=Get_LinkList(L,i-1); /*查找第查找第i-1个结点个结点*/ if (p=NULL) printf(第第i-1个结点不存在个结点不存在);exit( -1); else if (p-next=NULL) printf(第第i个结点不存在个结点

12、不存在);exit(0); else s=p-next; /*s指向第指向第i个结点个结点*/ p-next=s-next; /*从链表中删除从链表中删除*/ free(s); /*释放释放*s */ 通过上面的基本操作可以得知通过上面的基本操作可以得知: :1.1.在单链表上插入、删除一个结点在单链表上插入、删除一个结点, ,必须必须知道其前驱结点知道其前驱结点. .2.2.单链表不具有按序号随机访问的特点单链表不具有按序号随机访问的特点, ,只能从头指针开始顺序地进行只能从头指针开始顺序地进行. .2.3.3 循环链表循环链表 若将链表中最后一个结点的若将链表中最后一个结点的next域指向

13、头结点域指向头结点 实现循环链表的类型定义与单链表完全相同，它的所有实现循环链表的类型定义与单链表完全相同，它的所有操作也都与单链表类似。只是判断链表结束的条件有操作也都与单链表类似。只是判断链表结束的条件有所不同由原来的所不同由原来的p或或p-next是否为空，变为是否为空，变为p是否等于是否等于头指针头指针.head 图图2-7 带头结点的循环链表示意图带头结点的循环链表示意图说明 在解决某些实际问题时循环链表可能要比线性链在解决某些实际问题时循环链表可能要比线性链表方便些。因为在单循环链表中可以从表中任意表方便些。因为在单循环链表中可以从表中任意一个结点开始遍历整个链表一个结点开始遍历整

14、个链表. 对循环链表，有时不给出头指针，而是给出尾指对循环链表，有时不给出头指针，而是给出尾指针，设了尾指针可以很方便的找到线性表的第一针，设了尾指针可以很方便的找到线性表的第一个元素和最后一个元素结点，可使某些操作易于个元素和最后一个元素结点，可使某些操作易于实现；例如将两个链表首尾相连的操作；实现；例如将两个链表首尾相连的操作；(见课本见课本P32)r ra1an给出尾指针的循环链表给出尾指针的循环链表 2.3.4 2.3.4 双向链表双向链表 1.1.在循环链表中，访问结点的特点在循环链表中，访问结点的特点: : 访问后继结点，只需要向后走一步，而访问前访问后继结点，只需要向后走一步，而

15、访问前驱结点，就需要转一圈。驱结点，就需要转一圈。 结论：循环链表并不适用于经常访问前驱结点的结论：循环链表并不适用于经常访问前驱结点的情况。情况。 2.2.解决方法：在需要频繁地同时访问前驱和后继解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓双向链表。结点的时候，使用双向链表。所谓双向链表。 双向链表就是每个结点有两个指针域。一个指双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。向后继结点，另一个指向前驱结点。2. 2.3.42.3.4双向链表(Double Linked List)类型描述typedef struct Dlnode dataT

16、ype data; struct Dlnode *prior, *next; Dlnode, *DLinkList;prior data next前驱指针域 数据域后继指针域La1a2a3L(a) 空的双向循环链表(b) 非空的双向循环链表2.3.4双向循环链表双向循环链表p-next-prior = p-prior-next;pp-nextp-priorp-prior-nextl双向链表的前双向链表的前(后后)插操作插操作abspcs-prior = p-prior; p-prior-next = s; s-next = p; p-prior = s;qs-next = q-next; q-

17、next-prior= s; s-prior = q; q-next = s;abcpl双向链表的删除操作双向链表的删除操作p-prior-next = p-next;p-next-prior = p-prior; free(p)l删除删除*p的直接后继结点的语句序列的直接后继结点的语句序列 q = p-next; p-next = p-next-next; p-next-prior = p; free(q);l删除删除*p的直接前驱结点的语句序列的直接前驱结点的语句序列 q = p-prior; p-prior = p-prior-prior; p- prior-next = p; free

18、(q); 基于空间的考虑基于空间的考虑 存储密度存储密度=元素本身所占的存储量元素本身所占的存储量/实际分配的存储实际分配的存储总量总量基于时间的考虑基于时间的考虑 顺序表：随机存取结构，顺序表：随机存取结构，O(1) 。 链表：链表： 顺序存取结构，顺序存取结构，O(n) 。例例2.4 已知单链表H，写一算法将其倒置。即实现如图2.22的操作。(a)为倒置前，(b)为倒置后。 图2.22 单链表的倒置254525187629H297625184525H(a)(b)HH29761845252545187629(a)(b)算法思路：依次取原链表中的每个结点，将其作为第一个结点插算法思路：依次取原

19、链表中的每个结点，将其作为第一个结点插到新链表中去，指针到新链表中去，指针p用来指向当前结点，用来指向当前结点，p为空时结束。算法如为空时结束。算法如下：下：void reverse (Linklist H) LNode *p, *q; p=H-next; /*p指向第一个数据结点指向第一个数据结点*/ H-next=NULL; /*将原链表置为空表将原链表置为空表H*/ while (p) q=p; p=p-next; q-next=H-next; /*将当前结点插到头结点的后面将当前结点插到头结点的后面*/ H-next=q; 例例2.5 有顺序表有顺序表A和和B，其元素均按从小到大的升序

20、，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表排列，编写一个算法将它们合并成一个顺序表C，要，要求求C的元素也是从小到大的升序排列。的元素也是从小到大的升序排列。 算法思路：依次扫描通过算法思路：依次扫描通过A和和B的元素，比较当前的元素，比较当前的元素的值，将较小值的元素赋给的元素的值，将较小值的元素赋给C，如此直到一个，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给分赋给C即可。即可。C的容量要能够容纳的容量要能够容纳A、B两个线性表两个线性表相加的长度。相加的长度。 算法如下：算法如下：merge(int

21、 a, int m, int b,int n,int c) int i,j,k; i=0;j=0;k=0; while ( i=m-1 & j=n-1 ) if (aibj) ck+=ai+; else ck+=bj+;while (i=m-1 ) c+= ai+;while (jnext;q=B-next;C=A; /*C表的首结点表的首结点*/C-next=NULL;free (B);while(p&q)if(p-datadata)s=p;p=p-next;elses=q;q=q-next; /*从原从原AB表上摘出较小者表上摘出较小者*/s-next=c-next; /*插入插入C表的头

22、部表的头部*/c-next=s; if(p=NULL) p=q;while (p) /*插入插入C表的头部表的头部*/s=p;p=p-next;s-next=c-next; /*插入插入C表的头部表的头部*/c-next=s;除了可以使用C提供的标准类型名和、共用体、指针、枚举类型外，还可以 typedef 定义新的类型名来代替已有的类型名。typedef int INTEGER；typedef float REAL；int i,j；float a;b；等价于INTEGER i,j;REAL a,b; 声明结构体类型：typedef structint month; int day; int year;DATE;可以定义变量:DA