链表专题(C语言)

 本文目录:

                一.初识链表

                        1.链表的基本概念

                        2.链表和顺序表的区别

                二.链表的基本操作

                        1.链表的初始化

                        2.链表的创建（头插法，尾插法）

                        3.打印链表

                        4.获得链表的长度

                        5.获得链表中间结点

                        6.在任意位置处添加结点

                        7.删除结点

一.初识链表

1.链表的基本概念

        链表一种线性的数据结构，通过指针将一个个零散的内存块连接起来，链表的每个内存块称为结点。 

2.顺序表和链表的区别 

• 存储分配方式不同：顺序存储结构是用一段连续的存储单元依次存储线性表的数据元素，单链表是采用链式存储结构，用一组任意的存储单元存放线性表的元素。可以是物理地址不连续的物理空间
• 空间利用率不同：顺序表的空间利用率比链表高。因链表在存储数据时，每次只申请一个节点的空间，这种申请存储空间的方式一定程序上造成了空间浪费。 

二.链表的基本操作

基本操作接口：

LinkList InitList();//初始化链表
void CreatByRear(LinkList head);//尾插法
void CreatByHead(LinkList head);//头插法
void OutPut(LinkList head);//打印链表
int GetLength(LinkList head);//获得链表的长度
Node *GetMid(LinkList head);//获得链表中间结点
void DelNode(LinkList head,int pos);//删除结点
void InsertPos(LinkList head,int pos);//在任意位置处插入结点

 首先：链表的基本结构：

typedef struct ListNode{
    int val;
    struct ListNode *next;
}Node,*LinkList;

1.链表的初始化：

LinkList InitList()
{
    LinkList head;
    head=(Node *)malloc(sizeof(Node));
    head->next=NULL;
    return head;
}

2.链表的创建：

• 尾插法： 

void CreatByRear(LinkList head)
{
    int val;
    Node *p=head,*s;
    while(1)
    {
        scanf("%d",&val);
        if(val==0) break;
        else {
            s=(Node *)malloc(sizeof(Node));
            s->val=val;
            p->next=s;
            p=s;
        }
    }
    s->next=NULL;
}

• 头插法：

void CreatByHead(LinkList head)
{
	Node *s;
	int val;
	while(1)
	{
		scanf("%d",&val);
		if(val==0) break;
		else {
			s=(Node *)malloc(sizeof(Node));
			s->val=val;
			s->next=head->next;
			head->next=s;
		}
	}
}

 3.打印链表

void OutPut(LinkList head)
{
    Node *p=head->next;
    while(p)
    {
        printf("%d ",p->val);
        p=p->next;
    }
}

 4.获得链表的长度

int GetLength(LinkList head)
{
	int cnt=0;
	Node *p=head->next;
	while(p)
	{
		p=p->next;
		cnt++;
	}
	return cnt;
}

 5.获得链表的中间结点

         快慢指针法：fast每次走两步，slow指针每次走一步，当fast指针走到链表尾部时，slow指针就走到了链表的中间结点

Node *GetMid(LinkList head)
{
	Node *slow=head,*fast=head;
	while(fast!=NULL && fast->next!=NULL)
	{
		fast=fast->next->next;
		slow=slow->next;
	}
	return slow;
}

 6.在任意位置处插入结点

        首先，判断pos位置是否合法，调用GetLength()函数，获得链表的长度，如果说pos小于等于0或者大于链表的长度的话，位置不合法。

        其次，要找到要插入位置的前一个结点 

void InsertPos(LinkList head,int pos,int val)
{
	if(pos<0 || pos>GetLength(head))
	{
		printf("pos位置不合法\n");
		return;
	}
	int i=1;
	Node *p=head,*s;
	s->val=val;
	while(i<pos)
	{
		p=p->next;//找到要插入位置处的前一个结点
		i++;
	}
	s->next=p->next;
	p->next=s;
}

7.删除结点 

         与在任意位置处插入结点一样，要判断pos位置是否合法

        其次，要找到要删除结点的前一个结点

void DelNode(LinkList head,int pos)
{
	if(pos<=0 || pos>GetLength(head))
	{
		printf("pos位置不合法\n");
		return;
	}
	Node *s=head;
	int i=1;
	while(i<pos)
	{
		i++;
		s=s->next;//找到要删除结点的下一个结点
	}
	Node *p=s->next;
	s->next=p->next;
	free(p);//最后要释放要删除的结点的空间
}

    还有一些其他的操作还没有写，等下次再跟大家分享!!!