-
基本運算
鎖定
- 中文名
- 基本運算
- 外文名
- Basic operation
- 應用學科
- 數學
- 基本概念
- 指執行運算最基礎的算法
- 種 類
- 並、差、投影、選擇、笛卡爾積
- 屬 性
- 基礎算法
基本運算基本運算
傳統的集合運算
選擇運算
從關係中找出滿足給定條件的那些元組稱為選擇。其中的條件是以邏輯表達式給出的，值為真的元組將被選取。這種運算是從水平方向抽取元組。在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;
}
注意：
基本運算定長順序串
基本運算串聯接
把兩個串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);
}
