【数据结构】考研代码总结-简书(数据结构考研是什么专业)

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(!emptyst

ack(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并返回

chapter 4 树与二叉树