数据结构-线性表的链式实现(链式表)

——C版本的链式表实现————

#include <stdio.h>
#include <malloc.h>
#define OK 0
#define ERROR 1

typedef int T;
typedef struct lnode{
    T data;
    struct lnode *next;
}LNode;

LNode* newNode(){
    LNode * p = (LNode *) malloc(sizeof(LNode));
    if(!p) return 0;
    p->next = 0;
    return p;
}

LNode * initLkList(){
   return newNode();    
}

int insertLkList(LNode *L,int i,T e){
   LNode *p = L,*s; int j = 0;
   while(p&&j<i-1){
       p = p ->next; j++;
   }
   if(!p||j>i-1) return ERROR;
   s = newNode();
   s->data =e;
   s->next = p->next;
   p->next = s;
   return OK;
}

int deleteLkList(LNode *L,int i){
   LNode *p = L,*s; int j = 0;
   while(p&&j<i-1){
       p = p ->next; j++;
   }
   if(!p||j>i-1) return ERROR;
   
   if(p->next){
       s = p->next;
       p->next = s->next;
       free(s);
   }
   return OK;
   return OK;
}

int insert_front_LkList(LNode *L,T e){
    LNode *s = newNode();
    s->data = e;
    s->next = L->next;
    L->next = s;
    return OK;
}

int sizeSqList(LNode *L){
    LNode *p = L; int j = 0 ;
    while(p){
        p = p->next; j++;
    }
    return j;
}

void printSqList(LNode *L){
    LNode *p = L->next;
    while(p){
        printf("%d\n",p->data);
        p = p->next; 
    }   
    printf("\n");
}


int main(){
    LNode *L;
    T e;
    L = initLkList();

    e = 10;
    insertLkList(L,1,e);
    e = 20;
    insertLkList(L,3,e);
    printSqList(L);

    insert_front_LkList(L,30);
    insert_front_LkList(L,40);
    insert_front_LkList(L,50);
    printSqList(L);

    deleteLkList(L,2);
    printSqList(L);
}

——C++(引用)版本的链式表实现————

LkLis.h

typedef double ElemType;
typedef int Status;
#define OK 0
#define ERROR 1
typedef struct node{
    ElemType data;
    struct node *next;
}LNode, *LinkList; //LinkList 等价于 LNode* 

bool InitList_L(LinkList &L);
Status GetElem_L(LinkList L, int i, ElemType &e);
Status SetElem_L(LinkList L, int i, ElemType e);
Status ListDelete_L(LinkList &L, int i, ElemType& e);
Status ListInsert_L(LinkList &L, int i, ElemType e);
int ListLength(LinkList L);

LkList.cpp

//#include "LkList.h"

//初始化一个带头结点的单链表
bool InitList_L(LinkList &L){
    L = new LNode();
    if(!L) return false;
    L->next = 0;
    return true;
}
Status GetElem_L(LinkList L, int i, ElemType &e)
{
  LNode *p = L->next;   int j = 1;
  // 循环直到p为空或到了第i个节点
  while(p && j < i) {
    p = p->next;      
    ++ j;
  }
  if(!p || j > i)   // 第i个节点不存在
    return ERROR;
  e = p->data;      // copy数据到e中
  return OK;
}

Status SetElem_L(LinkList L, int i, ElemType e)
{
  LNode *p = L->next;   int j = 1;
  // 循环直到p为空或到了第i个节点
  while(p && j < i) {
    p = p->next;      
    ++ j;
  }
  if(!p || j > i)   // 第i个节点不存在
    return ERROR;
  p->data = e;      // copy e到数据中
  return OK;
}

Status ListInsert_L(LinkList &L, int i, ElemType e)
{
    LNode *p = L;   int j = 0;
    // 寻找第i-1个节点
    while(p && j < i-1){    
        p = p->next;
        ++ j;
    }
    // 若第i-1个节点不存在
    if(!p || j > i-1)
        return ERROR;
    // 生成一个新节点，并链接到L中
    LNode *s = new LNode; //(LNode *) malloc (sizeof(LNode));

    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

Status ListDelete_L(LinkList &L, int i, ElemType& e)
{
    LNode *p = L;   int j = 0;
    // 让p指向第i-1个节点
    while(p && j < i-1){    
        p = p->next;
        ++ j;
    }
    // 若第i个节点不存在
    if(!(p->next) || j > i-1)
        return ERROR;
    LNode *q = p->next;       // q指向待删除节点
    p->next = q->next; // 使q脱离链表
    e = q->data;       // e得到q的数据
    delete q; //free(q);           // 释放q的空间
    return OK;
}

int ListLength(LinkList L){
    LNode *p = L; int j = 0;
    while(p->next){
        j++; p = p->next;
    }
    return j;
}

test.cpp

//#include "LkList.h"
#include <iostream>
using std::cout;
int main(){
    LinkList L;
    ElemType e = 67.8;
    InitList_L(L);
    ListInsert_L(L,1,e);
    e=99;
    ListInsert_L(L,3,e);
    e = 88;
    ListInsert_L(L,1,e);
    e = 33;
    ListInsert_L(L,2,e);
    e=45;
    SetElem_L(L,1,e);

    int length = ListLength(L);
    for(int i = 1 ;i<=length;i++){
        if(GetElem_L(L,i,e)==OK)
            cout<<e<<" ";
    }
    cout<<"\n";
}

赏

支付宝打赏

微信打赏

您的打赏是对我最大的鼓励！

Linked list

——C版本的链式表实现————

——C++(引用)版本的链式表实现————

CATALOG

FEATURED TAGS

FRIENDS