单链表基本操作

#include<iostream>
#include"stdlib.h"
using namespace std;
typedef struct node          //定义结点
{
    int data;             //结点的数据域为整型
    struct node *next;      //结点的指针域
}ListNode;

int dataflag = 0;
int reverseflag = 0;
typedef ListNode * LinkList;         // 自定义LinkList单链表类型

LinkList CreatListR1(LinkList head);              //函数，用尾插入法建立带头结点的单链表

ListNode *LocateNode(LinkList head, int key);              //函数，按值查找结点

void DeleteList(LinkList head,int key);                   //函数，删除指定值的结点

void printlist(LinkList head);                    //函数，打印链表中的所有值

void DeleteAll(LinkList *L);                    //函数，删除所有结点，释放内存

void DeletePioneer(LinkList head, int x);//删除指定值的前驱结点

void DeleteRepeat(LinkList head);//删除重复

void DeleteUI();//删除界面

LinkList InvertedSequence(LinkList head2);//逆序

void ui();



//==========主函数==============


void main()
{
  int num, key, x, choose, dechoose, fichoose;
  char ch;
  LinkList head, t, head2;
  t = (LinkList)malloc( sizeof(ListNode));
  while(1)
  {
    system("cls");
    ui();
    cin>>choose;
    if(choose == 1)
    {
        head = CreatListR1(head);          //用尾插入法建立单链表，返回头指针
        printlist(head);             //遍历链表输出其值
        printf("\n");
        cout<<"按任意键返回"<<endl;
        fflush(stdin);
        getchar();
    }
    else if(choose == 2)
    {
        system("cls");
        DeleteUI();
        printlist(head);
        cin>>dechoose;
        if(dechoose == 1)
        {
            cout<<"请输入删除的值:";
            scanf("%d",&key);
            DeleteList(head,key);
            printlist(head);
        }
        else if(dechoose == 2)
        {
            printlist(head);
            cout<<"请输入删除的值:";
            scanf("%d",&key);
            DeletePioneer(head,key);
            printlist(head);
        }
        else if(dechoose == 3)
        {
            DeleteRepeat(head);
            printlist(head);
        }
        else if(dechoose == 4)
        {
            DeleteAll(&head);
        }
        else
        {

        }
        fflush(stdin);
        cout<<"按任意键回到主界面"<<endl;
        getchar();
    }
    else if(choose == 3)
    {
        printlist(head);
        if(dataflag == 1)
        {
        cout<<"请输入查找的值:";
        scanf("%d",&key);
        LocateNode(head, key);
        }
        fflush(stdin);
        cout<<"按任意键返回"<<endl;
        getchar();
    }
    else if(choose == 4)
    {
        printlist(head);
        fflush(stdin);
        cout<<"按任意键返回"<<endl;
        getchar();
    }
    else if(choose == 5)
    {
        printlist(head);             //遍历链表输出其值
        head2 = InvertedSequence(head);
        reverseflag = 1;
        printlist(head2);
        reverseflag = 0;
        fflush(stdin);
        cout<<"按任意键返回"<<endl;
        getchar();
    }
    else
    {
        return;
    }
  }
}
void ui()
{
    printf(" 欢迎进入单链表操作界面\n");
    printf(" 1.插入数据\n");
    printf(" 2.删除数据\n");
    printf(" 3.查找数据\n");
    printf(" 4.显示数据\n");
    printf(" 5.逆序显示数据\n");
    printf(" 6.退出程序\n");
}
void DeleteUI()
{
    printf(" 删除界面\n");
    printf(" 1.删除当前节点数据\n");
    printf(" 2.删除前驱节点数据\n");
    printf(" 3.删除重复节点数据\n");
    printf(" 4.删除所有节点数据\n");
    printf(" 5.返回主界面\n");
}
LinkList CreatListR1(LinkList head)//尾插法
 {
    int n, i;
    int x;
    LinkList p, q;
    head = (LinkList)malloc( sizeof(ListNode));
    head->next = NULL;
    cout<<"请输入结点数量:";
    cin>>n;
    cout<<"请输入结点值:";
    for(i = 0; i < n; i++)
    {
        //非递减有序单链表输入
        while(1)
        {
            scanf("%d",&x);
            if(i == 0 ||x >= q->data)
                break;
            else
            {
                printf("输入错误,请重新输入\n");
            }
        }
        //scanf("%d",&x);
        p = (LinkList)malloc( sizeof(ListNode));
        p->data = x;
        p->next = NULL;
        if(head->next == NULL)
            head->next = p;
        else 
            q->next = p;
        q = p;
    }
    q->next = NULL;
    dataflag = 1;//表示有数据
    return head;        //返回头指针
}
ListNode *LocateNode(LinkList head, int key)//按值查找
{
    LinkList p;
    p = head->next;
    while( p != NULL&& p->data != key)
    {
        p = p->next;
    }
    if(p != NULL)
    {
        cout<<"找到了";
        cout<<p->data<<endl;
        return p;
    }
    else
    {
        cout<<"没找到\n";
        return NULL;
    }
}


