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

来自软件实验室
跳转至: 导航搜索
2.1 线性表的定义
2.2线性表的抽象数据类型
第7行: 第7行:
  
 
== 2.2线性表的抽象数据类型 ==
 
== 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线性表的顺序存储结构 ==

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

2.1 线性表的定义

概念

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

参考资料

[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.4线性表顺序存储结构的插入与删除

2.5线性表的链式存储结构

2.6单链表的读取

2.7单链表的插入与删除

2.8单链表的整表创建

2.9单链表的整表删除