单链表设计与实现C++

数据结构课程设计之单链表设计与实现。

链表的结构体：

typedef struct  LNode 
{
	int    data;//数据域
	struct LNode   *next;//指针域
} LNode, *LinkList; 

链表的初始化(带头节点)：

bool initList(LinkList& list)
{
	list = new LNode();
	list->next = NULL;
	return true;
}

链表的指定位置插入：

bool insertList(LinkList& list, int pos,int e)
{
   if(list == NULL)
	   return false;

   LNode* pre = findPosNode(list,pos-1);
   if(pre == NULL)
	   return false;
   
   LNode* newNode = new LNode();
   newNode->data = e;
   newNode->next = pre->next;
   pre->next = newNode;
   return true;
}

链表的指定位置删除：

bool deleteList(LinkList& list, int pos,int& e)
{
   if(list == NULL)
	   return false;

   LNode* pre = findPosNode(list,pos-1);
   if(pre == NULL)
	   return false;
   
   LNode* delNode = pre->next;
   pre->next = pre->next->next;
   e = delNode->data;
   delete delNode;

   return true;
}

 得到数据节点的个数：

int getListLength(LinkList& list )
{
	 
	int cnt = 0; 

	LNode* p = list->next;  
	while ( p != NULL) { 
		p = p->next; 
		cnt++; 
	}   
	return cnt;
}

头插法：

void insertListByHead(LinkList& list, int x)
{
	
		LNode* newNode = new LNode();
		newNode->data = x;
		newNode->next = list->next;  
		list->next = newNode;	
}

 尾插法：

void insertListByTail(LinkList& list,int x)
{
	if(list == NULL)//判断单链表存不存在
		return;
    LNode* tail = list; 
	while(tail->next != NULL)//判断是不是尾节点
		tail = tail->next;  //往后面走一步
		LNode* newNode = new LNode(); //依次创建新节点
		newNode->data = x;
		newNode->next = NULL;
		tail->next = newNode; //把新节点链到尾节点后面
		tail = newNode;       //指定新的尾节点
}

 头删法：

int deleteListByHead(LinkList& list,int x)
{
	
		LNode* delNode = list->next;
		list->next=list->next->next;
        x=delNode->data;
		delete delNode;
		return x;
	
}

迭代实现链表反转：

重复上面的步骤

直至走完循环。 

执行L -> next = preNode;语句，完成反转。

LNode* reverse(LinkList& list) {
      LNode *preNode = NULL, *curNode = list->next;
      while (curNode) {
         LNode *nextNode = curNode -> next;
          curNode -> next = preNode;
          preNode = curNode;
          curNode = nextNode;
      }
    list -> next = preNode;
    return list;
 }

代码如下：

#include 
using namespace std;
//链表结构体 
typedef struct  LNode 
{
	int    data;//数据域
	struct LNode   *next;//指针域
} LNode, *LinkList;  
//初始化链表 
bool initList(LinkList& list)
{
	list = new LNode();
	list->next = NULL;
	return true;
}
//获取pos位置的结点 
LNode* findPosNode( LinkList& list, int pos)
{
	LNode* p  = list;
	int count = 0;

	while(p != NULL)
	{
		if(count == pos)
			return p;  
		count++;	
		p = p ->next;
	}

	return NULL;
}
//指定位置插入 
bool insertList(LinkList& list, int pos,int e)
{
   if(list == NULL)
	   return false;

   LNode* pre = findPosNode(list,pos-1);
   if(pre == NULL)
	   return false;
   
   LNode* newNode = new LNode();
   newNode->data = e;
   newNode->next = pre->next;
   pre->next = newNode;
   return true;
}
//指定位置删除 
bool deleteList(LinkList& list, int pos,int& e)
{
   if(list == NULL)
	   return false;

   LNode* pre = findPosNode(list,pos-1);
   if(pre == NULL)
	   return false;
   
   LNode* delNode = pre->next;
   pre->next = pre->next->next;
   e = delNode->data;
   delete delNode;

   return true;
}
//打印 
void print(LinkList& list)
{
	if(list == NULL)
		return;
	LNode* p = list->next;
	while(p != NULL)
	{
        cout<data<<" ";
		p = p->next;
	}
	cout<next;  
	while ( p != NULL) { 
		p = p->next; 
		cnt++; 
	}   
	return cnt;
}
//头插法 
void insertListByHead(LinkList& list, int x)
{
	
		LNode* newNode = new LNode();
		newNode->data = x;
		newNode->next = list->next;  
		list->next = newNode;	
}
//尾插法 
void insertListByTail(LinkList& list,int x)
{
	if(list == NULL)//判断单链表存不存在
		return;
    LNode* tail = list; 
	while(tail->next != NULL)//判断是不是尾节点
		tail = tail->next;  //往后面走一步
		LNode* newNode = new LNode(); //依次创建新节点
		newNode->data = x;
		newNode->next = NULL;
		tail->next = newNode; //把新节点链到尾节点后面
		tail = newNode;       //指定新的尾节点
}
//头删法 
int deleteListByHead(LinkList& list,int x)
{
	
		LNode* delNode = list->next;
		list->next=list->next->next;
        x=delNode->data;
		delete delNode;
		return x;
	
}
//迭代实现链表反转 
LNode* reverse(LinkList& list) {
      LNode *preNode = NULL, *curNode = list->next;
      while (curNode) {
         LNode *nextNode = curNode -> next;
          curNode -> next = preNode;
          preNode = curNode;
          curNode = nextNode;
      }
    list -> next = preNode;
    return list;
}

int main()
{
	LinkList  list = NULL;
	//初始化链表，带头节点的链表。 
	initList(list);
	cout<<"插入十个数据:"; 
	for(int i = 0; i < 10; i++)
		insertList(list,i,i);
	print(list);
	cout<<"反转后链表:"; 
	LNode *r=reverse(list);
	print(r);
	cout<<"头插一个10：";
	insertListByHead(list,10);
	print(list);
	cout<<"尾插一个0： ";
	insertListByTail(list,0);
	print(list);
	cout<<"pos位置后的链表：";
	LNode *t=findPosNode(list,5); 
	print(t);
	return 0;
}