数据结构与算法--顺序表--单链表

一 顺序表

• 需要指向存储位置的基地址
• 分配一段连续的内存
• 用length记录实际的元素的个数，也即顺序表的长度，因为顺序表是允许删除和插入元素的
• 不需要定义数组

1.1 普通结构体数组实现版本，实现白色的点以一定的步长移除画面，大量for循环，并且由于数组内部数据需要去除的点并不是连续的，就需要每次从0遍历到数组的结尾，但是实际上，已经消失的点可以不用再进行循环和判断

#include <iostream>
#include <exception>
#include <stdexcept>
#include "string"
#include <fstream>
#include<conio.h>
#include<Windows.h>
#include <graphics.h>#define SCREEN_WIDTH 654
#define SCREEN_HEIGHT 480
#define STAR_MAX_NUM 100
#define MAX_STEP 2
#define MAX_STAR_RADIUS 3
#define BOTTOM_MARGIN 100
#define IMG_SIZE 50enum STATUS {STOP=0,UP,DOWN,LEFT,RIGHT,RANDON
};struct STAR {int x;int y;unsigned radius;int step;  //每次走的间隔int color;bool alive;enum STATUS stat;
}star[STAR_MAX_NUM];void initStar(int i) {//初始化星星star[i].x = rand() % SCREEN_WIDTH;star[i].y = rand() % (SCREEN_HEIGHT - IMG_SIZE);star[i].step = rand() % MAX_STEP + 1;int rgb = 0;rgb = rand() % 255;star[i].color = RGB(rgb, rgb, rgb);star[i].radius = rand() % MAX_STAR_RADIUS;setfillcolor(star[i].color);solidcircle(star[i].x, star[i].y, star[i].radius);star[i].alive = true;
}void eraseStar(int i) {for (int i = 0; i < STAR_MAX_NUM; i++) {//擦除原来的星星setfillcolor(BLACK);solidcircle(star[i].x, star[i].y, star[i].radius);if (star[i].alive && (star[i].y - star[i].step) >0) {star[i].y = star[i].y - star[i].step;setfillcolor(star[i].color);solidcircle(star[i].x, star[i].y, star[i].radius);}else {star[i].alive = false;}}
}//判断画面里面还有没有星星
bool hasStar() {for (int i = 0; i < STAR_MAX_NUM; i++) {if (star[i].alive == true) {return true;break;}}return false;
}int main() {initgraph(SCREEN_WIDTH, SCREEN_HEIGHT);IMAGE bg_img;loadimage(&bg_img, _T("y3.png"), IMG_SIZE, IMG_SIZE, true);putimage(int(SCREEN_WIDTH * 0.3), SCREEN_HEIGHT - IMG_SIZE, &bg_img);putimage(int(SCREEN_WIDTH * 0.7), SCREEN_HEIGHT - IMG_SIZE, &bg_img);//绘制星星for (int i = 0; i < STAR_MAX_NUM; i++) {initStar(i);}//消除星星,并不是直接擦除，是以一定的步长走出画面的int i = 0;while(hasStar()) {for (int i = 0; i < STAR_MAX_NUM; i++) {eraseStar(i);}Sleep(100);}system("pause");return 0;
}

1.2 顺序表实现

• 插入元素，插入位置不能小于0，也不能大于当前数组长度；还需要判断数组是不是满了，如果满了就不能再插入；从最后一个元素开移动
• 添加元素：判断空间有没有满即可

定义顺序：

• （1) 定义一个结构体，包含顺序表的首地址，内存大小，以及实际元素个数

typedef struct _OrderList Olist;   //定义结构体的别名
struct _OrderList {int* firstElement;  //顺序表的首地址int elemNum;        //档期那表里的元素int size;            //顺序表分配的空间，也就是连续内存的大小
};

• (2)为结构体分配内存空间

1.2.1 结构体别名问题 ，定义结构体的别名，可能有时候名字太长了typedef

