数据结构(C语言描述)——线性表

type p=^integer; var p1:p; p1
34F2 地址 被释放，变 量P与地址 34F2没有关 系
p1^
200 34F2
34F2
new（p1） ——向计算机申请内存地址 p1^:=200 ——给p1指向的单元赋值 dispose(p1) ——释放存储单元
链式结构——什么是指针
Type p=^integer; arr=array[1..4] of char; arrp = ^arr; Var p1:p; p2:arrp;
线性结构 数据的逻辑结构 数 据 结 构 树形结构 图形结构 数据的存储结构 顺序存储
链式存储
数据结构的基本运算 :查找、插入、删除等
三、线性结构——线性表
1、线性表的概念
线性表是由n（n≥0）个具有相同特性数据元素(结点)
a1，a2，…，an组成的有限序列。
线性表的长度：所含元素的个数,用n表示，n>=０。
在我们生活中有哪些属于线性表的例子,列举几个。 1、英文字母表（A，B，…，Z）是线性表， 表中每个字母是一个数据元素（结点）
2、学生成绩表中，每个学生及其成绩是一
个数据元素，其中数据元素由学号、姓名、
各科成绩及平均成绩等数据项组成。
4、线性表的顺序存储
顺序存储是线性表的一种最 简单的存储结构，存储方式是： 在内存中为线性表开辟一块连 续的存储空间。用数组来存放 每一个节点。
[例4-2] 法雷序列
[问题描述]对任意给定的一个自然数n（n<=100），将 分母小于等于n的不可约的真分数按上升次序排序，并 且在第一个分数前加0/1，而在最后一个分数后加1/1, 这个序列称为n级的法雷序列。 当n=8时序列为：0/1, 1/8, 1/7, 1/6,1/5, 1/4,2/7,1/3,3/8, 2/5,3/7,1/2,4/7,3/5,5/8,2/3,5/7,3/4, 4/5,5/6,6/7,7/8, 1/1 。 编程求出n级的法雷序列，每行输出10个分数。

实现逻辑上相邻—物理地址相邻 实现逻辑上相邻— 实现随机存取 实现随机存取
实现：可用C 实现：可用C语言的一维数组实现
6
V数组下标 0 1
内存 a1 a2
元素序号 1 2
typedef int DATATYPE; #define M 1000 DATATYPE data[M]; 例 typedef struct card { int num; char name[20]; char author[10]; char publisher[30]; float price; }DATATYPE; DATATYPE library[M];
4
{加工型操作 加工型操作} 加工型操作
ClearList( &L ) 初始条件：线性表 L 已存在。 操作结果：将 L 重置为空表。 PutElem( &L, i, &e ) 初始条件：线性表L已存在，1≤i≤LengthList(L)。 操作结果：L 中第 i 个元素赋值同 e 的值 ListInsert( &L, i, e ) 初始条件：线性表 L 已存在，1≤i≤LengthList(L)+1。 操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。 ListDelete( &L, i, &e ) 初始条件：线性表 L 已存在且非空，1≤i≤LengthList(L)。 操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。 }ADT LIST
3
PriorElem( PriorElem L, cur_e, &pre_e ) 初始条件：线性表 L 已存在。 操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回 它的前驱，否则操作失败，pre_e 无定义。 NextElem( NextElem L, cur_e, &next_e ) 初始条件：线性表 L 已存在。 操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返 回它的后继，否则操作失败，next_e 无定义。 GetElem( GetElem L, i, &e ) 初始条件：线性表 L 已存在，1≤i≤LengthList(L)。 操作结果：用 e 返回 L 中第 i 个元素的值。 LocateElem( LocateElem L, e, compare( ) ) 初始条件：线性表 L 已存在，compare( ) 是元素判定函数。 操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元 素的位序。若这样的元素不存在，则返回值为0。 ListTraverse(L, visit( )) ListTraverse 初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。 操作结果：依次对 L 的每个元素调用函数 visit( )。 一旦 visit( ) 失败，则操作失败。

(9) Status NextElem_Sq(SqList L, ElemType cur_e, ElemaType &next_e)
//若cur_e是线性表L的元素且不是最后一个，返回它的后继 { for (i=0; i<L.length-1; i++) if (cur_e==L.elem[i]) { next_e=L.elem[i+1]; return OK; } return ERROR; }//NextElem_Sq O(n)
抽象数据类型 唯 一 数据的逻辑结构 确 操作的定义 定
集合 *
线性表
特殊线性表 扩展线性表
线性结构
树形结构 图形结构
灵 活 数据的存储结构 操作的实现 设 计
顺序存储 链式存储 散列（哈希）存储
数据的基本操作：针对结构、针对元素、针对状态
数据结构---第二章 线性表 1
第二章 线性表
2.1 2.2 2.3 2.4
数据结构---第二章 线性表
9
2.2 线性表的顺序存储结构(顺序表)
起始地址为b、最多可容纳maxlen个元素的线性表
下标 存储地址
0
1
b b+c
b+(i-1)c
a1 a2
ai
c个存储单元
i-1
LOC(ai)=LOC(a1)+(i-1)c LOC(ai)=LOC(ai-1)+c
n-1
b+(n-1)c
n-1
int LocateElem_Sq(SqList L, ElemType e, (7) Status (*compare)(ElemType,ElemType) ) //在线性表L中查找第1个值与e满足 //compare（）的元素的位序 { for (i=0; i<L.length; i++) L.elem[i]==e if ( (*compare)(L.elem[i],e) ) return i+1; return 0 ; //作为未找到的特殊标记 } // LocateElem_Sq O(n) P25-2.6

27
线性表的顺序存储结构适用于数据 元素不经常变动或只需在顺序存取设备 上做成批处理的场合。为了克服线性表 顺序存储结构的缺点，可采用线性表的 链式存储结构。
28
2.3 线性表的链式存储结构
线性表的链式存储表示 基本操作在单链表上的实现 循环链表 双向链表 线性表链式存储结构小结
2.3.1 线性表的链式存储表示 29
2.1.1 线性表的定义
6
一个线性表（linear_list）是 n（n≥0）个具有相同属性的数 据元素的有限序列，其中各元素有着依次相邻的逻辑关系。
线性表中数据元素的个数 n 称为线性表的长度。当 n = 0 时 该线性表称为空表。当 n > 0 时该线性表可以记为：
（a1，a2，a3，…，ai，…，an）
数据域 指针域
结点 data next
31
(2) 线性表的单链表存储结构
通过每个结点的指针域将线性表中 n 个结点按其逻辑顺序链 接在一起的结点序列称为链表，即为线性表 ( a1, a2, a3, …, ai, …, an ) 的链式存储结构。如果线性链表中的每个结点只有一个指针域， 则链表又称为线性链表或单链表 (linked list)。
17
(2) 算法编写
#define OK 1
#define ERROR 0
Int InsList ( SeqList *L, int i, ElemType e ) /*在顺序线性表 L 中第 i 个位置插入新的元素 e。*/ /* i 的合法值为 1≤i ≤L->last+2*/ {
int k; if ( i < 1) ||( i > L->last+2)) /*首先判断插入位置是否合法*/ { printf(“插入位置i值不合法”）；