866数据结构笔记 - 第二章线性表

线性表是逻辑结构还是物理结构？
顺序表的随机访问是什么意思？
顺序表的插入与删除操作是如何实现的？
顺序表的插入和删除移动次数？
顺序表和单链表的结构体怎么定义？
带头结点和不带头结点判空怎么判断？
单链表插入和删除怎么实现？
单链表、双链表的插入删除顺序问题
如何高效的将顺序表逆置？
如何删除有序表的重复值？
如何将两个有序表合成一个有序表？
如何将单链表就地逆置？
如何删除单链表中介于两值之间的元素？
如何将两个有序单链表归并成一个有序单链表？
如何得到单链表的倒数第k个元素

一、线性表

线性表：n个数据元素的有限序列。（同类型、有限、逻辑有序）
除第一个元素，每个元素仅有一个直接前驱。除最后一个元素，每个元素仅有一个直接后继。
线性表是逻辑结构，物理结构包括：顺序表和链表

二、顺序表

1.特点

逻辑上相邻元素，物理上也相邻。
随机访问（能在O(1)时间内找到指定元素）
查询操作很方便，插入，删除会涉及到大量元素移动。

2.定义

#define MaxSize 50   //定义表的最大长度 
typedef struct{
	int data[MaxSize];//用静态的"数组"存放数据元素
	int length; //顺序表的当前长度  
}SqList;

3.基本操作

遍历

for (int i = 0; i < L.length; i++)
    visit(L.data[i]);

查找

// 按位查找(随机访问)
L.data[i-1]; // 获得第i个位置元素

// 按值查找(遍历顺序表)
for (int i = 0; i < L.length; i++)
    if (L.data[i] == x) break;
if (i < L.length) return ture; // return i;
else return false;

插入

注意插入范围：1<= i <= L.length + 1，第一个元素到最后一个元素后移一个元素，在第i个位置插入x，表长增1（如果不增加，顺序表是什么情况？）。

bool ListInsert(SqList &L, int i, int e){ 
    //判断i的范围是否有效
    if(i<1||i>L.length+1) 
        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

    // 可以思考一下，如果表长不增加1，此时顺序表是什么情况？
    L.length++;      //长度加1
    return true;
}

删除

bool LisDelete(SqList &L, int i, int &e){ // e用引用型参数 
    //判断i的范围是否有效
    if(i<1||i>L.length) 
        return false;

    e = L.data[i-1]    //将被删除的元素赋值给e

    for(int j=L.length; j>=i; j--){    //将第i个后的元素前移
        L.data[j-1]=L.data[j];
    }
    L.length--;      //长度减1
    return true;
}

4.算法分析

其实比较容易搞混的介绍插入和删除的移动次数，插入是n-i-1，删除是n-i。如果考试中遇到这种题，可以考虑特殊值法。如果i=1，插入操作需要移动n次，如果i=n，删除操作需要移动0次。

三、单链表

1.特点

用指针表示数据元素之间的逻辑关系（逻辑相邻的元素物理位置不一定相邻）

2.定义

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

3.实现方式

带头结点：头指针指向的头结点不存放实际数据,头结点指向的下一个结点才存放实际数据。空表判断：L->next == NULL
不带头结点：写代码麻烦！对第一个数据节点和后续数据节点的处理需要用不同的代码逻辑，对空表和非空表的处理也需要用不同的代码逻辑; 头指针指向的结点用于存放实际数据。空表判断：L == NUL

4.基本操作

遍历

// 应用：求表长，打印表中所有元素
p = L->next;
while (p != NULL){
    visit(p->data);
    p = p->next;
}

查找

// 按位查找，O(n)
LNode * GetElem(LinkList L, int i){
    if(i<0) return NULL;
    
    LNode *p;               //指针p指向当前扫描到的结点
    int j=0;                //当前p指向的是第几个结点
    p = L;                  //L指向头结点,头结点是第0个结点(不存数据)
    while(p!=NULL && j<i){  //循环找到第i个结点
        p = p->next;
        j++;
    }

    return p;               //返回p指针指向的值
}

