注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

刘邓

每天收获一点点-目标:富足

 
 
 

日志

 
 

基础从链表抓起  

2012-07-14 10:23:02|  分类: 基础类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
基础从链表抓起,小小链表中还是蕴藏着巨大的财富的:指针运算,取值,取值,排序等等内容。
这次链表实践的3大收获:
1.多个指针指向同一位置的时候,一定要注意每个指针对值的作用。
2.切勿将条件判断写成赋值语句!!!切记!!切记!!!
3.错误的引用局部变量的地址,在对链表排序时,我视图通过将临时链表的首位地址赋值给待排序链表,结果提示存储器错误,突然想到《深入理解计算机系统》中常见的地址操作错误中有错误引用局部变量的地址:因为局部变量在函数调用结束以后就消散了,他们没有对应在实际存储器上的存储单元。
基础从链表抓起 - 刘邓 - 刘邓
 

//main.cpp 主要用来完成模块测试
#include"list.h"
using namespace std;

int main()
{
CList list;
for(int i =0;i<15;++i)
list.insert(rand()%15);
list.print();
list.sort();
list.print();
if(list.find(5)) cout<<"Find It!"<<endl;
else cout<<"Not Find It!"<<endl;
cout<<list.find(3)->next
<<endl;
list.insert(list.find(3),3);
list.insert(list.begin(),3);
list.insert(list.end(),3);
list.del(list.begin());
list.del(list.end());
list.del(list.find(5));
list.print();
cout<<list.size;
return 0;
}

//list.h

#ifndef LIST_H
#define LIST_H
#include <iostream>
#include<cstdlib>
using namespace std;
class CList
{
public:
struct CNode{
int val;
CNode *next;
};
size_t size;
CNode *head;
CNode *tail;

public:
CList();
CList(int n);//构造一个长度为n值为0的链表
CList(int n,int v);//构造一个长度为n,每个值均为v的链表
~CList();
void print();//默认全部输出
void print(CNode* begin,CNode *end);//打印指定区间的值
void sort();//默认从小到大排列
void sort(CNode* begin,CNode *end);//将指定区间按照从小到大排列
CNode* find(int v);//在链表中查找v,如果找到返回指向找到节点的地址 否则返回NULL
CNode* begin();//获取链表元素首地址
CNode* end();//获取链表元素尾地址
void insert(int v);//默认从尾部插入
void insert(CNode* p,int v);//在p后面插入
void del(CNode* p);//删除指定位置的元素
void cleanup();//清空元素
};
CList::CList()
{
size = 0;
head = tail = NULL;
}
CList::CList(int n)
{
head = new CNode;
head->val = 0;
CNode* tmp1;
CNode* tmp2;
tmp1 = head;
for(int i =0;i<n-1;++i)
{
tmp2 = new CNode;
tmp2->val =0;
tmp1->next = tmp2;
tmp1 = tmp2;
}
tmp2->next = NULL;
tail = tmp2;
size = n;
}
CList::CList(int n,int v)
{
head = new CNode;
head->val = v;
CNode *tmp1 = head;
CNode *tmp2;
for(int i = 0;i<n-1;++i)
{
tmp2 = new CNode;
tmp2->val =v;
tmp1->next = tmp2;
tmp1 = tmp2;
}
tmp2->next =NULL;
tail = tmp2;
size = n;
}
CList::~CList()
{
CNode *tmp1 = head;
CNode *tmp2;
while(tmp1->next!=NULL)
{
tmp2 = tmp1;
tmp1 = tmp2->next;
delete tmp2;
}
}
void CList::print()
{
if(size ==0){cout<<"NULL"<<endl;return ;}
CNode *p = head;
while(1)
{
std::cout<<p->val<<" ";
p = p->next;
if(p->next ==NULL){cout<<p->val;break;}
}
std::cout<<std::endl;
}
void CList::insert(int v)
{
CNode *tmp = new CNode;
if(head == NULL) {head = tmp;tail = tmp;};
tmp->val = v;
tmp->next = NULL;
tail ->next = tmp;
tail = tmp;
size += 1;
}
void CList::insert(CNode* Lp,int v)
{
CNode *p = Lp;
if(p->next == NULL) {(*this).insert(v);return ;} //判断条件写成赋值语句伤不起啊!!
CNode *tmp = new CNode;
tmp->val = v;
tmp->next = p->next;
p->next = tmp;
size += 1;
}
void CList::del(CNode* p)
{
if(p == head) {head =head->next;size-=1;return;}
CNode *tmp = head;
while(1)
{
if(tmp->next ==p)
{
if(tmp->next==tail)
{
if(p == tail)
{
tmp->next =NULL;
tail = tmp;
size -=1;
return ;
}
else {cout<<"条件错误!"<<endl;return;}
}
tmp->next = p->next;
size -=1;
return;
}
tmp = tmp->next;
}
}
CList::CNode* CList::find(int v)
{
CNode *tmp = head;
while(1)
{
if(tmp ->val == v) return tmp;
tmp =tmp->next;
if(tmp->next == NULL){if(tmp->val == v) return tmp;break;}
}
return NULL;
}
CList::CNode* CList::begin()
{
return head;
}
CList::CNode* CList::end()
{
return tail;
}
void CList::cleanup()
{
size = 0;
head = tail = NULL;
}
/*
排序的思想是:
先将链表清空,将链表的值通过指针保存在另外一个临时的链表p中。
遍历临时链表找出最小的元素插入到链表中,然后删除p中最小值所在节点
循环上述过程即可完成排序
*/
void CList::sort()
{
int min = head->val;
CNode* tmp ;
CNode* tmp1 ;
CList p;
p.head =head;
p.tail = tail;
p.size = size;
int tmpsize = size;
cleanup();
for(int i = 0;i<tmpsize;i++)
{
tmp = p.head;
tmp1 = p.head;
min = p.head->val;
while(1)
{
if(tmp->val<min) {min = tmp->val;tmp1 = tmp;}
tmp = tmp->next;
if(tmp == p.tail) {if(min>tmp->val){min = tmp->val;tmp1 = tmp;} break; }
}
insert(min);
p.del(tmp1);
if(p.tail == p.head) {insert(p.head->val);break;}
}
}
#endif

  评论这张
 
阅读(115)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018