数据结构笔记2（线性表及其理解）

前言

写一下数据结构线性表的知识。10月20日写了《数据结构笔记2线性表》，现在消化吸收，突出重点。

文章目录

数据结构笔记2（线性表及其理解）

前言
笔记

顺序表特点
单链表特点
顺序表的算法

顺序表结构
创建
简单算法
运算算法
插入和删除

单链表的算法

单链表结构
创建
简单算法
运算算法

双向循环链表的算法

插入与删除

试题分析
判断题

总结

笔记

顺序表特点

线性表的顺序表示

用一段连续存储空间存储线性表中的各元素

特点：

逻辑上相邻的元素其物理地址也相邻

用存储位置来直接反映逻辑关系

可实现随机存取

实现：可采用C语言的一维数组实现

顺序存储结构的优缺点

优点

逻辑关系相邻，物理位置相邻

可随机存取任一元素

存储空间使用紧凑

缺点

插入、删除操作需要移动大量的元素

分配空间需按固定大小分配，利用不充分

顺序存储的主要优点是可以随机存取任一元素，缺点的插入和删除需要移动大量元素。

单链表特点

线性表的链式表示

用一组任意的存储单元存储线性表的数据元素

利用指针表示数据元素之间的逻辑关系

每个数据元素，除存储本身信息外，还需存储其逻辑关系（直接后继元素）

单链表特点

是一种动态结构

不需预先分配空间

指针占用额外存储空间

不能随机存取，查找速度慢

链式存储的主要优点是插入和删除简便，缺点是不能随机存取，且查找速度慢。

顺序表与链表其实对应和操作系统中的连续空间分配和离散空间分配很相似。顺序表就是分配独立的空间，就好比自己的房子，属于你，你想住就住，不过这个空间可能闲置；链表就是使用离散的空间，就好比宾馆，不属于你，不然如果你想要住，就需要预约。两者各有优点，也有缺点。根据现实使用情况使用。

顺序表的算法

从顺序表的特点看，我们知道一维数组就是一种顺序表。顺序表的增删改查和一维数组的增删改查很相似。

首先我们先定义线性表顺序存储结构

顺序表结构

#define  LIST_INIT_SIZE  100 //存储空间的初始分配量
#define  LISTINCREMENT  10 //存储空间的分配增量
typedef  struct{
        ElemType  *elem ; //存储空间基址
         int length ; //当前长度
         int listsize ; //当前分配的存储容量
 }SqList ;

创建

接着我们实现第一个算法。创建顺序表。

方法是将给定的含有n个元素的数组的每个元素依次放入到顺序表中，并将n赋给顺序表的长度成员。

/*建立顺序表*/
void CreateList(SqList &L,ElemType a[],int n){
   int i;
   L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
   if ( !L.elem ) exit ( OVERFLOW ) ;
   for (i=0;i<n;i++)
   L.elem[i]=a[i];
   L.length=n;
   L.listsize= LIST_INIT_SIZE;
   }

//线性表的初始化
Status  InitList_sq ( SqList  &L ){
   L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
   if ( !L.elem ) exit ( OVERFLOW ) ; 
   L.length = 0 ;
   L.listsize = LIST_INIT_SIZE ;
   return OK ;
}

//销毁线性表:释放线性表L占用的内存空间
void DestroyList(SqList &L){
   free(L.elem);
}

简单算法

判断是否为空表、求线性表的长度、输出线性表

//判定是否为空表
int ListEmpty(SqList L){
   return(L.length==0);
}
//求线性表的长度
int ListLength(SqList L){
return(L.length);
}
//输出线性表
void DispList(SqList L)
    {
   int i;
   if (L.length==0) return;
   for (i=0;i<L.length;i++)
      printf("%c",L.elem[i]);
   printf("\n");
    }

运算算法

插入一个X数到有序递增表中；就地转置；

//插入x到有序递增表汇总
status insert_SqList（SqList &L,int x){
  if(L.length+1>L.listsize)return Error;
  for(i=L.length-1;L.elem[i]>x && i>=0;i--)
  L.elem[i+1]=L.elem[i];
  L.elem[i+1]=x;
  L.length++;
  return ok;
}
//顺序表就地转置
void reverse(SqList &A){
  int i,j,temp;
  for(i=0,j=A.length-1;i<j;i++,j--){
    temp=A.elem[i];
    A.elem[i]=A.elem[j];
    A.elem[j]=temp;
  }
}

