数据结构（二）——千字线性表

这是我参与更文挑战的第11天，活动详情查看：更文挑战

线性表

线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长。

初始化，求表长，按值查找，按位查找，插入，删除，输出，判空，销毁

线性表的顺序表示

线性表的顺序存储又称顺序表，他是用一组地址连续的存储单元依次存储线性表中的数据元素，使逻辑上相邻的元素在物理位置上也相邻。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同

假定线性表的元素类型为ElemType，则线性表的顺序存储类型描述为

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize]; // 顺序表的元素
    int length;    // 顺序表的当前长度
}SqList   // 顺序表的类型定义
复制代码

动态分配

#define InitSize 100
typedef struct{
    ElemType *data; //指示动态分配数组的指针
    int MaxSize,length; //数组的最大容量和当前个数
}SeqList;
复制代码

L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
复制代码

动态分配不是链式存储，他同样属于顺序存储结构，物理结构没有变化，依然是随机存储方式，只是分配的空间大小可以在运行时决定

顺序表最主要的特点是随机访问,即通过首地址和元素序号可在O(1)内找到指定的元素

顺序表逻辑上相邻的元素在物理上也相邻，所以插入和删除的操作需要移动大量元素

基本操作

• 插入操作

bool ListInsert(SqList &L,int i,ElemType e){
    //本算法实现将e元素插入至顺序表L中第i个位置
    if(i<1||i>L.length+1)return false;
    if(L.length>=MaxSize)return false;
    for(int j=L.length;j>=i;j--)L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}
复制代码

• • 最好情况O(1)
  • 最坏情况O(n)
  • 平均O(n)
• 删除操作

bool ListDelete(SqList &L,int i,Elemtype &e){
    if(i<1||i>L.length) return false;
    e = L.data[i-1];
    for(int j=1;j<L.length;j++)L.data[j-1] = L.data[j];
    L.length--;
    return true;
}
复制代码

• • 最好情况：删除表尾元素（即i=n），无须移动元素，时间复杂度为O(1)
  • 最坏情况O(n)
  • 平均O(n)
• 按值查找
  • 最好情况O(1)
  • 最坏情况O(n)
  • 平均O(n)

线性表的链式表示

单链表

typedef struct LNode{ //定义单链表结点类型
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
复制代码

单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点

• 头指针为NULL时表示一个空表
• 为了操作的方便，一般设置一个头结点。
• 头结点数据域可以不设置任何信息，也可以记录表长等信息。

引入头结点的优点

• 由于开始结点的位置被放在了头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无需特殊处理
• 无论链表是否为空，其头指针都指向头结点的非空指针，因此空表和非空表的处理也得到了统一。

头插法建立单链表

LinkList List_HeadInsert(LinkList &L){
    //从表尾到标头逆向建立单链表L,每次均在头结点之后插入元素
    LNode *s;int x;
    L = (LinkList)malloc(sizeof(LNode)); //创建头结点
    L->next = NULL; //初始为空链表
    scanf("%d",&x); //输入结点的值
    while(x!=9999){ //输入9999表示结束
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x); 
    }
    return L;
}
复制代码

尾插法建立单链表

需要设置一个尾结点r

LinkList List_TailInsert(LinkList &L){
    //从表头到表尾正向建立单链表L，每次均在表尾插入元素
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;//r为表尾指针
    scanf("%d",&x); 
    while(x!=9999){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
    	r->next = s;
        r = s;
        scanf("%d",&x); 
    }
    r->next = NULL;
    return L;
}
复制代码

按序号查找结点值

LNode *GetElem(LinkList L,int i){
    //本算法取出单链表L（带头结点）中第i个位置的结点指针
    int j = 1;
    LNode *p = L->next;
    if(i==0)return L;
    if(i<1)return Null;
    while(p&&j<i){
        p = p->next;
        j++
    }
    return p;
}
复制代码

按值查找表结点

LNode *LocationElem(LinkList L,ElemType e){
    //本算法查找L中数据域值等于e的结点指针，否则返回NULL
    LNode *p = L->next;
    while(p!=NULL&&p->data!=e) p = p->next
    return p;
}
复制代码

插入结点操作

p = GetElem(L,i-1);
s->next = p->next;
p->next = s;
复制代码

删除结点操作

p = GetElem(L,i-1);
q = p->next;
p->next = q->next;
free(q);
复制代码

双链表

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;
复制代码

双链表的插入操作

s->next = p->next;
p->next->prior = s;
s->prior = p;
p -> next = s;
复制代码

双链表删除操作

p->next = q->next;
q->next->prior = p;
free(q);
复制代码

循环链表

循环链表的最后一个结点的指针指向头结点，从而整个链表形成一个环

循环双链表

当循环双链表为空表时，其头结点的prior域和next域都等于L

静态链表

#define MaxSize 50
typedef struct{
    ElemType data;
    int next; 
}SLinkList[MaxSize];
复制代码

顺序表与链式表的比较