spy 发表于 2015-3-27 17:21:35

链表集合上的各种操作

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

struct Node
{
        int data;
        struct Node * next;
};

struct Node * CreateList();
void InsertList(struct Node *, int, int);
void DeleteList(struct Node *, int, int*);
int LocateNode(struct Node *, int);
void ListTraverse(struct Node *);
int IsEmpty(struct Node *);
int ListLength(struct Node *);


void main()
{
        struct Node *head = NULL;
        int n, i, value;
        char ch;

        printf("\n");
        printf("------------------------");
        printf("\n\n");
        printf("1.初始化链表\n");
        printf("2.插入结点\n");
        printf("3.删除结点\n");
        printf("4.返回结点位置\n");
        printf("5.遍历链表\n");
        printf("0.退出\n\n");

        printf("请选择您的操作: ");
        scanf("%d", &n);
        putchar('\n');

        while(n)
        {
                switch(n)
                {
                case 1:
                        {
                                head = CreateList();
                                if(IsEmpty(head))
                                {
                                        break;
                                }
                                else
                                {
                                        ListTraverse(head);
                                }
                                break;
                        }

                case 2:
                        {
                                if(IsEmpty(head))
                                {
                                        printf("链表为空,请初始化链表!");
                                        break;
                                }
                                else
                                {
                                        printf("输入需要插入结点的位置? ");
                                        scanf("%d", &i);
                                        while(i<1 || i>ListLength(head)+1)
                                        {
                                                printf("插入的位置非法, 是重新输入还是放弃当前操作?(Y/N)\n");
                                                getchar();             //之前输入的回车符还存在缓冲区,需要清除后才能正确接受当前的输入
                                                ch = getchar();
                                                if('N'==toupper(ch))
                                                {
                                                        putchar('\n');
                                                        goto SELECT;
                                                }
                                                else
                                                        if('Y'==toupper(ch))
                                                        {
                                                                printf("输入需要插入结点的位置? ");
                                                                scanf("%d", &i);
                                                        }
                                                        else
                                                        {
                                                                printf("error!\n");
                                                        }
                                        }
                                        printf("输入要插入结点的值: ");
                                        scanf("%d", &value);
                                        InsertList(head, i, value);
                                        printf("在位置%d插入值后:\n\n", i);
                                        ListTraverse(head);

                                        /*while(1)
                                        {
                                                if(i<1 || i>ListLength(head)+1)
                                                {
                                                        printf("插入的位置非法, 是重新输入还是放弃当前操作?(Y/N)\n");
                                                        getchar();             //之前输入的回车符还存在缓冲区,需要清除后才能正确接受当前的输入
                                                        if('n'==getchar())
                                                        {
                                                                putchar('\n');
                                                                goto SELECT;
                                                        }
                                                        else
                                                        {
                                                                printf("输入需要插入结点的位置? ");
                                                                scanf("%d", &i);
                                                        }
                                                }
                                                else
                                                {
                                                        break;
                                                }
                                        }
                                        printf("输入要插入结点的值: ");
                                        scanf("%d", &value);
                                        InsertList(head, i, value);
                                        printf("在位置%d插入值后:\n\n", i);
                                        ListTraverse(head);
                                        break;*/
                                }
                                break;
                        }

                case 3:
                        {
                                if(IsEmpty(head))
                                {
                                        printf("链表为空,请初始化链表!");
                                        break;
                                }
                                else
                                {
                                        printf("输入要删除节点的位置? ");
                                        scanf("%d", &i);
                                        while(1)
                                        {
                                                if(i<1 || i>ListLength(head))
                                                {
                                                        printf("删除的位置非法, 是重新输入还是放弃当前操作?(Y/N)\n");
                                                        //getchar();
                                                        fflush(stdin);//清除缓冲区
                                                        if('n'==getchar())
                                                        {
                                                                putchar('\n');
                                                                goto SELECT;
                                                        }
                                                        else
                                                        {
                                                                printf("输入需要删除结点的位置? ");
                                                                scanf("%d", &i);
                                                        }
                                                }
                                                else
                                                {
                                                        break;
                                                }
                                        }
                                        DeleteList(head, i, &value);
                                        printf("删除的结点元素是%d, 删除第%d个结点后:\n\n", value, i);
                                        ListTraverse(head);
                                        break;
                                }
                        }

                case 4:
                        {
                                printf("输入要查找的值: ");
                                scanf("%d", &value);
                                while(1)
                                {
                                        if(LocateNode(head, value))
                                        {
                                                printf("元素%d所在的位置: %d\n\n", value, LocateNode(head, value));
                                                break;
                                        }
                                        else
                                        {
                                                printf("要查找的值不存在, 是重新输入还是放弃当前操作?(Y/N)\n");
                                                getchar();
                                                if('n'==getchar())
                                                {
                                                        putchar('\n');
                                                        goto SELECT;
                                                }
                                                else
                                                {
                                                        printf("输入要查找的值: ");
                                                        scanf("%d", &value);
                                                }
                                        }
                                }
                                break;
                        }

                case 5:
                        {
                                if(IsEmpty(head))
                                {
                                        printf("链表为空,请初始化链表!");
                                        break;
                                }
                                else
                                {
                                        ListTraverse(head);
                                }
                                break;
                        }
                default:
                        {
                                printf("您的输入有误, 请重新输入选择菜单!\n\n");
                        }
                }
SELECT: printf("请选择您的操作: ");
                scanf("%d", &n);
                putchar('\n');
        }

}

