1.算法描述
数据结构与算法分析C++版:3.11
实现一个有序单链表,要求能返回链表大小,打印链表,检测x是否在链表(在则删除,否则添加)
2.实现
List.h
#ifndef LIST_H
#define LIST_H
#include <iostream>
template<class T>
struct Node{
Node<T>* next;
T data;
};
template<class T>
class List{
public:
List(){
len = 0;
first = new Node<T>;
first->next = NULL;
}
List(T a[], int n){
len = 0;
first = new Node<T>;
first->next = NULL;
for(int i=0; i<n; i++){
//有序插入元素
insertData(a[i]);
}
}
~List(){ release(); };
//长度
int length(){
return len;
}
//长度(通过遍历链表)
int getLength(){
int length=0;
Node<T>* r = first->next;
while(r){
length++;
r = r->next;
}
return length;
}
//打印链表
void printList(){
Node<T>* r = first->next;
std::cout<<"[";
while(r){
std::cout<<r->data<<" ";
r = r->next;
}
std::cout<<"]"<<std::endl;
}
//检测元素是否存在
bool isExsit(T x){
Node<T> *r = first->next;
bool b = true;
while(r && r->data != x){
r = r->next;
}
if(!r){
b = false;
}
return b;
}
//添加或删除存在元素(存在则删除,不存在则添加)
void findAddOrDelete(T x){
Node<T> *r = first->next, *p=first, *t;
while(r && r->data != x){
p = r;
r = r->next;
}
if(!r){
insertData(x);
}else{
//因为序列是有序的,删除连续相同的x
while(r && r->data == x){
t = r;
p->next = t->next;
delete t;
r = p->next;
len--;
}
}
}
//有序插入元素
void insertData(T x){
Node<T> *t = first->next, *p=first;
Node<T> *r = new Node<T>;
r->data = x;
r->next = NULL;
while(t && t->data < x){
p = t;
t = t->next;
}
p->next = r;
r->next = t;
len++;
}
private:
Node<T>* first;
int len;//存储链表长度
void release(){
Node<T> *r = first;
while(r->next){
Node<T> *t = r->next;
r->next = t->next;
delete t;
}
first->next = NULL;
}
};
#endif
main.cpp
#include <iostream>
#include "list.h"
using namespace std;
int main( ){
int a[] = {3,11,2,8,4,5,3,6,8,8,8};
List<int> l(a, 11);
cout<<"length:"<<l.length()<<endl;
l.printList();
cout<<l.isExsit(32)<<" "<<l.isExsit(8)<<endl;
l.findAddOrDelete(7);
cout<<"length:"<<l.length()<<endl;
l.printList();
l.findAddOrDelete(8);
cout<<"length:"<<l.length()<<endl;
l.printList();
return 0;
}
3.总结
难度没什么,主要是考察链表的基本操作,边界检查,尤其是使用指针的时候尤其注意,指针检查!
4.删除
- 大小: 8.7 KB
分享到:
相关推荐
4.熟练掌握简单的演示菜单与人机交互设计方法。 二、实验内容 1. 编制一个演示单链表插入、删除、查找等操作的程序。 三、实验步骤 1.需求分析 本演示程序用JAVA编写,完成单链表的生成,任意位置的插入、删除,...
(1).键盘输入一组元素,建立一个无头结点的单向链表(无序)。 (2).遍历(打印)单向链表。...判断算法1和算法5生成单链表所表示的集合是否相等。 (10).在主函数中设计一个简单的菜单,分别调试上述算法。
(2)设计实验:其主要内容是针对具体问题,应用某一个知识点,自己设计方案,并上机实现,目的是培养学生对数据结构的简单应用能力; (3)综合实验:其主要内容是针对具体问题,应用某几个知识点,自己设计方案,并...
链表 单链表 LinkList 循环链表 ClinkList 双循环链表 DLinkList 静态链表 SlinkList 应用 集合并 MerGroup 多项式求和 Poly 3 栈 顺序栈 SqStack 链栈 LinkStack 栈应用 数制转换 Conversion 表达式计算 ...
实验题目3:简单的图书管理程序 实验题目4:反转单链表 实验八:文件 实验题目1:写入文本文件 实验题目2:统计文本文件 实验题目3:格式化写文件 实验题目4:格式化读文件 实验题目5:读写二进制文件
《GLib库入门与实践》专栏的配套源码。专栏地址:https://blog.csdn.net/field1003/article/details/123420966。 还在为C语言开发时重复造轮子苦恼吗,链表、队列、线程池,统统都得自己实现?先了解一下GLib-2.0库...
天,以鼓励一致的实践。 来源:编程面试要素 第 6 章 - 字符串 章节 # 问题 可能重复的 Leetcode/CTCI 6 6.1 字符串和整数的相互转换 - 简单的 6 6.2 基数转换 6 6.3 计算电子表格列编码 6 6.4 更换和移除 6 6.5 ...
数据结构主题: 单链表队列和堆栈双链表二叉搜索树相关代码挑战问题伸展目标: LRU缓存堆AVL树完成要求模块1:使用内置的Python列表以及您在模块1指导项目期间创建的Node和LinkedList类,实现Stack和Queue类。...
构建一个简易菜单,形如: 用户通过输入数值选择所需运行的子程序,当一个子程序运行结束后回到菜单界面,直至用户输入0后退出程序。 5.实训选题 每人至少做6题,题目如下(每人的题目由任课老师安排) (1)...
1.5 关于C++上机实践 习题 第2章 数据类型与表达式 2.1 C++的数据类型 2.2 常量 2.2.1 什么是常量 2.2.2 数值常量 2.2.3 字符常量 2.2.4 符号常量 2.3 变量 2.3.1 什么是变量 2.3.2 变量名规则 2.3.3 定义变量 ...
1.5 关于C++上机实践 习题 第2章 数据类型与表达式 2.1 C++的数据类型 2.2 常量 2.2.1 什么是常量 2.2.2 数值常量 2.2.3 字符常量 2.2.4 符号常量 2.3 变量 2.3.1 什么是变量 2.3.2 变量名规则 2.3.3 定义变量 ...
回顾起此次课程设计,至今我仍感慨颇多,的确,从拿到题目到完成整个编程,从理论到实践,在整整半个学期的日子里,可以学到很多很多的东西,同时不仅可以巩固了以前所学过的知识,而且学到了很多在书本上所没有学到...