typedef struct _OrderList Olist;   //定义结构体的别名，可能有时候名字太长了struct _OrderList {int* firstElement;  //顺序表的首地址int elemNum;        //档期那表里的元素int size;            //顺序表分配的空间，也就是连续内存的大小
};

typedef  struct {int* firstElement;  //顺序表的首地址int elemNum;        //档期那表里的元素int size;            //顺序表分配的空间，也就是连续内存的大小
}Olist;

1.2.2 顺序表可以直接list.elems[i]来访问数组，数组名本质上是指向数组第一个元素的指针。因此，elems 作为 int* 类型，可以像数组一样使用下标操作符 [] 来访问元素。类似于函数形参，void print(int *array) 和 void print(int array[])一样

elems[i] 等价于 *(elems + i)，即通过指针算术运算访问第 i 个元素的值

void listPrint(Olist& list) {cout << "顺序表元素个数" << list.elemNum << ", 顺序表空间:" << list.size << endl;for (int i = 0; i < list.elemNum; i++) {cout << list.elems[i] << " ";}cout << endl;
}

1.2.3 连续输入数据 cout << "\n请输入要插入的位置和元素:"; cin >> pos >> e;

#include <iostream>
#include <exception>
#include <stdexcept>
#include "string"
#include <fstream>
#include<conio.h>
#include<Windows.h>
#include <graphics.h>using namespace std;
#define MAX_SIZE 20typedef struct _OrderList Olist;   //定义结构体的别名
struct _OrderList {int* elems;  //顺序表的首地址int elemNum;           //表里的元素个数int size;            //顺序表分配的空间，也就是连续内存的大小
};void listPrint(Olist& list) {cout << "\n顺序表元素个数" << list.elemNum << ", 顺序表空间:" << list.size << endl;for (int i = 0; i < list.elemNum; i++) {cout << list.elems[i] << " ";}cout << endl;
}bool  init(Olist& list) {//初始是没有元素的，为首地址元素分配空间其实就是为顺序表分配空间list.elems = new int[MAX_SIZE];if (!list.elems) {return false;}list.elemNum = 0;list.size = MAX_SIZE;return true;
}bool appendList(Olist& list, int ele) {if (list.elemNum == list.size) {cout << "顺序表已经满了，不能再插入" << endl;return false;}list.elems[list.elemNum] = ele;   //能这样做是因为地址是连续的list.elemNum++;return true;
}bool insertList(Olist& list, int position, int ele) {if (list.elemNum == list.size) {cout << "顺序表已经满了，不能再插入" << endl;return false;}if (position < 0 || position >= list.elemNum) {cout << "插入位置不合法" << endl;return false;}for (int i = list.elemNum - 1; i >= position; i--) {list.elems[i + 1] = list.elems[i];}list.elems[position] = ele;list.elemNum++;return true;
}bool deleteList(Olist& list, int position)
{if (list.elemNum == 0 || position < 0 || position >= list.elemNum) {cout << "删除位置不合法" << endl;return false;}list.elems[position] = -1;for (int i = position; i < list.elemNum-1; i++) {list.elems[i] = list.elems[i+1];}list.elemNum--;return true;
}void destroyList(Olist& list) {if (list.elems) delete[] list.elems;list.size = 0;list.elemNum = 0;
}int main() {Olist list;///cout << "初始化顺序表" << endl;if (!init(list)) {cout << "顺序表内存分配失败" << endl;return 0;}listPrint(list);///int count = 0;int e;cout << "请输入要添加的元素个数:";cin >> count;for (int i = 0; i < count; i++) {cout << "\n请输入要添加的元素:";cin >> e;appendList(list,e);}listPrint(list);/int pos;cout << "\n请输入要插入的位置和元素:";cin >> pos >> e;	if (insertList(list, pos, e)){cout << "插入成功" << endl;}else {cout << "插入失败" << endl;}listPrint(list);///cout << "\n请输入要删除的位置";cin >> pos;if (deleteList(list, pos)){cout << "删除成功" << endl;}else {cout << "删除失败" << endl;}listPrint(list);destroyList(list);return 0;
}

