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

Posted by xuepro on November 9, 2017

## ——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;

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);


LkList.cpp

//#include "LkList.h"

//初始化一个带头结点的单链表
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;
}

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(){
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";
}