// IntLink.cpp : Defines the entry point for the console application.
//
//
/**//**//**///////////////////////////////////////////////////////////////////////////
//作者：梦在天涯
//单向链表类
/**//**//**///////////////////////////////////////////////////////////////////////////
//
//
#pragma once
#include <stdio.h>
#include <tchar.h>
#include <iostream>
using namespace std;
struct NODE
{
int data;
NODE * next;
};
class CIntLink
{
private:
NODE * head;
public:
CIntLink()
{
head=NULL;
}
~CIntLink()
{
delete head;
}
void Add( int iValue );
void Remove( int iIndex);
void Insert(int iIndex, int iValue );
int Find( int iValue );
void output();
int size();
};
//链表的标号是从0开始。且第一个节点有存有数据。
void CIntLink::Add(int ivalue)
{
if(head==NULL)
{
head=new NODE;
head->data=ivalue;
head->next=NULL;
}
else
{
NODE *temp=new NODE;
temp->data=ivalue;
temp->next=NULL;
NODE *p=head;
while(p->next!=NULL)
p=p->next;
p->next=temp;
}
}
void CIntLink::Remove(int iIndex) //iIndex 从0开始，即第一个值也即头指针为iIndex为0
{
if(iIndex==0)
{
NODE * p=head;
head=head->next;
delete p;
p=NULL;
}
else if(iIndex==1)
{
NODE * p2=head->next;
head->next=p2->next;
delete p2;
p2=NULL;
}
else
{
NODE *pre=head->next;
NODE *p=pre->next;
for(int i=2;p!=NULL;i++) //p 为要删除的值的位置
{
if (iIndex==i) break;
pre=p;p=p->next;
}
if(iIndex==i&&p!=NULL)
{
pre->next=p->next;
delete p;
p=NULL;
}
else //p->NULL
{
cout<<"remove fail:no fond iIndex"<<endl;
}
}
}
void CIntLink::Insert(int iIndex, int iValue)
{
if(iIndex==0)
{
NODE * p1=new NODE;
p1->data=iValue;
p1->next=head;
head=p1;
}
else if(iIndex==1)
{
NODE * p2=new NODE;
p2->data=iValue;
p2->next=head->next;
head->next=p2;
}
else
{
NODE *pre=head->next;
NODE *pp=pre->next;
for(int i=2;pp!=NULL;i++) //i为要插入的值的位置
{
if (iIndex==i) break;
pre=pp;pp=pp->next;
}
if(iIndex==i&&pp!=NULL)
{
NODE *q=new NODE;
q->data=iValue;
q->next=pp->next;
pre->next=q;
q->next=pp;
}
else //(pp->next=NULL)
{
cout<<"insert fail:iIndex is out of range "<<endl;
}
}
}
int CIntLink::Find(int iValue)
{
if(head==NULL)
{
cout<<"find fail:no found ivalue ,and it retrun is -1"<<endl;
return -1;
}
NODE *pp= head;
for(int i=0;pp->next!=NULL;i++)
if(pp->data==iValue)
{
return i;//--i;
}
else
pp=pp->next;
cout<<"find fail:no found ivalue,and it return is -1"<<endl;
return -1;
}
void CIntLink::output()
{
NODE * p=head;
cout<<"the link data is :"<<endl;
for(;p!=NULL;p=p->next)
cout<<p->data<<endl;
}
int CIntLink::size()
{
NODE * p=head;
int i=0;
for( ;p!=NULL;p=p->next,i++);
return i;
}
int _tmain(int argc, _TCHAR* argv[])
{
CIntLink link;
link.Add(10);
link.Add(30);
link.Add(40);
link.Add(50);
link.Insert(5,20);
link.Remove(5);
int num=link.size();
cout<<"the link data number is :"<<num<<endl;
link.output();
int re=link.Find(20);
cout<<re<<endl;
return 0;
}
#include<iostream.h>
#include<stdlib.h>
struct List
{
int data; //节点存储信息
List* next; //指向下一个节点的指针
};
typedef List Node;
typedef Node *Link;
Link createList( int n ) //输入单链表长度，然后依次输入节点信息，返回表头
{
Link head, pointer1, pointer2;
int i;
pointer1 = head = new Node;
for( i = 1; i <= n; i ++ )
{
pointer2 = new Node;
pointer1->next = pointer2;
cout << "Input Data " << i << ": ";
cin >> pointer2->data;
pointer1 = pointer2;
}
cout << endl;
pointer2->next = NULL;
return head;
}
void getElement( Link head, int k ) //输出第k个节点的信息。范围是1≤k≤n，首先需判断单链表是否为空，否则无法删除。
{
int i;
Link pointer;
pointer = head;
for( i = 1; i < k && pointer->next != NULL; i ++ )
pointer = pointer->next;
if( pointer->next == NULL && i == k || k <= 0 )
cout << "Incorrect position input!" << endl;
else
cout << pointer->next->data;
}
void insertList( Link head, Link newNode, int k ) //为新插入的节点申请空间，然后输入该节点信息，并输入插入位置
{
int i;
Link pointer;
pointer = head;
for( i = 1; i < k && pointer->next != NULL; i ++ )
pointer = pointer->next;
if( pointer->next == NULL && i < k || k <= 0 )
cout << "Incorrect position input!" << endl;
else
{
newNode->next = pointer->next;
pointer->next = newNode;
}
}
void deleteList( Link head, int k ) //仅需要输入删除节点的位置即可
{
int i;
Link pointer1, pointer2;
pointer1 = head;
for( i = 1; i < k && pointer1->next != NULL; i ++ )
pointer1 = pointer1->next;
if( pointer1->next == NULL || k <= 0 )
cout << "Incorrect position input!" << endl;
else
{
pointer2 = pointer1->next;
pointer1->next = pointer2->next;
delete pointer2;
}
}
void printList( Link head )
{
int i = 1;
Link pointer;
pointer = head->next;
while( pointer != NULL )
{
cout << "Data " << i << ": " << pointer->data << endl;
pointer = pointer->next;
i ++;
}
i --;
if( i == 0 )
{
cout << "No data left!" << endl;
exit(0);
}
cout << "List length: " << i << endl;
}
void main()
{
Link head, newNode;
int n, k, choice;
cout << "Input the length of the List: ";
cin >> n;
head = createList( n );
cout << "List Information:" << endl;
printList( head );
cout << endl << "Try these following operations:" << endl;
cout << "(0) Exit ……" << endl;
cout << "(1) Inserting ……" << endl;
cout << "(2) Deleting ……" << endl;
cout << "(3) Getting Data ……" << endl;
cout << "Input your choice: " ;
cin >> choice;
while( choice != 0 )
{
switch( choice )
{
case 1:
newNode = new Node;
cout << "<----Inserting---->" << endl;
cout << "Input data of the new node: ";
cin >> newNode->data;
cout << "Input insert position: ";
cin >> k;
insertList( head, newNode, k );
printList( head );
break;
case 2:
cout << "<----Deleting---->" << endl;
cout << "Input delete position: ";
cin >> k;
deleteList( head, k );
printList( head );
break;
case 3:
cout << "<----Getting---->" << endl;
cout << "Input getting position: ";
cin >> k;
getElement( head, k );
break;
default:
cout << "Incorrect Input! Please reinput!" << endl;
}
cout << endl << "Try again?" << endl;
cout << "Input your choice: " ;
cin >> choice;
}
}