线性表的应用
标签: 数据结构
学习人数: 9330


全屏播放
赞赏支持

顺序表上基本操作的实现

线性表在采用不同的存储结构时,它的描述方法是不一样的,那么它的基本操作实现方法也截然不同。下面来看线性表在顺序存储下,也就是顺序表的每一个基本操作的具体实现方法以及编写方法。

 

插入操作

还是上一个例子,一群朋友去吃火锅。此时有一个女生过来了,她叫小红。小红是小绿的女朋友,当然想和小绿坐在一起,但是小绿旁边是没有空位置的。所以小绿麻烦他旁边的朋友小黄和小黑依次移动了一个位置。这样就空出了一个位置,小红就可以过来坐下了。这样就完成了一个类似顺序表插入的过程。

代码实现

知道了顺序表插入的大致过程,来看它用程序语言是如何编写的。首先画出了一个顺序表

其中数据元素是连续存放的。接着标出了存放该顺序表数据元素的数组下标。注意一下,数组下标是从 0 开始的,而顺序表的元素标号是从 1 开始的。接着用 C++ 写出了该插入操作的函数体:

bool ListInsert(SqList &L, int i, ElemType e) {  
    if(i<1 || i>...
登录查看完整内容


课后作业

课后习题

 

【2019年真题】设线性表L=(a1,a2,a3…,an-2,an-1,an)采用带头结点的单链表保存,链表中结点定义如下:

typedef struct node {  
    int data;  
    struct node* next;  
} NODE;  

请设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L中的各结点,得到线性表L'=(a1,an,a2,an-1,a3,an-2…)。
要求:
(1) 给出算法的基本设计思想
(2) 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
(3) 说明你所设计的算法的时间复杂度。

参考答案:
(1)算法的基本设计思想:
算法分3步完成。第1步,采用两个指针交替前行,找到单链表的中间结点;第2步,将单链表的后半段结点原地逆置;第3步,从单链表前后两段中依次各取一个结点,按要求重排。
(2)算法实现:

void change_list(NODE *h) 
{
    NODE *p, *q, *r, *s;
    p = q = h;
    while (q->next != NULL) //寻找中间结点
    {
        p = p->next;    // p走一步
        q = q->next;
        if (q->next != NULL) q = q->next; //q走两步
    }
    q = p->next;    //p所值结点为中间结点,q为后半段链表的首结点
    p->next = NULL;
    while (q != NULL)//将链表后半段逆置
    {
        r = q->next;
        p->next = q;
        q = r;
    }
    s = h->next;    //s指向前半段的第一个数据结点,即插入点
    q = p->next;    //q指向后半段的第一个数据结点
    p->next = NULL;
    while (q != NULL)//将链表后半段的结点插入到指定位置
    {
        r = q->next;   //r指向后半段的下一个结点
        q->next = s->next; //将q所指结点插入到s所指结点之后
        s->next = q;
        s = q->next;    //s指向前半段的下一个插入点
        q = r;
    }
}

(3)算法的时间复杂度:
参考答案的时间复杂度为O(n)。


【2012年真题】假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。 

设 str1 和 str2 分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算法,找出由 str1 和 str2 所指向两个链表共同后缀的起始位置(如图中字符 i 所在结点的位置 p)。要求: 
1)给出算法的基本设计思想。 
2)根据设计思想,采用 C 或 C++或 JAVA 语音描述算法,关键之处给出注释。 
3)说明你所设计算法的时间复杂度。

参考答案:
1)顺序遍历两个链表到尾结点时,并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长 k 个结点,我们先在长链表上遍历 k 个结点,之后同步遍历两个链表,这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的,所以它们肯定同时到达第一个公共结点。算法的基本设计思想: 
①分别求出 str1 和 str2 所指的两个链表的长度 m 和 n; 
②将两个链表以表尾对齐:令指针 p、q 分别指向 str1 和 str2 的头结点,若 m>=n,则使 p 指向链表中的第 m-n+1 个结点;若 m<n,则使 q 指向链表中的第 n-m+1 个结点,即使指针 p 和 q 所指的结点到表尾的长度相等。 
③反复将指针 p 和 q 同步向后移动,并判断它们是否指向同一结点。若 p 和 q 指向同一结点,则该点即为所求的共同后缀的起始位置。 
2)算法的 C 语言代码描述:

LinkNode *Find_1st_Common(LinkList str1,LinkList str2){  
    int len1=Length(str1),len2=Length(str2);  
    LinkNode *p,*q;  
    for(p=str1;len1>len2;len1--) //使 p 指向的链表与 q 指向的链表等长  
        p=p->next;  
    for(q=str2;len1<len2;len2--) //使 q 指向的链表与 p 指向的链表等长  
        q=q->next;  
    while(p->next!=NULL&&p->next!=q->next){//查找共同后缀起始点  
        p=p->next; //两个指针同步向后移动  
        q=q->next;  
    }  
    return p->next; //返回共同后缀的起始点  
}  

