|
//链表应用1
#include <iostream.h>
#include <malloc.h>
#include <stdio.h>
typedef int elemtype;
//定义结构体
typedef struct node
{
elemtype data; //数据域
struct node *next; //指针域
}linklist,*prtnode;
/*
(1)create linklist
表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配
，而是运行时系统根据需求而生成的，因此建立单链表从空表开始，每读入一个数据元素则申请一
个结点，然后插在链表的尾部。
*/
//算法描述跟随输入
linklist *createlist(int n)
{
int i;
int x;
/*
初始化操作,定义phead(头指针,给他分配空间),定义尾指针ptail,定义跟随指针pfollow;
linklist *phead ,*ptail,*pfollow;
phead = new linklist;
ptail = phead;
pfollow = phead;
ptail->next = NULL; // 一定要加空表
*/
//构建头结点空间
linklist *phead;
phead = new linklist;
//构建尾结点,不断读入数->next=NULL;
linklist *ptail;
ptail = phead;
ptail->next = NULL;//创建空表p->phead==NULL,应用程序不出错
//构造跟随指针
linklist *pfollow;
pfollow = phead;
//循环构建n个结点
for(i = 1; i<=n; i++)
{
cout<<"第"<<i<<"个";
cin>>x;
//不断取得空间,完成一个结点工作ptail
ptail = new linklist; //h,f,t本身地址0x003708a8;next:0x00000000; data:NULL
ptail->data = x; //h,f本身地址0x003708a8;next:0x00000000; data:NULL /t本身0x00370d80 next:0xcdcdcdcd data:NULL
ptail->next = NULL; //h,f本身地址00x003708a8;next:0x00000000; data:NULL /t本身0x00370d80 next:0xcdcdcdcd data:5
//由于起初fh相互关联,告诉他们下个地址就是ptail
pfollow->next = ptail; //h,f本身地址0x003708a8;next:0x00000000; data:NULL /t本身0x00370d80 next:0x00000000 data:5
//一个结点本身地址和next地址,将next地址传给本身,meaning将本身跳到该结点
pfollow = pfollow->next ; //*h,f本身0x003708a8,next:0x00370d80,data:null /t本身0x00370d80 next:0x00000000 data:5
} //h本身0x003708a8,next:0x00370d80,data:null /f,t 本身0x00370d80 next:0x00000000 data:5
return phead;
}
//倒置输入//先读数据,将数据插入
linklist *createlist2(int n)
{
int i;
linklist *p;
linklist *phead;
phead = new linklist;//头结点空间
phead->next=NULL;
for(i=1;i<=n;i++)
{
//初始化新结点
p=new linklist;
cout<<"第"<<i<<"个";
cin>>p->data;
//插入
p->next=phead->next;
phead->next=p;
}
linklist *end;
end=phead;
/// if(end->next==NULL)
// {
//
// phead=phead->next;
// }
// while(end->next!=NULL)
// {
// end=end->next;
// }
// end->next=phead;
return phead;
}
/*
(2)查找<一>
查找元素按值查找：(从头指针开始)
在链表中查找是否有结点等于给定值key的结点
若有则返回首次找到值的存储位置,否则返回null
算法思想:
从开始结点出发,顺链表逐个结点的值和给定key做比较
*/
linklist *locate(const linklist *phead,elemtype &e) //phead是头结点,不是首结点
//or prtnode locate(prtnode phead,elemtype &e)
{
linklist *pindex;
pindex = phead->next; //从头结点获得首结点
while(pindex!=NULL) //while(pindex!=NULL&&pindex->data!=x)
{ //{ pindex = pindex->next; }
if(pindex->data==e)
{
cout<<"找到了";
break;
}
pindex = pindex->next;
}
//跳出循环访问到pindex为
/*
和head没关系
while里不能用做pindex->pnext!=NULL,错误很多:
如因为若为空表,首结点data没有值,pindex->data访问出错
如果第二个结点(不包括头结点),为空,while(pindex->pnext!=null)
为真,没法对首结点进行访问;只能是while(pindex!=NULL)形式
*/
return pindex;
}
/*<二>
查找元素按序号查找(从头指针开始)
设单链表长度为length,要查找第i个结点
算法思想
从头结点开始扫描.用j做已扫描的计数器,当p扫描下一个结点时,j++;
p的初值指向头结点,j=0
当j==i,,指针p所指就是第i个结点
*/
linklist *findi(linklist *phead,elemtype i_base)
{
int j_add;
linklist *pindex;
pindex = phead->next;
j_add = 1;
while(pindex!=NULL)
{ //while(p && j
if(i_base==j_add)
{
//{
break;
} // j++;p = p->next;
pindex = pindex->next; //}
j_add++;
}
return pindex;
}
/*
(3)插入元素<定值后插一>
类似于查找运算，单链表的插入运算也可分两种方式来处理，一种按给定值插入
另一种按给定序号插入，根据给定的问题而定。下面主要讨论按给定值来处理。
*/
linklist *insertlist( linklist *phead,elemtype compare,elemtype insert)
{
linklist *ptem;
linklist *pinsert;
//初始化一个结点,赋值
pinsert = new linklist;
pinsert->data = insert;
pinsert->next = NULL;
ptem = phead->next;
if(NULL==ptem) //空表直接插入
{
phead->next = pinsert;
}
else
{
while( ptem->next!=NULL && ptem->data!=compare ) //条件要注意 ptem && ptem->next 能保证链表有两个元素
ptem=ptem->next; //两种推出情况end退出,找到推出
if(ptem->data==compare) //在此访问会出问题,处理找到推出
{
pinsert->next = ptem->next; //注意交换次序
ptem->next = pinsert;
}
else //处理end推出
{
ptem->next=pinsert;
}
}
return phead;
}
//插入按值<前插二>
linklist *insertlist2(linklist *phead,elemtype compare,elemtype insert)
{
linklist *ptem;
linklist *ptemnext;
//初始化一个结点,赋值
linklist *pinsert;
pinsert = new linklist;
pinsert->data = insert;
pinsert->next = NULL;
ptem=phead->next; //链表为空时做前插
if(NULL==ptem)
{
phead->next = pinsert;
}
else
{
while( ptem && ptem->next) //限制存在两个结点,//ptemnext,和ptem
{
ptemnext=ptem->next;
if(ptem->data==compare) //当compare首次出现在ptem时做前插
{
phead->next=pinsert;
pinsert->next=ptem;
break;
}
if(ptemnext->data==compare) //根据ptemnext比较做前插
{
ptem->next=pinsert;
pinsert->next=ptemnext;
break;
}
ptem=ptem->next; //下一个,指针后移
ptemnext=ptemnext->next;
}
//限制一个结点,做前插
if(ptem->data==compare &&ptem->next==NULL)
{
phead->next=pinsert;
pinsert->next=ptem;
}
else //都没有匹配时做最后一个插入
{
ptem->next=pinsert;
pinsert->next=ptemnext;
}
}
return phead;
}
/*
单链表删除
*/
//按值删除
linklist *dellist(linklist *phead,elemtype delelem)
{
linklist *ptem;
linklist *ptemnext;
ptem=phead->next;
if(ptem==NULL)
{
cout<<"the link is empty\n";
return phead;
}
while(ptem!=NULL && ptem->next!=NULL) //限制两个结点
{
ptemnext=ptem->next;
if(ptemnext->data==delelem)
{
ptem->next=ptemnext->next;
}
ptem=ptem->next;
}
return phead;
}
//按序号删除
linklist *dellist2(linklist *phead,int i)
{
linklist *pfollow;
linklist *ptem;
int j; //j++确定删除的元素次序
pfollow=phead->next;
if(i==1) //限制结点为首结点
{
phead->next=pfollow->next;
//phead=pfollow ;
}
else //其余结点
{
j=1;
while( pfollow!=NULL && j<i-1) //follow保证不超过链表尾地址
{
pfollow = pfollow->next;
j++;
}
ptem=pfollow->next; //删除元素
pfollow->next=ptem->next;
delete ptem; //不要忘记释放指针
}
return phead;
}
//()输出数据
int printlist(const linklist *phead)
{
linklist *ptemp;
ptemp = phead->next;
while(ptemp) //while(ptemp!=NULL) 更安全
{
cout<<ptemp->data<<" ";
ptemp = ptemp->next;
}
cout<<endl;
return 1;
}
linklist *empty(linklist *phead)
{
linklist *ptem;
linklist *ptem_release;
ptem = phead->next;
if(ptem==NULL)
{
return phead;
}
while(ptem)
{
ptem_release=ptem;
ptem=ptem->next;
delete ptem_release;
}
delete ptem;
phead->next=NULL;
return phead;
}
int lengthlist(const linklist *phead)
{
int length=0;
linklist *ptem;
ptem=phead->next;
while(ptem)
{
ptem=ptem->next;
length++;
}
return length;
}
void destorylist(linklist *phead)
{
linklist *ptem;
linklist *ptem_release;
ptem = phead->next;
//删除非头结点,释放内存
while(ptem)
{
ptem_release=ptem;
ptem=ptem->next;
delete ptem_release;
}
//释放头结点
delete phead;
}
/*
linklist *createlist(int n);
linklist *createlist2(int n);
linklist *locate(const linklist *phead,elemtype &e);
linklist *findi(linklist *phead,elemtype i_base);
linklist *insertlist( linklist *phead,elemtype compare,elemtype insert);
linklist *insertlist2(linklist *phead,elemtype compare,elemtype insert);
linklist *dellist(linklist *phead,elemtype delelem);
linklist *dellist2(linklist *phead,int i);
void printlist(const linklist *phead);
linklist *empty(linklist *phead)
int lengthlist(const linklist *phead)
*/
void information()
{
printf(" ----------------------------------------\n");
printf(" | Test 链表应用测 |\n");
printf(" |__ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|\n");
printf(" | 1. 初始化化链表 |\n");
printf(" | 2. 查询数据是否在表中 |\n");
printf(" | 3. 查询表中数据的号码 |\n");
printf(" | 4. 前插数据 |\n");
printf(" | 5. 后插数据 |\n");
printf(" | 6. 删除指定位置数据 |\n");
printf(" | 7. 删除所选数据 |\n");
printf(" | 8. 打印链表数据 |\n");
printf(" | 9. 将已有链表置空 |\n");
printf(" | 10. 返回表中的数据个数 |\n");
printf(" | 0. 退出程序 |\n");
printf(" --------------------------------------- \n");
printf(" \n\n");
printf(" <按99重新打印帮助说明>\n");
}
int mainwhile(void)
{
linklist test;
linklist *head;
int n=0;
int length=0;
int compare;
int insert;
int del;
int finde;
int base;
int i_base;
information();
cout<<"请输入您选择的号码___";
cin>>base;
while(1)
{
switch (base)
{
case 1:
cout<<"请输入数据总数____";
cin>>n;
head=createlist(n);
break;
case 2:
if(n==0)
{
cout<<"请先初始化表";
break;
}
cout<<"请输入要查询的数据__";
cin>>finde;
head=locate(head,finde);
break;
case 3:
if(n==0)
{
cout<<"请先初始化表";
break;
}
cout<<"请输入要查询的序列___";
cin>>i_base;
head=findi(head,i_base);
break;
case 4:
if(n==0)
{
cout<<"请先初始化表";
break;
}
cout<<"请输入要插入的数据__";
cin>>insert;
cout<<"请选定在哪个数据前插入__";
cin>>compare;
head=insertlist2(head, compare, insert);
break;
case 5:
if(n==0)
{
cout<<"请先初始化表";
break;
}
cout<<"请输入要插入的数据__";
cin>>insert;
cout<<"请选定在哪个数据后插入__";
cin>>compare;
head=insertlist(head, compare, insert);
break;
case 6:
if(n==0)
{
cout<<"请先初始化表";
break;
}
cout<<"请输入要删除数据的位置__";
cin>>i_base;
head=dellist2(head, i_base);
break;
case 7:
if(n==0)
{
cout<<"请先初始化表";
break;
}
cout<<"请输入要删除的数据";
cin>>del;
head=dellist2(head,del);
break;
case 8:
if(n==0)
{
cout<<"请先初始化表";
break;
}
cout<<"表的内容为\n";
printlist(head);
break;
case 9:
if(n==0)
{
cout<<"请先初始化表";
break;
}
n=0;
empty(head);
printlist(head);
information();
break;
case 10:
if(n==0)
{
cout<<"请先初始化表";
break;
}
length=lengthlist(head);
cout<<"表中的数据个数为:\n";
cout<<length;
break;
case 99:
cout<<"\n\n\n\n\n";
information();
break;
case 0:
cout<<"感谢使用\n";
return 0;
}
cout<<"\n请输入您选择的号码___";
cin>>base;
}
return 1;
}
void main()
{
mainwhile();
}
|
