数据结构--线性表

单链表的基本操作

1.清空单链表

• 链表仍然存在，但链表中无元素，成为空链表（头指针和头链表仍存在）
• 算法思路：依次释放所有结点，并将头结点指针设置为空

2.返回表长

3.取值–取单链表中第i个元素

• 因为存储方式为顺序存储，所以需要依次扫描

4.按值查找

• 返回该元素所在的位置
• 返回该元素对应的下标索引

5.插入结点

算法分析：

• 先找到第i个元素位置
• 将i-1元素的指针指向新节点
• 新节点的指针域指向原先第i个
• 结点数量自增1

不能直接更换2-3步的顺序，否则会导致第i个元素的位置丢失

6.删除第i个结点

​

7.查找、插a入和删除的时间复杂度分析

• 查找：
  • 因为线性来拿吧只能顺序存取，即在查找时要从头指针找起，所以时间复杂度为O(n)
• 插入和删除
  • 因线性链表不需要移动元素，只要修改指针，所以一般时间复杂度为O(n)

8.头插法建立单链表

算法分析：

• 从一个空表开始，重复读入数据
• 生成新结点，将数据存入新结点的数据域中
• 从最后一个结点开始依次将各节点插入链表前端

• 时间复杂度O(n)

9.尾插法创建单链表

• 从一个空表开始，将新结点诸葛插入链表尾部，尾指针r指向链表的尾结点
• 初始时r均指向头结点，每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点

代码

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
struct Lnode {													//链表结点的类型定义
	char name[10];
	int score;
	struct Lnode* next;
};
int init_Lnode(Lnode* L);										//单链表的初始化
int isLnode(Lnode* L);											//判断是否为空,0表示空，1表示非空
int destroyLnode(Lnode* L);										//销毁单链表
int deleteLnode(Lnode* L);										//清空单链表
int lengthLnode(Lnode* L);										//求表长
int getLnode(Lnode* L, int i, Lnode& e);						//取值，求第i个元素
Lnode* findLnode(Lnode* L, int i, char* name1, int score);		//按照值查找,返回第一个元素的位置
int insertLnode(Lnode* L, char* name2, int score);				//在第i个位置前增添一个
int denLnode(Lnode* L, int n);									//删除第n个元素的结点
void creatLnode_1(Lnode* L, int n);								//利用头插法创建链表
void creatLnode_2(Lnode* L, int n);								//利用尾插法创建链表
int main() {
	
}
int init_Lode(Lnode *L) {
	L = (Lnode*)malloc(sizeof(Lnode));
	if (!L)	return 0;
	L->next = NULL;
	return 1;
}
int isLnode(Lnode* L) {
	if (!L->next)	return 0;
	return 1;
}
int destroyLonde(Lnode* L) {
	Lnode* p;
	while (L->next) {
		p = L;
		L = L->next;
		free(p);
	}
	return 1;
}
int deleteLnode(Lnode* L) {
	Lnode* p = L->next;
	Lnode* q;
	while (p) {
		q = p->next;
		free(p);
		p = q;
	}
	L->next = NULL;
	return 1;
}
int lengthLnode(Lnode* L) {
	int sum = 0;
	if (!isLnode(L))	return sum;
	Lnode* p = L->next;
	while (p) {
		sum++;
		p = p->next;
	}
	free(p);
	return sum;
}
int getLnode(Lnode* L, int i, Lnode& e) {
	Lnode *p = L->next;
	int j = 1;
	while (p && j < i) {
		p = p->next;
		j++;
	}
	if (!p || j>i)	return 0;
	e = *p;
	return 1;
}
Lnode* findLnode(Lnode* L, int i, char* name1, int score) {
	Lnode* p = L->next;
	while (p) {
		if (strcmp(p->name, name1) && p->score == score) {
			break;
		}
		p = p->next;
	}
	return p;
}

