基本運算是指執行運算最基礎的算法。
在關係代數運算中，有5種基本運算，它們是並（U）、差（—）、投影、選擇、笛卡爾積（X），其它運算即交、連線和除，均可通過5種基本的運算來表達。
基本介紹
- 中文名：基本運算
- 外文名：Basic operation
- 套用學科：數學
- 基本概念：指執行運算最基礎的算法
- 種類：並、差、投影、選擇、笛卡爾積
- 屬性：基礎算法
基本運算,棧的定義,棧的定義,棧的基本運算,定長順序串,串聯接,求字串,串比較,
基本運算
傳統的集合運算
1、並（UNION）設有兩個關係R和S，它們具有相同的結構。R和S的並是由屬於R或屬於S的元組組成的集合，運算符為∪。記為T=R∪S。
2、差（DIFFERENCE）R和S的差是由屬於R但不屬於S的元組組成的集合，運算符為－。記為T=R－S。
3、交（INTERSCTION）R和S的交是由既屬於R又屬於S的元組組成的集合，運算符為∩。記為T=R∩S。R∩S=R－（R－S）。
選擇運算
從關係中找出滿足給定條件的那些元組稱為選擇。其中的條件是以邏輯表達式給出的，值為真的元組將被選取。這種運算是從水平方向抽取元組。在FOXPRO中的短語FOR<條件>和WHILE<條件>均相當於選擇運算。
如：LISTFOR出版單位='高等教育出版社'AND單價<=20
投影運算
從關係模式中挑選若干屬性組成新的關係稱為投影。這是從列的角度進行的運算，相當於對關係進行垂直分解。在FOXPRO中短語FIELDS<欄位1，欄位2，…>相當於投影運算。如：LISTFIELDS單位，姓名
連線運算
選擇和投影運算都是屬於一目運算，它們的操作對象只是一個關係。連線運算是二目運算，需要兩個關係作為操作對象。
1、連線是將兩個關係模式通過公共的屬性名拼接成一個更寬的關係模式，生成的新關係中包含滿足連線條件的元組。運算過程是通過連線條件來控制的，連線條件中將出現兩個關係中的公共屬性名，或者具有相同語義、可比的屬性。連線是對關係的結合。在FOXPRO中有單獨一條命令JOIN實現兩個關係的連線運算。如：
SELE1
USE定單
SELE2
USE商品
JOINWITHATOXGXFORA->貨號=貨號AND庫存量>=A->定購量
設關係R和S分別有m和n個元組，則R與S的連線過程要訪問m×n個元組。由此可見，涉及到連線的查詢應當考慮最佳化，以便提高查詢效率。
2、自然連線是去掉重複屬性的等值連線。它屬於連線運算的一個特例，是最常用的連線運算，在關係運算中起著重要作用。
如果需要兩個以上的關係進行連線，應當兩兩進行。利用關係的這三種專門運算可以方便地構造新的關係。
外關鍵字
如果一個關係中的屬性或屬性組並非該關係的關鍵字，但它們是另外一個關係的關鍵字，則稱為該關係的外關鍵字。
綜上所述，關係資料庫系統有如下特點：
（1）資料庫中的全部數據及其相互聯繫都被組織成關係，即二維表的形式。
（2）關係資料庫系統提供一種完備的高級關係運算，支持對資料庫的各種操作。
（3）關係模型有嚴格的數學理論，使資料庫的研究建立在比較堅實的數學基礎上。
棧的定義
棧的定義
棧（Stack）是限制僅在表的一端進行插入和刪除運算的線性表。
(1)通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。
(2)當表中沒有元素時稱為空棧。
(3)棧為後進先出（LastInFirstOut）的線性表，簡稱為LIFO表。
棧的修改是按後進先出的原則進行。每次刪除（退棧）的總是當前棧中"最新"的元素，即最後插入（進棧）的元素，而最先插入的是被放在棧的底部，要到最後才能刪除
【示例】元素是以a1，a2，…，an的順序進棧，退棧的次序卻是an，an-1，…，a1。
棧的基本運算
（1）InitStack（S）
構造一個空棧S。
（2）StackEmpty（S）
判棧空。若S為空棧，則返回TRUE，否則返回FALSE。
（3）StackFull（S）
判棧滿。若S為滿棧，則返回TRUE，否則返回FALSE。
注意：
該運算只適用於棧的順序存儲結構。
（4）Push（S，x）
進棧。若棧S不滿，則將元素x插入S的棧頂。
（5）Pop（S）
退棧。若棧S非空，則將S的棧頂元素刪去，並返回該元素。
（6）StackTop（S）
取棧頂元素。若棧S非空，則返回棧頂元素，但不改變棧的狀態。
順序棧
棧的順序存儲結構簡稱為順序棧,它是運算受限的順序表。
1、順序棧的類型定義
#defineStackSize100//假定預分配的棧空間最多為100個元素
typedefstruct{
DataTypedata[StackSize];
inttop;
}SeqStack;
注意：
①順序棧中元素用向量存放
②棧底位置是固定不變的，可設定在向量兩端的任意一個端點
③棧頂位置是隨著進棧和退棧操作而變化的，用一個整型量top（通常稱top為棧頂指針）來指示當前棧頂位置
2、順序棧的基本操作
前提條件：
設S是SeqStack類型的指針變數。若棧底位置在向量的低端，即S->data[0]是棧底元素。
（1）進棧操作
進棧時，需要將S->top加1
注意：
①S->top==StackSize-1表示棧滿
②"上溢"現象--當棧滿時，再做進棧運算產生空間溢出的現象。
上溢是一種出錯狀態，應設法避免。
（2）退棧操作
退棧時，需將S->top減1
注意：
①S->toptop=-1;
}
（2）判棧空
intStackEmpty（SeqStack*S）
{
returnS->top==-1;
}
（3）判棧滿
intStackFull（SeqStack*SS）
{
returnS->top==StackSize-1;
}
（4）進棧
voidPush（S，x）
{
if(StackFull(S))
Error("Stackoverflow");//上溢，退出運行
S->data[++S->top]=x;//棧頂指針加1後將x入棧
}
（5）退棧
DataTypePop（S）
{
if(StackEmpty(S))
Error("Stackunderflow");//下溢，退出運行
returnS->data[S->top--];//棧頂元素返回後將棧頂指針減1
}
（6）取棧頂元素
DataTypeStackTop（S）
{
if(StackEmpty(S))
Error("Stackisempty");
returnS->data[S->top];
}
4、兩個棧共享同一存儲空間
當程式中同時使用兩個棧時，可以將兩個棧的棧底設在向量空間的兩端，讓兩個棧各自向中間延伸。當一個棧里的元素較多，超過向量空間的一半時，只要另一個棧的元素不多，那么前者就可以占用後者的部分存儲空間。
只有當整個向量空間被兩個棧占滿（即兩個棧頂相遇）時，才會發生上溢。因此，兩個棧共享一個長度為m的向量空間和兩個棧分別占用兩個長度為└m/2┘和┌m/2┐的向量空間比較，前者發生上溢的機率比後者要小得多。
鏈棧
棧的鏈式存儲結構稱為鏈棧。
1、鏈棧的類型定義
鏈棧的類型說明如下：
typedefstructstacknode{
DataTypedata
structstacknode*next
}StackNode;
typedefstruct{
StackNode*top;//棧頂指針
}LinkStack;
注意：
①LinkStack結構類型的定義是為了方便在函式體中修改top指針本身
②若要記錄棧中元素個數，可將元素個數屬性放在LinkStack類型中定義。
2、鏈棧的基本運算
（1）置棧空
VoidInitStack(LinkStack*S)
{
S->top=NULL;
}
（2）判棧空
intStackEmpty(LinkStack*S)
{
returnS->top==NULL;
}
（3）進棧
voidPush(LinkStack*S,DataTypex)
{//將元素x插入鏈棧頭部
StackNode*p=(StackNode*)malloc(sizeof(StackNode));
p->data=x;
p->next=S->top;//將新結點*p插入鏈棧頭部
S->top=p;
}
（4）退棧
DataTypePop(LinkStack*S)
{
DataTypex;
StackNode*p=S->top;//保存棧頂指針
if(StackEmpty(S))
Error("Stackunderflow.");//下溢
x=p->data;//保存棧頂結點數據
S->top=p->next;//將棧頂結點從鏈上摘下
free(p);
returnx;
}
（5）取棧頂元素
DataTypeStackTop(LinkStack*S)
{
if(StackEmpty(S))
Error("Stackisempty.")
returnS->top->data;
}
注意：
鏈棧中的結點是動態分配的，所以可以不考慮上溢，無須定義StackFull運算。
定長順序串
串定位在下一小節討論，設串結束用'\0'來標識。
串聯接
把兩個串s1和s2首尾連線成一個新串s，即：sMAXSIZE-1)return0;/*s長度不夠*/
j=0;
while(s1[j]!=’\0’){s=s1[j];i++;j++;}
j=0;
while(s2[j]!=’\0’){s=s2[j];i++;j++;}
s=’\0’;return1;
}
求字串
intStrSub(char*t,char*s,inti,intlen)
/*用t返回串s中第個i字元開始的長度為len的子串1≤i≤串長*/
{intslen;
slen=StrLength(s);
if(islen||lenslen-i+1)
{printf("參數不對");return0;}
for(j=0;j
t[j]=s[i+j-1];
t[j]=’\0’;
return1;
}
串比較
intStrComp(char*s1,char*s2)
{inti=0;
while(s1
==s2&&s1!=’\0’)i++;
return(s1-s2);
}
