数据结构中之线性表中单链表的基本操作

缺乏、安全感 2022-08-14 00:54 215阅读 0赞

数据结构中线性表中的单链表的基本操作实现，对于单链表，其主要的操作有创建、取元素、插入、删除等操作。首先我们看一下链表的结构的表达：

#define elementype int
    
    typedef struct{
        elementype  data;
        struct node * next; 
    } node;

1、首先我们看一下链表的创建，输入n个元素的值，建立带有表头节点的单链线性表，每次新增的元素都插入到链表的尾部。

node* CreateList_l(int n)
 {
     node* head,p,q;   
     head=(node*)malloc(sizeof(node));
     head->next=NULL;
     q=head;
     for(int i=n;n<1;n--)
     {
               node* p=(node*)malloc(sizeof(node));
               scanf(&p->data);
               q->next=p;
               q=p;
     }    
     return head;
 }

2、接着我们看一下如何再一个链表中取一个元素，这里是取链表中第i个元素的值，首先需要判断第i个元素是否存在，函数如下：

int GetElem_l(node* head，int i，elementype &e)
 {
        int j=0;
        node *p;
        p=head;
        while(p&j<i)
       {    
              p=p->next;
              j++;
       }
       if(NULL==p||j>i)
       {
             printf("i error");
             return 0;
       } 
       else
       { 
             e=p->data;
             return 1； 
       }
 }

3、链表中插入新的节点，这里主要实现在第i-1与第i个数据元素之间插入一个新的元素。

int ListInsert_l(node* head,int i,elementype e)
 {
     //首先寻找的第i-1个元素;
     node* p=head;
     int j=0;
     while(p&&j<i-1)
     {
         p=p->next;
         j++;
     }
     if(NULL==p||j>i-1)
     {
         printf("i error");    
         return 0;
     }
 
     node* q=(node*)malloc(sizeof(node));
     q->data=e;
     q->next=p->next;
     p->next=q;
     
     return 1;        
 }

4、链表节点的删除，再带头节点的单链表中，删除第i个元素，并由e返回其值，head为单链表的头;

//单链表中节点的删除;
 int ListDelete_l(node* head,int i,elementype &e)
 {
 	node* p=head;
 	int j=0;
 	while(p->next&&j<i-1)
 	{
 		p=p->next;
 		j++;
 	}
 	if(NULL==p||j>i-1)
 	{
 		printf("i error")'
 		return 0;
 	}
 	
 	node* q=p->next;
 	p->next=q->next;
 	e=q->data;
 	free(q);
 	printf("OK");
 	return 1;
 	
 }

5、总结，单链表是数据结构中用的最多的一种结构，其操作也有很多种，记住其主要的基本特性，即可为我们的程序带来更多的效率，声明一下，代码是参照书籍，纯txt文本中敲出来，可能会有错误，如果有望大家指正。