学步园

重点：练习单链表的初始化、查找、插入、删除操作，重点掌握创建链表的前插法和后插法两种方法。
1.单链表的存储结构
//-----单链表的存储结构-----
typedef struct LNode{
ElemType date;//结点的数据域
struct LNode *next;//结点的指针域
}LNode,*LinkList;//LinkList为指向LNode的指针类型

2.单链表基本操作的实现
//-----单链表的初始化-----
Status InitList_L(LinkList &L){//构造一个空的单链表L
L=new LNode;//生成新结点做为头结点
L->next=NULL;//头结点的指针域为空
return OK;
}

//-----按序号查找-----
Status GetElem_L(LinkList L,int i,ElemType &e){//在头结的为L的单链表中查找第i个元素
p=L->next;j=1;
while(p&&j<i){
p=p->next;
++j;
}
if(!p||j>i) return ERROR;//第i个元素不存在
e=p->date;
return OK;
}

//-----按值查找-----
LNode *LocateElem_L(LinkList L, ElemType e){//在带头结点的单链表L中查找值为e的元素
p=L->next;
while(p&&p->date!=e){
p=p->next;
}
return p;
}

//-----单链表的插入-----
Status LinkInsert_L(LinkList &L,int i,ElemType e){//在带头结的单链表L中第i个位置插入元素e
p=L;j=0;
while(p&&j<i-1){
p=p->next;
++j;
}
if(!p||j>i-1) return ERROR;
s=new LNode;
s->date=e;
s->next=p->next;
p->next=s;
return OK;
}

//-----单链表的删除-----
Status LinkDelete_L(LinkList &L,int i,ElemType &e){//删除L的第i个元素，并赋给e
p=L,j=0;
while(p->next&&j<i-1){
p=p->next; ++j;
}
if(!(p->next)||j>i-1; return ERROR;//i大于表长+1或者小于1
q=p->next;
p->next=q->next;
e=q->date;
delete q;
return OK;
}

//-----前插法创建链表-----
void CreatList_F(LinkList &L, int n){//逆位序输入n个元素的值,建立带头结点的单链表L
L=new LNode;
L->next=NULL;
for(i=n; i>0; --i){
p=new LNode;
cin>>p->date;
p->next=L->next; L->next=p;
}
}
//注意：前插法逆序输入n个元素的值，结合图示更易理解前插法。
图示：

//-----后插法创建链表-----
void CreatList_L(LinkList &L,int n){//正位序输入n个元素的值，建立带头结点的单链表L
L=new LNode;
L->next=NULL;
r=L;
for(i=0; i<n; i++){
p=new LNode;
cin>>p->data;
p->next=NULL;r->next=p;
}
}

总结：二者时间复杂度均为O(n),但是后插法较前插法更易理解，但前插法在特定情况也有它的用处，应熟练掌握。

题目描述：
设计一个算法，通过一趟遍历，将链表中所有结点的链接方向逆转且仍利用原表的存储空间。

#include<iostream>
using namespace std;
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, *LinkList;

void CreatList(LinkList L){//创建一个链表 
    LinkList p,q;//p、q为结构体指针类型 
    p=L;//创建头结点L 
    cout<<"输入结点数量"<<endl;
    int n; cin>>n; 
    for(int i=0; i<n; i++){
        q=new LNode;
        cin>>q->data;
        p->next=q;
        p=q;
    }
    p->next=NULL;
    return;
}

void ReverseList(LinkList L){//使用前插法将结点顺序逆转且不改变存储空间
    LinkList p,q;
    p=L->next;
    L->next=NULL;
    while(p!=NULL){
        q=p->next;
        p->next=L->next;
        L->next=p;
        p=q;
    } 
}

void ListTraverse(LinkList L){//遍历链表 
    LinkList p;
    p=L->next;
    while(p!=NULL){
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
    return ;
}

int main(){
    LNode L;
    CreatList(&L); 
    ReverseList(&L); 
    ListTraverse(&L);
    while(1);
}

输出结果：