数据结构 链表

　

链表

链表的生成

上学期学链表的时候掌握了点皮毛，马马虎虎写了不带头结点的链表，这学期学数据结构觉得写代码要规范点才行，于是写了带头结点的链表。链表，顾名思义就是一串像链子的表格串接起来，当你不够用了，再开辟块内存接在这个链表的尾部，这时，就可以动态得分配内存大小，既不用担心拿多了内存造成浪费，也不用“处心积虑”地去考虑要存的数据到底需要多少。但是，相对于顺序表，链表的弊端还是有的，没错，就是要查哪个位置的元素内容，链表时间复杂度O(n)，顺序表只需要O(1);然而，它的优势也是有的，在增加或者删除节点的时候，顺序表需要O(n),链表则只需要O(1)。各有所长！

要求：

实现链表各种基本运算的算法

1 实验目的

实现链表的各种基本运算（含链表逆序的操作）。

2 实验内容

实现链表的各种基本运算，并在此基础上设计一个主程序完成以下功能：

(1) 以学号分解后的数字，如学号为20161100，则通过键盘输入2、0、1、6、1、1、0、0生成单链表L；

(2) 依次输出链表L的元素

(3) 输出链表L的长度

(4) 输出链表L的第2个元素

(5) 输出元素6的位置

(6) 在第4个元素位置上插入9元素

(7) 依次输出链表L的元素

(8) 删除L的第3个元素

(9) 依次输出链表L的元素

(10) 对链表进行逆序，再依次输出链表L的元素

(11) 释放链表L。

具体代码如下：

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

//******宏定义参数内容******
#define DATA_SIZE 200
#define EXTEND_DATA_SIZE 50
#define NO 0
#define OK 1
#define ERROR -1

//******基本数据类型别名******
typedef int Status;
typedef char excelelem;
typedef int Numelem;

//******链表数据结构******
typedef struct Node
{
	Excelelem book;
	struct Node *next;
}Liststruct;

/******链表表头信息******/
typedef struct
{
	Excelelem book[100]; //表头信息
	Liststruct *next;
	Numelem Length;
}ListHead;

//******初始化链表******
Liststruct *init(int *i)
{
	Liststruct *Head,*p,*q;
	Excelelem ch;
	Head=q=NULL;
	printf("请输入顺序表Head的内容:\n");
	while((ch=getchar())!='\n')
	{
		p=(Liststruct *)malloc(sizeof(Liststruct));
		p->book=ch;
		if(!(*i)) Head=q=p,(*i)++;
		else
		{
			q->next=p;
			q=p;
			(*i)++;
		}
	}//注意*q++与(*q)++,有区别！
	if(q) q->next=NULL;
	return Head;
}

ListHead *Headinit()
{
	ListHead *Head;
	Head=(ListHead *)malloc(sizeof(ListHead));
	Head->Length=0;
	Head->next=init(&Head->Length);
	return Head;
}

/******打印表中数据内容******/
void DATA_cout(ListHead *Head)
{
	Liststruct *p=Head->next;
	while(p!=NULL)
	{
		printf("%c",p->book);
		p=p->next;
	}
	printf("\n");
	return ;
}
 /******打印表中local位置元素内容******/
void Local(ListHead* Head,int local)
{
	if(Head->Length<local || local<1)
	{
		printf("警告！不存在%d位置的元素\n",local);
		return ;
	}
	Liststruct *p=Head->next;
	int i=1;
	while(p && i++!=local)
		p=p->next;
	printf("%c\n",p->book);
	return ;
}

/******找到表中出现的字符ch的位置******/
void DATA_find(ListHead* Head,char ch)
{
	int i=1,flag=0,count=1;
	Liststruct *p=Head->next;
	while(p)
	{
		if(p->book==ch)
		{
			flag=1;
			printf("%d.在第%d个位置出现元素%c\n",count++,i,ch);
		}
		p=p->next;
		i++;
	}
	if(!flag)
		printf("未能找到%c元素！\n",ch);
	return ;
}

