计算机软件基础：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,ktK，表示在结点ks, kt之间存在关系ri。【例5-1.1】数据结构示例。09可组成集合K，在集合K=09上可存在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)，其中rR, (k, kK)，则称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点前件后件前件后件12,4213,65632,6,77415542623277336关系N关系T始结点14终结点47内结点2,3,6,72,5,6孤立结点51,34.1.3 数据结构的存储方式假定r是B=(K, R)中的一种关系，实现r的存储方式有以下两种： 顺序存储若对于任何一对结点(k, k)都成立ak = ak + s(s为存储单元的大小，固定长度)，则称r是用顺序方式存储的, 简称顺序存储。 链接存储若对于任何一对结点(k, k)都成立akpk，则称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+1K, 0 i n-1，则称B为线性表。 推论有且仅有一个始结点和一个终结点，其余为内结点除终结点外，每个结点有且仅有一个后件。除始结点外，每个结点有且仅有一个前件。 课程约定 如果没有特别说明，数据结构中的结点k只有一个数据场分量。 假定可以调用一个已设计的出错函数error(), 用于出错处理。 线性表的顺序存储采用数组实现线性表的顺序存储。 存储单元ki = aki, dki可省略指针场，其中，aki = idki = ai,pki = aki+1 = aki + 1 = i + 1 数据定义和生成线性表#defineM1000short n; /* M=n*/short aM;/* 在a0an-1中分别存放各结点的值dk0 dkn-1*/ 生成线性表的程序scanf(%hd, &n);if(n M | n 1)error();/* 结点数超界*/for(j=0; jnext ，即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; jnum = 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 #include #defineM1000void searchNode(short *a, short n, short key)short j;for (j=0; j M | n 1)error();/* 结点数超界 */for(j=0; jn; j+)scanf(%hd, &aj);scanf(%hd, &key);searchNode(a, n, key); 算法复杂度查找次数与n成正比，最多为n次，称该算法的时间复杂度为O(n)。 根据结点地址查找结点的程序#include #include #defineM1000void prtNode(a, n, j)short n, a , j;if(jn-1)error();/* 结点地址超界*/printf(“node(%hd) = %hdn”, j, aj);main()short n, aM, j;scanf(“%hd”, &n);if(n M | n 1)error();/* 结点数超界 */for(j=0; jnext = NULL;/* 生成链表 */createList(Head); /* 读入key*/scanf(%hd, &key);/* 查找结点*/if(node = searchNode(Head, key)printf(node = %hdn, node-num);elseerror();/* 查找结点失败*/ 查找结点函数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。将an-1到aj+1向数组尾部移动，腾出添加新结点key的位置，再将新结点key插入。 顺序存储添加结点的程序#include #include #defineM1000void addNode(a, n, j, key)short a, j, key;short *n; /* 添加结点后*n要加1*/short k;if(j(*n)-1)error(); /* 结点地址超界*/for(k=(*n)-1; kj; k-)ak+1 = ak; /* 向后移动 */aj+1 = key;(*n)+;main()short aM, n, j, key;scanf(“%hd”, &n);if(n M-1 | n 1)error(); /* 结点数超界*/for(j=0; jnum = key;key-next = node-next;node-next = key; 链接存储添加结点的算法复杂度添加结点的操作次数与n无关，是一个常数C，算法复杂度为O(C)。 链接存储添加结点的程序#include #include #define NODE struct nodeNODEshort 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。将aj+1到an-1向数组前部移动，待删结点aj(kj)被覆盖。 顺序存储删除结点的程序#include #include #defineM1000void deleteNode(a, n, j)short a, j;short *n; /* 删除结点后*n要减1 */short k;if(j(*n)-1)error(); /* 结点地址超界 */for(k=j+1; k M-1 | n 1)error(); /* 结点数超界*/for(j=0; jnext指向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 #include #define NODE struct nodeNODEshort 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 = k0, k1, k2, kn-1，使得K和K中结点数值相同，而dki dki+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 | kiU，U = U - ki在S中插入ki，使得S = Skey为已排序。若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; jn; j+) /* 初始*/* 暂存: key=aj,定位: keyak*/for(key=aj, k=j-1; key=0; k-)ak+1 = ak;/* 移动*/a+k =key;/* 插入*/ 顺序存储的插入排序程序#include #include #defineM1000void insert(short *a, short n) . /* 略 */main()short aM, n, j;scanf(“%hd”, &n);if(n M-1 | n 1)error();/* 结点数超界*/for(j=0; jn; j+)scanf(“%hd”, &aj);insert(a, n); /* 排序*/for(j=0; jnext指向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 | kiU，U = U - ki程序语句为：key = unsort; unsort = key-next;将结点key插入S：S = Skey，并且保持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 next-number)break;/* 定位插入点*/key-next = node-next; /* 将key插入S，保持S有序*/node-next = key; 链接存储的插入排序算法的时间复杂度从U取出结点为n-1次(while循环)，定位插入点的次数最多为n-1(for循环)，所以算法复杂度为O(n2)。 链接存储的插入排序程序#include #include #define NODE struct nodeNODEshort 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(“%hdn”, 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题将上机题发给助教。