2014-21线性表(4h)解答.pptVIP

2.1 数据结构的基本概念;二. 数据的逻辑结构;例子1;1. 顺序存储结构;2. 链式存储结构; 总结： （1）逻辑结构和物理结构的关系;2.1.3 线性结构（线性表）; 一个线性结构中插入和删除任何一个结点后还是线性结构。;空数据结构;1. 什么是线性表;非空线性表结构特征; ;2. 特点;程序代码; 线性表顺序存储下插入运算;;template typename T//参考教材P25 void ins_sq_LList (T* v, int m, int*n ;int i; T b ) //在表中第 i 个位置插入新元素 b { int k; if( *n == m){ cout “overflow”endl; reurn;} if( i *n) i = *n+1; if(i 1) i = 1; for( k = *n ; k = i ; k --) v[k] = v[k-1]; v[ i -1 ] =b; *n=*n +1; return; };线性表顺序存储下删除运算;表项的删除; template class T void del_sq_LList ( T* v ,int m ,int *n ,int i) { //在表中删除已有第i元素 参考教材P27 int k; if (*n== 0) { cout“under flow” endl; return; } if(i1 || i * n){cout“under flow” endl; return; } for( k =i; k *n; k ++) v[k-1] =v[k]; *n =*n -1; return ; };总结：顺序存储结构的优缺点;顺序表类;课堂练习;;堆栈(Stack) 栈是允许在同一端进行插入和删除操作的特殊线性表。 允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动； 栈中元素个数为零时称为空栈。 栈结构也称为后进先出表（LIFO）。 ;栈有关概念 ;2 栈的顺序存储及其运算;template class T class sq_stack { private: int top; //栈顶指针 T *s; //栈元素数组 int mm; //栈最大容量 public: void prt_sq_Stack () ; int flag_sq_Stack(); void ins_sq_Stack() //入栈 push T del_sq_Stack ( ); //出栈 pop T read_sq_stack ( ); //取栈顶 top } ;栈操作举例;进栈算法;void sq_StackT::push（T x） { if (top ＝＝ m ） { cout (“Stack－overflow＼n”)； return； } top＝top+1； s[top-1］=x； return； };出栈算法;T sq_StackT:: pop（） { T y; if (top == 0) {cout “Stack-underflow\n”；return；} y=s[top-1]； top=top-1； return (y)； };课堂练习 ;表达式计算;计算表达式算法步骤; 1 ; 3 PUSH（OPND，3） 2 ; 3 + PUSH（OPTR，‘+’） 3 ;+ 3 2 PUSH（OPTD，‘2’） 4 ;+ 3,2 * PUSH（OPNR，*） 5 ;+* 3,2 7