數(shù)據(jù)庫(kù)結(jié)構(gòu)第一單元復(fù)習(xí)

第一單元復(fù)習(xí)緒論、線性結(jié)構(gòu)的存儲(chǔ)及其基本運(yùn)算一、課程目的意義數(shù)據(jù)結(jié)構(gòu)是普通高校計(jì)算機(jī)專業(yè)和信息管理專業(yè)一門必修的核心課程。(專業(yè)基礎(chǔ)課)

數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的邏輯結(jié)構(gòu)、在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)以及各種非數(shù)值運(yùn)算的算法。使學(xué)生掌握數(shù)據(jù)組織、存儲(chǔ)和處理的常用方法，為以后進(jìn)行軟件開發(fā)和學(xué)習(xí)后續(xù)專業(yè)課打下良好的基礎(chǔ)。二、基本術(shù)語(yǔ)數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)處理（檢索、插入、刪除、…）數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)）數(shù)據(jù)類型與抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)的描述法：圖形表示——用小圓圈表示數(shù)據(jù)(稱為結(jié)點(diǎn)或頂點(diǎn))、用連接小圓圈的邊或弧表示數(shù)據(jù)之間的關(guān)系。例：討論某單位人事表中的各種關(guān)系1：姓名貴賤關(guān)系（集合結(jié)構(gòu)）2：年齡大小關(guān)系（線性結(jié)構(gòu)）3：領(lǐng)導(dǎo)與被領(lǐng)導(dǎo)關(guān)系（樹形結(jié)構(gòu)）4：朋友關(guān)系（圖形結(jié)構(gòu)）三、計(jì)算時(shí)間復(fù)雜性的數(shù)量級(jí)一個(gè)算法的時(shí)間復(fù)雜性的計(jì)算是相當(dāng)繁瑣的。實(shí)際上，一般只要求計(jì)其數(shù)量級(jí)即可。一個(gè)函數(shù)f(n)的數(shù)量級(jí)表示法若f(n)/g(n)k(n∞，k0)

則記f(n)=O(g(n))如4n+4=O(n),4n2+5n+2=O(n2)等直接求算法的時(shí)間復(fù)雜性的數(shù)量級(jí)不必對(duì)算法的每一步都進(jìn)行詳細(xì)分析，只需分析算法中的主要部分：對(duì)循環(huán)語(yǔ)句分析循環(huán)體內(nèi)簡(jiǎn)單操作的執(zhí)行次數(shù)，對(duì)遞歸函數(shù)分析其調(diào)用的次數(shù)等等一個(gè)算法的時(shí)間復(fù)雜性可以分為最好、最差和平均三種情況討論。四、線性表的邏輯結(jié)構(gòu)

1、線性表：由n(n≥0)個(gè)同類型元素的組成有限序列。線性表可簡(jiǎn)稱為表，記作

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

其中n稱為線性表L的長(zhǎng)度，n=0時(shí)稱為空表。2、線性表的特點(diǎn):當(dāng)表非空時(shí),

(1)存在唯一的一個(gè)被稱為“表首”的元素;

(2)存在唯一的一個(gè)被稱為“表尾”的元素;

(3)除表首元素外,表中的每一個(gè)元素均只有一個(gè)直接前驅(qū);

(4)除表尾元素外,表中的每一個(gè)元素均只有一個(gè)直接后繼。3、線性表的圖形表示

La1a2a3...ai-1ai…an

五、線性表的基本運(yùn)算構(gòu)造空的線性表L：

InitList(L)求線性表的長(zhǎng)度：

ListLength(L)讀出表L中第i個(gè)位置的元素:

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

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

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

DeleteList(L,i)六、調(diào)用基本函數(shù)舉例

例設(shè)線性表L0的元素是整數(shù)：L0=（25，38,19,42,33），試給出對(duì)L0調(diào)用上述基本函數(shù)的一些方法及結(jié)果。k=ListLength(L0);//k=5,這是表L0的長(zhǎng)度k=LocateNode(L0,42,)；//k=4InsertList(L0,65,3)；

//結(jié)果L0=(25,38,65,19,42,33)ListDelete(L0,3)；//結(jié)果L0=(25,38,42,33)將L0改為L(zhǎng)0=(2,4,6,8,…,100):

InitList(L0);

