线性表-栈-队

栈 1.6栈的应用
运算符的优先级关系表在运算过程中非常重要，它是判定进栈、出栈的重要依据。
θ1
θ2
+
-
+
>
>
-
>
>
*
>
>
/
>
>
(
<
<
)
>
>
#
<
<
*
/
(
)
#
<
<
<
>
>
<
<
<
>
>
>
>
<
>
>
>
>
<
>
>
<
<
<
=
>
>
>
>
<
<
<
=
栈
1.6栈的应用
下面以分析表达式 4+2*3-12/(7-5)为例来说明求解过程，从而总结出表达式求值的算 法。求解中设置两个栈：操作数栈和运算符栈。从左至右扫描表达式：# 4+2*3-12/(7-5) #， 最左边是开始符，最右边是结束符。表达式求值的过程如下表所示：
1.4栈的顺序存储结构
设计进栈算法——Push 函数。首先，判断栈是否已满，如果栈已满，就运用 realloc 函 数重新开辟更大的栈空间。如果 realloc 函数返回值为空，提示溢出，则更新栈的地址以及栈 的当前空间大小。最终，新元素入栈，栈顶标识 top 加 1。

3.
索引存储的优点
查寻某个结点k，无须遍查F中的所有结点。 只需根据结点k的性质p，计算索引函数求 得i，从索引表中找到结点xi，得到子线性 表Fi的首地址。然后在线性表Fi中查找这 个结点k。
1.6.2 索引存储
4. 存储方法 （1）顺序-索引-链接，即索引表为顺序存储， 子线性表为链接存储。（常用） （2）顺序-索引-顺序，即索引表与子线性表 均为顺序存储。 （3）链接-索引-链接，即索引表与子线性表 均为链接存储。 （4）链接-索引-顺序，即索引表为链接存储， 子线性表为顺序存储。
1.6.3 散列存储
1.
概念 散列存储（也称Hash存储），通过对结点的 键值作某种运算来确定具有此结点的存放位置。 设有线性表F=(k0, k1, …, kn-1)和数组T[m]， 而结点ki的键值为keyi，若h(x)是键值集合到 整数0至m-1的一个一一对应函数。对于任意 结点ki在数组T[m]中的存放位置由h(keyi)决定， 这种存放结点的方法，称为散列（Hash）存储。 函数h(x)为散列函数，数组T[m]为散列表。
9
1.6.3 散列存储
2.
问题 （1）难于选取一个从键值集合到散列表地 址空间的一一对应的函数h(x)，即对于 keyi≠keyj，有可能h(keyi)=h(keyj)。这种 情况称为冲突。 （2）一旦有冲突，应选取怎样的解决方法？
这些问题留待以后解决。
0 7 78
12 9
2
-9
4 11 93
3 ^
-61
1.6.1 线性表的压缩存储
3.
压缩存储的优缺点 优点：当相同取值的结点数量较多时， 可节省存储空间。 缺点：给定序号，要求查寻相应结点， 比较困难。对于顺序存储，可用两分查 找法；对于链接存储，就需扫描几乎全 部结点。

while( p !=NULL && j < i ) { p=p->link; j++; } // 指向第i结点，i＝0,1,…，当链表 //中结点数小于i时返回NULL return p; }
单链表插入算法
// 插入数据内容为value的新结点，为第i个 结点。 ListNode * Insert(ELEM value, int i) { ListNode *p，*q; q = new ListNode; p = FindIndex(i-1); if(p == NULL ) return NULL;
}
2.2.2

Байду номын сангаас
向量的运算
插入元素运算

void insert( item) ELEM remove( )

删除元素运算

插入算法
/*（设元素的类型为ELEM，nodelist是存储顺序表的 向量， msize 是此向量的最大长度， curr_len 是此向 量的当前长度，curr为此向量当前下标）*/ ＃include <assert.h> viod insert(ELEM item) { //需要检查当前长度不能等于msize，当前游标指针 //curr不能小于0,也不能大于当前长度
q->link = p->link; q->data = value; p->link = q; if(q->link == NULL ) last=q; return q;
}
插入过程
单链表删除算法
//删除由参数link所指定的结点
void RemoveAfter(ListNode * link) { ListNode *newlink=link; if(link!=NULL) link=link->link; delete newlink; }

②X=S[TOP]，（退栈后的元素赋给X）； ③TOP--，结束（栈指针减１，指向栈顶）。
栈的应用 十进制数N和其它d进制数的转换是实现计算的基本问题，
解决方法很多，下面给出一种算法原理： N=(N / d)×d＋N % d （其中 / 为整除运算，%为求余运算）。
例如：(1348)10＝(2504)8运算过程如下：
default:x=0; while (s[i]!=' ') x=x*10+s[i++]-'0'; stack[++top]=x;
break;
}
i++;
}
//while
return stack[top];
}
main() {
printf("input a string(@_over):"); gets(s); printf("result=%d",comp(s)); return 0; }
cout<<"Please enter a number(N) base 10:"; cin>>n; cout<<"please enter a number(d):"; cin>>d; do{
a[++i]=n%d; n=n/d; }while(n!=0); for (j=i;j>=1;j--)cout<<a[j]; return 0; }
集合
• 数据元素的物理结构有两种：顺序存储结构和链 式存储结构
• 顺序存储结构:用数据元素在存储器中的相对位 置来表示数据元素之间的逻辑关系。