数据结构——线性表的链式结构（C语言）

忘是亡心i 2022-08-25 05:22 194阅读 0赞

**链式存储：以节点的方式存储，节点包括数据域和指针域，指针域的指针指向下一个节点的存储位置，数据的存储可以不连续。头指针作为链表的索引，使链表操作方便，头指针指向头节点，头节点指向第一个节点，以此类推，直到尾节点。**

**以下是源程序：**

**函数声明**

#ifndef List_H
    #define List_H
    
    typedef struct Node *PNode;//定义节点指针
    typedef int Item;//定义数据类型
    
    typedef struct Node//定义节点结构
    {
    	Item data;//数据域
    	PNode next;//指针域
    }node;
    
    typedef PNode Position;
    typedef PNode List;
    
    /**函数声明**/
    /***创建空链表，并返回链表指针***/
    List Creat_Empty(List);
    
    /***判断是否为空链表***/
    int Is_Empty(List);
    
    /***创建链表，并返回头指针***/
    List Make_List();
    
    /*** 链表反转 ***/
    List Invert(List);
    
    /***判断是为最后节点***/
    int Is_Last(Position);
    
    /***计算链表的长度***/
    int Length(List);
    
    /***遍历链表***/
    void Traverse_List(List); 
    
    /***在链表的某个位置插入数据项***/
    void Insert(Item,List,Position);
    
    /***查找链表中对应的数据项，并返回该数据项***/
    int Search(Item,List);
    
    /***查找链表中对应的数据项，并返回该数据项的前驱位置***/
    Position Search_Previous(Item,List);
    
    /***查找链表中对应的数据项，并返回该数据项的后继位置***/
    Position Search_Next(Item,List); 
    
    /***获得P的后继节点***/
    Position Advance(Position P);
    
    /***删除链表中的某个数据项***/
    void Delete(Item,List);
    
    /***删除链表除头节点外的所有节点***/
    void Delete_List(List); 
    
    /***查找P节点的数据项***/
    int Get_Item(Position P);
    #endif

函数定义

