博客

今天复习单链表的基本操作，先把最基础的掌握，其他还有增加的操作，附在下一篇中。然后如果想看整个代码，直接拉到最下面。

一般步骤，第一步先定义一个单链表：

定义的方式有多种，写自己习惯的方式就行：

typedef struct Node{
	int data;
	struct Node* next;
}SLNode;

第二步，创建头结点。用到malloc函数，注意让首元结点指向空结点。

SLNode* head_create(){//创建头结点 
	SLNode* head = (SLNode*)malloc(sizeof(SLNode));
	if(head==NULL) exit(1);
	head->next=NULL; 
	return head; 
} 

第三步，尾插入结点。

SLNode* Node_insert(SLNode *head,int i,int x)//把x插入i位置 ,从头结点开始遍历 
{
	SLNode *p;p=head;//p指向头结点
	int m=0;
	while(m<i-1)//遍历到i-1位 
	{
		p=p->next;
		m++;
	}
	SLNode *q = (SLNode*)malloc(sizeof(SLNode));
	q->next=p->next;
	p->next=q; 
	q->data=x;
}

第四步，执行删除操作。其实和插入几乎是一样的，遍历到前一位置，再执行操作。

SLNode* Node_delete(SLNode *head,int i)//删除i位置的结点 
{
	SLNode *p,*s;
	p=head;
	int m=0;
	while(m<i-1){//遍历到i-1位 
		p=p->next;
		m++;
	}
	s=p->next;
	p->next=s->next;
	free(s);
}

第五步，计算单链表长度。和顺序表不同，单链表计算长度，直接从头结点所指的下一个结点开始，遍历到空节点停止。

int SL_length(SLNode *head)//链表长度 
{
	SLNode *p;p=head;
	int n=0;
	while(p->next!=NULL) 
	{
		n++;
		p=p->next;
	}
	return n;
}

第六步，打印链表。以前总是分不清链表的头结点和第一个结点，如果某个函数操作的时候忘记了头结点的含义，总是会导致各种各样的小错误，干脆就把头分开来看了。其实printf（“head”）完全没必要，可以删的。

void print_SL(SLNode *head)//打印链表 
{
	SLNode *p;p=head;
	if(p==NULL) printf("单链表空！\n");
    else{
		printf("head");
		p=p->next;
	}
	while(p!=NULL)
	{
		printf("->%d",p->data);
		p=p->next;
	}
	printf("\n");
}

要取数据也很简单。

int get_num(SLNode *head,int i)//取链表i位置的数据 
{
	SLNode *p;p=head;
	for(int k=0;k<i;k++)
	{
		p=p->next;
	}
	return p->data;
}

整个代码：

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

#define MAX 100


typedef struct Node{
	int data;
	struct Node* next;
}SLNode;


SLNode* head_create(){//创建头结点 
	SLNode* head = (SLNode*)malloc(sizeof(SLNode));
	if(head==NULL) exit(1);
	head->next=NULL; 
	return head; 
} 


SLNode* Node_insert(SLNode *head,int i,int x)//把x插入i位置 ,从头结点开始遍历 
{
	SLNode *p;p=head;//p指向头结点
	int m=0;
	while(m<i-1)//遍历到i-1位 
	{
		p=p->next;
		m++;
	}
	SLNode *q = (SLNode*)malloc(sizeof(SLNode));
	q->next=p->next;
	p->next=q; 
	q->data=x;
}


SLNode* Node_delete(SLNode *head,int i)//删除i位置的结点 
{
	SLNode *p,*s;
	p=head;
	int m=0;
	while(m<i-1){//遍历到i-1位 
		p=p->next;
		m++;
	}
	s=p->next;
	p->next=s->next;
	free(s);
}


int SL_length(SLNode *head)//链表长度 
{
	SLNode *p;p=head;
	int n=0;
	while(p->next!=NULL) 
	{
		n++;
		p=p->next;
	}
	return n;
}


int get_num(SLNode *head,int i)//取链表i位置的数据 
{
	SLNode *p;p=head;
	for(int k=0;k<i;k++)
	{
		p=p->next;
	}
	return p->data;
}


void print_SL(SLNode *head)//打印链表 
{
	SLNode *p;p=head;
	if(p==NULL) printf("单链表空！\n");
    else{
		printf("head");
		p=p->next;
	}
	while(p!=NULL)
	{
		printf("->%d",p->data);
		p=p->next;
	}
	printf("\n");
}


main()
{
	int x,y; 
	SLNode *SL1=head_create();
	for(int i=1;i<10;i++)
	{
		Node_insert(SL1,i,i*i);//把i^2插入i的位置 
	}
	printf("单链表1为：\n");
	print_SL(SL1);
	printf("单链表长度为%d\n",SL_length(SL1));
	x=3;
	Node_delete(SL1,x);//删去第3个位置的结点 
	printf("删去第%d个结点后单链表为：\n",x);
	print_SL(SL1);
	printf("单链表长度为%d\n",SL_length(SL1));
	y=6;
	int num1=get_num(SL1,y);
	printf("取第%d个元素为%d\n\n",y,num1);
	return 0;
}

运行结果如图：