数据结构---数组与链表
程序员文章站
2024-03-23 09:53:46
...
数组与链表
文章目录
1.数组
1.1实现一个支持动态扩容的数组
- [思想]：所谓动态数组，就是可以根据需要，可以动态的增长数组的空间大小。我的思路很简单，就是增加一个新的数组，将原数组中的数据复制到新的数组中，再增加新的数据，同时删除原来旧的数组，释放空间。
代码实现：语言C++
#include<iostream>
// 实现一个支持动态扩容的数组
using namespace std;
int main()
{
int num,i,addNum;
cout<<"输入初始数组长度：";
cin>>num;
int *array=new int[num];
cout<<"输入数组内容(数字):";
//输入num个数字
for(i=0;i<num;i++)
cin>>array[i];
cout<<"输入需要增加的数组长度为：";
cin>>addNum;
//下面对数组进行扩容,并输入拓展的数组内容
int *addArray=new int[num+addNum];
//将原数组中的数据复制到新数组
for(i=0;i<num;i++)
addArray[i]=array[i];
cout<<"请输入增加的数组内容(数字)：";
for(i=0;i<addNum;i++)
cin>>addArray[num+i];
//释放不用的空间
delete []array;
array=addArray;
num=num+addNum;
cout<<"拓展后数组中的长度为"<<num<<endl;
cout<<"内容为："<<endl;
for(i=0;i<num;i++)
cout<<array[i]<<" ";
cout<<endl;
delete []array;
return 0;
}
1.2实现一个大小固定的有序数组，支持动态增删改操作
#include<iostream>
using namespace std;
const int initialLen = 10; //设数组初始长度为10
template <class T>
class Array{
public:
Array(int len=initialLen){
T *p=new T[len];
_data=p;
_capacity=len;
_size=0;
}
//打印
void print(){
cout << "Array: ";
cout << "Capacity = " << _capacity << ", " << "Size = " << _size << endl;
cout << '[';
for (int i = 0; i < _size; ++i){
cout << _data[i];
if (i != _size - 1){
cout << ',';
}
}
cout << ']' << endl;
}
//扩容
void resize(int len){
T *p=new T[len];
for(int i=0;i<_size;i++){
p[i]=_data[i];
}
delete []_data;
_data=p;
_capacity=len;
}
//增删改
void add(int index,T num);
T remove(int index);
void modify(int index,T num);
private:
T *_data; //数组数据
int _capacity; //数组容量
int _size; //数组大小
};
//增加操作 添加到任意位置
template <typename T>
void Array<T>::add(int index,T num){
if(index < 0 || index > _size){
cout<<"添加位置非法"<<endl;
return;
}
if(_size >= _capacity){
resize(2 * _capacity);
}
for(int i=_size;i>index;--i){
_data[i]=_data[i-1]; //后移
}
_data[index]=num;
_size++;
}
//删除 任意位置元素
template <class T>
T Array<T>::remove(int index){
if(index < 0 || index >= _size){
cout << "删除位置非法！" << endl;
return 0;
}
T res=_data[index];
_size--;
for(int i=index;i<_size;++i){
_data[i]=_data[i+1]; //前移
}
if (_size < _capacity / 4){
resize(_capacity / 2);
}
return res;
}
//修改
template <class T>
void Array<T>::modify(int index,T num){
if(index < 0 || index >= _size){
cout << "修改位置非法！" << endl;
return;
}
_data[index]=num;
}
int main()
{
Array<int> array(10);
//测试增加
array.add(0,1);
array.add(1,2);
array.add(2,3);
array.add(3,4);
array.print();
//测试删除
array.remove(3);
array.print();
//测试修改
array.modify(2,7);
array.print();
return 0;
}
1.3实现两个有序数组合并为一个有序数组
using namespace std;
#define N1 6
#define N2 4
int main()
{
int array1[N1]={0,2,4,6,8,10};
int array2[N2]={1,3,5,7};
int array3[N1+N2];
int i=0,j=0,k=0;
while(i<N1 && j<N2){
if(array1[i]<array2[j])
array3[k++]=array1[i++];
else
array3[k++]=array2[j++];
}
//若1数组已经到达末尾，直接把2数组剩余元素拷贝到3数组即可
if(i==N1){
while(j<N2)
array3[k++]=array2[j++];
}
//若2数组已经到达末尾，直接把1数组剩余元素拷贝到3数组即可
if(j==N2){
while(i<N1)
array3[k++]=array1[i++];
}
for(int m=0;m<(N1+N2);m++){
cout<<array3[m]<<" ";
}
return 0;
}
1.4 leetcode-两数之和(1)、Happy Number(202)(用哈希思想实现！)
哈希表，又名散列表，是key-value类型的数据结构，通过关键码值直接进行访问。
通过散列函数进行键和数组的下标映射从而决定该键值应该放在哪个位置，哈希表可以理解为一个键值需要按一定规则存放的数组，
而哈希函数就是这个规则。算法中时间和空间是不能兼得的，哈希表就是一种用合理的时间消耗去减少大量空间消耗的操作，这取决于具体的功能要求
哈希表的思想是：用一个与集合规模差不多大的数组来存储这个集合，将数据元素的关键字映射到数组的下标，这个映射称为“散列函数”，数组称为“散列表”。查找时，根据被查找的关键字找到存储数据元素的地址，从而获取数据元素。
1.4.1LeetCode: Two Sum 求解两数之和
题目链接
代码实现：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> twoSum;
map<int,int> tmap;
for(int i=0;i<nums.size();++i){
if(tmap.count(nums[i])!=0){
twoSum.push_back(tmap[nums[i]]);
twoSum.push_back(i);
break;
}
tmap[target - nums[i]]=i;
}
return twoSum;
}
};
1.4.2 LeetCode 202 Happy Number
//哈希思想实现
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> v;
while(v.find(n)==v.end()){
v.insert(n);
int temp=0;
while(n){
tmp+=(n%10)*(n%10);
n/=10;
}
n=tmp;
if(n==1)
return true;
}
return false;
}
};
2.链表
2.1实现单链表、循环链表、双向链表，支持增删操作
注：由于时间有限，这里只完成了单链表，剩下的加班补上~
- 2.1.1单链表：
//定义类
class node
{
public:
int data;
node *next;
};
class linklist
{
node *h;
void head(linklist &l,int n); //头插法建表
void insert(linklist &l,int n,int num); //插入单结点
void del(linklist &l,int n); //单结点删除
}
//头插法建表
void head(linklist &l,int n)
{
node *p;
p=new node;
l.h=p; //定义头结点和投指针
p->data=n; //头指针的数据域是结点个数
p->next=NULL; //最末结点的后继必须为空
for(int i=0;i<n;i++) //创建n个新结点
{
node *q=new node;
cin>>q->data;
q->next=p->next;
p->next=q; //每个新结点都放在头结点后面
}
}
//插入单结点
void insert(linklist &l,int n,int num)
{
node *p=l.h;
for(int i=0;i<n;i++)
{
p=p->next;
} //找到插入的位置
node *q=new node;
q->next=p->next;
p->next=q;
q->data=num;
}
//单结点删除
void del(linklist &l,int n)
{
node *p=l.h;
for(int i=0;i<n-1;i++)
{
p=p->next;
} //找到删除的位置
node *q=p;
q=q->next;
p->next=q->next;
delete q; //释放空间
}
2.2实现单链表反转
单链表反转，用头插法即可实现，代码如下：
void reverse(linklist l)
{
node *p=l.h;
node *q;
p=p->next;
while(p->next)
{
q=p->next;
p->next=q->next;
q->next=l.h->next;
l.h->next=q;
}
}
2.3实现两个有序的链表合并为一个有序链表
LeetCode-21
题目链接
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode temp_head(0);
ListNode *ptr = &temp_head;
while(l1&&l2){
if(l1->val < l2->val){
ptr->next = l1;
l1 = l1->next;
}
else{
ptr->next = l2;
l2 = l2->next;
}
ptr = ptr->next;
}
if(l1){ //l1有剩余
ptr->next = l1;
}
if(l2){
ptr->next = l2;
}
return temp_head.next;
}
};
2.4实现求链表的中间结点
LeetCode-876
题目链接
- 题目描述： 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode*cur=head->next;
ListNode*prev=head;
while(cur)
{
if(cur->next)
{
cur=cur->next->next;
}
else
{
cur=cur->next;
}
prev=prev->next;
}
return prev;
}
};
数组和链表对应的 LeetCode 练习题未完待续···