C语言链式结构表2

我会带着你远行 2022-07-15 05:24 150阅读 0赞

//单链表（线性表的链式存储）的实现
    
    #include <stdio.h>
    #include <stdlib.h>
    
    //定义数据类型
    typedef int datatype_t;
    
    //定义结构体
    typedef struct node{
    	datatype_t data;
    	struct node *next;
    }linklist_t;
    
    //创建一个空的单链表
    linklist_t *linklist_create()
    {
    	linklist_t *h;
    	h = (linklist_t *)malloc(sizeof(linklist_t));
    
    	h->next = NULL;
    	
    	return h;
    }
    
    //插入数据（头插法）
    int linklist_insert_head(linklist_t *h, datatype_t value)
    {
    	linklist_t *temp = (linklist_t *)malloc(sizeof(linklist_t)); //创建一个新的结点
    	temp->data = value; //赋值
    
    	temp->next = h->next; //新创建的结点指向头结点的下一个结点
    	h->next = temp; //头结点指向新创建的结点
    	
    	return 0;
    }
    
    //插入数据（尾插法）
    int linklist_insert_tail(linklist_t *h, datatype_t value)
    {
    	linklist_t *temp = (linklist_t *)malloc(sizeof(linklist_t));
    	temp->data = value;
    
    	while(h->next != NULL)
    	{
    		h = h->next;
    	}
    
    	h->next = temp;
    	temp->next = NULL;
    
    	return 0;
    }
    
    //打印数据
    int linklist_show(linklist_t *h)
    {
    	while(h->next != NULL)
    	{
    		h = h->next;
    		printf("%d ", h->data);
    
    		//printf("%d ", h->next->data);
    		//h = h->next;
    	}
    
    	putchar(10);
    
    	return 0;
    }
    
    //删除数据（头删法）
    datatype_t linklist_delete_head(linklist_t *h)
    {
    	//第一步：直接删除，不要返回值
    	//h->next = h->next->next;
    
    	//第二步：需要返回值
    	//datatype_t value = h->next->data;
    	//h->next = h->next->next;
    
    	//第三步：需要返回值，并且需要释放
    	linklist_t *temp = NULL;
    	temp = h->next;
    
    	datatype_t value = temp->data;
    	h->next = temp->next;
    	
    	free(temp);
    	temp = NULL;
    
    	return value;
    }
     
    //更改数据
    int linklist_change_value(linklist_t *h, datatype_t old_value, datatype_t new_value)
    {
    	while(h->next != NULL)
    	{
    		if(h->next->data == old_value)
    		{
    			h->next->data = new_value;
    			return 0;
    		}
    		else
    		{
    			h = h->next;
    		}
    	}
    
    	printf("value is not exist\n");
    	return -1;
    }
    
    //根据数据查找位置
    int linklist_search_value(linklist_t *h, datatype_t the_value)
    {
    	int pos = 0;
    
    	while(h->next != NULL)
    	{
    		if(h->next->data == the_value)
    		{
    			return pos;
    		}
    		else
    		{
    			pos++;
    			h = h->next;
    		}
    	}
    
    	printf("the value is not exist\n");
    	return 0;
    }
    
    //按照位置插入数据
    int linklist_insert_pos(linklist_t *h, int pos, datatype_t value)
    {
    	int i = 0;
    	linklist_t *temp = (linklist_t *)malloc(sizeof(linklist_t));
    	temp->data = value;
    	
    	while(i < pos && h->next != NULL)
    	{
    		h = h->next;
    		i++;
    	}
    
    	temp->next = h->next;
    	h->next = temp;
    
    	return 0;
    }
    
    //按照顺序插入数据
    int linklist_insert_sort(linklist_t *h, datatype_t value)
    {
    	linklist_t *temp = (linklist_t *)malloc(sizeof(linklist_t));
    	temp->data = value;
    
    	while(h->next != NULL && h->next->data < temp->data)
    	{
    		h = h->next;
    	}
     
    	temp->next = h->next;
    	h->next = temp;
    
    	return 0;
    }
    
    //实现链表的翻转：让第一项指向NULL 第二项指向第一项，
    //第三项指向地二项，第四项指向第三项...以此类推 最后使head指向最后一项 
    int linklist_recover(linklist_t *head)
    {
    	//把头结点的下一个结点（第一个数据结点）赋值给p 
    	linklist_t *p = head->next;
    	//定义空的q结点 
    	linklist_t *last = NULL;
        //把头结点的下一个结点设置为NULL 
    	head->next = NULL;
    
    	while(p != NULL)//如果数据结点不为NULL 
    	{
    		last = p;//把p数据结点赋值给last 
    		p = p->next;//p再跳到下一个结点 
    
    		last->next = head->next;//第一次赋值 last为第一个值  把其下一个结点设置为NULL 
                                    //第二次赋值 last为第二个值 把其下一个结点设置为 其上一个值 
    		printf("last->data=%d    ",last->data);
    		head->next = last;
    	}
    
    	return 0;
    }
    
    int main(int argc, const char *argv[])
    {
    //	linklist_t *h = linklist_create();
    
    //	linklist_insert_head(h, 10);
    //	linklist_insert_head(h, 20);
    //	linklist_insert_head(h, 30);
    ///	linklist_insert_head(h, 40);
    //	linklist_insert_head(h, 50);
    //	linklist_insert_head(h, 60);
    //	linklist_show(h);
    
    //	linklist_insert_tail(h, 20);
    //	linklist_insert_tail(h, 30);
    	linklist_insert_tail(h, 40);
    //	linklist_insert_tail(h, 50);
    //	linklist_insert_tail(h, 60);
    //	linklist_show(h);
    
    //	printf("del = %d\n", linklist_delete_head(h));
    //	linklist_show(h);
    	
    //	linklist_change_value(h, 30, 70);
    //	linklist_show(h);
    
    //	printf("value = 70, pos = %d\n", linklist_search_value(h, 70));
    
    //	linklist_insert_pos(h, 3, 80);
    //	linklist_show(h);
    
    //	printf("*********************\n");
    
    	linklist_t *h1 = linklist_create();
    //
    	linklist_insert_sort(h1, 10);
    	linklist_insert_sort(h1, 40);
    	linklist_insert_sort(h1, 30);
    	linklist_insert_sort(h1, 60);
    	linklist_insert_sort(h1, 50);
    	linklist_insert_sort(h1, 40);
    	linklist_show(h1);	
    //
    
        
    	linklist_recover(h1);
    	linklist_show(h1);
    
    	return 0;
    }