数据结构三(线性表)

2016-09-18 本文已影响343人 e40c669177be

1.线性表的定义

线性表:零个或多个数据元素的有限序列
序列:也就是说元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他的每个元素都有且只有一个前驱和后继
定义:
若将线性表记为(a1, a2......ai-1,ai,ai+ 1,.....an),则表中ai-1领先于ai,ai领先于ai+ 1,称ai -1 为ai的前驱,ai + 1为ai的后继.当i = 1, 2....n- 1,ai有且只有一个直接后继,当i = 2,3,.....n时,ai有且只有一个直接前驱

线性表元素的个数n(n >= 0)定义为线性表的长度,当n= 0时,成为空表.

在较复杂的线性表中,一个数据元素可以由若干个数据项组成.

2.线性表的抽象数据类型

ADT 线性表(list)
Data 线性表的数据对象集合为(a1,a2,....an),每个元素的类型均为DataType
Operation
InitList(L):初始化操作,建立一个空的线性表L
ListEmpty(L):若线性表为空,返回true,否则返回false
ClearList(L):将线性表清空
GetElem(L,i,e):将线性表L中的第i个位置元素值返回给e
LocateElem(L,e):线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功,否则,返回0表示失败
ListInsert(L.i.e):在线性表L中的第i个元素插入新元素e
ListDelete(L,u,e):删除线性表L中的第i个元素,并用e返回其值
ListLength(L):返回线性表L的元素个数
endADT

实现两个线性集合A和B的并集操作,即A = A U B,就是把集合B中但并不存在A中的数据元素插入到A中即可.
操作:

1.循环集合B中的每个元素
2.判断当前元素是否存在A中

3.若不存在,则插入到A中即可

La表示集合A,Lb表示集合B
//将所有的在线性表Lb中,但不在La中的数据元素插入到La中
void union(List *La,List Lb){
int La_len ,Lb_len , i;
ElemType e;  //声明与La和Lb相同的数据元素e
La_len = ListLength(La);//线性表的长度
Lb_len = ListLength(Lb);
for (i = 1; i <= Lb_len;i++){
    GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e
    if (!LocateElem(La,e,equal))//La中不存在和e相同的数据元素
        ListInsert(La,++La_len,e);//插入
   }
}

3.线性表的顺序存储结构

线性表的两种物理结构的第一种----顺序存储结构
线性表的顺序存储结构:指的是用一段地址连续的存储单元依次存储线性表的数据元素

顺序存储结构示意图

#define MAXSIZE 20;//存储空间初始分配量
typedef int ElemType; //ElemType类型根据实际情况而定,这里假设为int 
  typeded struct{
  ElemType data[MAXSIZE];//数组存储数据元素,最大值为MAXSIZE
 int length;//线性表当前元素
}Sqlist;

顺序存储结构需要三个属性:

存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置
线性表的最大存储容量:数组长度MAXSIZE
线性表的当前长度 :length

3.1.数据长度与线性表长度的区别

数据长度:是存放线性表的存储空间的长度,存储分配后这个量是一般不变的
线性表的长度:线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的
在任意时刻,线性表的长度应该小于等于数组的长度

3.2.地址计算方法

LOC(ai) = LOC(a1) + (i - 1) *c
c是占用存储单元
线性表的起始为1
C语言中数组是从0开始的

地址计算

他的存储时间性能为O(1),我们通常把这一特点的存储结构为随机存储结构

3.3.顺序存储结构的插入与删除

3.3.1获取元素操作

只要i的数组在数组下标范围内,就把数组第i- 1下标的值返回即可

#define OK 0
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//Status 是函数的类型,其值是函数结果状态代码.如OK等
//初始条件:顺序线性表L已存储,1<= i <= LIstLength (L)
//操作结果:用e返回L中第i个数据元素的值
Status GetElem (Sqlist L,int i ,ElemType *e){
  if (L.length == 0 || i < 1 || i > L.length)
  return ERROR
  *e = L.data(i - 1);
  return OK;
 }

3.3.2插入操作

** 插入算法的思路:**

如果插入的位置不合理,抛出异常
如果线性表长度大于等于数组长度,则抛出异常或动态增加容量
从最后一个元素开始向前遍历到第i个位置,分别将他们都向后移动一个位置
将要插入元素填入位置i处

