单向链表的插入、查找和遍历方法

昵称502168 2009-12-03

展开全文

#include<stdio.h>
#include<conio.h>

#define N 3

int Link_Length = N; //记录链表的长度

//定义结构体
struct t_node
{
int data;
struct t_node *next;
};

定义别名
typedef struct t_node Node;

//定义链表变量
Node * example_link = NULL;

/*
*功能：获取指定位置的节点的地址
*输入：plink=链表，i=索引位置，从零开始
*输出：无
*返回值：索引节点的地址
*/
Node * get(Node *plink,int i)
{

if(NULL == plink)
     return NULL;
int count = 0;
Node * pNext = plink;
while(count<i && pNext != NULL)
{
    count++;
    pNext = pNext->next;
}
return pNext;
}//endget()

/*
*功能：向指定链表中的指定位置前插入节点
*输入：plink=链表，x=新节点的值，i=插入位置
*输出：plink=插入节点后的新链表
*返回值：成功返回true, 否则为false
*/
bool Insert(Node *&plink,int x,int i)
{
Node *s = NULL; //新节点
Node *q = NULL; //中间变量

//构建新节点
   s = (node *)malloc( sizeof(node) );
   if( s == NULL )
        return false;

   s->data = x;
   s->next = NULL;

   if(i==0)//插入在头节点前
   {
       s->next = plink;
       plink = s;
    }
    else//插入在中间部位
    {//0
       //获取需插入位置的节点
        q = get(plink,i-1);
        if( NULL==q )
    return false;

        s->next=q->next;
        q->next=s;

    }//endelse0

return true;

}//endInsert()

/*
*功能：初始化链表
*输入：无
*输出：无
*返回值：无
*/
void Init_Link(void)
{
   Node *pNext = NULL;
   //头节点
   example_link = (Node *)malloc( sizeof(Node) );
   if(NULL == example_link)
       return;
   scanf("%d\n",&example_link->data);
   example_link->next = NULL;

//中间节点
pNext = example_link; //为游标赋值
for(i=1,i<N,i++)
{
    pNext->next = (Node *)malloc( sizeof(Node) );
     if(NULL == pNext->next)
       return;
    scanf("%d\n",&pNext->next->data);
    pNext->next->next = NULL;
    pNext = pNext->next; //移动游标
}

}
main()
{
int i,n;
Node *pNext = NULL;

//初始化链表
Init_Link();

//插入新节点
Insert(example_link, 2, 1);/* 2为插入的元素值，1为插入的位置*/

   //节点数增加
   Link_Length++;

   if(NULL == example_link)
       return;
   /*/在该行前面加"/"则使用第一方法
   //第一方法
   pNext = example_link;
   for(i=0,i<Link_Length; i++)
   {
      printf("%d\n",pNext->data);
      pNext = pNext->next;
   }
   /*/
   //第二方法
   pNext = example_link;
   while(pNext != NULL)
   {
      printf("%d\n",pNext->data);
      pNext = pNext->next;
   }
   //*/
   getch();

}//endmain()

本文出自 “C++” 博客，请务必保留此出处http://ljqy27.blog.51cto.com/1054/40150