定义
链表称为线性表的链式存储,顺序表逻辑上相邻的数据,存储位置也相邻。链表逻辑上相邻的数据,存储位置是随机分布在内存的各个位置上的。
故
对于每一个结点,定义的结构体是:
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;
}
这里也可以将代码复制,自己调试测试一下,删除某些代码,看看会有什么影响,更能理解。