Chapter 2 線性表
2-1線性表的基本操作 書2.1.2
InitList(&L); //初始化線性表
Length(L); //求表長配乓，返回表長
LocationElem(L,e); //按值查找起宽，返回關(guān)鍵元素e的位置
GetElement(L,i); //按位查找浆兰，范圍指定位置元素值
ListInsert(&L,i,e); //指定位置i插入指定的元素
ListDelete(&L,i,&e);//刪除指定位置i的值撞叨，并用e返回被刪除元素值
PrintList(L); //輸出鏈表值
Empty(L); //判斷量表是否為空惜犀，并返回TRUE或FALSE
DestroyList(&L);//銷毀線性表尘奏，釋放線性表所占的空間
2-2將La表與Lb表合并到La表中
void Union(SqList *La, SqList Lb){
ElemType e;
int La_len,Lb_len;
int i;
//求兩個線性表的長度
La_len = ListLength(*La);
Lb_len = ListLength(Lb);
for(i = 1; i < Lb_len; i++){
e = GetElement(Lb,i); //將第i個元素取出并賦值給e,每次變量e的值都會被修改
if(!LocationElem(*La,e)) //在A中沒有找到B的元素牙甫，則插入
ListInsert(La,++La_len,e); //在La的末尾插入
}//for
}
2-3已知線性表La和Lb的數(shù)據(jù)元素按值非遞減排列
歸并La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素也按值非遞減排
void MergeList(SqList La, SqList Lb, SqList *Lc)
{
int i = 1, j = 1, k = 0;
int La_len, Lb_len;
ElemType ai,bj;
InitList(Lc);
//求兩個線性表的長度
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while(i <= La_len && j <= Lb_len){
ai = GetElement(La,i);
bj = GetElement(Lb,j);
if(ai <= bj){
ListInsert(Lc, ++k, ai);
++i;
}
else{
ListInsert(Lc, ++k, bj);
++j;
}
while( i <= La_len) //表La非空且表Lb空
{
ai = GetElement(La, i++);
ListInsert(Lc, ++k, ai);
}
while( i <= La_len) //表La非空且表Lb空
{
ai = GetElement(La, i++);
ListInsert(Lc, ++k, ai);
}
}
}
Chapter 3 棧和隊列
3-1 棧的基本操作
- InitStack(&S) //初始化一個空棧
- StackEmpty(S) //判斷一個棧是否為空掷酗，返回
- Push(&S,x) //進(jìn)棧，若棧不滿窟哺，則加入x泻轰，使x成為新的棧頂
- Pop(&S,&x) //出棧，若棧不為空且轨，則刪除棧頂元素復(fù)制給x浮声，并返回x
- Getop(S,&x) //讀出棧頂元素虚婿，若棧不為空，則將棧頂元素賦值給x泳挥，并返回x
- DestroyStack(&S) //銷毀棧
3-2 對于輸入的任意一個非負(fù)十進(jìn)制整數(shù)然痊，打印輸出與其等值的八進(jìn)制數(shù)
算法思路，將十進(jìn)制取模8依次進(jìn)棧屉符，再輸出
void conversion()
{
SqStack s;
unsigned n;
ElemType e;
InitStack(&s);
scanf("%u",&n); //輸入非負(fù)的十進(jìn)制數(shù)
while(n){ //當(dāng)n不等于0剧浸，所有余數(shù)入展
Push(&s,n%8); //入棧（n/8）的余數(shù)（8進(jìn)制的低位）
n=n/8;
}
while(!EmptyStack(S)){ //當(dāng)棧不為空時
Pop(&s,&e); //將棧元素彈出并賦值給e
printf("%d",e); //輸出e
}
printf("\n");
}
3-3 對于輸入的字符串檢驗括號是否成對出現(xiàn)（假設(shè)只有())
bool Match(char exp[],int n)
{
int i = 0;
char e;
bool match = true;
LinkStNode *st;
while(i < n && match){
if(exp[i]=='(')
Push(st,exp[i]);
else if(exp[i]==')'){
if(GetTop(st,e)==true){
if(e!='(')
match = false;
else
Pop(st,e)
}
else match = false;
}
i++;
}
if(!StackEmpty(st))
match = false;
DestroyStack(st);
return match;
}
3-4 隊列的基本操作
- InitQueue(&Q) //初始化隊列，構(gòu)造一個空隊列
- QueueEmpty(Q) //判斷隊列是否為空矗钟，并返回TRUE或FALSE
- EnQueue(&Q,x) //入隊唆香，若隊列未滿，則將x加入隊列成為新的隊尾
- DeQueue(&Q,&x) //出隊吨艇，若隊列不空躬它，則刪除隊頭元素，并將隊頭元素賦值給x返回
- GetHead(Q,&x) //讀出隊頭元素秸应，若隊列非空則將隊頭元素賦值給x并返回
