数据结构知识点总结

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 头指针始终指向队列头元素