3)时间复杂度为:O(len1+len2)或 O(max(len1,len2)),其中 len1、len2 分别为两个链表的长度。 


【2010年真题】设将 n(n>1)个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法。将 R 中保存的序列循环左移 p(0<p<n)个位置,即将 R 中的数据由(X0, X1…Xn-1)变换为(Xp,Xp+1 …Xn-1, X0, X1…Xp-1)。要求: 
⑴ 给出算法的基本设计思想。 
⑵ 根据设计思想,采用 C 或 C++或 JAVA 语言描述算法,关键之处给出注释。 
⑶ 说明你所设计算法的时间复杂度和空间复杂度。 

参考答案:
(1)算法的基本设计思想: 
可以将这个问题看做是把数组 ab 转换成数组 ba(a 代表数组的前 p 个元素,b 代表数组中余下的 n-p 个元素),先将 a 逆置得到 a-1b,再将 b 逆置得到 a-1b-1,最后将整个 a-1b-1 逆置得到(a-1b-1)-1 =ba。设 Reverse 函数执行将数组元素逆置的操作,对 abcdefgh 向左循环移动 3(p=3)个位置的过程如下: 
Reverse(0,p-1)得到 cbadefgh; 
Reverse(p,n-1)得到 cbahgfed; 
Reverse(0,n-1)得到 defghabc; 
注:Reverse 中,两个参数分别表示数组中待转换元素的始末位置。 
(2)使用 C 语言描述算法如下: 

void Reverse(int R[],int from,int to) {   
    int i,temp;   
    for(i = 0; i < (to-from+1)/2; i++)   
    {   
        temp = R[from+i];   
        R[from+i] = R[to-i];   
        R[to-i] = temp;   
    }   
}//Reverse  
  
void Converse(int R[],int n,int p) {   
    Reverse(R,0,p-1);   
    Reverse(R,p,n-1);   
    Reverse(R,0,n-1);   
}  

(3)上述算法中三个 Reverse 函数的时间复杂度分别为O(p/2) 、O((n-p)/2)和O(n/2),故所设计的算法的时间复杂度为O(n),空间复杂度为O(1)。
另解,借助辅助数组来实现: 
算法思想:创建大小为 p 的辅助数组 S,将 R 中前 p 个整数依次暂存在 S 中,同时将 R 中后 n-p 个整数左移,然后将 S 中暂存的 p 个数依次放回到 R 中的后续单元。 
时间复杂度为O(n),空间复杂度为O(p)。


【2009年真题】已知一个带有表头结点的单链表,结点结构为: 

假设该链表只给出了头指针 list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的 data 域的值,并返回 1;否则,只返回 0。要求: 
⑴ 描述算法的基本设计思想; 
⑵ 描述算法的详细实现步骤; 
⑶ 根据设计思想和实现步骤,采用程序设计语言描述算法(使用 C、C++或 Java 语言实现),关键之处请给出简要注释。 

参考答案:
(1)算法的基本设计思想: 
问题的关键是设计一个尽可能高效的算法,通过链表的一趟遍历,找到倒数第 k 个结点的位置。算法的基本设计思想是:定义两个指针变量 p 和 q,初始时均指向头结点的下一个结点(链表的第一个结点)。p 指针沿链表移动;当 p 指针移动到第 k 个结点时,q 指针开始与 p 指针同步移动;当 p 指针移动到最后一个结点时,q指针所指示结点为倒数第 k 个结点。以上过程对链表仅进行一遍扫描。 
(2)算法的详细实现步骤: 
① count=0,p 和 q 指向链表表头结点的下一个结点; 
② 若 p 为空,转⑤; 
③ 若 count 等于 k,则 q 指向下一个结点;否则,count=count+1; 
④ p 指向下一个结点,转②; 
⑤ 若 count 等于 k,则查找成功,输出该结点的 data 域的值,返回 1;否则,说明 k 值超过了线性表的长度,查找失败,返回 0; 
⑥ 算法结束。
(3)算法实现:

typedef int ElemType; //链表数据的类型定义  
typedef struct LNode{ //链表结点的结构定义  
    ElemType data; //结点数据  
    struct Lnode *link; //结点链接指针  
} *LinkList;  
  
int Search_k(LinkList list, int k){   
    //查找链表 list 倒数第 k 个结点,并输出该结点 data 域的值  
    LinkList 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 同步移动  
    }  
    if(count < k)  
        return 0; //查找失败返回 0  
    else { //否则打印并返回 1  
        printf("%d",q->data);   
        return 1;   
    }  
}  

提示:算法程序题,如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数,如果能用伪代码写出自然更好,比较复杂的地方可以直接用文字表达。 

 


登录后发布评论

1 条评论
xia
2020年12月17日 15:40

666