计算机软件基础：11第四章数据结构_线性表.doc

《计算机软件基础》多媒体教程
第十一讲
第四章 数据结构
4.1 基本概念
4.1.0 数据结构的研究内容
※ 数据(对象)的性质
什么样的数据/集合
※ 数据联系
相互之间是什么关系
※ 数据表示
如何在计算机中存储
※ 数据处理
如何对数据进行操作

4.1.1 数据结构的定义
※ 数据结构的定义
设B是一个二元组，记为B=(K,R)。K是数据的有限集合，R是K中各数据的有限关系集合，则称B是数据结构。
其中，K的成员k1, k2, …，又称为数据元素(或数据结点，结点)，记为K={k1, k2, …, kn }。
R的成员r1, r2, …，称为关系，记为R={r1, r2, …, rm| ri= (ks, kt), ks,kt∈K}，表示在结点ks, kt之间存在关系ri。
【例5-1.1】数据结构示例。
0~9可组成集合K，在集合K={0~9}上可存在GT(大于)和LT(小于)两种关系。
定义：B=(K, R), K={0, 1, …, 9}, R={GT, LT},
其中，GT = {(1, 0), (2, 0), (2, 1), …}, LT = {(0, 1), (0, 2), (1, 2), …},
则称B=(K, R)是一种数据结构。
4.1.2 结点定义
设B=(K, R)是一种数据结构，可有以下定义：
※ 结点的存储单元
结点k的存储单元由结点地址ak，数据场dk和指针场pk组成，记为：
k = {ak, dk, pk}
※ 结点的数据场
若结点k的数据场dk有m个分量，即每个结点都有m个不同的数据，则记为：
dk = {dik | i=1, ..., m} = {d1k, d2k, …, dmk}
※ 结点的指针场
若结点k的指针场pk有h个分量，每个指针场分量都对应于R的一个关系rj(j=1, …, h)，则记为：
pk = {pjk | j=1, ..., h} = {p1k, p2k, … , phk}

结点k的存储单元
结点k的数据场
结点k的指针场
假定对应于一种关系rj的指针场pjk，需要指向t(j)个结点，即：
pjk = {pjkk | k=1, …, t(j)} = {pj1k, …, pj t(j)k}，
则pk又可以进一步记为
pk = {p11k, … , p1 t(1)k, p21k, … , p2 t(2)k, … , ph1k, … , ph t(h)k}
从而
k = {ak, d1k, d2k,…,dmk, p11k,…, p1 t(1)k, p21k,…, p2 t(2)k,…, ph1k,…, ph t(h)k}

⊙ 空置的指针场
用φ或NULL表示空置的指针场pik，记为pik=φ或pik=NULL。
※ 结点性质
⊙ 前件和后件
设r = (k, k’)，其中r∈R, (k, k’∈K)，则称k是k’关于关系r的前件，k’是k关于关系r的后件。图中用箭头从k指向k’。
当R中只有一种关系r时，可以省略关系的名称，并直接称k是k’的前件，k’是k的后件。

⊙ 孤立结点
若在K中对于关系r而言，既无前件又无后件的k称为孤立结点。
对于非孤立的结点，定义：
⊙ 始结点
若在K中不存在任何k’，使得成立(k’,k)∈r, 则称k为r的始结点。
⊙ 终结点
若在K中不存在任何k’，使得成立(k,k’)∈r, 则称k为r的终结点。
⊙ 内结点
既非始结点又非终结点的称为r的内结点。

【例4-1.2】结点性质示例
定义B1=(K,R)，其中
K={1, 2, 3, 4, 5, 6, 7}，
R = {N,T}，
N = {(1,2), (1,4), (2,3), (2,6),
(3,7), (6,3), (7,3)}，
T = {(2,6), (4,5), (5,2), (6,7)}。

结
关系
N
关系
T
点
前件
后件
前件
后件
1

2,4

2
1
3,6
5
6
3
2,6,7
7

4
1

5
5

