Chapter 2 线性表
2-1线性表的基本操作 书2.1.2
InitList(&L); //初始化线性表
Length(L); //求表长，返回表长
LocationElem(L,e); //按值查找，返回关键元素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的数据元素按值非递减排列
归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排
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) //进栈，若栈不满，则加入x，使x成为新的栈顶
- Pop(&S,&x) //出栈，若栈不为空，则删除栈顶元素复制给x，并返回x
- Getop(S,&x) //读出栈顶元素，若栈不为空，则将栈顶元素赋值给x，并返回x
- DestroyStack(&S) //销毁栈
3-2 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数
算法思路，将十进制取模8依次进栈，再输出
void conversion()
{
SqStack s;
unsigned n;
ElemType e;
InitStack(&s);
scanf("%u",&n); //输入非负的十进制数
while(n){ //当n不等于0，所有余数入展
Push(&s,n%8); //入栈（n/8）的余数（8进制的低位）
n=n/8;
}
while(!EmptyStack(S)){ //当栈不为空时
Pop(&s,&e); //将栈元素弹出并赋值给e
printf("%d",e); //输出e
}
printf("\n");
}
3-3 对于输入的字符串检验括号是否成对出现（假设只有())
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) //初始化队列，构造一个空队列
- QueueEmpty(Q) //判断队列是否为空，并返回TRUE或FALSE
- EnQueue(&Q,x) //入队，若队列未满，则将x加入队列成为新的队尾
- DeQueue(&Q,&x) //出队，若队列不空，则删除队头元素，并将队头元素赋值给x返回
- GetHead(Q,&x) //读出队头元素，若队列非空则将队头元素赋值给x并返回
