数据结构-严蔚敏版第二章笔记

前言

准备考研了，我们学校使用的教材不是这一本，大概整理一下。共勉

正文

第二章

线性结构的特点：在数据元素的非空有限集合中

1. 存在唯一的一个被称为“第一个”的数据元素
2. 存在唯一的一个被称为“最后一个”的数据元素
3. 除了第一个之外，集合中的每个数据元均只有一个前驱
4. 除了最后一个之外，集合中的每一个元素均只有一个后继

2.1线性表的类型定义

线性表是最常用 且最简单的一种数据结构，即一个线性表是n个数据元素的有限序列。例如26个英文字母表：

(a,b,c,…z)

在稍复杂的线性表中，一个数据元素可以由若干的数据项组成。此时，数据元素常常称为记录，含有大量记录的线性表又称为文件。
例如一个学校的学生健康情况登记表如下图

• 例2-1
  假设利用两个线性表LA和LB分别表示两个集合A和B，现在求一个新的集合A=A U B（交集）

void union(List &La, List &Lb){
	//将所有在线性表Lb但是不在La中的数据元素插入到La中
	//求线性表的长度
	La_len = ListLength(La);
	Lb_len = ListLength(Lb);
	for(i = 1; i <= Lb_len; i  ){
		GetElem(Lb, i, e);//取Lb中的第i个数据元素赋值给e
		//La中不存在和e相同的数据元素，则插入
		if(!LocateElem(La, e, equal))
			ListInsert(La,   La_len, e);
	}
}

• 例2-2
  已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中数据元素仍按值非递减有序排列。例如

LA = (1,3,4,5)
LB = (2,7)
LC = (1,2,3,4,5,7)

void MergeList(List La, List Lb, List &Lc){
	//已知线性表La和Lb中的数据元素按值非递减排列
	//归并Lb和Lb得到新的线性表Lc，Lc的数据元素也按值费递减排序
	InitList(Lc);
	i = j =1;
	k = 0;
	La_len = ListLength(La);
	Lb_len = ListLength(Lb);
	while((i<=La_len)&&(j<=Lb_len)){
		GetElem(La, i, ai);
		GetElem(La, j, bj);
		if(ai<=bj){
			ListInsert(Lc,   k, ai);
			  i;
		}else{
			ListInsert(Lc,   k, bj);
			  j;
		}
	}
	while(i<=La_len){
		GetElem(La, i  , ai);
		ListInsert(Lc,   k, ai);
	}
	while(j<=Lb_len){
		GetElem(La, j  , bj);
		ListInsert(Lc,   k, bj);
	}
}

2.2线性表的顺序表示和实现

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据单元。线性表的这种机内表示称为线性表的顺序存储结构或者顺序映像。称这种存储结构的线性表称为顺序表。只要确定了存储线性表的起始位置，线性表中的任意一个数据单元都可随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构。

图中的l代表每一个元素需要占用的l个存储单元。

后言

来源：http://www./content-4-67301.html