數(shù)據(jù)庫結構第一單元復習

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

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

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

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)六、調(diào)用基本函數(shù)舉例

例設線性表L0的元素是整數(shù)：L0=（25，38,19,42,33），試給出對L0調(diào)用上述基本函數(shù)的一些方法及結果。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、將線性表的數(shù)據(jù)元素按邏輯順序依次存放到一組地址連續(xù)的存儲單元里。這樣的線性表又稱為順序表2、假設表A=(a1,a2,…,an)的每個元素占用c個存儲單元,則線性表的存儲示意圖如圖2-1(P14)。而且每個元素的存儲地址可通過下式計算：

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

typedefstruct{

DataTypedata[ListSize];

intlength;

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

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

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

ai….an

^L3、單鏈表的結點定義

typedefstructnode{

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

structnode*next;//指針域

}ListNode;//結點類型

typedefListNode*LinkList;//頭指針類ListNode*p;//某結點指針

LinkListhead;//鏈表頭指針4、有關指針的一些主要知識點

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

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

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

free(p);5、在鏈式存儲下基本運算的實現(xiàn)。6、循環(huán)鏈表：將單鏈表終端結點的指針域NULL改成指向表頭結點，就形成一個單循環(huán)鏈表，在許多問題中，表的操作常常在表的首尾進行，所以實用中多采用尾指針來表示循環(huán)鏈表，如下圖所示：a1a2anrear……這樣，rear表示尾指針，rear->next表示表頭指針。終端結點為rear->data=an,而開始結點為rear->next->next->data=a1。7、雙向鏈表雙向鏈表結點結構為priordatanext九、棧1、棧的定義：棧是一種運算受限的線性表，其限制是僅在表的一端進行插入和刪除運算。2、桟的基本運算構造一個空棧InitStack(S)判斷?？誗tackEmpty(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)、在順序存儲下桟基本運算的實現(xiàn)2、鏈桟鏈桟：棧的鏈式存儲結構稱為鏈桟。(1)、鏈桟結點的定義

typedefstructstacknode{

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

structstacknode*next；//指針域

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

stacknode*top；

}LinkStack;(3)在鏈式存儲下桟基本運算的實現(xiàn)

如初始化

InitStach(LinkStack*S){

S=(StackNode*)

malloc(sizof(StackNode));

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

它是一種運算受阻的線性表:允許在表的一端進行插入，而在另一端進行刪除。允許插入的一端稱為隊尾，進行刪除的另一端稱為隊首。2、隊列的的基本運算：初始化、置空、判隊空、判隊滿、進隊和出隊3、隊列的順序存儲結構：

typedefstruct{

Datatypedata[QueueSize];

intfront,rear,count;

}cirQueue;循環(huán)隊列：將存儲隊列的數(shù)組空間看成首尾相連的環(huán)，隊列的順序存儲一般都是指循環(huán)隊列。4、隊列的鏈式存儲(1)鏈隊列的結點結構

typedefstructqueueNode{

Datatypedata;

structqueueNode*next;

}QueueNode;(2)鏈隊列的表頭結構

typedefstruct{

QueueNode*front;QueueNode*rear;}LinkQueue;(3)、在鏈式存儲下隊列基本運算的實現(xiàn)

十一、串及其運算1、串：由若干個字符組成的有限序列。一般記為S=“a1a2a3…an”。其中n稱為串的長度，n為零時稱為空串，空串可以為S=“”。2、基本術語數(shù)字字符串：“123”；（對比：數(shù)字123）空白串：“”；（對比：空串“”）子串：一個串的任意個連續(xù)的字符組成的子序列。如“cdef”是“abcdefg”的子串；串常量與串變量3、串的基本運算字符串是計算機應用中最常用的數(shù)據(jù)結構，所以大多高級語言都提供字符串基本運算的標準函數(shù)，C語言把它們存放在庫函數(shù)<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)串聯(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、串的順序存儲

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

＃defineMaxSize256//定義串的大小

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

SeqStrings;