[数据结构与算法] 数据结构课上练习（三）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构课上练习（三） -> 正文阅读

[数据结构与算法]数据结构课上练习（三）

方法一:
直接使用指针的指针来保存头指针L，不使用函数返回头结点的指针
使用指针的指针目的是保存单链表头指针
（只要找到单链表的头指针，就能找到整个单链表）

#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
//创建结点结构体
typedef struct Node
{	//数据域
	ElemType data;
	//指针域
	struct Node* next;
}LNode, * LinkList;
//初始化单链表
//函数周期结束后不会销毁指针变量，所以用一个指针存储头指针L，这样便可保存指向头指针，而不用返回值 
void InitList(LinkList* L)	
{
	*L = (LNode*)malloc(sizeof(LNode));
	(*L)->next = NULL;
}
//创建单链表(头插法)
void CreateLinkList_Head(LinkList* L, int n) //n个结点
{
	//新建结点p
	LNode* p;
	//循环插入新建结点p
	for (int i=0; i < n; i++)
	{
		p = (LNode*)malloc(sizeof(LNode));
		printf("输入结点的数据(整数):");
		//输入结点的数据
		scanf("%d", &p->data);
		p->next = (*L)->next;
		(*L)->next = p;
	}
}
//创建单链表(尾插法)
void CreateLinkList_Rear(LinkList *L, int n)
{	
	//新建结点p，r指向尾结点
	LNode *p,*r;
	r = *L;	//初始化尾指针，指向头结点
	for (int i = 0; i < n; i++)
	{	
		p = (LNode*)malloc(sizeof(LNode));
		printf("输入结点的数据(整数):");
		//输入结点的数据
		scanf("%d", &p->data);
		//将结点p的指针域置空(因为是后插，所以新结点p在单链表尾部)
		p->next = NULL;
		//新结点p插入单链表尾部
		r->next = p;
		//将尾指针指向新单链表的尾部，即结点p
		r = p;
	}
}
//输出单链表
void PrintLinkList(LinkList L)
{
	//指向结点的指针
	LNode* p;
	//p指向首元结点
	p = L->next;
	while (p != NULL)
	{
		//打印结点数据域
		printf("%d", p->data);
		//指针p右移
		p = p->next;
	}
}

int main()
{
	LinkList L;
	//初始化单链表
	InitList(&L);
	//单链表中结点个数
	int n;
	printf("需要为该单链表输入结点个数:");
	scanf("%d", &n);
	//头插法创建单链表
	CreateLinkList_Head(&L, n);
	//尾插法创建单链表
	//CreateLinkList_Rear(&L, n);
	//打印单链表
	printf("打印的链表为:\n");
	PrintLinkList(L);
	return 0;
}

头插法

尾插法

方法二：
直接用函数返回单链表的头指针，以便保存单链表头指针
（只要找到单链表的头指针，就能找到整个单链表）

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
//创建结点结构体
typedef struct Node
{	//数据域
	ElemType data;
	//指针域
	struct Node* next;
}LNode, * LinkList;
//初始化单链表
LinkList InitList(LinkList L)	//返回类型为指针类型，返回单链表头指针
{
	//L指向头结点
	L = (LinkList)malloc(sizeof(LinkList));
	//头结点置空
	L->next = NULL;
	return L;	//返回单链表头指针
}
//创建单链表(头插法)
LinkList CreateLinkList_Head(LinkList L, int n) //返回类型为指针类型，返回单链表头指针
{	
	
	//新建结点p
	LNode* p;
	//采用头插法将结点p插入单链表
	for (int i = 0; i < n; i++)
	{
		p = (LNode*)malloc(sizeof(LNode));
		printf("输入结点的数据(整数):");
		//输入结点的数据
		scanf("%d", &p->data);
		p->next = L->next;
		L->next = p;
	}
	return L; //返回单链表头指针
}
//创建单链表(尾插法)
LinkList CreateLinkList_Rear(LinkList L, int n)	//返回类型为指针类型，返回单链表头指针
{
	//新建结点p，r指向尾结点
	LNode* p, * r;
	r = L;	//初始化尾指针，指向头结点
	for (int i = 0; i < n; i++)
	{
		p = (LNode*)malloc(sizeof(LNode));
		printf("输入结点的数据(整数):");
		//输入结点的数据
		scanf("%d", &p->data);
		//将结点p的指针域置空(因为是后插，所以新结点p在单链表尾部)
		p->next = NULL;
		//新结点p插入单链表尾部
		r->next = p;
		//将尾指针指向新单链表的尾部，即结点p的尾部
		r = p;
	}
	return L; //返回单链表头指针
}
//输出单链表
void PrintLinkList(LinkList L)
{
	//指向结点的指针
	LNode* p;
	//p指向首元结点
	p = L->next;
	while (p != NULL)
	{
		//打印结点数据域
		printf("%d", p->data);
		//指针p右移
		p = p->next;
	}
}