/******在第k个元素前插入一个元素******/
void DATA_Insert(ListHead *Head,int k,Excelelem ch)
{
	if(Head->Length<k || k<1)
	{
		printf("警告！不存在%d位置的元素\n",k);
		return ;
	}
	Liststruct *p=Head->next,*q,*t;
	int i=1;
	while(p && i++!=k)
		t=p,p=p->next;
	q=(Liststruct *)malloc(sizeof(Liststruct));
	q->book=ch;
	if(k==1)
	{
		Head->next=q;
		q->next=p;
	}
	else
	{
		q->next=p;
		t->next=q;
	}
	Head->Length++;
	return ;
}

/******删除第k个元素******/
void DATA_Delete(ListHead *Head,int k)
{
	if(Head->Length<k || k<1)
	{
		printf("警告！不存在%d位置的元素\n",k);
		return ;
	}
	int i=1;
	Liststruct *p=Head->next,*q;
	while(p && i++!=k)
		q=p,p=p->next;
	if(k==1)
		Head->next=p->next;
	else
		q->next=p->next;
	free(p);
	Head->Length--;
	return ;
}

/******逆置链表******/
void DATA_UN(ListHead *Head)
{
	Liststruct *p,*q;
	p=Head->next;
	Head->next=NULL;
	while(p!=NULL)
	{
		q=p;
		p=p->next;
		q->next=Head->next;
		Head->next=q;
	}
	return ;
}

/******返还内存******/
void List_FREE(ListHead *Head)
{
	Liststruct *p=Head->next,*q;
	free(Head);
	while(p)
	{
		q=p;
		p=p->next;
		free(q);
	}
	return ;
}

int main()
{
	ListHead *Head;
	Numelem i;
	Excelelem ch;
	puts("");
	puts("******等待链表Head初始化!******");
	Head=Headinit();
	puts("******链表Head初始化完成!******");
	printf("链表中的内容为:\n");
	DATA_cout(Head);
	printf("链表Head的长度为:\n");
	printf("%d\n",Head->Length);
	printf("链表第%d个元素是:\n",i=2);
	Local(Head,i);
	printf("链表中出现%c元素的位置分别是:\n",ch='6');
	DATA_find(Head,ch);
	printf("在链表的第%d个元素之前插上%c\n",i=4,ch='9');
	DATA_Insert(Head,i,ch);
	printf("链表中的内容为:\n");
	DATA_cout(Head);
	printf("将链表中第%d个元素删除\n",i=3);
	DATA_Delete(Head,i);
	printf("链表中的内容为:\n");
	DATA_cout(Head);
	printf("将链表所有元素逆置，请稍后...\n\n");  //多种方法
	DATA_UN(Head);
	printf("链表中的内容为:\n");
	DATA_cout(Head);
	puts("******链表Head使用完毕!******\n");
	List_FREE(Head);
	return 0;
}

总结：

链表写法有挺多种的，关键在于怎么定义那个结构，指向结构体的指针非常重要，有头的节点在使用上非常便捷，同时在进行增删改查也显得容易。

相关阅读

【数据结构】线索二叉树（构造与遍历）

主要内容 基本概念 构造线索二叉树 遍历线索二叉树   基本概念 遍历二叉树是对非线性结构结点的线性化过程，由此得到的遍历

Hbase数据结构+hbase shell基本语法

全栈工程师开发手册 （作者：栾鹏）架构系列文章 HBase中的表一般有这样的特点：1 大：一个表可以有上亿行，上百万列2 面向列:面向列(族)的存

严蔚敏老师版《数据结构》笔记之基本概念和术语

1. 什么是数据结构 如果要写好一个程序，必须分析待处理的对象的特性和对象之间的关系，这是“数据结构”形成和发展的背景。 “数据

数据结构(Java随笔)—图

图（Graph）——非线性数据结构，现实的图结构模型有通信网络，交通网络，人际关系网络等，图结构的组织形式比树结构更为复杂，因此，图结构对存

数据结构与算法——从零开始学习（一）基础概念篇

前言 数据结构：是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、（存