Geekerstar

《数据结构题集(C语言版)》习题解析(二)线性表
基础知识题2.1 描述以下三个概念的区别:头指针,头结点,首元结点(第一个元素结点)。解:头指针是指向链表中第一个...
扫描右侧二维码阅读全文
17
2018/03

《数据结构题集(C语言版)》习题解析(二)线性表

基础知识题

2.1 描述以下三个概念的区别:头指针,头结点,首元结点(第一个元素结点)。
解:
头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针。若链表中附设头结点,则不管线性表是否为空表,头指针均不为空,否则表示空表的链表的头指针为空。
头结点是为了操作方便,在链表的首元结点之前附设的一个结点,该结点的数据域中不存储线性表的数据元素,其作用是为了对链表进行操作时,可以对空表、非空表的情况以及对首元结点进行统一处理。
首元结点是指链表中存储线性表中第一个数据元素a1的结点。
这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点,是不同的存储结构表示同一逻辑结构的间题。

2.2 填空题。
解:
(1) 在顺序表中插入或删除一个元素,需要平均移动表中一半元素,具体移动的元素个数与元素在表中的位置有关。
(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。
(3) 在单链表中,除了首元结点外,任一结点的存储位置由其直接前驱结点的链域的值指示。
(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理

2.3 在什么情况下用顺序表比链表好?
解:
当线性表的数据元素在物理位置上是连续存储的时候,用顺序表比用链表好,其特点是可以进行随机存取。

2.4 对以下单链表分别执行下列各程序段,并画出结果示意图。
2.png

解:

1)Q=P->next;
(2)L=P->next;
(3)R->data=P->data;
(4)R->data=P->next->data;
(5)P->next->next->next->data=P->data;
(6)T=P;
      while(T!=NULL)
      {
            T->data=T->data*2;
            T=T->next;
      }
(7)T=P;
      while(T->next!=NULL)
      {
            T->data=T->data*2;
            T=T->next;
      }

7.jpg

2.5 画出执行下列各行语句后各指针及链表的示意图。

    L=(LinkList)malloc(sizeof(LNode));    P=L;
    for(i=1;i<=4;i++){
        P->next=(LinkList)malloc(sizeof(LNode));
        P=P->next;    P->data=i*2-1;
    }
    P->next=NULL;
    for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);
    for(i=1;i<=3;i++) Del_LinkList(L,i);

解:

8.jpg

2.6 已知L是无表头结点的单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。
a.在P结点后插入S结点的语句序列是__(4)(1)__。
b.在P结点前插入S结点的语句序列是__(7)(11)(8)(4)(1)__。
c.在表首插入S结点的语句序列是__(5)(12)__。
d.在表尾插入S结点的语句序列是__(9)(1)(6)__。
(1)P->next=S;
(2)P->next=P->next->next;
(3)P->next=S->next;
(4)S->next=P->next;
(5)S->next=L;
(6)S->next=NULL;
(7)Q=P;
(8)while(P->next!=Q)

    P=P->next;

(9)while(P->next!=NULL)

    P=P->next;

(10)P=Q;
(11)P=L;
(12)L=S;
(13)L=P;

2.7已知L是带表头结点的非空单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。
a.删除P结点的直接后继结点的语句序列是__(11)(3)(14)__。
b.删除P结点的直接前驱结点的语句序列是__(10)(12)(8)(3)(14)__。
c.删除P结点的语句序列是__(10)(12)(7)(3)(14)__。
d.删除首元结点的语句序列是__(12)(11)(3)(14)__。
e.删除尾元结点的语句序列是__(9)(11)(3)(14)__。

(1)P=P->next;
(2)P->next=P;
(3)P->next=P->next->next;
(4)P=P->next->next;
(5)while(P!=NULL)

    P=P->next;

(6)while(Q->next!=NULL)

  {
    P=Q;
    Q=Q->next;
  }

(7)while(P->next!=Q)

    P=P->next;

(8)while(P->next->next!=Q)

    P=P->next;

(9)while(P->next->next!=NULL)

    P=P->next;

(10)Q=P;
(11)Q=P->next;
(12)P=L;
(13)L=L->next;
(14)free(Q);