int main()
{
	LinkList l;
	//新建有头结点的单链表
	l = (LinkList)malloc(sizeof(LinkList));
	//初始化单链表
	l=InitList(l);	//函数返回单链表头指针给l接收
	//单链表中结点个数
	int n;
	printf("需要为该单链表输入结点个数:");
	scanf("%d", &n);
	//头插法创建单链表
	l=CreateLinkList_Head(l, n);
	//尾插法创建单链表
	//l=CreateLinkList_Rear(l, n);
	//打印单链表
	printf("打印的链表为:\n");
	PrintLinkList(l);
	return 0;
}

头插法

尾插法

获取链表第 i 个位置元素

#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
//创建结点结构体
typedef struct Node
{	//数据域
	ElemType data;
	//指针域
	struct Node* next;
}LNode, * LinkList;
//初始化单链表
void InitList(LinkList* L)	//函数周期结束后不会销毁指针变量，所以用一个指针存储指向头结点的指针，这样便可留下指向头结点的指针，而不用返回值 
{

	*L = (LNode*)malloc(sizeof(LNode));
	(*L)->next = NULL;
}
//创建单链表(头插法)
void CreateLinkList_Head(LinkList* L, int n) //n个结点 *L保存头指针的值，避免用函数返回
{
	//新建结点p
	LNode* p;
	//采用头插法将结点p插入单链表
	for (int i = 0; i < n; i++)
	{
		p = (LNode*)malloc(sizeof(LNode));
		printf("输入结点的数据(整数):");
		//输入结点的数据
		scanf("%d", &p->data);
		p->next = (*L)->next;
		(*L)->next = p;
	}
}
//创建单链表(尾插法)
void CreateLinkList_Rear(LinkList* L, int n)
{	
	//新建结点p，r指向尾结点
	LNode *p,*r;
	r = *L;	//初始化尾指针，指向头结点
	for (int i = 0; i < n; i++)
	{	
		p = (LNode*)malloc(sizeof(LNode));
		printf("输入结点的数据(整数):");
		//输入结点的数据
		scanf("%d", &p->data);
		//将结点p的指针域置空(因为是后插，所以新结点p在单链表尾部)
		p->next = NULL;
		//新结点p插入单链表尾部
		r->next = p;
		//将尾指针指向新单链表的尾部，即结点p的尾部
		r = p;
	}

}
//根据序号i获取对应位置的元素e
int GetElem(LinkList L, int i, ElemType* e)
{
	LNode* p;
	//循环向后遍历单链表
	p = L->next;
	//计数器j
	int j=0;
	while (p!=NULL && j<i)
	{	
		//指针后移
		p = p->next;
		//计数器j
		j++;
	}
	//循环结束后p会指向指定元素
	*e = p->data;
	return *e;
}
//输出单链表
void PrintLinkList(LinkList L)
{
	//指向结点的指针
	LNode* p;
	//p指向首元结点
	p = L->next;
	while (p != NULL)
	{
		//打印结点数据域
		printf("%d", p->data);
		//指针p右移
		p = p->next;
	}
	printf("\n");
}

int main()
{
	LinkList L;
	//初始化单链表
	InitList(&L);
	//单链表中结点个数
	int n;
	printf("需要为该单链表输入结点个数:");
	scanf("%d", &n);
	//头插法创建单链表
	//CreateLinkList_Head(&L, n);
	//尾插法创建单链表
	CreateLinkList_Rear(&L, n);
	//打印单链表
	printf("打印的链表为:");
	PrintLinkList(L);
	int i;	//元素位置
	ElemType e;	//接收获取元素
	//输入要获取元素的位置i
	printf("输入要获取元素的位置:");
	scanf("%d",&i);
	e=GetElem(L, i-1, &e);	//位置为i对应链表位置i-1
	printf("元素内容为:%d",e);
	return 0;
}

获取链表第 i 个位置的元素

根据寻找输入元素在链表中的位置