1.3 顺序表优化星星消除。什么时候使用顺序表：频繁的遍历所有元素。顺序表存储数据都是相邻的。

知识点1：防止头文件重复包含

#ifndef _SATR_H_
#define _SATR_H_。。。。
#endif

知识点2：顺序表的数据类型可以任意定义，顺序表本质是一个结构体，给的是一个结构体首地址，然后初始化的时候分配内存空间。而当前案例里面，星星本身也是一个结构体，因此顺序表里面的数据类型变成了结构体，Olist starList; //初始化一个顺序表，对应是首地址，存放第一颗星星，struct STAR star;创建的只是一颗星星，当前案例是在starList顺序表里面存放多颗星星，所以传入数据void eraseStar(Olist& list, int i)是顺序表时，访问顺序表里面的每一颗星星，需要先通过顺序表访问每一个对象，再访问对象本身的属性list.elems[i].alive

//定义顺序表，存储多个星星
typedef struct _OrderList Olist;   //定义结构体的别名
struct _OrderList {struct STAR* elems;  //顺序表的首地址int elemNum;           //表里的元素个数int size;            //顺序表分配的空间，也就是连续内存的大小
};

知识点3：删除顺序表里面的元素的的时候，是在void eraseStar(Olist& list, int i)函数里面调用了deleteList(list,i);进行元素的删除，而 不是 直接在主函数里面做如下操作，因为每一次消除星星,并不是直接擦除，是以一定的步长走出画面的，如果做如下操作，逻辑不对，走出画面的星星才擦除，而不是直接擦除

	int i = 0;while(starList.elemNum) {for (int i = 0; i < starList.elemNum; i++) {eraseStar(starList,i);deleteList(list,i);}Sleep(200);}

code

• star.h

#pragma once
#ifndef _SATR_H_
#define _SATR_H_#define SCREEN_WIDTH 654
#define SCREEN_HEIGHT 480
#define STAR_MAX_NUM 100
#define MAX_STEP 2
#define MAX_STAR_RADIUS 3
#define BOTTOM_MARGIN 100
#define IMG_SIZE 50enum STATUS {STOP = 0,UP,DOWN,LEFT,RIGHT,RANDON
};//定义星星结构体对象，描述一颗星星
struct STAR {int x;int y;unsigned radius;int step;  //每次走的间隔int color;bool alive;enum STATUS stat;
};//定义顺序表，存储多个星星
typedef struct _OrderList Olist;   //定义结构体的别名
struct _OrderList {struct STAR* elems;  //顺序表的首地址int elemNum;           //表里的元素个数int size;            //顺序表分配的空间，也就是连续内存的大小
};void listPrint(Olist& list);
bool  init(Olist& list);
bool appendList(Olist& list, struct STAR ele);
bool deleteList(Olist& list, int position);
void destroyList(Olist& list);
#endif

• star.cpp

#include "star.h"
#include <iostream>using namespace std;void listPrint(Olist& list) {cout << "\n顺序表元素个数" << list.elemNum << ", 顺序表空间:" << list.size << endl;
}bool  init(Olist& list) {//初始是没有元素的，为首地址元素分配空间其实就是为顺序表分配空间list.elems = new struct STAR[STAR_MAX_NUM];if (!list.elems) {return false;}list.elemNum = 0;list.size = STAR_MAX_NUM;return true;
}bool appendList(Olist& list, struct STAR ele) {if (list.elemNum == list.size) {cout << "顺序表已经满了，不能再插入" << endl;return false;}list.elems[list.elemNum] = ele;   //能这样做是因为地址是连续的list.elemNum++;return true;
}bool deleteList(Olist& list, int position)
{if (list.elemNum == 0 || position < 0 || position >= list.elemNum) {cout << "删除位置不合法" << endl;return false;}for (int i = position; i < list.elemNum - 1; i++) {list.elems[i] = list.elems[i + 1];}list.elemNum--;return true;
}void destroyList(Olist& list) {if (list.elems) delete[] list.elems;list.size = 0;list.elemNum = 0;
}

