-
2019-01-25 15:20:48
二分法是一种快速查找的方法,时间复杂度低,逻辑简单易懂,总的来说就是不断的除以2除以2…
例如需要查找有序数组arr里面的某个关键字key的位置,那么首先确认arr的中位数或者中点center,下面分为三种情况:
1假如arr[center]>key,说明key在arr中心左边范围;
2假如arr[center]<key,说明key在arr中心右边范围;
3假如arr[center]=key,说明key在arr中心。
范围每次缩小一半,写个while的死循环知道找到为止。
二分法查找非常快且非常常用,但是唯一要求是要求数组是有序的方法1:二分法的代码如下,先判断key是否在arr里然后再查询
def BinarySearch(arr, key): # 记录数组的最高位和最低位 min = 0 max = len(arr) - 1 if key in arr: # 建立一个死循环,直到找到key while True: # 得到中位数 # 这里一定要加int,防止列表是偶数的时候出现浮点数据 center = int((min + max) / 2) # key在数组左边 if arr[center] > key: max = center - 1 # key在数组右边 elif arr[center] < key: min = center + 1 # key在数组中间 elif arr[center] == key: print(str(key) + "在数组里面的第" + str(center) + "个位置") return arr[center] else: print("没有该数字!") if __name__ == "__main__": arr = [1, 6, 9, 15, 26, 38, 49, 57, 63, 77, 81, 93] while True: key = input("请输入你要查找的数字:") if key == " ": print("谢谢使用!") break else: BinarySearch(arr, int(key))
方法2:不提前判断key是否在序列里
def Dich(L,v): '''L为有序列表''' if isinstance(L,list) and sorted(L)==L: min=0 max=len(L) while True: mid=int((min+max)/2) if max != min: if v>a[mid]: min=mid+1 elif v<a[mid]: max=mid-1 else: return mid else: print('%s不在%s中'%(v,L)) #如果key不在arr里,最终会导致min=max,通过加此判断即可判断key是否在arr里 return None else: print('参数不符合二分法的要求') return None
更多相关内容 -
利用链表实现一个简单的学生成绩管理系统(附源码)
2022-04-02 22:53:06利用链表实现一个简单的学生成绩管理系统(附源码)1.系统需要实现的操作:
(1)学生成绩信息包括学号、姓名、性别、班级、高等数学成绩、大学英语成绩、C语言程序设计成绩和软件工程导论成绩等;
(2)系统的主要功能包括:学生成绩信息的创建、输出学生成绩信息、查询学生成绩、增加学生成绩、删除学生成绩。
2.目的:
1. 掌握线性表的定义;
2. 掌握线性表的基本操作,如建立、查找、插入和删除等。
3.成品
点个赞鼓励一下吧哈哈哈哈哈哈
代码设计
1.创建结构体
typedef struct { char id[20]; // 学号 char name[50]; // 姓名 char sex[20]; // 性别 char grade[20]; // 班级 char math[10]; // 数学 char english[10]; // 英语 char Cyuyan[10]; // C语言 char Daolun[10]; // 软工导论 } Student; typedef struct LNode { Student data; //数据域 struct LNode *next; // 指针域 }LNode,*LinkList;
2.输入信息:设置p指向新结点,r指向当前链表的尾结点,然后初始化,是链表为空,使用scanf函数,把输入的值分别存放在p->data中,然后r->next = p;r = r->next。
void input(LNode *head){ LinkList p,r; //p指向新结点,r指向当前链表的尾结点 int i,n; //n 为需要输入的学生人数 r = head; printf("请输入学生的人数:"); scanf("%d",&n); printf("请输入学生的信息"); for(i=1;i<=n;i++){ p = (LinkList)malloc(sizeof(LNode)); p->next = NULL; printf("学号\n"); scanf("%s",p->data.id); printf("姓名\n"); scanf("%s",p->data.name); printf("性别\n"); scanf("%s",p->data.sex); printf("班级\n"); scanf("%s",p->data.grade); printf("数学成绩\n"); scanf("%s",p->data.math); printf("英语成绩\n"); scanf("%s",p->data.english); printf("C语言程序设计成绩\n"); scanf("%s",p->data.Cyuyan); printf("软件工程导论成绩\n"); scanf("%s",p->data.Daolun); r->next = p; r = r->next; printf("---------------------------"); } printf("************************"); }
3.输出学生的信息:使用while循环遍历p中的值,然后输出。
*head){ LinkList p; p=head; printf("学号\t姓名\t性别\t班级\t数学\t英语\tC语言程序设计\t软件工程导论\n"); while(p->next!=NULL){ p = p->next; printf("%s\t%s\t%s\t%s\t%s\t%s\t%s\t\t%s\n",p->data.id,p->data.name,p->data.sex,p->data.grade,p->data.math,p->data.english,p->data.Cyuyan,p->data.Daolun); } }
4.通过学号查看学生的成绩:先获取用户输入的学号,然后做一个判断语句,判断列表是否为真,在使用strcmp函数对比输入的学号与数据哪一个匹配,然后输出。
//通过学号查看学生的成绩 void research_1(LNode *head,Student e) { LinkList p; p=head; printf("请输入查找的学号:\n"); scanf("%s",e.id); while((p->next!=NULL)&&strcmp(e.id,p->data.id)) { p=p->next; } printf("数学\t英语\tC语言程序设计\t软件工程导论\n"); printf("%s\t%s\t%s\t\t%s\n",p->data.math,p->data.english,p->data.Cyuyan,p->data.Daolun); }
5.插入学生的信息:获取用户要插入的位置,然后用p->data=e;p->next=r->next;r->next=p;插入。
//插入学生的信息· void insert(LNode *head,int i,Student e) { int k; LinkList p,r; r=head;k=0; printf("请输入你要插入的位置:\n"); scanf("%d",&i); printf("学号\n"); scanf("%s",e.id); printf("姓名\n"); scanf("%s",e.name); printf("性别\n"); scanf("%s",e.sex); printf("班级\n"); scanf("%s",e.grade); printf("数学成绩\n"); scanf("%s",e.math); printf("英语成绩\n"); scanf("%s",e.english); printf("C语言程序设计成绩\n"); scanf("%s",e.Cyuyan); printf("软件工程导论成绩\n"); scanf("%s",e.Daolun); while(r!=NULL&&k<i-1) { r=r->next; k=k+1; } if(r==NULL) { printf("插入失败!\n"); } p=(LinkList)malloc(sizeof(LNode)); p->data=e; p->next=r->next; r->next=p; printf("插入成功!\n"); }
6.删除:获取用户的要删除的学号,算法:p=r->next;r->next=p->next;*e=p->data;free(p);即可。
void delete_1(LNode *head,int i,Student *e) { LinkList p,r; int k; r=head;k=0; printf("请输入你要删除的位置:\n"); scanf("%d",&i); while(r->next!=NULL&&k<i-1) { r=r->next; k++; } if(r==NULL) { printf("删除失败!\n"); } p=r->next; r->next=p->next; *e=p->data; free(p); printf("删除成功!\n"); }
源代码:
#include "stdio.h" #include "stdlib.h" #include "string.h" typedef struct { char id[20]; // 学号 char name[50]; // 姓名 char sex[20]; // 性别 char grade[20]; // 班级 char math[10]; // 数学 char english[10]; // 英语 char Cyuyan[10]; // C语言 char Daolun[10]; // 软工导论 } Student; typedef struct LNode { Student data; //数据域 struct LNode *next; // 指针域 }LNode,*LinkList; //输入学生信息 void input(LNode *head){ LinkList p,r; //p指向新结点,r指向当前链表的尾结点 int i,n; //n 为需要输入的学生人数 r = head; printf("请输入学生的人数:"); scanf("%d",&n); printf("请输入学生的信息"); for(i=1;i<=n;i++){ p = (LinkList)malloc(sizeof(LNode)); p->next = NULL; printf("学号\n"); scanf("%s",p->data.id); printf("姓名\n"); scanf("%s",p->data.name); printf("性别\n"); scanf("%s",p->data.sex); printf("班级\n"); scanf("%s",p->data.grade); printf("数学成绩\n"); scanf("%s",p->data.math); printf("英语成绩\n"); scanf("%s",p->data.english); printf("C语言程序设计成绩\n"); scanf("%s",p->data.Cyuyan); printf("软件工程导论成绩\n"); scanf("%s",p->data.Daolun); r->next = p; r = r->next; printf("---------------------------"); } printf("************************"); } //输出学生的信息 void output(LNode *head){ LinkList p; p=head; printf("学号\t姓名\t性别\t班级\t数学\t英语\tC语言程序设计\t软件工程导论\n"); while(p->next!=NULL){ p = p->next; printf("%s\t%s\t%s\t%s\t%s\t%s\t%s\t\t%s\n",p->data.id,p->data.name,p->data.sex,p->data.grade,p->data.math,p->data.english,p->data.Cyuyan,p->data.Daolun); } } //通过学号查看学生的成绩 void research_1(LNode *head,Student e) { LinkList p; p=head; printf("请输入查找的学号:\n"); scanf("%s",e.id); while((p->next!=NULL)&&strcmp(e.id,p->data.id)) { p=p->next; } printf("数学\t英语\tC语言程序设计\t软件工程导论\n"); printf("%s\t%s\t%s\t\t%s\n",p->data.math,p->data.english,p->data.Cyuyan,p->data.Daolun); } //插入学生的信息· void insert(LNode *head,int i,Student e) { int k; LinkList p,r; r=head;k=0; printf("请输入你要插入的位置:\n"); scanf("%d",&i); printf("学号\n"); scanf("%s",e.id); printf("姓名\n"); scanf("%s",e.name); printf("性别\n"); scanf("%s",e.sex); printf("班级\n"); scanf("%s",e.grade); printf("数学成绩\n"); scanf("%s",e.math); printf("英语成绩\n"); scanf("%s",e.english); printf("C语言程序设计成绩\n"); scanf("%s",e.Cyuyan); printf("软件工程导论成绩\n"); scanf("%s",e.Daolun); while(r!=NULL&&k<i-1) { r=r->next; k=k+1; } if(r==NULL) { printf("插入失败!\n"); } p=(LinkList)malloc(sizeof(LNode)); p->data=e; p->next=r->next; r->next=p; printf("插入成功!\n"); } //删除 void delete_1(LNode *head,int i,Student *e) { LinkList p,r; int k; r=head;k=0; printf("请输入你要删除的位置:\n"); scanf("%d",&i); while(r->next!=NULL&&k<i-1) { r=r->next; k++; } if(r==NULL) { printf("删除失败!\n"); } p=r->next; r->next=p->next; *e=p->data; free(p); printf("删除成功!\n"); } void exit_1() { printf("退出成功!请按任意键结束!"); exit(0); } int main(){ LNode *head; head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; int select = -1; int i; Student e; printf("********************************************************************\n"); printf("* 1. 根据指定学生个数,逐个输入学生信息; *\n"); printf("* 2. 逐个显示学生表中所有学生的相关信息; *\n"); printf("* 3. 根据学号进行查找,返回此学生的成绩; *\n"); printf("* 4. 给定一个学生信息,插入到表中指定的位置; *\n"); printf("* 5. 删除指定位置的学生记录; *\n"); printf("* 6.退出。 *\n"); printf("********************************************************************\n"); printf("\n"); while(select!=0){ printf("请选择你要操作的选项:"); scanf("%d",&select); printf("\n"); switch(select) { case 1: input(head);break; case 2: output(head);break; case 3: research_1(head,e);break; case 4: insert(head,i,e);break; case 5: delete_1(head,i,&e);break; case 6: exit_1();break; } } return 0; }
-
链表简单实现(增删查改)
2021-12-26 21:48:41关于链表的原理已经有一篇链表文章写的很详细了,这篇文章主要侧重于代码的实现,主要使用go实现。链表
关于链表的原理已经有一篇链表文章写的很详细了,这篇文章主要侧重于代码的实现,主要使用go实现。
单链表实现
package List type listNode struct { val int next *listNode } func newNode(val int) *listNode { node := new(listNode) node.val = val node.next = nil return node } // NewList 初始化一个不带头结点的链表 func NewList(vals []int) *listNode { var fistNode *listNode var curNode *listNode for _, v := range vals { node := newNode(v) if curNode == nil { fistNode = node curNode = fistNode continue } curNode.next = node curNode = curNode.next } return fistNode } // FistAdd 头插 func FistAdd(fistNode *listNode, val int) *listNode{ if fistNode == nil { return fistNode } node := newNode(val) node.next = fistNode return node } // LastAdd 尾插 func LastAdd(fistNode *listNode, val int) { if fistNode == nil { return } curNode := fistNode for curNode.next != nil { curNode = curNode.next } node := newNode(val) curNode.next = node return } // IndexValAdd 在第一个指定值后插入,若没有,在链表尾部插入 // fistNode 链表第一个节点, indexVal 目标节点值, val 新节点值 func IndexValAdd(fistNode *listNode, indexVal, val int) { if fistNode == nil { return } curNode := fistNode for curNode.next != nil && curNode.val != indexVal { curNode = curNode.next } node := newNode(val) nextNode := curNode.next node.next = nextNode curNode.next = node return } // ChangVal 更改目标节点值,若没有,不做改动 // fistNode 链表第一个节点, indexVal 目标节点值, val 目标值 func ChangVal (fistNode *listNode, indexVal, tarVal int) { if fistNode == nil { return } curNode := fistNode for curNode != nil && curNode.val != indexVal { curNode = curNode.next } // 判断是走到最后都没有找到对应值还是找到对应值 if curNode == nil{ return } curNode.val = tarVal return } // DelNode 删除指定节点,若没有则不删除 func DelNode(fistNode *listNode, indexVal int) { if fistNode == nil { return } curNode := fistNode // 查找要删除节点的前一个节点 for curNode.next != nil { nextNode := curNode.next if nextNode.val == indexVal { break } curNode = curNode.next } if curNode.next == nil { return } nextNode := curNode.next curNode.next = nextNode.next } // Show 不带头节点查 func Show(node *listNode) []int { if node == nil { return []int{} } valSlice := make([]int, 0, 4) curNode := node for curNode != nil { valSlice = append(valSlice, curNode.val) curNode = curNode.next } return valSlice }
验证代码
package main import ( "Data/List" "fmt" ) func main() { // 初始化一个链表 fistNode := List.NewList([]int{1, 2, 3, 4, 5}) fmt.Println("初始化一个链表 :",List.Show(fistNode)) // 对链表进行头插 fistNode = List.FistAdd(fistNode, 0) fmt.Println("对链表进行头插 0 :",List.Show(fistNode)) // 对链表进行尾插 List.LastAdd(fistNode, 6) fmt.Println("对链表进行尾插 6 :",List.Show(fistNode)) // 删除指定节点 List.DelNode(fistNode, 3) fmt.Println("删除指定节点 3 :",List.Show(fistNode)) List.DelNode(fistNode, 3) fmt.Println("删除指定节点 3 :",List.Show(fistNode)) List.DelNode(fistNode, 3) fmt.Println("删除指定节点 7 :",List.Show(fistNode)) // 在第一个指定值后插入 List.IndexValAdd(fistNode, 4, 41) fmt.Println("在第一个指定值后插入,若没有,在链表尾部插入 4 41 :",List.Show(fistNode)) List.IndexValAdd(fistNode, 7, 42) fmt.Println("在第一个指定值后插入,若没有,在链表尾部插入 7 42 :",List.Show(fistNode)) // 更改目标节点值 List.ChangVal(fistNode, 4, 40) fmt.Println("更改目标节点值 4 40 :",List.Show(fistNode)) List.ChangVal(fistNode, 7, 43) fmt.Println("更改目标节点值 7 43 :",List.Show(fistNode)) }
效果图
循环链表实现
package List import "fmt" func newCircleNode(val int) *listNode { node := new(listNode) node.val = val node.next = node return node } func NewCircleList(vals []int) *listNode { var fistNode *listNode var curNode *listNode for _, v := range vals { if curNode == nil { fistNode = newCircleNode(v) curNode = fistNode continue } node := newCircleNode(v) node.next = fistNode curNode.next = node curNode = curNode.next } return fistNode } func isLastNode(fistNode *listNode, node *listNode) bool { return node.next == fistNode } // CircleFistAdd 头插 func CircleFistAdd(fistNode **listNode, val int) { if fistNode == nil { return } curNode := *fistNode for !isLastNode(*fistNode, curNode) { curNode = curNode.next } node := newCircleNode(val) curNode.next = node node.next = *fistNode *fistNode = node } // CircleLastAdd 尾插 func CircleLastAdd(fistNode *listNode, val int) { if fistNode == nil { return } curNode := fistNode for !isLastNode(fistNode, curNode) { curNode = curNode.next } node := newCircleNode(val) node.next = fistNode curNode.next = node } // CircleIndexValAdd 在第一个指定值后插入,若没有,在链表尾部插入 func CircleIndexValAdd(fistNode *listNode, indexVal,val int) { if fistNode == nil { return } curNode := fistNode for !isLastNode(fistNode, curNode) && curNode.val != indexVal { curNode = curNode.next } node := newCircleNode(val) node.next = curNode.next curNode.next = node } // CircleChangVal 更改目标节点值,若没有,不做改动 func CircleChangVal(fistNode *listNode, indexVal, tarVal int) { if fistNode == nil { return } curNode := fistNode for curNode.val != indexVal && !isLastNode(fistNode, curNode) { curNode = curNode.next } if curNode.val == indexVal { curNode.val = tarVal return } fmt.Printf("节点 %d 不存在\n", indexVal) } // CircleDelNode 删除指定节点,若没有则不删除 func CircleDelNode(fistNode *listNode, indexVal int) { if fistNode == nil { return } curNode := fistNode for curNode.next.val != indexVal && !isLastNode(fistNode, curNode) { curNode = curNode.next } if curNode.next.val == indexVal { curNode.next = curNode.next.next return } fmt.Printf("没有该节点 %d \n", indexVal) } // CircleShow 查看链表 func CircleShow(fistNode *listNode) { if fistNode == nil { return } curNode := fistNode for { if isLastNode(fistNode, curNode) { fmt.Printf("val:%d next:%d", curNode.val, curNode.next.val) break } fmt.Printf("val:%d next:%d -> ", curNode.val, curNode.next.val) curNode = curNode.next } fmt.Println() }
验证代码
package main import ( "Data/List" "fmt" ) func main() { // 初始化一个环形链表 circleFistNode := List.NewCircleList([]int{1, 2, 3}) fmt.Println("初始化一个链表 :") List.CircleShow(circleFistNode) // 对链表进行头插 List.CircleFistAdd(&circleFistNode, 0) fmt.Println("对链表进行头插 0:") List.CircleShow(circleFistNode) // 对链表进行尾插 List.CircleLastAdd(circleFistNode, 4) fmt.Println("对链表进行尾插 4 :") List.CircleShow(circleFistNode) // 删除指定节点 fmt.Println("删除指定节点 3 :") List.CircleDelNode(circleFistNode, 3) List.CircleShow(circleFistNode) fmt.Println("删除指定节点 3 :") List.CircleDelNode(circleFistNode, 3) List.CircleShow(circleFistNode) fmt.Println("删除指定节点 7 :") List.CircleDelNode(circleFistNode, 7) List.CircleShow(circleFistNode) // 在第一个指定值后插入 circleFistNode = List.NewCircleList([]int{1, 2, 3}) fmt.Println("初始化一个链表 :") List.CircleShow(circleFistNode) List.CircleIndexValAdd(circleFistNode, 2, 41) fmt.Println("在第一个指定值后插入,若没有,在链表尾部插入 2 41 :") List.CircleShow(circleFistNode) List.CircleIndexValAdd(circleFistNode, 7, 42) fmt.Println("在第一个指定值后插入,若没有,在链表尾部插入 7 42 :") List.CircleShow(circleFistNode) // 更改目标节点值 circleFistNode = List.NewCircleList([]int{1, 2, 3, 4}) fmt.Println("初始化一个链表 :") List.CircleShow(circleFistNode) fmt.Println("更改目标节点值 3 40 :") List.CircleChangVal(circleFistNode, 3, 40) List.CircleShow(circleFistNode) fmt.Println("更改目标节点值 7 43 :") List.CircleChangVal(circleFistNode, 7, 43) List.CircleShow(circleFistNode) // }
效果图
-
C++中实现一个简单的单向链表
2016-09-17 21:00:04最近在linux了一个简单的单向链表,直接上代码 链表头文件 list.h #ifndef _LIST_H_ #define _LIST_H_ typedef int T; template class List { private: struct Node { T data; Node* next...最近在linux了一个简单的单向链表,直接上代码
链表头文件 list.h
#ifndef _LIST_H_
#define _LIST_H_
typedef int T;
template<typename T>
class List
{
private:
struct Node
{
T data;
Node* next;
Node(const T& d=T()):data(d),next(NULL){} //零初始化
};
Node* head;//头指针,用来保存头节点的地址
int len;
public:
List():head(NULL),len(0){}
List(const List& l);
void operator=(const List& l);
~List();
T getElementAtIndex(int index)const;//取得链表中指定位置的元素值
List<T>& push_front(const T& d);//前插
List<T>& push_back(const T& d); //尾插
int size()const;//获取链表中节点个数
Node*& getptr(int pos); //在链表中找指向指定位置的指针
List<T>& insert(const T& d,int pos); //在任意位置插入
void travel()const; //遍历
void clear(); //清空链表
void erase(int pos); //删除链表中指定位置的元素
int find(const T& d)const; //查找指定数值的元素在链表中出现的位置
void remove(const T& d); //删除链表中指定的元素
void set(int pos,const T& d);
bool empty()const;
const T& front()const;
const T& back()const;
void reverse();//链表元素倒置
};
#endif
链表实现文件 list.cpp
#include <iostream>
#include <string>
#include "list.h"
using namespace std;
template<typename T>
List<T>::List(const List<T>& l)
{
len = l.len;
Node* items[len];
for(int i=0;i<len;i++)
{
items[i] = new Node(l.getElementAtIndex(i));
}
for(int i=0;i<len-1;i++)
{
items[i]->next = items[i+1];
}
head = items[0];
}
template<typename T>
void List<T>::operator=(const List<T>& l)
{
clear();
len = l.len;
Node* items[len];
for(int i=0;i<len;i++)
{
items[i] = new Node(l.getElementAtIndex(i));
}
for(int i=0;i<len-1;i++)
{
items[i]->next = items[i+1];
}
head = items[0];
}
template<typename T>
List<T>::~List()
{
clear();
}
//取得链表中指定位置的元素值
template<typename T>
T List<T>::getElementAtIndex(int index)const
{
if(index < 0 || index >= len) throw "索引位置越界";
if(index == 0) return head->data;
Node* p = head;
for(int i=1;i<index;i++)
{
p = p->next;
}
return p->next->data;
}
//前插
template<typename T>
List<T>& List<T>::push_front(const T& d)
{
insert(d,0);
return *this;
}
//后插
template<typename T>
List<T>& List<T>::push_back(const T& d)
{
insert(d,len);
return *this;
}
//获取链表中节点个数
template<typename T>
int List<T>::size()const
{
return len;
}
//在链表中找指向指定位置的指针
template<typename T>
typename List<T>::Node*& List<T>::getptr(int pos)
{
if(pos < 0 || pos > len) pos = 0;
if(pos == 0) return head;
Node* p = head;
for(int i=1;i<pos;i++)
{
p = p->next;
}
return p->next;
}
//在任意位置插入节点
template<typename T>
List<T>& List<T>::insert(const T& d,int pos)
{
Node*& pn = getptr(pos);
Node* p = new Node(d);
p->next = pn;
pn = p;
++len;
return *this;
}
//遍历
template<typename T>
void List<T>::travel()const
{
Node* p = head;
while(p)
{
cout << p->data << ' ';
p = p->next;
}
cout << endl;
}
//清空链表
template<typename T>
void List<T>::clear()
{
while(head)
{
Node* p = head->next;
delete head;
head = p;
}
len = 0;
}
//删除链表中指定位置的节点
template<typename T>
void List<T>::erase(int pos)
{
if(pos < 0 || pos >= len) return;//有效位置为0~len-1
Node*& pn = getptr(pos);
Node* p = pn;
pn = pn->next;
delete p;
--len;
}
//查找指定数值的节点在链表中出现的位置
template<typename T>
int List<T>::find(const T& d)const
{
Node* p = head;
int pos = 0;
while(p)
{
if(p->data == d)
return pos;
else
p = p->next;
++pos;
}
return -1;
}
//删除链表中指定数值的节点
template<typename T>
void List<T>::remove(const T& d)
{
int pos;
while((pos = find(d))!= -1)
{
erase(pos);
}
}
//修改指定位置的节点数据
template<typename T>
void List<T>::set(int pos,const T& d)
{
if(pos < 0 || pos >= len) return;
getptr(pos)->data = d;
}
//判断链表是否为空
template<typename T>
bool List<T>::empty()const
{
return head == NULL;
}
//取得链表中第一个节点数据
template<typename T>
const T& List<T>::front()const
{
if(empty()) throw "空";
return head->data;
}
//取得链表中最后一个节点数据
template<typename T>
const T& List<T>::back()const
{
if(empty()) throw "空";
Node* p = head;
while(p->next)
{
p = p->next;
}
return p->data;
}
//将链表中的元素倒置
template<typename T>
void List<T>::reverse()
{
if(head == NULL) return;
Node *pre,*cur,*next;
pre = head;
cur = head->next;
while(cur)
{
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
head->next = NULL;
head = pre;
}
template class List<T>; // 显式实例化
链表测试文件 listTest.cpp#include <iostream>
#include "list.h"
//typedef int T;
using namespace std;
int main()
{
List<T> l;
List<T> m;
l.push_front(5); //5
l.push_front(8); //8 5
l.push_front(20);// 20 8 5
l.insert(9,2); // 20 8 9 5
l.insert(8,100); //6 20 8 9 5
l.insert(11,-10);//11 6 20 8 9 5
l.insert(9,2);//11 6 1 20 8 9 5
l.push_back(10).push_back(19);//11 8 9 20 8 9 5 10 19
l.travel();
l.reverse();
l.travel();
l.remove(8);
l.remove(9);
l.set(1,33);
l.set(l.find(19),-8);
// cout << l.front() << " " << l.back() << endl;
l.travel(); // 11 33 5 10 -8
// while(!l.empty()) l.erase(0);
// cout << l.size() << endl;
// cout << l.getElementAtIndex(0) << endl;
m.insert(-9,0);
m.insert(13,1);
m.push_front(-5);
m.push_back(2);
cout << "========m链表原始值======" << endl;
m.travel();// -5 -9 13 2
m = l;
cout <<"==========将链表m中元素倒置==========" << endl;
m.reverse();
m.travel();
cout <<"===========程序结束======" << endl;
return 0;
}
-
C语言-------实现一个简单的单向链表
2017-02-09 20:12:54编写一个链表程序,在程序中实现简单的功能#include #include struct node{ int num; char name[20]; struct node* next; //指向下一个地址的指针 }; //声明一个链表,此时内存不分配内存 typedef struct node... -
【Java基础】【写一个简单的链表】
2018-01-11 20:59:201. 定义一个Link类和一个Node类,其中Node类为Link类的内部类(避免了反复的getter和setter方法) Link类的目的是进行节点创建 Node类的目的是进行数据和节点链接,并且Node只能为Link调用,需要定义为private 再... -
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
2020-07-29 10:23:04本文将来讲解一下一种常见的线性数据结构—链表,因为链表和数组一样都是一种线性的数据结构,但是它俩的实现原理是完全不同的,所以在讲解链表之前,我们来回顾一下 数组 结构。 -
【数据结构与算法】详解什么是双向链表,并用代码手动实现一个双向链表
2020-08-02 10:30:43上一篇文章讲解了链表的相关知识,并用代码实现了一个链表结构。那么本文将介绍一下另一种特殊的链表结构,叫做 双向链表。 顾名思义,普通的链表都是从 head 开始往后遍历结构内的元素,那么双向链表就是既可以从头... -
实现一个简单的哈希表(数组 + 链表)
2019-11-22 16:02:141、什么是哈希表 2、主要方法的逻辑和代码实现 1)put()方法 2)get()方法 3) remove()方法 1、哈希表 hash,哈希表这个词,以前接触过好多次了,对哈希表了解最多的就是,这玩意儿也是...在本文中,我用的是一个数... -
使用线程安全型双向链表实现简单 LRU Cache 模拟
2021-11-16 09:11:22使用线程安全型双向链表实现简单 LRU Cache 模拟目录????博主介绍前言1、动机1.1、要解决的问题2、系统设计2.1、系统总体框架2.2、系统功能模块2.3 系统整体流程3、数据结构设计4、关键技术与系统实现4.1、生成访问... -
Java实现双向链表及其常规操作
2022-03-16 17:35:43数据结构链表的学习结束了,我已经将重要的三种链表的简单实现整理并发布在了博客上,希望我的文章...所以,从双向链表任意一个结点开始,都可以很方便的访问它的前驱结点和后继结点。 简易的双向链表模型 目. -
python数据结构链表之单向链表(实例讲解)
2020-09-21 06:00:50下面小编就为大家带来一篇python数据结构链表之单向链表(实例讲解)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧 -
数据结构-链表(含全部实现代码)
2022-03-12 17:01:04一个链表由n个节点组成,每一个节点都是一个结构体,这个结构体里的一个成员是该节点存储的数据,另一个成员是指向下一个节点的指针。 其结构如下 上图只是一种结构的链表,并不是所有的链表都是这样的结构,在实际... -
【C语言数据结构】双向循环链表
2022-03-06 22:05:00一、双向循环链表 循环结构 1.双向循环链表头文件及函数声明 2.初始化 1.结点构造 2.初始化函数 3.结点申请 4.数据插入 1.按位置插入 2.尾插 3.头插 5.查找 6.数据删除 1.按位置删除 2.按值删除 3.尾... -
C++ 入门算法,新手必看之:单向“链表”(一)
2020-03-22 12:50:47俗话说得好,不懂链表的程序员,不配称为C/C++程序员。 为什么呢? 链表的存储主要依据指针来实现,而指针又是C/C++...链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不必须相邻,那么,怎么表... -
C语言之链表:单向链表,循环链表,双向链表
2020-11-22 18:21:06的要求非常高,比如说我们申请一个100M大小的数组,而如果我们的内存可用空间大于100M,但是没有连续的100M可用空间,那即便是我们的内存空间充足,在申请空间时也会申请失败 而对于链表来说,他对内存空间的要求就... -
【数据结构】链表
2022-03-12 16:41:05链表 -
【Java实现链表操作】 万字肝爆 !链表的图文解析(包含链表OJ练习解析)
2021-09-01 09:46:33这里写目录标题链表的概念及结构链表的实现实现链表的函数操作一、实现链表的打印函数二、实现得到单链表的长度函数三、查找是否包含关键字key是否在单链表当中三、链表头插法三、链表尾插法四、任意位置插入,第一... -
LeetCode-题目详解:链表
2021-05-13 15:20:00将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] ... -
是什么让普通的链表也能达到二分查找的效率,你知道吗?
2021-03-10 17:56:02由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。 优点 链表结构可以充分利用计算机内存空间,实现灵活的内存... -
动画:面试如何轻松手写链表?
2019-09-26 08:10:31暑假参加的第一个公司的就让我手写一个双向链表,并完成插入数据和删除数据的操作。当时我很蒙蔽,懵逼的不是思路,而是手写,虽然写出来了,但是很多边界条件和代码规范自我感觉不好,所以有了这些细心的总结。那么... -
链表是什么?有多少种链表?时间复杂度是?
2021-03-13 09:32:34由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表... -
(LeetCode 35 and 34)查找第一个大于(等于)target的位置 [二分查找解题思路模板]
2018-09-07 13:18:06给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1: 输入: [1,3,5,6], 5 输出: 2 示例 2: ... -
数据结构与算法详解——链表篇(附c++实现代码)
2022-05-01 16:00:49链表详解及完整实现 -
一文带你看懂链表的奥秘 手把手教你实现链表的各项操作
2020-03-18 13:45:16很多人刚开始学习数据结构与算法这门课的时候都对链表有一些恐惧、懵逼,看不懂书上要表达的意思,照抄书上代码却又运行不起来,真的是10行代码9个error,把小伙伴们折磨的苦不堪言,今天博主就带领大家来探究一下... -
数组和链表
2020-07-27 15:56:261.1 在内存中,数组是一块连续的区域 1.2 数组需要预留空间 在使用前需要提前申请所占内存的大小,如果提前不知道需要的空间大小时,预先申请就可能会浪费内存空间,即数组的空间利用率较低。注:数组的空间在编译... -
Java实现简单的链表-面向初学者
2018-07-15 02:24:24就先用JAVA实现一个简单链表好了,还是使用最原始的C语言实现的思路,想来语言变了实现方式大同小异吧。后续可能会不断实现不一样的数据结构。 节点 先确定节点数据结构(一个节点一个数字好了),后续慢慢一点点... -
数据结构:链表-笔记
2020-06-16 16:11:311、在链表中进行操作比在顺序表中进行操作效率高 正确答案: D 你的答案: B (错误) 顺序查找 折半查找 分块查找 插入 2、在______运算中,使用顺序表比链表好 正确答案: C 你的答案: A (错误) 插入 删除 根据序号查找... -
详解结构体与链表
2020-11-12 20:06:46链表的创立、增删查改插 链表的创立 链表的插入元素 链表的删除元素 链表的查找元素 链表的更新元素 链表的添加元素 由于博主水平有限,所以博客中难免会出现错误,如果发现,可以加以指正,博主会在第一时间修改。... -
Java数据结构之链表及实现
2021-05-16 22:02:13链表由一序列的结点(链表中的每一个元素成为结点)组成。 结点API设计: 类名 Node 构造方法 Node(T t,Node next) 创建Node对象 成员变量 T item:存储数据 Node next :指向下一个结点 ...