插入和删除

这里其实涉及到空间的重新分配，不过下面的算法是用数组来表示的。

//插入
int ListInsert(SqList &L,int i,ElemType e){
  int j;
  if (i<1 || i>L.length+1)  return 0;
  i--;  /*将顺序表逻辑位序转化为elem下标即物理位序*/
  for (j=L.length;j>i;j--) L.elem[j]=L.elem[j-1];
  /*将elem[i]及后面元素后移一个位置*/
  L.elem[i]=e;
  L.length++;      /*顺序表长度增1*/
  return 1;
}
//删除
int ListDelete(SqList &L,int i,ElemType &e){
  int j;
  if (i<1 || i>L.length)  return 0;
  i--;     /*将顺序表逻辑位序转化为elem下标即物理位序*/
  e=L.elem[i];
  for (j=i;j<L.length-1;j++) L.elem[j]=L.elem[j+1];
  /*将elem[i]之后的元素前移一个位置*/
  L.length--; /*顺序表长度减1*/
  return 1;
}

顺序表比较简单。不过由于其空间都是固定分配的，所以其空间复杂性一般比较高。优点是实现简单，并且存取方便。

确定就是插入和删除比较复杂。而单链表恰恰可以解决这个问题。单链表的插入和删除较为简单。

单链表的算法

顺序表可以结合一维数组去理解。单链表需要结合图形去理解。可以把单链表理解成链子，上一个与下一个连接在一起，单链表的增删改查就和链子的增加、删除、操作很像。

单链表结构

typedef  struct  LNode {
    ElemType  data ;
    struct  LNode  * next ;
} LNode , * LinkList ;

创建

//单链表的创建
void  CreateList_L ( LinkList  &L , int  n )
{ L = ( LinkList ) malloc ( sizeof (LNode ) ) ;
  L ->next = NULL ;
  for ( i = n ; i > 0 ; -- i ) {
        p = ( LinkList ) malloc ( sizeof ( LNode ) ) ;
        scanf ( & p -> data ) ;
        p -> next = L -> next ;
        L -> next = p ;
    }
}
//初始化
void InitList(LinkList &L){
  L=(LinkList )malloc(sizeof(LNode));/*创建头结点*/
  L->next=NULL;
}
//销毁：逐一释放空间
void DestroyList(LinkList &L){
  LinkList p=L,q=p->next;
  while (q!=NULL)
  {free(p);
   p=q;q=p->next;
  }
  free(p);
}

简单算法

和顺序表形成对比。

//判断是否为空表：如果单链表没有数据结点则为空
int ListEmpty(LinkList L){
  return(L->next==NULL);
}
//求线性表的长度
int ListLength(LinkList L){
  LinkList p=L;int i=0;
  while (p->next!=NULL){
  i++;
  p=p->next;
}xgjhu 
  return(i);
} 
 //输出线性表
void DispList(LinkList L){
LinkList p=L->next;
while (p!=NULL){
printf("%c",p->data); 
p=p->next;
}
printf("\n");
}

运算算法

两个单链表的合并

删除单链表中大于max和小于min的数。

双向循环链表的算法

typedef  struct  DuLNode  {
 ElemType   data ;
 struct  DuLNode  * prior ; 
 struct  DuLNode  * next ;
} DuLNode , * DuLinkList ; 
//删除
Status Listdelete_DuL( DuLinkList &L,int i,ElemType  &e )
{  if ( ! ( p = GetElemP_DuL ( L , i ) ) )  return  ERROR ;
   e = p -> data ;
   p -> prior -> next = p -> next ;
   p ->next -> prior = p -> prior ;
   free ( p ) ;
   return  OK ;
}
//插入
Status  ListInsert_DuL( DiLinkList &L,int  i ,ElemType  e )
{  if ( ! ( p = GetElemP_DuL ( L , i ) ) )  return ERROR ;
   if ( ! ( s = ( DuLinkList ) malloc ( sizeof ( DuLNode ) ) ) ) 
          return  ERROR ;
   s -> data = e ;
   s -> prior = p -> prior ; p -> prior -> next = s ;
   s -> next = p ; p -> prior = s ;
   retrun  OK ;
}

插入与删除

