[数据结构与算法]数据结构-c++版-硬钢单链表(待定)

在用c语言的函数时,要记住:
c语言函数内部的值,
只能在通过返回值来获取.

//单链表
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0 //if(0)为if(假)
#define OK 1    //if(非0)为if(真)

typedef  int ElemType;
typedef struct Node {
	ElemType date;//结点的数据域
	struct Node* next;//结点的指针域
}Node, LinkList;//链表结点,链表


LinkList* InitList(LinkList* L) {//构造一个空的单链表
	L = (LinkList *)  malloc( sizeof(Node));//生成新结点作为头结点,用头指针L指向头结点
	L->next = NULL;//头结点的指针域置空
	return L;
}

//尾插法  =>依次把元素插在后面(只要找到最后一个元素即可)
int ListInsert_back(LinkList* L, Node* node) {
	Node* last = NULL;
	if (!L || !node)return ERROR;
	last = L;
	while (last->next) last = last->next;//依次遍历找到最后一个节点(最后一个节点的特点:
	//最后一个节点的next为空)

	node->next = NULL;//左边是橄榄枝,右边人是受邀人
	last->next = node;//左边是橄榄枝,右边是受邀人
	return OK;
}



//在任意位置的插入
//指定位置插入
//也叫任意位置的前插法
int LinkInsert(LinkList* L, int i, int e) {//在位置i插入元素e
	if (!L) return ERROR;

	int j = 0;
	LinkList* p, * s;
	p = L;

	//找到位置为i-1的节点,p指向该节点
	while (p && j < i - 1) {//当p不为空且j<i-1
		p = p->next;
		j++;
	}
	//要在节点2插入一个元素,就要找到节点1(节点和位置在数值上保持一致)
	// eg:在节点2插入一个元素
	//第一轮循环:0<2-1  =>p从头节点指向第一个节点
	//第二轮循环:1<1     =>不成立,循环结束

	if (!p || j > i - 1) {
		//!p       防止出现你只有3个节点,但是你想在第5个节点插入的现象
		//j>i-1   防止你想在负位置插入(防止i=0和i<0的情况)(因为节点最小是1)
		return ERROR;
	}

	//如果能走到这,说明已经    找到了   要插入位置  的  前一个节点   了
	s = (LinkList*)malloc(sizeof(Node));//生成新节点
	s->date = e;
	s->next = p->next;
	p->next = s;
	return OK;

	//malloc一次free一次,new一次delete一次
	//函数调用完毕之后,堆空间是不会自动消失的!
	//函数调用完毕之后,指针变量s(存放在栈空间)没了,但是,之前申请的堆空间还在
	//=>也就是说,函数调用完毕之后,没有任何人指向之前申请的堆空间了,但是,内存,还在!
	free (s);
}

单链表的取值
 也叫按位查找
按位置获取对应位置的元素
//int Link_GetElem(LinkList* L, int i, int e) {
//	//在链表中查找第i个元素
//	//用e记录链表第i个数据元素的值
//	int index;
//	LinkList* p;//临时的指针
//
//	if (!L || !L->next) return ERROR;
//	//链表为空,或者只有一个头结点,直接return false
//
//	p = L->next;
//	index = 1;
//	while (p && index < i) {
//		//p不为空,当index==i时,就找到了
//		p = p->next;
//		index++;  //计数器相应+1
//	}
//	if (!p || index > i) return ERROR;//i值不合法,i>n或者i<=0
//
//	e = p->date;
//	return OK;
//}

//按值查找
int Link_FindElem(LinkList* L, int e) {
	//在带头结点的单链表L中查找值为e的元素
	//并返回元素e的位置index

	LinkList* p;//临时的指针
	p = L->next;//让p指向第一个节点
	int index = 1;

	if (!L || !L->next) {
		//链表为空,或者只有一个头结点,直接return false
		index = 0;//位置无效
		return ERROR;
	}

	while (p && p->date != e) {
		//p不为空,当p->date == e时,就找到了
		p = p->next;
		index++;
	}

	if (!p) {
		//查无此值
		index = 0;//位置无效
		return	ERROR;
	}

	return index;
}

