首页 > 代码库 > 单链表

单链表

2024-07-06 01:33:38   229人阅读

单链表是一种链式存储结构，它可以通过一组任意的存储单元来存储线性表中的数据元素。

头文件 声明

//
//  linklist.h
//  Datastructure
//
//  Created by zhou on 14-5-25.
//  Copyright (c) 2014年 zhou. All rights reserved.
//

#ifndef __Datastructure__linklist__
#define __Datastructure__linklist__

#include <iostream>

typedef struct Node  //单链表结构体
{
    int data;
    struct Node *next;
    ~Node(){delete next;};
}*linklist;

linklist createList(linklist &L);     //生成一个头结点为L的单链表
void printfL(linklist &L);            //打印单链表
Node *getElem (linklist L,int i);     //获取第i个结点
Node *findElem(linklist L,int data);  //获取值为data的结点
void insertL(linklist L,int index,int x);//在index位置插入值为x的结点
void deleteL(linklist L,int index);     //删除下标为index的结点
int length(linklist L);                 //获取链表长度
#endif /* defined(__Datastructure__linklist__) */

实现

//
//  linklist.cpp
//  Datastructure
//
//  Created by zhou on 14-5-25.
//  Copyright (c) 2014年 zhou. All rights reserved.
//

#include "linklist.h"

linklist createList(linklist &L)  
{
    Node *s,*r;
    int x;
    L = new Node;
    r = L;
    scanf("%d",&x);
    while(x != -1)
    {
        s = new  Node;
        s ->data =http://www.mamicode.com/ x;
        r ->next = s;
        r = s;
        scanf("%d",&x);
    }
    r ->next = NULL;
    return L;
}

void printfL(linklist &L)
{
    Node *p = L->next;
    while(p!= NULL)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

Node *getElem (linklist L,int i)
{
    int j = 1;
    Node *p = L->next;
    if(i==0)
        return L;
    if(i<0)
        return NULL;
    else
    {
        while (j<i&&p!=NULL) {
            p = p->next;
            j++;
        }
    }
    return p;
}

Node *findElem(linklist L,int x)
{
    Node * p = L->next;
    while (p&&p->data != x) {
        p = p->next;
    }
    return p;
}

void insertL(linklist L,int index,int x)
{
    Node *q = getElem(L, index-1);
    Node *p = new Node;
    p->data =http://www.mamicode.com/ x;
    p->next = q->next;
    q->next = p;
}

void deleteL(linklist L,int index)
{
    Node *p = getElem(L, index-1);
    Node *q = p->next;
    p->next = q->next;
    free(q);
}
int length(linklist L)
{
    int len = 0;
    Node *p = L->next;
    if(p==NULL)
        return 0;
    while(p)
    {
        len++;
        p = p->next;
    }
    return len;
}

主函数 测试

//
//  main.cpp
//  Datastructure
//
//  Created by zhou on 14-5-25.
//  Copyright (c) 2014年 zhou. All rights reserved.
//

#include "linklist.h"
#include <iostream>
using namespace std;

int main(int argc, const char * argv[])
{

    // insert code here...
    std::cout << "Hello, World!\n";
    linklist L;
    linklist st = createList(L);
    printfL(st);
    //cout<<sizeof(int)<<endl;
    //cout<<sizeof(L)<<endl;
    //cout<<getElem(L, 3)<<endl;
    //cout<<findElem(L, 4)<<endl;
    insertL(L, 3, 100);
    printfL(L);
    deleteL(L, 2);
    printfL(L);
    cout<<length(L)<<endl;
    return 0;
}

 


联系
我们