//插入
int ListInsert(LinkList &L,int i,ElemType e){
  int j=0;
  LinkList p=L,s;
  while (j<i-1 && p!=NULL){/*查找第i-1个结点*/
  j++;
  p=p->next;
  }
if (p==NULL) return 0; /*未找到位序为i-1的结点*/
  else  /*找到位序为i-1的结点*p*/
  {s=(LinkList )malloc(sizeof(LNode));
    /*创建新结点*s*/
    s->data=e;
    s->next=p->next;  /*将*s插入到*p之后*/
      p->next=s;
    return 1;
  }
}
//删除
 int ListDelete(LinkList &L,int i,ElemType &e){
  int j=0;
  LinkList p=L,q;
  while (j<i-1 && p->next!=NULL)  /*查找第i-1个结点*/
  {     j++;
        p=p->next;
  }
  if (p->next==NULL) return 0; /*未找到位序为i-1的结点*/
  else  /*找到位序为i-1的结点*p*/
  {      q=p->next;              /*q指向要删除的结点*/
                    p->next=q->next;   /*从单链表中删除*q结点*/
          e=p->data;
                    free(q);                           /*释放*q结点*/
          return 1;
  }
}

试题分析

下面关于线性表的叙述中，错误的是（）？

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

选B，顺序表便于随机存取，不便于插入和删除；单链表删除插入和删除。

在一个长度为n的顺序表中，在第i（0<i<=n+1）个元素之前插入一个元素时，需向后移动（）个元素。

A. n-i B. n-i+1 C. n-i-1 D. i

B。举例子。长度为5的数组，在第3个元素后插入一个元素，须向后移动3个。代入公式5-3+1成立。

若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

选A。

设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表

选D

链表不具有的特点是（）

A．插入、删除不需要移动元素 B．可随机访问任一元素

C．不必事先估计存储空间 D．所需空间与线性长度成正比

选B。随机访问任一元素是顺序表的特点。链表访问元素靠遍历。

线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）

O（i） B．O（1） C．O（n） D．O（i-1）

C。一个一个遍历。循环一次。

若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。

A. O(0) B. O(1) C. O(n) D. O(n2)

C。循环把元素向后移动一位。

在一个单循环链表(长度为n)中，已知p指针指向链表中一个非空结点，现要删除链表中p指针所指结点，其时间复杂度为（）。

A. O( n ) B. O( 1 ) C. O( n2) D. 不确定

A。查找的执行时间是O(n)。

对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。

A．O(n) O(n) B. O(n) O(1)

C. O(1) O(n) D. O(1) O(1)

C。顺序表访问一次操作，增删涉及循环一次。

非空的循环链表head的尾结点p↑满足（）

A．p->next=head B．P->next=NULL

C．p=NULL D．p= head

A。尾结点指向头

带头结点的循环链表L为空的条件是（）。

A. L == NULL B. L->next ==NULL

C. L->next == L D. L->next == L->next

C。尾结点指向自身为空

在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）

A．p->next=s;s->next=p->next;

B．s->next=p->next;p->next=s;

C．p->next=s;p->next=s->next;

D．p->next=s->next;p->next=s;

B。

在双向链表指针p的结点前插入一个指针q的结点操作是( )。

A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；

B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;

C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;

D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

C。

判断题

（）顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

错。顺序存储的插入和删除效率低

（）顺序存储方式插入和删除时效率太低，在这方面它不如链式存储方式好。

对。

（）顺序存储结构的主要缺点是不利于插入或删除操作。

对。

（）对任何数据结构链式存储结构一定优于顺序存储结构。

错。随机存取，顺序表更有优势。

（）取线性表的第i个元素的时间同i的大小有关。

错。顺序表的化，一次。

（）线性表、栈和队列都是线性结构。

对。

（）链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。

对。

（）线性表中每一个元素均存在唯一一个前驱和唯一一个后继。

错。单链表最后一个只有前驱，没有后继。

（）循环链表不是线性表。

错。

（）线性表的长度是线性表所占用的存储空间的大小。

错。顺序表的存储空间可以是10，而长度是5.

（）在单链表表示的线性表中，取线性表第i个元素操作的时间复杂度为O(1)。

错。遍历一次。

（）删除带头结点单链表的第一个元素结点的时间复杂度是O(1)。

对。

总结

有点多。中间的代码直接拷贝。没有实际操作，回头深入一下。

数据结构笔记2（线性表及其理解）