首页 > 代码库 > 数据结构之线性表1概括

数据结构之线性表1概括

线性表

1.线性表(LinearList)是由n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1]组成的有限序列。

其中:数据元素的个数n定义为表的长度 ="list".length() ("list".length() = 0(表里没有一个元素)时称为空表)

将非空的线性表(n>=0)记作:(a[0],a[1],a[2],…,a[n-1])

数据元素a[i](0≤i≤n-1)只是个抽象符号,其具体含义在不同情况下可以不同

一个数据元素可以由若干个数据项组成。数据元素称为记录,含有大量记录的线性表又称为文件。这种结构具有下列特点:存在一个唯一的没有前驱的(头)数据元素;存在一个唯一的没有后继的(尾)数据元素;此外,每一个数据元素均有一个直接前驱和一个直接后继数据元素。

2.线性表的基本操作
1)MakeEmpty(L) 这是一个将L变为空表的方法
2)Length(L) 返回表L的长度,即表中元素个数
3)Get(L,i) 这是一个函数,函数值为L中位置i处的元素(1≤i≤n)
4)Prev(L,i) 取i的前驱元素
5)Next(L,i) 取i的后继元素
6)Locate(L,x) 这是一个函数,函数值为元素x在L中的位置
7)Insert(L,i,x)在表L的位置i处插入元素x,将原占据位置i的元素及后面的元素都向后推一个位置
8)Delete(L,p) 从表L中删除位置p处的元素
9)IsEmpty(L) 如果表L为空表(长度为0)则返回true,否则返回false
10)Clear(L)清除所有元素
11)Init(L)同第一个,初始化线性表为空
12)Traverse(L)遍历输出所有元素
13)Find(L,x)查找并返回元素
14)Update(L,x)修改元素
15)Sort(L)对所有元素重新按给定的条件排序
16) strstr(string1,string2)用于字符数组的求string1中出现string2的首地址

3.线性表的存储结构  

a顺序表

b链表

  b1 单链表

     b11 动态单链表

      b12静态单链表

b2 双链表

c循环链表

      单循环链表

      双循环链表

数据结构之线性表1概括