2.8 已知P结点是某双向链表的中间结点,试从下列提供的答案中选择合适的语句序列。
a.在P结点后插入S结点的语句序列是__(7)(12)(3)(6)__。
b.在P结点前插入S结点的语句序列是__(8)(4)(5)(13)__。
c.删除P结点的直接后继结点的语句序列是__(15)(1)(11)(18)__。
d.删除P结点的直接前驱结点的语句序列是__(16)(2)(10)(18)__。
e.删除P结点的语句序列是__(14)(9)(17)__。
(1)P->next=P->next->next;
(2)P->priou=P->priou->priou;
(3)P->next=S;
(4)P->priou=S;
(5)S->next=P;
(6)S->priou=P;
(7)S->next=P->next;
(8)S->priou=P-priou;
(9)P->priou->next=P->next;
(10)P->priou->next=P;
(11)P->next->priou=P;
(12)P->next->priou=S;
(13)P->priou->next=S;
(14)P->next->priou=P->priou;
(15)Q=P->next;
(16)Q=P->priou;
(17)free(P);
(18)free(Q);

2.9 简述以下算法的功能。
(1) Status A(LinkedList L) { //L是无表头结点的单链表

(1)
Status A(LinkedList L)            //L是无表头结点的单链表
{
    if(L&&L->next)
    {
        Q=L;
        L=L->next;
        P=L;
        while(P->next)
            P=P->next;
        P->next=Q;
        Q->next=NULL;
    }
    return    OK;
}//A
(2)
void BB(LNode *s, LNode *q)
 {
    p=s;
    while(p->next!=q) p=p->next;
    p->next=s;
}//BB
void AA(LNode *pa, LNode *pb)
{//pa和pb分别指向单循环链表中的两个结点
    BB(pa, pb);
    BB(pb, pa);
}//AA

解:
(1) 如果L的长度不小于2,将L的首元结点变成尾元结点。
(2) 将单循环链表拆成两个单循环链表。

算法设计题

本章算法设计题设计的顺序表和线性链表的类型定义如下:
#define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    typedef struct
    {
ElemType *elem;            //存储空间基址
        int            length;            //当前长度
        int            listsize;            //当前分配的存储容量
    }SqList;                            //顺序表类型
注:此文档中,ElemType被定义为int类型。
typedef struct LNode
{
        ElemType    data;
        Struct    Lnode    *next;
    }LNode, *LinkList;                //线性链表类型

2.10 指出以下算法中的错误和低效之处,并将它改写为一个既正确又高效的算法。

Status DeleteK(SqList &a,int i,int k)
{
    //本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素
    if(i<1||k<0||i+k>a.length) return INFEASIBLE;//参数不合法
    else {
for(count=1;count<k;count++){
    //删除第一个元素
    for(j=a.length;j>=i+1;j--) a.elem[j-i]=a.elem[j];
            a.length--;
        }
    return OK;
}

解:

错误有两处:
(1)参数不合法的判别条件不完整。合法的入口参数条件为:(删除时包括第i个元素)(0<i≤a.length)&&(0≤k≤a.length-i+1)
(2)第二个for语句中,元素前移的次序错误。
低效之处是每次删除一个元素的策略。
修改如下:

/*代码参考自StrayedKing,略有修改*/
#include <stdio.h>
#include "Status.h"
#include "SequenceList.c"

/* 函数原型 */
Status Algo_2_10(SqList *a, int i, int k);
void PrintElem(LElemType_Sq e);            //测试函数,打印整型 

int main(int argc, char *argv[])
{
    SqList L;
    int i;
    
    if(InitList_Sq(&L))                    //链表L创建成功
    {
        for(i=1; i<=20; i++)                //链表L中元素1~20 
            ListInsert_Sq(&L, i, i);    
    }
    
    printf("L = ");
    ListTraverse_Sq(L, PrintElem);         //输出L
    printf("\n\n");    
    
    printf("删除第 5 个元素起的 10 个元素...\n"); 
    Algo_2_10(&L, 5, 10);
    printf("此时L = ");
    ListTraverse_Sq(L, PrintElem);         //输出L
    printf("\n\n");
        
    return 0;
}

/*
题2.10:删除顺序表中从第i个元素起的k个元素
*/
Status Algo_2_10(SqList *a, int i, int k)
{
    int j;
    
    if(i<1 || i>(*a).length || k<0 || i+k-1>(*a).length)
        return ERROR;
    
    for(j=i+k; j<=(*a).length; j++)
        (*a).elem[j-k-1] = (*a).elem[j-1];
    
    (*a).length -= k;
    
    return OK;
}

void PrintElem(LElemType_Sq e)
{
    printf("%d ", e);
}

2.11 设顺序表va中的数据元素递增有序。试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。
解:

#include <stdio.h>
#include <stdlib.h>//提供malloc、realloc、free、exit原型
#include "Status.h"  
#include "SequenceList.c"

/* 函数原型 */
Status Algo_2_11(SqList *va, LElemType_Sq x);
void PrintElem(LElemType_Sq e);            //测试函数,打印整型 

int main(int argc, char *argv[])
{
    SqList L;
    int i;
    
    if(InitList_Sq(&L))                    //链表L创建成功
    {
        for(i=1; i<=10; i++)                //链表L中元素1~20 
            ListInsert_Sq(&L, i, 2*i);    
    }
    
    printf("L = ");
    ListTraverse_Sq(L, PrintElem);             //输出L
    printf("\n\n");    
    
    printf("将元素 \"5\" 插入到链表L中...\n"); 
    Algo_2_11(&L, 5);
    printf("此时L = ");
    ListTraverse_Sq(L, PrintElem);             //输出L
    printf("\n\n");
        
    return 0;
}

/*
题2.11:将x插入到递增序列va中 
*/
Status Algo_2_11(SqList *va, LElemType_Sq x)
{
    int i;
    LElemType_Sq *newbase;
    
    if(!(*va).length)
        return ERROR;
    
    if((*va).length==(*va).listsize)        //若存储空间已满,需开辟新空间 
    {
        newbase = (LElemType_Sq*)realloc((*va).elem, ((*va).listsize+LISTINCREMENT)*sizeof(LElemType_Sq));
        if(!newbase)
            exit(OVERFLOW);

        (*va).elem = newbase;
        (*va).listsize += LISTINCREMENT;
    }
    
    for(i=(*va).length; i>=1; i--)
    {
        if((*va).elem[i-1]>x)
            (*va).elem[i] = (*va).elem[i-1];
        else    
            break;
    }
    
    (*va).elem[i] = x;
    (*va).length++;
    
    return OK;
}

void PrintElem(LElemType_Sq e)
{
    printf("%d ", e);
}

2.12 设A=(a1,...,an)和B=(b1,...,bn)均为顺序表,A'和B'分别为A和B中除去最大共同前缀后的子表(例如,A=(x,y,y,z,x,z),B=(x,y,y,z,y,x,x,z),则两者中最大的共同前缀为(x,y,y,z),在两表中除去最大共同前缀后的子表分别为A'=(x,z)和B'=(y,x,x,z))。若A'=B'=空表,则A=B;若A'=空表,而B'≠空表,或者两者均不为空表,且A'的首元小于B'的首元,则A<B;否则A>B。试写一个比较A,B大小的算法(请注意:在算法中,不要破坏原表A和B,并且,也不一定先求得A'和B'才进行比较)。
解:

#include <stdio.h>
#include <stdlib.h>//提供malloc、realloc、free、exit原型
#include "SequenceList.c"

/* 函数原型 */
int Algo_2_12(SqList A, SqList B);
void PrintElem(LElemType_Sq e);        //测试函数,打印整型 

int main(int argc, char *argv[])
{
    int i, mark;
    SqList A, B;
    int a[7] = {1, 2, 3, 4, 5, 9, 12};
    int b[7] = {1, 2, 3, 4, 5, 11, 12};
    
    InitList_Sq(&A);
    InitList_Sq(&B);
    
    for(i=1; i<=7; i++)
    {
        ListInsert_Sq(&A, i, a[i-1]);
        ListInsert_Sq(&B, i, b[i-1]);
    }
    
    printf("构建完成的顺序表为:\n");
    printf("A = ");
    ListTraverse_Sq(A, PrintElem);
    printf("\n");
    printf("B = ");
    ListTraverse_Sq(B, PrintElem);
    printf("\n\n");        
    
    mark = Algo_2_12(A, B);
    printf("后缀比较结果:");
    if(mark<0)
        printf("A<B\n");
    else if(mark>1)
        printf("A>B\n");
    else
        printf("A==B\n");
    printf("\n");                
    
    return 0;
}

/*
题2.12:比较顺序表后缀大小
*/
int Algo_2_12(SqList A, SqList B)
{
    int i;

    i = 0;
    
    while(i<A.length && i<B.length)            //A、B均未扫描完 
    {
        if(A.elem[i]>B.elem[i])
            return 1;
        else if(A.elem[i]<B.elem[i])
            return -1;
        else
            i++;                                //相等时比较下一元素 
    }
    
    if(i<A.length)                            //A还有剩余,A大 
        return 1;
    else if(i<B.length)                        //B还有剩余,B大 
        return -1;
    else
        return 0;                                //同时扫描完,相等 
}

void PrintElem(LElemType_Sq e)
{
    printf("%d ", e);
}

2.13 试写一算法在带头结点的单链表结构上实现线性表操作LOCATE(L,X)。

#include <stdio.h>
#include "SinglyLinkedList.c"
/* 函数原型 */
int Algo_2_13(LinkList L, LElemType_L x);
void PrintElem(LElemType_L e);            //测试函数,打印整型 

int main(int argc, char *argv[])
{
    LinkList L;
    int i;
    
    if(InitList_L(&L))                    //链表L创建成功
    {
        for(i=1; i<=10; i++)
            ListInsert_L(L, i, 2*i);    
    }
    
    printf("L = ");
    ListTraverse_L(L, PrintElem);         //输出L
    printf("\n\n");    
    
    printf("元素 \"12\" 在链表L中的位置为 %d \n", Algo_2_13(L, 18)); 
    printf("\n");
        
    return 0;
}

/*
题2.13:寻找元素x再L中的位置
*/
int Algo_2_13(LinkList L, LElemType_L x)
{
    int i;
    LinkList p;
        
    if(L)
    {
        i = 1;        
        p = L->next;
        while(p)
        {
            if(p->data==x)
                return i;
            i++;
            p = p->next;
        }
    }
    
    return 0;
}

void PrintElem(LElemType_L e)
{
    printf("%d ", e);
}

2.14试写一算法在带头结点的单链表结构上实现线性表操作LENGTH(L)。
解:

#include <stdio.h>
#include "SinglyLinkedList.c"
/* 函数原型 */
int Algo_2_14(LinkList L);
void PrintElem(LElemType_L e);                //测试函数,打印整型 

int main(int argc, char *argv[])
{
    LinkList L;
    int i;
    
    if(InitList_L(&L))                        //链表L创建成功
    {
        for(i=1; i<=10; i++)                    //链表L中元素1~20 
            ListInsert_L(L, i, 2*i);    
    }
    
    printf("L = ");
    ListTraverse_L(L, PrintElem);             //输出L
    printf("\n\n");    
    
    printf("链表L的长度为 %d \n", Algo_2_14(L)); 
    printf("\n");
        
    return 0;
}

/*
题2.14:求L长度 
*/
int Algo_2_14(LinkList L)
{
    return ListLength_L(L);                //已定义 
}

void PrintElem(LElemType_L e)
{
    printf("%d ", e);
}

2.15 已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后),假设指针hc指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。请分析你的算法和时间复杂度。
解:

#include <stdio.h>
#include "Status.h" 
#include "SinglyLinkedList.c"
/* 函数原型 */
Status Algo_2_15(LinkList ha, LinkList hb, LinkList *hc);
void PrintElem(LElemType_L e);                    //测试函数,打印整型 

int main(int argc, char *argv[])
{
    LinkList ha, hb, hc;
    int i;
    
    if(InitList_L(&ha) && InitList_L(&hb) && InitList_L(&hc))    //链表创建成功
    {
        for(i=1; i<=5; i++)                        //链表赋值
            ListInsert_L(ha, i, i);        
        for(i=1; i<=7; i++)                        //链表赋值
            ListInsert_L(hb, i, 2*i);        
    }
    
    printf("ha = ");
    ListTraverse_L(ha, PrintElem);                 //输出
    printf("\n");
    printf("hb = ");
    ListTraverse_L(hb, PrintElem);     
    printf("\n\n");    
    
    Algo_2_15(ha, hb, &hc);
    printf("连接ha和hb之后的链表为:\nhc = "); 
    ListTraverse_L(hc, PrintElem);     
    printf("\n\n");    
        
    return 0;
}

/*
题2.15:连接ha和hb
*/
Status Algo_2_15(LinkList ha, LinkList hb, LinkList *hc)
{
    LinkList pa, pb;                                //pa、pb分别指向ha、hb头结点 

    if(ha && hb)
    {
        pa = ha;
        pb = hb;
        
        while(pa->next && pb->next)
        {
            pa = pa->next;
            pb = pb->next;
        }
        
        if(!pa->next)
        {
            *hc = ha;
            pa->next = hb->next;        
        }
        
        if(!pb->next)
        {
            *hc = hb;
            pb->next = ha->next;
        }
        
        return OK;
    }
    
    return ERROR;    
}

void PrintElem(LElemType_L e)
{
    printf("%d ", e);
}

时间复杂度分析:此算法费时的操作主要为遍历链表,故时间复杂度只与链表ha或hb的长度有关,其时间复杂度为:m≤n ? O(m) : O(n)。

2.16 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后,将它们插入到表lb中的第j个元素之前。试问此算法是否正确?如有错,则请改正之。

Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len)
{
    if(i<0||j<0||len<0) return INFEASIBLE;
    p=la;    k=1;
    while(k<i){    p=p->next;    k++;    }
    q=p;
    while(k<=len){    q=q->next;    k++;    }
    s=lb; k=1;
    while(k<j){    s=s->next;    k++;    }
    s->next=p;     q->next=s->next;
    return OK;
}