int insertLnode(Lnode* L, char* name2, int score, int n) {
	int i = 0;
	Lnode* p = L;
	if (n<1 || n>lengthLnode(L) + 1) {
		printf("error");
		return 0;
	}
   
	while (i < n) {
		p = p->next;
		i++;
	}
	Lnode* s = (Lnode*)malloc(sizeof(Lnode));
	strcpy_s(s->name, name2);
	s->score = score;
	s->next = p->next;
	p->next = s;
	return 1;
}
int denLnode(Lnode* L, int n) {
	int i = 0;
	Lnode* p = L;
	if (n<1 || n>lengthLnode(L)) {
		printf("error");
		return 0;
	}
	while (i < n-1) {
		p = p->next;
		i++;
	}
	Lnode* s = p->next;
	p->next = p->next->next;
	free(s);
	return 1;
}
void creatLnode_1(Lnode* L, int n) {
	L = (Lnode*)malloc(sizeof(Lnode));
	L->next = NULL;
	Lnode* p;
	for (int i = 0; i < n; i++) {
		p= (Lnode*)malloc(sizeof(Lnode));
		scanf_s("输入姓名:%d", &p->name);
		scanf_s("输入成绩:%d", &p->score);
		p->next = L->next;
		L->next = p;
	}
}
void creatLnode_2(Lnode* L, int n) {
	L = (Lnode*)malloc(sizeof(Lnode));
	L->next = NULL;
	Lnode* p, * r;
	r = L;
	for (int i = 0; i < n; i++) {
		p = (Lnode*)malloc(sizeof(Lnode));
		scanf_s("输入姓名:%d", &p->name);
		scanf_s("输入成绩:%d", &p->score);
		p->next = NULL;
		r->next = p;
		r = p;		
	}
}

循环链表

• 即头尾相接的一个链表，表中最后一个结点的指针域指向头结点，使整个链表闭合成为一个环

• 

• 优点：从表中任意结点出发均可找到表中其他结点

• 注意：循环链表中没有NULL,所以遍历时终止条件为是否等于头指针

• 空表：头指针指向自己

• 在循环链表中操作首尾元素时用的最多的是尾指针，因为头指针要找最后一个元素比较麻烦，时间复杂度高

两个循环链表的合并

• 操作步骤：
  • p存表头结点
  • Tb表头连接到Ta表尾
  • 释放Tb表头结点
  • Tb表尾指向Ta表头
• 伪代码如下：

LinkList Connect(LinkList Ta, LinkList Tb) {		//Ta和Tb均为尾指针
	p = Ta->next;									
	Ta->next = Tb->next->next;
	free(Tb->next);
	Tb->next = p;
	return Tb;
}

双向链表

前面链表如果需要找到某一个元素的前驱结点比较麻烦，但如果我们采用双向链表就比较方便，时间复杂度O(n)->O(1)

结构体定义伪代码如下：

typedef struct DulNode {
	Elemtype data;
	struct Dulnode* prior, * next;
};

• 空表：前驱后继均为NULL
• 对称性：
  • p->next->prior = p = p->prior->next;
• 在双向链表中有些操作如（Listlength）等只涉及以后方向的指针，所以算法鱼线性链表相同。
• 但在插入删除时，许哟啊同时修改两个方向的指针，两者的时间复杂度为O(n)

双向循环链表：

• 头结点的前驱指针指向链表的最后一个结点
• 最后一个结点的后继指针指向头结点

双向链表的插入

算法分析：

• s->prior = p->prior
• p->prior->next = s
• s->next = p
• p->prior = s

伪代码如下：

int Listinsert_dul(LinkList& L, int i, Elemtype e) {		//Elemtype为题目所需压要的数据类型
	if (!(p = GetElem_dul(L, i)))		return 0;			//将p指向第i个元素
	s = new DulLnode;	s->data = e;
	s->prior = p->prior;
	p->prior->next = s;
	s->next = p;
	p->prior = s;
	return 1;
}

双向链表的删除

算法分析：

• p->prior->next = p->next;
• p->next->prior = p->prior

伪代码如下：

int Listinsert_dul(LinkList& L, int i, Elemtype &e) {		//Elemtype为题目所需压要的数据类型
	if (!(p = GetElem_dul(L, i)))		return 0;			//将p指向第i个元素
	e = p->data;
	p->prior->next = p->next->prior;
	p->next->prior = p->prior->next;
	free(p);
	return 1;
}

• 如果知道要删除的位置，那么时间复杂度为O(1)，但为了查找第i个元素的位置所以总的时间复杂度为O(n)

单链表、循环链表和双向链表的时间效率比较

顺序表和链表的比较

链表的优点：

• 结点空间可以动态申请和释放
• 逻辑次序通过结点的指针表示，插入和删除时不需要移动大量的数据元素

缺点：

• 每个指针域需要额外的占用空间
• 存储密度比较小
• 非随机存取结构，对结点的操作都要从头指针沿着指针链查找，增加了算法的复杂度

