单链表的设计与实现

怼烎@ 2023-03-13 06:46 22阅读 0赞

1、单链表的设计（linklist.h）：设计头文件linklist.h，其内容如下：  
①类型设计  
②基本操作的设计（包括初始化、单链表的创建、插入、删除、遍历等）  
2、设计文件c.h，提供比较和遍历时的操作函数  
3、测试：设计测试文件application.cpp文件，验证所设计的顺序表的正确性。其内容如下：  
设计一个主函数。  
4、利用上面设计的单链表，实现下列应用  
①设计函数，删除链表中元素在\[x, y\]之间的所有元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)；  
②设计函数，求解单链表中倒数第k个元素，要求算法的时间复杂度为O(n)；  
③求LA=LA∪LB，利用原有的结点空间。  
设计函数实现上诉功能。并设计一个测试文件测试其正确定。  
步骤：  
①设计app.h文件，设计三个函数分别实现上诉①、②、③  
②设计主函数测试：application.cpp  
1、linklist.h文件

#include "stdlib.h"
    #include "c.h"
    #include <iostream>
    using namespace std;
    //设计单链表
    //1：单链表数据类型定义
    typedef struct Lnode { 
    	elemtype data;
    	Lnode *next;
    } LNode, *LinkList;
    //2：设计函数（对单链表进行操作）
    //2.1 初始化带头结点的单链表
    void initList(LinkList &L) { 
    	L = new LNode;
    	L->next = NULL;
    }
    //2.1 根据给定的以elem为首地址的n个元素采用尾插入法创建带头结点的单链表
    void createList_rear(LinkList &L, elemtype *elem, int n) { 
    	LNode *p, *r;
    	initList(L);
    	r = L;
    	for (int i = 0; i < n; i++) { 
    		p = new LNode;
    		p->data = elem[i];
    		r->next = p;
    		r = p;
    	}
    	r->next = NULL;
    }
    //2.2 查找单链表中的第i个结点。如果存在返回该结点的地址；如果不存在，返回NULL
    LNode *getElem(LinkList L, int i) { 
    	if(i<=0){ 
    		cout<<"给定元素位序不合理！"<<endl;
    		exit(0);
    	}
    	LNode *p = L->next;
    	int j = 1;
    	while (p && j < i) { 
    		p = p->next;
    		j++;
    	}
    	return p;
    }
    //2.3 查找第i个结点的前驱
    LNode *getPrior(LinkList L, int i) { 
    	LNode *p;
    	if (i <= 0) { 
    		return NULL;
    	}
    	p = L;
    	int index = 0;
    	while (p && index < i - 1) { 
    		p = p->next;
    		index++;
    	}
    	return p;
    }
    //2.4 在单链表的第i个位置插入数据元素e
    void listInsert(LinkList L, int i, elemtype e) { 
    	if (i <= 0) { 
    		cout << "插入位置错误！" << endl;
    		exit(0);
    	}
    	LNode *p = getPrior(L, i);
    	if (p == NULL) { 
    		cout << "插入位置错误！" << endl;
    		exit(0);
    	}
    	LNode *s = new LNode;
    	s->data = e;
    	s->next = p->next;
    	p->next = s;
    }
    //2.5 删除第i个元素，并通过变量e返回第i个元素的值
    void listDelete(LinkList L, int i, elemtype &e) { 
    	if (i < 1) { 
    		cout << "删除元素不存在！" << endl;
    		exit(0);
    	}
    	LNode *p = getPrior(L, i);
    	if (p == NULL || p->next == NULL) { 
    		cout << "删除元素不存在！" << endl;
    		exit(0);
    	}
    	LNode *q = p->next;
    	e = q->data;
    	p->next = q->next;
    	delete q;
    }
    //2.6 查找（给定元素值，找该元素在链表中是否存在。存在返回其地址，不存在返回NULL）
    LNode *Location(LinkList L, elemtype e, bool (*comp)(elemtype, elemtype)) { 
    	LNode *p;
    	p = L->next;
    	while (p && !comp(e, p->data)) { 
    		p = p->next;
    	}
    	return p;
    }
    
    //2.7 遍历单链表
    void listTraverse(LinkList L, void (*visit)(elemtype)) { 
    	LNode *p = L->next;
    	while (p) { 
    		visit(p->data);
    		p = p->next;
    	}
    	cout << endl;
    }
    //2.8 销毁单链表
    void destroyList(LinkList &L) { 
    	LNode *p;
    	p = L->next;
    	while (p) { 
    		L->next = p->next;
    		delete p;
    		p = L->next;
    	}
    	delete L;
    }

