“2线性表”的版本间的差异

来自软件实验室
跳转至: 导航搜索
2.3.2顺序存储方式
概念
第3行: 第3行:
 
线性表是最基本、最简单、也是最常用的一种数据结构。在线性表中数据元素之间的关系是线性,数据元素可以看成是排列在一条线上或一个环上。
 
线性表是最基本、最简单、也是最常用的一种数据结构。在线性表中数据元素之间的关系是线性,数据元素可以看成是排列在一条线上或一个环上。
 
线性表分为静态线性表和动态线性表,常见的有顺序表(静态的)、单向链表(动态的)和双向链表(动态的)。
 
线性表分为静态线性表和动态线性表,常见的有顺序表(静态的)、单向链表(动态的)和双向链表(动态的)。
 +
[[File:线性表.png|options|caption]]
 +
 
=== 参考资料 ===
 
=== 参考资料 ===
 
[http://blog.csdn.net/luoweifu/article/details/8505178]
 
[http://blog.csdn.net/luoweifu/article/details/8505178]

2016年4月11日 (一) 22:32的版本

2.1 线性表的定义

概念

线性表是最基本、最简单、也是最常用的一种数据结构。在线性表中数据元素之间的关系是线性,数据元素可以看成是排列在一条线上或一个环上。 线性表分为静态线性表和动态线性表,常见的有顺序表(静态的)、单向链表(动态的)和双向链表(动态的)。 caption

参考资料

[1]

2.2线性表的抽象数据类型

定义

ADT 线性表 (List) Data Operation

   void initList(*L);	//创建并初始化一个空线性表,如果成功返回true,修改表传指针   
   bool listEmpty(L);	//判断一个线性表是否为空,不修改表传值   
   void clearList(*L);	//清空一个线性表,成功返回true   
   bool getElem(L,i,*e);	//从某个位置取出元素并赋值给e(i的范围是[1,L.length]),修改e的值所以传递一个指针,成功返回true  
   int locateElem(L,e);	//查找线性表中是否有e,如果有返回它的位置(从1开始),否则返回0表示失败  
   bool listInsert(*L,i,e);	//插入一个元素e在第i个元素之前(i的取值范围是[1,L.length+1]) ,成功返回true   
   bool listDelete(*L,i,*e);	//删除在第i个位置上的元素(i的取值范围是[1,L.length]),删除的元素赋给e,成功返回true  
   int listLength(L);	//返回线性表的元素个数  

endADT

举例

比如,要实现两个线性表集合A和B的并集操作。即要使得集合A=AUB。说白了,就是把存在集合B中但并不存在A中的数据元素插入到A中即可。

仔细分析一下这个操作,发现我们只要循环集合B中的毎个元素,判断当前元素是否存在A中,若不存在,则插入到A中即可。思路应该是很容易想到的。

void unionL(List *la,List lb){

   int index;  
   int laLength = listLength(*la);	//得到a的长度,需要一个线性表而不是一个地址   
   int lbLength = listLength(lb);}   
   ElemType e;	//声明一个元素   
     
   for(index=1;index<=lbLength;index++){	//遍历lb   
       getElem(lb,index,&e);	//依次得到lb中的元素   
       if(!locateElem(*la,e)){	//检查是否在la中出现   
           listInsert(la,++laLength,e);	//没有出现则插入队尾,前自增!   
       }  
   }  

}

2.3线性表的顺序存储结构

2.3.1定义

线性表的顺序存储是指用一组地址连续的存储单元一次存储线性表的数据元素。在C语言中,可以使用动态数组来实现线性表的顺序存储。

2.3.2顺序存储方式

结构代码示例:

   #define MAXLENGTH 20  /*存储空间初始分配量*/
     
   struct sequencelist  
   {  
       int data[MAXLENGTH];  /*数组存储数据元素,最大值为MAXSIZE*/
       int length;  /*线性表当前长度*/
   };

2.3.3数据长度与线性表长度的区别

2.3.4地址计算方法

2.4线性表顺序存储结构的插入与删除

2.5线性表的链式存储结构

2.6单链表的读取

2.7单链表的插入与删除

2.8单链表的整表创建

2.9单链表的整表删除