[C++知识库]【严蔚敏数据结构题集】C/C++编程线性表练习题（一）

都是自己练习的，难免有不对的地方，有错误欢迎纠正

线性表练习题

习题2.11-2.20

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAXSIZE  100

typedef struct {
	int *elem;
	int length;
}SqList;

void PrintList(SqList *L);
void InitList(SqList *L);
int Insert(SqList *L, int x);

void main()
{
	SqList  va;
	InitList(&va);
	PrintList(&va);
	int x;
	printf("Enter a number:");
	scanf("%d", &x);
	Insert(&va, x);
	PrintList(&va); 
	return;
}
int Insert(SqList *L,int x)
{
	if (L->length == MAXSIZE)//顺序表满了，不进行操作
		return -1;
	int i = 0;
	while (x > L->elem[i] && i < L->length)//找出插入位置i
	{
		++i;
	} 
	for (int j = L->length; j > i; --j)//将第length-1到第i个元素都向后移动一个位置
	{
		L->elem[j] = L->elem[j - 1];
	}
	L->elem[i] = x;
	L->length++;
	return 0;
}
void InitList(SqList *L)
{
	L->elem = (int)malloc(MAXSIZE);
	if (!L->elem)
		exit(1);
	L->length = 0;
	//初始化一个20个元素的顺序表，可随意发挥初始化
	for (int i = 0; i < 20; i++)
	{
		L->elem[i] = i * 5;
		L->length++;
	}
}
void PrintList(SqList *L)//打印顺序表
{
	for (int i = 0; i < L->length; ++i)
	{
		printf("%d  ", L->elem[i]);
	}
	printf("\n");
}

运行结果：


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大小的算法（请注意：在算法中不要破坏原表A和B，并且，也不一定先求得A’和B’才进行比较）。

#include <stdio.h>
#define MAXSIZE  100
typedef struct {
	char *elem;
	int length;
}SqList;
void InitList(SqList *L);//初始化顺序表
void PrintList(SqList  L);//打印顺序表
void compareList(SqList A, SqList B);//比较A和B
int main()
{
	SqList A, B;
	printf("Enter List A: ");
	InitList(&A);
	PrintList(A);
	printf("Enter List B: ");
	InitList(&B);
	PrintList(B);
	compareList(A, B);
	free(A);
	free(B);
	return;
}
void compareList(SqList A, SqList B)
{
	if (A.length == 0 && B.length == 0)
		printf("A==B");
	else if(A.length == 0){
		printf("A<B");
	}
	else if(B.length==0){
		printf("A>B");
	}
	else {
		int i = 0;
		while (A.elem[i] == B.elem[i])
		{
			++i;
		}
		if (A.elem[i] > B.elem) {
			printf("A>B");
		}
		else
		{
			printf("A<B");
		}
	}
}
void InitList(SqList *L)
{
	L->elem = (char*)malloc(MAXSIZE);
	if (!L->elem)
		exit(1);
	int length=0;
	char inputChar[MAXSIZE];
	char character = ' ';
	while (character != '\n')
	{
		character = getchar();
		if (character != '\n'){
			inputChar[length] = character;
			++length;
		}
		else
			break;
	}	
	L->length = length;
	for (int i = 0; i < length; ++i)
	{
		L->elem[i] = inputChar[i];
	}
}
void PrintList(SqList  L)
{
	for (int i = 0; i < L.length; ++i)
	{
		printf("%c  ", L.elem[i]);
	}
	printf("\n");
}

运行结果：
A、B都为空时：

A不空，B空：

A空，B不空

AB都不空：

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

#include <stdio.h>
typedef struct LNode {
	char data;						//数据域，这里设为字符型
	struct LNode *next;    //指针域
}LNode, *LinkList;           //LinkLis为指向结构体LNode的指针类型
void PrintList(LNode * L);//打印链表
void  InitList(LNode *L);//尾插法构建单链表
LNode *LocateData(LNode *L, char x);//查值的地址操作

