数据库结构第一单元复习

第一单元复习绪论、线性结构的存储及其基本运算一、课程目的意义数据结构是普通高校计算机专业和信息管理专业一门必修的核心课程。(专业基础课)

数据结构研究数据的逻辑结构、在计算机中的存储结构以及各种非数值运算的算法。使学生掌握数据组织、存储和处理的常用方法，为以后进行软件开发和学习后续专业课打下良好的基础。二、基本术语数据数据元素数据处理（检索、插入、删除、…）数据结构（逻辑结构与存储结构）数据类型与抽象数据类型数据结构的描述法：图形表示——用小圆圈表示数据(称为结点或顶点)、用连接小圆圈的边或弧表示数据之间的关系。例：讨论某单位人事表中的各种关系1：姓名贵贱关系（集合结构）2：年龄大小关系（线性结构）3：领导与被领导关系（树形结构）4：朋友关系（图形结构）三、计算时间复杂性的数量级一个算法的时间复杂性的计算是相当繁琐的。实际上，一般只要求计其数量级即可。一个函数f(n)的数量级表示法若f(n)/g(n)k(n∞，k0)

则记f(n)=O(g(n))如4n+4=O(n),4n2+5n+2=O(n2)等直接求算法的时间复杂性的数量级不必对算法的每一步都进行详细分析，只需分析算法中的主要部分：对循环语句分析循环体内简单操作的执行次数，对递归函数分析其调用的次数等等一个算法的时间复杂性可以分为最好、最差和平均三种情况讨论。四、线性表的逻辑结构

1、线性表：由n(n≥0)个同类型元素的组成有限序列。线性表可简称为表，记作

L=（a1,a2,…ai,ai+1,…,an)

其中n称为线性表L的长度，n=0时称为空表。2、线性表的特点:当表非空时,

(1)存在唯一的一个被称为“表首”的元素;

(2)存在唯一的一个被称为“表尾”的元素;

(3)除表首元素外,表中的每一个元素均只有一个直接前驱;

(4)除表尾元素外,表中的每一个元素均只有一个直接后继。3、线性表的图形表示

La1a2a3...ai-1ai…an

五、线性表的基本运算构造空的线性表L：

InitList(L)求线性表的长度：

ListLength(L)读出表L中第i个位置的元素:

GetNode(L,i)求表L中值为x元素的位置：

LocateNode(L,x)在表L的i处插入x：

InsertList(L,x,i)删除表L位置i的元素：

DeleteList(L,i)六、调用基本函数举例

例设线性表L0的元素是整数：L0=（25，38,19,42,33），试给出对L0调用上述基本函数的一些方法及结果。k=ListLength(L0);//k=5,这是表L0的长度k=LocateNode(L0,42,)；//k=4InsertList(L0,65,3)；

//结果L0=(25,38,65,19,42,33)ListDelete(L0,3)；//结果L0=(25,38,42,33)将L0改为L0=(2,4,6,8,…,100):

InitList(L0);

for(i=1;i<=50;i++)InsertList(L0,2*i,i)；将另一个同类型的线性表L1接在L0的后面，而L1仍保持不变:

m=ListLength(L0);n=ListLength(L1);

for(i=1;i<=n;i++)

InsertList(L0,GetNode(L1,i),m+i)；七线性表的顺序存储1、将线性表的数据元素按逻辑顺序依次存放到一组地址连续的存储单元里。这样的线性表又称为顺序表2、假设表A=(a1,a2,…,an)的每个元素占用c个存储单元,则线性表的存储示意图如图2-1(P14)。而且每个元素的存储地址可通过下式计算：

LOC(ai)=LOC(a1)+(i-1)*c1≤i≤n3、顺序表通常用一个结构体来定义：

typedefstruct{

DataTypedata[ListSize];

intlength;

}SeqList;4、在顺序存储下基本运算的实现八线性表的链接存储1.用一组任意的存储单元来存放线性表的结点。为了能正确表示结点之间的逻辑关系，在存储每个结点的同时，还必须存储指示其直接后继结点的地址的信息，这个信息叫做指针或链，这两部分信息组成了链表的结点结构。2.单链表的一般图形

设线性表L=（a1,a2,…,an)，则其图形为

La1a2a3...ai-1ai…an而单链表的逻辑示意图为：a1a2….

ai….an

^L3、单链表的结点定义

typedefstructnode{

DataTypedata;//数据域

structnode*next;//指针域

}ListNode;//结点类型

typedefListNode*LinkList;//头指针类ListNode*p;//某结点指针

LinkListhead;//链表头指针4、有关指针的一些主要知识点

