数据结构题集-第二章-线性表-单链表的插入

news/2024/11/5 14:34:05 标签: 数据结构, 算法

说明

  • 本文参照严蔚敏《数据结构(C语言版)题集》一书中包含的问答题和算法设计题目，提供解答和算法的解决方案。
  • 请读者在自己已经解决了某个题目或进行了充分的思考之后，再参考本解答，以保证复习效果。
  • 由于作者水平所限，本解答中一定存在不少这样或者那样的错误和不足，希望读者们在阅读中多动脑、勤思考，争取发现和纠正这些错误，写出更好的算法来。

2.17 试写一算法

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

解：
注意涉及空表和首元结点的操作。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

#define MAX_TEST_LENGTH 20
#define MAX_TEST_ELEM 1000
typedef int ElemType;

typedef struct SLNode{ // 结点类型
	ElemType data;
	struct LNode *next;
} LNode, *Link, *LinkedList;

Status MakeNode(Link *pp,ElemType e){
	// 分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR
	*pp=(Link)malloc(sizeof(LNode));
	if(!*pp) return ERROR;
	(*pp)->data=e;
	(*pp)->next=NULL;
	return OK;
}

void FreeNode(Link p){
	// 释放p所指结点
	if(NULL!=p){
		free(p);
	}
}

Status DestroyClearedList(LinkedList *pL){
	// 将线性表L重置为空表，并释放原链表的结点空间
	Link p;
	if(NULL==pL) return ERROR;
	p=*pL;
	while(p){
		*pL=p->next;
		//printf("free [%lld]=%d\n",(long long)p,p->data);
		FreeNode(p);
		p=*pL;
	}
	*pL=NULL;
	return OK;
}

void print_list(LinkedList L){
	// 显示链表的内容
	int c=0;
	while(L){
		printf("->[%d].%d",c++,L->data);
		L=L->next;
	}
	printf("\n");
}

int ListLen(LinkedList L){
	// 计算链表长
	int c=0;
	while(L){
		++c;
		L=L->next;
	}
	return c;
}

Status InsFirst(LinkedList *pL,Link s){
	// 已知线性链表的头指针，将s所指结点链接成新的首元
	if(NULL==pL||NULL==s) return ERROR;
	s->next=*pL;
	*pL=s;
	return OK;
}

Status INSERT(LinkedList *pL,int i,Link b){
	// 在无头结点链表L的第i个元素之前插入元素b
	Link p;
	// 若要初始化链表，用其他函数来完成
	if(NULL==pL||NULL==b||i<1) return INFEASIBLE;
	// 保证i值大于等于1才处理，并且链表长度在i>1时如果少于i-1也不可插入
	if(i==1){
		b->next=*pL;
		*pL=b; //插入到链表头部
	}else{
		p=*pL;
		i--;
		while(p&&--i) p=p->next;
		if(p){
			b->next=p->next;
			p->next=b; //插入到第i个位置
		}else return ERROR; //当链表元素个数少于i-1
	}
	return OK;
}

Status rand_test_list_insert(LinkedList *pL){
	// 在测试范围内，随机初始化链表
	int i,len,c;
	Status result;
	Link p;
	time_t t;
	
	srand((unsigned)time(&t)); // 初始化随机数发生器
	
	c=rand()%MAX_TEST_LENGTH;
	while(c--){
		p=NULL;
		if(ERROR==MakeNode(&p,rand()%MAX_TEST_ELEM)) return ERROR;
		if(ERROR==InsFirst(pL,p)) return ERROR;
	}
	print_list(*pL);
	
	len=ListLen(*pL);
	if(len>0){
		p=NULL;
		if(ERROR==MakeNode(&p,rand()%MAX_TEST_ELEM)) return ERROR;
		printf("Insert rand %d before i(i>=1):",p->data);
		scanf("%d",&i);
		result=INSERT(pL,i,p);
		if(result==OK){
			printf("\nInsert success, after insert:\n");
			print_list(*pL);
		}else if(result==ERROR){
			printf("\nERROR (pos %d) greater than (1 + %d(len of list))\n",i,len);
			return result;
		}else{
			printf("\nDo not support...\n");
			return result;
		}
	}
	return OK;
}

int main(){
	LinkedList La;
	La=NULL;

	if(OK==rand_test_list_insert(&La))
		printf("Any more?\n");
	
	if(OK==DestroyClearedList(&La)) printf("Free La success\n");

	return 0;
}

如果在带头结点的动态单链表上实现相同操作，
参照：数据结构题集-第二章-线性表-连接链表并安全释放，
实现同样功能的函数，基本类似，就不需要传结点指针的地址了，需要有头链表结构变量的地址，
插入后至少改变表长，除了对首元的指向，对头结点没有影响，且插入表尾时，需要改动尾指针。
在参照的基础上，加上这个算法并测试：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

