数据结构-线性表（顺序表和链表）

大纲：

1. 理解线性表的逻辑结构
2. 掌握线性表的顺序存贮结构和链式存贮结构；掌握线性表基本操作的实现。
3. 了解线性表的应用。

---

线性表的定义和基本操作

1. 线性表的定义

   具有相同数据类型的n（n>=0）个数据元素的有限序列

   线性表的特点：

   • 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继
   • 表中元素的个数有限
   • 表中元素具有逻辑上的顺序性
   • 表中每个元素都是数据元素，每个元素都是单个元素
   • 表中元素的数据类型都相同，即每一个元素占有相同大小的存储空间
   • 表中元素具有抽象性，即只关注于逻辑结构，不关注于元素表示什么内容

• 线性表示一种逻辑结构，表示元素之间一对一的相邻关系；顺序表和链表是存储结构，表示物理结构

2. 线性表的基本操作

   InitList(&L)：初始化表
   Length(L)：求表长
   LocateElem(L,e)：按值查找操作
   GetElem(L,i)：按位查找操作
   ListInsert(&L,e)：插入操作
   ListDelete(&L,i,&e)：删除操作
   PrintList(L)：输出操作
   Empty(L)：判空操作
   DestroyList(&L)：销毁操作

---

线性表的顺序表示

1. 顺序表的定义

   用一组连续的存储单元，依次存储线性表中的数据元素，使得逻辑上相邻的数据元素在物理位置上也相邻。

   结构体描述：

   //数组空间静态分配
   #define MaxSize 50  //数组最大长度
   typedef struct{
     ElemType data[MaxSize];  //顺序表的元素  
     int length;  //顺序表当前长度
   }SqList;  //静态分配数组顺序表的类型定义
   
   //数组空间动态分配
   #define InitSize 100  //表长度的初始定义
   typedef struct{
     ElemType *data;
     int MaxSize,length;
   }SeqList;  //动态分配数组顺序表的类型定义
   

   • C的初始动态分配语句
     L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
   • 顺序表的特点是随机访问，并且存储密度高。但是增删操作需要移动大量元素

2. 基本操作相关代码
   2.1 插入操作

   bool ListInsert(SqList &L,int i,ElemType e){
     if(i<1 || i>L.length)  //判断插入范围是否有效
       return false;
     if(i.length>=MaxSize)  //判断存储空间是否已满
       return false;
     for(int j=L.lengt;j>=i;j--)  //将i之后的元素依次向后移动
       L.data[j]=L.data[j-1];
     L.data[i-1]=e;  //在i位置上赋值，注意，i是位置序号，i-1是数组下标
     L.length++;  // 长度加一
     return true;
   }
   

   • 移动节点平均次数为n/2，时间复杂度为O(n)

   2.2 删除操作

   bool ListDelete(SqList &L,int i,ElemType &e){
     if(i<0 || i>L.length)  //判断删除范围是否有效
       return false;
     for(int j=i;j<L.length;j++)  //将i之后的值依次前移
       L.data[j-1]=L,data[j];
     L.length--;  //长度减一
     return false;
   }
   

   • 移动节点平均次数(n-1)/2，时间复杂度为O(n)

   2.3 按值查找

   int LocateElem(SqList L,ElemType e){
     //实现查找顺序表中值为e的元素，查找成功则返回元素位序，否则返回0
     int i;
     for(i=0;i<L>length;i++)
       if(L.data[i]==e)
         return i+1;  //下标为i的元素值为e，其位置为i+1
     return 0;
   }
   

   • 移动节点平均次数为(n+1)/2，时间复杂度为O(n)

---

线性表的链式表示

单链表

1. 单链表的定义

   通过一组任意的存储单元来存储线性表中的数据元素，每个链表节点除了存放自身的信息之外，还要存放一个指向后继的指针。其中data为数据域，next为指针域。

   结点类型定义

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

   • LinkList L==LNode *L
   • 单链表中的元素是离散地分布在存储空间中的，所以是非随机存取存储结构，想找到某个元素必须从头遍历
   • 通常用头指针标识一个单链表，此外，在单链表的第一个结点之前附加一个结点，称为头结点。头结点中可以不加任何信息，也可以记录表长等信息。
   • 引入头结点的优点：
     • 开始结点放在头结点的指针域中，所以链表的第一个位置上的操作与其他位置上的操作一致，不需要特殊处理
     • 若链表为空，头指针是指向头结点的非空指针（头结点的指针域为空），所以空表与非空表的处理统一
   • 单链表解决了顺序表需要大量连续存储空间的缺点，但是单链表附加指针域，也存在浪费存储空间的缺点

