link_list.cpp

C++的电子教程

#include <stdio.h>
#include <stdlib.h>

//声明结构变量类型NODE 
typedef struct node
{
	int data;
	struct node *next;
} NODE;

//链表的创建
NODE *link_create(NODE *head,int len)  //函数返回的是与节点相同类型的指针,len为结点个数
{
	NODE *p1,*p2;
	printf("创建链表，请输入结点值==>");
	p1=(NODE * )malloc(sizeof(NODE));       //申请新结点
	scanf("%d",&p1->data);                  //输入结点值
    p1->next=NULL;   
	
	if (head==NULL)                   
		head=p1;                                //p1接入表头    
	
	for (int i=1;i<len;i++)
	{
		printf("创建链表，请输入下一个结点值==>");
		p2=(NODE *)malloc(sizeof(NODE));    //申请下一个结点
		scanf("%d",&p2->data);
		p2->next=NULL;                      //新结点指针置为空

		p1->next=p2;                        //将p2连接到前一个结点
		p1=p1->next;
	}

	return head;
}

//链表的插入
NODE *link_ins(NODE *Head,int i,int x)
{
	NODE *p,*q;
	int j;
	q=(NODE *)malloc(sizeof(NODE));   //为插入结点分配内存
	q->data=x;

	if(Head==NULL)//空链表
	{
		Head=q;
		q->next=NULL;
		return Head;
	}

	if(i==0)                      //插入在第一个结点之前
	{
		q->next=Head;
		Head=q;
		return Head;
		
	}

	p=Head;
	j=0;
	while(++j<i && p!=NULL)     //寻找第i-1个结点
		p=p->next;

	if(p==NULL)                   //插入的位置在范围之外
	{
		printf("i out of range ! \n");
		return Head;
	}
	else
	{
		q->next=p->next;          //结点插入       
		p->next=q;
		return Head;
	}
}

//链表的删除
NODE *link_del(NODE *Head,int i)
{
	NODE *p,*q;
	int j;
	if(Head==NULL) return NULL;       //空链表

	if(i==0)                          //删除头结点
	{
		q=Head;
		Head=q->next;
		free(q);
		return Head;
	}

	p=Head;
	j=0;
	while(++j<i && p->next != NULL)         //寻找删除结点的前趋结点
		p=p->next;

	if(p->next == NULL)    //删除的位置在范围之外
	{
		printf("i out of range ! \n");
		return Head;
	}
	else
	{
		q=p->next;
		p->next=q->next;
		free(q);
		return Head;
	}
}


		
//链表的输出
void link_print(NODE *Head)
{
	NODE *Pointer;
	Pointer=Head;

	while(Pointer!=NULL)              //判断是否到表尾或空表
	{
		printf("[%d]",Pointer->data);
		Pointer=Pointer->next;
	}
	printf("\n");
}


//链表的释放
void link_free(NODE *Head)
{
	NODE *Pointer;
	while(Head!=NULL)               //逐一释放
	{
		Pointer=Head;
		Head=Head->next;            //指针下移
		free(Pointer);
	}
}


void main()
{
	int pos1,x,pos2,len;                    
	NODE *head;
	head=NULL;                    //置空头结点
	printf("请输入链表的长度==>");
	scanf("%d",&len);

	head=link_create(head,len);       //创建链表
	link_print(head);             //输出链表

	printf("请输入插入结点位置==>");
	scanf("%d",&pos1);
	printf("请输入插入的结点值==>");
	scanf("%d",&x);
	head=link_ins(head,pos1,x);   //插入结点
	link_print(head);             //输出链表

	printf("请输入删除结点位置==>");
	scanf("%d",&pos2);
	head=link_del(head,pos2);     //删除结点
	link_print(head);             //输出链表

    link_free(head);              //链表释放
}