表长 + 1

//初始化条件:顺序线性表L已存在,1<= i <= ListLengt(L)
//操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
Status ListInsert (Sqlist *L,int i,ElemType e){
  int k;
  if( L -> length == MAXSIZE)//顺序线性表已满
    return ERROR;
  if (i < 1 || i > L -> length + 1)//当i不在范围内
        for(k = L-> length- 1; k >= i - 1; k--)//将要插入位置后数据元素向后移动一位
        L->data[k + 1] = L ->data[k];
      }
    L->data[i - 1] = e;
    L->length++;
    return OK;
}

3.3.3删除操作

删除操作思路

如果删除位置不合理,抛出异常
取出删除元素
从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置

表长 -1

//初始化条件:顺序线性表已存在,1 <= i<= ListLength(L)
//操作结果:删除L的第i个数据元素,并用e返回其值,L的长度-1
  Status ListDelete (Sqlist *L,int i ,ElemType *e){
    int k;
    if (L->length == 0) //线性表为空
          return ERROR;
    if (i < 1 || i > L->length)//删除位置不正确
            return ERROR;
     *e = L->data[i - 1];
     if (i < L->length)//如果删除的不是最后位置
      {
            for (k = i ; k < L->length ; k++)  //将删除位置后元素前移
            L->data[k - 1] = L->data[k];
        }
      L ->length--;//线性表长度-1
      return OK;
}

3.3.4插入和删除的时间复杂度

最好情况:插入和删除的都在最后一个元素,此时时间复杂度为 O(1)
最坏情况:插入和删除的都是第一个元素,移动所有的元素,时间复杂度为O(n)
平均情况:次数为(n- 1)/ 2,时间复杂度还是O(n)

3.3.5线性存储结构的优缺点

优点:
1)无须为表示表中元素之间的逻辑顺序而增加额外的存储空间
2)可以快速地存储表中任何一个位置的元素
缺点:
1)插入和删除操作需要移动大量元素
2)当线性表长度变化较大时,难以确定存储空间的容量
3)造成存储空间的"碎片"

3.4线性表的链式存储结构

为了解决线性表的顺序存储结构,插入数据需要移动大量的元素,而存在的线性表链式存储结构
定义: 为了表示每个数据元素ai与其直接后继数据元素ai+ 1之间的逻辑关系.对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其后继的信息(即直接后继的存储位置).我们把存储数据元素信息的域称为数据域,把存储后继的位置的域称为指针域.指针域中存储的信息称做指针或链.这两部分信息组成的元素ai的存储映像,称为结点
n个结点(ai的存储映像)链结成一个链表,即为线性表(a1,a2,...an)的链式存储结构,因为此链表的每个结点中只包含一个指针域,所有叫做单链表

单链表

单链表通过每个结点的指针域将线性表的数据元素按其逻辑顺序依次链接在一起.

链表中第一个结点的存储位置叫做头指针,整个链表的存储必须是从头指针开始进行的,之后的每一个结点,其实就是上一个的后继指针指向的位置.最后一个,其后继不存在,我们规定,线性链表的最后一个结点指针为''空"(通常用NULL或"^"表示)

单链表的结构

为了更方便的进行指针的操作,我们会在单链表的第一个结点附近设置一个结点,称为头结点.头结点的数据域可以不存储任何信息,也可以存储线性表的程度长度等附加信息,头结点的指针域指向第一个结点的指针

屏幕快照 2016-09-18 下午1.37.47.png

3.5头指针与头结点的异同

头指针:
1)头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针
2)头指针具有标识作用,所以常常用头指针冠宇链表的名字
3)无聊链表是否为空,头指针均不为空.头指针是链表的必要元素
头结点:
1)头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度)
2)有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其它结点的操作就统一了
3)头结点不一定是链表必须要素

3.6线性表链式存储结构描述

1.线性表为空

空链表

单链表

带有头结点的单链接

空的单链表

//线性表的单链表存储结构
typedef struct Node{
 ElemType data;
 struct Node *next;
}Node;
typedef struct Node *LinkList;//定义LinkList