• mian

#include <iostream>
#include <exception>
#include <stdexcept>
#include "string"
#include <fstream>
#include<conio.h>
#include<Windows.h>
#include <graphics.h>
#include "star.h"void initStar(struct STAR &star) {//初始化星星star.x = rand() % SCREEN_WIDTH;star.y = rand() % (SCREEN_HEIGHT - IMG_SIZE);star.step = rand() % MAX_STEP + 1;int rgb = 0;rgb = rand() % 255;star.color = RGB(rgb, rgb, rgb);star.radius = rand() % MAX_STAR_RADIUS;setfillcolor(star.color);solidcircle(star.x, star.y, star.radius);star.alive = true;
}void eraseStar(Olist& list, int i) {for (int i = 0; i < list.elemNum; i++) {//擦除原来的星星setfillcolor(BLACK);solidcircle(list.elems[i].x, list.elems[i].y, list.elems[i].radius);if (list.elems[i].alive && (list.elems[i].y - list.elems[i].step) > 0) {list.elems[i].y = list.elems[i].y - list.elems[i].step;setfillcolor(list.elems[i].color);solidcircle(list.elems[i].x, list.elems[i].y, list.elems[i].radius);}else {list.elems[i].alive = false;deleteList(list,i);}}
}int main() {initgraph(SCREEN_WIDTH, SCREEN_HEIGHT);IMAGE bg_img;loadimage(&bg_img, _T("y3.png"), IMG_SIZE, IMG_SIZE, true);putimage(int(SCREEN_WIDTH * 0.3), SCREEN_HEIGHT - IMG_SIZE, &bg_img);putimage(int(SCREEN_WIDTH * 0.7), SCREEN_HEIGHT - IMG_SIZE, &bg_img);Olist starList;  //初始化一个顺序表，对应是首地址，存放第一颗星星struct STAR star;init(starList);//绘制星星for (int i = 0; i < STAR_MAX_NUM; i++) {initStar(star);appendList(starList, star);}//消除星星,并不是直接擦除，是以一定的步长走出画面的int i = 0;while(starList.elemNum) {for (int i = 0; i < starList.elemNum; i++) {eraseStar(starList,i);}Sleep(200);}system("pause");return 0;
}

1.4 企业应用案例：顺序表管理并剔除超时连接。

• connect.h

#pragma once
#ifndef _CONNECT_H_
#define _CONNECT_H_#define SCREEN_WIDTH 654
#define SCREEN_HEIGHT 480
#define STAR_MAX_NUM 10
#define MAX_STEP 2
#define MAX_STAR_RADIUS 3
#define BOTTOM_MARGIN 100
#define IMG_SIZE 50struct ConnectOut {int fd;  unsigned int timeout;
};//定义顺序表，存储多个超时连接
typedef struct _OrderList Olist;   //定义结构体的别名
struct _OrderList {struct ConnectOut* elems;  //顺序表的首地址int elemNum;           //表里的元素个数int size;            //顺序表分配的空间，也就是连续内存的大小
};void listPrint(Olist& list);
bool  init(Olist& list);
bool appendList(Olist& list, struct ConnectOut ele);
bool deleteList(Olist& list, int position);
void destroyList(Olist& list);
#endif

• connect.cpp

