单向链表的操作

2015 年 02 月 20 日

4558 次浏览

6664字数

#include <iostream>
using namespace std;
typedef char ElemType;//定义char类型的ElemType，方便修改
typedef struct LNode//定义一个结构体
{
    ElemType data;//链表数据区
    LNode *next;//链表指针区
}LinkList;

void initList(LinkList * & L)
{
    L=(LinkList *)malloc(sizeof(LinkList));//为链表开辟空间
    L->next=NULL;//带头节点的顺序链表
}
void createList (LinkList * &L,ElemType a[],int n)//插入数据
{
    int i;
    LinkList *p;
    for(i=0;i<n;i++)//头插法 ，输出结果是逆序的
    {
        p=(LinkList *)malloc(sizeof(LinkList));
        p->data=a[i];
        p->next=L->next;
        p->next=p;
    }
}
int locateElem(LinkList *L,ElemType e)//查找元素
{
    LinkList *p=L->next;//第一个元素
    int i=1;
    while (p&&p->data!=e)//判断链表是否为空，然后查找链表里的元素
    {
        p=p->next;
        i++;
    }
    if(!p)//查找完了，没找到
    {
        cout<<"没有这个元素!"<<endl;
        return 0;
    }
    return i;
}
void listInsert(LinkList * &L,int i,ElemType e)//插入一个元素
{
    //[i>=1&&i<=size+1]
    if(i<=0)
    {
        cout<<"无法插入!"<<endl;
        return;
    }
    //1.检查i<＝size＋1   2.找到插入位置
    int j=0;
    LinkList *p=L,*q;
    while (p&&j<i-1)//p不存在退出，j>=i-1退出
    {
        j++;
        p=p->next;
    }
    if(!p)
    {
        cout<<"无法插入!"<<endl;
        return;
    }
    q=(LinkList *)malloc(sizeof(LinkList));//开辟一个q链表
    q->data=e;
    q->next=p->next;
    //插入节点 （p插入位置前面一个元素，q需要插入的元素）
    p->next=q;
    cout<<"插入完成!"<<endl;
}
void nixuList(LinkList *&L)//逆序
{
   
    LinkList *p,*t,*q;
    if(L==NULL||L->next==NULL)
    {
        cout<<"无法逆序输出!"<<endl;
        return;
    }
    p=L->next;
    t=p->next;
    p->next=NULL;
   
    while(t)//
    {
        q=t->next;
        t->next=L->next;
        L->next=t;
        t=q;
    }
}
void  listDelete(LinkList * &L,int i)//删除一个元素（位置）
{
    if(i<=0)
    {
        cout<<"无法删除!"<<endl;
        return;
    }
    //1.检查i<＝size＋1   2.找到插入位置
    int j=0;
    LinkList *p=L,*q;
    while (p&&j<i-1)//p不存在退出，j>=i-1退出
    {
        j++;
        p=p->next;
    }
    if(!p)
    {
        cout<<"无法删除!"<<endl;
        return;
    }
    else
    {
        //p要删除的元素的前一个
        q=p->next;//要删除的对象
        if(q==NULL)
        {
            cout<<"无法删除!"<<endl;
            return;
        }
        p->next=q->next;
        free(q);
        cout<<"删除成功!"<<endl;
    }

}
void dispList(LinkList*L)
{
    if(L==NULL||L->next==NULL)
    {
        cout<<"链表为空！"<<endl;
        return;
    }
    LinkList *p=L->next;
    while (p)
    {
        printf("%c ",p->data);
        p=p->next;
    }
    putchar('\n');
}
void destroyList (LinkList *&L)//销毁链表
{
    LinkList *p=L->next;//指向第一个元素
    while (L->next)
    {
        L->next=p->next;
        free(p);//释放原来第一个元素
        p=L->next;//p指向第一个元素
    }
    //free(p);//要不要？
    free(L);//释放head
    L->next=NULL;
    cout<<"销毁完成!"<<endl;
}
int main(int argc, const char * argv[])
{
    LinkList *p = nullptr;
    int n,j;
    printf("                  *******************\n");
    printf("                  1.创建单链表        \n");
    printf("                  2.查找单链表元素    \n");
   
    printf("                  3.插入元素         \n");
   
    printf("                  4.删除元素         \n");
   
    printf("                  5.输出链表元素     \n");
   
    printf("                  6.销毁单链表       \n");
   
    printf("                  7.逆序输出       \n");
   
    printf("                  8.退出             \n");
   
    printf("                  *******************\n");
   
    while(1)
        
    {
        
        printf("选择(1-8):");
        
        scanf("%d",&n);
        
        switch(n)
        
        {
               
            case 1:
               
                ElemType elem_create,elem[50];
               
                printf("请输入元素(头插)(字符之间无空格):\n");
               
                getchar();
               
                j=0;
               
                while((elem_create=getchar())!='\n')
                    
                    elem[j++]=elem_create;
               
                initList(p);
               
                createList(p,elem,j);
               
                printf("链表创建完成!\n\n");
               
                break;
               
            case 2:
               
                ElemType elem_search;
               
                printf("请输入要查找的元素:");
               
                getchar();
               
                elem_search=getchar();
               
                if(locateElem(p,elem_search))
            //  if(locateElem(p,elem_search))
                    
                    printf("要查找的元素是第%d个数据结点
\n",locateElem(p,elem_search));
               
                else
                    
                    printf("找不到元素%c\n\n",elem_search);
               
                break;
               
            case 3:
               
                int loc_insert;
               
                ElemType elem_insert;
               
                printf("输入插入位置和元素(逗号隔开):");
               
                scanf("%d,%c",&loc_insert,&elem_insert);
               
                listInsert(p,loc_insert,elem_insert);
               
                break;
               
            case 4:
               
                int loc_del;
               
                printf("输入删除位置:");
               
                scanf("%d",&loc_del);
               
                listDelete(p,loc_del);
               
                break;
               
            case 5:
               
                printf("链表元素有:\n");
               
                dispList(p);
               
                putchar('\n');
               
                break;
               
            case 6:
               
                destroyList(p);
               
                break;
            case 7:
                printf("逆序输出!\n");
                nixuList(p);
                break;
               
            case 8:
               
                return 0;
               
            default:
               
                printf("请输入正确的数字!\n\n");
               
        }
        
    }
   
}