C++链表实现
一般线性链表类的C++实现
出处：www.examlink.com 作者：小罗 日期：2007年01月24日 14时48分
以下的C++类LinkList实现了线性链表的一般操作。可以直接在其他的程序中直接建立它的对象，其中线性表中的数据在此为整型，具体应用的时候可以适当的修改，并可以在此基础上继续封装特定的功能。
头文件：LinkList.h
typedef struct LNode {
int data;
struct LNode *next;
}LNode, *pLinkList;
class LinkList {
private:
pLinkList m_pList;
int m_listLength;
public:
LinkList();
~LinkList();
bool InitList ();
bool DestroyList ();
bool ClearList();
bool IsEmpty ();
int GetLength ();
bool GetNode(int position, LNode** node);
int LocateElem(int elem);
bool SetNodeData(int position, int newData);
bool GetNodeData(int position, int &data);
bool InsertNode(int beforeWhich, int data);
bool DeleteNode(int position);
};
Cpp文件：LinkList.cpp
#include <iostream.h>
#include 'LinkList.h'
LinkList::LinkList() {
m_pList = NULL;
m_listLength = 0;
InitList();
}
LinkList::~LinkList() {
if (!DestroyList()) {
DestroyList();
}
}
//初始化，分配一个头节点。
bool LinkList::InitList() {
if (!(m_pList = new LNode)) {
return false;
}
m_pList->next = NULL;
return true;
}
//销毁链表。
bool LinkList::DestroyList() {
if (!ClearList()) {
return false;
}
delete m_pList;
return true;
}
//判断链表是否为空。若为空，返回true，否则返回false。
bool LinkList::IsEmpty() {
if (m_pList->next == NULL) {
return true;
}
return false;
}
//返回链表的中当前节点数。
int LinkList::GetLength() {
return m_listLength;
}
//将链表清空，释放当前所有节点。
bool LinkList::ClearList() {
if (m_pList == NULL) {
return false;
}
LNode *pTemp = NULL;
while (m_pList->next != NULL) {
pTemp = m_pList->next;
m_pList->next = pTemp->next;
delete pTemp;
}
m_listLength = 0;
return true;
}
//将position指定的节点内的数据设置为newData。
//第一个有效节点的position为1。
bool LinkList::SetNodeData(int position, int newData) {
LNode *pTemp = NULL;
if (!(GetNode(position, &pTemp))) {
return false;
}
pTemp->data = newData;
return true;
}
//得到指定位置节点的数据。
//节点索引从1到listLength。
bool LinkList::GetNodeData(int position, int &data) {
LNode *pTemp = NULL;
if (!(GetNode(position, &pTemp))) {
return false;
}
data = pTemp->data;
return true;
}
//在链表中插入一个节点。
//插入的位置由beforeWhich指定，新节点插入在beforeWhich之前。
//beforeWhich的取值在1到ListLength+1之间。
bool LinkList::InsertNode(int beforeWhich, int data) {
LNode *pTemp = NULL;
if (beforeWhich < 1 || beforeWhich > (m_listLength + 1)) {
return false;
}
if (!(GetNode(beforeWhich - 1, &pTemp))) {
return false;
}
LNode *newNode = new LNode;
newNode->data = data;
newNode->next = pTemp->next;
pTemp->next = newNode;
m_listLength++;
return true;
}
//删除一个指定的节点。
//节点位置由position指定。
//positon的值从1到listLength。
//若链表为空或指定的节点不存在则返回false。
bool LinkList::DeleteNode(int position) {
if (position < 1 || position > m_listLength) {
return false;
}
LNode *pTemp = NULL;
if (!(GetNode(position - 1, &pTemp))) {
return false;
}
LNode *pDel = NULL;
pDel = pTemp->next;
pTemp->next = pDel->next;
delete pDel;
m_listLength--;
return true;
}
//得到指定位置节点的指针。
bool LinkList::GetNode(int position, LNode **node) {
LNode *pTemp = NULL;
int curPos = -1;
pTemp = m_pList;
while (pTemp != NULL) {
curPos++;
if (curPos == position)
break;
pTemp = pTemp->next;
}
if (curPos != position) {
return false;
}
*node = pTemp;
return true;
}
//定位与指定数据相等的数据节点。
//如果在当前链表中已经存在该数据则返回该数据节点的索引号。
//若不存在这样的节点则返回0。
//节点索引从0开始到listLength。
int LinkList::LocateElem(int elem) {
LNode *pTemp = NULL;
int curIndex = 1;
pTemp = m_pList->next;
while ((pTemp != NULL) && (pTemp->data != elem)) {
pTemp = pTemp->next;
curIndex++;
}
if (pTemp == NULL) {
return 0;
}
return curIndex;
}
/*
int main(){
LinkList l;
l.InsertNode(1, 10);
l.InsertNode(2, 20);
l.InsertNode(3, 30);
l.InsertNode(4, 40);
cout << l.GetLength() << endl;
int dataTemp = 0;
for (int i = 1; i <= l.GetLength(); i++) {
l.GetNodeData(i, dataTemp);
cout << dataTemp << endl;
}
if (l.SetNodeData(3, 50)) {
cout <<'DONE\n';
} else {
cout << 'Failed\n';
}
for (i = 1; i <= l.GetLength(); i++) {
l.GetNodeData(i, dataTemp);
cout << dataTemp << endl;
}
if (l.DeleteNode(4)) {
cout <<'DONE\n';
} else {
cout << 'Failed\n';
}
for (i = 1; i <= l.GetLength(); i++) {
l.GetNodeData(i, dataTemp);
cout << dataTemp << endl;
}
cout << l.LocateElem(50) << endl;
return 0;
}
*/
不使用任何中间变量实现strlen
http://www.51testing.com/?uid-225738-action-viewspace-itemid-221151
《C语言实现strlen函数的几种方法》
http://blog.csdn.net/sailor_8318/article/details/3071048
递归的思想：
“不使用中间变量”只是说程序员不能显式的申请内存而已，即不能有局部变量或者动态内存申请。
如果函数自动申请栈内存或者使用寄存器存储变量，或者使用立即数寻址即常量，那么就相当于“不使用中间变量”。
从函数原型看，返回值为int，那么在函数内部必定需要一个地方存储这个值，要么是常数要么是寄存器。
长度不为1时不能一次就求出来，说明必须有递归调用，这样递归时函数会自动申请栈内存，这样就相当于程序员“不使用中间变量”了。
中间返回的值通过寄存器自动保存，最后一次返回时拷贝到int中去。
这种问题都是利用常量，或者将变量的申请交给编译器在递归过程中自动在栈中申请。
链表笔试面试题
《链表笔试面试题》
http://blog.csdn.net/fatshaw/article/details/6452460
|
链表倒序输出（不能改表链表结构，不能用任何自己开的辅助空间） |
//递归方法 倒序输出
void reversePrint(node* head)
{
if(head->next != NULL)
{
reversePrint(head->next);
cout<<head->next->data<<" ";
}
}
设计一个算法，找出一个无环的单链表里面倒数第k个元素。
首先，检查链表是否为空，以及检查输入的k的有效性。
其次，考虑单链表少于K个元素的情况。
struct node{
int key;
node* next;
};
typedef node* List;
int findLastKthElement(List list, intk)
{
//遍历整个链表，声明一个临时指针指向头节点
//当遍历过元素个数小于K的时候，继续遍历
//当遍历过的元素个数等于k的时候，临时指针指向下一个元素，然后继续遍历
//当遍历到链表尾部的时候，则临时指针指向的节点就为倒数第k个元素。
if (list == NULL || k <=0)
{
return-1; //查找失败。
}
List p = list;
List tempList =list;
int num = 0;
while(p)
{
if (num <k)
{
num++;
}
else if (num== k)
{
tempList = tempList->next;
}
p =p->next;
}
if (num < k)
{
return -1; //查找倒数第k个元素失败
}
return tempList->key;
}
|
逆置单链表（手写代码） |
有一个单链表，要求写出此单链表的逆置链表。
typedef struct node
{
int data;
struct node *next;
}node;
node *reverse(node *head)
{
//如何实现，请给出说明，谢谢！
}
node *reverse(node *head)
{
node *p, *q, *t;
if (NULL == head || NULL == head->next)//检查边界情况
{
cout<<"链表为空"<<endl;
returnhead;
}
p = head->next;
t = q = p->next;
p->next = NULL;
while(t != NULL)
{
t =q->next;
q->next =p;
p = q;
q = t;
}
head->next = p;
return head;
}
|
单链表的创建，逆置（C++代码实现） |
#include<iostream>
using namespace std;
//创建链表节点结构体
struct node
{
int data;
node* next;
};
//创建链表
node *create()
{
node *head;
head = (node *)malloc(sizeof(node));//为head指针分配空间
head->next=NULL;
head->data =0;
node *p = head; //创建尾指针
cout<<"Please input all thedata and end with '-1': "<<endl;
int x;
node *s;
while (cin>>x)
{
if (-1 !=x)
{
s = (node *)malloc(sizeof(node)); //分配空间
s->data = x;
p->next =s;
p = s;
head->data++;
}
else
{
break;
}
}
p->next =NULL;
return head;
}
//打印链表
void print(node* head)
{
if(NULL == head ||NULL == head->next)
{
cout<<"链表为空"<<endl;
}
node* temp =head->next;
while(temp != NULL)
{
cout<<temp->data<<"";
temp = temp->next;
}
cout<<endl;
}
//逆置函数
node *reverse(node *head)
{
node *p1, *p2, *p3;//需要三个辅助节点
if (NULL == head || NULL ==head->next)//检查边界情况
{
cout<<"链表为空"<<endl;
returnhead;
}
p1 =head->next;
p2 = p1->next;
p1->next = NULL;
while (NULL != p2)
{
p3 =p2->next;
p2->next =p1;
p1 = p2;
p2 = p3;
}
head->next = p1;
return head;
}
int main()
{
node* list =create();
print(list);
reverse(list);
print(list);
system("pause");
return 0;
}
函数
|
atoi函数 - 字符串转换成整型数 |
atoi函数，ASCII to Integer.把字符串转换成整型数。
int atoi(const char *nptr)
函数说明：参数nptr字符串，如果第一个非空格字符存在，是数字或者正负号则开始做类型转换，之后检测到非数字包括结束符字符时停止转换，返回整型数。否则返回零。
示例使用代码：
char*str ="12345.67";
n =atoi(str);
chara[] ="-100";
charb[] ="123";
intc ;
c =atoi( a ) +atoi( b ) ;
1 2.1 isalpha
1 2.2 iscntrl
1 2.3 isdigit
1 2.4 isgraph
1 2.5 islower
1 2.6 isupper
1 2.7 tolower
1 2.8 toupper
1 2.9 isalnum
1 2.10 isprint
写出c库的atoi函数，要求，尽量完美，考虑到溢出，异常等情况。
1 #include <limits.h>
1 #include <ctype.h>
1 #include<stdlib.h>
1 #include <stdio.h>
1 int myatoi (const char *nptr) {
1 int sign = 1;
1 int retval = 0;
1 int int_bound = INT_MAX /10;
1
1 /* ignore preceding white spaces */ 忽略最前面连续的空格
1 while (isspace (*nptr))
1 nptr++;
1
1 /* handle preceding sign if there isany */ 处理正负号
1 if (*nptr == '-' || *nptr == '+')
1 sign= (*nptr++ == '+') ? 1 :-1;
1
1 /* add digits to number(retval), * but not more than one less than the number of digits ofINT_MAX */
1 while (isdigit (*nptr) &&int_bound) {
1 retval= retval * 10 + (*nptr - '0');
1 int_bound/= 10;
1 nptr++;
1 }
1 if (!isdigit (*nptr))
1 return sign * retval;
1 else {
1 if (retval > INT_MAX /10)
1 goto overflow;
1 else if (retval < INT_MAX /10)
1 goto normal;
1 else if (*nptr - '0' > abs (((sign == 1) ? INT_MAX : INT_MIN) %10))
1 goto overflow;
1 else
1 goto normal;
1 }
1 normal:
1 if (isdigit (*(nptr +1)))
1 goto overflow;
1 else
1 return sign * (retval * 10 + (*nptr - '0'));
1 overflow:
1 return ((sign == 1) ? INT_MAX :INT_MIN);
1 }
1
1 int main() {
1 printf("%d/n",myatoi("-123456c7"));
1 return 0;
1 }
|
memcpy函数 |
笔试编程题：已知memcpy的函数为： void* memcpy(void *dest , const void* src , size_t count)其中dest是目的指针，src是源指针。不调用c++/c的memcpy库函数，请编写memcpy。
1 //copyright@July 2013/9/24
2 void* memcpy(void *dst, const void *src, size_t count)
3 {
4 //安全检查
5 assert( (dst != NULL)&& (src != NULL) );
6
7 unsigned char *pdst = (unsigned char *)dst;
8 const unsigned char *psrc= (const unsigned char *)src;
9
10 //防止内存重复
11 assert(!(psrc<=pdst&& pdst<psrc+count));
12 assert(!(pdst<=psrc&& psrc<pdst+count));
13
14 while(count--)
15 {
16 *pdst= *psrc;
17 pdst++;
18 psrc++;
19 }
20 return dst;
21 }
说明
1.source和destin所指的内存区域可以重叠，但是如果source和destin所指的内存区域重叠,那么这个函数并不能够确保source所在重叠区域在拷贝之前被覆盖。而使用memmove可以用来处理重叠区域。函数返回指向destin的指针。
2.strcpy和memcpy主要有以下3方面的区别。
2.1、复制的内容不同。strcpy只能复制字符串，而memcpy可以复制任意内容，例如字符数组、整型、结构体、类等。
2.2、复制的方法不同。strcpy不需要指定长度，它遇到被复制字符的串结束符"\0"才结束，所以容易溢出。memcpy则是根据其第3个参数决定复制的长度。
2.3、用途不同。通常在复制字符串时用strcpy，而需要复制其他类型数据时则一般用memcpy
3.如果目标数组destin本身已有数据，执行memcpy（）后，将覆盖原有数据（最多覆盖n）。如果要追加数据，则每次执行memcpy后，要将目标数组地址增加到你要追加数据的地址。
注意：source和destin都不一定是数组，任意的可读写的空间均可。
编辑本段函数实现
微软中：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
void* __cdeclmemcpy( void* dst, constvoid* src, size_tcount ) { void* ret = dst; #if defined (_M_MRX000) || defined (_M_ALPHA) || defined (_M_PPC) { externvoidRtlMoveMemory(void*,constvoid*,size_tcount ); RtlMoveMemory( dst, src, count ); } #else /* defined (_M_MRX000) || defined (_M_ALPHA) || defined (_M_PPC) */ /* * copy from lower addresses to higher addresses */ while(count--) { *(char*)dst = *(char *)src; dst = (char*)dst + 1; src = (char*)src + 1; } #endif /* defined (_M_MRX000) || defined (_M_ALPHA) || defined (_M_PPC) */ return(ret); }
|
coreutils中：
void *memcpy (void *destaddr,void const*srcaddr, size_t len){ char *dest =destaddr; char const *src = srcaddr; while(len-- > 0) *dest++ =*src++; return destaddr;}
Linux中：
void *memcpy(void *dest, const void*src, size_t count){ assert(dest != NULL && src !=NULL); char *tmp = dest; const char *s =src; while(count--) *tmp++ = *s++; return dest;}
编辑本段程序例
example1
作用：将s中的字符串复制到字符数组d中。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// memcpy.c #include <stdio.h> #include <string.h>
intmain() { char*s="Golden Global View"; chard[20]; clrscr(); memcpy(d,s,(strlen(s)+1)); printf("%s",d); getchar(); return0; }
|
输出结果：Golden Global View
example2
作用：将s中第14个字符开始的4个连续字符复制到d中。(从0开始)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <string.h>
intmain() { char*s="Golden Global View"; chard[20]; memcpy(d,s+14,4);//从第14个字符(V)开始复制，连续复制4个字符(View) //memcpy(d,s+14*sizeof(char),4*sizeof(char));也可 d[4]='\0'; printf("%s",d); getchar(); return0; }
|
输出结果： View
example3
作用：复制后覆盖原有部分数据
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#include <stdio.h> #include <string.h>
intmain(void) { charsrc[] ="******************************"; chardest[] ="abcdefghijlkmnopqrstuvwxyz0123as6"; printf("destination before memcpy: %s\n", dest); memcpy(dest, src,strlen(src)); printf("destination after memcpy: %s\n", dest); return0; }
|
输出结果：
destination beforememcpy:abcdefghijlkmnopqrstuvwxyz0123as6
destination after memcpy:******************************as6
memcpy和memmove函数的实现，需要注意memmove的覆盖问题，还有指针类型需要考虑。下面的例子中，先给出了错误的例子，而后给出了正确的例子，引以为戒！
区别：两个函数都是进行n字节内存内容的拷贝，入口参数和返回参数也都一样，可是这两个函数在内部实现上是有一定区别的，这主要是因为dest内存区域和src内存区域可能有一下四种不同的情况，注意count的影响：
src的内存区域和dest的内存区域相对位置和重叠关系有四种情况，memcpy没有考虑重叠的情况，而memmove考虑到了全部情况，因此memcpy函数的时候可能出现意向不到的结果。
这两个函数的实现：
***********下面两个是错误的实现**************
void* memcpy(void*dest, void* source, size_t count)
{
void* ret = dest;
//copy from lower address to higher address
while (count--)
*dest++ = *source++; //不知道两个指针的类型，不可以这样自加。
return ret;
}
void* memmove(void*dest, void* source, size_t count)
{
void* ret = dest;
if (dest <= source || dest >= (source + count))
{
//Non-Overlapping Buffers
//copy from lower addresses to higher addresses
while (count --)
*dest++ =*source++;
} else{
//Overlapping Buffers
//copy from higher addresses to lower addresses
dest += count - 1;
source += count - 1;
while (count--)
*dest-- =*source--; // 情况同上
}
return ret;
}
***********************正确的如下**************************
void*mymemcpy(void* dest, void* source, size_t count)
{
char *ret = (char *)dest;
char *dest_t = ret;
char *source_t = (char *)source;
while (count--){
*dest_t++ = *source_t++;
}
return ret;
}
void*my_memmove(void *dst,const void *src,int count)
{
char*ret;
char*dst_t;
char*src_t;
ret =(char *)dst;
if((unsigned char*)dst <= (unsigned char*)src
|| (unsigned char*)dst >= ((unsigned char *)src + count))
{
dst_t = (char *)dst;
src_t = (char *)src;
while (count--)
{
*dst_t++ = *src_t++;
}
}else{
dst_t = (char *)dst + count - 1;
src_t = (char *)src + count - 1;
while (count--)
{
*dst_t-- = *src_t--;
}
}
return(ret);
}