链表的原理
链表是线性表的链式存储方式, 逻辑上相邻的数据在计算机内的存储位置不一定相邻, 那么如何表示逻辑上的相邻关系呢, 我们可以给每一个元素附加一个指针域, 用来
指向下一个元素的存储位置.
1. 每个节点由指针域跟数据域组成
2. 指针域中存储的指针指向下一个元素的地址
其结构体定义如下:
- typedef struct Node{
- int data;
- Node* next;
- }LinkList,LinkNode;
- //LinkList: 表头 ListNode: 节点
链表的算法实现
链表的初始化
- bool ListInit(LinkList*& L) {
- L = new LinkList;
- if (!L) return false;// 初始化失败
- L->next = NULL;
- L->data = -1;
- return true;
- }
在链表的头部插入数据
- bool addListFront(LinkList* &L,LinkNode* &N) {// 插入的数据在链表前面
- if (!L || !N) {
- cout <<"插入失败!" << endl;
- return false;
- }
- N->next = L->next;
- L->next = N;
- return true;
- }
在链表的尾部插入数据
- bool addListEnd(LinkList*& L, LinkNode*& N) {// 插入在最后面
- if (!L || !N) {
- cout <<"插入失败!" << endl;
- return false;
- }
- LinkList* last = NULL;
- last = L;
- while (last->next) last = last->next;
- last->next = N;
- N->next = NULL;
- return true;
- }
在链表的任意处插入数据, e 作为链表第 index 个元素的数据
- bool insertList(LinkList*& L, int index,int e) {
- if (!L) {
- return false;
- }
- LinkNode* N = new LinkNode;
- N->data = e;
- LinkList* nodeI = L;
- int count = 0;
- while (nodeI->next&&count<index-1) {
- nodeI = nodeI->next;
- count++;
- }
- if (!nodeI||count>index-1) {//!nodeI 时表示 index 的值传入过大, count>=index-1 时表示传入的 index 是非正数
- return false;
- }
- N->next = nodeI->next;
- nodeI->next = N;
- return true;
- }
链表查找第 index 个元素的值, 并存储在 e 里面
- bool listGetElem(LinkList*& L, int index, int& e) {
- if (!L) {
- return false;
- }
- else if (!L->next) {
- return false;
- }
- LinkNode* p = L->next;
- int count = 1;
- while (p&&count<index){
- p = p->next;
- count++;
- }
- if (!p || count> index) {
- return false;
- }
- e = p->data;
- return true;
- }
查找链表 L 里面是否有值为 e 的元素并且将序号返回到 index
- bool listHadElem(LinkList*& L, int e, int& index) {
- if (!L || !L->next) {
- index = 0;
- return false;
- }
- index = 1;
- LinkNode* p = L->next;
- while (p&&p->data!=e) {
- p = p->next;
- index++;
- }
- if (!p) {
- return false;
- }// 没有这个值
- return true;
- }
删除 L 中第 index 个元素
- bool LinkDelete(LinkList*&L,int index){
- if (!L) {
- return false;
- }
- else if (!L->next) {
- //cout <<"链表中没有元素!" << endl;
- return false;
- }
- LinkNode* p = L;
- int count = 0;
- while (p && count < index-1) {
- p = p->next;
- count++;
- }
- if (!p || count> index-1) {
- //cout <<"查找失败!" << endl;
- return false;
- }
- LinkNode* node = p->next;
- if (!node) return false;
- p->next = node->next;
- delete node;
- return true;
- }
干掉整个链表
- bool LinkDestroy(LinkList*& L) {
- if (!L) {
- return false;
- }
- LinkNode* p1 = L;
- while (p1) {
- L=L->next;
- cout <<"删除元素:" << p1->data <<endl;
- delete p1;
- p1 = L;// 最后 L=NULL 了 是因为中间把 L->next 的值赋给了 L
- }
- return true;
- }
遍历 L 中每一个元素的数据
- void printL(LinkList* &L) {
- if (!L|| !L->next) {
- cout <<"链表中不存在元素, 或不存在此链表" << endl;
- return;
- }
- LinkNode* p = L->next;
- while(p) {
- cout <<p->data <<"\t";
- p = p->next;
- }
- }
以上就是我对于单链表的学习内容
链表学习
来源: http://www.bubuko.com/infodetail-3529888.html