list.cpp

内核中链表结构的实现,并通过实例对每个链表操作接口进行了详尽的讲解。 一、 链表数据结构简介 链表是一种常用的...这些链表大多采用在[include/linux/list.h]实现的一个相当精彩的链

//*************************************
// list.cpp : 链表使用示例
//包括链表的建立，链表输出，访问链表某个结点，插入链表，删除链表
//
//***********************************

#include "stdafx.h"
#include <iostream.h>

//函数原型
node *createList(int n);              //链表的建立
void createList1(node * &L, int n);    //链表的建立
void outputList(node * head);          //链表输出
node *findData(int n, node * head);       //访问链表某个结点
int insertData(int n, int e, node * &head);   //插入链表
int deleteData(node* &head, int i, int &e);     //删除链表

int main(int argc, char* argv[])
{

	int n;
	int num, e;
	node * listHead=NULL;
	cout <<"请输入结点数目:";
	cin>>n;
	//if(n>0)
	//	listHead=createList(n);
    createList1(listHead, n);
	outputList(listHead);
	cout<<"\n请输入查询结点的值:";
	cin>>num;
	findData(num, listHead);
	cout<<"\n要在第几个结点前插入？";
	cin>>num;
	cout<<"\n要插入的结点值为？";
	cin>>e;
	insertData(num,e,listHead);
    cout<<"插入后链表为"<<endl;
	outputList(listHead);
	cout<<"\n要删除第几个结点？";
	cin>>num;
	deleteData(listHead, num, e);
    cout<<"删除后链表为"<<endl;
	outputList(listHead);
	cout<<"删除结点值为"<<endl;
	cout<<e<<endl;
	return 0;
}

//建立链表——注，这是与课本不同的算法
node *createList(int n)                   //建立链表
{
	node *temp,*head=NULL;
	int num;
	cout <<"请输入结点的值:";
	cin>>num;
	head = new node;
	if (head==NULL) 
	{
		cout<<"内存分配出错!";
		return NULL;
	}
	else
	{
		head->data=num;
		head->next=NULL;
	}
	for(int i=0; i<n-1;i++)
	{
		cout <<"please enter data of nodes:";
		cin>>num;
		temp=new node;
		if(temp == NULL)
		{
			cout<<"No memory available!";
			return head;
		}
		else
		{
			temp->data=num;
			temp->next=head;
			head=temp;
		}
	}
	return head;
}

//课本链表建立算法(从表尾到表头逆向建立链表)
void createList1(node* &L, int n)         
{
	node *p;
	L= new node;
  
	L->next =NULL;                       //先建立一个带头结点的单链表
	for(int i=n; i>0; --i)
	{
		
		p=new node;                       //生成新结点
        cout <<"请输入结点的值";          //逆序输入
		cin>>p->data;                     //输入元素值
		p->next=L->next;                  //插入到表头
		L->next=p;
	}
}



//链表输出
void outputList(node * head)  
{
	cout<<"List:";
	node * p=head->next;    //从头结点指向的第一个结点开始输出
	while(p)                //p指针为空，表示链表结束
	{
		cout<<p->data;
		if(p->next)
			cout<<"->";
		p=p->next ;        //p指针后移
	}
	cout<<endl;
	return;
}

//查找元素值为n的结点，并返回该结点的指针
node *findData(int n, node * head)  
{
	node * p=head;
	while(p)
	{
		if(p->data == n)                   
		{                           //寻找到该结点
			cout<<"Find "<<n<<" in the list."<<endl;
			return p;

		}
		p=p->next; 
	}
	cout<<"can't find"<<n<<"in the list."<<endl;
	return NULL;
}

//在带头结点的单链表中的第i位置前插入元素e
int insertData(int i, int e, node * &head)  
{
	node * p=head;        
	node * s;                   //新结点指针
	int j=0;
	while(p&&j<i-1)             //寻找第i-1个结点
	{
		p=p->next; ++j;
	}
	if(!p||j>i-1) return 0;
	s= new node;                //生成新结点
	s->data = e;  
	s->next = p->next ;         //插入链表中
	p->next = s;
	return 1;	
}

//在带头结点的单链线性表中，删除第i个元素，并由e返回起值
int deleteData(node* &head, int i, int &e)
{	
	int j=0;  
	node *p=head;   
	node* q;
	while (j<i-1 && p!=NULL)  //查找第i-1个结点
	{     j++;
	      p=p->next;
	}
    if (p==NULL) return 0;            //未找到位序为i-1的结点
	else	                                      //找到位序为i-1的结点*p
	{       q=p->next;	                        //q指向要删除的结点
	        if (q==NULL)   return 0;
   	                                       //若不存在第i个结点,返回ERROR
	        p->next=q->next;	          //从单链表中删除*q结点
	        e=q->data;
			delete(q);	                         //释放*q结点
	        return 1;
	}
}