Question

数据结构 线性表

链表操作
利用链表的插入运算建立线性链表，然后利用链表的查找、删除、排序计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、排序、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。

Answer 1

我给出插入，查找，删除等基本算法，你自己再写一下吧。。
（1）我介绍两种建表方法：
1.头插法建表：
算法：void CreateFromHead(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;
}
}
2.尾插法：
算法：void CreateFromTail(LinkList L)
{
Node *r, *s;
char c;
int flag =1; /*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/
r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
while(flag) /*循环输入表中元素值，将建立新结点s插入表尾*/
{
c=getchar();
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/
}
}
}
（2）我再讲一下初始化链表：
算法：void init_linklist(LinkList *l)/*对单链表进行初始化*/
{
*l=(LinkList)malloc(sizeof(Node)); /*申请结点空间*/
(*l)->next=NULL; /*置为空表*/
}
（3）我接着讲查找：
1.按序号查找：（给出在单链表L中查找第i个结点的算法）
Node * 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)
return p; /* 找到了第i个结点 */
else
return NULL; /* 找不到，i≤0或i>n */
}
2.按值查找：给出在单链表L中查找值为key的结点的算法
Node *Locate( LinkList L,ElemType key)
/*在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/
{
Node *p;
p=L->next; /*从表中第一个结点开始 */
while (p!=NULL)
{
if (p->data!=key)
p=p->next;
else
break; /*找到结点值=key时退出循环 */
}
return p;
}
这两个算法的平均时间复杂度均为O（n）。
（4）我来讲插入操作：
算法如下：int InsList(LinkList L,int i,ElemType e)
/*在带头结点的单链表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("插入位置不合理!");
return ERROR;
}
s=(Node*)malloc(sizeof(Node)); /*申请一个新的结点S */
s->data=e; /*值e置入s的数据域*/
s->next=pre->next; /*修改指针，完成插入操作*/
pre->next=s;
return OK;
}
（5）我接着讲删除操作：
算法：int DelList(LinkList L,int i,ElemType *e)
/*在带头结点的单链表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不合理!");
return ERROR;
}
r=pre->next;
pre->next=pre->next->next; /*修改指针，删除结点r*/
*e = r->data;
free(r); /*释放被删除的结点所占的内存空间*/
printf("成功删除结点!");
return OK;
}
（6）我讲一下合并两个有序的单链表：
算法：LinkList MergeLinkList(LinkList LA, LinkList LB)
/*将递增有序的单链表LA和LB合并成一个递增有序的单链表LC*/
{
Node *pa,*pb;
Node *r;
LinkList LC;
/*将LC初始置空表。pa和pb分别指向两个单链表LA和LB中的第一个结点,r初值为LC*/
pa=LA->next;
pb=LB->next;
LC=LA;
LC->next=NULL;
r=LC;
/*当两个表中均未处理完时，比较选择将较小值结点插入到新表LC中。*/
while(pa!=NULL && pb!=NULL)
{
if(pa->data <= pb->data)
{
r->next=pa;
r=pa;
pa=pa->next;
}
else
{
r->next=pb;
r=pb;
pb=pb->next;
}
}
if(pa) /*若表LA未完，将表LA中后续元素链到新表LC表尾*/
r->next=pa;
else /*否则将表LB中后续元素链到新表LC表尾*/
r->next=pb;
free(LB);
return(LC);
}
（7）我最后讲一下求单链表的长度：
算法：int ListLength(LinkList L)
/*求带头结点的单链表L的长度*/
{
Node *p;
int j;
p=L->next;
j=0; /*用来存放单链表的长度*/
while(p!=NULL)
{
p=p->next;
j++;
}
return j; /*j为求得的单链表长度*/
}
关于单链表的所有操作我都写上算法了，要实现什么样的操作都可以参考以上算法了，只要选取以上合适的算法进行组合就可以实现你的要求了。。。。

Answer 2

插入
#include<malloc.h>
#include<iostream.h>
#include<conio.h>

#define LIST_INIT_SIZE 100 //线性表初始分配量
#define LIST_INIT_LENGTH 10 //线性表初始长度
#define LISTINCREMENT 10 //分配量
#define OK 1
#define ERROR 0

typedef struct sqlist
{
int *elem; //存储空间的基地址
int length; //当前长度
int listsize; //当前分配的存储容量
} sqlist;

