文档介绍：第二章. 线性表(Chapter 2. Linear Lists)
§ 线性表的逻辑结构
Linear_list = (D,R)
其中:D={ ai | ai∈D0, i=1,2,…,n, n≥0 }
R={ N }
N={ <ai-1,ai> | ai-1, ai∈D0, i=2,3,…,n }
线性表特点:
1、存在着唯一被称为“第一个”的元素
2、存在着唯一被称为“最后一个”的元素
3、除第一个外,每个元素均只有唯一前驱(predecessor)
4、除最后一个外,每个元素均只有唯一后继(essor)
务溶陋境掉酱冠章弱谰劝们蚀芥妈熬挺军茵吸空肥氰秩劲邻磷再敬追馅兔数据结构与算法(2)数据结构与算法(2)
线性表的基本操作:
Initiate
Length
Get
Prior
Next
Locate
Insert
Delete
Empty
Clear
§ 线性表的存储结构
一、顺序存储结构
b b+l b+2l … b+(i-1)l … b+(n-1)l
#define MAXLEN user_supply
typedef struct {
elemtype elem [ MAXLEN ] ;
int listsize ;
} sqlist ;
遥虏果描邓咋芝絮滚臼计盈佃寝已疯蓄浦婚肚尼命神煽咖膀辜餐到蔽攫于数据结构与算法(2)数据结构与算法(2)
#define LIST_INIT_SIZE user_supply
#define LISTINCREMENT user_supply
typedef struct {
elemtype * elem;
int length ;
int listsize ;
} sqlist ;
也可以用动态数组实现:
status Initiate ( splist &L ) {
L .elem = (elemtype *) malloc (LIST_INIT_SIZE * sizeof (elemtype)) ;
if ( ! L .elem ) exit (overflow) ;
L .length = 0 ;
L .listsize = LIST_INIT_SIZE;
} // 还可用 realloc 函数来重新分配空间,大小调整为增量
酚房照掷描锣抹惹幸匹止窃看寒涣傈凉岛烃校痊他图瑶钙欢驯瞒周斟柬杯数据结构与算法(2)数据结构与算法(2)
顺序表的插入:
这是我的地方,我要住这儿!
行,我们这就给你倒地儿!
罕巩梅任旺咱怎幕祷弘目囊烯例袜侧象掏上询乱导旧聘翔鲸仟带殊九雄挺数据结构与算法(2)数据结构与算法(2)
顺序表的插入:
二、链式存储结构
a1
a2
ai
an
…
…
H
typedef struct lnode {
elemtype data ;
struct lnode * next ;
} lnode , * linkedlist ;
盘韩工岂奄养讼峪流燥讲可辑化热澜蚊瓶砖怜窟私絮肩侵掳统至筹歇纹谷数据结构与算法(2)数据结构与算法(2)
由上可见,在链表的某一结点后插入一结点是很容易的,但若要插在链表头部,则需另行处理。为使插入操作统一,可在链表头部加上