2.17 试写一算法,在无头结点的动态单链表上实现线性表操作INSERT(L, i, b),并和在带头结点的动态单链表上实现相同操作的算法进行比较。

2.18 试写一算法,实现线性表操作Delete(L,i),并和在带头结点的动态单链表上实现相同操作的算法进行比较。

#include <stdio.h>
#include <stdlib.h>//提供malloc、realloc、free、exit原型
#include "Status.h" 
#include "SinglyLinkedList.c"

/* 函数原型 */
Status Algo_2_16(LinkList *la, LinkList *lb, int i, int j, int len);
Status Algo_2_17(LinkList *L, int i, LElemType_L b);
Status Algo_2_18(LinkList *L, int i);
void InitList_2_16(LinkList *L);        //初始化L 
void Output_2_16(LinkList L);            //输出L
     
int main(int argc, char *argv[])
{
    int i;
    LinkList la, lb;
    
    InitList_2_16(&la);
    InitList_2_16(&lb);
    
    printf("███题 2.17 验证...███\n");
    for(i=1; i<=10; i++)
    {
        Algo_2_17(&la, i, 2*i-1);
        Algo_2_17(&lb, i, 2*i);    
    }

    printf("创建好的无头结点链表为:\n");
    printf("la = ");        
    Output_2_16(la);
    printf("\n");
    printf("lb = ");
    Output_2_16(lb);
    printf("\n\n");

    printf("███题 2.16 验证...███\n");        
    printf("将la中从第2个结点起的5个结点插入到lb的第6个结点之前...\n");
    Algo_2_16(&la, &lb, 2, 6, 5); 
    printf("la = ");        
    Output_2_16(la);
    printf("\n");
    printf("lb = ");
    Output_2_16(lb);
    printf("\n\n");    

    printf("███题 2.18 验证...███\n");        
    printf("删除lb第6个结点起的5个结点...\n");
    for(i=1; i<=5; i++)
        Algo_2_18(&lb, 6);
    printf("删除完成后:lb = ");
    Output_2_16(lb);
    printf("\n\n");    
        
    return 0;
}