#include "connect.h"
#include <iostream>using namespace std;void listPrint(Olist& list) {cout << "\n顺序表元素个数" << list.elemNum << ", 顺序表空间:" << list.size << endl;for (int i = 0; i < list.elemNum; i++) {cout << "[" << list.elems[i].fd << "] = " << list.elems[i].timeout << endl;}
}bool  init(Olist& list) {//初始是没有元素的，为首地址元素分配空间其实就是为顺序表分配空间list.elems = new struct ConnectOut[STAR_MAX_NUM];if (!list.elems) {return false;}list.elemNum = 0;list.size = STAR_MAX_NUM;return true;
}bool appendList(Olist& list, struct ConnectOut ele) {if (list.elemNum == list.size) {cout << "顺序表已经满了，不能再插入" << endl;return false;}list.elems[list.elemNum] = ele;   //能这样做是因为地址是连续的list.elemNum++;return true;
}bool deleteList(Olist& list, int position)
{if (list.elemNum == 0 || position < 0 || position >= list.elemNum) {cout << "删除位置不合法" << endl;return false;}for (int i = position; i < list.elemNum - 1; i++) {list.elems[i] = list.elems[i + 1];}list.elemNum--;return true;
}void destroyList(Olist& list) {if (list.elems) delete[] list.elems;list.size = 0;list.elemNum = 0;
}