2. 基本操作相关代码
   2.1 建立单链表

   //头插法
   LinkList CreatList1(LinkList &L){
     //从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
     LNode *s;
     int x;
     L=(LinkList)malloc(sizeof(LNode));  //创建头结点
     L->next=NULL;  //初始空链表
     scanf("%d",&x);  //输入结点中的元素
     while(x!=999){
       s=(LNode*)malloc(sizeof(LNode));  //创建新的结点
       //下面三条代码为头插法的插入细则
       s->data=s;
       s->next=L->next;
       L->next=s;
       scanf("%d",&x);
     }
     return L;
   }
   
   //尾插法
   LinkList CreatList2(LinkList &L){
     //从表头到表尾正向建立单链表L，每次均在表尾插入元素
     LNode *s,*r=L;  //除了s这个新结点的指针，还建立了一个指向尾结点的r指针
     int x;
     L=(LinkList)malloc(sizeof(LNode));
     L->next=NULL;
     scanf("%d",&x);
     while(x!=999){
       s=(LNode*)malloc(sizeof(LNode));
       //以下三条代码为尾插法的插入细则
       s->data=s;
       r->next=s;
       r=s;  //r指向新的尾结点
       scanf("%d",&x);
     }
     r->next=NULL;
     return L;
   }
   

   • 头插法建立单链表，读入数据的顺序与生成的链表中的元素的顺序是相反的；尾插法建立单链表，读入数据的顺序与生成的链表中的元素的顺序是相同的
   • 两种方法的时间复杂度都为O(n)

   2.2 按序号查找结点值

   LNode *GetElem(LinkList L,int i){
     int j=1;  //计数器
     LNode *p=L->next;  //p指向头结点指针
     if(i==0)
       return L;
     if(i<1)
       return NULL;
     while(p&&j<i){  //从第一个结点开始找，查找第i-1个结点
       p=p->next;
       j++;
     }
     return p;  //返回第i个结点的指针，如果i大于表长，p=NULL，直接返回p即可
   }
   

   • 时间复杂度为O(n)

   2.3 按值查找

   LNode *LocateElem(LinkList L,ElemType e){
     LNode *p=L->next;
     while(p!=NULL&&p->data!=e)
       p=p->next;
     return p;
   }
   

   • 时间复杂度为O(n)

   2.4 插入结点主要代码片段

   p=GetElem(L,i-1);  //查找插入位置的前驱结点
   s->next=p->next;
   p->next=s;
   

   • 时间复杂度为O(1)
   • 单链表一般都是后插操作，但可以通过如下方式将前插操作转化为后插操作

     //将s结点插入到p结点之前的主要代码片段
     s->next=p->next;
     p->next=s;
     temp=p->data;  //交换数据域
     p->data=s->data;
     s->data=temp;
     

   2.5 删除结点操作

   //删除当前指针下一个结点
   p=GetElem(L,i-1);
   q=p->next;
   p->next=q->next;
   free(p);
   
   //删除当前指针所在结点
   q=p->next;
   p->data=p->next->data;
   p->next=q->next;
   free(q);
   

   • 第一个删除操作时间复杂度为O(n)；第二个删除操作时间复杂度为O(1)

---

双链表

双链表是在单链表只有一个指向后继结点的指针next的基础上，增加了一个指向前驱结点的指针prior

• 单链表想访问某个结点的前驱结点时，只能从头遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度O(n)

结点类型定义

typedef struct DNode{
  ElemType data;
  struct DNode *prior,*next;
}DNode,*LinkList;

• 插入操作主要代码片段

s->next=p->next;
p->next-prior=s;
s->prior=p;
p->next=s;

• 删除操作主要代码片段

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

---

循环链表

循环单链表： 在单链表的基础上，表中最后一个结点的指针不是NULL，而是改为指向头结点，整个链表形成一个环

• 因为没有指针域为NULL的结点，所以，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。
• 插入，删除操作算法与单链表一致，只是在表尾操作有所不同，需维持环的状态。且，任何位置插入，删除操作都是等价的，所以不需要判断表尾

循环双链表：在双链表的基础上，表中最后一个结点的指针不是NULL，而是改为指向头结点，整个链表形成一个环

• 判空条件为头结点的prior域和next域都等于头结点

---

静态链表

静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，不过这里的指针域指的是数组下标（游标）

结点类型定义

#define MaxSize  //静态链表的最大长度
typedef struct{
  ElemType data;
  int next;   //下一个元素的数组下标
}SLinkList[MaxSize];

• 同顺序表一样，需要预先分配一块连续的内存空间
• 静态链表以next=-1作为其结束的标志

---

顺序表和单链表的比较

1. 存取方式
   顺序表可以顺序存取，也可以随机存取；链表只能顺序存取
2. 逻辑结构和物理结构
   顺序表，逻辑上相邻的元素，物理位置上也相邻；链表，逻辑上相邻的元素，物理位置上不一定相邻
3. 查找，插入和删除操作时间复杂度
   按值查找：顺序表无序时，两者时间复杂度都是O(n)；当顺序表有序时，可以采用折半查找，时间复杂度为O(log₂n)
   按位查找：顺序表支持随机访问，时间复杂度为O(1)；链表平均时间复杂度为O(n)
   插入，删除的时间内复杂度见上
4. 空间分配
   顺序表易造成空间浪费，链表则不会

• 实际中，应基于存储，运算，环境的多方面考虑，恰当地选择存储结构