/*
题2.16:删除la中第i个结点起的len个结点并添加到lb第j个结点之前 
*/
/* 本题中的链表无头结点 */
Status Algo_2_16(LinkList *la, LinkList *lb, int i, int j, int len)
{
    LinkList p, q, s, prep;
    int k;
    
    if(i<0 || j<0 || len<0)
        return INFEASIBLE;
    
    p = *la;
    k = 1;
    prep = NULL;
    while(p && k<i)                    //在la中查找第i个结点,用p标记 
    {
        prep = p;
        p = p->next;
        k++; 
    }
    if(!p)                                //找不到第i个元素 
        return INFEASIBLE;

    q = p;                                //p指向la表中第i个结点 
    while(q && k<i+len-1)            //查找la表中第i+len-1个结点,用q标记 
    {
        q = q->next;
        k++;
    }
    if(!q)                            
        return INFEASIBLE;
        
    if(!prep)                            //i=1的情况 
        *la = q->next;
    else                                //完成删除 
        prep->next = q->next;

    if(j==1)
    {
        q->next = *lb;
        *lb = p;
    }
    else
    {
        s = *lb;
        k = 1;
        while(s && k<j-1)                //查找lb表中第j-1个元素 
        {
            s = s->next;
            k++;
        }
        if(!s)
            return INFEASIBLE;
            
        q->next = s->next;
        s->next = p;                    //完成插入 
        
        return OK;
    }

}