由这个结构的定义中,我们知道,结点由存放数据元素的数据域,存放后继结点的指针的指针域组成
假设p是指向线性表第i个元素的指针,则
该结点ai的数据域用p->data来表示
p->data的值是一个数据元素
结点ai的指针域可以用p->next表示,
p->next的值是一个指针
p->next指向第i+1个元素,即指向ai+1的指针.也就是说 p->data = ai;
p->next ->data = ai+ 1;

屏幕快照 2016-09-18 下午2.04.21.png

3.7单链表的读取

获取链表第i个数据的算法思路

1.声明一个结点p指向链表的第一个结点,初始化j 从1开始
2.当j < i,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
3.若到链表末尾p为空,说明第i个元素不存在

4.否则查找成功返回结点p的数据

//初始化条件:顺序线性表L已存在,1<= i <=ListLength(L)
//操作结果:用e返回L中第i个数据元素的值
Status GetElem(LinkList L , int i ,ElemType *e){
int j ;
LinkList p ;//声明一结点p 
p = L ->next;//让p指向链表L的第一个结点
j = 1;//j为计数器
while(p && j < i)//p不为空或者计数器j还没有等于i时,循环继续
{
   p  = p ->next;//让p指向下一个结点
  ++j;
}
if (!p || j > i)
      return ERROR;//第i个元素不存在
*e = p ->data;//取第i个元素的数据
return OK;
}

单链表的最坏时间复杂度是O(n)
因为单链表的结构定义中没有定义表长,所以实现不知道循环多少次,因此不方便使用for来循环控制,其主要核心思想是"工作指针后移"

3.7单链表的插入与删除

3.71单链表的插入

单链表的插入

只需要让s->next = p->next,p->next = s即可

插入

插入后
单链表第i个数据插入节点的算法思想

1.声明一结点p指向链表第一个结点,初始化j 从1开始
2.当j < i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;
3.若到链表末尾p为空,说明第i个元素不存在
4.否则查找成功,在系统中生成一个空结点s;
5.将数据元素e赋值给s->data
6.单链表的插入标准语句s->next = p->next,p->next = s;

7.返回成功

//初始化条件:顺序线性表L已存在,1<= i<=ListLength(L)
//操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
Status ListInsert (LinkList *L, int i,Element e)
  {
        int j ;
        LinkList p,s;
        P = *L;
        j = 1;
        while(p && j < i){
            p = p -> next;
            j++;
        }
        if (!p || j > i){
             return ERROR;
        s = (LinkList)malloc(sizeof(Node));//生成新的结点
        s -> data = e;
        s -> next = p -> next;//将p的后继结点赋值给s的后继
        p ->next = s;   //将s赋值给p的后继
        return OK;
   }

3.72单链表的删除

单链表的删除

实际上就一步 ,p->next = p ->next -> next,用q 来取代p ->next即

q = p -> next, p -> next = q -> next;

单链表第i个数据删除结点的算法思路

1.声明一结点p指向链表第一个结点,初始化j从1开始
2.当j < i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j 累加1
3.若到链表末尾p为空,则说明第i个元素不存在
4.否则查找成功,将欲删除结点p->next赋值给q
5.单链表的删除标准语句 p->next = q -> next
6.将q结点中的数据赋值给e,作为返回
7.释放q结点

8.返回成功

//初始条件:顺序线性表L已存储, 1<= i<= ListLength(L)
//操作结果:删除L的第i个数据元素,并用e返回其值,L的长度- 1
Status ListDelete ( LinkList *L , ElemType *e)
 {
        int j ;
        LinkList p,q;
        p = *L;
        j = 1;
        while (p -> next && j < 1)//遍历寻找第i个元素
        {
              p = p -> next;
              ++j;
          }
          if (!(p -> next )|| j > i)
                return ERROR;
            q = p ->next;
            p -> next = q -> next;//将q的后继赋值给p的后继
          *e = q -> data;
          free(q);
         return OK;
   }  
    对于插入或删除数据越频繁的操作,单链表的效率优势就越明显

3.73单链表的创建

思路:

1.声明一结点p和计数器变量i
2.初始化一空链表L
3.让L的头结点的指针指向NULL ,即建立一个带头结点的单链表

4.循环
1)生成一新结点赋值给p
2)随机生成一数字赋值给p的数据域p -> data;
3)将p插入到头结点与前一新结点之间