for(i=1;i<=50;i++)InsertList(L0,2*i,i)；將另一個(gè)同類型的線性表L1接在L0的后面，而L1仍保持不變:

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

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

InsertList(L0,GetNode(L1,i),m+i)；七線性表的順序存儲(chǔ)1、將線性表的數(shù)據(jù)元素按邏輯順序依次存放到一組地址連續(xù)的存儲(chǔ)單元里。這樣的線性表又稱為順序表2、假設(shè)表A=(a1,a2,…,an)的每個(gè)元素占用c個(gè)存儲(chǔ)單元,則線性表的存儲(chǔ)示意圖如圖2-1(P14)。而且每個(gè)元素的存儲(chǔ)地址可通過下式計(jì)算：

LOC(ai)=LOC(a1)+(i-1)*c1≤i≤n3、順序表通常用一個(gè)結(jié)構(gòu)體來定義：

typedefstruct{

DataTypedata[ListSize];

intlength;

}SeqList;4、在順序存儲(chǔ)下基本運(yùn)算的實(shí)現(xiàn)八線性表的鏈接存儲(chǔ)1.用一組任意的存儲(chǔ)單元來存放線性表的結(jié)點(diǎn)。為了能正確表示結(jié)點(diǎn)之間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)的同時(shí)，還必須存儲(chǔ)指示其直接后繼結(jié)點(diǎn)的地址的信息，這個(gè)信息叫做指針或鏈，這兩部分信息組成了鏈表的結(jié)點(diǎn)結(jié)構(gòu)。2.單鏈表的一般圖形

設(shè)線性表L=（a1,a2,…,an)，則其圖形為

La1a2a3...ai-1ai…an而單鏈表的邏輯示意圖為：a1a2….

ai….an

^L3、單鏈表的結(jié)點(diǎn)定義

typedefstructnode{

DataTypedata;//數(shù)據(jù)域

structnode*next;//指針域

}ListNode;//結(jié)點(diǎn)類型

typedefListNode*LinkList;//頭指針類ListNode*p;//某結(jié)點(diǎn)指針

LinkListhead;//鏈表頭指針4、有關(guān)指針的一些主要知識(shí)點(diǎn)

(1)、指針變量p與結(jié)點(diǎn)變量*p的關(guān)系datanextp*p結(jié)點(diǎn)的數(shù)據(jù)域表示為：(*p).data或p->data結(jié)點(diǎn)的指針域表示為：(*p).next或p->next(2)、定義了一個(gè)指針變量p，必須給它指定或者分配存儲(chǔ)單元，這樣*p才有意義。如：inta,*p;執(zhí)行a=123;p=&a后*p=123;(3)、可以直接給指針變量分配存儲(chǔ)單元,如：

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

表示用函數(shù)malloc分配一個(gè)int類型的結(jié)點(diǎn)。(4)、可以通過函數(shù)free釋放上述方法分配的存儲(chǔ)單元(即結(jié)點(diǎn))：

free(p);5、在鏈?zhǔn)酱鎯?chǔ)下基本運(yùn)算的實(shí)現(xiàn)。6、循環(huán)鏈表：將單鏈表終端結(jié)點(diǎn)的指針域NULL改成指向表頭結(jié)點(diǎn)，就形成一個(gè)單循環(huán)鏈表，在許多問題中，表的操作常常在表的首尾進(jìn)行，所以實(shí)用中多采用尾指針來表示循環(huán)鏈表，如下圖所示：a1a2anrear……這樣，rear表示尾指針，rear->next表示表頭指針。終端結(jié)點(diǎn)為rear->data=an,而開始結(jié)點(diǎn)為rear->next->next->data=a1。7、雙向鏈表雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)為priordatanext九、棧1、棧的定義：棧是一種運(yùn)算受限的線性表，其限制是僅在表的一端進(jìn)行插入和刪除運(yùn)算。2、桟的基本運(yùn)算構(gòu)造一個(gè)空棧InitStack(S)判斷?？誗tackEmpty(S)判斷棧滿StacKFull(S)進(jìn)棧(或稱入棧)Push(S,x)退棧(或稱出棧)Pop(S)取棧頂元素StackTop(S)3、順序棧(1)、順序棧的定義

