数据结构（2）—单链表（带头结点和不带头结点）

一、定义说明：

��       单链表是通过一组任意的存储单元来存储线性表中的数据元素。每个结点都有data数据域（用来存放数据元素）和next指针域（用来存放后继节点的地址）。

（）

        对于顺序表，单链表可以解决顺序表需要一整个大量的连续的存储单元的缺点，单链表的元素可以离散地分布在存储空间中，即非随机存取的存储结构，不能直接找到表中某个特定的结点，当查找某个特定的结点时，需要从表头开始一个一个遍历。因为单链表附加了指针域，缺点就是存储空间增大。

        单链表有带头结点和不带头结点两种类型。引入头结点的好处：①便于第一个结点的处理：增加头结点后，第一个结点的地址保存在头结点的指针域中，则对链表的第一个元素的操作和其他元素相同，无需进行特殊处理。（若单链表不带头结点，则第一个结点无前驱结点，在其前插入结点和删除该结点操作复杂些。）②便于空表和非空表的统一处理：增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。

（）

二、带头结点的程序说明

2.1 单链表的存储结构

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

2.2 初始化

bool Initlist(LinkList &L){//L = (LinkList)malloc(sizeof(LNode)); //c语言定义头结点L = new LNode; //定义头结点L->next = NULL; //尾指针为空，头结点指向空return true;}

2.3 头插法建立单链表

void List_HeadInsert(LinkList& L){int n;  //输入元素的个数cout  n;LinkList s;  //定义指针变量scout  s->data;s->next = L->next;L->next = s;}}

2.4 尾插法建立单链表

void List_TailInsert(LinkList& L){int n; //输入元素的个数cout  n;LinkList r; //定义一个表尾指针r = L;LinkList s;//定义指针变量scout  s->data;s -> next = NULL;r->next = s;r = s;}}

2.5 打印链表

void Print_list(LinkList& L){LinkList s;s = L->next;while(s){cout data next;}cout next;while (s){length++;s = s->next;}return length;}

2.7 按位置序号查找结点

LNode* GetElem(LinkList& L, int i){if (iLength_list(L))return NULL;int j = 1;LNode* p = L->next; //链表第一个结点赋给p，L是头结点while (p != NULL && j next;j++;}return p; //返回第i个结点的指针，"p != NULL"其实是在和表长对比，但我这里其实不需要}

2.8 按值查找位置信息

int LocateElem(LinkList& L, Elemtype e){LNode* p = L->next; //第一个结点赋给p;int j = 1;while (p != NULL && p->data != e){p = p->next;j++;}return j;}

2.9在第i个结点之后插入新的结点

bool ListInsert(LinkList& L, int i, Elemtype e){if (iLength_list(L) + 1)return false; //判断i的合法性if (i == 1)//这样就能在第1个位置插入结点了{LinkList p;p = new LNode; //创建想要插入的结点信息p->next = L->next;p->data = e;L->next = p;}else{LinkList s;s = GetElem(L, i - 1); //查找到第i-1个结点,是查不到第1个位置的LinkList p;p = new LNode; //创建想要插入的结点信息p->next = s->next;p->data = e;s->next = p;}return true;}

2.10 删除第i个位置的结点

bool ListDelete(LinkList& L, int i){if (iLength_list(L))return false;if (i == 1){LNode* p = L->next;//第一个结点赋给p;L->next = p->next;free(p);}else{LinkList s;s = GetElem(L, i - 1);//查找到第i-1个结点,是查不到第1个位置的LinkList p; //被删除的结点p = s->next;s->next = p->next;free(p);}return true;}

2.11单链表的逆置

bool ListReverse(LinkList& L){if (!L->next)return false; //空链表不需要逆置LinkList r, p, q; //r代表前驱节点，p当前节点，q后继节点r = NULL;p = L->next;q = p->next;  //从单链表的第一个节点开始，沿着链表滑动，直到最后一个节点，逐一反转while (p){p->next = r;r = p;p = q;if (q) //保证指向后继节点的指针q不会移出表尾q = q->next;}L->next = r; //当从循环出来时说明p为空，则r就是最后一个节点，此时把最后一个节点作为首节点}

2.12 两个链表的合并

//（11）两个链表的合并,把B有顺序地插入A中(假设A是有顺序的)void CombineList(LinkList& A, LinkList& B){LinkList q, p, r;q = A; //q指向A的头指针p = B->next; //p指向B的第一个结点while (p){while ((q->next) && (q->next->data data)){q = q->next;} //找到现在的p应该插入到哪的位置r = p;p = p->next;r->next = q->next;q->next = r;}}

2.13 main函数

#include#include"stdlib.h"using namespace std;#define Elemtype intint main(){LinkList L;//(1)初始化链表，形成带有"头节点"的空链表Initlist(L);//(2)使用头插法建立链表List_HeadInsert(L);Print_list(L);//(3)使用尾插法建立链表List_TailInsert(L);Print_list(L);//(4)按照序号进行查找int n1;cout  n1;LinkList p;p = GetElem(L, n1);cout data next = L;L = s;//更新头指针}}

3.4 尾插法建立单链表

void TailInsert(LinkList& L){int n;cout  n;cout  s->data;s->next = L;L = s; //更新头指针Lr = s; //更新尾指针r}else{s = new LNode;cin >> s->data;s->next = r->next;r->next = s;r = s;}}}

3.5 打印链表

void PrintList(LinkList& L){LinkList s;s = L;while (s){cout data next;}cout next;}return length;}

3.7 按位置序号查找结点

LNode* GetElem(LinkList& L, int i){if (iLength_list(L))return NULL;int j = 1;LNode* p = L; //链表第一个结点赋给pwhile (p != NULL && j next;j++;}return p; //返回第i个结点的指针，"p != NULL"其实是在和表长对比，但我这里其实不需要}

3.8 按值查找位置信息

int LocateElem(LinkList& L, Elemtype e){LNode* p = L; //第一个结点赋给p;int j = 1;while (p != NULL && p->data != e){p = p->next;j++;}return j;}

3.9在i位置插入新的结点（方法一）

//（8）在第i个位置插入结点(后插法)bool ListInsert(LinkList& L, int i, Elemtype e){if (iLength_list(L) + 1)return false; //判断i的合法性if (i == 1)//这样就能在第1个位置插入结点了{LinkList p;p = new LNode; //创建想要插入的结点信息p->next = L;p->data = e;L = p; //更新头指针}else//不是在第1个位置插入结点{LinkList s;s = GetElem(L, i - 1); //查找到第i-1个结点LinkList p;p = new LNode; //创建想要插入的结点信息p->next = s->next;p->data = e;s->next = p;}return true;}

3.10 在i位置插入新的结点（方法二）

//（9）在第i个位置插入结点(前插法)bool List_HeadInsert(LinkList& L, int i, Elemtype e){if (iLength_list(L) + 1)return false; //判断i的合法性LinkList s;s = GetElem(L, i); //查找到第i个结点LinkList p;p = new LNode;p->next = s->next;p->data = s->data;//定义一个结点p，复制原本i结点的全部信息s->next = p;s->data = e;//再把原本i结点变成插入的新结点的信息return true;}

3.11 删除第i个位置的结点　

bool ListDelete(LinkList& L, int i){if (iLength_list(L))return false;if (i == 1){LNode* p = L;//第一个结点赋给p;L = p->next; //更新头指针free(p);}else{LinkList s;s = GetElem(L, i - 1);//查找到第i-1个结点,是查不到第1个位置的LinkList p; //被删除的结点p = s->next;s->next = p->next;free(p);}return true;}

3.13 main函数

#includeusing namespace std;#include"stdlib.h"#define Elemtype intint main(){LinkList L;InitList(L);//（1）使用头插法创建链表//HeadInsert(L);//PrintList(L);//(2)使用尾插法创建链表TailInsert(L);PrintList(L);//(3)按照位置序号进行查找//int n1;//cout  n1;//LinkList p;//p = GetElem(L, n1);//cout data