单链表---结构体实现

定义

链表称为线性表的链式存储，顺序表逻辑上相邻的数据，存储位置也相邻。链表逻辑上相邻的数据，存储位置是随机分布在内存的各个位置上的。

故

对于每一个结点，定义的结构体是：

typedef struct _LinkNode 
{int date;				//数据域，存储数据，这里是int类型的数据struct _LinkNode* next; // 指针域，指向了后继元素（下一个结点）的地址
}LinkNode , LinkList;       //两个别名的作用是一模一样的，只是为了区分头结点和结点

 链表的初始化

我们用一个结构体指针L来指向链表，最开始是带一个头结点的空链表，头结点的数据域一般赋值为-1，也可以存储着链表的长度。头结点的指针域指针第一个元素结点，最开始是没有元素结点的空链表（有头结点），如图：

代码实现

bool initLinkList(LinkList*& L) //参数是对结构体指针的引用
{L = new LinkList; //也可以写成 L = new LinkNode ;if (!L){return false; // 申请内存失败，返回了一个空指针}L->next = NULL;return true;
}

链表的插入

头插法

将新结点插到头结点的后面，有两种形式，一是链表为空，二是链表中已有元素结点，如图

你可以分情况，不过也可以不用，例如：

bool insertLinkList(LinkList*& L, LinkNode *node) //node指向要添加的结点
{if (!L || !node) return false;node->next = L->next; //包含两种情况L->next = node;return true;
}

尾插法

尾插，顾名思义就是在最后一个结点插入之后，也分两种情况，一是链表为空，二是链表中已有元素结点，第一种情况的图和头插法的第一种情况的图一样，就是插入方式不同，以下是第二种情况的图：

我们只需要找到 next 指向 NULL 的这个结点就好了

bool LinkListinsert(LinkList*& L, LinkNode *node)
{if (!L || !node) return false;LinkNode* p = NULL;p = L;while (p->next != NULL) //如果是空链表，p == L，所以是包含两种情况{p = p->next;}node->next = p->next;p->next = node;return true;
}

指定位置插入

在第 i 个结点前插入，那么我们就必须有个临时指针指向第 i-1 个结点

bool InsertLink(LinkList*& L, int i, int e) // 这里也可以用之前的LinkNode *node参数，不过可能i不合法
{if (!L) return false;LinkNode* p = L , *s = NULL ;int j = 0;while (p && j < i - 1) // 指向第 i-1 个结点{	p = p->next;j++;}//如果在第0个位置之前插入(i<1) || 如果在最后一个结点+2的位置之前插入(i>n+1,n为链表长度)---都是非法的if (i < 1 || !p) return false;s = new LinkNode;s->date = e;s->next = p->next;p->next = s;return true;
}

遍历链表（打印链表）

bool PrintLinkList(LinkList *& L)
{if(!L) return false; LinkNode* p = L->next; //首先指向第一个结点，如果为空链表就会指向 NULLwhile (p != NULL) // 直到指向最后一个结点的 next 指针（NULL）{printf("%d ", p->date);p = p->next;}cout << endl;return true;
}

遍历链表，也可以用来求链表的长度，代码与这个类似。

链表的获取

获取链表第 i 个结点的数据域。

bool GetElemLink(LinkList*& L, int i, int &e) //e返回获取的数据域
{LinkNode* p = L;int j = 0;while ( p!=NULL && j < i){p = p->next;j++;}if (p==NULL || i < 1) //i是非法的：i > n（n为链表长度，例如：获取第n+1个结点的数据域）或者是 i < 1（例如：获取了第0个结点的数据域）{return false;}e = p->date;return true;
}

链表的查找

查找我们输入的元素在链表中出现的第一个位置。

bool FindElem(LinkList* L, int e,int &index) // index返回位置
{if (!L || !L->next) return false; //空链表LinkNode* p = L->next; // 现在指向第一个结点int j = 1;  while (p != NULL && p->date != e) {p = p->next;j++;}if (p == NULL)return false;else{index = j;return true;}
}

链表的删除

删除第 i 个结点，i 可能不合法，注意不合法的原因。