2、c.h文件

#include <iostream>
    using namespace std;
    
    void printElem(int e) { 
    	cout << e << " ";
    }
    bool comp(int a,int b){ 
    	return a==b;
    }
    void printElem(char ch){ 
    	cout<<ch<<" ";
    }

3、cpp.h文件

//①设计函数，删除链表中元素在[x, y]之间的所有元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)；
    //②设计函数，求解单链表中倒数第k个元素，要求算法的时间复杂度为O(n)；
    //③求LA=LA∪LB，利用原有的结点空间。
    
    void delete_sq_fromAandB(LinkList L, elemtype a, elemtype b) { 
    	//补充完整
    	/*LNode *p,*q; p=L; elemtype y; if(p->next==NULL) cout<<"链表为空！"<<endl; while(p->next->data >a && p->next->data <b) { q=p->next; y=q->data; p->next=q->next; free(q); p=p->next; }*/
        LNode *p,*q;
    	p=L;
    	q=p;
    	p=p->next;
    	if(p==NULL)
    	cout<<"链表为空"<<endl;
    	while(p!=NULL) { 
    		if((p->data>=a)&&(p->data<=b)) { 
    			q->next=p->next;
    			free(p) ;
    			p=p->next;
    		}else{ 
    			q=p;
    			p=p->next;
    		}
    	}
    }
    //求解倒数第k个元素，并通过变量e返回其值
    void getElemReverse(LinkList L,int k,elemtype &e) { 
    	//补充完整
    	LinkList p,q;
    	int i=1;
    	p=L;p=p->next;
    	q=L;
    	while(p){ 
    		p=p->next;
    		i++;
    		if(i>k)
    		q=q->next;
    	}
    	e=q->data;
    }
    //求LA=LA∪LB
    void union_sq(LinkList LA, LinkList LB) { 
    	//补充完整
        LNode *p,*q;
    	p=LA;q=LB;
    	int i=1;
    	/*for(p=p->next;p!=NULL;p=p->next){ if(!Location(LA,q->data,comp)){ listInsert(LA,i,q->data); q=q->next; }else{ q=q->next; } i++; }*/
    	for(p=p->next;p!=NULL,q!=NULL;p=p->next){ 
    		if(!Location(LA,q->data,comp)){ 
    			listInsert(LA,i,q->data);
    			q=q->next;
    		}else{ 
    			q=q->next;
    		}
    		i++;
    	}
    }

4、application.cpp文件

typedef int elemtype;
    #include "LinkList.h"
    #include "cpp.h"
    int main() { 
    	elemtype a[6] = {  3, 17, 11, 14, 20, 51 };
    	elemtype b[5] = {  3, 14, 9, 22, 36 };
    	LinkList LA, LB;
    	initList(LA);
    	initList(LB);
    	for (int i = 0; i < 6; i++) { 
    		listInsert(LA, i + 1, a[i]);
    	}
    	for (int i = 0; i < 5; i++) { 
    		listInsert(LB, i + 1, b[i]);
    	}
    	cout << "LA表中元素为：" << endl;
    	listTraverse(LA, printElem);
    	cout << "LB表中元素为：" << endl;
    	listTraverse(LB, printElem);
    	union_sq(LA, LB);
    	cout << "LA和LB的并集为：" << endl;
    	listTraverse(LA, printElem);
    	int k;
    	k=4;
    	elemtype e;
    	getElemReverse(LA,k,e);
    	cout << "LA中倒数第"<<k<<"个元素：" <<e<< endl;
    /* delete_sq_fromAandB(LA, 3, 15); cout << "删除LA中3到15之间的所有元素后：" << endl; listTraverse(LA, printElem); listTraverse(LA, printElem);*/
    	destroyList(LA);
    	return 0;
    }

**运行截图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTEwMDgz_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTEwMDgz_size_16_color_FFFFFF_t_70]: /images/20230312/23867972b7234757a43a4b2418dea514.png