typedefstruct{//定義結(jié)構(gòu)體

Datatypedata[stacksize]；//存儲(chǔ)空間

inttop；//棧頂指針

}Sqstack;(2)、注意：棧的順序存儲(chǔ)結(jié)構(gòu)與線性表的順序存儲(chǔ)結(jié)構(gòu)基本相同，只是將長(zhǎng)度變量length改成棧頂指針top。但length=0表示線性表為空表，而top=0表示棧頂下標(biāo)在0處，棧中仍有一個(gè)元素。當(dāng)元素進(jìn)棧時(shí)，棧頂指針top++,而當(dāng)元素退棧時(shí)棧頂指針top--。若top=stacksize-1,表示棧滿，不能再進(jìn)棧，否則稱為“上溢”；若top=-1,表示?？?，不能再退棧，否則稱為“下溢”。(3)、在順序存儲(chǔ)下桟基本運(yùn)算的實(shí)現(xiàn)2、鏈桟鏈桟：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈桟。(1)、鏈桟結(jié)點(diǎn)的定義

typedefstructstacknode{

Datatypedata；//數(shù)據(jù)域

structstacknode*next；//指針域

}StackNode;(2)棧頂指針的定義typedefstruct{

stacknode*top；

}LinkStack;(3)在鏈?zhǔn)酱鎯?chǔ)下桟基本運(yùn)算的實(shí)現(xiàn)

如初始化

InitStach(LinkStack*S){

S=(StackNode*)

malloc(sizof(StackNode));

s->top=NULL;}十隊(duì)列1、隊(duì)列的定義

它是一種運(yùn)算受阻的線性表:允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許插入的一端稱為隊(duì)尾，進(jìn)行刪除的另一端稱為隊(duì)首。2、隊(duì)列的的基本運(yùn)算：初始化、置空、判隊(duì)空、判隊(duì)滿、進(jìn)隊(duì)和出隊(duì)3、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)：

typedefstruct{

Datatypedata[QueueSize];

intfront,rear,count;

}cirQueue;循環(huán)隊(duì)列：將存儲(chǔ)隊(duì)列的數(shù)組空間看成首尾相連的環(huán)，隊(duì)列的順序存儲(chǔ)一般都是指循環(huán)隊(duì)列。4、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)(1)鏈隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu)

typedefstructqueueNode{

Datatypedata;

structqueueNode*next;

}QueueNode;(2)鏈隊(duì)列的表頭結(jié)構(gòu)

typedefstruct{

QueueNode*front;QueueNode*rear;}LinkQueue;(3)、在鏈?zhǔn)酱鎯?chǔ)下隊(duì)列基本運(yùn)算的實(shí)現(xiàn)

十一、串及其運(yùn)算1、串：由若干個(gè)字符組成的有限序列。一般記為S=“a1a2a3…an”。其中n稱為串的長(zhǎng)度，n為零時(shí)稱為空串，空串可以為S=“”。2、基本術(shù)語(yǔ)數(shù)字字符串：“123”；（對(duì)比：數(shù)字123）空白串：“”；（對(duì)比：空串“”）子串：一個(gè)串的任意個(gè)連續(xù)的字符組成的子序列。如“cdef”是“abcdefg”的子串；串常量與串變量3、串的基本運(yùn)算字符串是計(jì)算機(jī)應(yīng)用中最常用的數(shù)據(jù)結(jié)構(gòu)，所以大多高級(jí)語(yǔ)言都提供字符串基本運(yùn)算的標(biāo)準(zhǔn)函數(shù)，C語(yǔ)言把它們存放在庫(kù)函數(shù)<string.h>中。(1)求串長(zhǎng):intstrlen(char*s);如對(duì)前面定義的串t，語(yǔ)句k=strlen(t),則k=18。(2)串復(fù)制:char*strcpy(char*to,char*from);如：s=strcpy(t,s);則s=“programCLanguage”。(3)串聯(lián)接: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、串的順序存儲(chǔ)

順序存儲(chǔ)就是用一組地址連續(xù)的地存儲(chǔ)單元來存儲(chǔ)串中的字符序列，因此在高級(jí)語(yǔ)言中就是用數(shù)組來實(shí)現(xiàn)。這可以分成兩類：(1)靜態(tài)存儲(chǔ)分配的順序串直接式：chars[256];//最多可存放256個(gè)字符的串變量s間接式——先定義類型，再定義變量：

＃defineMaxSize256//定義串的大小

typedefcharSeqString[MaxSize];//定義字符串類型

SeqStrings;