(1)、指针变量p与结点变量*p的关系datanextp*p结点的数据域表示为：(*p).data或p->data结点的指针域表示为：(*p).next或p->next(2)、定义了一个指针变量p，必须给它指定或者分配存储单元，这样*p才有意义。如：inta,*p;执行a=123;p=&a后*p=123;(3)、可以直接给指针变量分配存储单元,如：

p=(int*)malloc(sizeof(int));

表示用函数malloc分配一个int类型的结点。(4)、可以通过函数free释放上述方法分配的存储单元(即结点)：

free(p);5、在链式存储下基本运算的实现。6、循环链表：将单链表终端结点的指针域NULL改成指向表头结点，就形成一个单循环链表，在许多问题中，表的操作常常在表的首尾进行，所以实用中多采用尾指针来表示循环链表，如下图所示：a1a2anrear……这样，rear表示尾指针，rear->next表示表头指针。终端结点为rear->data=an,而开始结点为rear->next->next->data=a1。7、双向链表双向链表结点结构为priordatanext九、栈1、栈的定义：栈是一种运算受限的线性表，其限制是仅在表的一端进行插入和删除运算。2、桟的基本运算构造一个空栈InitStack(S)判断栈空StackEmpty(S)判断栈满StacKFull(S)进栈(或称入栈)Push(S,x)退栈(或称出栈)Pop(S)取栈顶元素StackTop(S)3、顺序栈(1)、顺序栈的定义

typedefstruct{//定义结构体

Datatypedata[stacksize]；//存储空间

inttop；//栈顶指针

}Sqstack;(2)、注意：栈的顺序存储结构与线性表的顺序存储结构基本相同，只是将长度变量length改成栈顶指针top。但length=0表示线性表为空表，而top=0表示栈顶下标在0处，栈中仍有一个元素。当元素进栈时，栈顶指针top++,而当元素退栈时栈顶指针top--。若top=stacksize-1,表示栈满，不能再进栈，否则称为“上溢”；若top=-1,表示栈空，不能再退栈，否则称为“下溢”。(3)、在顺序存储下桟基本运算的实现2、链桟链桟：栈的链式存储结构称为链桟。(1)、链桟结点的定义

typedefstructstacknode{

Datatypedata；//数据域

structstacknode*next；//指针域

}StackNode;(2)栈顶指针的定义typedefstruct{

stacknode*top；

}LinkStack;(3)在链式存储下桟基本运算的实现

如初始化

InitStach(LinkStack*S){

S=(StackNode*)

malloc(sizof(StackNode));

s->top=NULL;}十队列1、队列的定义

它是一种运算受阻的线性表:允许在表的一端进行插入，而在另一端进行删除。允许插入的一端称为队尾，进行删除的另一端称为队首。2、队列的的基本运算：初始化、置空、判队空、判队满、进队和出队3、队列的顺序存储结构：

typedefstruct{

Datatypedata[QueueSize];

intfront,rear,count;

}cirQueue;循环队列：将存储队列的数组空间看成首尾相连的环，队列的顺序存储一般都是指循环队列。4、队列的链式存储(1)链队列的结点结构

typedefstructqueueNode{

Datatypedata;

structqueueNode*next;

}QueueNode;(2)链队列的表头结构

typedefstruct{

QueueNode*front;QueueNode*rear;}LinkQueue;(3)、在链式存储下队列基本运算的实现

十一、串及其运算1、串：由若干个字符组成的有限序列。一般记为S=“a1a2a3…an”。其中n称为串的长度，n为零时称为空串，空串可以为S=“”。2、基本术语数字字符串：“123”；（对比：数字123）空白串：“”；（对比：空串“”）子串：一个串的任意个连续的字符组成的子序列。如“cdef”是“abcdefg”的子串；串常量与串变量3、串的基本运算字符串是计算机应用中最常用的数据结构，所以大多高级语言都提供字符串基本运算的标准函数，C语言把它们存放在库函数<string.h>中。(1)求串长:intstrlen(char*s);如对前面定义的串t，语句k=strlen(t),则k=18。(2)串复制:char*strcpy(char*to,char*from);如：s=strcpy(t,s);则s=“programCLanguage”。(3)串联接:char*strcat(char*to,char*from);如：s=strcpy(t,”?”);则s=“programCLanguage?”。(4)串比较:intstrcmp(char*s1,char*s2);若s1>s2,则strcmp(s1,s2)>0,而strcmp(s2,s1)<0。(5)字符定位：char*strchr(char*s,charc);4、串的顺序存储

顺序存储就是用一组地址连续的地存储单元来存储串中的字符序列，因此在高级语言中就是用数组来实现。这可以分成两类：(1)静态存储分配的顺序串直接式：chars[256];//最多可存放256个字符的串变量s间接式——先定义类型，再定义变量：

＃defineMaxSize256//定义串的大小

typedefcharSeqString[MaxSize];//定义字符串类型

SeqStrings;