/*
题2.17:将b插入为L的第i个结点 
*/
/* 本题中的链表无头结点 */
Status Algo_2_17(LinkList *L, int i, LElemType_L b)
{
    LinkList p, q;
    int count;
    
    p = (LinkList)malloc(sizeof(LNode));
    if(!p)
        exit(OVERFLOW);
    p->data = b;
    
    if(i>0)
    {
        if(i==1)
        {
            p->next = *L;
            *L = p;
            return OK;            
        }
        else
        {
            if(*L)
            {
                count = 1;
                q = *L;
                while(count<i-1 && q)
                {
                    count++;
                    q = q->next;    
                }
                
                if(q)
                {
                    p->next = q->next;
                    q->next = p;
                    return OK;
                }
            }        
        }
    }

    return ERROR;
}

/*
题2.18:删除L的第i个结点
*/
/* 本题中的链表无头结点 */
Status Algo_2_18(LinkList *L, int i)
{
    LinkList p, q;
    int count;
    
    if(i>1)
    {
        p = *L;
        count = 1;
        while(p && count<i-1)
        {
            count++;
            p = p->next;
        }
        
        if(p)
        {
            if(count>i-1)                        //删除头结点
            {
                *L = (*L)->next;
                free(p);
                return OK;
            }
            else
            {
                if(p->next)                    //第i个结点存在
                {
                    q = p->next;
                    p->next = q->next;
                    free(q);
                    return OK;
                } 
            }
        }
    }
    
    return ERROR;
}

