1.2 单链表

本文主要是介绍1.2 单链表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这一章是单链表的算法分析和代码实现。

单链表的结点数据结构：

typedef struct LNode {
	ElemType data;								//数据域
	struct LNode* next;							//指针域
}LNode, *LinkList ;

主要有以下实现功能的函数：

1. LinkList List_HeadInsert(LinkList& L) 功能：头插法建立单链表（逆向建立单链表）；
   参数：L:链表头结点；
   时间复杂度：O(n);

2. LinkList List_TailInsert(LinkList& L) 功能：尾插法建立单链表（正向建立单链表）；
   参数：L:链表头结点；
   时间复杂度：O(n)；

3. LNode* GetElem(LinkList L, int i) 功能：按序号查找结点；
   参数：L:链表头结点 , i:要查找的结点的位置;
   时间复杂度：O(n);

4. LNode* LocateElem(LinkList L, ElemType e) 功能：按值查找结点（查找第一次出现的）；
   参数：L:链表头结点，e:要查找的结点的值；
   时间复杂度：O(n)；

5. bool LNodeInsert(LinkList &L,int i,ElemType e) 功能：插入一个结点；
   参数：L:链表头结点 ，i:插入的位置，e:插入结点的值
   时间复杂度：O(n);

6. bool LNodeDelete(LinkList &L, int i) 功能：删除一个结点；
   参数：L:链表头结点，i:删除结点的位置；
   时间复杂度：O(n);

7. bool LNodeRevise(LinkList& L, int i, ElemType e) 功能：修改一个结点的值；
   参数：L:链表头结点，i:要修改的结点位置，e:要改成的值；
   时间复杂度：O(n)；

8. int LinkLength(LinkList L) 功能：求表长；
   参数：L:链表头结点；
   时间复杂度：O(n)；

9. void PrintList(LinkList L) 功能：输出所有结点的值；
   参数：L:链表头结点；
   时间复杂度：O(n);

可能理解困难的地方：
关于头插法和尾插法：头插法是把每次插入的结点都放到头结点后一位；而尾插法有尾结点指针，每次插入新结点到尾结点后面，然后把尾结点指针移到新插入的结点上。所以用头插法建立的链表和输入的顺序倒序，而尾插法是顺序的。



完整代码：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>

#define ElemType int

/*--------------------------------------------数据结构部分--------------------------------------------*/
/*单链表的数据结构*/
typedef struct LNode {
	ElemType data;								//数据域
	struct LNode* next;							//指针域
}LNode, *LinkList ;

/*初始化链表*/
void InitList(LinkList& L) {
	L = (LinkList)malloc(sizeof(LNode));		//创建头结点
	L->next = NULL;								//初始为空链表
}

/*头插法建立单链表（逆向建立单链表）*/
LinkList List_HeadInsert(LinkList& L) {
	LNode* s,* p;								//s是创建的结点的指针
	int x;
	InitList(L);								//初始化链表
	p = L;
	scanf("%d", &x);							//输入结点的值
	while (x!=9999)								//输入9999结束
	{
		s = (LNode*)malloc(sizeof(LNode));		//创建新结点
		//s = new LNode							//c++可以new
		s->data = x;
		s->next = p->next;						//将新结点插入表中，s->next指向头结点外的第一个结点
		p->next = s;
		scanf("%d", &x);
	}
	return L;
}

/*尾插法建立单链表（正向建立单链表）*/
LinkList List_TailInsert(LinkList& L) {
	int x;
	InitList(L);
	LNode* s, * r = L;						//r为表尾指针
	scanf("%d", &x);
	while (x!=9999)
	{
		s = new LNode;
		s->data = x;
		r->next = s;						//把新结点s添加到表尾r
		r = s;								//r指向新的表尾结点
		scanf("%d", &x);
	}
	r->next = NULL;							//尾结点指针置空
	return L;
}

/*按序号查找结点*/
LNode* GetElem(LinkList L, int i) {
	int j = 1;								//计数，初始为1
	LNode* p = L->next;						//头结点赋值给p
	if (i == 0)								//若i == 0 则返回头结点
		return L;							
	if (i < 1)								//若i无效则返回NULL
		return NULL;
	while (p && j<i)						//从第一个结点开始找，找到第i个结点
	{										//在p == NULL(表遍历结束)或j == i(已找到第i个结点)时跳出循环
		p = p->next;
		j++;
	}
	return p;								//返回第i个结点的指针，若i大于表长返回NULL
}

/*按值查找结点*/
LNode* LocateElem(LinkList L, ElemType e) {
	LNode* p = L->next;
	while (p != NULL && p->data != e)		//从第1个结点开始查找data为e的结点
	{
		p = p->next;						//移动结点指针
	}
	return p;								//找到后返回该节点的指针，否则返回NULL
}

