数据结构----单链表

数据结构之单链表

• 单链表
  继上一篇线性表之顺序表，这一篇文章接着来讲讲线性表的另一个表现形式：单链表，
  【注】单链表不可以顺序存取！
  以下是部分代码：

#include <stdio.h>
#include <stdlib.h>
#include <iostream>

using namespace std;

//typedef为重命名方法，这里将struct LNode重命名成了LNode 和LinkList
//LNode强调结点，而LinkList强调的是一个单链表，强调的不一样，即内涵不一样
typedef struct LNode{
   
    int data;
    struct LNode *next;
}LNode,*LinkList;  


//初始化(带头结点)----单链表不支持随机存取
bool InitList(LinkList &l){
   
    //malloc返回申请空间的起始地址，即指针
    l=(LNode *)malloc(sizeof(LNode));
    if(l==NULL)
        return false;
    else{
   
        l->next=NULL;//初始化，防止原来该内存中存的乱七八糟的东西妨碍编程
        return true;
    }
}

//判断链表是否为空
bool IsEmpty(LinkList l){
   
    if(l->next==NULL){
   
        return true;
    }
    else{
   
        return false;
    }
}

//1.头插法(初始化后调用)
void  Head_Insert(LinkList &l){
   
    //初始化
    //InitList(l);

    //输入插入的数值
    int e;
    cout << "请输入要插入的节点的值：" <<endl;
    cin >> e;
    //进行头插
    while(e!=00){
   
        //新建一个节点，存放插入的数值
        LNode *Ltemp = (LinkList)malloc(sizeof(LNode));
        //Ltemp->next=NULL;
        Ltemp->data=e;
        Ltemp->next=l->next;
        l->next=Ltemp;
        cin >> e;
    }   
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 
//2.尾插法----开始的想法：遍历到最后一个节点，然后加上插入节点，这样是错误的！
//开始的想法导致链表最后只剩最后的节点了，前面都没了。
//按照王道书上讲的，加一个指针，为表尾指针,须知，该单链表在调用该函数时应是空的，即初始化后调用
//另外，注意r指针(尾指针)永远指向最后一个结点！
//这里，单链表的同步更新使用指针操作！
void Tail_Insert(LinkList &l){
   
    LNode *t=l;
    LNode *n;
    int e;
    cout << "请输入要尾插的数值："<<endl;
    cin >> e;
    while (e!=00)
    {
   
        n = (LNode *)malloc(sizeof(LNode));
        n->data=e;
        t->next=n;
        t=n;//注意这条语句！！！把插入的结点变成尾指针指向的
        cin >> e;
    }
    t->next=NULL; //不要忘记这一句，对尾结点的初始化操作
}
//3.按值查找
LNode * Search_Val(LinkList l,int e){
   
    
    LNode *p=l->next;
    while (p!=NULL && p->data!=e)
    {
   
        p=p->next;
    }
    return p;
  
}
//4.按位查找,从1开始
LNode *Search_Loc(LinkList l,int loc){
   
    LNode *p=l->next;
    int i=1;
    if(loc==0)
        return l;
    if(loc<1){
   
        cout<<"输入的查找位置不存在！"<<endl;
        return NULL;
    }
        
    while (p!=NULL&&i<loc)//注意判断条件是小于，没有等于
    {
   
        i++;
        p=p->next;
    }
    return p;
}
//5.插入节点
void Insert(LinkList &l,int loc,int e){
   
    if(loc<1){
   
        cout<<"输入的查找位置不存在！"<<endl;
        return;
    }
    LNode *p=(LinkList)malloc(sizeof(LNode));
    p->data=e;
    LNode *q;
    q=Search_Loc(l,loc-1);
    p->next=q->next;
    q->next=p;
}
//6.删除节点
void Delete(LinkList &l,int loc){
   
    if(loc<1){
   
        cout<<"输入的查找位置不存在！"<<endl;
        return;
    }
    LNode *p=Search_Loc(l,loc);
    //cout<<p->data<<endl;
    if(IsEmpty(l))
        return;
    LNode *q=p->next;
    p->data=p->next->data;
    p->next=q->next;
    free(q);
}
//7.求表长
int GetLength(LinkList l){
   
    int i=0;
    LNode *p=(LinkList)malloc(sizeof(LNode));
    p = l;
    p=p->next;
    while(p!=NULL){
   
        i++;
        p = p->next;
    }
    return i;
}


//输出
void Print(LinkList l){
    
    LinkList p;
    p=l;
    //cout<<"输出链表！"<<endl;
    //迭代调用
    if(p->next){
   
        p=p->next;
        cout<<p->data<<" ";
        Print(p);
    }
    //普通循环方法输出
    /* while (p->next) { p=p->next; cout<<p->data<<" "; }*/
    
}

int main()
{
   
    LinkList l;
    if(InitList(l))
        cout << "初始化成功！" << endl;
    else
        cout << "初始化失败！" << endl;
    Head_Insert(l);
    //Tail_Insert(l);
    cout << "查的值为：" << Search_Val(l,2)->data << endl;
    Print(l);
    Insert(l,2,3);
    cout<<endl;
    Print(l);
    cout<<endl;
    cout<< "表长为：" << GetLength(l) << endl;
    Delete(l,2);
    Print(l);
    cout<<endl;
    system("pause");
    return 0;
}