数据结构第二章.doc

第二章 线性表（Linear List）
| 逻辑结构及其基本操作
| 线性表的顺序存储结构
| 线性表的链式存储结构
| 静态链表
| 应用实例

逻辑结构及其基本操作
| 定义：由n个相同类型数据元素a0 a1…ai…an-1 构成的有限序列。
z 说明：ai是抽去现实意义的抽象表示符号。
typedef int DataType;
typedef char DataType;
typedef struct student DataType;
| 基本操作
初始化：Initiate（L)
求长度：ListLength（L）
前插：ListInsert（L,i,x）
删除：ListDelete（L,i,x）
取元素：ListGet(L,i,x)
注：L为线性表
| 顺序存储结构：用一组地址连续的存储单元依次存储线性表的各个元素。

线性表的定义：
#define MaxSize 1024 //假定线性表的最大长度为1024
typedef int DataType; /*定义数据类型*/

typedef struct
{
DataType List[MaxSize];
int size;
}SeqList;
M注意：这样定义不能对size进行初始化，因此一定要在使用前进行初始化赋值。

| 线性表元素的插入

| 线性表元素的删除

小结：很显然，顺序表的插入和删除一个元素时，其时间主要花费在移动数据元素上。
算法的代价分析：
插入 删除
平均移动结点的次数： 同理可得：
E= E=

假设结点插入的概率相同，即　

Pi=

把Pi代入E的计算公式中，则有：
E=

所以，在顺序表上插入和删除一个元素的时间复杂度是：Ｏ（n）。
对于取元素和定位操作可以直接实现。

| 例：利用线性表的基本运算实现清除L中多余的重复节点。

| 顺序表的优点：
简单、常用。无须为表示节点间的逻辑关系而增加额外的存储空间
可以方便的随机存取表中的任一节点
| 顺序表的缺点
插入和删除运算时，需移动大量数据，运行速度受到影响。
需预先确定数据元素最大个数。

| 线性表的链式存储
| 链表（Linked List）：一种物理存储上非连续、非顺序的线性存储结构，数据元素间的逻辑顺序是通过链表中的指针链接次序实现的。
| 节点构成：数据域＋指针域

| 单链表结点的定义
typedef struct Node
{ DataType data;
struct Node *next;
} SLNode;

| 单链表的结点结构的定义
（１）一般形式的单链表存储结构的结点定义方法
typedef struct Node
{
DataType Data;
struct Node *Next
} SLNode;

|
typedef int datatype;
typedef struct {
char name[10];
int age;
} DataType;

节点存储空间的申请
p＝(SLNode *)malloc(sizeof(SLNode));
节点存储空间的释放
free(p);

| 单链表中的基本操作——初始化
int ListInitiate(SLNode * *head)
{
if ((*head = (SLNode *)malloc(sizeof(SLNode)))
== NULL)
return 0;
用头指针建立了一个空表。

(*head) -> Next = NULL;
return 1;
}

| 单链表中的基本操作——前插
在单链表h中的第i个元素之前插入一个数据元素x。

int ListInsert (SLNode *head, int i , DataType x)
{
SLNode *p,*q;
int j;
p = h;
j = 0;
while( p != NULL && j < i-1) /*寻找第i个结点*/
{
p = p -> Next;
j + +;
}
if (j != i-1)
{
printf(“\n插入位置不合理！ ”);
return 0;
}
/*申请一空结点*/
if ((q =(SLNode *)malloc(sizeof(SLNode))) = =NULL) return 0;
q -> Data = x; /*给数据赋值*/
q -> Next = p -> Next;
p -> Next = s;
return 1;
}

| 单链表中的基本操作——删除
在单链表h中删除第i个结点。

| 单链表中的基本操作——取元素
在单链表h中寻找第i个结点，并返回该结点的数据元素。

| 单链表中的操作举例
假设已有单链表la，复制一个具有同样结构的单链表lb。

| 循环单链表
循环单链表的定义：循环单链表是单链表的另一种形式,其特点是链表中最后一个结点的指针不再是空的,而是指向头结点或第一个结点,整个链表形成一个环。从表中任一个结点出发，都可找到表中其它结点。

| 双向链表
双向链表的定义：具有两个方向的指针域的链表叫双向链表，这两个指针域分别指向当前结点的前驱和后继。单链表只能从表头开始沿一个方向查找；而双向链表可以从任一个结点出发，向前或向后查找 。

| 双向链表结点的结构定义
typedef struct Node
{
DataType Data；
struct Node * Prior，* Next；
}DLNode；

双向链表前插操作的C语言算法 P-49

| 双链表中的基本操作——删除

双向链表删除操作的C语言算法 p-50

| 链式存储结构的特点
链式存储结构的优点
(1) 结点空间的动态申请和动态释放;
(2) 数据元素的逻辑次序用结点的指针域指示，插入、删除等操作中不需要大量移动数据。
链式存储结构的缺点
(1) 每个结点中的指针域需额外占用存储空间；
(2)链式存储结构是一种非随机存储结构。

| 应用实例
| 以单链表存储结构实现线性表的就地逆转

| 一元多项式的相加（合并同类项）