单向链表

到期末了,准备最后一个月把数据结构的一些小算法总结下,都在Fedora上用 codeblocks+ddd写,刚好可以熟悉下linux平台。另外C++还是没开始学,于是就准备在写数据结构实现的过程中直接用C++,发现写成了C+,真是悲剧。。。。

先是简单的单向链表,书上的很简洁,但是看起来不是很懂,于是我就自己写了,虽然复杂了很多,但是还是比较简洁,效率应该是差不多的,我多的不过是几个分支。下面是几个注意点

#define ElementType int
typedef struct Node{ //Node
ElementType num;
struct Node* Next;
}Node,*pNode;

1.链表的0号节点内的是来记录链表中所有节点的总合的。

2.在插入节点的时候要保证:插入的序号必须在链表最长范围以内;插入情况主要是两种,一是在末尾插入;二是插入位置不是在链表尾。

3.在删除节点的时候要保证:删除的需要必须在链表最长范围以内:删除情况也是两种,一是删除末尾节点;二是插入位置不是在链表尾。

4.在清空链表的之后,要把头节点重新初始化,保证下次能够继续添加。

代码比较简单,就不多说了,直接看吧。。。
[code]
#include <iostream>

using namespace std;

#define ElementType int

typedef struct Node{ //Node
ElementType num;
struct Node* Next;
}Node,*pNode;

class Link {
public :
bool InitLink(pNode *L); //Init Node
bool InsertNode(pNode *L,ElementType data,int num); //Insert Node To Link
bool DeleteNode(pNode *L,int NumberDel); //Delete Node From Link
int LengthOfLink(pNode *L); //Get Length of Link
bool DestoryLink(pNode *L); //Clear Link
void PrintLink(pNode L); //display Node of Link
pNode Header; //Header of Link
};

void prinf();

int main()
{
Link L;
if(!L.InitLink(&(L.Header)))
return false;
int iChoice;
while(1)
{
prinf();
cin >> iChoice;
switch(iChoice)
{
case 1:
{

int num;
int data;
// cout <<"Input Number and Data Insert : " << endl;
// cin >> num ;//>> data;
for(int i = 1; i < 10;++i)
L.InsertNode(&(L.Header),i,i-1);
L.PrintLink(L.Header);
cout << endl;
break;
}
case 2:
{
int num;
cout << "Inout Number To Delete " << endl;
cin >> num;
L.DeleteNode(&(L.Header),num);
L.PrintLink(L.Header);
cout << endl;
break;
}
case 3:
cout << "Node of The Link is " << L.LengthOfLink(&(L.Header)) << endl;
break;
case 4:
L.DestoryLink(&(L.Header));
L.PrintLink(L.Header);
if(!L.InitLink(&(L.Header)))
return false;
break;
default :
break;
}
}
return 0;
}

void prinf()
{
cout << "1:Insert Node"<< endl;
cout << "2:delete Node" << endl;
cout << "3:Length of Link" << endl;
cout << "4:Clear Link" << endl;
}

bool Link::InitLink(pNode *L)
{
*L = new Node[sizeof(Node)];
if(!*L)
{
return false;
}
(*L)->num = 0;
(*L)->Next = NULL;
return true;
}

bool Link::InsertNode(pNode *L,ElementType data,int num)
{
if(num > (*L)->num)
{
cout << "Please Input Right Number" << endl;
return false;
}

pNode pNew = NULL,pTail = NULL,pTemp = *L;

if(!InitLink(&pNew))
return false;
pNew->num = data;

for(int i = 0; i < num;++i) //Find The Right Node
{
pTemp = pTemp->Next;
}
if(!pTemp->Next) //The lastest Node
{
pTemp->Next = pNew;
}
else //Not The lastest Node
{
pTail = pTemp->Next;
pTemp->Next = pNew;
pNew->Next = pTail;
}
(*L)->num++; //sum of link ++
return true;
}

bool Link::DeleteNode(pNode *L,int NumberDel)
{
if(NumberDel > (*L)->num)
{
cout << "Number To Delete Not Exsist" << endl;
return false;
}
pNode pTemp = *L;

for(int i = 1; i < NumberDel;++i)
pTemp = pTemp->Next;

pNode pDelNode = pTemp->Next;
if(!pDelNode->Next) //Delete The Lastest Node
{
pTemp->Next = NULL;
delete pDelNode;
pDelNode = NULL;
}
else //Not The lastest Node
{
pTemp->Next = pDelNode->Next;
delete pDelNode;
pDelNode = NULL;
}
(*L)->num--; //sum of node --
return true;
}

bool Link::DestoryLink(pNode *L)
{
pNode pTemp = *L,pTail = *L; //Clear Link
while(pTemp)
{
pTail = pTemp->Next;
pTemp->Next = NULL;
delete pTemp;
pTemp = pTail;
}
(*L)->Next = NULL;
(*L)->num = 0;
return true;
}

int Link::LengthOfLink(pNode *L)
{
return (*L)->num;
}
void Link::PrintLink(pNode L)
{
if(!L)
{
cout << "No Node" << endl;
return ;
}
pNode pTemp = L->Next;
cout << L->num << " Node in The Link " << endl;
for(int i = 1;i <= L->num;++i)
{
cout << "No." << i <<" Node " << pTemp->num << endl;
pTemp = pTemp->Next;
}

}
[/code]

标签:DataStructure