#include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #include"List.h"
    
    /**函数定义**/
    /***创建空链表，并返回链表指针***/
    List Creat_Empty(List L)
    {
    	L=(PNode)malloc(sizeof(node));
    	L->next=NULL;
    	L->data=0;
    	return L;
    }
    
    /***判断是否为空链表***/
    int Is_Empty(List L)
    {
    	return L->next==NULL;
    	/*
    	if(NULL==L->next)
    		return 1;
    	else
    		return 0;
    	*/
    }
    
    /***创建链表，并返回链表***/
    List Make_List()
    {
    	int val;
    	PNode pHead =(PNode)malloc(sizeof(node));  
    	PNode pCurrent = pHead;  
    	pCurrent->next = NULL;
    	if(NULL==pHead)
    		{
    			printf("Malloc the list is failed.");
    			exit(1);
    		}
    	printf("Input the first data:");
    	while(scanf("%d",&val)==1)
    		{
    			PNode pNew=(PNode)malloc(sizeof(node));
    			if(NULL==pNew)
    			{
    				printf("Malloc the pNew is failed.");
    				exit(1);
    			}
    			pNew->data=val;
    			pCurrent->next=pNew;
    			pNew->next=NULL;
    			pCurrent=pNew;
    			printf("Please input the next data:");
    		}
    	return pHead;
    }
    
    /*** 链表的反转 ***/
    List Invert(List Head)
    {
        PNode middle, trail;
        middle = NULL;
    
        PNode temp = Head->next;
        while(temp)
        {
            trail = middle;
            middle = temp;
            temp = temp->next;
            middle->next = trail;
        }
        Head->next = middle;
        return Head;
    }
    
    
    /***判断是为最后节点***/
    int Is_Last(Position P)
    {
    	return P->next==NULL;
    }
    /***计算链表的长度***/
    int Length(List L)
    {
    	int len=0;
    	PNode PCurrent=L->next;
    	while(NULL!=PCurrent)
    	{
    		len++;
    		PCurrent=PCurrent->next;
    	}
    	return len;
    }
    
    /***遍历链表***/
    void Traverse_List(List L)
    {
    	PNode PCurrent=L->next;
    	printf("The data of list are:\n");
    	while(NULL!=PCurrent)
    	{
    		printf("%d   ",PCurrent->data);
    		PCurrent=PCurrent->next;
    	}
    	printf("\n");
    }
    
    /***在链表的某个位置插入数据项***/
    void Insert(Item val,List L,Position P)
    {
    	PNode temp;
    	temp=(PNode)malloc(sizeof(node));
    	if(NULL==temp)
    		exit(0);
    	temp->data=val;
    	temp->next=P->next;
    	P->next=temp;
    }
    
    /***查找链表中对应的数据项，并返回该数据项***/
    int Search(Item val,List L)
    {
    	Position P;
    	P=L->next;
    	if(P!=NULL && P->data !=val)
    		P=P->next;
    	return P->data;
    }
    
    /***查找链表中对应的数据项，并返回该数据项的前驱位置***/
    Position Search_Previous(Item val,List L)
    {
    	Position P;
    	P=L;
    	if(P->next!=NULL && P->next->data!=val)
    		P=P->next;
    	return P;
    }
    
    /***查找链表中对应的数据项，并返回该数据项的后继位置***/
    Position Search_Next(Item val,List L)
    {
    	Position P;
    	P=L;
    	if(P!=NULL && P->data!=val)
    		P=P->next;
    	return P;
    }
    /*
    获得位置P后继节点位置 
    */  
    Position Advance(Position P)  
    {  
        if(P!=NULL)  
        return P->next;  
    }
    
    /***删除链表中的某个数据项***/
    void Delete(Item val,List L)
    {
    	Position P, temp;
    	P=Search_Previous(val,L);
    	if(!Is_Last(P))
    	{
    		temp=P->next;
    		P->next=temp->next;
    		free(temp);
    	}
    
    }
    
    /***删除链表L除头节点外的所有节点***/
    void Delete_List(List L)
    {
    	Position P, temp;
    	P=L->next;
    	L->next=NULL;
    	while(P!=NULL)
    	{
    		temp=P->next;
    		free(P);
    		P=temp;
    	}
    }
    
    /***返回P节点位置的数据项****/
    int Get_Item(Position P)  
    {  
        if(P!=NULL)  
        return P->data;  
    }

测试程序

#include<stdio.h>
    #include<stdlib.h>
    #include"List.h"
    #define NUMBER 5
    #define N 3
    
    
    
    
    int main(void)
    {
    List list;
    Position P;
    int len,val;
    list=NULL;
    List L=NULL;
    
    L=Creat_Empty(L);//创建空链表
    printf("The empty of list is created.\n");
    if(Is_Empty(L))//判断链表是否为空
    printf("The list is empty.\n");
    
    
    list=Make_List();//生成存储有数据项的链表
    Traverse_List(list);//遍历该链表
    
    list=Invert(list);//反转链表
    Traverse_List(list);//遍历该链表
    
    len=Length(list);//链表的长度
    if(!Is_Empty(list))
    printf("The length of list is:%d\n",len);
    
    
    P=list;
    Insert(NUMBER,list,P);//在链表中插入数据项
    P= Advance(P);//获取P后继节点位置
    if(P)
    printf("Insert the new data of %d is successed\n",Get_Item(P));
    else
    printf("Insert the data of %d is failed.\n",NUMBER);
    Traverse_List(list);//遍历该链表
    
    
    val=Search(N,list);//在链表中查找相应的数据项
    if(val==N)
    printf("Search the data of %d is successed.\n",N);
    else
    printf("Search the data of %d is failed.\n",N);
    
    
    Delete(NUMBER,list);//删除数据项
    Traverse_List(list);//遍历该链表
    
    
    Delete_List(list);//摧毁链表
    if(Is_Empty(list))
    printf("The list is destroied.");
    return 0;
    }