链表集合上的各种操作

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

#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

鼓励一下楼主

账号		自动登录	找回密码
密码			立即注册

[技术交流] 链表集合上的各种操作

马上注册，结交更多好友，享用更多功能^_^