void DeleteList(LinkList head,int key)//删除值为key的节点
{
    //按key值查找结点的
    //若没有找到结点，退出
    //若找到，则从单链表中删除该结点，并释放结点
    LinkList p, q, t;
    p = head->next;
    q = head->next;
    while(   p != NULL&& p->data != key )
    {
    // cout<<"p"<<endl;
        p = p->next;
        q = p;
    }
    if(q == head->next) //q是第一个节点
    {
        head->next = q->next;
        free(q);
        return;
    }
    //q是p的前一个节点
    t = head->next;
    while(t->next != q)
    {
        t = t->next;
    }
    //t是q的前一个节点
    if(p != NULL)//找到了删除q这个结点
    {
    // cout<<"t"<<endl;
        t->next = q->next;  
    }
    else//没找到
    {
        cout<<"数据中没有这个值,删除失败"<<endl;
        return;
    }
    free(q);
}
void DeletePioneer(LinkList head, int x)//删除指定结点的前驱结点
{
    LinkList p, q, t;
    p = head->next;
    while(p && p->data != x)
    {
        q = p;
        p = p->next;    
    }//q是p的前驱结点目的删除q
    t = head->next;
    while(t->next != q)
    {
        t = t->next;
    }//t是q的前驱结点
    if(p != NULL)
    {
        t->next = p;
        free(q);
    }
    else
    {
        printf("链表中无其值\n");
    }
}
void DeleteAll(LinkList *L)//删除所有结点
{
    LinkList p, q;
    p = (*L)->next;
    while(p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    dataflag = 0;
    printf("所有结点已删除\n");
} 

void printlist(LinkList head)//打出结点
{
    LinkList t;
    t = head->next;
    if(t == NULL)
    {
        printf("无数据\n");
        return;
    }
    if(reverseflag != 1)
    cout<<"\n当前所有数据为:";
    else if(reverseflag == 1)
        cout<<"\n逆序显示所有数据：";
    while(t != NULL)
    {
        cout<<t->data<<' ';
        t = t->next;
    }
    printf("\n");
}
void DeleteRepeat(LinkList head)
{
    LinkList t, k, q;
    for(t = head->next;t->next != NULL && t != NULL;)
    {
        if(t->data == t->next->data)//前一个等于后一个
        {
            q = t->next;
            t->next = q->next;
            free(q);
        }
        else
        {
        t = t->next;
        }
    }
}
//单链表逆序 取出来数据 用头插法插给另一个链表
LinkList InvertedSequence(LinkList head2)
{
    LinkList t, p;
    int x;
    t = head2->next;
    head2 = (LinkList)malloc( sizeof(ListNode));
    head2->next = NULL;
    while(t != NULL)
    {
        x = t->data;
        p = (LinkList)malloc( sizeof(ListNode));
        p->data = x;
        p->next = head2->next;
        head2->next = p;
        t = t->next;
    }
    return head2;
}