数据结构：链表

实验目标：

提示

（1）用头插法创建单链表

（2）用尾插法创建单链表

（3）在单链表中查找第i个元素

（4）在单链表中第i个位置插入元素

（5）在单链表中删除第i个位置的元素

（6）在单链表中删除e元素

（7）遍历单链表

（8）销毁单链表

（9）退出

---

实验代码

#include <bits/stdc++.h>
using namespace std;

//这代码写的真丑

struct Node//定义一个结点
{
    int data;
    struct Node* next;
};

struct Node* CreateListHead()//创建一个链表
{
    struct Node* headNode=(struct Node*)malloc(sizeof(struct Node));//分配空间以创建链表
    headNode->next=NULL;
    return headNode;
}

struct Node* CreateNode(int data)//创建一个结点
{
    struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));//分配空间以创建结点
    newNode->data=data;
    newNode->next=NULL;
    return newNode;
}

void ShowList(struct Node* headNode)//展示链表
{
    struct Node* pmove=headNode->next;
    while(pmove){
        int x;
        x=pmove->data;
        cout<<x<<' ';
        pmove=pmove->next;
    }
    cout<<endl;
}

void ShowNode(struct Node* headNode,int i)//展示第i位置的元素
{
	struct Node* pos=headNode->next;
    int j=1;

    while(pos!=headNode && j<=i-1){
        j++;
        pos=pos->next;
    }

	int x=pos->data;
	cout<<"链表中第i位置的元素为："<<x<<endl;
}

void InsertNodeHead(struct Node* headNode,int data)//头插法插入新元素
{
    struct Node* newNode=CreateNode(data);
    newNode->next=headNode->next;
    headNode->next=newNode;
}

void InsertNodeTail(struct Node* headNode,int data)//尾插法插入新元素，用结点指针一个一个遍历，p=p->next
{
	struct Node* newNode=CreateNode(data);
    struct Node* p=headNode->next;

    if(p==NULL) newNode=headNode->next;//当链表为空链表时

    else{
        while(p->next!=NULL){
            p=p->next;
        }
        p->next=newNode;
    }
}

void DeleteNodeHead(struct Node* headNode,int posdata)//删除尾结点
{
    struct Node* posNode=headNode->next;
    struct Node* posNodeFront=headNode;

    if(posNode==NULL) cout<<"链表为空"<<endl;//判断链表是否为空
    else{
        while(posNode->data!=posdata){
            posNodeFront=posNode;
            posNode=posNodeFront->next;

            if(posNode==NULL){
                cout<<"未找到相关信息"<<endl;
                break;
            }
        }
        posNodeFront->next=posNode->next;
        free(posNode);
    }
}

void InsertNode(struct Node* headNode,int i,int newdata)//在任意位置差入元素
{
    struct Node* FrontNode=headNode;
    struct Node* NextNode=FrontNode->next;
    struct Node* newNode=CreateNode(newdata);

    for(int j=1;j<=i-1;j++)
    {
        FrontNode=NextNode;
        NextNode=FrontNode->next;
    }

    FrontNode->next=newNode;
    newNode->next=NextNode;
}

void DeleteNode(struct Node* headNode,int i)//删除链表第i个元素
{
    struct Node* FrontNode=headNode;
    struct Node* NextNode=FrontNode->next;
    NextNode=NextNode->next;

    if(FrontNode==NULL) cout<<"该链表为空"<<endl;
    else{
         for(int j=1;j<=i-1;j++){
            FrontNode=FrontNode->next;
            NextNode=NextNode->next;
        }

        if(NextNode==NULL){
            FrontNode->next=NextNode;

            if(NextNode==NULL){
                NextNode=FrontNode;
            }
        }
        else FrontNode->next=NextNode;
    }
}

void DeleteNode_data(struct Node* headNode,int e)//删除第一个值为e的元素
{
    struct Node* frontNode=headNode;
    struct Node* posNode=frontNode->next;
    struct Node* nextNode=posNode->next;

    if(frontNode==NULL) cout<<"该链表为空"<<endl;
    else{
        
        while(posNode->data!=e)
		{
            frontNode=frontNode->next;
            posNode=posNode->next;
               nextNode=nextNode->next;
        }
            frontNode->next=posNode->next;
        
        free(posNode);
        cout<<"已成功删除"<<endl;
    }
}

bool ClearList(struct Node* headNode)//销毁链表
{
    if(headNode->next ==headNode){//判断是否为空链表
        cout<<"该链表为空，不需删除！"<<endl;
        return false;
    }

    struct Node* p=headNode->next;
    struct Node*q;
    while(p != NULL){//逐一删除
        q=p->next;
        free(p);
        p=q;
    }
    p=headNode->next;
    cout<<"清空成功！"<<endl;
    return true;
}

int main()
{
    struct Node* L=CreateListHead();
	while(1){
        cout<<endl;
		cout<<"**1,用头插法创建单链表"<<endl;
		cout<<"**2,用尾插法创建单链表"<<endl;
	    cout<<"**3,在单链表中查找第i个元素"<<endl;
	    cout<<"**4,在单链表中第i个位置插入元素"<<endl;
		cout<<"**5,在单链表中删除第i个位置的元素"<<endl;
		cout<<"**6,在单链表中删除e元素"<<endl;
        cout<<"**7,遍历单链表"<<endl;
        cout<<"**8,销毁单链表"<<endl;
		cout<<"**9,退出系统"<<endl<<endl;

		int choice;
	    cout<<"请输入您要进行的操作：";
	    cin>>choice;

	    switch(choice)
	    {
	        case 1:{
				int n;
				cout<<"请输入您本次要输入的元素的个数：";
				cin>>n;
				cout<<endl<<"请输入您要输入的元素：";
				for(int i=1;i<=n;i++)
				{
					int data;
					cin>>data;
					InsertNodeHead(L,data);
				}

				cout<<endl<<"您链表中的元素有：";
				ShowList(L);
		        break;
		    }

	        case 2:{
                int n;
				cout<<"请输入您本次要输入的元素的个数：";
				cin>>n;
				cout<<endl<<"请输入您要输入的元素：";
				for(int i=1;i<=n;i++)
				{
					int data;
					cin>>data;
					InsertNodeTail(L,data);
				}

				cout<<endl<<"您链表中的元素有：";
				ShowList(L);
		        break;
            }

		    case 3:{
			    int i;
			    cout<<"请输入要查找的位置：";
			    cin>>i;
			    cout<<endl;

				ShowNode(L,i);

			    break;
			}

	        case 4:{
				int i,newdata;
				cout<<"请输入要插入的位置：";
				cin>>i;
			    cout<<endl<<"请输入要插入的元素：";
				cin>>newdata;

				InsertNode(L,i,newdata);

				cout<<endl<<"更新后的链表为：";
				ShowList(L);
				break;
            }

		    case 5:{
				int i;
				cout<<"请输入要删除的位置:";
                cin>>i;
				DeleteNode(L,i);

				cout<<endl<<"更新后的链表为：";
				ShowList(L);
				break;
			}

	        case 6:{
                int data;
                cout<<"请输入您要删除的元素的值：";
                cin>>data;
                cout<<endl;
                DeleteNode_data(L,data);
                break;}

            case 7:ShowList(L);break;

            case 8:ClearList(L);break;

            case 9:exit(0);
        }
    }

    system("pause");
    return 0;
}