void main()
{
	LinkList L = (LNode *)malloc(sizeof(LNode));//头节点
	if (!L)
		exit(1);
	L->next = NULL;
	InitList(L);//初始化
	PrintList(L);//打印
	printf("Enter the elem that you need：");
	char x=getchar();
	LNode *node=LocateData(L, x);//查询地址
	if (node)
		printf("%c is stored at address of  %u\n", x, node);
	else
		printf("there is no %c on the list\n",x);
	return;
}
LNode *LocateData(LNode* L, char x)
{
	LinkList p=L->next;
	while (p)
	{
		if (p->data == x)//找到了
			break;
		else
			p = p->next;
	}
	return p;//返回地址
}
void InitList(LNode *L)//尾插法初始化单链表
{
	LinkList q = L;//q指向p前面一个节点
	printf("Enter the list's value\n");
	char ch = ' ';
	int len = 0;
	while (ch!='\n')
	{
		ch = getchar();
		if (ch != '\n')
		{
			LinkList p = (LNode *)malloc(sizeof(LNode));
            if (!p)
     		exit(1);
			p->data = ch;
			p->next = NULL;
			q->next = p;
			q = q->next;
			len++;
		}
		else
			break;
	}
}
void PrintList(LNode *L )
{
	LinkList p = L->next;
	while (p)
	{
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}

运行结果：

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

#include <stdio.h>
typedef struct LNode {
	char data;						//数据域，这里设为字符型
	struct LNode *next;    //指针域
}LNode, *LinkList;           //LinkLis为指向结构体LNode的指针类型
void PrintList(LNode * L);//打印链表
void  InitList(LNode *L);//尾插法构建单链表
int ListLength(LNode *L);//返回元素的个数

void main()
{
	LinkList L = (LNode *)malloc(sizeof(LNode));//头节点
	if (!L)
		exit(1);
	L->next = NULL;
	InitList(L);//初始化
	//PrintList(L);//打印
	printf("The list have %d nodes(include the head node) ",ListLength(L));
	return;
}
int ListLength(LNode *L)
{
	int len = 0;
	LinkList p = L;
	while (p)
	{
		++len;
		p = p->next;
	}
	return len;
}
void InitList(LNode *L)//尾插法初始化单链表
{
	LinkList q = L;//q指向p前面一个节点
	printf("Enter the list's value\n");
	char ch = ' ';
	int len = 0;
	while (ch != '\n')
	{
		ch = getchar();
		if (ch != '\n')
		{
			LinkList p = (LNode *)malloc(sizeof(LNode));
			if (!p)
				exit(1);
			p->data = ch;
			p->next = NULL;
			q->next = p;
			q = q->next;
			len++;
		}
		else
			break;
	}
}
void PrintList(LNode *L)
{
	LinkList p = L->next;
	while (p)
	{
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}

运行结果：

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

#include <stdio.h>
typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode,*LinkList;
void junction(LNode *ha, LNode *hb);//连接两个单链表
int InitList(LNode *L);//初始化链表
void PrintList(LNode* L);
void main()
{
	int m = 0,n=0;
	LinkList ha = (LNode*)malloc(sizeof(LNode));
	if (!ha)
		return;
	LinkList hb = (LNode*)malloc(sizeof(LNode));
	if (!hb)
		return;
	ha->next = NULL;
	hb->next = NULL;
	m=InitList(ha);
	n=InitList(hb);
	printf("ha list:");
	PrintList(ha);
	printf("hb list:");
	PrintList(hb);
	junction(ha, hb);
	LinkList hc = ha;
	printf("the list after junction:");
	PrintList(hc);
	return;
}
void junction(LNode *ha, LNode *hb)
{
	LinkList p = ha;
	while (p->next)
	{
		p = p->next;
	}
	p->next = hb->next;
}
int InitList(LNode *L)
{
	int num,len=0;
	LinkList q = L;
	printf("Enter the num of the list:\n");
	scanf("%d",&len);
	printf("Enter the value:\n");
	for (int i = 0; i < len; ++i)
	{
		scanf("%d", &num);
		LinkList p = (LNode*)malloc(sizeof(LNode));
		if (!p)
			exit(1);
		p->data = num;
		p->next = NULL;
		q->next = p;
		q = q->next;
	}
	return len;
}
void PrintList(LNode *L)
{
	LinkList p = L->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\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;
}//DeleteAndInsertSub

更改后的算法

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,prev=NULL;
		while(p&&k<i)//找到la表中第i个结点p
		{prev=p;p=p->next;k++;}
		if(!p)return INFEASIBLE;
		q=p;k=1;
		while(q&&k<len)//找到la表中第i+len-1个结点
		{q=q->next;k++}
		if(!q)return INFEASIBLE;
		if(!prev)la=q->next;//i=1的情况
		else prev->next=q->next;//完成删除
		//将从la中删除的结点插入到lb中
		if(j==1){q->next=lb;lb=p}
		else{
			s=lb;k=1;
			while(s&&k<j-1)
			{s=s->next;k++;}//查找lb表中的第j-1个元素
			if(!s)return INFEASIBLE;
			q->next=s->next;
			s->next=p;//完成插入
			return OK;
		}
}//DeleteAndInsertSub

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

（1）无头结点：（比起有头结点的单链表要注意首元结点的插入）

#include <stdio.h>
typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode, *LinkList;
LNode * InitList();
void PrintList(LNode *L);//打印列表
void InsertList(LNode **L, int i, int b);//在第i个位置插入列表

void main()
{
	LinkList L = InitList();
	printf("before:");
	PrintList(L);
	int i,b;
	printf("Enter the location:");//输入待插入元素的位置
	scanf("%d", &i);
	printf("Enter the number you want to insert into the list:");//输入待插入元素的值
	scanf("%d", &b);
	InsertList(&L, i, b);
	printf("after:");
	PrintList(L);
	return;
}
void InsertList(LNode **L, int i, int b)//插入的位置可能是首元结点所以传L的值必须传地址，
{																		//否则会出现无法插入元素到首元结点的现象
	LinkList p = *L;
	LinkList q=*L;
	if (i == 1)//若在插入的位置是首元位置
	{
		LinkList newNode = (LNode *)malloc(sizeof(LNode));//生成新节点
		if (!newNode)
			exit(1);
		newNode->data = b;
		newNode->next =*L;
		*L = newNode;
	}
	else//若在插入的位置不是首元位置
	{
		int j = 1;//从第一个位置开始找
		while (p && (j < i - 1))//找到第i-1的位置，p指向i-1
		{
			p = p->next;
			++j;
		}
		if (!p || j > i)//插入的位置大于列表的长度
		{
			exit(1);
		}
		LinkList newNode = (LNode *)malloc(sizeof(LNode));//生成新节点
		if (!newNode)
			exit(1);
		newNode->data = b;
		newNode->next = p->next;
		p->next = newNode;
	}
}
LNode * InitList()
{
	int num, len = 0;
	LinkList  L=NULL;
	LinkList q = NULL;//q用来保存当前结点的前驱
	printf("Enter the length of the list:\n");
	scanf("%d", &len);
	printf("Enter the value:\n");
	for (int i = 0; i < len; ++i)
	{
		scanf("%d", &num);
		LinkList p = (LNode*)malloc(sizeof(LNode));
		if (!p)
			exit(1);
		p->data = num;
		p->next = NULL;
		if (i == 0) {//i=0时，p是首元结点
			L = p;
			q = p;
		}
		if (q)
		{
			q->next = p;
			q = p;
		}
	}
	return L;
}
void PrintList(LNode *L)
{
	LinkList p = L;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

运行结果：

（2）有头结点单链表插入:

#include <stdio.h>
typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode, *LinkList;
LNode * InitList();
void PrintList(LNode *L);//打印列表
void InsertList(LNode *L, int i, int b);//在第i个位置插入列表
//包含头结点的单链表插入
void main()
{
	LinkList L = InitList();
	printf("before:");
	PrintList(L);
	int i, b;
	printf("Enter the location:");//输入待插入元素的位置
	scanf("%d", &i);
	printf("Enter the number you want to insert into the list:");//输入待插入元素的值
	scanf("%d", &b);
	InsertList(L, i, b);
	printf("after:");
	PrintList(L);
	return;
}
void InsertList(LNode *L, int i, int b)
{
	LinkList p = L;
	int j = 0;
	while (p && (j < i - 1))//找到第i-1的位置，p指向i-1
	{
		p = p->next;
		++j;
	}
	if (!p || j > i - 1)//插入的位置大于列表的长度
	{
		exit(1);
	}
	LinkList newNode = (LNode *)malloc(sizeof(LNode));//生成新节点
	if (!newNode)
		exit(1);
	newNode->data = b;
	newNode->next = p->next;
	p->next = newNode;
}
LNode * InitList()
{
	int num, len = 0;
	LinkList  L = (LNode*)malloc(sizeof(LNode));
	if (!L)
		exit(1);
	LinkList q = L;//q用来保存当前结点的前驱
	printf("Enter the length of the list:\n");
	scanf("%d", &len);
	printf("Enter the value:\n");
	for (int i = 0; i < len; ++i)
	{
		scanf("%d", &num);
		LinkList p = (LNode*)malloc(sizeof(LNode));
		if (!p)
			exit(1);
		p->data = num;
		p->next = NULL;
		q->next = p;
		q = q->next;
	}
	return L;
}
void PrintList(LNode *L)
{
	LinkList p = L->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

运行结果：

2.18同2.17要求。试写一算法，实现线性表操作DELETE(L,i)；
（1）不包含头结点单链表的删除指定位置元素

#include <stdio.h>
//不含头结点的单链表删除
typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode, *LinkList;
LNode * InitList();//初始化链表
void PrintList(LNode *L);//打印链表
void DeleteList(LNode **L, int i);// 删除第i个元素
void main()
{
	LinkList L = InitList();
	printf("before:");
	PrintList(L);
	int i;
	printf("Enter the location:");//输入待删除元素的位置i
	scanf("%d", &i);
	DeleteList(&L, i);
	printf("after:");
	PrintList(L);
	return;
}
void DeleteList(LNode **L, int i)
{
	LinkList p = *L;
	LinkList q = p;
	int temp;//记下删除元素的值
	if (i == 1)//如果删除的是首元结点
	{
		temp = p->data;
		p = p->next;
		free(*L);
		(*L) = p;
	}
	else//要删除的不是首元结点
	{
		int j = 1;
		while (p&&j < i-1 )//找到要删除的前一个结点p
		{
			p = p->next;
			++j;
		}
		if (!p || j > i)
		{
			printf("DELETE ERROR\n");
			return;
		}
		q = p->next;//q就是要删除的结点
		temp = q->data;
		p->next = p->next->next;
		free(q);
	}
	printf("成功删除第%d个位置元素：%d\n",i,temp);
}
LNode * InitList()
{
	int num, len = 0;
	LinkList  L=NULL;
	LinkList q = NULL;//q用来保存当前结点的前驱
	printf("Enter the length of the list:\n");
	scanf("%d", &len);
	printf("Enter the value:\n");
	for (int i = 0; i < len; ++i)
	{
		scanf("%d", &num);
		LinkList p = (LNode*)malloc(sizeof(LNode));
		if (!p)
			exit(1);
		p->data = num;
		p->next = NULL;
		if (i == 0) {//i=0时，p是首元结点
			L = p;
			q = p;
		}
		if (q)
		{
			q->next = p;
			q = p;
		}
	}
	return L;
}
void PrintList(LNode *L)
{
	LinkList p = L;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

运行结果：

（2）包含头结点单链表删除指定位置元素

#include <stdio.h>
//含头结点的单链表删除指定位置的元素
typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode, *LinkList;
LNode * InitList();
void PrintList(LNode *L);//打印列表
void DeleteList(LNode *L, int i);//删除i位置的元素
void main()
{
	LinkList L = InitList();
	printf("before:");
	PrintList(L);
	int i, b;
	printf("Enter the location:");//输入待删除元素的位置
	scanf("%d", &i);
	DeleteList(L, i);
	printf("after:");
	PrintList(L);
	return;
}
void DeleteList(LNode *L, int i)
{
	LinkList q,p = L;
	int temp;//保存被删掉的元素值
	int j = 0;
	while (p && (j < i - 1))//找到第i-1的位置，p指向i-1
	{
		p = p->next;
		++j;
	}
	if (!p || j > i - 1)//i超出指定位置
	{
		printf("DELETE ERROR\n");
		return;
	}
	q = p->next;
	temp = q->data;
	p->next = p->next->next;
	free(q);
	printf("成功删除第%d个元素：%d\n", i, temp);

}
LNode * InitList()
{
	int num, len = 0;
	LinkList  L = (LNode*)malloc(sizeof(LNode));
	if (!L)
		exit(1);
	LinkList q = L;//q用来保存当前结点的前驱
	printf("Enter the length of the list:\n");
	scanf("%d", &len);
	printf("Enter the value:\n");
	for (int i = 0; i < len; ++i)
	{
		scanf("%d", &num);
		LinkList p = (LNode*)malloc(sizeof(LNode));
		if (!p)
			exit(1);
		p->data = num;
		p->next = NULL;
		q->next = p;
		q = q->next;
	}
	return L;
}
void PrintList(LNode *L)
{
	LinkList p = L->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

运行结果：

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

#include <stdio.h>
typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode, *LinkList;
LNode * InitList();
void PrintList(LNode *L);//打印列表
void DeleteList(LNode *L,int  mink, int maxk);
void main()
{
	LinkList L = InitList();
	printf("before:");
	PrintList(L);
	int mink,maxk;
	printf("Enter the range:\n");//输入待删除元素的大小范围
	scanf("%d %d", &mink,&maxk);
	if (mink > maxk) {//保证mink<=maxk
		int temp = maxk;
		maxk = mink;
		mink = temp;
	}
	DeleteList(L, mink,maxk);
	printf("after:");
	PrintList(L);
	return;
}
void DeleteList(LNode *L,int  mink, int maxk)
{
	LinkList p1=NULL,p2=NULL;
	LinkList p=L;
	while (p)//找到第一个大于mink结点的前驱p1
	{
		if ((p->next)->data> mink)
		{
			p1 = p;
			break;
		}
		p = p->next;
	}
	p = p1;
	while (p)//找到最后一个小于maxk的结点p2
	{
		if (p->next&&(p->next->data )< maxk)//若当前元素比maxk小，就找下一个
		{
			p = p->next; 
		}
		else
		{
			p2 = p;
			break;
		}
	}

	if (p1&&p2)
	{
		p = p1->next;
		p1->next = p2->next;//从链表中改变结点后继
		
		LinkList temp=NULL;
		while (p)//释放被删除的结点
		{
			temp = p->next;
			free(p);
			p = temp;
			if (p == p2)
				break;
		}
	}
}
LNode * InitList()
{
	int num, len = 0;
	LinkList  L = (LNode*)malloc(sizeof(LNode));
	if (!L)
		exit(1);
	LinkList q = L;//q用来保存当前结点的前驱
	printf("Enter the length of the list:\n");
	scanf("%d", &len);
	if (len == 0)
		return;
	printf("Enter the value:\n");
	for (int i = 0; i < len; ++i)
	{
		scanf("%d", &num);
		LinkList p = (LNode*)malloc(sizeof(LNode));
		if (!p)
			exit(1);
		p->data = num;
		p->next = NULL;
		q->next = p;
		q = q->next;
	}
	return L;
}
void PrintList(LNode *L)//含头结点的单链表输出
{
	LinkList p = L->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

运行结果：

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

#include <stdio.h>
typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode, *LinkList;
LNode * InitList();//初始化链表
void PrintList(LNode *L);//打印链表
void Removeduplication(LNode *L);//去除链表的重复元素
void main()
{
	LinkList L = InitList();
	printf("before:");
	PrintList(L);
	Removeduplication(L);//去掉重复元素
	printf("after:");
	PrintList(L);
	return;
}
void Removeduplication(LNode *L)
{
	LinkList p = L->next;
	LinkList pre = L;
	LinkList temp;
	while (p)
	{
		while (p&&pre->data == p->data)//有相同元素时，向后找到与pre不同的元素p
		{
			temp = p;
			p = p->next;
			free(temp);//释放重复元素
		}
			pre->next = p;
			pre = p;
			if (p)
			{
				p = p->next;
			}
	}
}
LNode * InitList()
{
	int num, len = 0;
	LinkList  L = (LNode*)malloc(sizeof(LNode));
	if (!L)
		exit(1);
	LinkList q = L;//q用来保存当前结点的前驱
	printf("Enter the length of the list:\n");
	scanf("%d", &len);
	if (len == 0)
		return;
	printf("Enter the value:\n");
	for (int i = 0; i < len; ++i)
	{
		scanf("%d", &num);
		LinkList p = (LNode*)malloc(sizeof(LNode));
		if (!p)
			exit(1);
		p->data = num;
		p->next = NULL;
		q->next = p;
		q = q->next;
	}
	return L;
}
void PrintList(LNode *L)//含头结点的单链表输出
{
	LinkList p = L->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

运行结果：