实验3-单链表（优化版/王道版）

单链表结构体

typedef int ElemType;
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,* LinkList;

单链表的初始化

void InitList(LinkList &L)
{L=new LNode;L->next=NULL;
}

打印单链表

void visit(LinkList L)
{L=L->next;while(L){cout<<L->data<<" ";L=L->next;}cout<<endl;
}

头插法建表

void HeadInsert(LinkList &L)
{InitList(L);LinkList p=NULL;ElemType e;cin>>e;while(e!=9999){p=new LNode;p->data=e;p->next=L->next;L->next=p;cin>>e;}
}

尾插法建表

void TailInsert(LinkList &L)
{InitList(L);LinkList p;LinkList r=L;ElemType e;cin>>e;while(e!=9999){p=new LNode;p->data=e;r->next=p;r=p;cin>>e;}r->next=NULL;
}

求表长操作

int Length(LinkList L)
{int len=0;L=L->next;while(L){len++;L=L->next;}return len;
}

按位查找结点

LinkList GetElem(LinkList L,int i)
{if(i<0) return NULL;int j=0;while(L && j<i){L=L->next;j++;}return L;
}

按值查找结点

LinkList LocateElem(LinkList L,ElemType e)
{L=L->next;while(L && L->data!=e) L=L->next;return L;
}

插入结点

bool ListInsert(LinkList &L,int i,ElemType e)
{LinkList p=GetElem(L,i-1);if(p==NULL) return false;LinkList s=new LNode;s->data=e;s->next=p->next;p->next=s;return true;
}

删除结点

bool ListDelete(LinkList &L,int i,ElemType &e)
{LinkList p=GetElem(L,i-1);if(p==NULL || p->next==NULL) return false;LinkList s=p->next;e=s->data;p->next=s->next;delete s;return true;
}

main函数

int main()
{LinkList L;ElemType e;HeadInsert(L);//5 4 3 2 1 9999
//	TailInsert(L);//1 2 3 4 5 9999visit(L);cout<<"len:"<<Length(L)<<endl;cout<<"elem:"<<GetElem(L,5)->data<<endl;cout<<"pos:"<<LocateElem(L,5)<<endl;ListInsert(L,6,6);visit(L);ListDelete(L,6,e);visit(L);return 0;
}

完整代码

	#include <iostream>using namespace std;typedef int ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LNode,* LinkList;void InitList(LinkList &L){L=new LNode;L->next=NULL;}void visit(LinkList L){L=L->next;while(L){cout<<L->data<<" ";L=L->next;}cout<<endl;}void HeadInsert(LinkList &L){InitList(L);LinkList p=NULL;ElemType e;cin>>e;while(e!=9999){p=new LNode;p->data=e;p->next=L->next;L->next=p;cin>>e;}}void TailInsert(LinkList &L){InitList(L);LinkList p;LinkList r=L;ElemType e;cin>>e;while(e!=9999){p=new LNode;p->data=e;r->next=p;r=p;cin>>e;}r->next=NULL;}int Length(LinkList L){int len=0;L=L->next;while(L){len++;L=L->next;}return len;}LinkList GetElem(LinkList L,int i){if(i<0) return NULL;int j=0;while(L && j<i){L=L->next;j++;}return L;}LinkList LocateElem(LinkList L,ElemType e){L=L->next;while(L && L->data!=e) L=L->next;return L;}bool ListInsert(LinkList &L,int i,ElemType e){LinkList p=GetElem(L,i-1);if(p==NULL) return false;LinkList s=new LNode;s->data=e;s->next=p->next;p->next=s;return true;}bool ListDelete(LinkList &L,int i,ElemType &e){LinkList p=GetElem(L,i-1);if(p==NULL || p->next==NULL) return false;LinkList s=p->next;e=s->data;p->next=s->next;delete s;return true;}int main(){LinkList L;ElemType e;HeadInsert(L);//5 4 3 2 1 9999//	TailInsert(L);//1 2 3 4 5 9999visit(L);cout<<"len:"<<Length(L)<<endl;cout<<"elem:"<<GetElem(L,5)->data<<endl;cout<<"pos:"<<LocateElem(L,5)<<endl;ListInsert(L,6,6);visit(L);ListDelete(L,6,e);visit(L);return 0;}

输出示例

5 4 3 2 1 9999
1 2 3 4 5
len:5
elem:5
pos:0xc56a20
1 2 3 4 5 6
1 2 3 4 5