[408] [数据结构] 链表-代码基础
1.单链表的定义
typedef struct LNode{ //定义单链表结点类型 ElemType data; //数据域 struct LNode *next; //指针域 }LNode, *LinkList;单链表是一种非随机存取的存储结构。
当头指针为NULL时，表示链表为空。
在带头结点的单链表中，头指针L指向头结点，而头结点的next指向第一个数据节点。
在不带头结点的单链表中，头指针L直接指向第一个数据结点。
2.单链表上基本操作的实现
2.1 单链表的初始化
bool InitList(LinkList &L){ //带头结点的单链表初始化 L=(LNode*)malloc(sizeof(LNode)); //创建头结点 L->next=NULL; //头节点之后暂无数据结点 return true; }不带头结点的单链表初始化时，只需将头指针L初始化为NULL。
bool InitList(LinkList &L){ //不带头结点的单链表初始化 L=NULL; return true; }2.2 求表长操作
求表长是指统计单链表中数据结点的个数（不包括头结点）
int Length(LinkList L){ int len=0; //计数变量，初始为0 LNode *p=L; while(p->next!=NULL){ p=p->next; len++; //每访问一个结点，计数加1 } return len; }求表长操作的时间复杂度为O(n)O(n)O(n)。
2.3 按序号查找结点
LNode *GetElem(LinkList L, int i){ LNode *p=L; //指针p指向当前扫描结点。 int j=0; //j记录当前位序，头结点为第0个结点。 while(p!=NULL&&j<i){ //循环找到第i个结点 p=p->next; j++; } return p; //返回第i个节点的指针或NULL }按序号查找操作的时间复杂度为O(n)O(n)O(n)。
2.4 按值查找表结点
LNode *LocateElem(LinkList L, elemtype e){ LNode *p=L->next; while(p!=NULL&&p->data!=e) //从第一个结点开始擦汗中阿数据域为e的节点 p=p->next; return p; //找到后返回该结点指针，否则返回NULL }按值查找操作的时间复杂度为O(n)O(n)O(n)。
2.5 插入结点操作
bool ListInsert(LinkList &L, int i, Elemtype e){ LNode *p=L; //p指向当前扫描结点 int j=0; //j记录当前位序，头结点为第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; //(1) p->next=s; //(2) return true; }时间复杂度为O(n)O(n)O(n)。
(1)和(2)的顺序不可颠倒。
扩展：对某个节点进行前插操作。
前插操作是指在某结点前插入一个新结点，与后插操作相反。
主要代码片段如下：
s->next=p->next; //修改指针域，不能颠倒 p=>next=s; temp=p->data; //交换数据域部分 p->data=s->data; s->data=temp;时间复杂度为O(n)O(n)O(n)。
2.6 删除结点操作
bool ListDelete(LinkList &L, int i, ElemType &e){ LNode *p=L; //指针p指向当前扫描到的结点 int j=0; //记录当前结点的位序，头结点是第0个结点 while(p->next!=NULL&&j<i-1){ //循环找到第i-1个结点 p=p->next; j++; } if(p->next==NULL||j>i-1) //i值不合法 return false; LNode *q=p->next; //令q指向被删除结点 e=q->data; //用e返回元素的值 p->next=q->next; //将*q节点从链中“断开” free(q); //释放节点的存储空间 return true; }时间复杂度为O(n)O(n)O(n)。
扩展：删除给定结点*p。
主要代码片段：
LNode *q=p->next; //令q指向*p的后继结点 p->data=p->next->data; //用后继结点的数据域覆盖 p->next=q->next; //将*q节点从链中“断开” free(q); //释放后继结点的存储空间时间复杂度为O(n)O(n)O(n)。
2.7 采用头插法建立单链表
LinkList List_HeadInsert(LinkList &L){ //逆向建立单链表 LNode *s; int x; //设元素类型为整数 L=(LNode*)malloc(sizeof(LNode)); //创建头结点 L->next=NULL; //初始为空链表 scanf("%d", &x); //输入结点的值 while(x1=9999){ //输入9999表示结束 s=(LNode*)malloc(sizeof(LNode)); //创建新结点 s->data=x; s->next=L->next; L->next=s; //将新结点插入表中，L为头结点 scanf("%d", &x); } return L; }每插入一个结点的时间复杂度为O(1)O(1)O(1)，总时间复杂度为O(n)O(n)O(n)。
2.8 采用尾插法建立单链表
LinkList List_TailInsert(LinkList &L){ //正向建立单链表 int x; //设元素类型为整数 L-(LNode*)malloc(sizeof(LNode)); //创建头结点 LNode *s, *r=L; //r为表尾指针 scanf("%d", &x); //输入结点的值 while(x!=9999){ //输入9999表示结束 s=(LNode*)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; //r指向新的表尾结点 scanf("%d", &x); } r->next=NULL; //尾节点置空 return L; }因为附设了一个尾指针，故无须遍历查找尾部，总时间复杂度为O(n)O(n)O(n)。
3.双链表
3.1 双链表的定义
typedef struct DNode{ //定义双链表结点类型 ElemType data; //数据域 struct DNode *prior,*next; //前驱和后继指针 }DNode, *Dlinklist;3.2 双链表的插入操作
核心代码片段如下：
s->next=p->next; p->next->prior=s; s->prior=p; p->next=s;3.3 双链表的删除操作
p->next=q-next; q->next->prior=p; free(q);4.静态链表
定义：
#define MaxSize 50 //静态链表的最大长度 typedef struct{ //静态链表的结构类型定义 ElemType data; //存储数据元素 int next; //下一个元素的数组下标 } SLinkList[MaxSize];