bool DeleteLinkNode(LinkList*& L, int i)
{LinkNode* p = NULL , *q = NULL;p = L;int j = 0;while ( p->next!=NULL && j < i - 1){p = p->next;j++;}// 指向第 i-1 个结点if (i < 1 || p->next == NULL) //i非法，删除第0个结点(i<1) 或者是 删除第n+1个结点(i>n,n为链表的长度)return false;else{q = p->next;p->next = q->next ;delete q;return true;}}

链表的销毁（清空）

销毁就是要归还所申请的内存，删除某个结点时，一定要保存下一个结点的地址。简要解释：先保存第一个结点的地址，随后删除头结点（也申请了空间），再保存第二个结点的地址，删除第一个结点，再保存第三个结点……以此类推，可以将全部结点删除。

void DestoryLink(LinkList*& L)
{LinkNode* p = NULL, * q = NULL;p = L;while (p != NULL){	q = p->next;//cout << "删除元素" << p->date << endl;delete p;p = q;}}

总代码

以下是全部代码，链表的函数有不同的实现方法。也许我的代码和别人有些差异，所以可以看看 main 函数中是怎样的。

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>using namespace std;typedef struct _LinkNode
{int date;				//数据域struct _LinkNode* next; // 指针域}LinkNode , LinkList;//初始化链表
bool initLinkList(LinkList*& L)
{L = new LinkList;if (!L){return false;}L->next = NULL;return true;
}//前插法
bool insertLinkList(LinkList*& L, LinkNode *node)
{if (!L || !node) return false;node->next = L->next;L->next = node;return true;
}//尾插法
bool LinkListinsert(LinkList*& L, LinkNode *node)
{if (!L || !node) return false;LinkNode* p = NULL;p = L;while (p->next != NULL){p = p->next;}node->next = p->next;p->next = node;return true;
}//在第i个结点前插入---指定位置插入
bool InsertLink(LinkList*& L, int i, int e)
{if (!L) return false;LinkNode* p = L , *s = NULL ;int j = 0;while (p && j < i - 1){	p = p->next;j++;}//如果在第0个位置之前插入(i<1) || 如果在最后一个结点+2的位置之前插入(i>n+1,n为链表长度)---都是非法的if (i < 1 || !p) return false;s = new LinkNode;s->date = e;s->next = p->next;p->next = s;return true;
}//打印链表
void PrintLinkList(LinkList *& L)
{LinkNode* p = L->next;while (p != NULL){printf("%d ", p->date);p = p->next;}cout << endl;
}//获取第i个结点的数据元素
bool GetElemLink(LinkList*& L, int i, int &e)
{LinkNode* p = L;int j = 0;while ( p!=NULL && j < i){p = p->next;j++;}if (p==NULL || i < 1){return false;}e = p->date;return true;
}//在链表中查找元素,并且用index返回位置
bool FindElem(LinkList* L, int e,int &index)
{if (!L || !L->next) return false;LinkNode* p = L->next;int j = 1;while (p && p->date != e){p = p->next;j++;}if (p == NULL)return false;else{index = j;return true;}
}//删除第i个结点
bool DeleteLinkNode(LinkList*& L, int i)
{LinkNode* p = NULL , *q = NULL;p = L;int j = 0;while ( p->next!=NULL && j < i - 1){p = p->next;j++;}if (i < 1 || p->next == NULL) //删除第0个结点(i<1) 或者是 删除第n+1个结点(i>n,n为链表的长度)return false;else{q = p->next;p->next = q->next ;delete q;return true;}}//清空(销毁)链表
void DestoryLink(LinkList*& L)
{LinkNode* p = NULL, * q = NULL;p = L;while (p != NULL){	q = p->next;//cout << "删除元素" << p->date << endl;delete p;p = q;}}
int main(void)
{LinkList* L = NULL; //指向表头（头结点）的指针LinkNode* e = NULL; //指向结点的指针initLinkList(L);int elem = 0;		//结点的数据元素int i;				//第几个结点int n = 0;			//输入的个数int flag = -1;while (flag != 0){cout << "1.前插链表" << endl<< "2.尾插链表" << endl<< "3.指定位置前插入" << endl<< "4.打印链表" << endl<< "5.获取第i个结点的数据" << endl<< "6.查找元素" << endl<<"7.删除元素"<<endl<< "0.退出(销毁链表)" << endl;cout << "请选择:";cin >> flag;switch (flag){case 1:cout << "请输入前插法插入链表的个数";cin >> n;cout << "请依次输入" << n << "个数:";while (n--){e = new LinkNode;cin >> e->date;insertLinkList(L, e);}break;case 2:cout << "请输入尾插入链表的个数";cin >> n;cout << "请依次输入" << n << "个数:";while (n--){e = new LinkNode;cin >> e->date;LinkListinsert(L, e);}break;case 3:cout << "请输入插入的位置和元素:";cin >> i >> elem;InsertLink(L, i, elem);break;case 4:PrintLinkList(L);break;case 5:cout << "请输入要获取的结点i:";cin >> i;if (GetElemLink(L, i, elem)){cout << "第" << i << "个结点的值为" << elem << endl;}else{cout << "获取元素失败" << endl;}break;case 6:cout << "请输入要查找的元素:";cin >> elem;if (FindElem(L, elem, i)){cout << "找到了,此元素的位置是" << i << endl;}else{cout << "表中无此值" << endl;}break;case 7:cout << "请输入要删除的结点i:";cin >> i;if (DeleteLinkNode(L, i)){cout << "删除成功" << endl;}else{cout << "删除失败" << endl;}break;case 0:DestoryLink(L);break;default:cout << "输入非法! " << endl;break;}}return 0;
}

这里也可以将代码复制，自己调试测试一下，删除某些代码，看看会有什么影响，更能理解。