单链表的创建及操作

迈不过友情╰ 2023-07-12 08:47 18阅读 0赞

1、创建一个带头结点的单链表（头指针为head），且遍历此链表（输出链表中各结点的值）；  
2、查找单链表中的第i个结点，并输出结点元素的值；  
3、在单链表中的第i个结点前插入一个结点值为e的正整数(从外部输入);  
4、删除单链表中的第j个结点；  
\*5、将单链表中的各结点就地逆序（不允许另建一个链表）；

#include<windows.h>
    #include<stdio.h>
    #include<iostream>
    using namespace std;
    #define N 8
    typedef struct Lnode
    {
        
    	int data;
    	struct Lnode *next;
    }Lnode, *Linklist;//类型定义
    				  //函数声明
    
    void Initlist(Linklist L)//初始化单链表
    {
        
    	L = (Lnode*)malloc(sizeof(Lnode));
    	if (L == NULL)
    	{
        
    		cout << "申请空间失败！";
    		exit(0);
    	}
    	else L->next = NULL;
    }
    
    Linklist Createndlist(int a[N])//尾插法创建一个单链表（顺序输入一个数组）
    {
        
    	Linklist L;
    	L = (Lnode*)malloc(sizeof(Lnode));
    	if (L == NULL)
    	{
        
    		cout << "error";
    		exit(0);
    	}
    	else L->next = NULL;
    	Linklist tail, p;
    	tail = L;
    	int j;
    	for (j = 0; j < N; j++)
    	{
        
    		p = (Lnode*)malloc(sizeof(Lnode));
    		if (p == NULL)
    		{
        
    			cout << "error";
    			exit(0);
    		}
    		else p->next = NULL;
    		p->data = a[j];
    		tail->next = p;
    		tail = p;
    	}
    	tail->next = NULL;
    	return L;
    
    }
    
    Linklist Greatheadlist(int a[N])//头插法创建一个单链表（逆序输入一个数组）
    {
        
    	int j;
    	Linklist L;
    	L = (Lnode*)malloc(sizeof(Lnode));
    	if (L == NULL)
    	{
        
    		cout << "error";
    		exit(0);
    	}
    	else L->next = NULL;
    	for (j = 0; j < N; j++)
    	{
        
    		Linklist p;
    		p = (Lnode*)malloc(sizeof(Lnode));
    		if (p == NULL)
    		{
        
    			cout << "error";
    			exit(0);
    		}
    		else p->next = NULL;
    		p->data = a[j];
    		p->next = L->next;
    		L->next = p;
    	}
    	return L;
    }
    
    void GetElem(Linklist L)//获取单链表中第i个值
    {
        
    	int i, j = 0;
    	cout << "请输入你要获取第__个值:";
    	cin >> i;
    	Linklist p;
    	p = L->next;
    	while (p&&j < i - 1)
    	{
        
    		p = p->next;
    		j++;
    	}
    	if (!p || j > i - 1)
    		cout << "error";
    	else
    	{
        
    		printf("第%d个元素为：", i);
    		cout << p->data;
    		cout << endl;
    	}
    }
    
    void putlist(Linklist L)//输出单链表
    {
        
    	int i;
    	Linklist p;
    	p = L->next;
    	cout << "当前链表为：";
    	while (p != NULL)
    	{
        
    		cout << p->data << " ";
    		p = p->next;
    	}
    	cout << endl;
    }
    
    Linklist Insertlist(Linklist L)//在第i个元素前插入一个元素
    {
        
    	int i, j = 0, x;
    	cout << "请依次输入你要在第__个元素前插入__:";
    	cin >> i >> x;
    	Linklist p, q, pre;
    	p = L->next;
    	while (p&&j < i - 1)
    	{
        
    		p = p->next;
    		j++;
    	}
    	q = (Lnode*)malloc(sizeof(Lnode));
    	if (q == NULL)
    	{
        
    		cout << "error";
    		exit(0);
    	}
    	else q->next = NULL;
    	q->data = x;
    	pre = L;
    	while ((pre != NULL) && (pre->next != p))           //寻找p的前驱
    	{
        
    		pre = pre->next;
    	}
    	q->next = pre->next;
    	pre->next = q;
    
    	return L;
    }
    
    Linklist Deletelist(Linklist L)//删除第i个元素
    {
        
    	int i, j = 0;
    	cout << "请输入你要删除第__个元素";
    	cin >> i;
    	Linklist p, pre;
    	p = L->next;
    	while (p&&j < i - 1)
    	{
        
    		p = p->next;
    		j++;
    	}
    	pre = L;
    	while ((pre != NULL) && (pre->next != p))      //查找元素e的前驱
    	{
        
    		pre = pre->next;
    	}
    	p = pre->next;
    
    	if (p != NULL)                //找到需要删除的结点
    	{
        
    		pre->next = p->next;
    		free(p);
    	}
    	return L;
    }
    
    Linklist Clearlist(Linklist L)//清空单链表
    {
        
    	Linklist p;
    	p = (Lnode*)malloc(sizeof(Lnode));
    	while (L->next)
    	{
        
    		p = L->next;
    		L->next = p->next;
    		free(p);
    	}
    	return L;
    }
    
    Linklist Inverselist(Linklist L)//将单链表就地逆序
    {
        
    	Linklist  p, q;
    	p = L->next;
    	L->next = NULL;
    	while (p != NULL)
    	{
        
    		q = p->next;
    		p->next = L->next;
    		L->next = p;
    		p = q;
    	}
    	return L;
    }