Question

长度N的单链表接在长度M的单链表后的算法时间复杂度是多少 ，要有解释~

Answer 1

#include<iostream>
#include <malloc.h>
#define FALSE 0
#define TRUE 1
#define OK 1
#define ERROR 0
#define MaxSize 10
using namespace std;
typedef char ElemType;
typedef struct Node
{
ElemType data;
Node *next;
}Node, *LinkList;
int InitList_L(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node));
if(!L)
exit (FALSE);
(*L)->next=NULL;
return TRUE;
}
void qcreate(LinkList L)
{
Node *s;
char c;
int flag=1;
while(flag) /* flag初值为1，当输入"#"时，置flag为0，建表结束*/
{
c=getchar();
if(c!='#')
{
s=(Node*)malloc(sizeof(Node)); /*建立新结点s*/
s->data=c;
s->next=L->next;/*将s结点插入表头*/
L->next=s;
}
else
flag=0;
}
}
//计算链表长度
void length(LinkList L)
{
Node *p;
p=L->next;
int j=0;
while(p!=NULL)
{
p=p->next;
j++;
}
printf("%d",j);
printf("\n");
}
//输出链表
void printf(LinkList L)
{
LinkList p;
p=L;
while(p->next!=NULL)
{
p=p->next;
printf("%c",p->data);
}
printf("\n");
}
//对链表排序
void paixu(LinkList L)
{
Node *r,*q,*small;
char temp;
for(r=L->next;r->next!=NULL;r=r->next)
{
small=r;
for(q=r->next;q;q=q->next) /*找到链表中最小字符*/
if(q->data<small->data)
small=q;
if(small!=r)
{
temp=r->data;
r->data=small->data; /*把最小的数值换到P指针所指的位置数值上（原P指针的next指向不变）*/
small->data=temp; /*把原先p指针所指位置的数值填入被置换出的最小字符位置*/
}
}
printf(L);
}
// 查找第i个结点
void Get(LinkList L, int i)
/*在带头结点的单链表L中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置; 否则返回NULL*/
{
int j;
Node *p;
p=L;
j=0; /*从头结点开始扫描*/
while ((p->next!=NULL)&&(j<i))
{
p=p->next; /* 扫描下一结点*/
j++; /* 已扫描结点计数器 */
}
if(i == j)
printf("%c",p->data); /* 找到了第i个结点 */
else
printf("NULL"); /* 找不到，i≤0或i>n */
printf("\n");
}
//在单链表中找到与x相同的数值
void Getchar(LinkList &L)
{
char n;
cout<<"输入这个元素:";
cin>>n;
LinkList p;
p=L;
while(p->data!=n)
{
if(p->next==NULL)
printf("FALSE");
p=p->next;
}
printf("TRUE");
}
// 插入结点
void cins(LinkList L,int i,ElemType x)
/*在带头结点的单链表L中第i个位置插入值为e的新结点s*/
{
Node *pre,*s;
int k;
pre=L;
k=0; /*从"头"开始，查找第i-1个结点*/
while(pre!=NULL&&k<i-1) /*表未查完且未查到第i-1个时重复，找到pre指向第i-1个*/
{
pre=pre->next;
k=k+1;
} /*查找第i-1结点*/
if(!pre) /*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/
{
printf("插入位置不合理!");
}
s=(Node*)malloc(sizeof(Node)); /*申请一个新的结点S */
s->data=x; /*值e置入s的数据域*/
s->next=pre->next; /*修改指针，完成插入操作*/
pre->next=s;
printf("插入成功!链表为：");
}
//删除结点
void del(LinkList L,int i)
/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量e中*/
{
Node *pre,*r;
int k;
pre=L;
k=0;
while(pre->next!=NULL && k<i-1) /*寻找被删除结点i的前驱结点i-1使p指向它*/
{
pre=pre->next;
k=k+1;
} /*查找第i-1个结点*/
if(!(pre->next)) /* 即while循环是因为p->next=NULL或i<1而跳出的,而是因为没有找到合法的前驱位置，说明删除位置i不合法。*/
{
printf("删除结点的位置i不合理!");
}
r=pre->next;
pre->next=pre->next->next; /*修改指针，删除结点r*/
free(r); /*释放被删除的结点所占的内存空间*/
printf("成功删除结点!链表为:");
}
void main()
{
LinkList L;
InitList_L(&L);
int e,i;
char x;
int flag=1;
printf("初始化单链表: (请输入10个以内的字符,以'#'结尾,之间无须空格)\n");
qcreate(L);
printf(L);
while(flag)
{
printf("请选择操作:");
printf("\n");
printf("1.插入结点");
printf("\n");
printf("2.删除结点");
printf("\n");
printf("3.查找第i个元素");
printf("\n");
printf("4.求链表长度 ");
printf("\n");
printf("5.是否能在单链表中找到与x相同的数值");
printf("\n");
printf("6.输出链表");
printf("\n");
printf("7.排序");
printf("\n");
printf("8.退出");
cin>>e;
switch(e){
case 1:printf("请输入要插入的元素值:");
cin>>x;
printf("请输入要在第几个结点处");
cin>>i;
cins(L,i,x);
printf(L);
break;
case 2: printf("请输入你要删除第几个结点: ");
cin>>i;
del(L,i);
printf(L);
break;
case 3:printf("请输入位置i: ");
cin>>i;
printf("数值为:");
Get(L,i);
break;
case 4:printf("链表长度为:");
length(L);
break;
case 5:Getchar(L);
break;
case 6:printf(L);
break;
case 7:paixu(L);
case 8:flag=0;
break;
}
}
}
请参考