/*插入结点*/
bool LNodeInsert(LinkList &L,int i,ElemType e) {
	LNode* s;
	LinkList p = L;
	p = GetElem(L, i - 1);					//查找插入位置的前驱结点
	if (!p)
		return false;
	s = new LNode;
	s->data = e;
	s->next = p->next;						//s->next指向原来p的下一个结点
	p->next = s;							//p->next指向新增的s结点
	return true;
}

/*删除结点*/
bool LNodeDelete(LinkList &L, int i) {
	LNode* q;
	LinkList p = L;
	p = GetElem(L, i - 1);					//查找删除位置的前驱结点
	if (!p)
		return false;
	q = p->next;							//q指向被删除结点
	p->next = q->next;						//将*q结点从链中断开
	free(q);								//释放结点的存储空间
	return true;
}

/*求表长*/
int LinkLength(LinkList L) {
	LNode* p = L->next;						//头节点不存放数据，不算长度
	int sum = 0;
	while (p)
	{
		p = p->next;						//移动结点指针
		sum++;
	}
	return sum;								//返回表长
}

/*修改节点*/
bool LNodeRevise(LinkList& L, int i, ElemType e) {
	LinkList p = L;
	p = GetElem(L, i);						//拿到要修改的结点
	if (!p || i == 0)						//结点不能为空，不能修改头结点
		return false;
	p->data = e;							//修改结点的值
	return true;
}

/*--------------------------------------------下面是功能函数--------------------------------------------*/
/*插入结点的功能*/
void Insert(LinkList& L) {
	int location;
	ElemType elem;
	printf("输入要插入的元素：");
	scanf("%d", &elem);
	printf("要插入的位置：");
	scanf("%d", &location);
	if (LNodeInsert(L, location, elem))
		printf("插入成功\n");
	else
		printf("插入失败\n");
}

/*删除结点的功能*/
void Delete(LinkList& L) {
	int location;
	printf("输入要删除的元素的位置：");
	scanf("%d", &location);
	if (LNodeDelete(L, location))
		printf("删除成功\n");
	else
		printf("删除失败\n");
}

/*修改结点的功能*/
void Revise(LinkList& L) {
	int i;
	ElemType e;
	printf("输入要修改的位置：");
	scanf("%d", &i);
	printf("修改为：");
	scanf("%d", &e);
	if (LNodeRevise(L, i, e))
		printf("修改成功\n");
	else
		printf("修改失败\n");
}

void Search(LinkList L) {
	int searchChoice;
	printf("（1）按位查找\n");
	printf("（2）按值查找\n");
	printf("选择查找功能：\n");
	scanf("%d", &searchChoice);
	int i;
	ElemType e;
	LNode* p;
	switch (searchChoice)
	{
		case(1):
			printf("输入要查找的节点位置：");
			scanf("%d", &i);
			p = GetElem(L, i);
			if (p && i != 0)					//查找的结点不能为空，也不能查找头结点的值
				printf("第%d个结点的值为%d\n", i, p->data);
			else
				printf("查找失败\n");
			break;
		case(2):
			printf("输入要查找的结点的值：");
			scanf("%d", &e);
			p = LocateElem(L, e);
			if (p)
				printf("找到该元素,查找成功\n");
			else
				printf("找不到该元素,查找失败\n");
			break;
		default:
			break;
	}
}

void PrintList(LinkList L) {
	LinkList p = L->next;					 //头结点无数据不输出
	if (!p)
		printf("表空\n");
	else {
		printf("链表数据：\n");
		while (p)
		{
			printf("%d  ", p->data);
			p = p->next;
		}
		printf("\n共%d个元素\n", LinkLength(L));
	}
}

void menu() {
	printf("\n\n");
	printf("----------①前插法建立链表----------\n");
	printf("----------②后插法建立链表----------\n");
	printf("----------③   插入结点   ----------\n");
	printf("----------④   删除结点   ----------\n");
	printf("----------⑤   修改结点   ----------\n");
	printf("----------⑥   查找结点   ----------\n");
	printf("----------⑦    打印表    ----------\n");
	printf("按“0”退出\n");
	printf("\n\n");
}

int main() {
	LinkList L;
	int choice;
	do
	{
		menu();
		scanf("%d", &choice);
		switch (choice)
		{
			case(1):
				printf("输入每个元素的值（输入9999停止建表）\n");
				List_HeadInsert(L);
				break;
			case(2):
				printf("输入每个元素的值（输入9999停止建表）\n");
				List_TailInsert(L);
				break;
			case(3):
				Insert(L);
				break;
			case(4):
				Delete(L);
				break;
			case(5):
				Revise(L);
				break;
			case(6):
				Search(L);
				break;
			case(7):
				PrintList(L);
				break;
			default:
				break;
		}
	} while (choice!=0);
	return 0;
}

这篇关于1.2 单链表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！