#define MAX_TEST_LENGTH 20
#define MAX_TEST_ELEM 1000
typedef int ElemType;

typedef struct SLNode{ // 结点类型
	ElemType data;
	struct LNode *next;
} LNode, *Link;

typedef struct{ // 链表类型
	Link head,tail; // 分别指向线性链表中的头结点和最后一个结点
	int len; // 指示线性链表中数据元素的个数
} LinkList;

Status MakeNode(Link *pp,ElemType e){
	// 分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR
	*pp=(Link)malloc(sizeof(LNode));
	if(!*pp) return ERROR;
	(*pp)->data=e;
	(*pp)->next=NULL;
	return OK;
}

void FreeNode(Link p){
	// 释放p所指结点
	if(NULL!=p){
		//printf("\nvalue of adddress:%lld\n",(long long)p);
		free(p);
	}
}

Status InitList(LinkList *pL){
	// 构造一个空的线性链表L
	Link p;
	if(ERROR==MakeNode(&p,0)) return ERROR;
	(*pL).head=p;
	(*pL).tail=NULL;
	(*pL).len=0;
	return OK;
}

Status ClearList(LinkList *pL){
	// 将线性表L重置为空表，并释放原链表的结点空间
	Link p;
	if(NULL==pL) return ERROR;
	if(NULL!=(*pL).head) p=((*pL).head)->next;
	while(p){
		((*pL).head)->next=p->next;
		printf("free [%lld]=%d\n",(long long)p,p->data);
		FreeNode(p);
		p=((*pL).head)->next;
	}
	(*pL).tail=NULL;
	(*pL).len=0;
	return OK;
}

Status DestroyList(LinkList *pL){
	// 销毁线性链表L
	if(ERROR==ClearList(pL)) return ERROR;
	if(NULL!=(*pL).head) FreeNode((*pL).head);
	(*pL).head=NULL;
	return OK;
}

void print_list(LinkList L){
	// 显示链表的内容
	int c=0;
	Link p=(L.head)->next;
	while(p){
		printf("->[%d].%d",++c,p->data);
		p=p->next;
	}
	printf("\n%d elements\n",L.len);
}

Status InsFirst(LinkList *pL,Link s){
	// 已知线性链表的头结点，将s所指结点插入到第一个结点之前
	// 线性链表的尾指针没有变化，线性链表的元素个数加1
	Link p;
	if(NULL==pL||NULL==s) return ERROR;
	p=(*pL).head;
	s->next=p->next;
	if(NULL==p->next) (*pL).tail=s; // 插入前链表为空时，记录表尾
	p->next=s;
	(*pL).len+=1;
	return OK;
}

Status InsLast(LinkList *pL,Link s){
	// 已知线性链表的尾结点，将s所指结点插入到最后结点之后
	// 尾指针发生变化，若非空，线性链表的头结点指针域没有变化，线性链表的元素个数加1
	// 注意这里提供s的时候，需要先从较短链表中复制一份再传进来
	if(NULL==pL||NULL==s) return ERROR;
	if(NULL==pL->head->next){
		pL->head->next=s;
	}else{
		pL->tail->next=s;
	}
	pL->tail=s;
	pL->len+=1;
	return OK;
}//InsLast

Status INSERT(LinkList *pL,int i,Link b){
	// 在有头结点的链表L的第i个元素之前插入元素b
	Link p;
	// 若要初始化链表，用其他函数来完成
	if(NULL==pL||NULL==b||i<1) return INFEASIBLE;
	// 保证i值大于等于1才处理，并且链表长度在i>1时如果少于i-1也不可插入
	// 由于有头结点，不必单独考虑当i==1时插入到首元前的情况
	p=pL->head;
	while(p&&--i) p=p->next;
	if(p){
		b->next=p->next;
		p->next=b; //插入到第i个位置
		if(!i) pL->tail=b;
		(pL->len)++;
	}else return ERROR; //当链表元素个数少于i-1
	return OK;
}