// 按值查找，O(n)
LNode * LocateElem(LinkList L, ElemType e){
    LNode *P = L->next;    //p指向第一个结点
    //从第一个结点开始查找数据域为e的结点
    while(p!=NULL && p->data != e){
        p = p->next;
    }
    return p;           //找到后返回该结点指针，否则返回NULL
}

插入（选择题常考）

注意顺序！如果第2步与第3步反过来，会出现什么情况？

删除（选择题常考）

LNode *q = p->next;      //令q指向*p的后继结点
p->data = p->next->data; //让p和后继结点交换数据域
p->next = q->next;       //将*q结点从链中“断开”
free(q);

建立链表（头插法、尾插法）

// 头插法，每次都将生成的结点插入到链表的表头
LinkList List_HeadInsert(LinkList &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);   
    }
    return L; 
}

// 尾插法，每次将新节点插入到当前链表的表尾。
// 所以必须增加一个尾指针r,使其始终指向当前链表的尾结点。
// 好处：生成的链表中结点的次序和输入数据的顺序会一致
LinkList List_TailInsert(LinkList &L){       //正向建立单链表
    int x;                                   //设ElemType为整型int
    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 = s                                //r指针指向新的表尾结点
        scanf("%d", &x);   
    }
    r->next = NULL;                          //尾结点指针置空
    return L;
}

四、双链表

如果p是最后一个元素，那么下面哪些需要修改呢？

// p之后插入s
s->next = p->next;
p->next = s;
s->prior = p;
s->next->prior = s;

// p之前插入s
s->prior = p->prior;
p->prior = s;
s->next = p;
s->prior->next = s;

// 删除p的后继s
s = p->next;
p->next = s->next;
s->next->prior = p;
free(s);

// 删除p
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);

五、循环链表

1.循环单链表

//判断循环单链表是否为空（终止条件为p或p->next是否等于头指针）
bool Empty(LinkList L){
    if(L->next == L)
        return true;    //为空
    else
        return false;
}
// 判断p是否为表尾
p->next == L;

2.循环双链表

//判断循环双链表是否为空
bool Empty(DLinklist L){
    if(L->next == L)
        return true;
    else
        return false;
}
// 判断p是否为表尾
p->next == L;

六、静态链表（了解即可，866并未考察过）

用数组的方式来描述线性表的链式存储结构: 分配一整片连续的内存空间，各个结点集中安置，包括了——数据元素和下一个结点的数组下标(游标)

其中数组下标为0的结点充当"头结点"。
游标为-1表示已经到达表尾。
若每个数据元素为4B，每个游标为4B，则每个结点共8B；假设起始地址为addr，则数据下标为2的存放地址为：addr+8*2。
注意： 数组下标——物理顺序，位序——逻辑顺序。
优点：增、删操作不需要大量移动元素。
缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变！

七、插入删除顺序题

这种题目一般喜欢在选择题出，做这种题建议画图，将四个选项的操作依次画一遍，答案就很明显了。

下面的题目和一般的题目不一样，一般的题目是能找到前驱结点的，但是如果找不到前驱结点的情况应该怎么处理？其实，虽然找不到前驱，但是找后继是很容易，所以删除后继很容易，只要将后继的值赋值给前驱，然后删除后继就解决了。如图所示。

八、选择何种链表题

不管是插入还是删除，最关键的就是能否找到处理结点的前驱。

末尾进行插入和删除，那么需要很容易找到倒数第二个元素，或者如果是循环链表，则需要很容易找到第一个元素。

带头结点的双循环链表能够很容易找到第一个元素，O(1)，所以符合要求。

单循环链表找到倒数第二个元素需要O(n)，因为是单链表，所以第一个元素没有指向末尾元素的指针，所以不符合要求。

带尾指针的单循环链表删除末尾元素时，找到倒数第二个元素需要O(n)。

单链表删除末尾元素时，找到倒数第二个元素需要O(n)。

A.四种操作时间复杂度：O(1)、O(n)、O(1)、O(1)

