【数据结构】-线性表-顺序表-1325:链表的基本操作【好题】
问题 A: 算法2-8~2-11:链表的基本操作题目描述链表是数据结构中一种最基本的数据结构,它是用链式存储结构实现的线性表。它较顺序表而言在插入和删除时不必移动其后的元素。现在给你一些整数,然后会频繁地插入和删除其中的某些元素,会在其中某些时候让你查找某个元素或者输出当前链表中所有的元素。 输入输入数据只有一组,第一行有n+1个整数,第一个整数是这行余下的整数数目n,后面是n个整数。这一行整数是用来初始化列表的,并且输入的顺序与列表中的顺序相反,也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。 输出如果获取成功,则输出该元素;如果删除成功则输出“delete OK”;如果获取失败或者删除失败,则输出“get fail”以及“delete fail”。如果插入成功则输出“insert OK”,否则输出“insert fail”。如果是“show”则输出列表中的所有元素,如果列表是空的,则输出“Link list is empty”。注:所有的双引号均不输出。 样例输入3 3 2 1 样例输出1 2 3 提示:1、因为输入数据中含有大量的插入和删除操作(不管你信不信,反正我信了),所以必须使用链表,否则很可能会超时。这也是考查链表的特性吧。 2、初始化链表的元素是倒序的,这个使用题目中创建列表的方法(从头部插入)就可以了。 总结:这题考查的是链表的特性。顺序表中,怎样判断何时使用顺序表何时使用链表呢?就要看它们的特点了。顺序表的特点是随机存取、随机访问,也就是说如果存取和查询比较频繁的话使用顺序表比较合适;链表的特点是插入和删除时不必移动其后的节点,如果插入和删除操作比较频繁的话使用链表比较合适。 这个结果没问题 但是超时了 分析了一下,求长度的时候多遍历了一次,浪费了时间,明天优化下#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode;
typedef struct
{
char mark[10];
}Mark;
void InitList(LNode *&L,ElemType number)//初始化
{
//1.申请新节点
//2.插入到头结点
LNode *s;///新节点
int i;
///申请新节点空间并且存入数据
s= (LNode * )malloc(sizeof(LNode));
s->data = number;
///插入到头结点(头插法)
s->next = L->next;
L->next = s;
}
void printList(LNode *L)
{
L=L->next;
while(L!=NULL)///不是写成L->next为NULL
{
printf("%d ",L->data);
L=L->next;
}
printf("n");
}
void deletelist(LNode *&L,int i)///删除
{
//1.找前驱节点
//2.排除不合理的位置
//3.删除 0.1
LNode *qlen,*q,*qfree;
qlen=L;
q=L;
int length=0;
while(qlen->next!=NULL)//求出L长度
{
qlen=qlen->next;
++length;
}
//printf("当前L长度为%dn",length);
if(i<=0||i>length)
{
printf("delete failn");
return ;
}
else
{
//q是要删除部分的前驱节点
int j=1;
while(q->next!=NULL)
{
if(j==i)
{
qfree = q->next;
q->next = q->next->next;
free(qfree);
printf("delete OKn");
return ;///少了这一步,会崩溃....
}
++j;
q=q->next;
}
return ;
}
}
int GetElem(LNode *L,int number)
{
LNode *qlen,*q;
qlen=L;
q=L;
int length=0;
while(qlen->next!=NULL)
{
qlen=qlen->next;
++length;
}
if(number<=0||number>length)
{
return -1;
}
int j=0;///这里又是j=0不是j=1
while(q->next!=NULL)
{
q=q->next;
++j;
if(j==number)
{
return q->data;
}
}
}
int insertlist (LNode *&L,int i,int number)
{
LNode *q,*qlen,*s;
int length=0;
q=L;
qlen=L;
while(qlen->next!=NULL)
{
qlen=qlen->next;
++length;
}
if(i<=0||i>length+1)
{
return -1;
}
int j=0;
while(q!=NULL)
{
++j;
if(j==i)
{
s=(LNode *)malloc(sizeof(LNode));
s->data=number;
s->next=q->next;
q->next=s;
//printList(L);
return 1;
}
q=q->next;
}
}
int main (void)
{
int n;
ElemType number;
LNode *L,*q;///声明链表要带*号
///把L表置为空表
L= (LNode *)malloc(sizeof(LNode));
L->next = NULL;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&number);
InitList(L,number);
}
int linenumber;
scanf("%d",&linenumber);
Mark a;
for(int i=1;i<=linenumber;i++)
{
scanf("%s",a.mark);
if(strcmp(a.mark,"show")==0)
{
if(L->next==NULL)
printf("Link list is emptyn");
else
printList(L);
}
else if(strcmp(a.mark,"delete")==0)
{
int number;
scanf("%d",&number);
deletelist(L,number);
}
else if(strcmp(a.mark,"get")==0)
{
int number;
scanf("%d",&number);
int x = GetElem(L,number);
if(x==-1)
printf("get failn");
else
printf("%dn",x);
}
else if(strcmp(a.mark,"insert")==0)
{
int i,number;
scanf("%d%d",&i,&number);
int x = insertlist(L,i,number);
if(x==1)
printf("insert OKn");
else
printf("insert failn");
}
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |