[线性表](7)题集_1
基本内容:
- 线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法
- 线性表的两类存储结构(顺序的和链式的)上基本操作的实现
- 稀疏多项式的抽象数据类型定义、表示和加法的实现
线性表的逻辑结构特性是数据元素之间存在着线性关系。
在计算机中表示这种关系的两类不同的存储结构分为:顺序存储结构和链式存储结构
前者表示线性表简称为顺序表,后者表示线性表简称为链表
顺序表:
- 静态顺序表:内存空间固定的,表的大小固定的,无法改变
- 动态顺序表:内存空间由用户自定义,可随着数据增大而重新分配
链表:
- 单向动态链表:只有一个指向后继结点的指针,结点空间由用户分配
- 双向动态链表:有两个指针,一个指向前置结点,一个指向后继结点,结点空间由用户分配
- 循环链表:尾结点的指针域指向头结点
- 静态链表:结合了顺序表易访问和链式表易操作的优点,通过一个整型数据游标来进行结点相链,操作途中要明确“备用表”和“数据表”的关系。空间由用户指定(在C语音里面,利用结构数组来表示)
基础知识题:
1.描述以下三个概念的区别:
- 头指针
- 头结点
- 首元节点
头指针:是指向表头数据的指针,它用于访问整个链表,存放整个链表的基址,在链表操作里边,头指针是不可或缺的角色
头结点:通常指的是头指针指向的结点,头结点可带数据可不带数据,在不带数据的情况下,头结点的指针域指向首元结点,头结点用于链接整个链表
首元结点:位于表头第一个带数据的结点,通常指头结点(不带数据)后的第一个结点,通过它对链表进行一系列操作。
2.填空题:
在顺序表中插入或删除一个元素,需要平均移动n/2个元素,具体移动的元素个数与需要删除或插入元素的位置有关
顺序表中逻辑相邻的元素的物理位置也紧邻,单链表中逻辑相邻的元素的物理位置不紧邻
在单链表中,除了首元结点外,任一节点的存储位置由它 前置结点的指针域指示
在单链表中设置头结点的作用是:用于链表结点的访问,易与控制整个链表,无需改变头指针的指向,链表逻辑清晰
3.在什么情况下用顺序表比链表好
在数据无需进行大规模的增删操作的时候,利用顺序表方便数据的引用以及修改,而在数据需要进行增删等操作的情况下,链表的存储方式比只需修改指针域的指向来修改结点之间的关系,而顺序表则需要大规模的移动数据
在已知数据的情况下利用顺序存储结构能更好的控制数据,而在未知的情况下利用链表能更好的控制数据
4.对以下单链表分别执行下列各程序段,并画出结果示意图
- Q=P->next
- L=P->next
- R->data=P->data
- R->data=P->next->data
- P->next->next->next->data=P->data
- T=P
- while(T!=NULL){T->data=T->data*2; T=T->next}
- T=P
- while(T->next!=NULL){T->data=T->data*2; T=T->next}
第一句,将Q指针指向P的后继结点
第二句,将L指针指向P的后继结点
第三句,将P指针指向的结点的数据域赋值给R指针指向结点的数据域
第四句,将P指向结点的后继结点的数据域赋值给R指针指向结点的数据域
第五句,将P指针指向结点数据域赋值给P第三个后继结点的数据域
第六句,将T指向P,当T指向的结点不为空的时候,将T指向结点的数据域*2,T指向下一个结点,继续循环
第七句,将T指向P,判断T的下一结点是否为空,将T指向结点的数据域*2,T指向下一个结点,继续循环
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);
}
先分析下题目:L作为头结点同时也作为头指针,程序先定义一个操作指针P让他指向L
再不断分配空间,一共分配了四个结点,链接至P后,链接完毕后,P已指向表尾,让P的指针域为空,程序示意图如下:
然后进入第二个循环,调用4次Ins_LinkList函数,该操作算法如下:
void Ins_LinkList(LinkList L, int j, int e)
{
LinkList P, node;
P = L;
for (int i = 1; i < j; i++)
{
P = P->next;
}
node = (LinkList)malloc(sizeof(LNode));
node->next = P->next;
P->next = node;
node->data = e;
}
不断在i+1的位置插入值为i*2的结点
- 第一次:插入位置为5,插入值为8
- 第二次:插入位置为4,插入值为6
- 第三次:插入位置为3,插入值为4
- 第四次:插入位置为2,插入值为2
运算后示意图如下:
后进入第二个循环语块调用三次Del_LinkList函数
删除第i个结点
完成算法如下:
void Del_LinkList(LinkList L, int i)
{
LinkList p, s;
p = L;
s = L->next;
for (int j = 1; j <= i && s != NULL; j++)
{
p = s;
s = s->next;
}
p->next = s->next;
free(s);
}
操作完成后示意图如下:
6.已知L表示无表头结点的单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列
-
在P结点后插入S结点的语句序列是:
- S->next=P->next;
- P->next=S;
- 在P结点前插入S结点的语句序列是:
- Q=P;
- P=L;
- while(P->next!=Q)P=P->next;
- S->next=P->next;
- P->next=S;
- 在表首插入S结点的语句序列是:
- S->next=L;
- L=S;
- 在表尾插入S结点的语句序列是:
- while(P->next!=NULL)P=P->next;
- P->next=S;
- S->next=NULL;
- 从下列语句中选出
- P->next=S;
- P->next=P->next->next;
- P->next=S->next;
- S->next=P->next;
- S->next=L;
- S->next=NULL;
- Q=P;
- while(P->next!=Q)P=P->next;
- while(P->next!=NULL)P=P->next;
- P=Q;
- P=L;
- L=S;
- L=P;
7.已知L是带表头结点的非空单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列
- 删除P结点的直接后继结点的语句序列是
- Q=P->next;
- P->next=P->next->next;
- free(Q);
- 删除P结点的直接前驱结点的语句序列是
- Q=P;
- P=L
- while(P->next!=Q)P=P->next;
- Q=P;
- P=L
- while(P->next!=Q)P=P->next;
- P->next=P->next->next;
- free(Q);
- 删除P结点的语句序列是
- Q=P;
- P=L
- while(P->next!=Q)P=P->next;
- P->next=P->next->next;
- free(Q);
- 删除首元结点的语句序列是
- P=L
- P=P->next;
- Q=P;
- P=L
- P->next=P->next->next;
- free(Q);
- 删除尾元结点的语句序列是
- while(P->next->next!=NULL)P=P->next;
- P->next=P->next->next;
- P=P->next;
- Q=P;
- free(Q);
- P=P->next;
- P->next=P;
- P->next=P->next->next;
- P=P->next->next;
- while(P!=NULL)P=P->next;
- while(Q->next!=NULL)P=P->next;
- while(P->next!=Q)P=P->next;
- while(P->next->next!=NULL)P=P->next;
- Q=P;
- Q=P->next;
- P=L
- L=L->next;
- free(Q);
8.已知P结点是某双向链表的中间结点,试从下列提供的答案中选择合适的语句序列
- 在P结点后插入S结点的语句序列是
- S->priou=p;
- S->next=P->next;
- P->next->priou=S;
- p->next=S;
- 在P结点前插入S结点的语句序列是
- S->priou=P->priou;
- P->priou->next=S;
- S->next=P;
- p->priou=S;
- 删除P结点的直接后继结点的语句序列是
- Q=P->next;
- P->next=P->next->next;
- P->next->priou=P;
- free(Q);
- 删除P结点的直接前驱结点的语句序列是
- Q=P->priou;
- P->priou=P->priou->priou;
- P->priou->next=P;
- free(Q);
- 删除P结点的语句序列是
- p->priou->next=p->next;
- P->next->priou=P->priou;
- free(p);
- P->next=P->next->next;
- P->priou=P->priou->priou;
- p->next=S;
- p->priou=S;
- S->next=P;
- S->priou=p;
- S->next=P->next;
- S->priou=P->priou;
- p->priou->next=p->next;
- P->priou->next=P;
- P->next->priou=P;
- P->next->priou=S;
- P->priou->next=S;
- P->next->priou=P->priou;
- Q=P->next;
- Q=P->priou;
- free(p);
- free(Q);
9.简述以下算法的功能:
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
}
这个算法一看就知道,将表头插到表尾,更新头指针指向。
void BB(LNode* s, LNode* q)
{
p = s;
while (p->next != q)
{
p = p -> next;
}
p->next = s;
}
void AA(LNode* pa, LNode* pb)
//pa和pb分别指向单循环链表中的两个结点
{
BB(pa, pb);
BB(pb, pa);
}
这个算法,就是将一个循环链表分割成两个循环链表
第一个函数的作用就将q之前的结点链接到头指针指向的节点,第二个函数的作用就是通过两个结点调用第一个函数,起到分割链表作用。
算法设计题:
按书本要求,以下算法涉及的顺序表和线性链表的类型定义如下:
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct
{
ElemType* elem;//存储空间的基址
int length;//当前长度
int listsize;//当前分配的空间长度
}SqList;
typedef struct LNode
{
ElemType data;
struct LNode* next
}LNode, * LinkList;//链表类型
10.指出下列算法中的错误和低效(费时)之处,并将它改写为一个既正确又高效的算法:
Status DeleteK(SqList& a, int i, int k)
//本过程从顺序表a中删除以第i个元素起的k个元素
{
if (i < || 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 - 1] = a.elem[j];
}
a.length--;
}
}
}
错误有两处:
- 参数不合法的判别条件不完整,合法的入口参数条件为:
- (0<i<a.length)||(0<=k<=a.length-i)
- 第二个错误是第二个循环语块中元素前移的次序错误
- 低效之处就是每次删除一个元素
时间复杂度取决于需要删除的次数和表的长度,正确的算法如下所示(完成测试代码)
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int* elem;
int length;
int listsize;
}SqList;
SqList S;
void DeleteK(SqList *S, int i, int k);
void InfoSqList(SqList);
int main()
{
S.elem = (int*)malloc(sizeof(int) * 100);
S.length = 0;
S.listsize = 100;
while (S.length < 10)
{
InfoSqList(S);
S.length++;
S.listsize--;
}
for (int i = 0; i < S.length; i++)
{
printf("%d ", S.elem[i]);
}
int i, e;
printf("\n请输入需要删除的起始位置:");
scanf("%d", &i);
printf("请输入需要删除的元素个数:");
scanf("%d", &e);
DeleteK(&S, i, e);
for (int i = 0; i < S.length; i++)
{
printf("%d ", S.elem[i]);
}
system("pause");
return 0;
}
void InfoSqList(SqList S)
{
scanf("%d", &S.elem[S.length]);
}
void DeleteK(SqList *S, int i, int e)
{
if (0 > i > S->length || 0 > e > S->length - i)
{
printf("删除位置或元素个数不合法");
exit(0);
}
for (int k = i + e; k <= S->length; k++)
{
S->elem[k - e] = S->elem[k];
}
S->length = S->length - e;
S->elem[S->length] = NULL;
}
11.设顺序表va中的数据元素递增有序,试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性
这题,有序,递增,那么一想到,二分查找,找到正确位置后插入:完整算法如下
int ListInsert(SqList *S, int e)
{
int len = S->length / 2;
int r = 0;
int l = S->length;
if (S->length<0)
{
printf("插入位置不合法\n");
return -1;
}
if (S->length >= S->listsize)
{
S->elem = (int*)malloc(sizeof(int) * (100 + 10));
S->listsize += 10;
}
if (e > S->elem[S->length-1])
{
S->elem[S->length] = e;
S->length++;
S->listsize--;
return 0;
}
if (S->elem[0] > e)
{
for (int k = S->length; k >= 0; k--)
{
S->elem[k] = S->elem[k - 1];
}
S->elem[0] = e;
S->length++;
S->listsize--;
return 0;
}
while (r <= len && len <= l)
{
if (S->elem[len - 1] <= e && e <= S->elem[len])
{
for (int k = S->length; k >= len; k--)
{
S->elem[k] = S->elem[k - 1];
}
S->elem[len] = e;
S->length++;
S->listsize--;
break;
}
else if (S->elem[len] > e)
{
len = len / 2;
}
else
{
len = (len + l) / 2;
}
}
}
12.设A=(a1,....am)和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大小的算法
这题大水题,用指针走到不相等的地方比较就好了,算法如下:
int CmpSqList(SqList A, SqList B)
{
int a = 0, b = 0;
while (A.elem[a] != NULL && B.elem[b] != NULL)
{
if (A.elem[a] < B.elem[b])
{
printf("\nA<B");
return -1;
}
if (A.elem[a] > B.elem[b])
{
printf("\nA>B");
return 1;
}
a++;
b++;
}
if (A.elem[a] == NULL && B.elem[b] == NULL)
{
printf("\nA=B");
return 0;
}
if (A.elem[a])
{
printf("\nA>B");
return 1;
}
if (B.elem[b])
{
printf("\nA<B");
return -1;
}
}
13.试写一算法在带表头结点的单链表结构上实现线性表操作LOCATE(L,X)
这题我的理解是在L表中找出X
LinkList LocateList(LinkList L, int x)
{
LinkList P;
P = L->next;
while (P != NULL && P->data != x)
{
P = P->next;
}
if (P == NULL)
{
printf("未找到该元素");
exit(0);
}
else
{
return P;
}
}
14.试写一算法在带表头结点的单链表结构上实现线性表操作LENGTH(L)
int LengthList(LinkList L)
{
LinkList P;
int count = 0;
P = L->next;
while (P != NULL && P->data != x)
{
P = P->next;
count++;
}
return count;
}
15.已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n,试写一算法将这两个链表链接到一起(其一链表的首元节点连接到另一链表的尾结点后),假设指针hc指向链接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算,请分析你的算法的时间复杂度
int ConnectList(LinkList A, LinkList B)
{
LinkList ha, hb, hc;
ha = A;
hb = B;
if (ha->next == NULL && hb->next == NULL)
{
return 0;
}
while (ha->next != NULL)
{
ha = ha->next;
}
ha->next = hb->next;
free(hb);
hc = ha;
}
时间复杂度与其一链表的长度有关,需要找到链表的表尾才能进行链表,在上述算法中,时间复杂度为O(m)
16.已知指针la和lb分别指向两个无头结点单链表中的首元结点,下列算法是从表la中删除自第i个元素起共len个元素后,将它们插入到表lb中第j个元素之前,试问此算法是否正确,若有错,请改正
Status DeleteAndInsertSub(LinkList la, LinkList 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;
}
讲真,看到这算法后,我脑海里边出现的就全是错误
入口条件,首先要规划边界,删除的总数必须小于链表的长度,而因为是不带头节点的,所有首元结点我喜欢称为第一结点,游标都从1,开始,则i,j,len,都不能小于1,主要思路是分割其一结点后,将分割出来的链表链接到另一链表的指定位置,需要保存:
- 分割链表的头,尾
- 待分割的前驱,后置
- 待插入的前驱,后置
还需要注意特殊值:插入到表头和表尾
完整算法如下:
int DeleteAAndInsertSub(LinkList *la, LinkList *lb, int i, int j, int len)
{
int k;
LinkList p, s, p1, s1, a, b;
if (i <= 0 || j <= 0 || len <= 0 || la[i + len] == NULL)
{
exit(0);
}
k = 1;
p = *la;
while (k < i)
{
p = p->next;
k++;
}
p1 = p;
a = p->next;//保存删除的头
k = 1;
while (k <= len)
{
p = p->next;
k++;
}
s = p;//保存删除的尾
p1->next = p->next;
b = *lb;
if (j == 1)
{
s->next = b;
*lb = a;
}
else
{
k = 1;
while (k < j - 1)//从1开始,j-1是找到它的前驱
{
b = b->next;
k++;
}
s1 = b->next;
b->next = a;
s->next = s1;
}
}
17.试写一算法,在无头结点的动态单链表上实现线性表操作INSERT(L,i,b),并和在带头结点的动态单链表上实现相同操作的算法进行比较
不带头结点:
需要考虑的是,插入的位置是头还是尾,不带头结点我喜欢从1开始,那么需要找到它的前驱和后置,然后前驱链接插入结点,插入结点链接后置,判决条件是不能小于一,也不能大于表长+1
完整代码:
int InsertList(LinkList *L, int i, int b)
{
int count = 1;
LinkList s = *L, p = s->next, node;
if (i <= 0)
{
printf("插入位置不合法");
exit(0);
}
if (i == 1)
{
node = (LinkList)malloc(sizeof(LNode));
node->data = b;
node->next = s;
*L = node;
return 0;
}
while (s != NULL && count < i - 1)
{
s = p;
p = p->next;
count++;
}
if (s == NULL)
{
printf("插入位置不合法");
}
else
{
node = (LinkList)malloc(sizeof(LNode));
node->data = b;
node->next = p;
s->next = node;
}
}
带头结点:
从0开始计数,不需要改变头指针位置,头指针后链接首元结点。
判决条件,不能小于1,也不能大于表长+1。完整代码:
int InsertList(LinkList *L, int i, int b)
{
int count = 0;
LinkList s = *L, p = s->next, node;
if (i <= 0)
{
printf("插入位置不合法");
exit(0);
}
if (i == 1)
{
node = (LinkList)malloc(sizeof(LNode));
node->data = b;
s->next = node;
node->next = p;
return 0;
}
while (s != NULL && count < i - 1)
{
s = p;
p = p->next;
count++;
}
if (s == NULL)
{
printf("插入位置不合法");
exit(0);
}
else
{
node = (LinkList)malloc(sizeof(LNode));
node->data = b;
node->next = p;
s->next = node;
}
}
18.同上要求,完成DELETE算法
int LenthList(LinkList L)
{
int count = 1;
LinkList p = L;
if (L == NULL)
{
return 0;
}
while (p->next != NULL)
{
p = p->next;
count++;
}
return count;
}
int DeleteList(LinkList* L, int i)
//删除L表中第i个位置
{
if (0 >= i || i > LenthList(*L))
{
printf("删除位置不合法\n");
return 0;
}
LinkList p,s;
p = *L;
s = (*L)->next;
int count = 1;
if (i == 1)
{
*L = s;
free(p);
return 0;
}
while (count < i - 1)
{
p = s;
s = s->next;
count++;
}
p->next = s->next;
free(s);
}
同上所述,不带头结点的元素从1开始,当删除位置到表头的时候,需要改变头指针指向
带头结点:
int DeleteList(LinkList* L, int i)
//删除L表中第i个位置
{
if (0 >= i || i > LenthList(*L))
{
printf("删除位置不合法\n");
return 0;
}
LinkList p,s;
p = *L;
s = (*L)->next;
int count = 0;
if (i == 1)
{
p->next = s->next;
free(s);
return 0;
}
while (count < i - 1)
{
p = s;
s = s->next;
count++;
}
p->next = s->next;
free(s);
}
相差不大,不需要改变头指针位置,单链表很好操作,都是基础题。我们看下一题:
总得来说:带头结点的首元结点位于头结点后,在指定位置插入和删除的时候位于第一位,而带头结点的首元节点就是头指针所指向的结点,位于第二位!
19.已知线性表中的元素以值递增有序排列,并以单链表做存储结构,试写一高效算法,删除表中所有值大于mink且小于maxk的元素(若表中存在满足条件的元素)同时释放被删除的结点空间,并分析你的算法的时间复杂度(注意:mink和maxk是给定的两个参变量,它们的值可以和表中的元素相同,也可以不同)
这道题需要注意两个点,一个是有序,一个是单链表,既然是链式存储,而且是动态带头结点的单链表,就不能二分查找,思路就是从首元节点开始,一个指针指向它的前驱,不断后移,知道满足mink的条件的数,利用一个指针指向这个数,继续后移,后移后释放刚刚满足条件的数,最后达到满足maxk元素的时候,将其链接起来,代码如下所示:
void MinkMaxkList(LinkList L, int i, int j)
{
LinkList p, s, p1, P;
s = L;
p = L->next;
while (p != NULL)
{
if (p->data > i && p->data < j)
{
p1 = p;
p = p->next;
free(p1);
continue;
}
if (p->data >= j)
{
s->next = p;
break;
}
s = p;
p = p->next;
}
if (p == NULL)
{
s->next = NULL;
}
}
20.同19题的条件,写一高效算法,删除表中所有值相同的多余元素(使得操作后的线性表所有值均不相同),同时释放被删的结点空间,并分析你的算法的时间复杂度
这道题我首先想的是,拿链表中的每一个数去往后边遍历,但是突然想到,这是一个有序链表,在蓝哥的指导下,用双指针也可以实现。
通用链表算法:
void DeleteEqualList(LinkList L)
//利用三个指针,一个快指针s,一个跟着快指针指向前驱p1
//一个慢指针p,不断去遍历
//时间复杂度与链表的元素有关,平均复杂度是O((2/n)n)
{
LinkList p, s, p1;
p = L->next;
while (p != NULL)
{
p1 = p;
s = p->next;
while (s != NULL)
{
if (p->data == s->data)
{
p1->next = s->next;
free(s);
s = p1->next;
continue;
}
p1 = s;
s = s->next;
}
p = p->next;
}
}
有序链表借鉴大佬的思想,算法如下:
void DeleteEqualList(LinkList L)
{
LinkList p, s, p1;
p = L->next;
s = p->next;
while (s)
{
if (p->data == s->data)
{
p1 = s;
s = s->next;
free(p1);
p->next = s;
continue;
}
p = s;
s = s->next;
}
}
时间复杂度仅仅为O(n),因为只需要快指针s遍历一次链表