#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
//创建结点结构体
typedef struct Node
{	//数据域
	ElemType data;
	//指针域
	struct Node* next;
}LNode, * LinkList;
//初始化单链表
void InitList(LinkList* L)	//函数周期结束后不会销毁指针变量，所以用一个指针存储指向头结点的指针，这样便可留下指向头结点的指针，而不用返回值 
{
	//	//L指向头结点
	//	L = (LinkList)malloc(sizeof(LinkList));
	//	//头结点置空
	//	L->next = NULL;
	*L = (LNode*)malloc(sizeof(LNode));
	(*L)->next = NULL;
}
//创建单链表(头插法)
void CreateLinkList_Head(LinkList* L, int n) //n个结点 *L保存头指针的值，避免用函数返回
{
	//新建结点p
	LNode* p;
	//采用头插法将结点p插入单链表
	for (int i = 0; i < n; i++)
	{
		p = (LNode*)malloc(sizeof(LNode));
		printf("输入结点的数据(整数):");
		//输入结点的数据
		scanf("%d", &p->data);
		p->next = (*L)->next;
		(*L)->next = p;
	}
}
//创建单链表(尾插法)
void CreateLinkList_Rear(LinkList* L, int n)
{	
	//新建结点p，r指向尾结点
	LNode *p,*r;
	r = *L;	//初始化尾指针，指向头结点
	for (int i = 0; i < n; i++)
	{	
		p = (LNode*)malloc(sizeof(LNode));
		printf("输入结点的数据(整数):");
		//输入结点的数据
		scanf("%d", &p->data);
		//将结点p的指针域置空(因为是后插，所以新结点p在单链表尾部)
		p->next = NULL;
		//新结点p插入单链表尾部
		r->next = p;
		//将尾指针指向新单链表的尾部，即结点p的尾部
		r = p;
	}

}
//根据传入元素获取其在链表中位置
int GetNum(LinkList L, ElemType e)
{
	LNode* p;
	p = L->next;
	int i=0;	//记录位置
	while (p != NULL && p->data != e)
	{
		p = p->next;
		i++;
		//找到该元素
		if ( p!=NULL && p->data == e)
			return i;
	}
	//未找到元素返回错误信息
	if (p == NULL) {
		return 0;
	}
}
//输出单链表
void PrintLinkList(LinkList L)
{
	//指向结点的指针
	LNode* p;
	//p指向首元结点
	p = L->next;
	while (p != NULL)
	{
		//打印结点数据域
		printf("%d", p->data);
		//指针p右移
		p = p->next;
	}
	printf("\n");
}

int main()
{
	LinkList L;
	//初始化单链表
	InitList(&L);
	//单链表中结点个数
	int n;
	printf("需要为该单链表输入结点个数:");
	scanf("%d", &n);
	//头插法创建单链表
	//CreateLinkList_Head(&L, n);
	//尾插法创建单链表
	CreateLinkList_Rear(&L, n);
	//打印单链表
	printf("打印的链表为:");
	PrintLinkList(L);
	int i;
	ElemType e;
	printf("输入要查询的元素:");
	scanf("%d",&e);
	i = GetNum(L, e);
	if (i==0)
		printf("未找到该元素");
	else
		printf("元素对应的位置:%d",i+1);		//i从0开始
	return 0;
}

根据寻找输入元素在链表中的位置

在指定位置插入元素

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
//创建结点结构体
typedef struct Node
{	//数据域
	ElemType data;
	//指针域
	struct Node* next;
}LNode, * LinkList;
//初始化单链表
void InitList(LinkList* L)	//函数周期结束后不会销毁指针变量，所以用一个指针存储指向头结点的指针，这样便可留下指向头结点的指针，而不用返回值 
{
	//	//L指向头结点
	//	L = (LinkList)malloc(sizeof(LinkList));
	//	//头结点置空
	//	L->next = NULL;
	*L = (LNode*)malloc(sizeof(LNode));
	(*L)->next = NULL;
}
//创建单链表(头插法)
void CreateLinkList_Head(LinkList* L, int n) //n个结点 *L保存头指针的值，避免用函数返回
{
	//新建结点p
	LNode* p;
	//采用头插法将结点p插入单链表
	for (int i = 0; i < n; i++)
	{
		p = (LNode*)malloc(sizeof(LNode));
		printf("输入结点的数据(整数):");
		//输入结点的数据
		scanf("%d", &p->data);
		p->next = (*L)->next;
		(*L)->next = p;
	}
}
//创建单链表(尾插法)
void CreateLinkList_Rear(LinkList* L, int n)
{	
	//新建结点p，r指向尾结点
	LNode *p,*r;
	r = *L;	//初始化尾指针，指向头结点
	for (int i = 0; i < n; i++)
	{	
		p = (LNode*)malloc(sizeof(LNode));
		printf("输入结点的数据(整数):");
		//输入结点的数据
		scanf("%d", &p->data);
		//将结点p的指针域置空(因为是后插，所以新结点p在单链表尾部)
		p->next = NULL;
		//新结点p插入单链表尾部
		r->next = p;
		//将尾指针指向新单链表的尾部，即结点p的尾部
		r = p;
	}

}

