如何建立一个有序链表

发布网友 发布时间：2022-05-15 18:51

我来回答

共3个回答

热心网友 时间：2024-02-27 00:25

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
typedef int ElemType;
typedef struct LNode {
ElemType date;
struct LNode *next;
}linklist,*link;

/*构造链表*//////////////////////////////////////
void IinitList(link &L)
{
if(L)delete L;
L= (link)malloc(sizeof(LNode)) ;
if (!L) exit(1);
L->next=NULL;
cout<<"链表已经建立\n";
}
//////////////////////////////////////////////////////
// /*删除结点*/// //////////////////////////////////////////////
int listdelete(link &L,int i,ElemType &e)
{
link p,q; int j;
p=L;j=0;
while(p->next&&j<i-1)
{
p=p->next;++j;
}

q=p->next;
p->next=q->next;
e=q->date;free(q);
cout<<"结点已经删除\n";
return 1;
}
////////////////////////////////////////////// /////////
// /*插入结点*/////////////// ///////////////////////
int listinsert(link &L,int i,ElemType e)
{
link p,q;
int j;
p=L;j=0;
while(p&&j<i-1)
{
p=p->next;++j;
}
q= (link)malloc(sizeof(LNode));
q->date=e;
q->next=p->next;
p->next=q; cout<<"结点已经插入\n";
return 1;
}
/////////////////////////////////////////////////////
////*显示数据*///////// ////////////////////////////////
void show(link l)
{ link p; int j;
p=l;j=0;
cout<<"链表的值为：\n";
while(p->next)
{
cout<<p->next->date<<endl;
p=p->next;
}
}
//////////////////////// /////////////////////////////////
//////销毁链表////// ////////////////////////////////////////
void destorylinst(link &L)
{
while(L)
{ link p=L;
L=L->next;

free(p) ;
}
L=NULL;
}

////// 打印表头///////////////////////////////////////
void print()
{
cout<<"------------------------\n";
cout<<"------------------------\n";
}

////查找结点//// ////////////////////////////////////////

void lookfor(link l,int e)
{
if(l==NULL)
cout<<"链表未建立，请先构造链表\n" ;
else{
link p; int i=0,j=0;
p=l->next;
cout<<"你查找值的位置是：\n " ;
while(p)
{ if(p->date==e)
{ j++;
cout<<i+1<<endl;
}
p=p->next; i++;
}cout<<"查找完毕\n";
if(j==0)
cout<<"你查找的值不在链表中 、\n";
} }

void putline(link &l)
{
if(l==NULL ||l->next==NULL )
cout<<"链表未建立或是空的，请先构造链表\n" ;
else{
link p,q;
p=l->next;
while(p!=NULL)
{ q=p->next;
while(q!=NULL)
{
if(p->date>q->date)
{ ElemType t;
t=p->date;
p->date=q->date;
q->date=t; }
q=q->next;
} p=p->next;
} cout<<"链表已经排序 \n";
}
}

//////测试函数///// /////////////////////

void main()
{ link L=NULL; int k;
while(1)
{
cout<<"按0退出\n"<<"按1建立链表\n"<<"按2插入结点\n"<<"按3删除结点\n"
<<"按4清空链表\n"<<"按5查找结点\n"<<"按6进行排序\n" ;
print();
int a,i,j;
cin>>a;
switch(a)
{ case 0: if(L!=NULL)
destorylinst(L) ;
exit(1);

case 1:
IinitList(L);
k=0;
print();show(L) ;
cout<<"空的链表\n";
cout<<"链表长度为: "<<k<<endl;
print();
cout<<"请先给链表输入值，输入 0 再按回车结束\n";
int bb;
cin>>bb;
while(bb!=0)
{ k++;
listinsert(L,k,bb) ;
cin>>bb;
} print();
show(L) ; cout<<"链表长度为: "<<k<<endl;
print();break;

case 2:
if(L!=NULL)
{
cout<<"输入位置:\n";
cin>>i;
while(i>k+1 || i<1)
{
cout<<"位置错误，重新输入插入位置\n" ;
cin>>i;
}
cout<<"输入植；\n";
cin>>j;
listinsert(L,i,j) ;
k++;
print();
show(L);
cout<<"链表长度为:"<<k<<endl;
print();
}else
{ cout<<"链表不存在,请先建链表\n";
print(); }break;

case 3:
if(L!=NULL)
{
cout<<"输入位置:\n";
cin>>i;
while(i>k || i<1)
{
cout<<"位置错误，重新输入删除位置\n" ;
cin>>i;
}
listdelete (L,i,j);
cout<<"你删除的是：\n";
cout<<j<<endl ;
k--; print();
show(L);
cout<<"链表长度为:"<<k<<endl;
print();
}
else {
cout<<"链表不存在,请先建链表\n";
print();
} break;

case 4:
destorylinst(L) ;
cout<<"链表已经清空\n";
print();break;

case 5:
print();
cout<<"输入要查找的值；\n";
int z;
cin>>z;lookfor(L,z);
print();break;

case 6:
putline(L);
if(L!=NULL)show(L);
print();break;

default:
break ;
}
}
delete L;
}

1

热心网友 时间：2024-02-27 00:25

#include
#include
struct Lnode {
int data;
Lnode *next;
};
void InitList(Lnode *&H){//初始化单链表即把单链表置为空
H=NULL;
}
bool ListEmpty(Lnode *&H){//链表的判空
return (H==NULL);
}
void TraverseList(Lnode *&H){//输出单链表
int i=0;
Lnode *L=H;
printf("\n");
while(H!=NULL){
i++;
printf(" %d",H->data );
H=H->next ;
if(i%10==0)
printf("\n");
}
H=L;
printf("\n");
}

void Insert(Lnode *&H, int item){//按顺序插入元素
Lnode *newptr;
newptr=new Lnode;
if(newptr==NULL){
printf("没有得到足够的空间");
exit(1);
}
newptr->data =item;
if (H==NULL||itemdata ){
newptr->next=H;
H=newptr;
return;
}
Lnode *q;
Lnode *p;
q=H;p=H->next ;
while(p!=NULL){
if(item p->data) break;
else{
q=p;
p=p->next;
}
}
newptr->next =p;
q->next=newptr;

}

bool Delete(Lnode *&H,int item){//删除给定值的元素
if(H==NULL){
printf("表空，不可以进行删除操作");
exit(1);
}
Lnode *q=H,*p=H->next ;
if (H->data ==item){
H=H->next ;
delete q;
return true;
}

while(p!=NULL){
if(p->data ==item)break;
q=p;
p=p->next ;
}
if (p==NULL){
printf("没有找到要删除的元素");
return false;
}

q->next =p->next ;
delete p;
return true;
}
void ClearList(Lnode *&H){//清空链表
Lnode *p;
if(H!=NULL){
p=H->next ;
delete H;
H=p;
}
}
void main(){

int m,n;
Lnode *lnode;
InitList(lnode);
printf("随机生成链表并排序后输出：\n");
for(int i=0;i<8;i++)
Insert(lnode,rand()/90+10);
TraverseList(lnode);
printf("\n请输入要在表内插入的元素： ");
scanf("%d",&m);
Insert(lnode,m);
printf("\n链表元素从小到大排序： ");
TraverseList(lnode);
printf("\n请输入要删除的元素： ");
scanf("%d",&m);
Delete(lnode,m);
TraverseList(lnode);
ClearList(lnode);
printf("链表已清空\n");
}

希望对你有帮助！

热心网友 时间：2024-02-27 00:26

下面是C#中的实现代码：