数据结构与算法——单链表（一）

以你之姓@ 2022-09-25 13:26 232阅读 0赞

单链表的头插法，插入时就是逆序。 InsertList()还不完善。

#include<stdio.h>
    #include<stdlib.h>
    #define ERROR 0
    #define OK 1
    
    typedef  int Status ;
    typedef int Elemtype ;
    typedef struct Node{
    	Elemtype data;//数据域
    	struct Node *next;//指针域
    }Node;
    typedef struct Node*  LinkList;//LinkList为指向Node的指针。
    
    /*
    *函数声明
    */
    Status FrontInsertList(LinkList &L);
    Status InsertList(LinkList &L,int i,Elemtype e);  
    void PrintList(LinkList L); 
    
    int main(){
    	Elemtype e;
    	int i;
    	LinkList L;
    	L=NULL; 
    	if(FrontInsertList(L))
        PrintList(L);//打印单链表
    	
    	printf("请输入要插入的元素和位置：\n");
    	scanf("%d %d",&e,&i);
    	if(InsertList(L, i,e))
    	{
    	printf("\n\n新的链表为：\n");
    	PrintList(L);
    	}
    	return 0;
    }
    Status FrontInsertList(LinkList &L){//头插法
    	LinkList p,q;//输入元素的新结点
    	int n;
    	q=(LinkList)malloc(sizeof(Node));
    	q=NULL;
        printf("请输入n和n个数据元素:\n");
    	scanf("%d",&n);	
    	 while(n--)
    	 {
    	  p=(LinkList)malloc(sizeof(Node));
    	  p->next=q;
    	  q=p;
    	  scanf("%d",&p->data);//头插法为逆值
    	 } 
    	
    	 while(p->next)//遍历到第一个结点
    	 {
    		 p=p->next;
    	 }
    
    	 L=q;	 
        printf("链表输入结束（END）\n"); 
    	 return OK;
    }
    
    
    /*
    *****给链表的第i个位置插入**************
    */   
    Status InsertList(LinkList &L,int i,Elemtype e)  
    {  
        LinkList p,s;
        int j=1; 
    	p=L;
        s=(LinkList)malloc(sizeof(Node));  
    
    	while(p&&j<i)//寻找第i个节点,有一个为假退出，NUll时最后一个。
    	{
    	    p=p->next;
    	    j++;
    	}
    	if(!p||j>i)//最后一个还没有或者找不到
    		return ERROR;
    	s->data=e;
    	s->next=p->next;
    	p->next=s;
    
        return OK;
    } 
    
    /*
    *****************打印链表***********************
    *
    **/  
    void PrintList(LinkList L)
    {  
    	
        LinkList temp;  
    	temp=L;                                                                  
        printf("\n链表存入的值为：\n");  
        while(temp!=NULL)      //非空表
        {  
            printf("%2d",temp->data);//输出链表节点的值
            temp=temp->next; 
        }  
        printf("\n链表打印结束!!\n");  
    }