线性表_建立一20个及以上数据的有序和无序的顺序表,表中可以仅存放记录的关键字,实现

1.线性表的定义

线性表是具有相同数据类型的n个数据元素的有限序列。其中n为表长，当n=0时该线性表是一个空表。若用L命名线性表，则其一般表示为：L=(a₁,a₂,…,a_i,a_i+1,…a_n)。其中a₁时唯一一个“第一个”数据元素，又称为表头元素；a_n是唯一的“最后一个”数据元素，又称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。

1.1顺序存储结构方式

顺序表的顺序存储结构又称顺序表。顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
假定线性表的元素类型为ElemType，线性表的顺序存储类型描述为：

#define MaxSize 50    //定义线性表的最大长度
typedef struct{
    ElemType date[MaxSize];    //顺序表的元素
    int length;    //顺序表的当前长度
}Sqlist;    //顺序表的类型定义
1
2
3
4
5

一维数组可以是静态分配，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将产生溢出，就会导致程序崩溃。
而动态分配时，存储数组的空间是在执行过程中通过动态存储分配语句分配的，一旦数据占满，可以另外开辟一块更大的存储空间，从而达到扩充存储数组空间的目的，而不需要一次性地划分所有所需空间给线性表。

#define InitSize 100    //表长度的初始定义
typedef struct{
    ElemType *data;    //指示动态分配数组的指针
    int MaxSize,length;    //数组的最大容量和当前的个数
}SeqList;    //动态分配数组顺序表的类型定义
1
2
3
4
5

C的初始动态分配语句为：L.data=(ElemType*)malloc(sizeof(ElemType) * InitSize);
C++的初始动态分配语句为：L.data=new ElemType[InitSize];
顺序表的最主要特点是*随机访问，即通过首地址和元素序号可以在O(1)的时间内找到指定元素。

1.2链式存储结构方式

（1）单链表
线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息之外，还需要存放一个指向其后继的指针。
单链表中的结点类型描述如下：

typedef struct LNode{    //定义单链表节点类型
    ElemType data;    //数据域
    struct LNode *next;    //指针域
}LNode,*LinkList;
1
2
3
4

利用单链表可以解决顺序表需要大量的连续存储空间的缺点，但是单链表增加指针域，也存在浪费存储空间的缺点。由于单链表的元素是离散地分布在存储空间中的，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找特定结点时，需要从表头开始遍历，依次查找。
通常用“头指针”来标识一个单链表，如单链表L，头指针为“NULL”时则表示一个空表。此外为了操作方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素结点。
头结点和头指针的区分：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表的第一个结点，结点内通常不存储信息。
引入头结点后，可以带来两个优点：
<1>由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置的操作一致，无须进行特殊处理。
<2>无论链表是否为空，其头指针是指向头节点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。
（2）双链表
单链表结点中只有一个指向其后继的指针，这使得单链表只能从头结点依次顺序的向后遍历。若要访问某个结点的前驱结点（插入、删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。
为了克服单链表的上述缺点，引入双链表，双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。
双链表中结点的类型描述如下：

typedef struct DNode{    //定义双链表结点类型
	ElemType data;    //数据域
	struct DNode *prior,*next;    //前驱和后继指针
}DNode,*DLinklist;
1
2
3
4

双链表仅仅是在单链表的结点中增加了一个指向其前驱的prior指针，因此，在双链表中执行按值查找和按位查找的操作和单链表相同。但双链表在插入和删除操作的实现上，和单链表有着较大的不同。这是因为“链”变化时也需要对prior指针做出修改，其关键在于保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除结点算法地时间复杂度仅为O(1)。
（3）循环链表
<1>循环单链表
循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。循环单链表的判空条件是头结点的指针是否等于头指针。
有时对单链表常做的操作是在表头和表尾进行的，此时可对循环单链表不设头指针而设尾指针，从而使得操作效率更高。
<2>循环双链表
由循环单链表的定义不难推出循环双链表，不同的是在循环双链表中，头结点的prior指针还要指向表尾结点。在循环双链表L中，某节点*p为尾节点时，p->next==L；当循环双链表为空表时，其头结点的prior域和next域都等于L。
（4）静态链表
静态链表时借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，与前面所讲的链表指针不同的是，这里的指针是结点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。
静态链表结构类型描述如下：

#define MaxSize 50    //静态链表的最大长度
typedef struct{    //静态链表结构类型的定义
    ElemType data;    //存储数据元素
    int next;    //下一个数据元素的下标
}SLinkList[MaxSize];
1
2
3
4
5

1.3顺序表和链表的比较

（1）存取方式
顺序表可以顺序存取也可以随机存取，链表只能从表头顺序存取元素。
（2）逻辑结构和物理结构
采用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，其物理存储位置则不一定相邻，其对应的逻辑关系是通过指针链接来表示的。
（3）查找、插入和删除操作
对于按值查找，当顺序表无序的情况下，两者的时间复杂度均为O(n)；而当顺序表有序时，可采用折半查找，此时时间复杂度为O(log₂n)。
对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1)，而链表的平均复杂度为O(n)。线性表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需要修改相关结点的指针域即可。由于链表每个结点带有指针域，因此在存储空间上比顺序表要付出较大的代价，存储密度不够大。
（4）空间分配
顺序存储在静态存储分配的情形下，一旦存储空间装满就不能扩充，如果再加入新的元素将内存溢出，需要预先分配足够大的存储空间。预先分配过大，可能导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间将导致分配失败。链式存储的结点空间只在需要的时候申请分配，只要内存有空间就可以分配，操作灵活、高效。

