C语言版-单链表

单链表 单链表的定义 什么是单链表

每个结点除了存放数据元素外，还要存储指向下一个节点的指针

顺序表和单恋表优缺点

顺序表：

优点：可随机存取，存储密度高
缺点：要求大片连续空间，改变容量不方便

单链表：

优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要耗费一定空间存放指针

用代码定义一个单链表

typedef struct LNode {			//定义单链表节点类型    typedef 关键字----数据类型重命名
	ElemType data;	//每个节点存放一个数据元素
	struct LNode *next;   //指针指向下一个节点
}LNode, *LinkList;
LinkList p = (LinkList)malloc(sizeof(LNode));

注意：

• LNode *：强调是一个结点
• *LinkList：强调是一个链表

两种实现 带头结点 初始化

/*初始化一个单链表（带头结点）*/
bool InitList(LinkList &L) {
	L = (LNode *) malloc(sizeof(LNode));
	if (L == NULL) return false;
	L->next = NULL;
	return true;
}

判断单链表是否为空

/*判断单链表是否为空（带头结点）*/
bool Empty(LinkList L) {
	return L->next == NULL;
}

不带头节点 初始化

/*初始化一个单链表（b带头结点）*/
bool InitList(LinkList &L) {
	L = NULL;
	return true;
}

判断单链表是否为空

/*判断单链表是否为空（不带头结点）*/
bool Empty(LinkList L) {
	return L == NULL;
}

单链表的插入删除 插入 按位序插入

插入 *** 作。

在表L中的第i个位置上插入指定元素e。

带头结点

/*  按位序插入 */
bool ListInsert(LinkList &L, int i, ElemType e) {
	if(i < 1) 
		return false;
	LNode *p;		//指针p指向当前扫描到的结点
	int j =0;		//当前p指向的是第几个结点
	p = L;			//L指向头结点，头结点是第0个结点（不存数据）
	while(p != NULL && j < i - 1) {		//循环找到第 i-1 个结点
		p = p->next;
		j ++;

	}
	if (p == NULL) 	//i值不合法
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;	//将结点s连到p之后
	return true;	//插入成功
}

不带头结点

/*  按位序插入 */
bool ListInsert(LinkList &L, int i, ElemType e) {
	if(i < 1) 
		return false;
	if(i == 1) {//插入第1个结点的操作与其他结点操作不同
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->next = e;
		s->next = L;
		L = s;		//头指针指向新结点
		return true;
	}
	LNode *p;		//指针p指向当前扫描到的结点
	int j =1;		//当前p指向的是第几个结点
	p = L;			//L指向头结点，（不是头结点）
	while(p != NULL && j < i - 1) {		//循环找到第 i-1 个结点
		p = p->next;
		j ++;

	}
	if (p == NULL) 	//i值不合法
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;	//将结点s连到p之后
	return true;	//插入成功
}

指定结点的后插 *** 作

/* 后插 *** 作：在p结点之后插入元素 e */
bool InsertNextNode(LNode *p, ElemType e) {
	if (p == NULL) return false;
    
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if (s == NULL) return false;	/* 内存分配失败 */
    
	s->data = e;		/* 用结点s保存数据元素e */
	s->next = p->next;
	p->next = s;		/* 将结点s连到p之后 */
	return true;	
}

指定结点的前插 *** 作

/* 前插 *** 作：在p结点之前插入元素 e */
bool InsertPriorNode(LNode *p, ElemType e) {
	if (p == NULL) return false;

	LNode *s = (LNode *)malloc(sizeof(LNode));
	if (s == NULL) return false;

	s->next = p->next;
	p->next = s;			/* 新结点s连到p之后 */
	s->data = p->data;		/* 将p中元素复制到s中 */
	p->data = e;			/* p中元素覆盖e */
	return true;
}

删除

删除 *** 作。

删除表L中第i个位置的元素，并用返回删除元素的值。

按位序删除（带头结点）

/*  按位序删除（带头结点） */
bool ListDelete(LinkList &L, int i, ElemType &e) {
	if (i < 1) return false;

	LNode *p;		/* 指针p指向当前扫描到的结点 */
	int j = 0;		/* 当前p指向的是第几个结点 */
	p = L;			/* L指向头结点，头结点是第0个结点（不存数据） */
	while(p != NULL && j < i - 1) {		/* 循环找到第 i-1 个结点 */
		p = p->next;
		j ++;
	}
	if (p == NULL) return false;		/* i值不合法 */

	if (p->next == NULL) return false;	/* 第 i-1 个结点之后已无其他结点 */

	LNode *q = p->next;			/* 令q指向被删除结点 */
	e = q->data;				/* 用e返回元素的值 */
	p->next = q->next;			/* 将*q结点从链中“断开” */
	free(q);					/* 释放结点的存储空间 */
	return true;				/* 删除成功 */
}

指定结点的删除

/*  指定结点的删除 */
bool DeleteNode(LNode *p) {
	if (p == NULL)
		return false;
	LNode *q = p->next;	/* 令q指向*p的后继结点 */
	p->data = q->data;	/* 和后继结点交换数据域 */
	p->next = q->next;	/* 将*q结点从链中“断开” */
	free(q);			/* 释放后继结点的存储空间 */
	return true;
}

查找 按位查找

/* 按位查找，返回第i个元素（带头结点） */
LNode * GetElem(LinkList L, int i) {
	if (i < 0) return NULL;

	LNode *p;						/* 指针p指向当前扫描到的结点 */
	int j = 0;						/* 当前p指向的是第几个结点 */
	p = L;							/* L指向头结点，头结点是第0个结点（不存数据） */
	while(p != NULL && j < i) {		/* 循环找到第 i 个结点*/
		p = p->next;
		j ++;
	}
	return p;
}

按值查找

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

表的长度

/* 求表的长度(带头结点) */
int Length(LinkList L) {
	int len = 0;
	LNode *p = L;
	while(p->next != NULL) {
		p = p->next;
		len ++;
	}
	return len;
}

单链表的建立 尾插法

/* 尾插法建立单链表(带头结点) */
LinkList List_TailInsert(LinkList &L) {		/* 正向建立单链表 */
	int x;									/* 设ElemType为整形 */
	L = (LinkList)malloc(sizeof(LNode));	/* 建立头结点 */
	LNode *s,*r=L;							/* r为表尾指针 */
	scanf("%d", &x);						/* 输入结点的值 */
	while(x != -1) {						/* 输入-1 表示结束 */
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;		
		r = s;								/* r指向新的表尾结点 */
		scanf("%d", &x);	
	}
	r->next = NULL;							/* 尾结点指针置空 */
	return L;
}

头插法(链表的逆置重要思想)

/* 头插法建立单链表(带头结点) */
LinkList List_HeadInsert(LinkList &L) {		/* 逆向建立单链表 */
	int x;									/* 设ElemType为整形 */
	L = (LinkList)malloc(sizeof(LNode));	/* 建立头结点 */
	L->next = NULL;							/* 初始为空链表 */
	LNode *s;								
	scanf("%d", &x);						/* 输入结点的值 */
	while(x != -1) {						/* 输入-1 表示结束 */
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;						
		L->next = s;						/* 将新结点插入表中，L为头指针 */
		scanf("%d", &x);	
	}
	return L;
}