void InitList_2_16(LinkList *L)
{
    *L = NULL;
}

void Output_2_16(LinkList L)
{
    LinkList p = L;
    
    while(p)
    {
        printf("%2d ", p->data);
        p = p->next;
    }
}

2.19 已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删结点空间,并分析你的算法的时间复杂度(注意,mink和maxk是给定的两个参变量,它们的值可以和表中的元素相同,也可以不同)。

时间复杂度分析:最坏的情况是全部扫描完也没找到适合的元素,故时间复杂度与链表长度有关,为O(Length(L))。

2.20 同2.19题条件,试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同),同时释放被删结点空间,并分析你的算法的时间复杂度。
解:

#include <stdio.h>
#include <stdlib.h>//提供malloc、realloc、free、exit原型
#include "Status.h"  
#include "SinglyLinkedList.c"

/* 函数原型 */
Status Algo_2_19_1(LinkList L, int mink, int maxk); 
Status Algo_2_19_2(LinkList L, int mink, int maxk);
Status Algo_2_20(LinkList L);
void PrintElem(LElemType_L e);                    //测试函数,打印整型 

int main(int argc, char *argv[])
{
    LinkList L;
    int mink, maxk_1, maxk_2, i;
    int a[] = {1, 2, 2, 3, 4, 4, 5, 6, 7, 7};
    
    mink = 2;
    maxk_1 = 4;
    maxk_2 = 6;
    
    InitList_L(&L);
    
    for(i=0; i<10; i++)
        ListInsert_L(L, i+1, a[i]);
    
    printf("原链表L = ");
    ListTraverse_L(L, PrintElem);
    printf("\n\n");
    
    printf("███题 2.19 验证...███\n");
    printf("删除链表中大于 %d 且小于 %d 的元素之后...\n", mink, maxk_1);
    Algo_2_19_1(L, mink, maxk_1);    
    printf("L = ");
    ListTraverse_L(L, PrintElem);
    printf("\n");

    printf("删除链表中大于 %d 且小于 %d 的元素之后...\n", mink, maxk_2);
    Algo_2_19_2(L, mink, maxk_2);    
    printf("L = ");
    ListTraverse_L(L, PrintElem);
    printf("\n\n");
    
    printf("███题 2.20 验证...███\n");
    printf("去掉链表中多余的重复元素...\n");
    Algo_2_20(L);    
    printf("L = ");
    ListTraverse_L(L, PrintElem);
    printf("\n\n");    
    
    
    return 0;
}

