《C语言程序设计与数据结构》课件第13章.ppt

C语言程序设计与数据结构 第十三章 线 性 表 本章学习内容 线性表的定义 线性表的基本运算 线性表的基本操作 线性表的链式存储 13.1 线性表及其基本运算 13.1.1 线性表的定义 线性表是最常用和最简单的一种数据结构。特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。 英文字母表（A，B，…，Z）是线性表，表中每个字母是一个数据元素（结点）。 扑克牌的点数（2，3，…，10，J，Q，K，A）也是一个线性表，其中数据元素是每张牌的点数和花色 。 线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) 其中n为表长， n＝0 时称为空表。 特点： 表中相邻元素之间存在着顺序关系。将 ai-1 称为 ai 的直接前趋，ai+1 称为 ai 的直接后继。就是说：对于ai，当 i=2，...，n 时，有且仅有一个直接前趋 ai-1.，当i=1，2，...，n-1 时，有且仅有一个直接后继 ai+1，而 a1 是表中第一个元素，它没有前趋，an 是最后一个元素，无后继。 13.1.2 线性表的基本运算 (1) InitList(L) L是没有初始化的线性表, 为L开辟空间并将L置为空表。 (2) DestroyList(L) 线性表L已存在, 将L的存储空间释放。 (3) ClearList(L) 线性表L已存在, 将表L置为空表。 (4) emptyList(L) 线性表L已存在, 如果L为空表则返回真，否则返回假。 (5) ListLength(L) 线性表L已存在, 如果L为空表则返回0，否则返回表中的元素个数。 (6) Locate(L，e) 表L已存在，e为线性表中元素或与之同型元素, 如果L中存在元素e，则返回元素e所在位置，如果L中不存在元素e，则返回0。 (7) Getelem(L，i) 表L存在，i为整数,i值合法，即1iListLength(L)。返回线性表L中第i个元素的值，否则提示出错。 (8) InsertList(L，i，e) 表L已存在，e的数据类型同线性表中数据元素，且1iListLength(L)+l，在L中第i个位置前插入新的数据元素e，现行表L的长度加1。 (9) DeleteList(L，i，e) 表L已存在且非空，i为整数,如果1≤i≤ListLength(L)，删除线性表中的第i个数据元素，并用e返回其值，函数值返回真，线性表的长度减1；否则函值返回假。 13.2 线性表的顺序表示及基本操作 13.2.1 线性表的顺序表示 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表 。 13.2.2 顺序表的基本操作实现 1.初始化 Status InitList_sq(SqList L) { L.elem = (ElemType *)malloc(INIT_SIZE*sizeof(ElemType)); //分配空间 if (!L.elem) exit(OVERFLOW); //若分配空间不成功，返回OVERFLOW L.length = 0; //将当前线性表长度置0 L.listsize = INIT_SIZE; return OK; //成功返回OK }// InitList_sq 2.插入运算 在线性表L中第i个数据元素之前插入数据元素e， 插入后使原表长为n的表： (a1，a2，... ，ai-1，ai，ai+1，... ，an) 成为表长为 n+1 表： (a1，a2，...，ai-1，e，ai，ai+1，...，an　) 其中 i 的取值范围为1= i = n+1 。 用类C语言实现顺序表的插入： Status ListInsert_sq(SqList L, int i, ElemType x) { if (i 1 || i L.length+1) //判断输入是否合法 return ERROR; if (L.length = L.Listsize) { //判断空间是否足够 newbase = (ElemType *)realloc(L.elem, (L.listsize+LI