中国地质大学（武汉）：《数据结构和VC编程》课程教学资源（课件讲稿）第二章 线性表

第二章线性表 B=(A,R) A={a1ya2y…an}R={a-api=2,3,…,n} 2.1线性表的基本概念 2.2顺序存储的线性表 2.3链式存储的线性表 PT PRESS 退出

第二章 线性表 B=（A，R） A={ a1，a2，……an } R={|i=2,3,…..,n} 2.1线性表的基本概念 2.2顺序存储的线性表 2.3链式存储的线性表 退出

对于一个线性表，经常遇到的一些操作是： 1、访问表中任意一个数据元素； 2、删除表中任意一个数据元素； 3、在表中第i(1<=i<=n-1)个数据元素之前或之后插入 一个新数据元素； 4、根据某种性质或特征，查找满足要求的数据元素； 5、对表中数据元素进行重新排列： 6、一些更复杂的操作，例如表的合并，拆分 等。 PT PRESS 然东续下一配 n

对于一个线性表，经常遇到的一些操作是： 1、访问表中任意一个数据元素； 2、删除表中任意一个数据元素； 3、在表中第i（1<=i <=n-1）个数据元素之前或之后插入 一个新数据元素； 4、根据某种性质或特征，查找满足要求的数据元素； 5、对表中数据元素进行重新排列； 6、一些更复杂的操作，例如表的合并，拆分 等

1.2顺序存储的线性表 顺序存储的线性表的定义如下： #define MAXSIZE 100 /*用宏定义一个 线性表的最大长度*/ typedef struct elemtype elemMAXSIZE]; /六定义一个存放数据元素的一维数组，元素类型 elemtype根据实际需要确定*/ int len; /*线性表的当前长度*/ SQLIST; PT PRESS 续不一

1. 2顺序存储的线性表 顺序存储的线性表的定义如下： #define MAXSIZE 100 /*用宏定义一个 线性表的最大长度*/ typedef struct {elemtype elem[MAXSIZE]; /*定义一个存放数据元素的一维数组，元素类型 elemtype根据实际需要确定*/ int len; /*线性表的当前长度*/ }SQLIST;

1、建立一个顺序存储的线性表 void creatsglist(SQLIST *L) fint i; printf(请输入线性表元素个数n”); scanf("%d",&(*L).len); printf(请输入%d个元素n”,(L).len); for (i=0;i<(*L).len;i++) scanf("%d",&(*L).elem i].key); /~这里略去了对数据元素中其他数据项的输入，仅输 入其主关键字。*/ PT PRESS

1、建立一个顺序存储的线性表 void creatsqlist(SQLIST *L) {int i; printf(“请输入线性表元素个数\n”); scanf("%d",&(*L).len); printf(“请输入%d个元素\n”,(*L).len); for (i=0;i<(*L).len;i++) scanf("%d",&(*L).elem[i].key); /*这里略去了对数据元素中其他数据项的输入，仅输 入其主关键字。*/

2、访问表中第个元素(0<=i(*L).len) 3、求第个元素的前驱和后继 前驱为：L.elemi-1],后继为：L.elem[i+l。 若=0则没有前驱，若=(L).len-1,则没有后 继。 4、查找表中的一个数据元素 算法2.1 如书第14页所示 PT PRESS 按续不一

2、访问表中第i个元素(0<=i<(*L).len)) 3、求第i个元素的前驱和后继 前驱为：L.elem[i-1]，后继为：L.elem[i+1]。 若i=0则没有前驱，若i=(*L).len-1，则没有后 继。 4、查找表中的一个数据元素 算法2.1 如书第14页所示

5、从线性表中删除第i个元素 算法2.2 如书第14页所示 6、在线性表的第i个元素之后插入一个新元素 算法2.3 如书第15页所示 PT PRESS 然东续了一列 n

5、从线性表中删除第i个元素 算法 2．2 如书第14页所示 6、在线性表的第i个元素之后插入一个新元素 算法 2．3 如书第15页所示

I例1]线性表中的元素以第一个元素的key为界 划分成两部分。 算法2.4 如书第15页所示 PT PRESS 然东续下一配 n

[例1] 线性表中的元素以第一个元素的key为界 划分成两部分。 算法 2．4 如书第15页所示

例1、两个有序表的归并 算法2.5 如书第16页所示 PT PRESS 然东续下一配 n

例1、两个有序表的归并 算法 2．5 如书第16页所示

2.3链式存储的线性表 2.3.1单链表 head a … A (a)不带头结点的单链表 红工工工 (b)带头结点的单链表 图2-1 PT PRESS 续不一 n

2.3链式存储的线性表 2．3．1单链表 图 2-1

单链表的存储结构，可用C语言的结构指针来定义： typedef struct node {elemtype data; /数据元素的类型，可 以替换为任何实际所需类型*/ struct node *next; /必指示后继结点地址 的指针*/ NODE,*NODEPTR; /六定义结点类型 和指向结点的指针类型*/ #define LEN sizeof(NODE) PT PRESS 续下一

单链表的存储结构，可用C语言的结构指针来定义： typedef struct node {elemtype data; /*数据元素的类型， 可 以替换为任何实际所需类型*/ struct node *next; /*指示后继结点地址 的指针*/ }NODE， *NODEPTR; /*定义结点类型 和指向结点的指针类型*/ #define LEN sizeof(NODE)