1.//---单链表的存储结构----
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
/*
LinkList与 LNode * 同为结构体指针类型，这两种定义本质上是等价的。
为了提高程序的可读性，通常习惯上用LinkList定义头指针变量，强调定义的是某个链表的头指针；
用LNode * 定义指向单链表中的任意结点的指针变量。例如，使用定义 LinkList L 则 L 为单链表的
头指针；使用定义 LNode *p 则 p 为指向单链表中任意结点的指针，用 *p表示该结点。
*/
2.//--单链表的初始化--
Status InitList(LinkList &L){
//构造一个空的单链表
L=new LNode;
L->nex=NULL;//头结点的指针域置空
return OK;
}
3.//--按序号查询-- Status GetElem(LinkList L,int i,ElemType &e){ //在单链表L中查找第i个元素 struct LNode *p; p=L->next; int j=0; while(p&&j<i){//顺链域向后扫描，知道p指向第i个元素或p为空 p=p->next; ++j; } if(!p||j>i){//第i个元素不存在 return ERROR; } e=p->data; return OK; }
4.//--按值查找--
LNode *LocationElem(Link:ist L,ElemType e){
//在单链表L中查找值为e的元素
struct LNode *p;
p=L->next;
while(p&&p->data!=e){
p=p->next;
}
return p;
}
5.//--单链表的插入--
Status ListInsert(LinkList &L,ElemType &e){
//在单链表的第i个位置插入元素e
struct LNode *p;
int j=0;
p=L;
while(p&&j<i-1){//寻找第i-1个结点
p=p->next;
++j;
}
if(!p||j>i-1){//i大于表长+1或小于1
return ERROR;
}
struct LNode *s;
s=new LNode;//生成新结点s
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
6.//--单链表的删除-- Status ListDeletee(LinkList L,ElemType e){ //在带头结点的单链表中删除第i个元素，并用e返回其值 struct LNode *p; p=L; int j=0; while(p->next&&j<i-1){//寻找第i-1个结点 p=p->next; ++j; } if(!(p->next)||j>i-1){//i大于表长+1或小于1 return ERROR; } struct LNode *q; q=p->next;//用p临时保存要删除的结点 p->next=q->next; e=q->data; delete q; return OK; }
7.//--头插法创建单链表--
void CreateList_F(LinkList &L,int n){
//逆位序输入n个元素，建立带头结点的单链表L
L=new LNode;
L->next=NULL;
for(int i=0;i<n;i++){
struct LNode *p;
p=new LNode;//生成新结点
cin>>p->data;//输入元素值
p->next=L->next;//插入到表头
L->next=p;
}
}
8.//--尾插法创建单链表--
void CreateList_L(LinkList &L,int n){
//正序输入n个元素的值，创建单链表L
L=new LNode;
L->next=NULL;
struct LNode *r;
r=L;
for(int i=0;i<n;i++){
struct LNode *p;
p=new LNode;//生成新结点
cin>>p->data;
p->next=NULL;//插入到表尾
r->next=p;
r=p;
}
}
具体实现：
#include<stdio.h> #include<iostream> using namespace std; #define MAX 100 //定义单链表的存储结构 typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; //初始化单链表 int InitList(LinkList &L){ //构造一个空的链表 L=new LNode; L->next=NULL;//头结点置空 return 1; } //判断链表是否为空 int ListEmpty(LinkList L){ if(L->next){ return 0;//非空 }else{ return 1;//链表为空 } } //获取链表长度 int ListLength(LinkList L){ struct LNode *p; int length=0; p=L->next; while(p){ p=p->next; length++; } return length; } //遍历链表 void TraveList(LinkList L){ struct LNode *p; p=L->next; printf("链表结构如下:\n"); while(p){ printf("%d ",p->data); p=p->next; } printf("\n"); } //头插法创建一个链表 void CreateList1(LinkList &L,int n){ //创建及一个链表，长度n L=new LNode;//建立一个带头结点的单链表 L->next=NULL; printf("请输入链表元素的值:\n"); for(int i=0;i<n;i++){ struct LNode *p; p=new LNode;//生成新结点 printf("请输入第%d个元素的值:",i+1); scanf("%d",&p->data); p->next=L->next; L->next=p; } } //尾插法创建链表 void CreateList2(LinkList &L,int n){ L=new LNode; L->next=NULL; printf("请输入链表元素的值:\n"); struct LNode *r; r=L;//r指向新的尾结点 for(int i=0;i<n;i++){ struct LNode *p; p=new LNode; printf("请输入第%d个元素的值:",&p->data); p->next=NULL; r->next=p; r=p; } } //插入操作 int ListInsert(LinkList &L,int &e){ //在L中的第i个位置前插入结点,其值为e int j=0; struct LNode *p; p=L; while(p&&j<i-1){//找到第i-1个元素 //++j; p=p->next; ++j; } if(j>i-1||!p){ return 0; } struct LNode *s;//新生成一个结点s s=new LNode; s->data=e; s->next=p->next; p->next=s; return 1; } //删除操作 int ListDelete(LinkList &L,int e){ //删除L中的第i个元素,并用e返回其值 int j=0; struct LNode *p; p=L; while(p->next&&j<i-1){ p=p->next; ++j; } if(!(p->next)||j>i-1){ return 0; } struct LNode *q; q=p->next; p->next=q->next; e=q->data; delete q; return 1; } //查询 //按序号查询 int SelectByNo(LinkList L,int &e){ //在L中查询第i个元素，用e返回其值 int j=0; struct LNode *p; p=L; while(p&&j<i){ p=p->next; ++j; } if(!p||j>i){ return 0; } e=p->data; return 1; } //按值查询 int SelectByValue(LinkList L,int e,int &loca){ //在L中查找值为e的元素 struct LNode *p; p=L->next; int j=0; int flag=0; // while(p&&p->data!=e){ // p=p->next; // ++j; // } //return p; while(p&&flag==0){ if(p->data==e){ flag=1; }else{ p=p->next; ++j; } } loca=j; return loca; } int main(){ LinkList L; 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("0.退出\n"); int choose=-1; while(choose!=0){ printf("请选择操作:\n"); scanf("%d",&choose); switch(choose){ case 1: if(InitList(L)){ printf("链表初始化成功!\n"); }else{ printf("链表初始化失败!\n"); } break; case 2: printf("1.头插法创建单链表\n"); printf("2.尾插法创建单链表\n"); printf("请选择操作:\n"); int choose1; scanf("%d",&choose1); switch(choose1){ case 1: int n; printf("请输入链表元素的个数:\n"); scanf("%d",&n); CreateList1(L,n); TraveList(L); break; case 2: int n1; printf("请输入链表元素的个数:\n"); scanf("%d",&n1); CreateList2(L,n1); TraveList(L); break; } break; case 3: if(ListEmpty(L)){ printf("当前链表为空!\n"); }else{ printf("当前链表非空.\n"); } break; case 4:{ int len=ListLength(L); printf("当前链表长度是:%d\n",len); break; } case 5: TraveList(L); break; case 6:{ printf("请输入插入元素的位置和值:\n"); int location,e; scanf("%d%d",&location,&e); if(ListInsert(L,location,e)){ printf("插入成功!\n"); //TraveList(L); }else{ printf("插入失败!\n"); } // ListInsert(L,e); // printf("插入后的链表：\n"); // TraveList(L); break; } case 7:{ printf("请输入要删除元素的位置:\n"); int e,location; scanf("%d",&location); if(ListDelete(L,e)){ printf("删除成功!\n"); //printf("要删除的元素值是:%d\n",e); TraveList(L); }else{ printf("删除失败!\n"); } break; } case 8: //查询 printf("1.按序号查询\n"); printf("2.按值查询\n"); printf("请选择操作:\n"); int choose2; scanf("%d",&choose2); switch(choose2){ case 1:{ printf("请输入待查找元素在链表中的位置:\n"); int e,location; scanf("%d",&location); SelectByNo(L,e); printf("要查找的元素的值是:%d\n",e); break; } case 2:{ printf("请输入要查找元素的值:\n"); int e,location; scanf("%d",&e); SelectByValue(L,e,location); printf("要查找的元素是链表的第%d个元素\n",location+1); break; } } break; case 0: printf("退出成功!\n"); break; } } return 0; }