B.四种操作时间复杂度：O(n)、O(1)、O(n)、O(1)

C.四种操作时间复杂度：O(1)、O(1)、O(1)、O(1)

D.四种操作时间复杂度：O(1)、O(n)、O(1)、O(1)

九、代码题（重点题目）

顺序表

866数据结构考研真题：

19年：n个整数，哪两个数绝对值差最大。
19年：两个数组A，B，要求在A和B中分别找一个数a,b，使得a+b=K(K已知)
19年：散列表，删除K
17年：顺序表找一个数，找到将其放在第一位。找不到，所有元素后移，将此数放在第一位。
03年：顺序表找一个数，找到将其放在第一位。找不到，所有元素后移，将此数放在第一位。

湖大本科期末题：

非递减有序顺序表，删除相同值。
顺序表中有多少对相反数。

1.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

/*
搜索整个顺序表，查找最小值元素并记住其位置，
搜索结束后用最后一个元素填补空出的原最小值元素的位置。
*/
bool Del_Min(sqList &L,int &value)
{
    if(L.length ==0)
        return false;
    value = L.data[0];
    int pos = 0;
    for(int i=1;i<L.length;i++)
    {
        if(L.data[i]<value)
        {
            value = L.data[i];
            pos = i; //循环找最小值的元素
        }
        //空出的位置由最后一个填补
        L.data[pos] = L.data[L.length -1];
        L.length--;
        returm true;
    }
}

2.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为 O1).

void Reverse(Sqlist &L)
{
    int temp; 
    for(i=0;i<L.length/2;i++)
    {
        temp = L.data[i]; //交换变量
        L.data[i] = L.data[L.length - i - 1];
        L.data[L.length - i -1] = temp;
    }
}

3.对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

/*
用 k 记录顺序表L中不等于x的元素个数(即需要保存的元素个数)，
边扫描L边统计k，并将不等于x的元素向前移动 k 个位置，最后修改L的长度。
*/
void del_x1(Sqlist &L，int x)
{
    int k=0; //记录值不等于x的元素个数
    for(i=0;i<L.length;i++)
        if(L.data[i]!=x)
        {
            L.data[k] = L.data[i];
            k++; //不等于x的元素增1
        }
    L.length = k; //顺序表L的长度等于k
}

4.从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。

/*
本题与上题的区别，因为是有序表，所有删除的元素必须是相连的整体。
从前向后扫描顺序表L，用k记录下元素值在s到t之间的元素的个数。
若其值不在s到t之间，则前移k个位置;否则执行k++.
*/
bool Del_s_t(SqList &L,int s,int t)
{
    int i,k=0;
    if(L.length==0||s>=t)
        return false;
    for(i=0;i<L.length;i++)
    {
        if(L.data[i]>=s && L.data[i]<=t)
            k++;
        else
            L.data[i-k] = L.data[i];//当前元素前移k个位置
    }
    L.length -= k; //长度减小
    return true;
}