存储密度指结点中数据本身所占系结点总空间的比重，即数据所占空间/结点总空间

一般存储密度越大，存储空间的利用率越高

线性表的合并

问题描述：

• 假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A = A∪B
  • 如La = (7，5，3，11)，Lb = (2，6，3) —>La = (7，5，3，11，2，6)
  • 算法分析：
    • 依次取出Lb的元素并在La中查找
      • 如果有，直接跳过该元素
      • 如果没有，则插入到La的表尾

伪代码如下：

void union(List& a, LIst b) {
	a_len = Listlength(a);
	b_len = Listlength(b);
	for (int i = 0; i < b_len; i++) {
		GetElem(b, i, e);
		if (!Locate(a, e)) {
			Listinsert(&a, ++a_len, e);				//即添加完后元素个数自增1
		}
	}
}

有序表的合并(顺序表)

已知La和Lb中的数据元素按照非递减有序排列合并为一个新的线性表Lc，且Lc中的元素也是按照值非递减有序排列

La=(1，7，8) Lb=(2，4，6，8，10，11)

–》Lc=(1，2，4，6，7，8，8，10，11)

算法步骤：

• 创建一个空表Lc
• 依次从La和Lb中摘取值较小的结点插入到Lc表的最后，直至某方变为一个空表为止
• 继续从另一个表中读取剩余元素

void MergeList1(List a, List b, List& c) {
	pa = a.elem;
	pb = b.elem;											//pa和pb分别指向第一个元素
	c.length = a.length + b.length;
	c.elem = new elem[c.length];
	pa_last = pa.elem + pa.length - 1;
	pb_last = pb.elem + pb.length - 1;
	while (pa <= pa_last && pb <= pb_last) {
		if (*pa <= *pb)	*pc++ = *pa++;
		else  *pc++ = *pb++;
	}
	while (pa <= pa_last) {
		*pc++ = *pa++;
	}
	while (pb <= pb_last) {
		*pc++ = *pb++;
	}
}

有序表的合并(链表)

算法步骤上同

伪代码：