//向链表第i个位置前插入元素
void LinkListInsert(LinkList *L, int i, ElemType e)
{
	int j=0;
	LNode *p,*s;
	//新建结点s
	s = (LNode*)malloc(sizeof(LNode*));
	//结点s数据域赋值
	s->data = e;
	p = (*L);
	while (p!=NULL && (j<i-1) )
	{
		//指针p循环右移
		p = p->next;
		j++;
	}
	//连接操作
	s->next = p->next;
	p->next = s;
}

//输出单链表
void PrintLinkList(LinkList L)
{
	//指向结点的指针
	LNode* p;
	//p指向首元结点
	p = L->next;
	while (p != NULL)
	{
		//打印结点数据域
		printf("%d", p->data);
		//指针p右移
		p = p->next;
	}
	printf("\n");
}

int main()
{
	LinkList L;
	//初始化单链表
	InitList(&L);
	//单链表中结点个数
	int n;
	printf("需要为该单链表输入结点个数:");
	scanf("%d", &n);
	//头插法创建单链表
	//CreateLinkList_Head(&L, n);
	//尾插法创建单链表
	CreateLinkList_Rear(&L, n);
	//打印单链表
	printf("打印的链表为:");
	PrintLinkList(L);
	int i;
	ElemType e;
	//插入操作
	printf("请输入要插入元素的内容(整数):");
	scanf("%d", &e);
	printf("请输入要插入的位置(整数):");
	scanf("%d", &i);
	LinkListInsert(&L,i,e);
	//打印单链表
	printf("插入后的链表为:");
	PrintLinkList(L);
	return 0;
}

在指定位置前插入元素

删除单链表

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
//创建结点结构体
typedef struct Node
{	//数据域
	ElemType data;
	//指针域
	struct Node* next;
}LNode, * LinkList;
//初始化单链表
void InitList(LinkList* L)	//函数周期结束后不会销毁指针变量，所以用一个指针存储指向头结点的指针，这样便可留下指向头结点的指针，而不用返回值 
{
	//	//L指向头结点
	//	L = (LinkList)malloc(sizeof(LinkList));
	//	//头结点置空
	//	L->next = NULL;
	*L = (LNode*)malloc(sizeof(LNode));
	(*L)->next = NULL;
}
//创建单链表(头插法)
void CreateLinkList_Head(LinkList* L, int n) //n个结点 *L保存头指针的值，避免用函数返回
{
	//新建结点p
	LNode* p;
	//采用头插法将结点p插入单链表
	for (int i = 0; i < n; i++)
	{
		p = (LNode*)malloc(sizeof(LNode));
		printf("输入结点的数据(整数):");
		//输入结点的数据
		scanf("%d", &p->data);
		p->next = (*L)->next;
		(*L)->next = p;
	}
}
//创建单链表(尾插法)
void CreateLinkList_Rear(LinkList* L, int n)
{	
	//新建结点p，r指向尾结点
	LNode *p,*r;
	r = *L;	//初始化尾指针，指向头结点
	for (int i = 0; i < n; i++)
	{	
		p = (LNode*)malloc(sizeof(LNode));
		printf("输入结点的数据(整数):");
		//输入结点的数据
		scanf("%d", &p->data);
		//将结点p的指针域置空(因为是后插，所以新结点p在单链表尾部)
		p->next = NULL;
		//新结点p插入单链表尾部
		r->next = p;
		//将尾指针指向新单链表的尾部，即结点p的尾部
		r = p;
	}

}

//链表的删除
void LinkListDelete(LinkList L)
{
	LNode *p,*q;
	p = L;
	//循环删除单链表中结点
	while (p->next != NULL)
	{
		//删除操作
		q = p->next;
		p->next = q->next;
		//释放结点
		free(q);
	}
}

//输出单链表
void PrintLinkList(LinkList L)
{
	//指向结点的指针
	LNode* p;
	//p指向首元结点
	p = L->next;
	while (p != NULL)
	{
		//打印结点数据域
		printf("%d", p->data);
		//指针p右移
		p = p->next;
	}
	printf("\n");
}

int main()
{
	LinkList L;
	//初始化单链表
	InitList(&L);
	//单链表中结点个数
	int n;
	printf("需要为该单链表输入结点个数:");
	scanf("%d", &n);
	//头插法创建单链表
	//CreateLinkList_Head(&L, n);
	//尾插法创建单链表
	CreateLinkList_Rear(&L, n);
	//打印单链表
	printf("打印的链表为:");
	PrintLinkList(L);

	//删除单链表
	LinkListDelete(L);
	//打印单链表
	printf("删除后的链表为:");
	PrintLinkList(L);
	return 0;
}