《数据结构 第四版 高职计算机应用技术专业 安训国 课件第二章 线性表》由会员分享，可在线阅读，更多相关《数据结构 第四版 高职计算机应用技术专业 安训国 课件第二章 线性表（42页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表,第2章 线性表,学习目的要求:,线性表的定义和线性表的特征。 线性表的顺序存储结构及其算法的实现。 线性链表的描述及其算法的实现。 循环链表和双向循环链表的描述。 数组的顺序存储和矩阵的压缩存储的描述。,2.1 线性表的基本概念,2.2 线性表的顺序存储结构及其算法,2.3 线性表的链式存储结构及其运算,2.4 算法应用举例,2.5 数组,第2章 线性表,2.1.1 线性表的定义,2.1 线性表的基本概念,线性表（linear list）是由 n个数据元素组成的有限序列。,线性表可以用一个标识符来命名，如果用A来表示线性表，则: A=（a1 ，a2 ，ai ，an ）,线性表是
2、一种非常典型的线性结构，用二元组可以表示成: S=（D，R） D= a1，a2 ，ai ，an R=，,2.1.2 线性表的基本操作,（1）InitList（List）:初始化操作，建立一个空的线性表List; （2）ListLength（List）:求线性表的长度; （3）GetElement（List， i ）:取线性表中的第 i 个元素（1 i n，n为线性表长度）; （4）PriorElement（List， x ）:若 x 不是第一个数据元素，则取 x 的直接前驱; （5）NextElement（List， x ）:若 x 不是最后一个元素，则取 x 的直接后继; （6）Locate
3、Element（List， x ）:若 x 存在于表中，则取得 x 的位置（位序）; （7）ListInsert（List， i ， x ）:在线性表第 i 个元素之前插入一个数据元素x; （8）ListDelete（List， i ）:删除线性表中第 i 个元素（1 i n，n为线性表长度）。,2.1 线性表的基本概念,2.2 线性表的顺序存储结构及其算法,2.2.1 线性表的顺序存储结构,线性表的顺序存储结构简称为顺序表（Sequential List）。,顺序存储结构的特点是:在线性表中逻辑关系相邻的数据元素，在计算机的内存中物理位置也是相邻的。,线性表中第i个元素ai的存储位置为: L
4、OC（ai ）=LOC（a1）+（i-1）L,2.2.2 顺序表的运算,1. 插入运算,插入运算是指在具有n个元素的线性表的第i（1in）个元素之前插入一个新元素x。,2.2 线性表的顺序存储结构及其算法,int insertsqlist(int i,elementtype x,SqList *sql) /*在顺序表(*sql)的第i个元素之前插入一个新元素x*/ int j; if(isql-len) /*i值非法，返回值为0*/ return(0); else for(j=sql-len;j=i;j-) sql-sj+1=sql-sj; /*向后移动数据，腾出要插入的空位*/ sql-sj
5、+1=x; /*修正插入位置为j+1*/ (sql-len)+; /*表长加1*/ return(1); /*插入成功，返回值为1*/ ,2.2 线性表的顺序存储结构及其算法,2. 删除运算,删除运算是指从具有n个元素的线性表中，删除其中的第i（1in）个元素，使表的长度减1。,2.2 线性表的顺序存储结构及其算法,int delsqlist(int i,SqList *sql) /*删除顺序表(*sql)的第i个元素*/ int j; if(isql-len) /*i值非法，返回值为0*/ return(0); else for(j=i+1;jlen;j+) sql-sj-1=sql-sj;
6、 /*向前移动数据，覆盖前一数据*/ (sql-len)-; /*表长度减1*/ return(1); /*删除成功，返回值为1*/ ,2.2 线性表的顺序存储结构及其算法,2.3.1 线性表的链式存储结构,为了表示出每个元素与其直接后继元素之间的关系，除了存储元素本身的信息外，还需存储一个指示其直接后继的存储位置信息。,typedef struct node int data; struct node *next; NODE;,2.3 线性表的链式存储结构及其运算,线性链表是通过结点指针域中的指针表示各结点之间的线性关系的。,线性表的每个结点都有一个链接指针，所以不要求链表中的结点必须按照结
7、点先后次序存储在一个地址连续的存储区中。,在链表中插入或删除数据元素比在顺序表中要容易得多，但是链表结构需要的存储空间较大。,2.3 线性表的链式存储结构及其运算,2.3.2 单链表的运算,若线性链表的每个结点只含有一个指针域，则称这样的线性链表为单链表。,1. 建立带表头结点的单链表,建立链表时，首先要建立表头结点，此时为空链表。然后将新的结点逐一插入到链表中，其过程如下: （1） 申请存储单元，用C语言的动态分配库函数malloc得到。 （2） 读入新结点的数据，新结点的指针域为空。 （3） 把新结点链接到链表上去（有前插和后插两种方式）。 重复以上步骤，直到将所有结点都链接到链表上为止。
8、,2.3 线性表的链式存储结构及其运算,NODE *create() /*此函数采用后插入方式建立单链表*/ NODE *head,*q,*p; /*定义指针变量*/ char ch; int a; head=(NODE*)malloc(sizeof(NODE); /*申请新的存储空间，建立表头结点*/ q=head; ch=*; printf(“nInput the list :“);,2.3 线性表的链式存储结构及其运算,(Continue ),while(ch!=?) /*“ch“为是否建立新结点的标志，若“ch“为“?“则输入结束*/ scanf(“%d“, /*返回表头指针head*
9、/ ,2.3 线性表的链式存储结构及其运算,2. 单链表中结点的查找,单链表有两种查找方法，即按序号查找和按给定值查找。,在单链表中，即使知道了要查找的结点的序号，也只能从头指针开始查找。与顺序表不一样，单链表不能实现随机查找。,2.3 线性表的链式存储结构及其运算,NODE *locate(NODE *head,int x) /*在已知链表中查找给定的值x*/ NODE *p; p=head-next; while(p!=NULL) ,（1） 按值查找,2.3 线性表的链式存储结构及其运算,按值查找，就是在单链表中查找是否存在数据域值为给定的值 （如整数x） 的结点。,NODE *find(
10、NODE *head,int i) /*在已知链表中查找给定的值x*/ int j=1; NODE *p; p=head-next; while(p!=NULL) ,（2） 按序号查找,2.3 线性表的链式存储结构及其运算,在单链表中查找第 i 个位置上的结点，若找到，则返回它的地址，否则返回NULL。,3. 单链表上的插入运算,在顺序表中，插入运算时，将会有大量元素向后移动。而在单链表中，插入一个结点不需要移动元素，只需要修改指针即可。,若将x插入到a1 和a2 之间， 其过程如下: （1） 建立一个新结点 q，将x值赋给q -data。 （2） 修改有关结点的指针域。,2.3 线性表的链式
11、存储结构及其运算,void insert(NODE *p,int x) /*在链表的p结点后插入给定元素x*/ NODE *q; q=(NODE*)malloc(sizeof(NODE); /*申请新的存储空间*/ q-data=x; q-next=p-next; /*实现图的*/ p-next=q; /*实现图的，将新结点q链接到p结点之后*/ ,2.3 线性表的链式存储结构及其运算,4. 单链表上的删除运算,删除单向链表中的结点x，并由系统收回其占用的存储空间，其过程如下: （1） 设定两个指针p和q，p指针指向被删除结点，q为跟踪指针，指向被删除结点的直接前驱结点。 （2） p从表头指针
12、 head 指向的第一个结点开始依次向后搜索。当p data 等于x时，被删除结点找到。 （3）修改p的前驱结点q的指针域。使p结点被删除，然后释放存储空间。,2.3 线性表的链式存储结构及其运算,void delete(NODE *head,int x) /*删除链表中的给定元素x*/ NODE *p,*q; q=head; p=q-next; while(p!=NULL) /*删除x结点，释放x结点空间*/ ,2.3 线性表的链式存储结构及其运算,5. 输出单链表,若要将单链表按其逻辑顺序输出，就必须从头到尾访问单链表中的每一个结点。,void print(NODE *head) /*输出
13、单向链表各元素*/ NODE *p; p=head-next; printf(“Output the list:“); while(p!=NULL) printf(“%3d“,p-data); p=p-next; ,2.3 线性表的链式存储结构及其运算,2.3.3 循环链表结构,如果将单链表最后一个结点的指针指向头结点，使链表形成一个环形，此链表就称为循环链表（Circular Link List）。,2.3 线性表的链式存储结构及其运算,2.3.4 双向链表结构,1. 双向链表的基本概念,在循环链表的结点中再增加一个指针域，这个指针直接指向该结点的 直接前驱。这样，链表中一个结点就有了两个指
14、针域，我们把这样的链表称为双向链表。,2.3 线性表的链式存储结构及其运算,如果每条链都构成一个循环链表，则称这样的链表为双向循环链表。,2. 插入运算,在双向链表的p结点之后插入新结点q。,2.3 线性表的链式存储结构及其运算,void insert（DUPNODE *p，DUPNODE *q） /*把q结点插在双向链表的p结点之后*/ q-prior=p; q-next=p-next; （p-next）-prior=q; p-next=q; ,2.3 线性表的链式存储结构及其运算,3. 删除运算,将双向链表中的 p 结点删除。,2.3 线性表的链式存储结构及其运算,void delete
15、（DUPNODE *p） /*在双向链表中删除结点p*/ （p-prior）-next=p-next; （p-next）-prior=p-prior; free （p）; ,2.3 线性表的链式存储结构及其运算,例2.1 有两个线性表A和B，都是循环链表存储结构，两个链表头指针分别为 head1和head2 ，将B链表链接到A链表的后面， 合并成一个链表。,2.4 算法应用举例,例2.2 一元多项式的加法运算。设有两个一元多项式分别为: An（x）=a0+a1x+a2x2+anxn Bm（x）=b0+b1x+b2x2 +bm x m,多项式中每个非零项的系数用一个结点来表示，结点中含有两个数据
16、域和一个指针域，两个数据域分别存放非零项的系数和指数。,typedef struct pnode int coef; /*系数以整型为例*/ int exp; /*指数*/ struct pnode *next; PNODE;,2.4 算法应用举例,设有多项式 A（x）=1+2x+4x3 （1） B（x）=2-2x+3x2 （2）,2.4 算法应用举例,多项式（1）加多项式（2）的和为多项式（3）: R（x）=3+3x2 +4x3 （3）,数组是线性表的推广，也是一种常用的数据结构。,2.5.1 数组的定义,数组是由一组具有相同特性的数据元素组成的。,数据元素在数组中的相对位置是由其下标来确定的。,一旦定义了数组，它的维数和元素数目也就确定了，而且数据元素的下标具有上下界约束关系，并且