2.线性表的实现

2.1顺序表上基本操作的实现

（1)插入操作

bool ListInsert(Sqlist &L,int i,ElemType e){
//本算法实现将元素e插入到顺序表L中的第i个位置
    if(i<1||i>L.length+1)    //判断i的范围是否有效
        return false;
    if(L.length>=MaxSize)    //当前存储空间已满，不能插入
        return false;
    for(int j=L.length;j>=i;j--)    //将第i个元素及之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;    //在位置i出放出e
    L.length++;    //线性表长度加1
    return ture;
}
1
2
3
4
5
6
7
8
9
10
11
12

（2）删除操作

bool ListDelete(Sqlist &L,int i,int &e){
//本算法实现删除顺序表L中的第i个元素
    if(i<1||i>L.length)    //判断i的范围是否有效
        return false;
    e=L.data[i-1];    //将给删除的元素赋值给e
    for(int j=i;j<L.length;j++)    //将第i个元素之后的元素前移
        L.data[j-1]=L.data[j];
    L.length--;    //线性表长度减1
    return true;
}
1
2
3
4
5
6
7
8
9
10

（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;    //退出循环，说明查找失败
}
1
2
3
4
5
6
7
8

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!=9999){    //输入结点9999表示结束
        s=(LNode*)malloc(sizeof(LNode));    //创建新结点
        s->data=x;
        s->next=L->next;
        L->next=s;    //将新结点插入到表中，L为头指针
        scanf("%d",&x);
    }    //while结束
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（2）采用尾插法建立单链表

LinkList CreatList2(LinkList &L){
//从表头向表尾正向建立单链表L，每次均在表尾插入元素
    int x;    //设元素类型为整型
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;    //r为表尾指针
    scanf("%d",&x);    //输入结点的值
    while(x!=9999){    //输入9999表示结束
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;    //r指向新的表尾结点
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;    //尾结点指针置空
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（3）按序号查找结点值

LNode *GetElem(LinkList L,int i){
//本算法取出单链表L（带头结点）中第i个位置的结点指针
    int j=1;    //计数，初始为1
    LNode *p=L->next;    //头结点指针赋给p
    if(i==0)
        return L;    //若i等于0，则返回头结点
    if(i<1)
        return NULL;    //若i无效，则返回NULL
    while(p&&j<i){    //从第1个结点开始找，查找到第i个结点
        p=p->next;
        j++;
    }
    return p;    //返回第i个结点的指针，如果i大于表长，p=NULL，直接返回p即可
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

（4）按值查找表结点

LNode *LocateElem(LinkList L,ElemType e){
//本算法查找单链表L（带头结点）中数据域值等于e的结点指针，否则返回NULL
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e)    //从第1个结点开始查找data域为e的结点
        p=p->next;
    return p;    //找到后返回该结点指针，否则返回NULL
}
1
2
3
4
5
6
7

（5）插入结点操作

p=GetElem(L,i-1);    //查找插入位置的前驱结点
s->next=p->next;    //将新结点s指针域指向p的后继结点
p->next=s;    //将p的指针域指向s
1
2
3

//将*s插入到*p之前的主要代码片段
s->next=p->next;    //修改指针域，不能颠倒
p->next=s;
temp=p->data;    //交换数据域部分
p->data=s->data;
s-data=temp;
1
2
3
4
5
6

（6）删除结点操作

p=GetElem(L,i-1);    //查找删除位置的前驱结点
q=p->next;    //令q指向被删除的结点
p->next=q->next;    //将*q结点从链中断开
free(q);    //释放后继结点的存储空间
1
2
3
4

2.3双链表上基本操作的实现

（1）双链表的插入操作

//将结点s插入到结点p之后
s->next=p->next;
p-next-prior=s;
s->prior=p;
p->next=s;
1
2
3
4
5

（2）双链表的删除操作

//删除结点*p的后继结点*q
p->next=q->next;
q->next->prior=p;
free(q);
1
2
3
4

---

例题：
1.设线性表中有20个元素，（A）在单链表上实现要比在顺序表上实现效率更高。
A.删除所有值为x的元素
B.在最后一个元素的后面插入一个新元素
C.顺序输出前k个元素
D.交换第i个元素和第2n-i-1个元素的值（i=0，…，n-1）
2.给定有n个元素的一维数组，建立一个有序的单链表的最低时间复杂度为（D）。
A.O(1)
B.O(n)
C.O(n²)
D.O(nlog₂n)
3.在一个长度为n的带头结点的单链表h上，设有尾指针r，则执行（B）操作与单链表的表长有关。
A.删除单链表的第一个元素
B.删除单链表的最后一个元素
C.在单链表第一个元素前插入一个新元素
D.在单链表的最后一个元素后插入一个新元素
4.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构为（B）。
A.单链表
B.静态链表
C.顺序表
D.双链表
5.已知双链表含有三个域prev，data，next。现有一个包含了三个结点的双链表，其中p指向第一个结点，q指向下一个结点，下列哪种操作不能让其中一个指针指向第二个结点（）。