基本数据结构及其运算.ppt

第二章 基本数据结构及其运算 线性表 什么是线性表? 日常生活中常见到表格形式的一类数据 列车时刻表 学生成绩表 周名缩写表 线性表概念 综上所述，线性表是由n（n≥0）个数据元素a1，a2，…，an 组成的一个有限序列。表中的每一个数据元素，除了第一个 外，有且只有一个前件；除了最后一个外，有且只有一个后 件。即线性表或是一个空表，或可以表示为： (a1，a2，…，ai，…，an) 其中ai(i = 1，2，…，n)是属于数据对象的元素，通常也称其 为线性表中的一个结点。 结构特征： ① 有且只有一个根结点a1，它无前件。 ② 有且只有一个终端结点an，它无后件。 ③ 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n = 0时，称为空表。 线性表的存储 在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。顺序存储的线性表通常称为顺序表。 线性表的顺序存储结构具有以下两个基本特点： ① 线性表中所有元素所占的存储空间是连续的。 ② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 线性表的存储 在计算机中的顺 序存储结构 如图所示。 一般来说，设长度为n的线性表为： 要在线性表的第i个元素ai之前插入一个新元素b，插入后得到长度为n + 1的线性表为： 则插入前后的两线性表中的元素满足如下关系： 已知线性表的当前状态是(a1，a2，…，ai-1，ai，…，an)，要在第i个位置插入一个元素x，线性表变为(a1，a2，…，ai-1，x，ai，…，an)。 其实施步骤为： (1) 将第n至第i个元素后移一个存储位置； (2) 将x插入到第i个位置； (3) 线性表的长度加1。 void insl(v,m,n,i,b) /*顺序表的插入*/ ET v[ ],b； /*v为顺序表空间,b为插入的元素*/ int m,*n,i； /*m为顺序表空间容量,n为指向线性表长度的指针, i为插入元素的序号*/ { if (*n==m) /*顺序表空间已满,上溢错误,返回*/ { printf(overflow \n)； return； } if (i＞*n–1) i=*n+1； /*在线性表的最后插入*/ if (i＜1) i=1； /*在线性表的第1个元素之前插入*/ for (j=*n；j＜=i；j– –) /*插入位置以后的元素依次往后移动一个位置*/ v[j]=v[j–1]； v[i–1]=b； /*插入元素b*/ *n= *n+1； /*线性表长度加1*/ return； } 一般来说，设长度为n的线性表为： 现要删除第i个元素，删除后得到长度为n – 1的线性表为： 则删除前后的两线性表中的元素满足如下关系： 已知线性表的当前状态是(a1，a2，…，ai-1，ai，ai+1，…，an)，若要删除第i个元素ai，则线性表成为(a1，a2，…，ai-1，ai+1，…，an)。 具体实施步骤为： (1) 若i值合法，则将第i+1至第n个位置上的元素依次向前移动一个存储单位； (2) 将线性表的长度减1。 void desl(v,m,n,i) /*顺序表的删除*/ ET v[ ]； /*顺序表空间*/ int m,*n,i； /*m为顺序表空间容量,n为指向线性表长度的指针, i为删除元素的序号*/ { if (*n==0) /*线性表为空,下溢错误,返回*/ printf(underflow \n)； return； } if ((i＜1) | | (i＞*n)) /*线性表中没有这种下标的元素,返回*/ printf(Not this element in the list \n)； return； } for (j=i；j＜=*n–1；j++＝ ) /*第i个以后的元素依次往前移动一个位置*/ v[j–1]=v[j]； *n= *n–1； /*线性表长度减1*/ return； } 算法性能分析 在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位置。 假设在第i个元素之前插入一个新元素的概率为1/(n+1)，即在表的任何位置(包括an之后)插入新元素的概率是相等的，则插入操作