数据结构之链表

女爷i 2022-08-07 14:36 180阅读 0赞

数据结构之链表

数据结构的第一章就是链表，链表是其他结构的基础，包括栈，树等等，链表由节点组成，其中在最前边有头指针和头结点组成其中，头指针是一个链表必要的元素，头结点可以使链表更为同一，但是头结点并非是一个链表的必要的元素。现在以一个结构体为一个节点，一个节点包含数据域，指针域两个部分，数据域用来存储需要存储的内容，指针域存储下一个结构体的地址。

typedef   struct  student

char name\[20\];

int age;

int number;

struct student   \*next;

\}STU;

此时一个STU就是一个节点，其中存储一个学生的名字，年龄，学号，以及指向这个结构体类型的指针，绝不是指向自己的指针。

下面我将贴上以学生信息为节点，和以电影信息为结点的简单 单链表的建立，删除等操作已经附加了注释

#include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<string.h>
    typedef struct student             /*以一个结构体为一个节点*/
    {
    	char name[20];
    	int age;
    	int number;
    	struct student *next;          /*一个指向该结构体类型的指针*/
    }STU;
    STU *start(STU *L,int n )          /*建立链表使用头插法（先来的在前）*/
    {
             int i;
    	STU *p;
             L=(STU *)malloc(sizeof(STU));  /*建立节点*/
    	(L)->next=NULL;
    	for(i=0;i<n;i++)
    	{
    		p=(STU *)malloc(sizeof(STU));
    		printf("please enter a name and something ");
    		scanf("%s %d %d",p->name,&p->age,&p->number);
    		//printf("%s %d %d\n",p->name,p->age,p->number);
    		p->next=(L->next);
    		(L)->next=p;
    	}
    	return L;
    }
    void print(STU *L);
    void print(STU *L)              /*输出链表*/
    {
    	//printf("********\n");
    	STU *temp;
    	//printf("********\n");
    	temp=L->next;
    	//printf("%p\n",temp);
    	while(temp!=NULL)
    	{
    	    //printf("********\n");
    		printf("%s %d %d  ****\n",temp->name,temp->age,temp->number);
    		temp=temp->next;
    	}
    }
    int main()
    {
    	int n;
    	STU *L;
    	printf("please enter a num");
    	scanf("%d",&n);
    	L=start(L,n);/*注意函数返回值的机制，又返回值必须有一个接受的变量*/
    	//printf("%p\n",L);
    	print(L);
    	return 0;
    }

#include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<string.h>
    typedef struct film             /*单链表的建立法2，尾插法*/
    {                               /*以一个结构体为一个节点*/
    	char *name;
    	//name=(char *)malloc(10*sizeof(char));
    	int num;
    	struct film *next;
    }FILM;
    FILM *make(FILM *L,int n)        /*建立单链表*/
    {
    	int i;
    	FILM *p,*r;
    	L=(FILM *)malloc(sizeof(FILM));
    	if(NULL==L)
    	{
    		return -1;
    	}
    	L->name=(char *)malloc(10*(sizeof(char)));
    	r=L;                                 /*使用R 来跟踪新建节点*/
    	for(i=0;i<n;i++)
    	{
    		p=(FILM *)malloc(sizeof(FILM));  
    		p->name=(char *)malloc(10*(sizeof(char)));
    		if(NULL==p)
    		{
    			return -1;
    		}
    		scanf("%s %d",p->name,&p->num);      /*将节点放到表尾*/
    		r->next=p;
    		r=p;
    	}
    	r->next=NULL;
    	return L;
    }
    void print(FILM *L);
    void print(FILM *L)                         /*输出函数*/
    {
    	FILM *pTemp;
    	pTemp=L->next;
    	while(pTemp!=NULL)
    	{
    		printf("%s %d",pTemp->name,pTemp->num);
    		pTemp=pTemp->next;
    		printf("\n");
    	}
    }
    int main()
    {
    	int n;
    	FILM *L;
    	printf("please enter some thing ");
    	scanf("%d",&n);
    	L=make(L,n);
    	//clearList(L);
    	print(L);
    	return 0;
    }
    int clearList(FILM *L);       /*删除一个链表*/
    int clearList(FILM *L)
    {
    	FILM *p,*q;
    	p=L->next;
    	while(p)
    	{
    		q=p->next;
    		free(q);
    		p=q;
    	}
    	L->next=NULL;
    	return 0;
    }
    int getelem(FILM *L,int i);
    int getelem(FILM *L,int i)           /*查找第i个节点的内容并显示*/
    {
    	int j;
    	FILM *p;
    	p=L->next;
    	j=1;
    	while(p && j<i)
    	{
    		p=p->next;
    		++j;
    	}
    	if(!q || j>i)
    	{
    		return -1;
    	}
    	else
    	{
    		printf("%s %d\n",p->name,p->num);
    	}
    	return 0;
    }
    
    int Listinsert(FILM *L,int i);      /*给I处增加一个节点*/
    int Listinsert(FILM *L,int i)
    {
    	int j;
    	FILM *p,*s;
    	p=L;
    	j=1;
    	while(p && i<j)
    	{
    		p=p->next;
    		++j;
    	}
    	if(!p||j>i)
    	{
    		return -1;
    	}
    	else
    	{
    		s=(FILM *)malloc(sizeof(FILM));
    		scanf("%s %d",s->name,&s->num);
    		s->next=p->next;
    		p-next=s;
    	}
    	return 0;
    }
    int Listdel(FILM *L ,int i);      /*删除一个节点*/
    int Listdel(FILM *L ,int i)
    {
    	int j;
    	FILM *p,*q;
    	p=*L;
    	j=1;
    	while(p->next && j<i)
    	{
    		p=p->next;
    		++j;
    	}
    	if(!(p->next) || j>i)
    	{
    		return -1;
    	}
    	else
    	{
    		q=p->next;
    		p->next=q->next;
    		free(q);
    	}
    	return 1;
    }

#include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<string.h>
    typedef struct film            /*建立一个只有头结点的单链表*/
    {
    	char *name;
    	int num;
    	struct film *next;
    }FILM;
    FILM *make(FILM *L,int n)
    {
    	int i;
    	FILM *p,*r;
    	L=(FILM *)malloc(sizeof(FILM));
    	r=L;
    	for(i=0;i<n;i++)
    	{
    		p=(FILM *)malloc(sizeof(FILM));
    		p->name=(char *)malloc(10*sizeof(char));
    		scanf("%s %d",p->name,&p->num);
    		r->next=p;
    		r=p;
    	}
    	r->next=NULL;
    	return L;
    }
    int main()
    {
    	int n;
    	FILM *L;
    	printf("please enter some thing");
    	scanf("%d",&n);
    	L=make(L,n);
    	print(L);
    	return 0;
    }
    int print(FILM *L);
    int print(FILM *L)
    {
    	FILM *pTemp;
    	pTemp=L->next;
    	while(pTemp!=NULL)
    	{
    		printf("%s %d\n",pTemp->name,pTemp->num);
    		pTemp=pTemp->next;
    	}
    }