Status rand_test_insert(){
	LinkList La;
	Status result;
	// 在测试范围内，随机初始化链表
	int i,c;
	Link p;
	time_t t;
	
	if(ERROR==InitList(&La)) return ERROR;
	srand((unsigned)time(&t)); // 初始化随机数发生器
	
	c=rand()%MAX_TEST_LENGTH;
	while(c--){
		p=NULL;
		if(ERROR==MakeNode(&p,rand()%MAX_TEST_ELEM)) return ERROR;
		if(ERROR==InsFirst(&La,p)) return ERROR;
	}
	print_list(La);
	
	if(La.len>0){
		p=NULL;
		if(ERROR==MakeNode(&p,rand()%MAX_TEST_ELEM)) return ERROR;
		printf("Insert rand %d before i(i>=1):",p->data);
		scanf("%d",&i);
		result=INSERT(&La,i,p);
		if(result==OK){
			printf("\nInsert success, after insert:\n");
			print_list(La);
		}else if(result==ERROR){
			printf("\nERROR (pos %d) greater than (1 + %d(len of list))\n",i,La.len);
			return result;
		}else{
			printf("\nDo not support...\n");
			return result;
		}
	}
	if(OK==DestroyList(&La)) printf("\nFree La success\n");
	return OK;
}

int main(){
	rand_test_insert();
	return 0;
}

http://www.niftyadmin.cn/n/5739578.html

相关文章

AD如何画PCB的外框

AD如何画PCB的外框

绘制步骤 ‌选择Mechanical层‌&#xff1a;首先&#xff0c;需要选择Mechanical层来进行外框的绘制。‌绘制外框‌&#xff1a;按下“p”键&#xff0c;再按“L”键开始绘制外框。根据需要的尺寸&#xff0c;绘制出四条边&#xff0c;形成外框。‌自定义板框尺寸‌&#xff1…
阅读更多...
【系统架构设计师】2022年真题论文: 论区块链技术及应用（包括解题思路和素材）

【系统架构设计师】2022年真题论文: 论区块链技术及应用（包括解题思路和素材）

更多内容请见： 备考系统架构设计师-专栏介绍和目录 文章目录 真题题目（2022年 试题3）解题思路区块链技术原理区块链技术的关键特性区块链技术的应用领域论文素材参考真题题目（2022年 试题3） 区块链作为一种分布式记账技术，目前已经被应用到了资产管理、物联网、医疗管理…
阅读更多...
如何对LabVIEW软件进行性能评估？

如何对LabVIEW软件进行性能评估？

对LabVIEW软件进行性能评估&#xff0c;可以从以下几个方面着手&#xff0c;通过定量与定性分析&#xff0c;全面了解软件在实际应用中的表现。这些评估方法适用于确保LabVIEW程序的运行效率、稳定性和可维护性。 一、响应时间和执行效率 时间戳测量&#xff1a;使用LabVIEW的时…
阅读更多...
Android Studio打包时不显示“Generate Signed APK”提示信息

Android Studio打包时不显示“Generate Signed APK”提示信息

Android Studio打包时&#xff0c;默认显示“Generate Signed APK”提示信息&#xff0c;如下图所示&#xff1a; 如果在打包时不显示“Generate Signed APK”提示信息&#xff0c;解决办法是&#xff1a; Android Studio菜单栏&#xff0c;“File->Settings->Appearan…
阅读更多...
2024 年智能驾驶行业深度分析研究报告

2024 年智能驾驶行业深度分析研究报告

一、智能化持续领先带来长期的估值溢价 全球车企市值与估值对比——高端化及智能化成影响车企估值的关键因素。从总市值看&#xff0c;特斯拉市值持续领跑全球车企&#xff0c;其次为丰田汽车、法拉利&#xff0c;比亚迪是国内市值最大的车企。品牌形象带来的高用户粘性&#…
阅读更多...
#Jest进阶知识：整合 webpack 综合练习

#Jest进阶知识：整合 webpack 综合练习

这一小节&#xff0c;我们来做一个综合的练习&#xff0c;该练习会整合&#xff1a; typescriptwebpackjest 准备工作 首先创建项目目录&#xff0c;通过 npm init -y 进行初始化。 整个项目我们打算使用 typescript 进行开发&#xff0c;因此需要安装 typescript npm i t…
阅读更多...
Angular解析本地json文件

Angular解析本地json文件

说明&#xff1a; 效果图&#xff1a; step1:E:\projectgood\ajnine\untitled4\public\config\config.json {"calcServerURL": "http://localhost:3000" }step2:E:\projectgood\ajnine\untitled4\src\app\orance\orance.component.ts import {Componen…
阅读更多...
ubuntu unrar解压 中文文件名异常问题解决

ubuntu unrar解压 中文文件名异常问题解决

sudo apt install language-pack-zh-hans修改/var/lib/locales/supported.d/local&#xff08;如果没有这个文件就新建一个&#xff09; en_US.UTF-8 UTF-8 zh_CN.UTF-8 UTF-8 zh_CN.GBK GBK zh_CN GB23124、执行命令 sudo locale-genUbuntu 中文乱码
阅读更多...
最新文章

Copyright @ 2022~2023