/*
题2.19:删除递增线性表中元素大于mink小于maxk之间的结点
*/
/* 方法1 */
Status Algo_2_19_1(LinkList L, int mink, int maxk)
{
    LinkList p, pre, s;

    if(!L || !L->next)            //L不存在或为空表时,无法删除 
        return ERROR;

    if(mink>=maxk)                //阙值设置错误 
        return ERROR;
            
    pre = L;
    p = pre->next;                //p指向首结点 

    while(p && p->data<maxk)     //上限 
    {
        if(p->data<=mink)         //下限 
        {
            pre = p;
            p = p->next;
        }
        else                        //删掉满足条件的结点 
        {
            s = p;
            pre->next = p->next;
            p = p->next;
            free(s);
        }
    }
    
    return OK;
}

/*
题2.19:删除递增线性表中元素大于mink小于maxk之间的结点
*/
/* 方法2 */
Status Algo_2_19_2(LinkList L, int mink, int maxk)
{
    LinkList p, pre, s;

    if(!L || !L->next)                //L不存在或为空表时,无法删除 
        return ERROR;

    if(mink>=maxk)                    //阙值设置错误 
        return ERROR;

    pre = L;
    p = pre->next;                    //p指向首结点 


    while(p && p->data<=mink)        //下限
    {
        pre = p;
        p = p->next;
    }

    if(p)
    {
        while(p && p->data<maxk)        //上限
        {
            s = p;
            pre->next = p->next;
            p = p->next;
            free(s);
        }
        return OK;
    }
}

/*
题2.20:删除表中值相同的多余结点
*/
Status Algo_2_20(LinkList L)
{
    LinkList p, pre, s;
        
    if(!L || !L->next)                //L不存在或为空表时,无法删除 
        return ERROR;

    pre = L->next;
    p = pre->next;                    //p指向首结点
    
    while(p)
    {
        if(pre->data==p->data)
        {
            s = p;
            pre->next = p->next;
            p = p->next;
            free(s);
        }
        else
        {
            pre = p;
            p = p->next;
        }
    }    
    
    return OK;
} 

void PrintElem(LElemType_L e)
{
    printf("%d ", e);
}

说明

由于数据结构这门课程的特殊性,书中涉及了大量代码需要去敲,很难做到每周更新一个章节,因此我做了如下决定:
1.本博客不再完全以章节的形式更新数据结构,取而代之的是:

  • 《数据结构(C语言版)》学习笔记总结(X)XXX的形式更新基础概念。
  • 《数据结构题集(C语言版)》习题解析(X)XXX的形式更新课后基础知识题。
  • 以《数据结构·编程题解》章节-内容的形式更新课本及配套题集的编程题答案。

2.预计两个月内更新完毕,并将所有内容整理至极客文库,以供查阅。在更新完毕之前会一直修改完善,最终以极客文库版本为最终版。


如果您发现了文章有任何错误欢迎指正,有任何意见或建议,或者有疑问需要我提供帮助,也欢迎在下面留言,只需输入昵称+邮箱即可,网站或博客可选填。对于所有留言内容我会及时回复,非常期待与大家的交流![/scode]

版权声明:本文(除特殊标注外)为原创文章,版权归 Geekerstar 所有。

本文链接:http://www.geekerstar.com/technology/565.html

除了有特殊标注文章外欢迎转载,但请务必标明出处,格式如上,谢谢合作。

本作品采用 知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议 进行许可。

最后修改:2018 年 03 月 17 日 02 : 24 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论