#include <iostream>
#include <exception>
#include <stdexcept>
#include "string"
#include <fstream>
#include<conio.h>
#include<Windows.h>
#include <graphics.h>
#include "connect.h"
#include <time.h>using namespace std;
void checkConnectOut(Olist &list, time_t now);int main() {time_t now, end, last_timeout;time(&now);end = now + 60;last_timeout = now;Olist list;struct ConnectOut ConOut;init(list);//随机模拟超时for (int i = 0; i < 10; i++) {ConOut.fd = i;ConOut.timeout = now + 5 + 2 * i;appendList(list, ConOut);}listPrint(list);do{//cout << "last_timeout = " << last_timeout << ", now =  " << now << endl;//每隔一秒检查一次是否有超时,说明上一次到现在已经过去1秒了if (last_timeout + 0.999 < now) {checkConnectOut(list, now);last_timeout = now;}time(&now);} while (now < end); //检查指定时间内的超时连接destroyList(list);Sleep(10);system("pause");return 0;
}void checkConnectOut(Olist& list, time_t now) {cout << "超时检查。。。。。\n";for (int i = 0; i < list.elemNum; i++) {if (list.elems[i].timeout > now) {continue; // 直接进入下一次循环}cout << "[" << list.elems[i].fd << "] 超时，已关闭..." << endl;deleteList(list, i);i--;}
}

二 单链表：可以让删除和插入元素时，尽可能地移动较少的数据

• 顺序表存在的问题：如果数据太多，删除或移动靠前的数据，后面的所有的数据都需要移动
• LinkList用于表示首节点，LinkNode用于表示其余的节点
• 链表的核心理解：每个节点本身就占据一个地址，同时地址内存存了下一个节点的地址
  
  
• 单链表头节点一般不存数据，指针指向下一个元素，尾节点指针为NULL，链表只能通过上一个节点才能知道下一个节点，不像顺序表，顺序表可以根据索引直接推断出元素位置
  

2.1 头插法和尾插法，头插法，先进入的存在最后面，尾插入法，先进入的存在最里面

2.1.1 为什么传递链表的时候，传递的是LinkList*&，传递指针本身已经能修改内容了：主要是为了在函数内部能够 修改指针本身的值list = new LinkList;，而不仅仅是修改指针指向的内容。其他插入打印等函数可以只使用指针而不使用指针的引用

void init(LinkList* &list) {	list = new LinkList;if (!list){cout << "初始化内存分配失败" << endl;return;}list->data = -1;list->next = NULL;
}```3
1```bash
void init(LinkList* list) {list = new LinkList;   修改的是局部副本，外部指针不变list->next = nullptr;
}int main() {LinkList* myList = nullptr;init(myList);   myList 仍然是 nullptr，没有被初始化！// ...
}

2.1.2 主函数里面，LinkList* list = NULL;只是初始化头节点为空指针，在插入的时候，没插入一个数据，都需要node = new LinkNode;分配新的内存空间来存放数据

int main() {LinkList* list = NULL;LinkNode* node = NULL;init(list);int num;int number;cout << "请输入要插入的数据个数:";cin >> num;cout << " ------------ 头插法---------" << endl;for (int i = 0; i < num; i++) {node = new LinkNode;cout << "请输入第" << i+1 << "个元素:";cin >> node->data;insert_head(list, node);}printList(list);

2.2 任意位置插入元素

//p = list->next;  1 3 5 ,在第2个位置插入4 ，将会变成1 3 4 5p = list;   1 3 5 ,在第2个位置插入4 ，将会变成1 4 3 5

bool insert(LinkList*& list, LinkNode* node, int pos) {LinkNode* p = NULL;//p = list->next;p = list;int counter = 0;//循环遍历找到pos位置的节点while (p && counter < pos-1) {p = p->next;counter++;};//索引超出有效范围if (!p || counter > pos - 1) {cout << "插入位置超出有效范围" << endl;return false;}node->next = p->next;p->next = node;return true;
}

2.3 获取指定位置的元素

2.3.1 为什么下列调用，只有在函数里面能正确打印node的值，在主函数里面无法正确打印，而其他函数形参也是LinkNode* node，却能实现数据插入链表bool insert(LinkList*& list, LinkNode* node, int pos)。和前面的原因一样，因为bool getElem(LinkList*& list, int pos, LinkNode* node)函数在函数内部对指针本身进行了修改， node = p->next;，而insert函数内部只是修改 node->next = p->next; p->next = node;指针指向的值，而没有修改指针本身，要修改指针本身，就需要传递指针的引用 ，或者下面的方式

- 简单来说：函数形参传递指针，函数内部只能修改指针指向的值，而无法修改指针本身的地址，正确用法bool getElem(LinkList*& list, int pos, LinkNode* &node)

--------------------------主函数---------------------------cout << " ------------ 取指定位置元素---------" << endl;int pos;while (1) {node = new LinkNode;cout << "请输入要取的元素的位置";cin >> pos ;getElem(list, pos, node);printList(list);//cout << "位置" << pos << "处的元素是" << node->data << endl;}bool getElem(LinkList*& list, int pos, LinkNode* node) {if (!list || !list->next) {return false;}LinkNode* p = NULL;int counter = 1;p = list;while (p && counter < pos) {p = p->next;counter++;}//索引超出有效范围if (!p || counter > pos) {cout << "选取元素位置超出有效范围" << endl;return false;}node = p->next;return true;}

2.4 完整程序

#include <iostream>
#include <exception>
#include <stdexcept>
#include "string"
#include <fstream>
#include<conio.h>
#include<Windows.h>
#include <graphics.h>
#include <time.h>using namespace std;typedef struct LinkNode {int data;struct LinkNode* next; //指向下一个节点的指针
}LinkList,LinkNode;  //LinkList表示初始节点void init(LinkList*& list);
bool insert_head(LinkList*& list, LinkNode* node);
bool insert_end(LinkList*& list, LinkNode* node);
bool insert(LinkList*& list, LinkNode* node, int pos);
void printList(LinkList*& list);
bool getElem(LinkList*& list,int pos, LinkNode* &node);  //链表，取第几个元素，将值给node传出来
bool findElem(LinkList*& list, int elem, int &index);  //按值查找，链表，查找元素
bool deleteElem(LinkList*& list,int pos);
void LinkDestroy(LinkList*& list);int main() {LinkList* list = NULL;LinkNode* node = NULL;init(list);int num;int number;cout << "请输入要插入的数据个数:";cin >> num;cout << " ------------ 头插法---------" << endl;for (int i = 0; i < num; i++) {node = new LinkNode;cout << "请输入第" << i+1 << "个元素:";cin >> node->data;insert_head(list, node);}printList(list);cout << " ------------ 尾插法---------" << endl;for (int i = 0; i < num; i++) {node = new LinkNode;cout << "请输入第" << i + 1 << "个元素:";cin >> node->data;insert_end(list, node);}printList(list);cout << " ------------ 指定位置插入---------" << endl;int pos;while (1) {node = new LinkNode;cout << "请输入要插入的位置和数据";cin >> pos >> node->data;insert(list, node, pos);printList(list);}cout << " ------------ 取指定位置元素---------" << endl;int pos;while (1) {node = new LinkNode;cout << "请输入要取的元素的位置";cin >> pos ;getElem(list, pos, node);printList(list);cout << "位置" << pos << "处的元素是" << node->data << endl;}cout << " ------------ 按值查元素，并返回位置---------" << endl;int value, index;while (1) {node = new LinkNode;cout << "请输入要查找的元素";cin >> value;printList(list);if (findElem(list, value, index)) {cout << value << "位置" << index << endl;}else {cout << "元素不存在" << endl;}}cout << " ------------ 删除元素---------" << endl;int index;while (1) {node = new LinkNode;cout << "请输入要删除的元素位置";cin >> index;printList(list);if (deleteElem(list, index)) {cout << index << "位置删除成公"  << endl;printList(list);}else {cout << "元素不存在" << endl;}}LinkDestroy(list);printList(list);system("pause");return 0;
}bool deleteElem(LinkList*& list, int pos) {if (!list || !list->next) {cout << "链表为空" << endl;return false;}LinkNode* p = NULL;p = list;int counter = 0;while (p && counter < pos-1) {p = p->next;cout << p->data << " ";counter++;}if (!p || counter > pos-1) {cout << "删除位置不合法" << endl;return false;}LinkNode* temp = NULL;  //用来存要删除的节点，最后要将其delete,因为在主函数里面是通过new建立的链表temp = p->next;p->next = temp->next;delete temp;return true;
}void LinkDestroy(LinkList*& L) {LinkNode* temp = NULL; //用于存放即将删除的节点temp = L;while (L) {L = L->next;delete temp;temp = L;}
}bool findElem(LinkList*& list, int elem, int& index) {if (!list || !list->next) {index = -1;return false;}LinkNode* p = NULL;int counter = 1;p = list->next;while (p && p->data != elem) {p = p->next;counter++;}if (!p) {return false;}index = counter;return true;
}bool getElem(LinkList*& list, int pos, LinkNode* &node) {if (!list || !list->next) {return false;}LinkNode* p = NULL;int counter = 1;p = list;while (p && counter < pos) {p = p->next;counter++;}//索引超出有效范围if (!p || counter > pos) {cout << "选取元素位置超出有效范围" << endl;return false;}node = p->next;return true;}void init(LinkList*& list) {	list = new LinkList;if (!list){cout << "初始化内存分配失败" << endl;return;}list->data = -1;list->next = NULL;
}bool insert_head(LinkList*& list, LinkNode* node) {if (!list || !node) {cout << "内存分配失败" << endl;return false;}node->next = list->next;list->next = node;return true;
}void printList(LinkList*& list) {LinkNode* p = NULL;if (!list) {cout << "链表为空" << endl;return;}p = list->next;do {cout << p->data << " ";p = p->next;}while(p);cout << endl;
}bool insert_end(LinkList*& list, LinkNode* node) {if (!list || !node) {cout << "内存分配失败" << endl;return false;}LinkNode* p = NULL;p = list->next;while(p->next) {p = p->next;};node->next = NULL;p->next = node;return true;
}bool insert(LinkList*& list, LinkNode* node, int pos) {LinkNode* p = NULL;//p = list->next;p = list;int counter = 0;//循环遍历找到pos位置的节点while (p && counter < pos-1) {p = p->next;counter++;};//索引超出有效范围if (!p || counter > pos - 1) {cout << "插入位置超出有效范围" << endl;return false;}node->next = p->next;p->next = node;return true;
}