数据结构知识点总结

p -> next ? q;

q ? p;

}

return ( p );

}

有一个单链表(不同结点的数据域值可能相同),其头指针为head,编写

一个函数计算数据域为x的结点个数。链表节点结构定义如下:

data next 解:遍历该链表的每个结点,每遇到一个结点,判断其值是否为x,是的话就计数。结点个数存储在变量n中。算法如下:

int Counter(head, x) {

int n = 0; p <= head; while ( p != NULL ) {

if (p->data = x )

n <= n + 1;

p <= p -> next; } return ( n ); }

-------------------------------------------------------------------------------

栈和队列

栈:限定仅在表尾进行插入或删除

栈:是限定仅在表尾进行插入或删除操作的线性表 表尾(栈顶) 表头(栈底)

假设栈S=(a1,a2,…,an),则称a1为栈底元素,an为栈顶元素。栈中元素按a1,a2,…,an的次序进栈,退栈的第一元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈又称为后进后出的线性表。

压栈算法:int PushStack(s[],top,x) {

if(top>=SMAX) {

printf(\return 0;

} else { } }

出栈算法:

ElemType Popstack(s[],top,bottom) {

if(top<=bottom) { } } else {

top<=top-1; y<=S[top]; return y; return 0;

printf(\S[top]<=x; top=top++;

}

作业2:为了节省空间,两个栈共享一段内存,写出这两个栈的压栈及出栈算法。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续地内存空间时,应将两栈的栈底,分别设在这片内存空间的两端,这样,当两个栈的栈顶在栈空间的某一位置相遇时,才会产生上溢。

两个栈共享空间的条件:两栈顶指针值相减的绝对值为1(两栈顶指针相邻) 数组Q[0..n-1]作为一个环形队列,f为当前队头元素的前一位置,r 为队尾元素的位置,假定队列中元素的个数总小于 n,计算队列中元素个数的公式是 (n+r-f) mod

队列特点:先进先出,队头出,队尾进,当队尾大于队头时,说明进的比出的多,此时元素个数为Rear – Front

循环队列用数组A[0..m-1]存放其元素值,已知其头尾指针分别是front和rear,则当前队列中的元素个数是(rear-front+m) MOD m

循环队列两指针front指示队列头元素位置rear指示队列尾元素位置 初始化建空队列时,令front=rear=0,插入新的尾元素->尾指针+1;删除队列头元素->头指针+1 头指针始终指向队列头元素

联系客服:779662525#qq.com(#替换为@)