线性表之链表实作一
//线性表的一个例子
#include<iostream>
using namespace std;
typedef struct List
{
int num;
struct List *next;//指向下一个元素
}list,*listp;//前者代表该种数据类型,后者代表该种数据类型的指针
void InitList(listp &first)
{
first=new list;
first->num=0;
first->next=NULL; //NULL 在此处不需要再次定义
}
//删除整个链表
void DestroyList(listp &first)
{
listp p;
while(first->next)
{
p=first;
first=first->next;
delete p;
}
delete first;
cout<<"The list have been destroyed !"<<endl;
}
//清空整个链表
void ClearList(listp &first)
{
listp p;
while(first->next)
{
p=first->next;
first->next=p->next;
delete p;
}
cout<<"The list have been cleared !"<<endl;
}
//判断链表是否为空,如果是空,返回true;否则返回false
bool ListEmpty(listp first)
{
if(first->next!=NULL)return false;
else return true;
}
//返回链表的长度
int ListLength(listp first)
{
listp p=first;
int len=0;
while(p->next!=NULL)
{
++len;
p=p->next;
}
return len;
}
//获取链表中第 i 个元素
int GetElem(listp first,int i)
{
int len=1;
listp p=first->next;
while(len<i)
{
++len;
p=p->next;
}
return p->num;
}
//获取元素 i 在链表中的位置
int LocateElem(listp first,int i)
{
int locate=1;
listp p=first->next;
while(p->num!=i)
{
++locate;
p=p->next;
}
return locate;
}
//获取元素 i 在链表中的 直接前驱
int PriorElem(listp first,int i)
{
listp p=first;
while(p->next->num!=i)
{
p=p->next;
}
return p->num;
}
//获取元素 i 在链表中的直接后继
int NextElem(listp first,int i)
{
listp p=first->next;
while(p->next!=NULL && p->num!=i)
{
p=p->next;
}
if(p->next==NULL)return 1;
else return p->next->num;
}
//在链表中用 前插法 插入元素
void ListInsert(listp first,int i)
{
listp p=new list;
p->next=first->next;
first->next=p;
p->num=i;
}
int main()
{
int elem=3;
listp first,p;
InitList(first); //初始化
for(int i=0;i<9;++i) //插入元素
ListInsert(first,i);
p=first;
while(p->next!=NULL)
{
cout<<p->next->num<<" ";
p=p->next;
}
cout<<"Length= "<<ListLength(first)<<endl;
cout<<elem<<" locate "<<LocateElem(first,elem)<<endl;
cout<<elem<<" preelem "<<PriorElem(first,elem)<<endl;
cout<<elem<<" nextelem "<<NextElem(first,elem)<<endl;
cout<<"IsEmpty "<<ListEmpty(first)<<endl;
cout<<"The "<<elem<<" num is "<<GetElem(first,elem)<<endl;
ClearList(first);
cout<<"IsEmpty "<<ListEmpty(first)<<endl;
DestroyList(first);
system("pause");
return 0;
}
值得说明的几个注意点:关于 指针 和 指针地址。众所周知,指针中存储的是一个地址,使用指针可以改变该地址中变量的值;然而,如果要想改变指针呢,是不是就要用指针的指针呢?显而易见,是的。使用指针的指针获得指针的地址,今儿改变指针的内容。
例如:int test=10;int *p=&test;则可以使用*p=100将test的值改为100;
补充:综合编程 , 其他综合 ,