//随机产生n个元素的值,建立带表头结点的单链线性表L(头插法)
void CreateListHead (LinkList *L, int n){
 LinkList p;
  int i ;
  srand(time (0));//初始化随机数
  *L = (LinkList)malloc (sizeof(Node));
  (*L) ->next = NULL;//先建立一个带头结点的单链表
  for (i = 0 ; i< n; i++)
   {
        p = (LinkList)malloc(sizeof(Node));//生成新的结点
        p -> data = rand() % 100 + 1;//随机生成100以内的数字
        p -> next = (* L)-> next;
        (*L) -> next = p;//插入到表头
      }
}

始终让新结点在第一位置,称为头插法

头插法

我们也可以把每次新结点都插在终端结点的后面,我们称为尾插法

//随机产生n个元素的值,建立带表头结点的单链线性表L(尾插法)

void  CreateListTail(LinkList *L , int n){
      LinkList p,r;
      int i;
      srand(time(0));
      *L = (LinkList)malloc(sizeof(Node));
      r = *L;//r为指向尾部的结点
      for (i = 0 ; i < n; i++){
            p = (Node *)malloc(sizeof(Node));
           p ->data = rang() % 100 + 1;
            r -> next = p;//将表尾终端结点的指针指向新结点
            r = p;//将当前的新结点定义为表尾终端指针
          }
      r -> next = NULL;//表示当前链表结束
    }

3.74单链表的整表删除

单链表的整表删除思路:

1.声明一结点p 和q
2.将第一结点赋值为p

3.循环:
1)将下一结点赋值给q
2)释放p
3)将q赋值给p

//初始条件:顺序线性表L已存在
//操作结果:将L重置为空表
 Status ClearList (LinkList *L){
        LinkList p ,q;
        p = (*L) -> next;//p指向第一个结点
        while(p){
              q = p -> next;
              free(p);
              p = q;
        }
      (*L) -> next =  NULL;//头结点指针域为空
        return OK;
 }

3.8单链表结构与顺序存储结构优缺点

存储分配方式:
1)顺序存储结构用一段连续的存储单元移除存储线性表的数据元素
2)单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素
时间性能
1)查找

顺序存储结构O(1)
单链表 O(n)
2)插入和删除
顺序存储结构需要平均移动表长一半的元素,时间为O(n)
单链表在线出某位置指针后,插入和删除时间仅为O(1)
3)空间性能
顺序存储结构需要预分配存储空间,分大了,浪费,分小了,易发生上溢
单链表不需要分配存储空间,只要有就可以分配,元素个数不受限制

3.9循环链表

将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链接,简称循环链表

空链表

非空的循环链表

与单链表的主要差异就是在循环判断条件上,原来判断p-> next 是否为空,现在则是p->next不等于头结点,循环未结束

用O(1)的时间由链表指针访问最后一个结点.我们需要改造下这个循环链表,不用头指针,而是用指向终端结点的尾指针来表示循环链表,这样查找开始结点和终端结点就很方便了
终端结点用尾指针rear指示.开始结点:rear ->next -> next,时间复杂度也是O(1)
链表的合并

链表的合并

p = rearA  ->next;//保存A表的头结点,即1
rearA ->next = rearB -> next ->next;//将本是指向B表的第一个结点(不是头结点)赋值给reaA -> next
rearB -> next = p;//将原A表的头结点赋值给rearB
free(p);

3.10双向链表

双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域

双向链表的存储结构
typedef struct DulNode{
    ElemType data;
    struct DulNode *prior;//直接前驱指针
    struct DulNode *next;..直接后继指针
    }DulNode , *DuLinkList;

双向链表的空链表 ![Uploading 屏幕快照 2016-09-18 下午4.45.46_357213.png . . .]

非空循环的双向链表

双向链表他的后继的前驱是他自己,他的前驱的后继也是他自己

p -> next -> prior = p = p -> prior -> next

3.10.1双向链表的插入

插入

s -> prior = p ;//把p赋值给s的前驱,如图中1
s ->next = p -> next;//把p->next赋值给s的后继,如图中2
p-> next -> prior = s;//把s赋值给p->next的前驱,如图3
p -> next = s;//把s赋值给p的后继,如图4

3.10.2双向链表的删除

删除

p -> prior -> next = p -> next;
p -> next -> prior = p -> prior;
free(p);

总结

线性表