struct Node * CreateList()
{
        int n=1, value;
        struct Node * head=NULL;
        struct Node * p, *q;
        printf("输入结点的值, 输入0完成初始化\n");
        scanf("%d", &value);
        while(!value)
        {
                printf("至少需要输入一个元素, 重新输入还是放弃当前操作? (Y/N)\n");
                fflush(stdin);
                if('N'==toupper(getchar()))
                {
                        putchar('\n');
                        return head;
                }
                else
                {
                        printf("输入结点的值, 输入0完成初始化\n");
                        scanf("%d", &value);
                }
        }
        head = (struct Node *)malloc(sizeof(struct Node));
        p = head;
        while(value)
        {
                q = (struct Node *)malloc(sizeof(struct Node));
                q->data = value;
                p->next = q;
                p= q;
                scanf("%d", &value);
        }
        p->next = NULL;
        return head;
}

void InsertList(struct Node *head, int i, int value)
{
        struct Node *p=head,*q;
        int j = 0;
        while(p->next && ++j<i)
        {
                p=p->next;
        }

        q = (struct Node *)malloc(sizeof(struct Node));
        q->data = value;
        q->next = p->next;
        p->next = q;
}

void DeleteList(struct Node *head, int i, int *e)
{
        struct Node *p = head, *q;
        int j=0;
        while(p->next && ++j<i)
        {
                p = p->next;
        }
        q = p->next;
        *e = q->data;
        p->next = q->next;
        free(q);
}

int LocateNode(struct Node *head, int value)
{
        struct Node *p = head;
        int i = 0;
        while(p->next && p->data!=value)
        {
                p = p->next;
                i++;
        }
        if(value == p->data)
        {
                return i;
        }
        else
        {
                printf("没有该结点!\n");
                return 0;
        }
}

void ListTraverse(struct Node *head)
{
        struct Node *p = head;
        p = p->next;
        printf("**********链表中的元素**********\n");
        while(p)
        {
                printf("%5d", p->data);
                p = p->next;
        }
        printf("\n\n");
}

int IsEmpty(struct Node *head)
{
        if(NULL == head)
                return 1;
        else
                return 0;
}

int ListLength(struct Node *head)
{
        struct Node *p = head;
        int i=0;
        while(p->next)
        {
                p = p->next;
                i++;
        }
        return i;
}

vanentu 发表于 2015-5-26 01:31:11

鼓励一下楼主
页: [1]
查看完整版本: 链表集合上的各种操作