//单链表删除元素
int LinkDelete(LinkList* L, int i) {
	//删除节点i
//要删除第二个节点,就要找到第一个节点
	LinkList* p, * q;

	int index = 0;
	p = L;//从头结点开始

	if (!L || !L->next) {
		return ERROR;
	}

	while (p->next && index < i - 1) {
		p = p->next;
		index++;
	}

	if (!p->next || index > i - 1) {//当i>n或i<1时,删除位置不合理
		return ERROR;
	}

	q = p->next;//这里q并没有抛出橄榄枝,然而直接把q变成了p->next本身
	p->next = q->next;//左边是橄榄枝,右边是受邀人(只有左边是->next时,才是抛出橄榄枝)

	free (q);//释放删除节点q的内存
	return OK;
}

//单链表的输出
void LinkPrint(LinkList* L) {
	printf("链表输出:\n");
	LinkList* p = NULL;//用一个临时指针来遍历
	if (!L) {
		printf("链表为空!\n");
		return;
	}
	p = L->next;
	while (p) {
		printf("%d\t", p->date);
		p = p->next;
	}
	printf("\n");
}

//销毁单链表
void LinkDextory(LinkList* L) {
	//定义临时节点p指向头结点
	LinkList* p = L;
	printf("正在销毁单链表...(注:头结点没有值,所以为负数)\n");
	while (p) {
		L = L->next;//L指向下一个节点
		printf("删除元素:%d\n", p->date);
		free (p);//删除当前节点
		p = L;//p移向下一个节点
	}
	printf("销毁单链表成功!\n");
}






int main() {
	LinkList* L = NULL;//L作为主体链表
	LinkList* s = NULL;//s作为要插入的新节点

	//初始化一个空的链表
	L=InitList(L);
	/*特别注意:在c语言中,
	* 如果用函数来申请堆空间,
	* 函数的返回值必须是一个指针,
	* (并在main函数中用一个指针来接这个函数的指针)
	* 否则,
	* 申请的空间只存在于函数中,
	* 一旦离开了这个函数,
	* 空间将被完全释放!
	*/

	if(!L)printf("初始化链表失败\n");
	printf("初始化链表成功\n");


	//使用尾插法插入数据
	int n;
	printf("尾插法创建单链表!\n");
	printf("请输入您要创建元素的个数:");
	scanf_s("%d", &n);
	printf("请依次输入%d个元素\n", n);
	while (n > 0) {
		s = (LinkList*)malloc(sizeof(Node));//生成新结点s   //新结点指针域
		scanf_s("%d",&s->date); //新结点数据域
		//printf("正在插入中...\n");
		ListInsert_back(L, s);
		//printf("插入成功!\n");
		n--;
	}

	//单链表的输出
	LinkPrint(L);

	//任意位置插入
	printf("这里插入3次.\n");
	for (int j = 0; j < 3; j++) {
		int i, x;
		printf("请输入要插入的位置和元素(用空格隔开):\n");
		scanf_s("%d %d", &i, &x);

		if (LinkInsert(L, i, x)) {
			printf("插入成功\n");
		}
		else {
			printf("插入失败\n");
		}
		LinkPrint(L);
	}

	//int element = 0;
	//if (Link_GetElem(L, 2, element)) {/
	//	printf("获取第二个元素成功!  值: %d\n", element);
	//}
	//else {
	//	printf("获取第二个元素失败!\n");
	//}


	if (Link_FindElem(L, 10)) {//查找元素10的位置
		printf("查找元素10的位置是:%d\n", Link_FindElem(L, 10));
	}
	else {
		printf("查无此值\n");
	}

	if (LinkDelete(L, 2)) {
		printf("删除第2个元素成功!\n");
		LinkPrint(L);
	}
	else {
		printf("删除第2个元素失败\n");
		LinkPrint(L);
	}

	LinkDextory(L);

	system("pause");
	return 0;
}