4
2
6
2
3
2
7
7
3
3
6

关系N
关系T
始结点
1
4
终结点
4
7
内结点
2,3,6,7
2,5,6
孤立结点
5
1,3
4.1.3 数据结构的存储方式
假定r是B=(K, R)中的一种关系，实现r的存储方式有以下两种：
※ 顺序存储
若对于任何一对结点(k, k’)都成立ak’ = ak + s(s为存储单元的大小，固定长度)，则称r是用顺序方式存储的, 简称顺序存储。
※ 链接存储
若对于任何一对结点(k, k’)都成立ak’∈pk，则称r是用链接方式存储的，简称链接存储。

例如，在N中各结点的最多后件数大于1，则只能用链接存储。
在T中，各结点的最多后件数不超过1，则既可用顺序存储，也可用链接存储。
【例4-1.3】存储单元的图形表示。
在数据结构B1=(K, R)中，每个结点k的数据场只有一个分量dk。
由于所有结点关于关系N的后件最多有2个，关于关系T的后件均为1个，则k的存储单元为：
k = {ak, dk, (pN1k, pN2k), pT}。
现以链接方式存储关系N，以顺序方式存储关系T， B1=(K, R)的存储单元如图所示（虚设存储单位的地址）。

4.1.4 数据结构的分类
根据结点的相互关系来分类

(1) 纯集合：结点间相互无关系，全部为孤立结点。
(2) 线性：只有一个始结点和一个终结点，各结点的前件和后件数至多一个，无孤立结点。
(3) 树状：只有一个始结点，各结点的前件数至多一个，无孤立结点。
(4) 网状：始结点和终结点的数目任意，各结点的前件和后件数任意，无孤立结点。
4.1.5 基本操作
数据结构的基本操作包括查找，增添，删除和排序。
(1) 查找：根据地址、序号或某个数据场的值来寻找某个结点。
例如，查找结点值为key=6的结点，即查找ki==6，得i=5。

(2) 增添：根据某种关系，在保持数据结构的特点不变情况下，增加结点或结点组。
例如，在已有的数据结构中增添两个结点：

(3) 删除：在保持数据结构的特点不变情况下，删去某些结点或结点组。
例如，在已有的数据结构中删除两个结点：

(4) 排序：按某种方式使各结点有序排列。
例如，使数据结构中的结点按照从小到大排序：

4.1.6 数据结构的学习内容
※ 数据类型：
线性，树状，网状。
※ 存储方式：
顺序存储，链接存储。
※ 基本操作：
查找，增添，删除和排序。
※ 算法实现：
用C语言编程。

《计算机软件基础》多媒体教程
第四章 数据结构
4.2 线性表
线性表(list)，又称并列表，线性并列表，或者有序表。
4.2.1 基本问题
※ 线性表的定义
设B=(K, R), 若K中有n个结点K={k0, …, kn-1}，R中只有一种关系N，即
N={(ki, ki+1) | ki, ki+1∈K, 0 ≤ i ≤ n-1}，
则称B为线性表。
※ 推论
有且仅有一个始结点和一个终结点，其余为内结点
除终结点外，每个结点有且仅有一个后件。
除始结点外，每个结点有且仅有一个前件。
※ 课程约定

⊙ 如果没有特别说明，数据结构中的结点k只有一个数据场分量。
⊙ 假定可以调用一个已设计的出错函数error(), 用于出错处理。
※ 线性表的顺序存储
采用数组实现线性表的顺序存储。
⊙ 存储单元
ki = {aki, dki}
可省略指针场，其中，
aki = i
dki = a[i],
pki = aki+1 = aki + 1 = i + 1
⊙ 数据定义和生成线性表
#define M 1000
short n; /* M>=n */

