链表(链式存储）

• 单链表
• 双链表
• 循环链表
• 静态链表

单链表

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

单链表的实现

typedef <数据类型> <别名>

typedef int zhengshu；
typedef int * zhengshu指针；

数据类型重命名前	数据类型重命名后
int x=1	zhengshu x=1;
int * p；	zhengshuzhizheng p；

用typedef重命名节点，头指针数据类型

typedef struct LNode LNode;
typedef struct LNode* LinkList;

要表示一个单链表时，值需声明一个头指针L,指向单链表的第一个节点。

//声明一个指向头指针的第一个节点的指针   两种方式
LNode *L;    //强调这是一个节点
LinkList L;  //强调这是一个单链表

用代码定义一个单链表

1.不带头节点

• 写代码跟复杂一点
• 头指针L指向的下一个节点实际存放数据的节点
• 空表判断：L == NULL

#include<stdio.h>

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;

//单链表的初始化
bool InitList(LinkList &L){
	L = NULL; //空表，暂时没有任何节点，防止脏数据
	return true;
}

//判断单链表是否为空
bool Empty(LinkList &L){
	if(L == NULL)
		return true;
	else
		return false;
}

int main()
{
    LinkList L;
	InitList(L);
    return 0;
}

带头节点

• 头指针L指向的下一个节点不存放数据，这个节点指向的下一个节点存放数据
• 空表判断：L->next== NULL

#include<stdio.h>
#include <cstdlib>

typedef struct LNode
{
    int data;
    struct LNode *next;
}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){
	if(L->next == NULL)
		return true;
	else
		return false;
}

int main()
{
    LinkList L;
	InitList(L);
	printf("data=\n");

    return 0;
}

用代码实现单链表的插入和删除

带头结点

#include<stdio.h>
#include <cstdlib>

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;

//单链表的初始化(带头节点）
bool InitList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode)); //分配一个头节点
	if(L == NULL) //内存不足，分配失败
		return false;
	L->next = NULL;   //头结点之后暂时没有节点
	return true;
}

//第i个位置插入元素e
bool ListInsert(LinkList &L,int i,int e){
	if(i<1)
		return false;
	LNode *p;
	int j=0;
	p=L;
	while(p!=NULL && j<i-1){
		p=p->next;
		j++;
	}
	if(p=NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

//判断单链表是否为空
bool Empty(LinkList &L){
	if(L->next == NULL)
		return true;
	else
		return false;
}

int main()
{
    LinkList L;
	InitList(L);
	printf("data=\n");

    return 0;
}

不带头结点插入

//第i个位置插入元素e
bool ListInsert(LinkList &L,int i,int e){
	if(i<1)
		return false;
	if(i==1){
		LNode *s = (LNode *)malloc(sizeof(LNode));
 	    s->data=e;
	    s->next=L;
		L=s;
		return true;
	}
	if(i<1)
		return false;
	LNode *p;
	int j=1;
	p=L;
	while(p!=NULL && j<i-1){
		p=p->next;
		j++;
	}
	if(p=NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

带头结点

• 删除节点并返回值

#include<stdio.h>
#include <cstdlib>

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;

//单链表的初始化(带头节点）
bool InitList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode)); //分配一个头节点
	if(L == NULL) //内存不足，分配失败
		return false;
	L->next = NULL;   //头结点之后暂时没有节点
	return true;
}

//第i个位置插入元素e
bool ListInsert(LinkList &L,int i,int e){
	if(i<1)
		return false;
	LNode *p;
	int j=0;
	p=L;
	while(p!=NULL && j<i-1){
		p=p->next;
		j++;
	}
	if(p=NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}
//后插操作，在p节点之后插入元素
bool InserNextNode(LNode *p,int e){
	if(p==NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s==NULL)
		return false;
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}
    
//指定节点的前插操作,把p的数据拷贝到s，然后把新插入的数据写到p
bool InsertPriorNode(LNode *p,int 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->data=p->data;
	p->data=e;
	return true;
}

bool ListDelete(LinkList &L,int i,int &e){
	if(i<i)
		return false;
	LNode *p;
	int j=0;
	p=L;
	while(p!=NULL && j<j-1){
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	if(p->next == NULL)
		return false;
	LNode *q=p->next;
	e=q->data;
	p->next=q->next;
	free(q);
	return true;
}


//判断单链表是否为空
bool Empty(LinkList &L){
	if(L->next == NULL)
		return true;
	else
		return false;
}

int main()
{
    LinkList L;
	InitList(L); 
	printf("data=\n");

    return 0;
}