int listlnsert_sq (sqlist&L,int i,int e)
{
if(i<1 || i>L.length+1)
{
cout<<"initial failure!"<<endl;
getch();
return (ERROR);
}
if(L.length>=L.listsize)
{
int *newbase;
newbase=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
//指针名=（数据类型*）realloc（要改变内存大小的指针名，新的大小）。//新的大小一定要大于原来的大小不然的话会导致数据丢失！
if(!newbase)
{
cout<<"overflow!"<<endl;
getch();
return (ERROR);
}
L.elem=newbase;
L.listsize=L.listsize+LISTINCREMENT;
}
int *p, *q;
q=&(L.elem[i-1]); //要插入地址
for(p=&(L.elem[L.length-1]);p>=q;--p)
*(p+1)=*p; //元素的指针加一，表示后移动一位
*q=e;
++L.length;
return (OK);
}

void main()
{
int i,e,j;
sqlist list;
list.length=LIST_INIT_LENGTH;
list.listsize=LIST_INIT_SIZE;
int array[11]={5,8,12,18,25,30,37,46,51,89};
list.elem=array;
cout<<endl<<endl<<"listlnsert_sq.cpp";
cout<<endl<<"==============";
cout<<endl<<endl<<"the old sqlist is:" ;
for(j=0;j<10;j++)
cout<<array[j]<<" ";
cout<<endl<<endl<<"please input the location to insert (1 to 11):";
cin>>i; //要插入的位置
while(i<1 || i>11)
{
cout<<endl<<"please input the location to insert (1 to 11):";
cin>>i;
}
cout<<"please input the integer to insert (eg,58):";
cin>>e; //要插入的数
if(listlnsert_sq(list,i,e))
{
cout<<endl<<"the new sqlist is:";
for(j=0;j<=10;j++)
cout<<array[j]<<" ";
}
cout<<endl<<endl<<".....OK!......";
getch();
}
删除
#include<stdlib.h>
#include<iostream.h>
#include<conio.h>

#define elemtype int
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef struct
{
int *elem;
int length;
int listsize;
} sqlist;

int initlist_sq(sqlist&L)
{
L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L.elem)
return 0;
L.length=0;
L.listsize=LIST_INIT_SIZE;
return 1;
}

void listdelete_sq(sqlist&L,int i,int &e)
{
int *q,*p;
if((i<1)||(i>L.length))
{
cout<<i<<" is overflow!"<<endl;
exit (0); //正常退出程序
}
p=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1;
for(++p;p<=q;++p)
*(p-1)=*p;
--L.length;
cout<<"success to delete sq_list!"<<endl;
}

void main()
{
sqlist L;
int e;
int i,j;
cout<<"listdelete_sq.cpp"<<endl<<"=================="<<endl<<endl;
initlist_sq(L);
cout<<"please input the length of demo sqlist L:<eg.5>";
cin>>L.length;
cout<<"please input the data of demo sqlist L:<eg.[34,54,30,2,40,.......]>"<<endl;
for(j=0;j<L.length;j++)
cin>>L.elem[j];
cout<<endl;
cout<<"success to creat a sqlist:"<<endl;
cout<<"please input the no.i element of sq_list to delete :<eg. 3>";
cin>>i;
listdelete_sq (L,i,e);
cout<<"the sqlist after delete is :";
for(j=0;j<L.length;j++)
cout<<L.elem[j]<<" ";
cout<<endl<<"...OK..."<<endl;
getch();
}
查找
#include<stdlib.h>
#include<malloc.h>
#include<iostream.h>
#include<conio.h>

#define LIST_INIT_SIZE 100 //初始分配的存储空间
#define LIST_INIT_LENGTH 10 //初始长度
#define LISTINCREMENT 10 //分配量
#define OK 1
#define ERROR 0

typedef struct sqlist
{
int *elem;
int length;
int listsize;
}sqlist;

int locateelem_sq(sqlist L,int e)
{
int i=1;
int *p=L.elem;
while(i<=L.length && *p++!=e)
++i;
if(i<=L.length)
return i;
else
return ERROR;
}

void main()
{
int i,e,j;
sqlist list;
int array[10]={5,8,12,18,25,30,37,46,51,89};
list.length=LIST_INIT_LENGTH;
list.listsize=LIST_INIT_SIZE;
list.elem=array;
cout<<endl<<endl<<"locateelem_sq.cpp";
cout<<endl<<endl<<"the old sqlist is:";
for(j=0;j<10;j++)
cout<<array[j]<<" ";
cout<<endl<<endl<<"please input the element to find:";
cin>>e;
j=locateelem_sq(list,e);
if(j)
cout<<endl<<e<<"is found!"<<endl<<"its locate is"<<j<<"!";
else
cout<<e<<"is not found!";
cout<<endl<<endl<<"....OK....";
getch();
}

Answer 3

很简单，晚上帮你写！

追问

啊啊 先谢谢你了 能快点么

追答

太长，贴不上，把你邮箱给我，发给你！

追问

hugao074@163.com 如上 我的邮箱

追答

发你了，有问题再提！