void MergeList2(List a, List b, List& c) {
	pa = a->next;pb = b->next;
	pc = c = a;
	while (a && b) {
		if (a->data < b->data) {
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else {
			pc->next = pb;
			pc = pb;
			pb= pb->next;
		}
	}
	pc->next = a ? a : b;
	delete(b);
}

实战：多项式相加运算

typedef struct aaa {
    float p;        //系数
    int e;          //指数
};
typedef struct bbb{
    aaa data;
    struct bbb* next;
}*List;
void add(List a, List b) {
    Lnode* p1 = a->next;
    Lnode* p2 = b->next;
    Lnode* pa = a;
    while (p1 && p2) {
        if (p1->data.e == p2->data.e) {
            p1->data.e += p2->data.e;
            if (p1->data.e == 0) {
                p1 = p1->next;
                p2 = p2->next;
            }
            else {
                pa->next = p1;
                pa = p1;
                p1 = p1->next;
                p2 = p2->next;
                continue;
            }
        }
        else if (p1->data.e < p2->data.e) {
            pa->next = p1;
            pa = p1; 
            p1 = p1->next;
        }
        else {
            pa->next = p2;
            pa = p2;
            p2 = p2->next;
        }
    }
    if (p1) pa->next = p1;
    if (p2) pa->next = p2;
}

实战：稀疏多项式的运算

算法分析(顺序表)：

• 先将两个多项式转化为存储为线性表形式
• 创建一个新的数组
• 分别遍历比较两个线性表的每一项
  • 指数相同，对应系数相加，若其和不为0，则在新数组中增加一个新项
  • 指数不同，将指数较小的项复制到新数组中
• 一个多项式遍历完毕后，将另外一个剩余项依次复制进新数组即可
• 问题：新数组应该多大？
  • 存储空间分配不灵活
  • 运算空间复杂度高

线性表分析大同小异,算法分析略

结点结构体的定义:

struct polynode{
	int coef;
	int exp;
	polynode *next;
}polynode,polylist;

尾插法创建线性表:

polylist polycreate() {	//尾插法
	polynode *head,*rear,*s;
	int c,e;
	head=(polynode *)malloc(sizeof(polynode));
	rear=head;
	scanf("%d %d",&c,&e);
	while(c!=0)
	{
		s=(polynode *)malloc(sizeof(polynode));
		s->coef=c;
		s->exp=e;
		rear->next=s;
		rear=s; 
		scanf("%d %d",&c,&e);
	}
	rear->next=NULL;
	//将表的最后一个结点的next置NULL，以表示结束
	return (head); 
}

实现两个多项式相加：

void polyadd(polylist polya, polylist polyb){
//将两个多项式相加，然后将和多项式存放在polya中，并将polyb删除
	polynode* p, * q, * tail, * temp;
	int sum;
	p = polya->next;
	q = polyb->next;
	tail = polya;//tail指向和多项式的尾结点
	while (p != NULL && q != NULL) {
		if (p->exp < q->exp){
			tail->next = p;
			tail = p;
			p = p->next;
		}
		else if (p->exp == q->exp){
			sum = p->coef + q->coef;
			if (sum != 0)
				//若系数和非0，则系数和置入结点p，释放结点q，并将指针后移
			{
				p->coef = sum;
				tail->next = p;
				tail = p;
				p = p->next;
				temp = q;
				q = q->next;
				free(temp);
			}
			else {
				//若系数和为0.删除p，q，并将指针指向下一个结点
				temp = p;
				p = p->next;
				free(temp);
				temp = q;
				q = q->next;
				free(temp);
			}
		}
		else {
			tail->next = q;
			tail = q;
			q = q->next;
		}
	}
	if (p != NULL){
		tail->next = p;
		tail = p;
		p = p->next;
	}
	else {
		tail->next = q;
		tail = q;
		q = q->next;
	}
}

实战：图书管理系统

略

代码

顺序存储结构

//线性表--顺序存储结构
#include<iostream>
using namespace std;
template<typename T>		//typename可以用class代替
struct sequentaillist {
	T* element;
	int size;			//大小
	int capital;		//容量
};

template<typename T>
void initlist(sequentaillist<T>* List,int capital) {				//初始化的过程其实就是分别初始化list三个变量
	List->element = new T[capital];				//动态分配内存	
	List->size = 0;
	List->capital = capital;
}

template<typename T>
void destroylist(sequentaillist<T>* list) {					//销毁线性表
	delete[] list->element;			//释放内存
}

template<typename T>
bool isempty(sequentaillist<T> list) {
	return list->size == 0;			//判断是否为空表
}

template<typename T>
int getsize(sequentaillist<T> list) {					//返回表长
	return list.size;
}

template<typename T>
void clearlist(sequentaillist<T>* list) {				//清空表长，就像未使用过一样
	if (list == nullptr) return;
	delete[] list->element;
	list->element = nullptr;
	list->size = 0;
	list->capital = 0;
}

template<typename T>
T getvalue(sequentaillist<T> list , int i) {					//获取表中第i个元素的值
	if (list.element == nullptr)	return nullptr;
	if (i<0 || i>list.size) {
		cout << "下标越界" << endl;
		return nullptr;
	}
	return list.element[i];
}

template<typename T>
int findelement(sequentaillist<T> list, int value) {			//查找元素
	if (list.element == nullptr) return -1;
	for (int i = 0; i < list.size; i++) {
		if (list.element[i] == value) {
			return i;
		}
	}
	return -1;			//没找到
}

template<typename T>
void insert(sequentaillist<T>* list, int i , T value) {					//在第i个位置插入元素value
	if (list == nullptr) return;
	if (i<0 || i>list->size) {
		cout << "下标越界" << endl;
		return;
	}
	if (list->size == list->capital) {					//满了，扩容
		T* newelement = new T[list->capital * 2];		//扩容两倍
		for (int i = 0; i < list->size; i++) {
			newelement[i] = list->element[i];
		}
		delete[] list->element;
		list->element = newelement;
		list->capital = list->capital * 2;
	}
	for (int j = list->size; j > i; j--) {
		list->element[j + 1] = list->element[i];
	}
	list->element[i] = value;
	list->size++;
}

template<typename T>
void deleteelement(sequentaillist<T>* list, int i) {				//删除第i个元素
	if (list == nullptr) return;
	if (i<0 || i>list->size) {
		cout << "下标越界" << endl;
		return;
	}
	for (int j = i; j < list->size - 1; j++) {
		list->element[j] = list->element[j + 1];
	}
	list->size--;
}
template<typename T>
void remove(sequentaillist<T>* list, int value) {				//删除表中的所有value
	if (list == nullptr) return;
	for (int i = 0; i < list->size; i++) {
		if (list->element[i] == value) {
			deleteelement(list, i);							
			i--;			//删除位置后因为所有元素都要向前一位，覆盖了原本的i号位置，所以i号位置重新比较一遍
		}
	}
}

template<typename T>
void setvalue(sequentaillist<T>* list, int i, int value) {			//设置第i个元素的值
	if (list == nullptr) return;
	if (i<0 || i>list->size) {
		cout << "下标越界" << endl;
		return;
	}
	list->element[i] = value;
}
int main() {
	// 初始化线性表
	sequentaillist<int> list;
	initlist(&list, 5); // 初始容量为5
	cout << "初始化线性表，容量为5" << endl;

	// 插入元素
	insert(&list, 0, 10);
	insert(&list, 1, 20);
	insert(&list, 2, 30);
	cout << "插入元素后，线性表内容为：";
	for (int i = 0; i < list.size; i++) {
		cout << list.element[i] << " ";
	}
	cout << endl;

	// 查找元素
	int value = 20;
	int index = findelement(list, value);
	if (index != -1) {
		cout << "查找元素" << value << "，位置为：" << index << endl;
	}
	else {
		cout << "查找元素" << value << "，未找到" << endl;
	}

	// 删除元素
	deleteelement(&list, 1);
	cout << "删除第1个元素后，线性表内容为：";
	for (int i = 0; i < list.size; i++) {
		cout << list.element[i] << " ";
	}
	cout << endl;

	// 删除所有指定值的元素
	remove(&list, 30);
	cout << "删除所有值为30的元素后，线性表内容为：";
	for (int i = 0; i < list.size; i++) {
		cout << list.element[i] << " ";
	}
	cout << endl;

	// 设置元素值
	setvalue(&list, 0, 100);
	cout << "设置第0个元素值为100后，线性表内容为：";
	for (int i = 0; i < list.size; i++) {
		cout << list.element[i] << " ";
	}
	cout << endl;

	// 清空线性表
	clearlist(&list);
	cout << "清空线性表后，线性表大小为：" << getsize(list) << endl;

	// 销毁线性表
	destroylist(&list);
	cout << "销毁线性表" << endl;

	return 0;
}

链式存储结构

#include <iostream>
using namespace std;

// 定义链表节点模板结构
template <typename T>
struct Node {
    T data; // 数据域
    Node<T>* next; // 指向下一个节点的指针
};

// 定义链表模板类
template <typename T>
class LinkedList {
private:
    Node<T>* head; // 头节点指针

public:
    // 构造函数
    LinkedList() : head(nullptr) {}

    // 析构函数
    ~LinkedList() {
        destroy(head); // 销毁链表
    }

    // 初始化链表
    void init() {
        head = new Node<T>; // 创建头节点
        head->next = nullptr;
    }

    // 判断链表是否为空
    bool isempty() const {
        return head->next == nullptr;
    }

    // 获取链表长度
    int getsize() const {
        int count = 0;
        Node<T>* current = head->next;
        while (current) {
            count++;
            current = current->next;
        }
        return count;
    }

    // 清空链表
    void clear() {
        destroy(head->next); // 销毁链表中的所有节点
        head->next = nullptr; // 重置头节点的next指针
    }

    // 插入元素
    bool insert(int index, const T& value) {
        if (index < 0) return false; // 索引不能为负

        Node<T>* current = head;
        int currentIndex = 0;

        // 找到插入位置的前一个节点
        while (current != nullptr && currentIndex < index) {
            current = current->next;
            currentIndex++;
        }

        if (current == nullptr) return false; // 索引超出链表范围

        // 创建新节点
        Node<T>* newNode = new Node<T>;
        newNode->data = value;
        newNode->next = current->next;
        current->next = newNode;

        return true;
    }

    // 删除元素
    bool remove(int index) {
        if (index < 0) return false; // 索引不能为负

        Node<T>* current = head;
        int currentIndex = 0;

        // 找到删除位置的前一个节点
        while (current->next != nullptr && currentIndex < index) {
            current = current->next;
            currentIndex++;
        }

        if (current->next == nullptr) return false; // 索引超出链表范围

        // 删除节点
        Node<T>* temp = current->next;
        current->next = temp->next;
        delete temp;

        return true;
    }

    // 查找元素
    int find(const T& value) const {
        Node<T>* current = head->next;
        int index = 0;

        while (current != nullptr) {
            if (current->data == value) {
                return index;
            }
            current = current->next;
            index++;
        }

        return -1; // 未找到
    }

    // 获取指定位置的元素
    bool getvalue(int index, T& value) const {
        if (index < 0) return false; // 索引不能为负

        Node<T>* current = head->next;
        int currentIndex = 0;

        while (current != nullptr && currentIndex < index) {
            current = current->next;
            currentIndex++;
        }

        if (current == nullptr) return false; // 索引超出链表范围

        value = current->data;
        return true;
    }

    // 设置指定位置的元素
    bool setvalue(int index, const T& value) {
        if (index < 0) return false; // 索引不能为负

        Node<T>* current = head->next;
        int currentIndex = 0;

        while (current != nullptr && currentIndex < index) {
            current = current->next;
            currentIndex++;
        }

        if (current == nullptr) return false; // 索引超出链表范围

        current->data = value;
        return true;
    }

    // 销毁链表
    void destroy(Node<T>*& head) {
        Node<T>* temp;
        while (head) {
            temp = head;
            head = head->next;
            delete temp;
        }
    }

    // 打印链表
    void print() const {
        Node<T>* current = head->next;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }

    //创建链表（头插法）
    void creatLnode_1(int n) {
        head = new Node<T>; // 创建头节点
        head->next = nullptr;

        Node<T>* p;
        for (int i = 0; i < n; i++) {
            p = new Node<T>; // 创建新节点
            cin >> p->data; // 从标准输入读取数据
            p->next = head->next; // 新节点指向头节点的下一个节点
            head->next = p; // 头节点指向新节点
        }
    }

    // 创建链表（尾插法）
    void creatLnode_2(int n) {
        head = new Node<T>; // 创建头节点
        head->next = nullptr;

        Node<T>* p, * r;
        r = head;
        for (int i = 0; i < n; i++) {
            p = new Node<T>; // 创建新节点
            cin >> p->data; // 从标准输入读取数据
            p->next = nullptr;
            r->next = p; // 将新节点链接到链表末尾
            r = p; // 更新尾指针
        }
    }

};

int main() {
    LinkedList<int> list;

    // 测试头插法创建链表
    cout << "使用头插法创建链表：" << endl;
    int n1;
    cout << "请输入链表的长度：";
    cin >> n1;
    list.creatLnode_1(n1);
    cout << "链表内容：";
    list.print();

    // 测试尾插法创建链表
    cout << "\n使用尾插法创建链表：" << endl;
    int n2;
    cout << "请输入链表的长度：";
    cin >> n2;
    list.clear(); // 清空链表
    list.creatLnode_2(n2);
    cout << "链表内容：";
    list.print();

    // 测试插入元素
    cout << "\n插入元素：" << endl;
    int index, value;
    cout << "请输入插入位置和值：";
    cin >> index >> value;
    if (list.insert(index, value)) {
        cout << "插入成功" << endl;
    }
    else {
        cout << "插入失败" << endl;
    }
    cout << "链表内容：";
    list.print();

    // 测试删除元素
    cout << "\n删除元素：" << endl;
    cout << "请输入删除位置：";
    cin >> index;
    if (list.remove(index)) {
        cout << "删除成功" << endl;
    }
    else {
        cout << "删除失败" << endl;
    }
    cout << "链表内容：";
    list.print();

    // 测试查找元素
    cout << "\n查找元素：" << endl;
    cout << "请输入要查找的值：";
    cin >> value;
    int foundIndex = list.find(value);
    if (foundIndex != -1) {
        cout << "元素" << value << "的位置为：" << foundIndex << endl;
    }
    else {
        cout << "元素" << value << "未找到" << endl;
    }

    // 测试获取指定位置的元素
    cout << "\n获取指定位置的元素：" << endl;
    cout << "请输入要获取的元素索引：";
    cin >> index;
    int retrievedValue;
    if (list.getvalue(index, retrievedValue)) {
        cout << "第" << index << "个元素的值为：" << retrievedValue << endl;
    }
    else {
        cout << "索引超出范围" << endl;
    }

    // 测试设置指定位置的元素
    cout << "\n设置指定位置的元素：" << endl;
    cout << "请输入要设置的元素索引和新值：";
    cin >> index >> value;
    if (list.setvalue(index, value)) {
        cout << "设置成功" << endl;
    }
    else {
        cout << "设置失败" << endl;
    }
    cout << "\n清空链表：" << endl;
    list.clear();
    cout << "清空链表后，链表是否为空：" << (list.isempty() ? "是" : "否") << endl;
    return 0;
}