short a[M]; /* 在a[0]~a[n-1]中分别存放各结点的值dk0~ dkn-1 */
⊙ 生成线性表的程序
scanf("%hd", &n);
if(n > M || n < 1)
error(); /* 结点数超界 */
for(j=0; j<n; j++)
scanf("%hd", &a[j]);
※ 线性表的链接存储
采用链表实现线性表的链接存储。
⊙ 存储单元
ki = {aki, dki, pki}
其中，
pki = aki+1
⊙ 数据定义
#define NODE struct node
NODE
{
short num; /* dki */
NODE *next; /* aki+1 */
};
short n;

⊙ 生成带哨兵的链表
指针Head指向一个空置的结点(哨兵)，首指针为Head->next ，即Head->next为始结点k0的地址ak0，终结点kn-1的指针next指向空(NULL)。
NODE *Head; /* 设置哨兵 */
/* 生成哨兵 */
if((Head = (NODE *)(malloc(sizeof(NODE))) == NULL)
error(); /* 内存分配失败 */
Head->next = NULL;
/* 生成链表 */
createList(Head);

⊙ 链表生成函数
void createList(NODE *head)
{
short n, j, num;
NODE *node;
scanf("%hd", &n);
if(n < 1)
error(); /* 结点数超界 */
for(j=0; j<n; j++)
{

if( (node=(NODE *)(malloc(sizeof(NODE))) == NULL)
error(); /* 内存分配失败 */
scanf("%hd", &num);
node->num = num;
node->next = head->next;
head->next = node;
}
}

4.2.2 查找结点
※ 查找结点的操作
⊙ 按结点值查找
根据结点kj的值dkj查找结点，打印序号j，使得dkj==key。

⊙ 按结点地址查找
根据结点kj的序号j(ak)，查找结点kj，打印结点kj的值dkj。

⊙ 按前件或后件查找
根据结点kj的前件(或后件)k’的值dk’，打印序号j和结点kj的值dkj，使得dk’==key。

※ 顺序存储的查找结点
⊙ 根据结点值查找结点的程序
#include <stdio.h>
#include <stdlib.h>
#define M 1000
void searchNode(short *a, short n, short key)
{
short j;
for (j=0; j<n; j++)
if (a[j]==key)
{
printf("node(%hd) =", j);
printf(" %hd\n", a[j]);
return;
}
error(); /* 查找结点失败 */
}
main()
{
short n, a[M], j, key;
scanf(“%hd”, &n);
if(n > M || n < 1)
error(); /* 结点数超界 */
for(j=0; j<n; j++)
scanf("%hd", &a[j]);
scanf("%hd", &key);
searchNode(a, n, key);
}
⊙ 算法复杂度
查找次数与n成正比，最多为n次，称该算法的时间复杂度为O(n)。
⊙ 根据结点地址查找结点的程序
#include <stdio.h>
#include <stdlib.h>
#define M 1000
void prtNode(a, n, j)
short n, a[ ], j;
{
if(j<0 || j>n-1)
error(); /* 结点地址超界 */
printf(“node(%hd) = %hd\n”, j, a[j]);
}
main()
{
short n, a[M], j;
scanf(“%hd”, &n);
if(n > M || n < 1)
error(); /* 结点数超界 */
for(j=0; j<n; j++)
scanf(“%hd”, &a[j]);
scanf(“%hd”, &j);
prtNode(a, n, j);
}
⊙ 算法复杂度
查找次数与n无关，是一个常数C，称该算法的时间复杂度为O(C)。
※ 链接存储的查找结点
main()
{
NODE *Head, *node;
short key;
/* 生成哨兵 */
if((Head = (NODE *)(malloc(sizeof(NODE))) == NULL)
error(); /*内存分配失败 */
Head->next = NULL;
/* 生成链表 */
createList(Head);
/* 读入key */
scanf("%hd", &key);
/* 查找结点 */
if(node = searchNode(Head, key))
printf("node = %hd\n", node->num);
else
error(); /* 查找结点失败 */
}

⊙ 查找结点函数
NODE* searchNode(NODE *head, short key)
{
NODE *node;
for(node=head->next; node; node=node->next)
if(node->num==key)
return(node);
return(NULL); /* 查找结点失败 */
}
⊙ 算法复杂度
查找次数与n成正比，最多为n次。称该算法的时间复杂度为O(n)。
4.2.3 添加结点
※ 顺序存储的添加结点
⊙ 添加结点的操作
已知结点kj的地址akj，在kj后添加新结点k’，使得dk’=key。

将a[n-1]到a[j+1]向数组尾部移动，腾出添加新结点key的位置，再将新结点key插入。

⊙ 顺序存储添加结点的程序
#include <stdio.h>
#include <stdlib.h>
#define M 1000
void addNode(a, n, j, key)
short a[], j, key;
short *n; /* 添加结点后*n要加1 */
{
short k;
if(j<-1 || j>(*n)-1)
error(); /* 结点地址超界 */
for(k=(*n)-1; k>j; k--)
a[k+1] = a[k]; /* 向后移动 */
a[j+1] = key;
(*n)++;
}
main()
{
short a[M], n, j, key;
scanf(“%hd”, &n);
if(n > M-1 || n < 1)
error(); /* 结点数超界 */
for(j=0; j<n; j++)
scanf(“%hd”, &a[j]);
scanf(“%hd%hd”, &j, &key);
addNode(a, &n, j, key);
}

⊙ 添加结点的算法复杂度
移动次数最多为n次，算法复杂度为O(n)。
※ 链接存储的添加结点
⊙ 添加结点的操作
已知结点k的值dk，在k后添加新结点k’，使得dk’=key。

由key指向待添加结点k’。先查找结点k，由node指向结点k，再在node后面插入结点k’。

⊙ 链接存储添加结点的函数
void addNode(NODE *node, short key)
{
NODE *key;
if (node==NULL)
error(); /* 非法结点 */
key =(NODE*)(malloc(sizeof(NODE)));
if(key == NULL)
error(); /* 内存分配失败 */
key->num = key;
key->next = node->next;
node->next = key;
}
⊙ 链接存储添加结点的算法复杂度
添加结点的操作次数与n无关，是一个常数C，算法复杂度为O(C)。
⊙ 链接存储添加结点的程序
#include <stdio.h>
#include <stdlib.h>
#define NODE struct node
NODE
{
short num;
NODE *next;
};
void createList(NODE *head)
{ ...... } /* 略 */
NODE *searchNode(NODE *head, short key)
{ ...... } /* 略 */
main()
{
short key, nxtkey;
NODE *Head, node;
/* 生成哨兵 */
if( (Head = (NODE *)(malloc(sizeof(NODE))) == NULL)
error(); /* 内存分配失败 */
Head->next = NULL;
/* 生成链表 */
createList(Head);
/* 读入key, nxtkey */
scanf("%hd%hd", &key, &nxtkey);
/* 查找结点 */
if(!(node = searchNode(Head, key))
error(); /* 查找结点失败 */
/* 添加结点 */
addNode(node, nxtkey);
}

4.2.4 删除结点
※ 顺序存储的删除结点
⊙ 删除结点的操作
已知结点kj的地址akj，删除kj。

将a[j+1]到a[n-1]向数组前部移动，待删结点a[j](kj)被覆盖。

⊙ 顺序存储删除结点的程序
#include <stdio.h>
#include <stdlib.h>
#define M 1000
void deleteNode(a, n, j)
short a[], j;
short *n; /* 删除结点后*n要减1 */
{
short k;
if(j<0 || j>(*n)-1)
error(); /* 结点地址超界 */
for(k=j+1; k<(*n); k++)
a[k-1] = a[k]; /* 向前移动 */
(*n)--;
}
main()
{
short a[M], n, j, key;
scanf(“%hd”, &n);
if(n > M-1 || n < 1)
error(); /* 结点数超界 */
for(j=0; j<n; j++)
scanf(“%hd”, &a[j]);
scanf(“%hd”, &j);
deleteNode(a, &n, j);
}
⊙ 删除结点的算法复杂度
移动次数最多为n-1次，算法复杂度为O(n)。

※ 链接存储的删除结点
⊙ 删除结点的操作
已知结点k的值dk，删除k的后件k’。

先查找结点k，由node指向结点k，由node->next指向node的后件k’(待删结点key)，再删除结点k’。

⊙ 链接存储删除结点的函数
void deleteNode(NODE *node)
{
NODE *key;
if (node==NULL)
error(); /* 非法结点 */
key = node->next;
node->next = key->next;
free(key); /* 释放删除结点的存储单元 */
}
⊙ 链接存储删除结点的算法复杂度
删除结点的操作次数与n无关，是一个常数C，算法复杂度为O(C)。
⊙ 链接存储删除结点的程序
#include <stdio.h>
#include <stdlib.h>
#define NODE struct node
NODE
{
short num;
NODE *next;
};
void createList(NODE *head)
{ ...... } /* 略 */
NODE *searchNode(NODE *head, short key)
{ ...... } /* 略 */
main()
{
short key;
NODE *Head, node;
/* 生成哨兵 */
Head = (NODE *)(malloc(sizeof(NODE)));
if(Head == NULL)
error(); /* 内存分配失败 */
Head->next = NULL;
/* 生成链表 */
createList(Head);
/* 读入key */
scanf("%hd", &key);
/* 查找结点 */
if(!(node= searchNode(Head, key))
error(); /*查找结点失败 */
/* 删除结点后件 */
deleteNode(node);
}

4.2.5 排序
※ 排序问题
以升序为例讨论排序问题。
⊙ 定义：
已知结点序列K = {k0, k1, k2, …, kn-1}，经排序得到K' = {k’0, k’1, k’2,…, k’n-1}，使得K和K’中结点数值相同，而dki’ ≤ dk’i+1(i=0, 1, …, n-2)，称新的结点序列K’为已排序的结点序列。
⊙ 需要掌握五种排序算法：
(1) 插入排序法 以下仅讨论插入排序算法
(2) 选择排序法
(3) 冒泡排序法
(4) 快速排序法
(5) 合并排序法
※ 插入排序算法
⊙ 插入排序算法描述
设已知结点序列为K = {k0, k1, k2, …, kn-1}，
将已排序的结点序列记为S，未排序的结点序列记为U。
初始：令S = {k0}，U = K - {k0} = {k1, k2, …, kn-1}
循环执行的插入步骤：
从i=1到n-1
令key = ki | ki∈U，U = U - {ki}
在S中插入ki，使得S = S∪{key}为已排序。
若U=φ，插入排序结束。
⊙ 排序过程示例
已知结点序列为{6, 5, 9, 4, 8}。
初始：令S = {k0} = {6}，U = {k1, …, k4} = {5, 9, 4, 8}。
循环插入的过程示例：
Step 1: i=1，插入5， 得S={5, 6}， U={9, 4, 8}；
Step 2: i=2，插入9， 得S={5, 6, 9}， U={4, 8}；
Step 3: i=3，插入4， 得S={4, 5, 6, 9}， U={8}；
Step 4: i=4，插入8， 得S={4, 5, 6, 8, 9}， U=φ，结束。
※ 顺序存储的插入排序函数
void insert(short *a, short n)
{
short key, j, k;
for(j=1; j<n; j++) /* 初始 */
{ /* 暂存: key=a[j] , 定位: key<a[k] */
for(key=a[j], k=j-1; key<a[k] && k>=0; k--)
a[k+1] = a[k]; /* 移动 */
a[++k] =key; /* 插入 */
}
}

⊙ 顺序存储的插入排序程序
#include <stdio.h>
#include <stdlib.h>
#define M 1000
void insert(short *a, short n)
{ ...... } /* 略 */
main()
{
short a[M], n, j;
scanf(“%hd”, &n);
if(n > M-1 || n < 1)
error(); /* 结点数超界 */
for(j=0; j<n; j++)
scanf(“%hd”, &a[j]);
insert(a, n); /* 排序 */
for(j=0; j<n; j++) /* 打印 */
printf(“%hd\n”, a[j]);
}

⊙ 顺序存储插入排序的算法复杂度
考虑n很大时，最多移动次数
= 1 + … + (n-2) + (n-1) = (n-1) * n / 2 ≈ n2 / 2 ≈ n2
所以，算法复杂度为O(n2)。
※ 链接存储的插入排序
⊙ 链接存储的插入排序算法
1) 初始设置
由head->next指向S = {k0}，由指针unsort指向未排序的结点序列U=K-S=K-{k0}。
程序语句为：
unsort = head->next->next;
head->next->next = NULL;

2) 从U中逐个取出结点在S中排序的过程
while(unsort)
从U中取出一个结点，由指针key指向，即在U中删除结点：
key = ki | ki∈U，U = U - {ki}
程序语句为：
key = unsort;
unsort = key->next;

将结点key插入S：S = S∪{key}，并且保持S为已排序。

⊙ 链接存储的插入排序函数
void insert(head)
NODE *head;
{
NODE *unsort, *key, *node;
if(head->next==NULL || head->next->next==NULL)
return; /* 空链表或者单结点链表 */
unsort = head->next->next; /* 初始：S = {k0}，U = K - {k0} */
head->next->next = NULL;
while(unsort) /* U非空，进行循环 */
{
key = unsort; /* U = U - {key} */
unsort = key->next;
for(node=head; node->next; node=node->next)
if(key->number <= node->next->number)
break; /* 定位插入点 */
key->next = node->next; /* 将key插入S，保持S有序 */
node->next = key;
}
}
⊙ 链接存储的插入排序算法的时间复杂度
从U取出结点为n-1次(while循环)，定位插入点的次数最多为n-1(for循环)，所以算法复杂度为O(n2)。
⊙ 链接存储的插入排序程序
#include <stdio.h>
#include <stdlib.h>
#define NODE struct node
NODE
{
short num;
NODE *next;
};
void createList(NODE *head)
{ ...... } /* 略 */
void insert(NODE *head)
{ ...... } /* 略 */
main()
{
NODE *Head, node;
/* 生成哨兵 */
if(!(Head=(NODE *)(malloc(sizeof(NODE))))
error(); /* 内存分配失败 */
Head->next = NULL;
createList(Head); /* 生成链表 */
insert(Head); /* 排序 */
for(node=Head->next; node;
node=node->next) /* 打印 */
printf(“%hd\n”, node->num);
}
4.2.6 存储方式与算法复杂度
以结点数n为基数，各种算法的时间复杂度O(f(n))表征所需的最多时间，并且与存储方式相关(见下表)。可以发现，两种存储方式没有绝对的优劣。例如，prtNode函数用顺序存储的算法复杂度与n无关，比链接存储要快。而添加结点和删除结点的函数，用链接存储的算法复杂度为O(C)，优于顺序存储的O(n)。
编程时要根据实际情况来决定采用哪一种存储方式。例如，需要频繁进行添加结点和删除结点操作的应用，采用链接存储较好。而只需要根据结点地址打印结点，则采用顺序存储较好。
另外，还应该综合n的可知情况决定采用数组还是链表(见3.3.5数组和指针应用的讨论)。
基本操作
操作函数
顺序存储
链接存储
查找结点
searchNode()
O(n)
O(n)
查找结点
prtNode()
O(C)
O(n)
添加结点
addNode()
O(n)
O(C)
删除结点
deleteNode()
O(n)
O(C)
插入排序
insert()
O(n2)
O(n2)

作 业

※ 习题 4-1(数据结构)，4-38(存储单元的图形表示)
※ 线性表上机题：4-39.1(顺序表操作)，4-40.1(链接表操作)，
4-39.2或者4-39.3任选1题，4-40.2或者4-40.3任选1题
将上机题发给助教。