顺序表上基本操作的实现
线性表在采用不同的存储结构时，它的描述方法是不一样的，那么它的基本操作实现方法也截然不同。下面来看线性表在顺序存储下，也就是顺序表的每一个基本操作的具体实现方法以及编写方法。
插入操作
还是上一个例子，一群朋友去吃火锅。此时有一个女生过来了，她叫小红。小红是小绿的女朋友，当然想和小绿坐在一起，但是小绿旁边是没有空位置的。所以小绿麻烦他旁边的朋友小黄和小黑依次移动了一个位置。这样就空出了一个位置，小红就可以过来坐下了。这样就完成了一个类似顺序表插入的过程。
代码实现
知道了顺序表插入的大致过程，来看它用程序语言是如何编写的。首先画出了一个顺序表
其中数据元素是连续存放的。接着标出了存放该顺序表数据元素的数组下标。注意一下，数组下标是从 0 开始的，而顺序表的元素标号是从 1 开始的。接着用 C++ 写出了该插入操作的函数体：
bool ListInsert(SqList &L, int i, ElemType e) {
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;
}
它的返回值类型是一个布尔类型，表示如果插入成功会返回一个 True ，插入失败会返回一个 False。它有三个参数，分别是一个引用类型的顺序表 L，这里为什么用引用类型？因为在函数体内部进行操作，其实是作用一个局部变量上的，不会真正作用到这个参数上，如果不用引用类型，是不能把插入操作真正作用到传入的顺序表上的。接着是一个整型变量 i，它表示的是插入的位置，要注意在采用插入操作时，往往是前插法，这是一个默认规定。还有一点要注意的就是，i 对应的是顺序表的表号而非数组的下标。最后一个参数是所插入的数据元素 e。
首先第一个条件 i<1 || i>L.length+1 ，顺序表的元素标号是从 1 开始的，i 表示的是插入的位置，如果插入的位置是 0 或者更小，又或者比 L.length+1 还大，都是不合法的。第二个条件判断的是插入的数组是否有足够空间去插入，因为数组不可以增加容量，一旦满了就没用新的空间去提供插入了。循环语句中申请了变量 j 初始化为顺序表的长度，j 进行减一操作，一直到 j=i 的时候中止循环。循环体中 L.data[j] = L.data[j-1] 的意思就是把每一个数据元素向后移了一位，一直移动到 ai 移动到原先 ai+1 的位置。 执行完了所有的循环，空出了一个位置用于插入，L.data[i-1] = e 就是把要插入的元素放到该位置。注意，在 i 的位置，元素对应的下标是 i-1。最后将顺序表的长度加一。
时间复杂度
再来看一下这个程序的时间复杂度，当循环次数最少时，它就是最好的时间复杂度，什么时候循环次数最少呢？发现当在顺序表的尾部，也就是 L.length+1 的时候...
课后习题
【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; } }提示：算法程序题，如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后开始许愿
666