5.从顺序表中删除其值在给定值s与之间(包含s和t，要求s<t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。

void del_st(SqList &list, int s, int t) {
  if (s >= t || list.length == 0) {
    cout << "ERROR!" << endl;
    return;
  }
  // 1.要保存的值都放在前面
  int k = 0; 
  for (int i = 0; i < list.length; i++) {
    if (list.data[i] < s || list.data[i] > t) {
      list.data[k++] = list.data[i];
    }
  }  
  // 2.直接扔掉后面的值
  list.length = k;
}

6.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

/*
有序顺序表，值相同的元素在连续的位置上，
用类似直接插入排序的思想，初始时将第一个元素视为非重复的有序表。
之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同，
若相同则继续向后判断，若不同则插入到前面的非重复有序表的最后，直到判断到表尾为止。
*/
bool Delete_Same(SeqList &L)
{
    if(L.length == 0)
        return false;
    int i,j;
    for(i=0;j=1; j<L.length;j++)
        if(L.data[i]!=L.data[j])
            L.data[++i] = L.data[j];
    L.length = i+1;
    return true;
}

7.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

/*
按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。
然后，看哪个表还有剩余，将剩余的部分加到新的顺序表后面。
*/
bool Merge(SeqList A,SeqList B,Seqlist &C)
{
    if(A.length + B.length > C.maxSize)
        return false;
    int i=0,j=0,k=0;
    while(i<A.length && j<B.length) //循环，两两比较，小者存入结果表
    {
        if(A.data[i] <= B.data[j])
            C.data[k++] = A.data[i++];
        
        else
            C.data[k++] = B.data[j++];
      }   
    
        while(i<A.length)
            C.data[k++] = A.data[i++];
        while(j<B.length)
            C.data[k++] = B.data[j++];
        C.length = k;
        return true;
}

单链表

866数据结构考研真题：

21年：单链表删除介于两个数之间的元素。
15年：有序单链表插入一个数，仍然有序。
15年：单链表冒泡排序。
14年：单链表原地逆置。
12年：两个递增有序单链表合并仍然有序。
10年：有序链表查找值为x，查不到则插入x。
06年：删除介于两值之间的所有元素。
05年：单链表找一个数，找到将其放在第一位。找不到，所有元素后移，将此数放在第一位。
03年：单链表判断是否为斐波那契数列。

湖大本科期末题：

两个有序链表合并后仍然有序。
链表元素逆置。
链表元素是否构成等差数列。
第k个元素与倒数第k个元素交换。

1.带头结点的单链表L删除所有值为 x 的结点，释放其空间，假设值 x 的结点不唯一。

/*
用p从头至尾扫描单链表，pre指向*p结点的前驱。
若p所指结点的值为x，则删除，并让p移向下一个结点，否则让pre、p指针同步后移一个结点。
该段代码可以一直使用,if条件可以更改。时间复杂度为O(n),空间复杂度为O(1).
*/
void Del_X(LinkList &L,int x)
{
    LNode *p = L->next,*pre = L,*q;
    while(p!=NULL)
    {
        if(p->data ==x)
        {
            q = p;  //q指向该结点
            p = p->next;
            pre->next = p;  //删除*q结点
            free(q);      
        }
        else      //否则,pre和p同步后移
        {
            pre= p;
            p = p->next;
        }
    }//while
}

2.带头结点的单链表L逆向输出每个结点的值。

void R_Print(LinkList &L)
{
    if(L->next != NULL)
    {
     	R_Print(L->next); 
    }
    print(L->data);
}

3.带头结点的单链表L中删除最小值结点(假设最小值结点唯一)。

LinkList Delete_Min(LinkList &L)
{
    LNode *pre = L,*P = pre->next; //p为工作指针,pre指向其前驱 
    LNode *minpre = pre,*minp = p; //保存最小值结点及其前驱
    while(p!=NULL)
    {
        if(p->data < minp->data)
        {
            minp = p;  //找到比之前找到的最小值结点更小的结点
            minpre = pre;
        }
        pre = p;   //继续扫描下一个结点
        p = p->next;
    }
    minpre->next = minp->next; //删除最小值结点
    free(minp);
    return L;
}
//若本题改为不带头结点的单链表，则实现上会有所不同，请读者自行思考。

4.带头结点的单链表就地逆置，即辅助空间复杂度为O(1)。

/*
将头结点摘下，然后从第一结点开始，依次插入到头结点的后面，
直到最后一个结点为止，这样就实现了链表的逆置。
*/
LinkList Reverse_1(LinkList L)
{
    LNode *p,*r; //p为工作指针，r为p的后继，以防断链
    p = L->next; //从第一个元素结点开始
    L->next = NULL; //先将头结点L的next域置为NULL
    while(p!=NULL) //依次将元素结点摘下
    { 
        r = p->next;  //暂存p的后继
        p->next = L->next; //将p结点插入到头结点之后
        L->next = p;
        p = r;
    }
    return L;
}

5.带头结点的单链表L无序，删除表中所有介于给定的两个值之间的元素(若存在)。

/*
因为链表是无序的，所以只能逐个结点进行检查，进行删除。 
*/
void RangeDelete(LinkList &L,int min,int max)
{
    LNode *pr = L,
    *p = L->link; //p是检测指针，pr是其前驱
    while(p!=NULL)
    {
        if(p->data>min && p->data<max) //寻找到被删结点，删除
        {
            pr->link = p->link;
            free(p);
            p = pr->link;
        }
        else  //否则继续寻找被删结点
        {
            pr = p;
            p = p->link;
        }
    }
}

6.递增的单链表，去掉表中重复的元素，只保留一个数值。

/*
由于是有序表，所有相同值域的结点都是相邻的。
用p扫描递增单链表L,若*p结点的值域等于其后继结点的值域，则删除后者，
否则p移向下一个结点。实际时间复杂度为O(n),空间复杂度为O(1)。
*/
void Del_Same(LinkList &L)
{
    LNode *P = L->next,*q;
    if(p==NULL)
    	return;
    while(p->next !=NULL)
    {
        q = p->next;  //q指向*p的后继结点
        if(p->data == q->data) //找到重复的结点
        {
            p->next = q->next;  //释放*q结点
            free(q);
        }
        else
            p = p->next; 
    }
}

7.两个递增的单链表归并为一个递减的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

/*
合并时，均从第一个结点起开始比较，将较小的结点链入链表中，同时后移工作指针。
该问题要求结果链表按元素值递减次序排列，故新链表的建立应该采用头插法。
比较结束后，可能会有一个链表非空，此时用头插法将剩下的结点依次插入新链表中即可。
*/
void MergeList(LinkList &La,LinkList &Lb)
{
    LNode *r,*pa = La->next, *pb = Lb->next;
    La->next = NULL; //La作为结构链表的头指针，先将结果链表初始化为空
    while(pa && pb) //当两链表不空时，循环
    {
        if(pa->data <= pb->next)
        {
            r = pa->next;
			pa->next = La->next;
            La->next = pa;
            pa = r;
        }
        else
        {
            r = pb->next;     //r暂存pb的后继结点指针
            pb->next = La->next;
            La->next = pb;   //将pb结点链于结果表中，同时逆置
            pb =r;   //恢复pb为当前待比较结点
        }
        if(pa)
            pb = pa;     //通常情况下会剩一个链表非空，处理剩余的部分。
        while(pb)		 //处理剩下的一个非空链表
        {		
            r = pb->next; //依次插入到La中
            pb->next = La->next;
            La->next = pb;
            pb =r;
        }
        free(Lb);
    }
}

8.查找链表倒数第 k 个位置上的结点 (k为正整数)。若查找成功，输出该结点的data域的值，并返回1;否则只返回0。

/*
描述算法的基本思想:定义两个指针变量p和q
初始时均指向头结点的下一个结点(链表的第一个结点)
p指针沿链表移动;当p指针移动到第k个结点时，q指针开始于p指针同步移动;
当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。
描述算法的详细实现步骤:
① count=0, p和q指向链表表头结点的下一个结点。
② 若p为空，转⑤
③ 若count等于k,则q指向下一个结点;否则，count = count +1。
④ p指向下一个结点，转②
⑤ 若count等于k,则查找成功，输出该结点的data域的值，返回1;
否则，说明超过了线性表的长度,查找长度,返回0。
⑥ 算法结束。
程序设计语言描述算法:
*/
typedef struct LNode
{
	int data;
    struct LNode *link;
}LNode,*LinkList

int Search_k(LinkList list,int k)
{
    LNode*p = list->link,*q = list->link; //指针p、q指示第一个结点
    int count =0;
    while(p!=NULL) //遍历链表直到第一个结点
    {
        if(count < k) count++; //计数，若count<k只移动p
        else q = q->link;
        p = p->link;  //之后让p、q同步移动
    }//while
    if(count < k)  //查找失败返回0
    	return 0;  //否则打印并返回1
    else
    {
        printf("%d",q->data);
    }
}